Direct Methods: Triangular Systems

Summary

After elimination or factorization, linear systems reduce to triangular solves. Forward substitution handles lower-triangular $L$ ; back substitution handles upper-triangular $U$ .

Prerequisites

• Matrix notation for $Ax=b$
• Nonzero diagonal pivots

Problem Type

Solve $Lx=b$ or $Ux=b$ with $L$ lower triangular and $U$ upper triangular.

Method Definition

Forward substitution for $Lx=b$ with $l_{ii}\ne 0$ :

Back substitution for $Ux=b$ with $u_{ii}\ne 0$ :

Assumptions / Requirements

• Square triangular matrix with nonzero diagonals
• Exact arithmetic cost is $O(n^2)$

Algorithm

1. Confirm triangular structure and $a_{ii}\ne 0$ .
2. Sweep down (forward) or up (back), substituting known unknowns immediately.
3. Optionally form residual $b-Ax$ for verification.

Worked Example

Upper triangular:

Check: $Ux=(5,6,10{)}^{\mathrm{\top }}=b$ .

Lower triangular:

Common Failure Modes

• Zero pivot on the diagonal
• Treating a nearly triangular matrix as exact without residual checks

Connections

• Gaussian Elimination, LU Factorization
• Numerical Methods/Linear Systems/Solving Linear Systems

References

Standard triangular solves after Gaussian elimination / LU factorization.^[1]