### 2 Using LU decomposition to solve systems of equations

Once a matrix $A$ has been decomposed into lower and upper triangular parts it is possible to obtain the solution to $AX=B$ in a direct way. The procedure can be summarised as follows

• Given $A$ , find $L$ and $U$ so that $A=LU$ . Hence $LUX=B$ .
• Let $Y=UX$ so that $LY=B$ . Solve this triangular system for $Y$ .
• Finally solve the triangular system $UX=Y$ for $X$ .

The benefit of this approach is that we only ever need to solve triangular systems. The cost is that we have to solve two of them.

[Here we solve only small systems; a large system is presented in Engineering Example 1 on page 62.]

##### Example 6

Find the solution of $X=\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \end{array}\right]$ of the system $\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 4\hfill \\ \hfill 3\hfill & \hfill 8\hfill & \hfill 14\hfill \\ \hfill 2\hfill & \hfill 6\hfill & \hfill 13\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 3\hfill \\ \hfill 13\hfill \\ \hfill 4\hfill \end{array}\right].$

##### Solution
• The first step is to calculate the $LU$ decomposition of the coefficient matrix on the left-hand side. In this case that job has already been done since this is the matrix we considered earlier. We found that

$\phantom{\rule{2em}{0ex}}L=\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 3\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right],\phantom{\rule{2em}{0ex}}U=\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 4\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 3\hfill \end{array}\right].$

• The next step is to solve $LY=B$ for the vector $Y=\left[\begin{array}{c}\hfill {y}_{1}\hfill \\ \hfill {y}_{2}\hfill \\ \hfill {y}_{3}\hfill \end{array}\right]$ . That is we consider

$\phantom{\rule{2em}{0ex}}LY=\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 3\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill {y}_{1}\hfill \\ \hfill {y}_{2}\hfill \\ \hfill {y}_{3}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 3\hfill \\ \hfill 13\hfill \\ \hfill 4\hfill \end{array}\right]=B$

which can be solved by forward substitution . From the top equation we see that ${y}_{1}=3$ . The middle equation states that $3{y}_{1}+{y}_{2}=13$ and hence ${y}_{2}=4$ . Finally the bottom line says that $2{y}_{1}+{y}_{2}+{y}_{3}=4$ from which we see that ${y}_{3}=-6$ .

• Now that we have found $Y$ we finish the procedure by solving $UX=Y$ for $X$ . That is we solve

$\phantom{\rule{2em}{0ex}}UX=\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 4\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 3\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 3\hfill \\ \hfill 4\hfill \\ \hfill -6\hfill \end{array}\right]=Y$

by using back substitution . Starting with the bottom equation we see that $3{x}_{3}=-6$ so clearly ${x}_{3}=-2$ . The middle equation implies that $2{x}_{2}+2{x}_{3}=4$ and it follows that ${x}_{2}=4$ . The top equation states that ${x}_{1}+2{x}_{2}+4{x}_{3}=3$ and consequently ${x}_{1}=3$ .

Therefore we have found that the solution to the system of simultaneous equations

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 4\hfill \\ \hfill 3\hfill & \hfill 8\hfill & \hfill 14\hfill \\ \hfill 2\hfill & \hfill 6\hfill & \hfill 13\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 3\hfill \\ \hfill 13\hfill \\ \hfill 4\hfill \end{array}\right]\phantom{\rule{2em}{0ex}}\text{is}\phantom{\rule{2em}{0ex}}X=\left[\begin{array}{c}\hfill 3\hfill \\ \hfill 4\hfill \\ \hfill -2\hfill \end{array}\right].$

Use the $LU$ decomposition you found earlier in the last Task (page 24) to solve

$\left[\begin{array}{ccc}\hfill 3\hfill & \hfill 1\hfill & \hfill 6\hfill \\ \hfill -6\hfill & \hfill 0\hfill & \hfill -16\hfill \\ \hfill 0\hfill & \hfill 8\hfill & \hfill -17\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 4\hfill \\ \hfill 17\hfill \end{array}\right]$ .

We found earlier that the coefficient matrix is equal to $LU=\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill -2\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 4\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{ccc}\hfill 3\hfill & \hfill 1\hfill & \hfill 6\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill \end{array}\right]$ .

First we solve $LY=B$ for $Y$ , we have

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill -2\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 4\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill {y}_{1}\hfill \\ \hfill {y}_{2}\hfill \\ \hfill {y}_{3}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 4\hfill \\ \hfill 17\hfill \end{array}\right].$

The top line implies that ${y}_{1}=0$ . The middle line states that $-2{y}_{1}+{y}_{2}=4$ and therefore ${y}_{2}=4$ . The last line tells us that $4{y}_{2}+{y}_{3}=17$ and therefore ${y}_{3}=1$ .

Finally we solve $UX=Y$ for $X$ , we have

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 3\hfill & \hfill 1\hfill & \hfill 6\hfill \\ \hfill 0\hfill & \hfill 2\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 4\hfill \\ \hfill 1\hfill \end{array}\right].$

The bottom line shows that ${x}_{3}=-1$ . The middle line then shows that ${x}_{2}=0$ , and then the top line gives us that ${x}_{1}=2$ . The required solution is $X=\left[\begin{array}{c}\hfill 2\hfill \\ \hfill 0\hfill \\ \hfill -1\hfill \end{array}\right]$ .