JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

LU and QR Factorizations

A factorization splits a matrix into a product of simpler matrices you can reuse. [[lu-decomposition|LU]] is [[gaussian-elimination|elimination]] written down once as A = L*U so repeated solves are cheap; [[qr-decomposition|QR]] packages [[gram-schmidt|Gram-Schmidt]] as A = Q*R for stable least squares. The payoff is factoring once and reusing many times.

Why factor a matrix at all?

Solving A*x = b once is easy. But in practice you often solve it again and again with the same A and a new b each time — many right-hand sides, one matrix. Redoing elimination from scratch every time wastes work. A factorization does the hard part once and stores the result as a product of simpler matrices.

Simpler matrices — triangular or orthogonal ones — are easy to solve with. So the whole game of this rung is: turn a hard matrix into a product of easy ones.

LU: elimination, remembered

Gaussian elimination turns A into an upper-triangular matrix U by subtracting rows. LU decomposition simply remembers the multipliers you used in a lower-triangular matrix L. The result is A = L*U: U is what elimination produces, and L records how you got there.

A = L*U
Solve A*x = b  ->  L*y = b   (forward)
                    U*x = y   (backward)
With L and U stored, each new b costs two cheap triangular solves instead of full elimination.

QR: Gram-Schmidt, packaged

QR decomposition writes A = Q*R, where Q has orthonormal columns and R is upper-triangular. This is exactly Gram-Schmidt on the columns of A, with R bookkeeping the lengths and overlaps. Because Q's columns are orthonormal, multiplying by Q does not stretch or distort — that is what makes QR numerically stable.

  1. Take the columns of A one at a time.
  2. Subtract off their projections onto the directions already chosen.
  3. Normalize what remains to length 1 — these become the columns of Q.
  4. Collect the lengths and overlaps into the upper-triangular R.