Quant Academy Math · Probability · Quant Finance
Phase 5 - Lesson 5.2

LU Factorization and Solving Linear Systems

Gaussian elimination as a matrix factorization, why we pivot, and the two triangular solves that do the real work.

⏱ 50 min● Intermediate🔗 Prereqs: 5.1
↖ Phase 5 hub
Builds on: 5.1 gives the stability language; pivoting is a stability device.
Leads to: LU is the workhorse; Cholesky (5.4) is its symmetric specialization.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Key Vocabulary

LU factorization
Writing \(A=LU\) with \(L\) unit lower-triangular and \(U\) upper-triangular.
Partial pivoting
Row-swapping to put the largest available entry on the pivot, giving \(PA=LU\).
Forward substitution
Solving \(Ly=b\) top-to-bottom in \(O(n^2)\) work.
Back substitution
Solving \(Ux=y\) bottom-to-top in \(O(n^2)\) work.
Growth factor
The largest magnitude appearing during elimination relative to \(A\); controls LU stability.
Permutation matrix
A reordering of the identity, \(P\), encoding the row swaps; orthogonal with \(P^{-1}=P^\top\).

Intuition & Motivation

Intuition
Gaussian elimination is not just a hand procedure - the row operations that zero out a column are themselves lower-triangular matrices. Bundling them gives \(A=LU\): a permanent record of the elimination that you can replay against any right-hand side. That is why factorizing costs \(O(n^3)\) once but each subsequent solve costs only \(O(n^2)\). Pivoting is the safety belt: choosing the largest pivot keeps the multipliers \(\le 1\) so rounding cannot blow up.

From elimination to a factorization

Eliminating column \(k\) subtracts multiples \(\ell_{ik}=a_{ik}/a_{kk}\) of row \(k\) from rows below. Collecting the multipliers into a unit lower-triangular \(L\) and the reduced matrix into \(U\) gives:

\[A = LU,\qquad L_{ik}=\ell_{ik}\ (i\gt k),\quad L_{ii}=1,\quad U\ \text{upper-triangular}.\] (5.2)
Theorem - LU with partial pivoting
For any square \(A\) there is a permutation \(P\) with \(PA=LU\), where all multipliers satisfy \(|\ell_{ik}|\le1\). The resulting algorithm is backward stable in practice, with growth factor almost always \(O(n)\).

With the factorization in hand, solving \(Ax=b\) is two cheap triangular solves:

\[PA=LU:\quad Ly = Pb\ \text{(forward)},\qquad Ux = y\ \text{(back)}.\] (5.3)
Worked Example - Solve a 3×3 system by LU
1
Factor \(A=\begin{psmallmatrix}2&1&1\\4&3&3\\8&7&9\end{psmallmatrix}\). With partial pivoting the largest first-column entry (8) becomes the pivot, so rows are swapped.
2
Eliminate to get \(U\) and record multipliers in \(L\): the multipliers are \(2/8=0.25\) and \(4/8=0.5\) for column one.
3
Forward-solve \(Ly=Pb\) for the permuted right-hand side, then back-solve \(Ux=y\).
4
Cost: one \(O(n^3)\) factorization, then \(O(n^2)\) per right-hand side - the reason we never recompute the factorization.

Interactive: forward and back substitution

Implement the two triangular solves that every dense linear-algebra library calls millions of times.

Common Mistakes to Avoid
  • Skipping pivoting: a zero or tiny pivot makes \(\ell_{ik}\) explode and destroys accuracy.
  • Recomputing the factorization for each new \(b\) instead of reusing \(L,U\).
  • Forgetting to permute the right-hand side: you must solve \(Ly=Pb\), not \(Ly=b\).
  • Inverting \(A\) to solve one system - slower and less stable than two triangular solves.
Quant Practitioner Tips
  • Call a factorization once and cache \(L,U,P\) for repeated solves (e.g. rolling risk systems).
  • For symmetric positive-definite systems, use Cholesky (5.4): half the cost, no pivoting needed.
  • Check the returned pivots; a near-zero pivot after partial pivoting signals a near-singular matrix.
  • Use library LAPACK (numpy.linalg/scipy.linalg.lu_factor) in production; hand code only to learn.

Knowledge Check

Q1 Medium
Why does partial pivoting improve numerical stability?
It reduces the flop count
It keeps every multiplier \(|\ell_{ik}|\le1\), bounding error growth
It makes \(A\) symmetric
It removes the need for back substitution
Q2 Medium
You must solve \(Ax=b_i\) for 100 different \(b_i\) with the same \(A\). The efficient approach is:
Compute \(A^{-1}\) once, multiply 100 times
Factor \(PA=LU\) once, then 100 pairs of triangular solves
Run full Gaussian elimination 100 times
Use Cramer’s rule per system
Q3 Easy
In \(PA=LU\) with partial pivoting, the matrix \(L\) is:
Upper-triangular with unit diagonal
Unit lower-triangular with entries \(|\ell_{ik}|\le1\)
Orthogonal
Diagonal

Practical Exercise

Show that once \(PA=LU\) is known, solving \(Ax=b\) requires only \(O(n^2)\) work, and count the multiplications in forward substitution for \(Ly=Pb\).

▶ Show full solution

Forward substitution computes \(y_i=(Pb)_i-\sum_{j\lt i}\ell_{ij}y_j\). Row \(i\) uses \(i-1\) multiplications, so the total is \(\sum_{i=1}^n(i-1)=n(n-1)/2\).

Back substitution for \(Ux=y\) is symmetric, another \(\approx n^2/2\) multiplications. Together the two solves are \(O(n^2)\), dominated by the one-time \(O(n^3)\) factorization.

After the reveal, answer for yourself: How does this cost split explain why LAPACK separates lu_factor from lu_solve?

Lesson Summary

LU turns Gaussian elimination into a reusable factorization \(A=LU\) (or \(PA=LU\) with pivoting). Factoring costs \(O(n^3)\) once; each solve is two \(O(n^2)\) triangular substitutions. Partial pivoting bounds the multipliers, making the method backward stable in practice.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers
Q: What does partial pivoting guarantee about \(L\)?
A: Its multipliers satisfy \(|\ell_{ik}|\le1\), bounding error growth and giving practical backward stability.
Q: Give the cost of factorization vs. a single solve.
A: Factorization is \(O(n^3)\); each right-hand-side solve is \(O(n^2)\) via forward then back substitution.

Completion Checklist

Confidence / mastery rating
Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

← 5.1Next: 5.3 →