Back substitution is an algorithm for solving a system of linear equations whose coefficient matrix is upper triangular. It determines the last unknown from the last equation, substitutes that value into the preceding equation, and continues upward until all unknowns have been found. In numerical linear algebra, it is a standard final step after a general system has been reduced to triangular form, particularly by Gaussian elimination.
Mathematical formulation
Consider the system
where is an upper triangular matrix, so that whenever . Written explicitly, the system is
If every diagonal entry is nonzero, the last equation gives
The remaining unknowns are then computed in descending index order:
At each stage, all unknowns appearing to the right of have already been determined. This dependency structure is what makes the procedure possible.
The nonzero-diagonal condition is equivalent to nonsingularity because the determinant of a triangular matrix is
Thus, under this condition, back substitution produces the unique solution. The same formulas apply over the real numbers, the complex numbers, or any field in which the required divisions are defined.
Example
For the system
the last equation gives
Substituting into the second equation gives
Finally,
The solution is therefore
Unlike elimination, this calculation does not create zeros in the coefficient matrix: it uses zeros that are already present.
Algorithm and computational cost
A direct implementation is:
for i = n, n-1, ..., 1:
s = b[i]
for j = i+1, ..., n:
s = s - U[i,j] * x[j]
x[i] = s / U[i,i]
For a dense triangular matrix, the algorithm performs
multiplications, the same number of subtractions, and divisions. Counting each of these as one arithmetic operation gives operations in total. Its running time is therefore in big-O notation, compared with for a conventional dense elimination or factorization.
The solution may overwrite the right-hand-side vector, so only constant auxiliary storage is required beyond the matrix and the storage used for that vector. If is unit upper triangular, meaning that all diagonal entries equal one, the divisions can be omitted.
For a sparse matrix, implementations can skip entries known to be zero. The arithmetic cost then depends on the number and arrangement of stored nonzero entries. For an upper triangular matrix with upper bandwidth , the solve requires operations.
Role in matrix factorizations
Back substitution is usually one stage of a larger solution method.
Gaussian elimination and LU decomposition
Gaussian elimination transforms a general system into an equivalent upper triangular system. Back substitution then recovers the unknowns; it is distinct from the elimination stage itself.
In an LU decomposition with row permutations, a common convention is
where is a permutation matrix, is lower triangular, and is upper triangular. Solving then consists of:
- Applying the permutation to obtain .
- Solving by forward substitution.
- Solving by back substitution.
Once the factors have been computed, they can be reused for different right-hand sides without repeating the factorization.
QR decomposition and least squares
For a real matrix with linearly independent columns, a reduced QR decomposition has the form
where has orthonormal columns and is square, upper triangular, and nonsingular. The least-squares problem
reduces to
which is solved by back substitution. For complex matrices, the conjugate transpose replaces the transpose.
Cholesky decomposition
For a real symmetric positive-definite matrix, the Cholesky decomposition can be written
The system is solved by forward substitution with , followed by back substitution with .
These methods use triangular solves rather than explicitly forming an inverse matrix, avoiding the additional work of computing an inverse when only solutions are needed.
Numerical accuracy
In floating-point arithmetic, multiplication, subtraction, and division introduce rounding errors. Nevertheless, ordinary back substitution has a standard componentwise backward-error bound. Under the usual arithmetic model, and assuming no overflow or problematic underflow, the computed solution satisfies
where absolute values and inequalities are componentwise, and
Here is the unit roundoff and is assumed. This means that the computed result is the exact solution of a nearby triangular system.
This form of numerical stability does not guarantee a small error in the solution itself. Forward accuracy also depends on the condition number of : an ill-conditioned system can amplify small perturbations substantially.
Large intermediate values may overflow even when the final mathematical solution is representable. Specialized triangular solvers can introduce scaling to reduce this risk. Moreover, the stability of back substitution does not by itself establish the stability of a preceding factorization.
Singular and rectangular systems
The standard recurrence requires nonzero diagonal entries. If , division by that entry is impossible. At that stage, the equation instead imposes the compatibility condition
A nonzero right-hand side makes that equation incompatible with the values already assigned; a zero right-hand side leaves undetermined at that step. Earlier equations may impose further constraints.
Consequently, a zero diagonal entry does not by itself distinguish an inconsistent system from one with infinitely many solutions. Handling singular systems requires identifying pivot variables, free variables, and compatibility conditions, using information about matrix rank.
Back substitution also applies to the pivot equations of a rectangular row-echelon system. Free variables are assigned parameters, after which pivot variables are determined in reverse pivot order.
Variants and implementation
With multiple right-hand sides, the problem becomes
Each column can be solved separately, but blocked implementations can process several columns together and exploit efficient matrix multiplication routines.
Block back substitution partitions the system into triangular blocks. For example,
is solved first for , then for :
The ordinary scalar algorithm has a sequential dependency between successive unknowns. This limits straightforward parallelization, although block updates, multiple right-hand sides, and independent portions of sparse dependency structures can provide parallel work.