Theorem 1 of the previous note stated the Cholesky factorisation without proof. This sub-note supplies it — an inductive construction, exactly analogous in structure to the LU derivation note's elimination bookkeeping, but exploiting symmetry and positive-definiteness at every step to guarantee the process never fails and never needs pivoting.
Learning objectives. By the end of this note you should be able to:
- carry out one step of the Cholesky construction explicitly;
- prove the induction that guarantees the algorithm always succeeds for an SPD matrix;
- explain why positive-definiteness (not merely symmetry) is essential for the proof;
- state the uniqueness argument.
In this lesson
- The inductive construction
- The induction
Before you start
The full lesson, with worked examples and exercise solutions, is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or browse the Linear Algebra, Optimisation and Numerical Methods syllabus.