Skip to content
Linear Algebra, Optimisation and Numerical Methods / Floating-Point Arithmetic, Conditioning, and Stability

Stability of Gaussian Elimination and Householder QR

This closing note of Topic 8 puts backward stability to work on the two workhorse algorithms the unit has used since LA-I's elimination note: Gaussian elimination with partial pivoting, and Householder QRQR. Both are backward stable in practice — but the mechanism behind their stability, and the one genuine caveat elimination carries that QRQR does not, is worth understanding precisely rather than taking on faith.
Learning objectives. By the end of this note you should be able to:
  • state why Householder QRQR is unconditionally backward stable;
  • state the (much weaker, conditional) stability guarantee for Gaussian elimination with partial pivoting;
  • define the growth factor and explain its role in elimination's stability analysis;
  • recommend an algorithm for a given problem based on both stability and cost.

In this lesson

  1. Householder QR: unconditional stability
  2. Gaussian elimination with partial pivoting: conditional stability
  3. Practical recommendation

Before you start

The full lesson, with worked examples and exercise solutions, is for members.

Read the full lesson

New to SelfMadeQuant.com? See membership options or browse the Linear Algebra, Optimisation and Numerical Methods syllabus.