LU Factorization

Summary

LU factorization writes a nonsingular matrix as $A = L U$ with $L$ unit lower triangular and $U$ upper triangular. Solving $A x = b$ becomes $L y = b$ then $U x = y$ . With row exchanges, the stable form is $P A = L U$ .

Prerequisites

Problem Type

Factor $A$ once, then solve one or many systems with different right-hand sides.

Method Definition

Without pivoting (Doolittle form): run Gaussian elimination on $A$ , store multipliers $m_{i j}$ in the strict lower part of $L$ (unit diagonal), and store the resulting upper matrix in $U$ .^[1]

With partial pivoting: apply row swaps, track them in a permutation matrix $P$ , and obtain $P A = L U$ .

Assumptions / Requirements

All leading principal minors nonzero for $A = L U$ without pivoting
Otherwise use partial pivoting ( $P A = L U$ )
Convention here: $diag (L) = 1$

Algorithm (no pivoting)

Set $U \leftarrow A$ , $L \leftarrow I$ .
For $k = 1, \dots, n - 1$ :
- For $i = k + 1, \dots, n$ :
  - $ℓ_{i k} \leftarrow u_{i k} / u_{k k}$
  - Row $i$ of $U$ $\leftarrow$ row $i - ℓ_{i k} \cdot$ row $k$
Solve $L y = b$ , then $U x = y$ .

Algorithm (partial pivoting)

At stage $k$ , swap for the largest $| u_{i k} |$ with $i \geq k$ , record the swap in $P$ , then eliminate as above (also swap the already-computed part of $L$ consistently). Result: $P A = L U$ .

Worked Example

A = (\begin{matrix} 2 & 3 & 1 \\ 4 & 7 & 7 \\ 6 & 18 & 22 \end{matrix})

Stage $k = 1$ : multipliers $ℓ_{21} = 2$ , $ℓ_{31} = 3$ .

U \leftarrow (\begin{matrix} 2 & 3 & 1 \\ 0 & 1 & 5 \\ 0 & 9 & 19 \end{matrix})

Stage $k = 2$ : multiplier $ℓ_{32} = 9 / 1 = 9$ .

U \leftarrow (\begin{matrix} 2 & 3 & 1 \\ 0 & 1 & 5 \\ 0 & 0 & - 26 \end{matrix}), L = (\begin{matrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 9 & 1 \end{matrix})

Check $L U = A$ :

L U = (\begin{matrix} 2 & 3 & 1 \\ 4 & 7 & 7 \\ 6 & 18 & 22 \end{matrix}) = A .

Solve $A x = b$ with $b = (1, 2, 3)^{⊤}$ . First $L y = b$ :

y_{1} = 1, y_{2} = 2 - 2 \cdot 1 = 0, y_{3} = 3 - 3 \cdot 1 - 9 \cdot 0 = 0.

Then $U x = y$ : $x_{3} = 0$ , $x_{2} = 0$ , $x_{1} = 1 / 2$ . Check: $A (1 / 2, 0, 0)^{⊤}$ is half the first column of $A$ , namely $(1, 2, 3)^{⊤} = b$ , so the residual is zero.

Convergence

Direct $O (n^{3})$ factorization; each subsequent solve is $O (n^{2})$ .

Error / Accuracy

Verify $L U \approx A$ (or $P A \approx L U$ ) and the residual of $A x = b$ . Prefer pivoting when pivots are small.

Common Failure Modes

Zero pivot without row exchange
Forgetting that $L$ stores multipliers from elimination
Confusing $A = L U$ with $P A = L U$ after swaps

Connections

References

Burden & Faires, Numerical Analysis, LU factorization; NIST DLMF Ch. 3, https://dlmf.nist.gov/3 ↩︎