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

  $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],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

  $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 $3y_1+y_2=13$ and hence $y_2=4$ . Finally the bottom line says that $2y_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

  $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 $3x_3=-6$ so clearly $x_3=-2$ . The middle equation implies that $2x_2+2x_3=4$ and it follows that $x_2=4$ . The top equation states that $x_1+2x_2+4x_3=3$ and consequently $x_1=3$ .

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

$\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]\text{is}X=\left[\begin{array}{c}\hfill 3\hfill \\ \hfill 4\hfill \\ \hfill -2\hfill \end{array}\right].$

Task!

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]$ .

Answer