Ch7.3 Gauss Elimination

A system of linear equations has the following form, and can be expressed in matrix-vector form \( A\mathbf{x} = \mathbf{b} \):

\[ \matrix{ x_1 & + & 2x_2 & = & 5 \cr 3x_1 & - & 4 x_2 & = & 6 } \, \, \Leftrightarrow \begin{bmatrix} 1 & 2 \\ 3 & -4 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 5 \\ 6 \end{bmatrix} \]

Alternatively, we can express the system as an augmented matrix; this is common when solving by hand.

\[ \matrix{ x_1 & + & 2x_2 & = & 5 \cr 3x_1 & - & 4 x_2 & = & 6 } \, \, \Leftrightarrow \begin{bmatrix} 1 & 2 & 5 \\ 3 & -4 & 6 \end{bmatrix} \]

Sometimes I tuck my knees into my chest and lean forward.

That's just how I roll.

• Add to get third line (pivot operation).
  
• To save space, third line often replaces one of the other lines.
• The sum of two lines (green) preserves solution.
• This green line is a pivoted version of the second line.

• Use elementary row operations to transform the matrix into upper triangular form.
  
• Be sure to label your row operations as in previous examples.

A = [1 -3 2 6;-2 7 -8 -19;3 -5 -9 -9];
[L,U,P] = lu(A)

L =

   1.0000        0        0
  -0.6667   1.0000        0
   0.3333  -0.3636   1.0000

U =

    3.0000   -5.0000   -9.0000   -9.0000
         0    3.6667  -14.0000  -25.0000
         0         0   -0.0909   -0.0909

P =

Permutation Matrix

   0   0   1
   0   1   0
   1   0   0

A = [1 -3 2 6;-2 7 -8 -19;3 -5 -9 -9]
rref(A)

A =

    1   -3    2    6
   -2    7   -8  -19
    3   -5   -9   -9

ans =

   1.0000        0        0  -5.0000
        0   1.0000        0  -3.0000
        0        0   1.0000   1.0000

• Use elementary row operations to transform the matrix into upper triangular form.
  
• Be sure to label your row operations as in previous examples.

A = [1 2 -4;2 6 -6;4 3 -15];
[L,U,P] = lu(A)

L =

   1.0000        0        0
   0.5000   1.0000        0
   0.2500   0.2778   1.0000

U =

    4.0000    3.0000  -15.0000
         0    4.5000    1.5000
         0         0   -0.6667

P =

Permutation Matrix

   0   0   1
   0   1   0
   1   0   0

Ab = [1 2 -4 5;2 6 -6 8;4 3 -15 13]
rref(Ab)

Ab =

    1    2   -4    5
    2    6   -6    8
    4    3  -15   13

ans =

   1.0000        0        0  -5.0000
        0   1.0000        0   1.0000
        0        0   1.0000  -2.0000

\[ \scriptsize{ \begin{align} & &\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & | & a_{1,n+1} \\ a_{21} & a_{22} & \cdots & a_{2n} & | & a_{2,n+1} \\ \vdots & \vdots & \ddots & \vdots & | & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & | & a_{n,n+1} \end{bmatrix} & \begin{matrix} R_2 = R_2 - \frac{a_{21}}{a_{11}}R_1 \\ \vdots \\ R_n = R_n - \frac{a_{n1}}{a_{11}}R_1 \end{matrix} \\ \\ & \rightarrow & \begin{bmatrix} a_{11}^{(2)} & a_{12}^{(2)} & \cdots & a_{1n}^{(2)} & | & a_{1,n+1}^{(2)} \\ 0 & a_{22}^{(2)} & \cdots & a_{2n}^{(2)} & | & a_{2,n+1}^{(2)} \\ \vdots & \vdots & \ddots & \vdots & | & \vdots \\ 0 & a_{n2}^{(2)} & \cdots & a_{nn}^{(2)} & | & a_{n,n+1}^{(2)} \\ \end{bmatrix} & \begin{array} {llll} a_{1j}^{(2)} = a_{1j}^{(1)}, \, \, j = 1, \ldots, n+1 \\ a_{k1}^{(2)} = 0, \, \, \, \, \, \, k = 1, \ldots, n \\ a_{kj}^{(2)} = a_{kj}^{(1)} - m_{k1} \cdot a_{1j}^{(1)} \\ m_{k1} = \frac{a_{k1}^{(1)}}{a_{11}^{(1)}}, \, \, a_{11}^{(1)} \neq 0 \end{array} \end{align} } \]

\[ \scriptsize{ \begin{bmatrix} a_{11}^{(k)} & a_{12}^{(k)} & \cdots & a_{1,k-1}^{(k)} & a_{1,k}^{(k)} & \cdots & a_{1n}^{(k)} & | & a_{1,n+1}^{(k)} \\ 0 & a_{22}^{(k)} & \cdots & a_{2,k-1}^{(k)} & a_{2,k}^{(k)} & \cdots & a_{2,n}^{(k)} & | & a_{2,n+1}^{(k)} \\ 0 & 0 & \ddots & \vdots & \vdots & \cdots & \vdots & | & \vdots \\ 0 & 0 & \cdots & a_{k-1,k-1}^{(k)} & a_{k-1,k}^{(k)} & \cdots & a_{k-1,n}^{(k)} & | & a_{k-1,n+1}^{(k)} \\ 0 & 0 & \cdots & 0 & a_{k,k}^{(k)} & \cdots & a_{k,n}^{(k)} & | & a_{k,n+1}^{(k)} \\ 0 & 0 & \cdots & 0 & a_{k+1,k}^{(k)} & \cdots & a_{k+1,n}^{(k)} & | & a_{k+1,n+1}^{(k)} \\ 0 & 0 & \cdots & \vdots & \vdots & \cdots & \vdots & | & \vdots \\ 0 & 0 & \cdots & 0 & a_{n,k}^{(k)} & \cdots & a_{n.n}^{(k)} & | & a_{n,n+1}^{(k)} \\ \end{bmatrix}} \]

\[ \scriptsize{ \begin{array} {llll} a_{ij}^{(k)} & = & a_{ij}^{(k-1)}, & 1 \leq i \leq k-1, & 1 \leq j \leq n+1 \\ a_{ij}^{(k)} & = & 0, & k \leq i \leq n, & 1 \leq j \leq k-1 \\ a_{ij}^{(k)} & = & a_{ij}^{(k-1)} - m_{i,k-1} \cdot a_{k-1,j}^{(k-1)}, & k \leq i \leq n, & k \leq j \leq n+1 \\ m_{i,k-1} & = & \frac{a_{i,k-1}^{(k-1)}}{a_{k-1,k-1}^{(k-1)}}, & {a_{k-1,k-1}^{(k-1)}} \neq 0 & k \leq i \leq n \end{array} } \]

\[ \scriptsize{ \begin{bmatrix} a_{11}^{(n)} & a_{12}^{(n)} & \cdots & a_{1,k}^{(n)} & \cdots & a_{1n}^{(n)} & | & a_{1,n+1}^{(n)} \\ 0 & a_{22}^{(n)} & \cdots & a_{2,k}^{(n)} & \cdots & a_{2,n}^{(n)} & | & a_{2,n+1}^{(n)} \\ 0 & 0 & \ddots & \vdots & \ddots & \vdots & | & \vdots \\ 0 & 0 & \cdots & a_{k,k}^{(n)} & \cdots & a_{k,n}^{(n)} & | & a_{k,n+1}^{(n)} \\ \vdots & \vdots & \cdots & \vdots & \ddots & \vdots & | & \vdots \\ 0 & 0 & \cdots & 0 & \cdots & a_{n,n}^{(n)} & | & a_{n,n+1}^{(n)} \\ \end{bmatrix} } \]

\[ \scriptsize{ \begin{array}{rcrcccccccc} a_{11}^{(n)}x_1 & + & a_{12}^{(n)}x_2 & + & \cdots & + & a_{1k}^{(n)}x_k & + & \cdots & + & a_{1n}^{(n)}x_n & = & a_{1,n+1}^{(n)} \\ 0x_1 & + & a_{22}^{(n)}x_{2} & + & \cdots & + & a_{2k}^{(n)}x_k & + & \cdots & + & a_{2,n}^{(n)}x_n & = & a_{2,n+1}^{(n)} \\ 0x_1 & + & 0x_{2} & + & \cdots & \vdots &\vdots &\vdots & \cdots & \vdots & \vdots & = & \vdots \\ 0x_1 & + & 0x_{2} & + & \cdots & + & a_{kk}^{(n)}x_k & + & \cdots & + & a_{k,n}^{(n)}x_n & = & a_{k,n+1}^{(n)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \cdots &\cdots &\ddots & \vdots & \vdots & = & \vdots \\ 0x_1 & + & 0x_{2} & + & \cdots & + & 0x_k & + & \cdots & + & a_{n,n}^{(n)}x_n & = & a_{n,n+1}^{(n)} \\ \end{array} } \]

• The method fails if one of the pivots \( \small{ a_{11}^{(1)}, a_{22}^{(2)},\ldots, a_{nn}^{(n)}} \) is zero.
• In this case, use a row switch during row operations stage.
• Otherwise, the solution is found using back substitution:

\[ \scriptsize{ \begin{aligned} x_n & = \frac{a_{n,n+1}^{(n)}}{a_{n,n}^{(n)}} \\ x_i & = \frac{ a_{i,n+1}^{(n)}-a_{i,n}^{(n)}x_n-a_{i,n-1}^{(n)}x_{n-1} -\ldots-a_{i,i+1}^{(n)}x_{i+1} } {a_{i,i}^{(n)}} \\ & = \frac{ a_{i,n+1}^{(n)}- \sum_{j \, = \, i+1}^n a_{i,j}^{(n)}x_j }{a_{i,i}^{(n)}}, \,\, i = n-1, n-2, \ldots, 1 \end{aligned} } \]

Use elementary row operations to transform the matrix into upper triangular form. Do not use row switches.

Find the matrices \( L \) and \( U \) for which \( A = LU \).

Find the matrices \( L \) and \( U \) for which \( A = LU \).

Use back substitution to solve for \( x_3, x_2, x_1 \) (in this order).

Ab = [2 3 1 2;-6 -10 1 -6;4 5 8 6]
rref(Ab)

Ab =

    2    3    1    2
   -6  -10    1   -6
    4    5    8    6

ans =

   1.0000        0        0  -5.5000
        0   1.0000        0   4.0000
        0        0   1.0000   1.0000

A = [2 3 1;-6 -10 1;4 5 8];
[L,U,P] = lu(A)

L =

   1.0000        0        0
  -0.6667   1.0000        0
  -0.3333   0.2000   1.0000

U =

   -6.0000  -10.0000    1.0000
         0   -1.6667    8.6667
         0         0   -0.4000

P =

Permutation Matrix

   0   1   0
   0   0   1
   1   0   0

Use Octave to check that \( A = LU \).

A = [2 3 1;-6 -10 1;4 5 8]
[L,U] = lu(A);
A1 = L*U

A =

    2    3    1
   -6  -10    1
    4    5    8

A1 =

    2.0000    3.0000    1.0000
   -6.0000  -10.0000    1.0000
    4.0000    5.0000    8.0000

Use elementary row operations to transform the matrix into upper triangular form. Do not use row switches.

Find the matrices \( L \) and \( U \) for which \( A = LU \).

Find the matrices \( L \) and \( U \) for which \( A = LU \).

Use back substitution to solve for \( x_3, x_2, x_1 \) (in this order).

Ab = [3 2 1 0;3 3 3 1;-12 -10 -5 4]
rref(Ab)

Ab =

    3    2    1    0
    3    3    3    1
  -12  -10   -5    4

ans =

   1.0000        0        0   1.3333
        0   1.0000        0  -3.0000
        0        0   1.0000   2.0000

A = [3 2 1;3 3 3;-12 -10 -5];
[L,U,P] = lu(A)

L =

   1.0000        0        0
  -0.2500   1.0000        0
  -0.2500  -1.0000   1.0000

U =

  -12.0000  -10.0000   -5.0000
         0    0.5000    1.7500
         0         0    1.5000

P =

Permutation Matrix

   0   0   1
   0   1   0
   1   0   0

Use Octave to check that \( A = LU \).

A = [3 2 1;3 3 3;-12 -10 -5]
[L,U] = lu(A);
A1 = L*U

A =

    3    2    1
    3    3    3
  -12  -10   -5

A1 =

    3    2    1
    3    3    3
  -12  -10   -5