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} & \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

License

Icon for the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Linear Algebra and Applications Copyright © 2023 by VinUiversity is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, except where otherwise noted.

Share This Book