Backwards substitution for solving triangular linear systems

L. El Ghaoui

Backwards substitution for solving triangular linear systems

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} & \dots r_{1n} \\ 0 & r_{22} & & r_{2n} \vdots & & \ddots & \vdots \\ 0 & & 0 & r_{nn} \end{pmatrix}$

with each $r_{ii}, i=1, \dots,n$ non-zero.

The backward substitution first solves for the last component of $x$ using the last equation:

$x_{n}=\dfrac{1}{r_{nn}}y_{n},$

and then proceeds with the following recursion, for $j = n-1,\dots,1$ :

*** QuickLaTeX cannot compile formula:
\[x_{j}=\dfrac{1}{r_{jj}\cdot\left(y_{j}-\sum_{k=j+1}^{n}r_{jk}x_{k}\right).\]

*** Error message:
File ended while scanning use of \@genfrac.
Emergency stop.

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

Backwards substitution for solving triangular linear systems

License

Share This Book