Module

for

Gauss-Jordan Elimination

     

    In this module we develop a algorithm for solving a general linear system of equations [Graphics:Images/GaussianJordanMod_gr_1.gif] consisting of n equations and n unknowns where it is assumed that the system has a unique solution.  The method is attributed Johann Carl Friedrich Gauss (1777-1855) and Wilhelm Jordan (1842 to 1899).  The following theorem states the sufficient conditions for the existence and uniqueness of solutions of a linear system [Graphics:Images/GaussianJordanMod_gr_2.gif].  

Theorem (Unique Solutions) Assume that [Graphics:Images/GaussianJordanMod_gr_3.gif] is an [Graphics:Images/GaussianJordanMod_gr_4.gif] matrix.  The following statements are equivalent.

     (i) Given any [Graphics:Images/GaussianJordanMod_gr_5.gif] matrix [Graphics:Images/GaussianJordanMod_gr_6.gif], the linear system [Graphics:Images/GaussianJordanMod_gr_7.gif] has a unique solution.
     
    (ii) The matrix [Graphics:Images/GaussianJordanMod_gr_8.gif] is nonsingular (i.e., [Graphics:Images/GaussianJordanMod_gr_9.gif] exists).
    
   (iii) The system of equations [Graphics:Images/GaussianJordanMod_gr_10.gif] has the unique solution [Graphics:Images/GaussianJordanMod_gr_11.gif].  
   
   (iv) The determinant of [Graphics:Images/GaussianJordanMod_gr_12.gif] is nonzero, i.e. [Graphics:Images/GaussianJordanMod_gr_13.gif].  

    It is convenient to store all the coefficients of the linear system [Graphics:Images/GaussianJordanMod_gr_14.gif] in one array of dimension [Graphics:Images/GaussianJordanMod_gr_15.gif].  The coefficients of [Graphics:Images/GaussianJordanMod_gr_16.gif] are stored in column [Graphics:Images/GaussianJordanMod_gr_17.gif] of the array (i.e. [Graphics:Images/GaussianJordanMod_gr_18.gif]).  Row [Graphics:Images/GaussianJordanMod_gr_19.gif] contains all the coefficients necessary to represent the [Graphics:Images/GaussianJordanMod_gr_20.gif] equation in the linear system. The augmented matrix is denoted [Graphics:Images/GaussianJordanMod_gr_21.gif] and the linear system is represented as follows:

         [Graphics:Images/GaussianJordanMod_gr_22.gif][Graphics:Images/GaussianJordanMod_gr_23.gif]  

    The system [Graphics:Images/GaussianJordanMod_gr_24.gif], with augmented matrix [Graphics:Images/GaussianJordanMod_gr_25.gif], can be solved by performing row operations on [Graphics:Images/GaussianJordanMod_gr_26.gif].  The variables  are placeholders for the coefficients and cam be omitted until the end of the computation.

Proof  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

 

Theorem (Elementary Row Operations). The following operations applied to the augmented matrix [Graphics:Images/GaussianJordanMod_gr_27.gif] 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:  [Graphics:Images/GaussianJordanMod_gr_28.gif].      

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

Proof  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

 

Definition (Pivot Element). The number [Graphics:Images/GaussianJordanMod_gr_29.gif] in the coefficient matrix [Graphics:Images/GaussianJordanMod_gr_30.gif] that is used to eliminate [Graphics:Images/GaussianJordanMod_gr_31.gif] where [Graphics:Images/GaussianJordanMod_gr_32.gif], is called the [Graphics:Images/GaussianJordanMod_gr_33.gif] pivot element, and the [Graphics:Images/GaussianJordanMod_gr_34.gif] row is called the pivot row.      

 

Theorem (Gaussian Elimination with Back Substitution). Assume that [Graphics:Images/GaussianJordanMod_gr_35.gif] is an [Graphics:Images/GaussianJordanMod_gr_36.gif] nonsingular matrix. There exists a unique system [Graphics:Images/GaussianJordanMod_gr_37.gif] that is equivalent to the given system [Graphics:Images/GaussianJordanMod_gr_38.gif], where [Graphics:Images/GaussianJordanMod_gr_39.gif] is an upper-triangular matrix with [Graphics:Images/GaussianJordanMod_gr_40.gif] for [Graphics:Images/GaussianJordanMod_gr_41.gif].  After  [Graphics:Images/GaussianJordanMod_gr_42.gif] are constructed, back substitution can be used to solve [Graphics:Images/GaussianJordanMod_gr_43.gif] for [Graphics:Images/GaussianJordanMod_gr_44.gif].  

Proof  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

 

Algorithm I. (Limited Gauss-Jordan Elimination).  Construct the solution to the linear system  [Graphics:Images/GaussianJordanMod_gr_45.gif]  by using Gauss-Jordan elimination under the assumption that row interchanges are not needed.  The following subroutine uses row operations to eliminate  [Graphics:Images/GaussianJordanMod_gr_46.gif]  in column  p  for  [Graphics:Images/GaussianJordanMod_gr_47.gif].

Computer Programs  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

Mathematica Subroutine (Limited Gauss-Jordan Elimination).

[Graphics:Images/GaussianJordanMod_gr_48.gif]

Example 1. Use the Gauss-Jordan elimination method to solve the linear system  [Graphics:Images/GaussianJordanMod_gr_49.gif].  
Solution 1.

Example 2. Interchange rows 2 and 3 and try to use the Gauss-Jordan subroutine to solve [Graphics:Images/GaussianJordanMod_gr_71.gif].  
Use lists in the subscript to select rows 2 and 3 and perform the row interchange.
Solution 2.

 

Provide for row interchanges in the Gauss-Jordan subroutine.

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

[Graphics:Images/GaussianJordanMod_gr_86.gif]

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  [Graphics:Images/GaussianJordanMod_gr_87.gif]  by using Gauss-Jordan elimination.  Provision is made for row interchanges if they are needed.  

Computer Programs  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

Mathematica Subroutine (Complete Gauss-Jordan Elimination).

[Graphics:Images/GaussianJordanMod_gr_88.gif]

Example 3. Use the improved Gauss-Jordan elimination subroutine with row interchanges to solve [Graphics:Images/GaussianJordanMod_gr_89.gif].  
Use the matrix A and vector B in Example 2.
Solution 3.

Example 4. Use the Gauss-Jordan elimination method to solve the linear system  [Graphics:Images/GaussianJordanMod_gr_116.gif].  
Solution 4.

 

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

Theorem (Inverse Matrix) Assume that [Graphics:Images/GaussianJordanMod_gr_152.gif] is an [Graphics:Images/GaussianJordanMod_gr_153.gif] nonsingular matrix. Form the augmented matrix [Graphics:Images/GaussianJordanMod_gr_154.gif] of dimension  [Graphics:Images/GaussianJordanMod_gr_155.gif].  Use Gauss-Jordan elimination to reduce the matrix [Graphics:Images/GaussianJordanMod_gr_156.gif] so that the identity [Graphics:Images/GaussianJordanMod_gr_157.gif] is in the first [Graphics:Images/GaussianJordanMod_gr_158.gif] columns.  Then the inverse [Graphics:Images/GaussianJordanMod_gr_159.gif] is located in columns [Graphics:Images/GaussianJordanMod_gr_160.gif].       

Proof  The Inverse Matrix  The Inverse Matrix  

 

Example 5. Use Gauss-Jordan elimination to find the inverse of the matrix  [Graphics:Images/GaussianJordanMod_gr_161.gif].
Solution 5.

 

Algorithm III. (Concise Gauss-Jordan Elimination).  Construct the solution to the linear system  [Graphics:Images/GaussianJordanMod_gr_195.gif]  by using Gauss-Jordan elimination.  The print statements are for pedagogical purposes and are not needed.  

Computer Programs  Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  

Mathematica Subroutine (Concise Gauss-Jordan Elimination).

[Graphics:Images/GaussianJordanMod_gr_196.gif]

Remark. The Gauss-Jordan elimination method is the "heuristic" scheme found in most linear algebra textbooks.  The line of code
        [Graphics:Images/GaussianJordanMod_gr_197.gif]
divides each entry in the pivot row by its leading coefficient [Graphics:Images/GaussianJordanMod_gr_198.gif].  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 [Graphics:Images/GaussianJordanMod_gr_199.gif];  

        [Graphics:Images/GaussianJordanMod_gr_200.gif].

For each point  [Graphics:Images/GaussianJordanMod_gr_201.gif]  is used to an equation  [Graphics:Images/GaussianJordanMod_gr_202.gif],  which in turn are used to write a system of six equations in six unknowns  [Graphics:Images/GaussianJordanMod_gr_203.gif]  

        

[Graphics:Images/GaussianJordanMod_gr_204.gif]

[Graphics:Images/GaussianJordanMod_gr_205.gif]

[Graphics:Images/GaussianJordanMod_gr_206.gif]

[Graphics:Images/GaussianJordanMod_gr_207.gif]

[Graphics:Images/GaussianJordanMod_gr_208.gif]

[Graphics:Images/GaussianJordanMod_gr_209.gif]

=

[Graphics:Images/GaussianJordanMod_gr_210.gif]

[Graphics:Images/GaussianJordanMod_gr_211.gif]

[Graphics:Images/GaussianJordanMod_gr_212.gif]

[Graphics:Images/GaussianJordanMod_gr_213.gif]

[Graphics:Images/GaussianJordanMod_gr_214.gif]

[Graphics:Images/GaussianJordanMod_gr_215.gif]

[Graphics:Images/GaussianJordanMod_gr_216.gif]

=

[Graphics:Images/GaussianJordanMod_gr_217.gif]

[Graphics:Images/GaussianJordanMod_gr_218.gif]

[Graphics:Images/GaussianJordanMod_gr_219.gif]

[Graphics:Images/GaussianJordanMod_gr_220.gif]

[Graphics:Images/GaussianJordanMod_gr_221.gif]

[Graphics:Images/GaussianJordanMod_gr_222.gif]

[Graphics:Images/GaussianJordanMod_gr_223.gif]

=

[Graphics:Images/GaussianJordanMod_gr_224.gif]

[Graphics:Images/GaussianJordanMod_gr_225.gif]

[Graphics:Images/GaussianJordanMod_gr_226.gif]

[Graphics:Images/GaussianJordanMod_gr_227.gif]

[Graphics:Images/GaussianJordanMod_gr_228.gif]

[Graphics:Images/GaussianJordanMod_gr_229.gif]

[Graphics:Images/GaussianJordanMod_gr_230.gif]

=

[Graphics:Images/GaussianJordanMod_gr_231.gif]

[Graphics:Images/GaussianJordanMod_gr_232.gif]

[Graphics:Images/GaussianJordanMod_gr_233.gif]

[Graphics:Images/GaussianJordanMod_gr_234.gif]

[Graphics:Images/GaussianJordanMod_gr_235.gif]

[Graphics:Images/GaussianJordanMod_gr_236.gif]

[Graphics:Images/GaussianJordanMod_gr_237.gif]

=

[Graphics:Images/GaussianJordanMod_gr_238.gif]

[Graphics:Images/GaussianJordanMod_gr_239.gif]

[Graphics:Images/GaussianJordanMod_gr_240.gif]

[Graphics:Images/GaussianJordanMod_gr_241.gif]

[Graphics:Images/GaussianJordanMod_gr_242.gif]

[Graphics:Images/GaussianJordanMod_gr_243.gif]

[Graphics:Images/GaussianJordanMod_gr_244.gif]

=

[Graphics:Images/GaussianJordanMod_gr_245.gif]

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

        
[Graphics:Images/GaussianJordanMod_gr_246.gif]

Solve this linear system for the coefficients  [Graphics:Images/GaussianJordanMod_gr_247.gif]   and then construct the interpolating polynomial

        [Graphics:Images/GaussianJordanMod_gr_248.gif].  

 

Example 6. Find the polynomial  p[x]  that passes through the six points  [Graphics:Images/GaussianJordanMod_gr_249.gif]  using the following steps.
(a). Write down the linear system MC = B to be solved.
(b). Solve the linear system for the coefficients [Graphics:Images/GaussianJordanMod_gr_250.gif] using our Gauss-Jordan subroutine.
(c). Construct the polynomial  p[x].
Solution 6.

 

Old Lab Project (Gauss-Jordan Elimination  Gauss-Jordan Elimination).  Internet hyperlinks to an old lab project.  

Research Experience for Undergraduates

Gauss-Jordan Elimination and Pivoting  Gauss-Jordan Elimination and Pivoting  Internet hyperlinks to web sites and a bibliography of articles.  

 

Download this Mathematica Notebook Gauss-Jordan Elimination

 

Return to Numerical Methods - Numerical Analysis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2004