Gauss-Jordan Elimination

    It is convenient to store all the coefficients of the linear system in one array of dimension .  The coefficients of are stored in column of the array (i.e. ).  Row contains all the coefficients necessary to represent the equation in the linear system. The augmented matrix is denoted and the linear system is represented as follows:

           

    The system , with augmented matrix , can be solved by performing row operations on .  The variables  are placeholders for the coefficients and cam be omitted until the end of the computation.

Theorem ( Elementary Row Operations ). The following operations applied to the augmented matrix yield an equivalent linear system.

     (i) Interchanges:    The order of two rows can be interchanged.  
     
    (ii) Scaling:       Multiplying a row by a nonzero constant.
    
   (iii) Replacement:    Row r can be replaced by the sum of that tow and a nonzero multiple of any other row;
                               that is:  .      

    It is common practice to implement (iii) by replacing a row with the difference of that row and a multiple of another row.  

 

Definition ( Pivot Element ). The number in the coefficient matrix that is used to eliminate where , is called the pivot element, and the row is called the pivot row.      

 

Theorem ( Gaussian Elimination with Back Substitution ). Assume that is an nonsingular matrix. There exists a unique system that is equivalent to the given system , where is an upper-triangular matrix with for .  After   are constructed, back substitution can be used to solve for .  

Algorithm I. (Limited Gauss-Jordan Elimination).  Construct the solution to the linear system    by using Gauss-Jordan elimination under the assumption that row interchanges are not needed.  The following subroutine uses row operations to eliminate    in column  p  for  .

Mathematica Subroutine (Limited Gauss-Jordan Elimination).

 

Provide for row interchanges in the Gauss-Jordan subroutine.

Add the following loop that will interchange rows and perform partial pivoting.

To make these changes, copy your subroutine GaussJordan and place a copy below. Then you can copy the above lines by selecting them and then use the "Edit" and "Copy" menus. The improved Gauss-Jordan subroutine should look like this (blue is for placement information only).  Or just use the active Mathematica code given below.

 

Algorithm II. (Complete Gauss-Jordan Elimination).  Construct the solution to the linear system    by using Gauss-Jordan elimination.  Provision is made for row interchanges if they are needed.  

Mathematica Subroutine (Complete Gauss-Jordan Elimination).

 

Use the subroutine "GaussJordan" to find the inverse of a matrix.

Theorem ( Inverse Matrix ) Assume that is an nonsingular matrix. Form the augmented matrix of dimension  .  Use Gauss-Jordan elimination to reduce the matrix so that the identity is in the first columns.  Then the inverse is located in columns .       

 

Algorithm III. (Concise Gauss-Jordan Elimination).nbsp; Construct the solution to the linear system    by using Gauss-Jordan elimination.  The print statements are for pedagogical purposes and are not needed.  

Mathematica Subroutine (Concise Gauss-Jordan Elimination).

Remark. The Gauss-Jordan elimination method is the "heuristic" scheme found in most linear algebra textbooks.  The line of code
        
divides each entry in the pivot row by its leading coefficient .  Is this step necessary?  A more computationally efficient algorithm will be studied which uses upper-triangularization followed by back substitution.  The partial pivoting strategy will also be employed, which reduces propagated error and instability.

 

Application to Polynomial Interpolation

    Consider a polynomial of degree n=5 that passes through the six points ;  

        .

For each point    is used to an equation  ,  which in turn are used to write a system of six equations in six unknowns    

        

						=
						=
						=
						=
						=
						=

 

The above system can be written in matrix form  MC = B  

        

Solve this linear system for the coefficients     and then construct the interpolating polynomial

        .