Background

    In the Gauss-Jordan module we saw an algorithm for solving a general linear system of equations 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 .  

Theorem (Unique Solutions) Assume that is an matrix.  The following statements are equivalent.

     (i) Given any matrix , the linear system has a unique solution.
     
    (ii) The matrix is nonsingular (i.e., exists).
    
   (iii) The system of equations has the unique solution .  
   
   (iv) The determinant of is nonzero, i.e. .  

    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.

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

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.  

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

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 .  

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

Pivoting Strategies

    There are numerous pivoting strategies discussed in the literature.  We mention only a few to give an indication of the possibilities.

(i)  No Pivoting.  No pivoting means no row interchanges.  It can be done only if Gaussian elimination never run into zeros on the diagonal.  Since division by zero is a fatal error we usually avoid this pivoting strategy.

Pivoting to Avoid

    If  ,  then row p cannot be used to eliminate the elements in column p below the main diagonal.  It is necessary to find row k, where and k > p, and then interchange row p and row k so that a nonzero pivot element is obtained.  This process is called pivoting, and the criterion for deciding which row to choose is called a pivoting strategy.  The first idea that comes to mind is the following one.

(ii) Trivial Pivoting.  The trivial pivoting strategy is as follows.  If  ,  do not switch rows.  If  ,  locate the first row below p in which   and then switch rows k and p.  This will result in a new element  ,  which is a nonzero pivot element.

Pivoting to Reduce Error

    Because the computer uses fixed-precision arithmetic, it is possible that a small error will be introduced each time that an arithmetic operation is performed. The following example illustrates how use of the trivial pivoting strategy in Gaussian elimination can lead to significant error in the solution of a linear system of equations.

(iii) Partial Pivoting.  The partial pivoting strategy is as follows.  If  ,  do not switch rows.  If  ,  locate row u below p in which    and and then switch rows u and p.  This will result in a new element  ,  which is a nonzero pivot element.        
Remark. Only row permutations are permitted. The strategy is to switch the largest entry in the pivot column to the diagonal.

(iv) Scaled Partial Pivoting.  At the start of the procedure we compute scale factors for each row of the matrix as follows:
           for  .  
The scale factors are interchanged with their corresponding row in the elimination steps.  The scaled partial pivoting strategy is as follows.  If  ,  do not switch rows.  If  ,  locate row u below p in which    and and then switch rows u and p.  This will result in a new element  ,  which is a nonzero pivot element.   
Remark. Only row permutations are permitted. The strategy is to switch the largest scaled entry in the pivot column to the diagonal.

(v) Total Pivoting.  The total pivoting strategy is as follows.  If  ,  do not switch rows.  If  ,  locate row u below p and column v to the right of p in which    and and then: first switch rows u and p and second switch column v and p.   This will result in a new element  ,  which is a nonzero pivot element.  This is also called "complete pivoting" or "maximal pivoting."
Remark. Both row and column permutations are permitted. The strategy is to switch the largest entry in the part of the matrix that we have not yet processed to the diagonal.

Proof  Pivoting Methods

Computer Programs  Pivoting Methods

Mathematica Subroutines for Pivoting.  Execute the cells in this group to activate to subroutines.  

Example 1.  Use the Gaussian elimination methods to solve  .  Use the trivial, partial scaled partial and total pivoting strategies.
Solution 1.

Example 2. Use the Gaussian elimination methods to solve  .  Use the trivial, partial scaled partial and total pivoting strategies.
Solution 2.

    A linear system with a Hilbert matrix     is difficult to solve numerically. The following examples illustrate this situation.  

Example 3. Use the Gaussian elimination methods to solve  ,  where is the Hilbert matrix and  .  Use the trivial, partial scaled partial and total pivoting strategies.
Solution 3.

Example 4. Use the Gaussian elimination methods to solve  ,  where is the Hilbert matrix and  .  Use the trivial, partial scaled partial and total pivoting strategies.
Solution 4.

Example 5. Use the Gaussian elimination methods to solve  ,  where is the Hilbert matrix and  .  Use the trivial, partial scaled partial and total pivoting strategies.
Solution 5.

Example 6. Use the Gaussian elimination methods to solve  ,  where is the Hilbert matrix and  .  Use the trivial, partial scaled partial and total pivoting strategies.
Solution 6.

Example 7. Use the Gaussian elimination methods to solve  ,  where is the Hilbert matrix and  .  Use the trivial, partial scaled partial and total pivoting strategies.
Solution 7.

Example 8 Use the Gaussian elimination methods to solve  ,  where is the Hilbert matrix and  .  Use the trivial, partial scaled partial and total pivoting strategies.
Solution 8.

Research Experience for Undergraduates

Pivoting Methods  Internet hyperlinks to web sites and a bibliography of articles.  

Hilbert Matrix  Internet hyperlinks to web sites and a bibliography of articles.  

Ill-Conditioned Linear Systems  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Pivoting Methods

(c) John H. Mathews 2005