Solving triangular systems of equations: backwards substitution example

L. El Ghaoui

18 Solving triangular systems of equations: backwards substitution example

Consider the triangular system

$R x=\left(\begin{array}{ccc} 3 & 8 & 3 \\ 0 & 6 & -1 \\ 0 & 0 & -3 \end{array}\right)\left(\begin{array}{l} x_1 \\ x_2 \\ x_3 \end{array}\right)=\left(\begin{array}{c} 1 \\ 2 \\ -3 \end{array}\right)$

we solve for the last variable $x_3$ first, obtaining (from the last equation) $x_3=1$ . We plug this value of $x_3$ into the first and second equation, obtaining a new triangular system in two variables $x_1,x_2$ :

$\left(\begin{array}{ll} 3 & 8 \\ 0 & 6 \end{array}\right)\left(\begin{array}{l} x_1 \\ x_2 \end{array}\right)=\left(\begin{array}{c} 1-3 x_3 \\ 2+x_3 \end{array}\right)=\left(\begin{array}{c} -2 \\ 3 \end{array}\right) .$

We proceed by solving for the last variable $x_2$ . The last equation yields $x_2=3 / 6=1 / 2$ . Plugging this value into the first equation gives $3 x_1=-2-8 x_2=-6$ .

We can apply the idea to find the inverse of the square upper triangular matrix $R$ , by solving

$R x^{(1)}=\left(\begin{array}{l} 1 \\ 0 \\ 0 \end{array}\right), R x^{(2)}=\left(\begin{array}{l} 0 \\ 1 \\ 0 \end{array}\right), R x^{(3)}=\left(\begin{array}{l} 0 \\ 0 \\ 1 \end{array}\right) .$

The matrix $\left[x^{(1)}, x^{(2)}, x^{(3)}\right]$ is then the inverse of $R$ . We find

$R^{-1}=\left(\begin{array}{c|c|c|c|c} x^{(1)} & x^{(2)} \mid x^{(3)} \end{array}\right)=\left(\begin{array}{ccc} 1 / 3 & -4 / 9 & 13 / 27 \\ 0 & 1 / 6 & -1 / 18 \\ 0 & 0 & -1 / 3 \end{array}\right) .$

As illustrated above, the inverse of a triangular matrix is triangular.

18 Solving triangular systems of equations: backwards substitution example

License

Share This Book