Back Substitution

Goals

Understand how to solve upper-triangular systems using back substitution and see how it complements forward substitution in the LU decomposition framework.

Prerequisites

Contents

1. Definition and Principle

Back substitution is an algorithm for solving the linear system

$$U\mathbf{x} = \mathbf{b}$$

where $U$ is an upper triangular matrix. Since $u_{ij} = 0$ for $i > j$, the last row reduces to the single-variable equation $u_{nn} x_n = b_n$, from which $x_n$ is immediately determined. Substituting $x_n$ into the row above yields $x_{n-1}$, and the process continues upward until all variables are found.

In matrix form:

$$\begin{pmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix}$$

A unique solution exists provided $u_{ii} \neq 0$ for all $i$ (i.e., $U$ is nonsingular).

Back substitution: solving Ux=b from the bottom row upward U 2 1 −1 0 3 2 0 0 4 x₁ x₂ x₃ = 8 7 4 bottom-up 1 2 3 1 Last row has one unknown:　4·x₃ = 4 → x₃ = 4 / 4 = 1　(immediate) 2 Substitute x₃ into the row above:　3·x₂ + 2·(1) = 7 → x₂ = (7 − 2) / 3 = 5/3 3 One more row up:　2·x₁ + (5/3) − (1) = 8 → x₁ = (8 − 5/3 + 1) / 2 = 11/3 Each xᵢ = ( bᵢ − sum of known terms ) / uᵢᵢ　(divide by the diagonal)
Figure 1. Flow of back substitution. Since the upper triangular matrix $U$ has all zeros below the diagonal (the staircase of zeros), the last row $4x_3=4$ has just one unknown. Determine $x_3$, substitute it into the row above to get $x_2$, and once more to get $x_1$. The order is ①②③ — that is, from the bottom row to the top. Each component is given by $x_i = \left(b_i - \sum_{j>i} u_{ij}x_j\right)/u_{ii}$.

2. Formula

$$x_n = \dfrac{b_n}{u_{nn}}$$
$$x_i = \dfrac{1}{u_{ii}} \left(b_i - \displaystyle\sum_{j=i+1}^{n} u_{ij} x_j\right), \quad i = n-1, n-2, \ldots, 1$$

Each $x_i$ is obtained by subtracting the contributions of the already-computed $x_{i+1}, \ldots, x_n$ from $b_i$, then dividing by the diagonal element $u_{ii}$.

3. Algorithm

function backSubstitution(U, b, n):
    x[n] = b[n] / U[n][n]
    for i = n-1 downto 1:
        sum = 0
        for j = i+1 to n:
            sum = sum + U[i][j] * x[j]
        x[i] = (b[i] - sum) / U[i][i]
    return x

The inner loop performs $n - i$ multiplications and additions for each $i$.

4. Complexity

The operation count for back substitution on an $n \times n$ upper triangular matrix:

OperationCount
Divisions$n$
Multiplications$\dfrac{n(n-1)}{2}$
Additions/Subtractions$\dfrac{n(n-1)}{2}$
Total$n^2$ ($O(n^2)$)

Compared to forward elimination in Gaussian elimination ($O(n^3/3)$), back substitution is very inexpensive. It represents a small fraction of the total computation, though care must be taken with rounding errors accumulated during forward elimination.

5. Role in Gaussian Elimination and LU Decomposition

Gaussian elimination consists of two phases:

  1. Forward elimination: row operations transform the augmented matrix to upper triangular form. $O(n^3/3)$.
  2. Back substitution: solve the upper triangular system. $O(n^2/2)$.

With LU decomposition $A = LU$:

  1. Solve $L\mathbf{y} = \mathbf{b}$ by forward substitution. $O(n^2/2)$.
  2. Solve $U\mathbf{x} = \mathbf{y}$ by back substitution. $O(n^2/2)$.

Once the LU factorization is computed, solving for different right-hand sides $\mathbf{b}$ requires only $O(n^2)$ work (forward + back substitution).

6. Numerical Stability

Back substitution is backward stable, and rounding error growth is mild. However, note:

  • Very small diagonal elements $u_{ii}$ amplify errors through division.
  • Errors accumulated during forward elimination cannot be removed by back substitution. Pivoting is important.
  • If the condition number $\kappa(U)$ is large, the result accuracy degrades on the order of $\varepsilon_{\mathrm{mach}} \cdot \kappa(U)$.

7. Worked Example

Example: 3x3 Upper Triangular System

$\begin{pmatrix} 2 & 1 & -1 \\ 0 & 3 & 2 \\ 0 & 0 & 4 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 8 \\ 7 \\ 4 \end{pmatrix}$

StepComputationResult
$x_3$$4 / 4$$x_3 = 1$
$x_2$$(7 - 2 \times 1) / 3$$x_2 = 5/3$
$x_1$$(8 - 1 \times 5/3 - (-1) \times 1) / 2$$x_1 = 11/3$

Solution: $\mathbf{x} = (11/3,\; 5/3,\; 1)^T$.

8. FAQ

Q1. What is back substitution?

An algorithm that solves upper triangular systems $U\mathbf{x} = \mathbf{b}$ by computing $x_n$ first and working backwards. It is an essential final step of Gaussian elimination and LU decomposition.

Q2. What is the complexity?

$O(n^2)$ for an $n \times n$ upper triangular matrix, much less than the $O(n^3)$ forward elimination phase.

Q3. How does it differ from forward substitution?

Back substitution solves upper triangular $U\mathbf{x} = \mathbf{b}$ backwards, while forward substitution solves lower triangular $L\mathbf{y} = \mathbf{b}$ forwards. LU decomposition uses both.

9. References