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.
More to read
11.6 Solving Systems with Gaussian Elimination
LU factorisation splits a matrix into a lower triangular L and an upper triangular U, recording elimination as you go. Each multiplier drops into L, each surviving row into U. The product LU reproduces the original matrix.
Solving then runs in two easy triangular stages. Forward substitution cracks Ly equal b, back substitution cracks Ux equal y. Triangular systems solve by plain substitution, no elimination needed.
7.6 Solving Systems with Gaussian Elimination
Zero pivots stop naive elimination cold, and tiny pivots are nearly as bad: huge multipliers amplify rounding error until the answer is noise. Partial pivoting swaps in the largest available pivot at each step, keeping multipliers small.
Row swaps are tracked by a permutation, giving PA equal LU. The swaps cost almost nothing beside the factorisation, and they rescue both singular looking and ill scaled systems.
9.6 Solving Systems with Gaussian Elimination
Factorisation costs about n cubed over three operations, paid once. After that each new right hand side needs only two triangular solves at about n squared each. Splitting the work this way is the whole point.
With many right hand sides, or repeated solves in an iteration, the factorisation pays for itself fast. Never re-eliminate from scratch for each new b.
2 · Watch
به انگلیسیTake it off screen
Where it sits
17 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.