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