1

How do you prove that QR factorization via Householder Triangularization is backward stable?

Theorem 16.1 (From Trefethen and Bau): Let the $QR$ factorization of a matrix $A$ be computed by Householder triangularization on a computer satisfying the floating point arithmetic axioms. Let the $\tilde{Q}$ and $\tilde{R}$ be the computed factors. Then we have $$\tilde{Q}\tilde{R} = A + \delta A$$ and $$\frac{||{\delta A}||}{||A||} = O(\epsilon_{machine})$$

mymindcastadrift
  • 80
  • If $H$ is an elementary Householder transformation and $\tilde H$ is its computed counterpart, then $|H-\tilde{H}|_2=O(\epsilon)$ and $\mathrm{fl}(\tilde{H}A)=H(A+E)$, where $|E|_2=O(\epsilon|A|_2)$. – Algebraic Pavel Jun 28 '15 at 23:46
  • There must be something obvious that I'm not seeing. Why is the first statement $|| H - \tilde{H}||_2 = O(\epsilon)$ true? – mymindcastadrift Jun 30 '15 at 16:43
  • 1
    The proofs are not hard but very technical. You can find more details in Section 18.3 of this book. This result is actually not very interesting and is true for all orthogonalization algorithms (even for the classical Gram-Schmidt). You can deduce it from Lemma 18.3 in the linked book. What is actually more pleasant for the Householder algorithm is that the "computed" $Q$ is really close to the exact $Q$ (see Theorem 18.4 there). – Algebraic Pavel Jul 01 '15 at 10:38
  • Thanks a lot! I will go take a look at the book. – mymindcastadrift Jul 03 '15 at 20:13

0 Answers0