13
$\begingroup$

I'm having trouble nailing down why using Householder transformations yields a more stable/accurate result than the modified Gram-Schmidt method when computing the QR decomposition of a matrix. Can anyone explain?

Thanks

$\endgroup$
11
$\begingroup$

Both algorithms compute a QR factorisation of a matrix $A$, that is, $A=QR$. Due to rounding errors, we have $A=\tilde{Q}\tilde{R}+E$, where $\tilde{Q}$ is no longer orthogonal (but close to in some sense). The residual $E$ is not usually the problem, for both Householder and Gram-Schmidt (even the classic one), $\|E\|\leq c\epsilon\|A\|$, where $c$ depends only on the dimension of $A$, $\epsilon$ is the machine precision. Here, $\|\cdot\|$ is some "rounding errors friendly" norm, e.g., any $p$-norm (usually $1$, $2$, or $\infty$).

The main difference is in the accuracy of the orthogonal factor. The Householder orthogonalisation gives $\tilde{Q}$ which is almost orthogonal in the sense that $\|I-\tilde{Q}^T\tilde{Q}\|\leq c\epsilon$. In the modified Gram-Schmidt, this "loss of orthogonality" is proportional to the condition number of $A$, that is, MGS yields $\|I-\tilde{Q}^T\tilde{Q}\|\leq c\epsilon\kappa_2(A)$ (note that the Q-factor from the classical Gram-Schmidt satisfies a similar bound with the condition number of $A$ squared).

The difference between Householder and MGS is, roughly speaking, due to the fact that Householder computes the Q-factor as a product of accurate Householder reflections while MGS directly orthogonalises the columns of $A$.

By the way, both Householder and MGS compute an accurate R-factor $\tilde{R}$ in the sense of backward error. For both, there is an (exact) orthogonal matrix $\hat{Q}$ and a residual matrix $\hat{E}$ (of course different for each) such that $\|\hat{E}\|\leq c\epsilon\|A\|$ and $A=\hat{Q}\tilde{R}+\hat{E}$.

$\endgroup$
4
  • $\begingroup$ Why is the Householder method's error smaller or why is it more accurate? Is it simply because there are fewer operations and therefore fewer rounding errors? $\endgroup$ – user146041 Apr 27 '14 at 14:02
  • 1
    $\begingroup$ @user146041 I've edited the answer. Hope it helps. $\endgroup$ – Algebraic Pavel Apr 27 '14 at 15:46
  • 1
    $\begingroup$ It's a very clear answer. Can you also provide some references that have the derivation for the results you mentioned? Thanks. $\endgroup$ – George C Oct 20 '20 at 17:12
  • 1
    $\begingroup$ In addition, you mentioned "MGS directly orthogonalises the columns of A" as the cause of its loss of orthogonality. Can you please explain more on this idea? This line of reasoning is not very transparent for me. Thanks. $\endgroup$ – George C Oct 20 '20 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.