LU decomposition

In this section we focus again on solving linear systems given by $A \boldsymbol{x}=\boldsymbol{b}$. However now we discuss a method that allows us to solve the matrix equation above with different vectors $\boldsymbol{b}$ without repeating the whole process for each case. The $L U$ decomposition records the steps of Gaussian elimination by decomposing $A$ into a lower and an upper triangular matrix. Suppose that we can write $A$ as

for some lower triangular matrix $L$ and some upper triangular matrix $U$. Then the matrix equation above becomes,

we let $\boldsymbol{z}=U \boldsymbol{x}$ which, when substituted in Eq. (10.70), yields,

Thus, in order to solve Eq. (10.70), we solve (10.71) for $\boldsymbol{z}$ and then use $\boldsymbol{z}=U \boldsymbol{x}$ to solve for $\boldsymbol{x}$. We illustrate the ideas with an example. Consider the matrix,

We want to write it in the following form

where the stars indicate possibly nonzero entries. The stars represent 12 unknowns in $L$ and $U$ but we only have 9 equations for the entries in matrix $A$. To make progress, we choose the diagonal entries of the lower triangular matrix to be all unity,

It follows that the first row of $U$ must be the first row of $A$ giving,

Between $L$ and $U$, we now have 6 unknowns which can be solved for by solving 6 equations. Alternatively, we can reduce the coefficient matrix $A$ to upper triangular form, keeping track of row operations used. The latter is done through the use of elementary matrices (see Subsec. 10.3.1).

Starting with the coefficient matrix $A$ given in Eq. (10.72), we perform $\left(R_{2}-R_{1}\right) \rightarrow\left(R_{2}\right)$ which is represented by the elementary matrix,

Recall that to perform this row operation on $A$, we need to pre-multiply $A$ by the elementary matrix $E_{1}$ yielding,

Next, we continue with $\left(R_{3}-R_{1}\right) \rightarrow\left(R_{3}\right)$ represented by the elementary matrix

and pre-multiplying $E_{1} A$ by $E_{2}$ gives,

Finally, we undertake $\left(R_{3}-3 R_{2}\right) \rightarrow\left(R_{3}\right)$ represented by the elementary matrix

and $E_{3} E_{2} E_{1} A$ gives,

So far we have

where the elementary matrices are given by Eqs. (10.76), (10.78), and (10.80). From Eq. (10.82), we have,

It follows that by taking the inverses of the elementary matrices in reverse order, we obtain $L$,

The $L U$ decomposition is therefore,

Suppose we wish to calculate the solution of $A \boldsymbol{x}=\boldsymbol{b}$ for $\boldsymbol{b}=(2,4,5)^{\top}$. We first solve the lower triangular system $L \boldsymbol{z}=\boldsymbol{b}$,

This gives $z_{1}=2, z_{2}=4-z_{1}=2$, and $z_{3}=5-z_{1}-3 z_{2}=-3$. We then solve for $U \boldsymbol{x}=\boldsymbol{z}$,

This gives $x=-3, y=4$, and $z=-1$.

Exercises

1. Use LU factorisation for the system $A \boldsymbol{x}=\boldsymbol{b}$ where $A=\left(\begin{array}{ccc}2 & -2 & -1 \\ 4 & 1 & -2 \\ 4 & 3 & -2\end{array}\right)$ and the following values of $\boldsymbol{b}$ : (a) $\boldsymbol{b}^{\top}=(-5,0,4)$; (b) $\boldsymbol{b}^{\top}=(-1,-1,-9)$; (c) $\boldsymbol{b}^{\boldsymbol{\top}}=(-1,8,12)$.
2. Use LU factorisation for the system $A \boldsymbol{x}=\boldsymbol{b}$ where $A=\left(\begin{array}{ccc}1 & 1 & 1 \\ 2 & 3 & -2 \\ 5 & -1 & -3\end{array}\right)$ and the following values of $\boldsymbol{b}$ : (a) $\boldsymbol{b}^{\top}=(4,1,1)$ (b) $\boldsymbol{b}^{\boldsymbol{\top}}=(3,-3,5)$ (c) $\boldsymbol{b}^{\top}=(-1,1,9)$