| |
for
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
HARDWARE implementation please reference to
An Efficient Low Complexity LDPC Encoder Based On
LU Factorization With Pivoting