Mathematics.

numerical linear algebra

LU Decomposition

Numerical Analysis25 minDifficulty4 out of 10

You should know: matrices

Overview

LU decomposition factors a square matrix A into the product of a lower triangular matrix L (with 1's on the diagonal) and an upper triangular matrix U, so that A = LU. It is the matrix formulation of Gaussian elimination: the multipliers used to eliminate entries below the diagonal during elimination become the entries of L, and the resulting row-echelon form is U. Once A is factored, solving Ax = b for many different right-hand sides b becomes cheap, since each solve reduces to a forward substitution (Ly = b) followed by a back substitution (Ux = y), each taking only O(n²) operations instead of the O(n³) needed to redo elimination from scratch. When a zero pivot would otherwise be encountered, row-permutation is added, giving PA = LU with a permutation matrix P.

Intuition

Gaussian elimination reduces a matrix to upper-triangular form by subtracting multiples of one row from rows below it; LU decomposition simply keeps a record of exactly which multiples were used, storing them below the diagonal of L while U holds the triangular result. Splitting the work this way pays off when the same system needs to be solved for many different right-hand sides: the expensive elimination step (forming L and U) is done once, and each new b only needs two cheap triangular solves — sliding down through L, then back up through U — like reusing a well-organized recipe instead of re-deriving it from scratch every time.

Formal Definition

Definition

For a square matrix A that admits decomposition without row swaps, A factors as:

A=LUA = LU
LU factorization (L lower triangular with unit diagonal, U upper triangular)
PA=LUPA = LU
LU with partial pivoting (P a permutation matrix), used when a pivot would be zero or small
Ly=b,thenUx=yLy = b, \quad \text{then} \quad Ux = y
Solving Ax=b via forward then back substitution

Worked Examples

  1. Eliminate the (2,1) entry: multiplier l₂₁ = a₂₁/a₁₁ = 4/2 = 2.

    l21=42=2l_{21} = \dfrac{4}{2} = 2

  2. Subtract 2× row 1 from row 2 to get U: row 2 becomes (4−2·2, 7−2·3) = (0, 1).

    U=[2301]U = \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}

  3. L holds the multiplier below the unit diagonal.

    L=[1021]L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}

  4. Verify: LU should reconstruct A.

    LU=[1021][2301]=[2347]=ALU = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix} = A

Answer: L = [[1,0],[2,1]], U = [[2,3],[0,1]], and LU = A exactly.

Practice Problems

Difficulty 4/10

Find the multiplier l₂₁ and the resulting U for A = [[3,6],[1,5]].

Difficulty 6/10

Why is LU decomposition preferred over plain Gaussian elimination when a structural engineer must solve Kd = F for many different load vectors F on the same stiffness matrix K?

Difficulty 4/10

Partial pivoting (giving PA = LU instead of A = LU) is used mainly to:

Quiz

LU decomposition expresses A as the product of:
Once A = LU is known, solving Ax = b for a new b requires:
The entries of L below the diagonal are:

Summary

  • LU decomposition factors A = LU, recording Gaussian elimination's multipliers in L (lower triangular, unit diagonal) and the eliminated matrix in U (upper triangular).
  • Once factored, Ax = b is solved cheaply for any b via forward substitution (Ly=b) then back substitution (Ux=y), each O(n²).
  • Partial pivoting (PA = LU) swaps rows to avoid zero or small pivots, which is essential for numerical stability.

References

  1. WebsiteWikipedia — LU decomposition