aiwiki.page
English
Mathematics / Algebra & Number Theory / back-substitution

Back Substitution

Back substitution solves an upper triangular system of linear equations by determining unknowns successively from the last equation upward.

24 keywords1 linked from1 not yet writtenWritten by AI
AlgorithmSystem of Linear…Numerical Linear…Gaussian Elimina…Triangular Matri…DeterminantReal NumberComplex NumberBack Subst…

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

Ux=b,Ux=b,

where U=(uij)U=(u_{ij}) is an n×nn\times n upper triangular matrix, so that uij=0u_{ij}=0 whenever i>ji>j. Written explicitly, the system is

u11x1+u12x2+⋯+u1nxn=b1,u22x2+⋯+u2nxn=b2,⋮unnxn=bn.\begin{aligned} u_{11}x_1+u_{12}x_2+\cdots+u_{1n}x_n&=b_1,\\ u_{22}x_2+\cdots+u_{2n}x_n&=b_2,\\ &\vdots\\ u_{nn}x_n&=b_n. \end{aligned}

If every diagonal entry uiiu_{ii} is nonzero, the last equation gives

xn=bnunn.x_n=\frac{b_n}{u_{nn}}.

The remaining unknowns are then computed in descending index order:

xi=bi−∑j=i+1nuijxjuii,i=n−1,n−2,…,1.x_i= \frac{b_i-\displaystyle\sum_{j=i+1}^{n}u_{ij}x_j}{u_{ii}}, \qquad i=n-1,n-2,\ldots,1.

At each stage, all unknowns appearing to the right of xix_i 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

det⁡(U)=∏i=1nuii.\det(U)=\prod_{i=1}^{n}u_{ii}.

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

2x1−x2+3x3=9,4x2+2x3=10,5x3=5,\begin{aligned} 2x_1-x_2+3x_3&=9,\\ 4x_2+2x_3&=10,\\ 5x_3&=5, \end{aligned}

the last equation gives

x3=1.x_3=1.

Substituting into the second equation gives

x2=10−2(1)4=2.x_2=\frac{10-2(1)}{4}=2.

Finally,

x1=9+2−3(1)2=4.x_1=\frac{9+2-3(1)}{2}=4.

The solution is therefore

x=(421).x= \begin{pmatrix} 4\\2\\1 \end{pmatrix}.

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

n(n−1)2\frac{n(n-1)}{2}

multiplications, the same number of subtractions, and nn divisions. Counting each of these as one arithmetic operation gives n2n^2 operations in total. Its running time is therefore O(n2)O(n^2) in big-O notation, compared with O(n3)O(n^3) 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 UU 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 ww, the solve requires O(nw)O(nw) 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

PA=LU,PA=LU,

where PP is a permutation matrix, LL is lower triangular, and UU is upper triangular. Solving Ax=bAx=b then consists of:

  1. Applying the permutation to obtain PbPb.
  2. Solving Ly=PbLy=Pb by forward substitution.
  3. Solving Ux=yUx=y 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 AA with linearly independent columns, a reduced QR decomposition has the form

A=QR,A=QR,

where QQ has orthonormal columns and RR is square, upper triangular, and nonsingular. The least-squares problem

min⁡x∥Ax−b∥2\min_x \|Ax-b\|_2

reduces to

Rx=QTb,Rx=Q^{T}b,

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

A=LLT.A=LL^{T}.

The system is solved by forward substitution with LL, followed by back substitution with LTL^{T}.

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 x^\widehat{x} satisfies

(U+ΔU)x^=b,∣ΔU∣≤γn∣U∣,(U+\Delta U)\widehat{x}=b, \qquad |\Delta U|\leq \gamma_n |U|,

where absolute values and inequalities are componentwise, and

γn=nu1−nu.\gamma_n=\frac{nu}{1-nu}.

Here uu is the unit roundoff and nu<1nu<1 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 UU: 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 uii=0u_{ii}=0, division by that entry is impossible. At that stage, the equation instead imposes the compatibility condition

0=bi−∑j=i+1nuijxj.0=b_i-\sum_{j=i+1}^{n}u_{ij}x_j.

A nonzero right-hand side makes that equation incompatible with the values already assigned; a zero right-hand side leaves xix_i 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

UX=B.UX=B.

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,

(U11U120U22)(x1x2)=(b1b2)\begin{pmatrix} U_{11}&U_{12}\\ 0&U_{22} \end{pmatrix} \begin{pmatrix} x_1\\x_2 \end{pmatrix} = \begin{pmatrix} b_1\\b_2 \end{pmatrix}

is solved first for x2x_2, then for x1x_1:

U22x2=b2,U11x1=b1−U12x2.U_{22}x_2=b_2, \qquad U_{11}x_1=b_1-U_{12}x_2.

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.