[latexpage]

Consider a triangular system of the form \(Rx = y\), where the vector \(y \in \mathbb{R}^m\) is given, and \(R\) is upper-triangular. Let us first consider the case when \(m=n\), and \(R\) is invertible. Thus, \(R\) has the form

\[ R = \begin{pmatrix} r_{11} & r_{12} & \ldots & r_{1n} \\ 0 & r_{22} & & r_{2n} \\ \vdots & & \ddots & \vdots \\ 0 & & 0 & r_{nn} \end{pmatrix} \]

with each \(r_{ii}\), \(i=1,\ldots,n\), non-zero.

The backwards substitution first solves for the last component of \(x\) using the last equation:

\[ x_n = \frac{1}{r_{nn}} y_n, \]

and then proceeds with the following recursion, for \(j=n-1,\ldots,1\):

\[ x_j = \frac{1}{r_{jj}} \left( y_j – \sum_{k=j+1}^n r_{jk} x_k \right). \]

Example: Solving a $3 \times 3$ triangular system by backward substitution