Forward Substitution and Back Substitution

    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.

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.  

Mathematica Subroutine (Back Substitution).

Pedagogical version for "printing all the details."

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.

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  .  

Mathematica Subroutine (Forward Substitution).

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.

      
    
      
    
      
    
    
    ...