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

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.

Derive the LU factorization from Gaussian elimination and count its cost.
Explain why partial pivoting is needed for stability and how it yields PA=LU.
Implement forward and back substitution and verify them against a known solution.
Interpret the growth factor and the backward stability of LU with pivoting.
Solve multiple right-hand sides efficiently by reusing one factorization.

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

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.

Eliminate to get \(U\) and record multipliers in \(L\): the multipliers are \(2/8=0.25\) and \(4/8=0.5\) for column one.

Forward-solve \(Ly=Pb\) for the permuted right-hand side, then back-solve \(Ux=y\).

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

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

← 5.1 Next: 5.3 →