Ch. 9.1 Gauss Elimination

System of Linear Equations

Consider a system of linear equations represented in matrix form as:

\[ A x = b \]

where \( A \) is an \( n \times n \) matrix of coefficients, \( x \) is a column vector of \( n \) unknowns, and \( b \) is a column vector of constants. This can be written explicitly as:

\[ \begin{cases} a_{11} x_1 + a_{12} x_2 + \dots + a_{1n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + \dots + a_{2n} x_n = b_2 \\ \vdots \\ a_{n1} x_1 + a_{n2} x_2 + \dots + a_{nn} x_n = b_n \\ \end{cases} \]

Forward Elimination

For each row \( i \) (from 1 to \( n-1 \)), we perform the following operations to create zeros below the pivot element \( a_{ii} \):

• For each row \( j \) below \( i \) (i.e., \( j = i+1, \dots, n \)):
  • Calculate the multiplier: \[ m_{ji} = \frac{a_{ji}}{a_{ii}} \]
  • Update each element in row \( j \) (both in the matrix \( A \) and the vector \( b \)) as follows: \[ a_{jk} = a_{jk} - m_{ji} \cdot a_{ik} \] \[ \text{for all } k = i, i+1, \dots, n \] \[ b_j = b_j - m_{ji} \cdot b_i \]

After completing forward elimination, the matrix \( A \) is transformed into an upper triangular form.

Back Substitution

After forward elimination, we have an upper triangular system, which can be solved for the unknowns starting from the last row and working upward.

The back substitution step can be described as follows:

• Solve for \( x_n \): \[ x_n = \frac{b_n}{a_{nn}} \]
• Solve for \( x_{n-1} \): \[ x_{n-1} = \frac{b_{n-1} - a_{n-1,n} x_n}{a_{n-1,n-1}} \]
• Continue this process until reaching \( x_1 \): \[ x_i = \frac{b_i - \sum_{j=i+1}^n a_{ij} x_j}{a_{ii}} \] \[ \text{for } i = n-1, n-2, \dots, 1 \]

General Formula for \( n \) Unknowns

In general, after forward elimination, the unknown \( x_i \) (for \( i = n, n-1, \dots, 1 \)) can be calculated using:

\[ x_i = \frac{b_i - \sum_{j=i+1}^n a_{ij} x_j}{a_{ii}} \]

This formula gives the value of each unknown by substituting the values obtained from previous calculations into the equation for each \( x_i \) in descending order.

System of Four Equations with Four Unknowns

Let's consider a system of four equations with four unknowns:

\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + a_{14}x_4 = b_1 \\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + a_{24}x_4 = b_2 \\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + a_{34}x_4 = b_3 \\ a_{41}x_1 + a_{42}x_2 + a_{43}x_3 + a_{44}x_4 = b_4 \end{cases} \]

This system can be represented as an augmented matrix:

\[ \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} & \vert & b_1 \\ a_{21} & a_{22} & a_{23} & a_{24} & \vert & b_2 \\ a_{31} & a_{32} & a_{33} & a_{34} & \vert & b_3 \\ a_{41} & a_{42} & a_{43} & a_{44} & \vert & b_4 \\ \end{bmatrix} \]

Step 1: Forward Elimination to Create an Upper Triangular Matrix

The goal is to zero out all elements below the diagonal by row operations.

Step 1.1: Eliminate \( a_{21}, a_{31}, \) and \( a_{41} \) Using Row 1

For \( R_2 \): \( R_2 \rightarrow R_2 - m_{21} R_1 \), where \( m_{21} = \frac{a_{21}}{a_{11}} \).
For \( R_3 \): \( R_3 \rightarrow R_3 - m_{31} R_1 \), where \( m_{31} = \frac{a_{31}}{a_{11}} \).
For \( R_4 \): \( R_4 \rightarrow R_4 - m_{41} R_1 \), where \( m_{41} = \frac{a_{41}}{a_{11}} \).

Step 1.2: Eliminate \( a_{32}' \) and \( a_{42}' \) Using Row 2

For \( R_3 \): \( R_3 \rightarrow R_3 - m_{32} R_2 \), where \( m_{32} = \frac{a_{32}'}{a_{22}'} \).
For \( R_4 \): \( R_4 \rightarrow R_4 - m_{42} R_2 \), where \( m_{42} = \frac{a_{42}'}{a_{22}'} \).

Step 1.3: Eliminate \( a_{43}'' \) Using Row 3

For \( R_4 \): \( R_4 \rightarrow R_4 - m_{43} R_3 \), where \( m_{43} = \frac{a_{43}''}{a_{33}''} \).

Step 2: Back Substitution to Find the Solution

Now that the matrix is in upper triangular form, we can solve for each variable by back substitution.

Solve for \( x_4 \): \( x_4 = \frac{b_4''' }{a_{44}'''} \).
Solve for \( x_3 \): \( x_3 = \frac{b_3'' - a_{34}'' x_4}{a_{33}''} \).
Solve for \( x_2 \): \( x_2 = \frac{b_2' - a_{23}' x_3 - a_{24}' x_4}{a_{22}'} \).
Solve for \( x_1 \): \( x_1 = \frac{b_1 - a_{12} x_2 - a_{13} x_3 - a_{14} x_4}{a_{11}} \).

General Formula for Back Substitution

The general formula for back substitution is given by: \[ x_i = \frac{b_i - \sum_{j=i+1}^n a_{ij} x_j}{a_{ii}} \]

System of Four Equations with Four Unknowns

Let's consider a system of four equations with four unknowns:

\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + a_{14}x_4 = b_1 \\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + a_{24}x_4 = b_2 \\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + a_{34}x_4 = b_3 \\ a_{41}x_1 + a_{42}x_2 + a_{43}x_3 + a_{44}x_4 = b_4 \end{cases} \]

This system can be represented as an augmented matrix:

\[ \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} & | & b_1 \\ a_{21} & a_{22} & a_{23} & a_{24} & | & b_2 \\ a_{31} & a_{32} & a_{33} & a_{34} & | & b_3 \\ a_{41} & a_{42} & a_{43} & a_{44} & | & b_4 \end{bmatrix} \]

Step 1: Forward Elimination to Create an Upper Triangular Matrix

The goal is to zero out all elements below the diagonal by row operations.

Step 1.1: Eliminate \(a_{21}\), \(a_{31}\), and \(a_{41}\) Using Row 1

Pivot Element: Start with \(a_{11}\) as the pivot element in the first row.

Row Operations:

For \( R_2 \): \( R_2 \rightarrow R_2 - m_{21} R_1 \), where \( m_{21} = \frac{a_{21}}{a_{11}} \).
For \( R_3 \): \( R_3 \rightarrow R_3 - m_{31} R_1 \), where \( m_{31} = \frac{a_{31}}{a_{11}} \).
For \( R_4 \): \( R_4 \rightarrow R_4 - m_{41} R_1 \), where \( m_{41} = \frac{a_{41}}{a_{11}} \).

The matrix after these operations will look like:

\[ \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} & | & b_1 \\ 0 & a_{22}' & a_{23}' & a_{24}' & | & b_2' \\ 0 & a_{32}' & a_{33}' & a_{34}' & | & b_3' \\ 0 & a_{42}' & a_{43}' & a_{44}' & | & b_4' \end{bmatrix} \]

Step 1.2: Eliminate \(a_{32}'\) and \(a_{42}'\) Using Row 2

Next, move to the second row and use \(a_{22}'\) as the pivot element.

Row Operations:

For \( R_3 \): \( R_3 \rightarrow R_3 - m_{32} R_2 \), where \( m_{32} = \frac{a_{32}'}{a_{22}'} \).
For \( R_4 \): \( R_4 \rightarrow R_4 - m_{42} R_2 \), where \( m_{42} = \frac{a_{42}'}{a_{22}'} \).

The matrix becomes:

\[ \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} & | & b_1 \\ 0 & a_{22}' & a_{23}' & a_{24}' & | & b_2' \\ 0 & 0 & a_{33}'' & a_{34}'' & | & b_3'' \\ 0 & 0 & a_{43}'' & a_{44}'' & | & b_4'' \end{bmatrix} \]

Step 1.3: Eliminate \(a_{43}''\) Using Row 3

Now, use \(a_{33}''\) as the pivot to eliminate \(a_{43}''\).

Row Operation:

For \( R_4 \): \( R_4 \rightarrow R_4 - m_{43} R_3 \), where \( m_{43} = \frac{a_{43}''}{a_{33}''} \).

The matrix is now in upper triangular form:

\[ \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} & | & b_1 \\ 0 & a_{22}' & a_{23}' & a_{24}' & | & b_2' \\ 0 & 0 & a_{33}'' & a_{34}'' & | & b_3'' \\ 0 & 0 & 0 & a_{44}''' & | & b_4''' \end{bmatrix} \]

Step 2: Back Substitution to Find the Solution

Now that the matrix is in upper triangular form, we can solve for each variable by back substitution.

Solve for \( x_4 \):

\[ x_4 = \frac{b_4'''}{a_{44}'''} \]

Solve for \( x_3 \): Substitute \( x_4 \) into the equation for row 3 to solve for \( x_3 \):

\[ x_3 = \frac{b_3'' - a_{34}'' x_4}{a_{33}''} \]

Solve for \( x_2 \): Substitute \( x_3 \) and \( x_4 \) into row 2 to solve for \( x_2 \):

\[ x_2 = \frac{b_2' - a_{23}' x_3 - a_{24}' x_4}{a_{22}'} \]

Solve for \( x_1 \): Finally, substitute \( x_2 \), \( x_3 \), and \( x_4 \) into row 1 to solve for \( x_1 \):

\[ x_1 = \frac{b_1 - a_{12} x_2 - a_{13} x_3 - a_{14} x_4}{a_{11}} \]

Gaussian Elimination with Partial Pivoting

Consider the following system of equations:

The corresponding augmented matrix A is:

Steps in Gaussian Elimination with Partial Pivoting

Partial Pivoting:

Before eliminating variables, we may need to rearrange the rows of the matrix to ensure numerical stability. If the pivot element is zero, it is impossible to perform the necessary elimination operations. Pivoting helps ensure that we do not divide by zero. The pivoting operation selects the largest absolute value in the current column (from the current row down) to be the pivot. If the current pivot A[k,k] is too small, we swap it with a row below it that contains a larger absolute value:

Forward Elimination:

This process transforms the matrix into an upper triangular form. For each column k, starting from the first column:

• For each row i below row k:

Subtract a multiple of the pivot row from the current row to eliminate the leading coefficient:

Back Substitution:

Once the matrix is in upper triangular form, we can solve for the unknowns starting from the last equation upwards. Given the upper triangular matrix A and the constants b, we solve for x_n first:

We continue substituting back to find all x_i.