NLA MT25, QR factorisation
Flashcards
Via Gram-Schmidt
Why isn’t the QR factorisation via the Gram-Schmidt process a good idea?
It is not numerically stable.
Via Householder reflectors
See [[Notes - Numerical Analysis HT24, Householder reflectors]]U and ∆qr-with-householder.
@State a result that characterises the backward stability of finding the QR decomposition of a matrix with Householder reflectors.
The computed version of the factorisation satisfies
\[\hat Q \hat R = A + \Delta A, \quad \vert \vert \hat Q^\top \hat Q - I \vert \vert _ 2 = \epsilon\]Hence this method is unconditionally backward stable.
What’s the difference between “orthogonal triangularisation” and “triangular orthogonalisation” for computing the QR factorisation of a matrix?
- Orthogonal triangularisation: use orthogonal matrices to create a triangular matrix, e.g. with Householder reflectors
- Triangular orthogonalisation: use triangular matrices to create an orthogonal matrix, e.g. with Gram-Schmidt
@State a result about the backward stability of the decomposition $A = \hat Q \hat R$ using Householder reflectors.
With Householder QR, the computed $\hat Q, \hat R$ satisfy
\[\vert \vert \hat Q^\top Q - I \vert \vert = O(\epsilon)\]and
\[\vert \vert A - \hat Q \hat R \vert \vert = O(\epsilon \vert \vert A \vert \vert )\]@Prove that for Householder QR, the computed $\hat Q, \hat R$ satisfy
\[\vert \vert \hat Q^\top Q - I \vert \vert = O(\epsilon)\]
and
\[\vert \vert A - \hat Q \hat R \vert \vert = O(\epsilon \vert \vert A \vert \vert )\]
- Each reflector satisfies $\text{fl}(H _ i A) = H _ i A + \epsilon _ i \vert \vert A \vert \vert $
- Hence $\hat R := \text{fl}(H _ n \cdots H _ 1 A) = H _ n \cdots H _ 1 A + \epsilon \vert \vert A \vert \vert $.
- $\text{fl}(H _ n \cdots H _ 1) =: \hat Q^\top = H _ n \cdots H _ 1 A + \epsilon$
- $\hat Q \hat R = A + \epsilon \vert \vert A \vert \vert $
@todo, clarify.