LU decomposition

1 LU decomposition

Suppose we have the system of equations

$A X = B .$

The motivation for an $L U$ decomposition is based on the observation that systems of equations involving triangular coefficient matrices are easier to deal with. Indeed, the whole point of Gaussian elimination is to replace the coefficient matrix with one that is triangular. The $L U$ decomposition is another approach designed to exploit triangular systems.

We suppose that we can write

$A = L U$

where $L$ is a lower triangular matrix and $U$ is an upper triangular matrix. Our aim is to find $L$ and $U$ and once we have done so we have found an $L U$ decomposition of $A$ .

Key Point 5

An $L U$ decomposition of a matrix $A$ is the product of a lower triangular matrix and an upper triangular matrix that is equal to $A$ .

It turns out that we need only consider lower triangular matrices $L$ that have 1s down the diagonal. Here is an example. Let

$A = [\begin{matrix} 1 & 2 & 4 \\ 3 & 8 & 14 \\ 2 & 6 & 13 \end{matrix}] = L U$ where $L = [\begin{matrix} 1 & 0 & 0 \\ L_{21} & 1 & 0 \\ L_{31} & L_{32} & 1 \end{matrix}]$ and $U = [\begin{matrix} U_{11} & U_{12} & U_{13} \\ 0 & U_{22} & U_{23} \\ 0 & 0 & U_{33} \end{matrix}]$ .

Multiplying out $L U$ and setting the answer equal to $A$ gives

$[\begin{matrix} U_{11} & U_{12} & U_{13} \\ L_{21} U_{11} & L_{21} U_{12} + U_{22} & L_{21} U_{13} + U_{23} \\ L_{31} U_{11} & L_{31} U_{12} + L_{32} U_{22} & L_{31} U_{13} + L_{32} U_{23} + U_{33} \end{matrix}] = [\begin{matrix} 1 & 2 & 4 \\ 3 & 8 & 14 \\ 2 & 6 & 13 \end{matrix}] .$

Now we use this to find the entries in $L$ and $U$ . Fortunately this is not nearly as hard as it might at first seem. We begin by running along the top row to see that

$U_{11} = 1, U_{12} = 2, U_{13} = 4 .$

Now consider the second row

\begin{array}{rcl} L_{21} U_{11} = 3 ∴ L_{21} \times 1 = 3 ∴ L_{21} = 3, \\ L_{21} U_{12} + U_{22} = 8 ∴ 3 \times 2 + U_{22} = 8 ∴ U_{22} = 2, \\ L_{21} U_{13} + U_{23} = 14 ∴ 3 \times 4 + U_{23} = 14 ∴ U_{23} = 2 . \end{array}

Notice how, at each step, the equation being considered has only one unknown in it, and other quantities that we have already found. This pattern continues on the last row

\begin{array}{rcl} L_{31} U_{11} = 2 ∴ L_{31} \times 1 = 2 ∴ L_{31} = 2, \\ L_{31} U_{12} + L_{32} U_{22} = 6 ∴ 2 \times 2 + L_{32} \times 2 = 6 ∴ L_{32} = 1, \\ L_{31} U_{13} + L_{32} U_{23} + U_{33} = 13 ∴ (2 \times 4) + (1 \times 2) + U_{33} = 13 ∴ U_{33} = 3 . \end{array}

We have shown that

$A = [\begin{matrix} 1 & 2 & 4 \\ 3 & 8 & 14 \\ 2 & 6 & 13 \end{matrix}] = [\begin{matrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & 1 & 1 \end{matrix}] [\begin{matrix} 1 & 2 & 4 \\ 0 & 2 & 2 \\ 0 & 0 & 3 \end{matrix}]$

and this is an $L U$ decomposition of $A$ .

Task!

Find an $L U$ decomposition of $[\begin{matrix} 3 & 1 \\ - 6 & - 4 \end{matrix}]$ .

Let

$[\begin{matrix} 3 & 1 \\ - 6 & - 4 \end{matrix}] = L U = [\begin{matrix} 1 & 0 \\ L_{21} & 1 \end{matrix}] [\begin{matrix} U_{11} & U_{12} \\ 0 & U_{22} \end{matrix}] = [\begin{matrix} U_{11} & U_{12} \\ L_{21} U_{11} & L_{21} U_{12} + U_{22} \end{matrix}]$

then, comparing the left and right hand sides row by row implies that $U_{11} = 3$ , $U_{12} = 1$ , $L_{21} U_{11} = - 6$ which implies $L_{21} = - 2$ and $L_{21} U_{12} + U_{22} = - 4$ which implies that $U_{22} = - 2$ . Hence

$[\begin{matrix} 3 & 1 \\ - 6 & - 4 \end{matrix}] = [\begin{matrix} 1 & 0 \\ - 2 & 1 \end{matrix}] [\begin{matrix} 3 & 1 \\ 0 & - 2 \end{matrix}]$

is an $L U$ decomposition of $[\begin{matrix} 3 & 1 \\ - 6 & - 4 \end{matrix}]$ .

Task!

Find an $L U$ decomposition of $[\begin{matrix} 3 & 1 & 6 \\ - 6 & 0 & - 16 \\ 0 & 8 & - 17 \end{matrix}]$ .

Using material from the worked example in the notes we set

$[\begin{matrix} 3 & 1 & 6 \\ - 6 & 0 & - 16 \\ 0 & 8 & - 17 \end{matrix}] = [\begin{matrix} U_{11} & U_{12} & U_{13} \\ L_{21} U_{11} & L_{21} U_{12} + U_{22} & L_{21} U_{13} + U_{23} \\ L_{31} U_{11} & L_{31} U_{12} + L_{32} U_{22} & L_{31} U_{13} + L_{32} U_{23} + U_{33} \end{matrix}]$

and comparing elements row by row we see that

$\begin{matrix} U_{11} = 3, & U_{12} = 1, & U_{13} = 6, \\ L_{21} = - 2, & U_{22} = 2, & U_{23} = - 4 \\ L_{31} = 0 & L_{32} = 4 & U_{33} = - 1 \end{matrix}$

and it follows that

$[\begin{matrix} 3 & 1 & 6 \\ - 6 & 0 & - 16 \\ 0 & 8 & - 17 \end{matrix}] = [\begin{matrix} 1 & 0 & 0 \\ - 2 & 1 & 0 \\ 0 & 4 & 1 \end{matrix}] [\begin{matrix} 3 & 1 & 6 \\ 0 & 2 & - 4 \\ 0 & 0 & - 1 \end{matrix}]$

is an $L U$ decomposition of the given matrix.

1 LU decomposition

Key Point 5

Task!

Answer

Task!

Answer