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 matrix is called upper-triangular provided that the elements satisfy whenever .  

    If A is an upper-triangular matrix, then is said to be an upper-triangular system of linear equations.  

(1)        

Theorem (Back Substitution).  Suppose that    is an upper-triangular system with the form given above in (1).  If   for 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 by the method of back-substitution. Proceed with the method only if all the diagonal elements are nonzero. First compute  

      

and then use the rule  

       for  
    
Or, use the "generalized rule"  

       for  

where the "understood convention" is that 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).

Pedagogical version for "printing all the details."

Example 1 (a). Use the back-substitution method to solve the upper-triangular linear system  .  

Example 1 (b). Use the back-substitution method to solve the upper-triangular linear system  .  
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 matrix is called lower-triangular provided that the elements satisfy whenever .  

    If A is an lower-triangular matrix, then is said to be a lower-triangular system of linear equations.

(2)       

Theorem (Forward Substitution).  Suppose that    is an lower-triangular system with the form given above in (2).  If   for 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 by the method of forward-substitution. Proceed with the method only if all the diagonal elements are nonzero. First compute  

      

and then use the rule  

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

      for  .  

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

Mathematica Subroutine (Forward Substitution).

Example 2. Use the forward-substitution method to solve the lower-triangular linear system  .  
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.

      
or
    

If  n+1  points    are given, then the following equations can be used to solve for the  n+1  coefficients .

      
or
       for   k=1, 2,..., n+1.  

This system of equations is lower-triangular.

      
    
      
    
      
    
    
    ...  
    

Example 3. Find the Newton polynomial of degree  n=3  that passes through the four points .  
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