Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
An LU factorization writes a matrix as , where is lower triangular and is upper triangular. It turns one hard solve into two easy triangular solves.
Elementary Matrices
An elementary matrix is the identity with one row operation applied. For :
Key facts:
- doing a row operation on is the same as computing
- a chain of operations gives
- every elementary matrix is invertible, and its inverse is the elementary matrix that undoes the operation (e.g. the inverse of is )
Building L and U
Reduce to an upper triangular using only "add a multiple of a row below" and scaling steps:
The product of the inverses is lower triangular, so it is .
Solving Ax = b with LU
Worked Example
(from , , ). Solve with :
- forward, : , so . Then , so . Then , so
- back, : , so . Then , so . Then , so
So .
Notes
Points to remember:
- LU factorization is not unique: e.g. you can move the diagonal scaling between and
- if a row swap is needed (zero pivot), you get a PLU factorization , where is a permutation matrix
- the reduction steps are exactly those of Gaussian Elimination, LU just stores them