LU Decomposition

The key problem of Linear Algebra is solving the equation $A x = b$ . We know that with Gaussian elimination, we can decompose $A = L U$ , where $L$ is a lower-triangular matrix and $U$ is an upper triangular matrix. An example speaks a thousand words:

$A x = [\begin{array}{ccc} 2 & 1 & 1 4 & - 6 & 0 - 2 & 7 & 2 \end{array}] [\begin{array}{l} u v w \end{array}] = [\begin{matrix} 5 - 2 9 \end{matrix}] = b$

We have that:

$U x = [\begin{array}{ccc} 2 & 1 & 1 0 & - 8 & - 2 0 & 0 & 1 \end{array}] [\begin{array}{l} u v w \end{array}] = [\begin{matrix} 5 - 12 2 \end{matrix}] = c$

And the process from getting from A to U is $G F E A = U$ :

$G F E = [\begin{array}{ccc} 1 \\ 1 \\ 1 & 1 \end{array}] [\begin{array}{ccc} 1 \\ 1 \\ 1 & 1 \end{array}] [\begin{array}{ccc} 1 & 1 \\ - 2 & 1 \\ 1 \end{array}] = [\begin{array}{ccc} 1 \\ - 2 & 1 \\ - 1 & 1 & 1 \end{array}]$

We have that $E^{- 1} F^{- 1} G^{- 1} U = L U = A$ :

$E^{- 1} F^{- 1} G^{- 1} = [\begin{array}{ccc} 1 \\ 2 & 1 \\ 1 \end{array}] [\begin{array}{ccc} 1 & 1 & - 1 & 1 \end{array}] [\begin{array}{ccc} 1 \\ 1 \\ - 1 & 1 \end{array}] = [\begin{array}{ccc} 1 & 2 & 1 & - 1 & - 1 & 1 \end{array}] = L$

The $A = L U$ decomposition is exactly the matrix that solves $A x = b$ . Each triangular system requires $\frac{n^{2}}{2}$ steps each, compared to the $O (n^{3})$ system of factoring $A$ .

The triangular factorization can be written $A = L D U$ where $L$ and $U$ have 1s on the diagonal, and $D$ is the diagonal matrix of pivots:

$A = [\begin{array}{ll} 1 & 2 3 & 4 \end{array}] = [\begin{array}{ll} 1 & 1 3 & 1 \end{array}] [\begin{array}{rr} 1 & 2 & - 2 \end{array}] = [\begin{array}{ll} 1 3 & 1 \end{array}] [\begin{array}{ll} 1 & - 2 \end{array}] [\begin{array}{ll} 1 & 2 & 1 \end{array}] = L D U$

This factorization is uniquely determined by $A$ .