Module

for

Forward Substitution and Back Substitution

     

Background

    We will now develop the back-substitution algorithm, which is useful for solving a linear system of equations that has an upper-triangular coefficient matrix.

Definition (Upper-Triangular Matrix).  An [Graphics:Images/BackSubstitutionMod_gr_1.gif] matrix [Graphics:Images/BackSubstitutionMod_gr_2.gif] is called upper-triangular provided that the elements satisfy [Graphics:Images/BackSubstitutionMod_gr_3.gif] whenever [Graphics:Images/BackSubstitutionMod_gr_4.gif].  

    If A is an upper-triangular matrix, then [Graphics:Images/BackSubstitutionMod_gr_5.gif] is said to be an upper-triangular system of linear equations.  

(1)    [Graphics:Images/BackSubstitutionMod_gr_6.gif]    

 

Theorem (Back Substitution).  Suppose that  [Graphics:Images/BackSubstitutionMod_gr_7.gif]  is an upper-triangular system with the form given above in (1).  If  [Graphics:Images/BackSubstitutionMod_gr_8.gif] for [Graphics:Images/BackSubstitutionMod_gr_9.gif] then there exists a unique solution.

Proof  Triangular Systems and Back Substitution  Triangular Systems and Back Substitution  

 

The back substitution algorithm.  To solve the upper-triangular system [Graphics:Images/BackSubstitutionMod_gr_10.gif] by the method of back-substitution. Proceed with the method only if all the diagonal elements are nonzero. First compute  

    [Graphics:Images/BackSubstitutionMod_gr_11.gif]  

and then use the rule  

    [Graphics:Images/BackSubstitutionMod_gr_12.gif]   for  [Graphics:Images/BackSubstitutionMod_gr_13.gif]
    
Or, use the "generalized rule"  

    [Graphics:Images/BackSubstitutionMod_gr_14.gif]   for  [Graphics:Images/BackSubstitutionMod_gr_15.gif]

where the "understood convention" is that [Graphics:Images/BackSubstitutionMod_gr_16.gif] is an "empty summation" because the lower index of summation is greater than the upper index of summation.

Remark. The loop control structure will permit us to use one formula.  

 

Computer Programs  Triangular Systems and Back Substitution  Triangular Systems and Back Substitution  

Mathematica Subroutine (Back Substitution).

[Graphics:Images/BackSubstitutionMod_gr_17.gif]

Pedagogical version for "printing all the details."

[Graphics:Images/BackSubstitutionMod_gr_18.gif]

Example 1 (a). Use the back-substitution method to solve the upper-triangular linear system  [Graphics:Images/BackSubstitutionMod_gr_19.gif].  

Example 1 (b). Use the back-substitution method to solve the upper-triangular linear system  [Graphics:Images/BackSubstitutionMod_gr_20.gif].  
Solution 1 ( a)
Solution 1 ( b)

 

 

Lower-triangular systems.    

    We will now develop the lower-substitution algorithm, which is useful for solving a linear system of equations that has a lower-triangular coefficient matrix.

Definition (Lower-Triangular Matrix).  An [Graphics:Images/BackSubstitutionMod_gr_87.gif] matrix [Graphics:Images/BackSubstitutionMod_gr_88.gif] is called lower-triangular provided that the elements satisfy [Graphics:Images/BackSubstitutionMod_gr_89.gif] whenever [Graphics:Images/BackSubstitutionMod_gr_90.gif].  

    If A is an lower-triangular matrix, then [Graphics:Images/BackSubstitutionMod_gr_91.gif] is said to be a lower-triangular system of linear equations.

(2)    [Graphics:Images/BackSubstitutionMod_gr_92.gif]   

 

Theorem (Forward Substitution).  Suppose that  [Graphics:Images/BackSubstitutionMod_gr_93.gif]  is an lower-triangular system with the form given above in (2).  If  [Graphics:Images/BackSubstitutionMod_gr_94.gif] for [Graphics:Images/BackSubstitutionMod_gr_95.gif] then there exists a unique solution.

Proof  Triangular Systems and Back Substitution  Triangular Systems and Back Substitution  

 

The forward substitution algorithm.  To solve the lower-triangular system [Graphics:Images/BackSubstitutionMod_gr_96.gif] by the method of forward-substitution. Proceed with the method only if all the diagonal elements are nonzero. First compute  

    [Graphics:Images/BackSubstitutionMod_gr_97.gif]  

and then use the rule  

    [Graphics:Images/BackSubstitutionMod_gr_98.gif]  for  [Graphics:Images/BackSubstitutionMod_gr_99.gif].  
    
Remark. The loop control structure will permit us to use one formula

    [Graphics:Images/BackSubstitutionMod_gr_100.gif]  for  [Graphics:Images/BackSubstitutionMod_gr_101.gif].  

 

Computer Programs  Triangular Systems and Back Substitution  Triangular Systems and Back Substitution  

Mathematica Subroutine (Forward Substitution).

[Graphics:Images/BackSubstitutionMod_gr_102.gif]

Example 2. Use the forward-substitution method to solve the lower-triangular linear system  [Graphics:Images/BackSubstitutionMod_gr_103.gif].  
Solution 2.

 

 

The Newton Interpolation Polynomial.    

    The following result is an alternate representation for a polynomial which is useful in the area of interpolation.

Definition (Newton Polynomial).  The following expression is called a Newton polynomial of degree n.

    [Graphics:Images/BackSubstitutionMod_gr_131.gif]  
or
    [Graphics:Images/BackSubstitutionMod_gr_132.gif]

If  n+1  points  [Graphics:Images/BackSubstitutionMod_gr_133.gif]  are given, then the following equations can be used to solve for the  n+1  coefficients [Graphics:Images/BackSubstitutionMod_gr_134.gif].

    [Graphics:Images/BackSubstitutionMod_gr_135.gif]  
or
    [Graphics:Images/BackSubstitutionMod_gr_136.gif]   for   k=1, 2,..., n+1.  

This system of equations is lower-triangular.

    [Graphics:Images/BackSubstitutionMod_gr_137.gif]  
    
    [Graphics:Images/BackSubstitutionMod_gr_138.gif]  
    
    [Graphics:Images/BackSubstitutionMod_gr_139.gif]  
    
    [Graphics:Images/BackSubstitutionMod_gr_140.gif]
    ...  
    [Graphics:Images/BackSubstitutionMod_gr_141.gif]

 

Example 3. Find the Newton polynomial of degree  n=3  that passes through the four points [Graphics:Images/BackSubstitutionMod_gr_142.gif].  
Solution 3.

 

Research Experience for Undergraduates

Triangular Systems and Back Substitution  Triangular Systems and Back Substitution  Internet hyperlinks to web sites and a bibliography of articles.  

 

Download this Mathematica Notebook Forward Substitution and Back Substitution

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2004