2

I learned in class about the QR-factorization, and I got to know two algorithms to calculate it; using the Gram–Schmidt process and Householder transformations.

My issue is that those two processes don't seem to always yield the same result for the same matrix - for example, consider the following matrix:

$A := \begin{bmatrix} 3 & -6 \\ 5&-8 \\ 0 & 1 \end{bmatrix}$

Using the Gram-Schmidt process, I arrive at the following decomposition:

$A = QR = \begin{bmatrix} \frac{3}{5} & 0 \\ \frac{4}{5}& 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 5 & -10 \\ 0& 1 \end{bmatrix}$

But using Householder transformations, I get a different result:

$A = Q^\prime R^\prime = \begin{bmatrix} -\frac{3}{5} & 0 & \frac{4}{5} \\ -\frac{4}{5}& 0 & -\frac{3}{5}\\ 0 & -1 & 0 \end{bmatrix}\begin{bmatrix} -5 & 10 \\ 0& -1 \\ 0 & 0 \end{bmatrix} $

Now, I do understand that the QR decomposition is not unique, but what confuses me is that even the dimensions of the resulting matrices are different. Why is this the case? Does this have any real consequences when I am asked to choose one of those algorithms? Does this cause stability issues?

Katharina
  • 384
  • 1
    That's because there are two different kinds of QR factorization for rectangular matrices. One kind has a square $R$, the other a square $Q$. The former is unique once a few extra conditions are required (this is at least claimed in https://math.stackexchange.com/questions/989627/uniqueness-of-thin-qr-factorization , although the only answer given so far is incorrect). The latter is not unique. Geometrically, the difference is whether you just construct an orthonormal basis for the column space of $A$, or whether you also extend it to an orthonormal basis of the whole ambient space. – darij grinberg Nov 18 '19 at 17:15
  • @darijgrinberg I see, and I do recognize that my $Q^\prime$ can be obtained from my $Q$ by extending the column vectors to a base of the ambient space. But what I am still a bit curious about is if I should care about the difference? Does it make any observable difference when choosing a method to implement some numerical process? – Katharina Nov 18 '19 at 17:27
  • This will probably require an actual numerical algebraist; I can only come up with platitudes like "use whatever is more suited for the specific problem". NumPy can do both, using the keywords "reduced" and "complete". – darij grinberg Nov 18 '19 at 17:47

0 Answers0