Talk:QR decomposition

From Wikipedia, the free encyclopedia

Contents 1 translation question 2 Sign of α in Householder 3 QR decomposition with rank deficiency 4 Householder-Example: QR=A ? 5 typo ? 6 A more stable version of Householder? 7 QR decomposition for complex matrices? 8 FULL QR decomposition

[edit] translation question

I'm trying to translate this article in french. I'm wondering about the example of Householder reflections method and especially, the calcul for the length of the vector a₁. I see that , I would prefer or . PierreLM April 13th 2005

You know you can just use that in your French version. Dysprosia 13:30, 14 Apr 2005 (UTC)

I'm so sorry, . So there is no problem. PierreLM April 15th 2005

[edit] Sign of α in Householder

The section on the Householder method says that α should take its sign from the first element in . In the example which follows, however, the second matrix generated appears not to use the sign operation. Am I missing something, or should this be fixed?--rlhatton 16:11, 25 January 2006 (UTC)

Using the other sign does not matter if you use exact computations, as in the example. I tried to clarify this. However, perhaps it is better to change the example to match the sign convention, or at least make a remark at that point. -- Jitse Niesen (talk) 13:44, 27 January 2006 (UTC)

[edit] QR decomposition with rank deficiency

Is there somebody to editorialize the definition without assuming the full rank? S. Jo 14:03, 7 May 2006 (UTC)

Aha, I didn't notice that this was the point behind the edit I reverted. Better now? -- Jitse Niesen (talk) 01:45, 8 May 2006 (UTC)

Somehow, I don't think that we need to start with a square matrix. When we solve an over-determined system of equations in order to minimize the unitarily invariant norm of residuals, we sometimes use the QR-factorization to reduce a computational complexity. That kind of application reveals one of the essential properties among which the QR-factorization has. Also, except for the uniqueness, QR factorization has good features even in non-square matrices, I guess. For example, we can recognize that an orthonormal basis of the column space of A (=QR) consists of the columns of Q associated with non-zero diagonal entries of R. S. Jo 02:21, 8 May 2006 (UTC)

I agree that it's possible to give only the general definition (complex rectangular matrices), and that the general definition is useful, but I think that it's better from an educational point of view to start with the simpler definition (real square matrices). However, I do not feel strongly about this.

I do not understand your last sentence. If we take

then A = QR where Q is the 3-by-3 identity matrix and R = A, but the column space of A is not spanned by the first and third columns of Q. -- Jitse Niesen (talk) 05:00, 8 May 2006 (UTC)

You are right. My claim was true only if A is full rank, I guess. S. Jo 21:38, 8 May 2006 (UTC)

[edit] Householder-Example: QR=A ?

Hello there,

I'm just wondering why (in the householder-example) the resulting Q- and R-matrices don't multiply to A. Futhermore, the given Q and Q^t are not equal to I. Is the example correct?

When I calculate the products, I get QR = A and QQ^T = I. Could you please be more specific? What value do you take for Q, and what do you get for QQ^T? -- Jitse Niesen (talk) 12:59, 8 June 2006 (UTC)

Oh, you're right. I'm sorry, math is too hard for me :-)

No worries, happens to me all the time ;) -- Jitse Niesen (talk) 13:54, 9 June 2006 (UTC)

[edit] typo ?

"We can similarly form Givens matrices G2 and G3, which will zero the sub-diagonal elements a21 and a32, forming a rectangular matrix" should this actually say triangular instead of rectangular? -- User:Richard Giuly

Yes, indeed. Now fixed. -- Jitse Niesen (talk) 12:43, 22 October 2006 (UTC)

[edit] A more stable version of Householder?

Hi, I am new to the Wikipedia community, as far as editing goes... this is my first so please let me know if this is against protocol. After studying numerical linear algebra using the textbook by Trefethen and Bau, I noticed that there is a crucial step in the Householder implementation of the QR decomposition in this article that makes this article less than optimal in numerical stability. The operation that I would like to verify is the last one in the following snippet of pseudo code from "Numerical Linear Algebra":

for k = 1 to n

x = A_k:m,k

v_k = sign(x₁)||x||₂e₁ + x

v_k = v_k / ||v_k||₂

A_k:m,k:n = A_k:m,k:n - 2v_k(v_k*A_k:m,k:n)

//---------

Notation:

* = complex conjugate

A_k:m,k:n = sub-matrix of A starting at the k-th row and k-th column

sign = sign of

The reason that I say this is more accurate is because the one presented in this page requires that A be multiplied with the successive new Q_n every iteration of the loop, which adds to the numerical instability of the algorithm. The pseudo code proposed by Trefethen and Bau reduces that by having a fresh copy of the original A every iteration. --Jasper 06:58, 23 January 2007 (UTC)

I'm afraid that I don't quite understand what you mean. What is the difference between the statement

A_k:m,k:n = A_k:m,k:n - 2v_k(v_k*A_k:m,k:n)

in Trefethen and Bau's code, and the operation

A = Q_kA

in the article?

I readily agree that the pseudocode is much easier to understand than the explanation in the article. Indeed, I've never been happy how the recursion is explained in the article (I think I am myself to blame for this), so please do go ahead and improve the text. -- Jitse Niesen (talk) 12:06, 24 January 2007 (UTC)

The reason that say that is because the operation you had was:

Q_n = I - ...

after trying to implement that I noticed that you have to do tempA = tempA*Q_n after initializing it to A with every iteration of Q. Whereas the technique I had you can get a fresh copy of A every time. —The preceding unsigned comment was added by 144.118.52.106 (talk) 17:36, 31 January 2007 (UTC).

[edit] QR decomposition for complex matrices?

hi. it seems that the algorithms that are discussed in this page are only compatible with matrices that have real elements and it seems that they can't be modified easily to be compatible with complex matrices.please guide me. —The preceding unsigned comment was added by Sina kh (talk • contribs) 11:59, 14 February 2007 (UTC).

Actually, I think that the algorithms all work for complex matrices if you replace the transpose with the conjugate transpose. For the first algorithm (Gram-Schmidt), this is mentioned in the section listed in the references. -- Jitse Niesen (talk) 04:44, 15 February 2007 (UTC)

Hi everyone.i had checked converting tranpose to transpose conjugate before and it doesn't work in householder reflectors algorithm(Q will be unitary but R won't be upper triangular).In Gram-Schmidt the algorithm have a constraint that "A" must be square(the author have mentioned it in the "definition" section).Sina kh 13:25, 27 February 2007 (UTC)

I'm afraid I don't understand you. I guess the A you're considering is not square. Why do you think R is not upper triangular when doing QR via Householder reflections? Where does it say that A has to be square for Gram-Schmidt? Did you check whether that is in fact true? -- Jitse Niesen (talk) 13:59, 28 February 2007 (UTC)

hi there.I have performed QR decomposition via householder reclection algorithm for a non-square small-sized complex matrix.I tried to follow the algorithm exactly:

A=

    -10+4i    4-5i
    2-i       8+6i
    6         7i

a1=A(:,1)=

         -10+4i
         2-i
         6

alfa=norm(a1)=sqrt(a1'*a1) ("'" means transpose conjugate)

alfa=12.53

u1=a1-(alfa*e) e=(1,0,0)t

u1=

   -22.53+4i
   2-i
   6

v1=u1/norm(u1)=

               -0.9482+0.1683i
               0.0842-0.0421i
               0.2525

q1=I(3*3)-2*v1*v1'=

                    -0.8548             0.1738 + 0.0515i   0.4789 - 0.0850i
                    0.1738 - 0.0515i    0.9823            -0.0425 + 0.0213i
                    0.4789 + 0.0850i   -0.0425 - 0.0213i   0.8725          

q1*a=

         11.8198 - 4.0000i   -1.7425 + 9.0803i
         0.1775 + 0.3551i    8.1473 + 4.5214i
         -0.0000 + 1.0652i   2.1279 + 3.6281i

as it is clear,the elements (2,1) and (3,1) of the matrix "q1*a" are not zero.(against the algorithm).I continued the algorithm but i don't want to take your time more than this.finally:

Q=

  -0.8548            -0.2307 + 0.4265i   0.0231 - 0.1837i
  0.1738 - 0.0515i   -0.1566 - 0.0464i    -0.5619 - 0.7904i
  0.4789 + 0.0850i   -0.4857 + 0.7088i   0.1520 + 0.0464i

and

R=

 11.8198 - 4.0000i  -1.7425 + 9.0803i
  0.8315 - 0.6607i   0.3750 - 4.5215i
 -0.3873 + 0.1202i  -7.9021 + 4.6355i

I also performed QR decomposition in MATLAB and the result was:

Q=

    -0.7981 + 0.3192i  -0.3036 - 0.2224i   0.3220 - 0.1260i
     0.1596 - 0.0798i  -0.7472 - 0.4151i  -0.4190 + 0.2490i
     0.4789 - 0.0000i  -0.1779 - 0.3101i   0.8017 - 0.0085i

and

R=

    12.5300            -3.9904 + 7.6616i
       0               -10.7413          
       0               0       

PS:I apologize if the text has some mistakes gramatically or in vocabulary.I'm not a native speaker and i am not fluent and i am not familiar with the other languages of the the article. thank you.Sina kh 17:07, 5 March 2007 (UTC)

It took me a while before I had time to go through it; sorry. It also was more complicated than I'd expected. Householder reflections behave a bit differently in complex spaces.

You are right, the algorithm does not work for complex matrices. However, it's possible to fix it. Instead of

you have to take

Of course, if v and x are real vectors then ω = 1 and we get the same algorithm as before.

In your Matlab code, you write q1 = eye(3) - (1 + conj(v1'*a1)/(v1'*a1)) * v1*v1' instead of q1 = eye(3) - 2*v1*v1' and it should work.

This formulation of the method is taken from Dirk Laurie's post to NA Digest. Apparently, this is somewhere in Golub and Van Loan; I'll look it up and add to the Wikipedia article. Let me know if you need some more help.

PS: Your English is fine. -- Jitse Niesen (talk) 06:45, 10 March 2007 (UTC)

In fact, Golub & Van Loan and Stoer & Bulirsch use a slightly different (but equivalent) approach. I added a sentence about it to the article. -- Jitse Niesen (talk) 07:19, 14 March 2007 (UTC)

[edit] FULL QR decomposition

Hello everyone. Is anyone interested in adding some information for FULL QR decomposition? Since currently, everything seem to be in reduced form. —The preceding unsigned comment was added by Yongke (talk • contribs) 22:11, 6 March 2007 (UTC).