LU Decomposition

Numerical Analysis · Axiom Academy

Factoring matrices for efficient linear system solving LU decomposition factors a matrix A into a product of two triangular matrices: where L is lower triangular (zeros above diagonal) and U is upper triangular (zeros below diagonal). Once we have A = LU, solving Ax = b becomes solving two triangular systems: Forward substitution Start from y₁ and work down Each yᵢ requires i-1 operations Back substitution Start from xₙ and work up Each xᵢ requires n-i operations LU decomposition is just Gaussian elimination with the multipliers saved! Now let's use our factorization to solve Ax = b with b = (4, 10, 24)ᵀ: When we use partial pivoting, we need to record the row swaps in a permutation matrix P: You've learned how to factor matrices using LU decomposition!

This is the written version of the interactive lesson above. See the full Numerical Analysis course.