LU Factorisation, Pivoting and the Cost of a Solve
Record Gaussian elimination as a product of two triangular matrices, add pivoting for stability, and count the operations each stage costs.
What a learner can do afterwards
- Factor a matrix into lower and upper triangular factors and solve by two substitutions
- Explain why partial pivoting is needed even when no pivot is exactly zero
- Count the operations for a factorisation and for each extra right-hand side, and say why the split matters
1 · Read
LU factorisation records elimination as you go. Each multiplier drops into a lower triangular L and each surviving row into an upper triangular U. The product LU reproduces the original matrix. Solving then runs in two easy triangular stages. Forward substitution cracks Ly equals b, then back substitution cracks Ux equals y. Triangular systems need plain substitution only, no elimination.
Zero pivots stop naive elimination cold. Tiny pivots are nearly as bad: huge multipliers amplify rounding error until the result is noise. Partial pivoting swaps in the largest available pivot at each step, which keeps multipliers small. The swaps are tracked by a permutation, giving PA equals LU. The swaps cost almost nothing beside the factorisation.
Take A with rows [2, 1] and [4, 3]. The multiplier is 4 over 2, which is 2. Subtract twice row one from row two to get [0, 1]. So L has rows [1, 0] and [2, 1], while U has rows [2, 1] and [0, 1]. Contrast A with rows [0, 1] and [1, 0]: the leading pivot is zero, so elimination breaks at step one without a swap.
Factorisation costs about n cubed over 3 operations, paid once. Each new right hand side then needs only two triangular solves at about n squared each. With many right hand sides the factorisation pays for itself fast. So never re-eliminate from scratch for each new b.
You store elimination as L times U, pivot to keep multipliers small, and reuse the factors so every extra solve costs only about n squared.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.