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

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

``````
``````

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.

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

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.

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

(c) John H. Mathews 2004