Gauss Elimination

Motivation:

 

                       Solve the following system equation:

 

                                                

 

                       People might have their own ways to solve this equation.  But is there any consistent way to solve all of this kind of problems?  At least, the existence of a consistent approach would be easier for implementing this method via computer programming.  As a matter of fact, a method was developed by Gauss several hundred years ago although there was no modern computer at that time.

 

 

 

 

 

Gauss Elimination

                                We only write down the coefficients  of equation as follows:

 

                                         1     1       1        2

                                         2     3       1        1

                                         2     1       2        5

 

                             multiplying row 1 by -2 and adding into row 2:

 

                                         1      1        1        2

                                         0      1        -1       -3

                                         2       1       2         5

 

                            multiplying row1 by -2 and adding into row 3:

 

                                          1       1        1         2

                                          0       1        -1        -3

                                          0       -1       0         1

 

                            multiplying row 2 by 1 and adding into row 3:

 

                                          1         1         1         2

                                          0         1        -1        -3

                                          0          0       -1        -2

 

 

 

                          So, we have

                                           x + y + z = 2

                                                 y – z  = -3

                                                     -z  = -2

 

 

                         And from the last equation, back substitution can be used to find out the solution to z, y, and x.  The principle of Gauss elimination is to eliminate the coefficients that are not diagonal line .   There is a variant form of Gauss elimination that is known as Gauss-Jordan Elimination.

 

 

 

Gauss-Jordan Elimination

                         

                                                

                 Similarly, we write down the coefficients as below:

 

                                         1     1       1        2

                                         2     3       1        1

                                         2     1       2        5

 

               

                             multiplying row 1 by -2 and adding into row 2:

 

                                         1      1        1        2

                                         0      1        -1       -3

                                         2       1       2         5

 

                            multiplying row1 by -2 and adding into row 3:

 

                                          1       1        1         2

                                          0       1        -1        -3

                                          0       -1       0         1

 

 

 

                   Up to this moment, it is the same as the previous method. But for the next a few steps, we are trying to use row 2 as much as possible to eliminate the other non-diagonal coefficients.

 

 

 

 

                              multiplying row 2 by 1 and adding into row 1:

 

                                          1         1         1         2

                                          0         1        -1        -3

                                          0          -1       0        1

 

 

                              multiplying row 2 by -1 and adding into row 1:

 

                                           1        0         2          5

                                           0        1         -1        -3

                                           0        -1         0         1

 

                              multiplying row 2 by 1 and adding into row 3:

 

                                          1        0         2          5

                                          0        1         -1        -3

                                          0        0         -1          -2

 

                              multiplying row 3 by 2 and adding into row 1:

 

                                           1        0         0          1

                                           0        1         -1         -3

                                           0        0         -1         -2

 

                              multiplying row 3 by  -1 and adding into row 2:

 

                                           1        0         0          1

                                           0        1         0          -1

                                           0         0        -1         -2

 

                               Thus, we have

                                                      x=1

                                                      y=-1

                                                      z=2

 

                   In general, you can use the method introduced here to check if there exists the solution to a system equation. However, there are many details associated with it.  For example, what if the diagonal element you want to use to eliminate the coefficients in other rows is zero? You might want to perform row permutation from the bottom.

 

                   And there are some other implementation issues when you want to use the computer to solve this kind of question. But the number of significant digits of computer operation is limited.  People usually avoid using the diagonal elements ( known as “pivot” ) that are very small while eliminating the elements in other rows. In this case, row swap is also needed.

 

                Furthermore,  if some of the rows are linearly dependent, the approach is also helpful to determine it.  Those things will be discussed in Linear Algebra systematically to cover all the cases. Here we only introduce some basic ideas and some very simple cases.

 

 

LU Decomposition

 

                Recall the row elementary operation introduced in previous section and the Gauss Elimination process.  When we perform Gauss Elimination, we always multiply the row on the top by some constant and add into the rows on the bottom. As discussed previous, the operation is corresponding to multiply a matrix which is formed by doing the same operation on identity matrix I_n .  So,  for the system equation

 

                                                  

 

                   The matrix representation is

 

                                                Ax=d

 

                                 where  A= ,   x=  ,  d=

 

                    In other words,

 

                                                  =

 

                    While Gauss Elimination is applied, we can consider that the matrix A is multiplied by a series of matrices from the left to perform row operations.  At the end, we obtain a “upper triangular matrix” with elements below the diagonal lines are zero. Since we only perform the row operations from top to bottom, the multiplication of a series of row operation matrices should be equivalent to a matrix with elements above the diagonal line are zero.  Thus, we have

 

                                                          WA=U

 

                                 where  W is a lower triangular matrix like

                                                        

 

                                              U is a upper triangular matrix like

                                                        

 

                       Let’s think further: if we use a matrix to multiply W from the right, what this matrix will be if the result is an identity matrix?  The answer is: this matrix should also be a lower triangular matrix because you can perform row operations again to make W into an identity matrix.  So, in general, we have

 

                                                  A=LU

 

                         where  L is a lower triangular matrix that makes W into identity matrix