4
$\begingroup$

Sorry for asking really silly question. I guess the answer will be very simple.

The question I am doing is: Does QR method always converge to a upper triangular matrix?

I think the answer is not. And I guess

$$A= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$

And I have $Q_k R_k =A_k$ (QR factorization) and $A_{k+1}=R_k Q_k$. But if my calculations are not wrong, I have all $A_k=A$, which is not upper trianguler.

But my professor had a theorem (and he didn't prove it) that any real symmetric non-singular matrix $A$ will converge to upper triangular form and the diagonal entries converges to eigenvalues. And in my case, $A$ doesn't converge, and the entries (even not the diagonal ones) don't match the eigenvalues ($1$ and $-1$) of $A$.

So, have I made any silly mistakes? Thank you.

$\endgroup$
4
$\begingroup$

The QR algorithm only converges using Wilkinson-Shift strategie! A numerical stable version of the Wilkinson Shift is given by $$\mu=A_{nn}-\frac{sgn(\sigma)A^2_{n,n-1}}{|\sigma|+\sqrt{\sigma^2+A^2_{n-1,n-1}}}$$ where $\sigma=\frac12(A_{n-1,n-1}-A_{nn})$ and in case $\sigma=0$ we take $sgn(\sigma)=1$. So as you can see, the Wilkinson shift is 1 in your example and therefore the algorithm converges.

The example you have given is the standard example for why the QR algo without shift does not converge. The problem is, that the Eigenvalues of the matrix are given by 1 and -1. So even using Rayleigh Quotient shift the algorithm will not converge, since the Rayleigh Quotient estimator is stuck at 0, between -1 and 1.

In theorem for convergence of the QR algrotihm without shifts you usually need that the first minors of the matrix do not vanish and that the eigenvalues fulfill $|\lambda_1|>|\lambda_2|>\dots >|\lambda_n|$, both does not hold true in your example. Maybe check if your professor included this conditions into his theorem, if the theorem refers to the QR algo without shifts. This is by the way usually proven by comparing the algorithm to the Power iteration.

You can find the QR algo with shifts and the proof of convergence here

As you can see, not a silly question! A very good question, indeed.

$\endgroup$

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.