Module for Forward Substitution and Back Substitution

Check out the new Numerical Analysis Projects page.

    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 .  The   matrix is called lower-triangular provided that whenever .  

    We will develop a method for constructing the solution to upper-triangular linear systems of equations an leave the investigation of lower-triangular systems to the reader.  If A is an upper-triangular matrix, then is said to be an upper-triangular system of linear equations and has the form

        

Theorem (Back Substitution).  Suppose that is an upper-triangular system with the form given above.  
If   for then there exists a unique solution to the linear system.

Constructive Proof.

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. 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.

The evolution of Mathematica programming for back substitution.

Mathematica Subroutine (Back Substitution).

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

Example 1 (b). Use the back-substitution method to solve the upper-triangular linear system  , where and .  
Solution 1 (b)

Lower-triangular systems.    

    Constructing the solution to a lower-triangular linear system  .  

The forward substitution method.

Forward Substitution. To solve the lower-triangular system  

      

Proceed with the method only if all the diagonal elements are non-zero.  First compute  

      

and then use the rule  

      for  .  

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

Mathematica Subroutine (Forward Substitution).

Example 2. Use the forward-substitution method to solve the lower-triangular linear system  .  
Use the menu "Input" then submenu "Create Table/Matrix/Palette" to enter matrix A and vector B.
Solution 2.

Research Experience for Undergraduates

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

Downloads (Forward Substitution and Back Substitution Forward Substitution and Back Substitution).  
Download this Mathematica notebook.  

(c) John H. Mathews 2003