Triangular systems and the LU factorization

Reading: Golub & Van Loan §3.1–3.2, pp. 106–122.

By the end of this week you should be able to

• Implement forward and back substitution and state their cost.
• Derive Gaussian elimination as a factorization A = LU.
• State when the LU factorization exists without pivoting.

Algorithms introduced

• Forward and back substitution
• Gaussian elimination / LU factorization

Where this shows up in AI

The factor-once-solve-many pattern: whenever the same operator is reused across many right-hand sides, the factorization is amortized.

Materials