Back substitution

Summary

Back substitution is a method to solve a system $Ux = b$, where $U$ is an $n \times n$ upper triangular matrix with nonzero diagonal entries. The last equation gives $x_n = b_n / u_{nn}$. Then, for $i = n-1, \dots, 1$ in this order, equation $i$ gives $$x_i = \frac{1}{u_{ii}} \left( b_i - \sum_{j = i+1}^{n} u_{ij} x_j \right),$$ which uses only the unknowns that are already known.

Remarks

Back substitution uses on the order of $n^2$ arithmetic operations. Forward substitution solves $Lx = b$ for a lower triangular matrix $L$ in the same way, from the first equation down. After Gaussian elimination, back substitution completes the solution of the system. With an LU decomposition $A = LU$, the system $Ax = b$ is solved by forward substitution for $Ly = b$ and then back substitution for $Ux = y$.

Explanations

L1 human

In a triangular system, the last equation has only one unknown, so we solve it at once. We put that value into the equation above it, which now has only one new unknown. We continue upwards until we know all the unknowns.