LU factorization

Splitting a matrix A into a lower-triangular L and an upper-triangular U, with A = LU -- L records elimination's own multipliers, U is the result of eliminating with no row swaps.

LU factorization writes a square matrix $A$ , reduced to upper-triangular $U$ by Gaussian elimination using only row-replacement operations (no swaps), as $A=LU$ , where $L$ is unit lower triangular ( $1$ 's on the diagonal) with the elimination multiplier $m_{ik}$ in position $(i,k)$ . Once computed, $A\mathbf{x}=\mathbf{b}$ solves for any new $\mathbf{b}$ in $O(n^2)$ by forward- then back-substitution, instead of repeating the $O(n^3)$ elimination.

Loading interactive…

Examples

For $A=\begin{pmatrix}2&1&1\\4&3&3\\8&7&9\end{pmatrix}$ , elimination gives $L=\begin{pmatrix}1&0&0\\2&1&0\\4&3&1\end{pmatrix}$ , $U=\begin{pmatrix}2&1&1\\0&1&1\\0&0&2\end{pmatrix}$ -- every multiplier used during elimination reappears directly in $L$ .