22
$\begingroup$

I tried to implement the QR algorithm for non-symmetric matrices with complex entries to show to my students. The main part of the implementation was standard: the Householder reduction to the Hessenberg form, complex Given's rotations, etc. So far so good.

Now, if you do it without shifts, it will never converge if two eigenvalues have equal absolute values (which is not such an exceptional case: most real-valued matrices have conjugate pairs, the companion matrices of polynomials like $z^n-1$ have all their roots on the circle, etc., etc.). So, I needed to shift in some intelligent way.

Both Raleigh (shifting by the bottom right element) and Wilkinson (shifting by an eigenvalue of the bottom right $2\times 2$ matrix) fail: it is fairly easy to create the matrix (say, the same companion matrix of $z^n-1$, but not only) for which the complex QR algorithm using these shifts will cycle or converge to a matrix that is not upper triangular, but has some $2\times 2$ blocks instead. No clever modification of those seemed to help either.

So, my solution was to follow my favorite general principle: "If you don't know how to do something, do it at random". My shift for a single run is just a uniform complex number in the bottom Gershgorin disk (centered at $a_{n,n}$ and of radius $|a_{n,n-1}|$). It seems to work like a charm (I couldn't create a matrix for which it would fail and it requires about 5 QR iterations per eigenvalue with relative precision $10^{-13}$ for the below the diagonal values in the "reasonable" cases), but for the life of mine I cannot figure out why.

All literature I know just discusses why guessing a shift sufficiently close to a true eigenvalue accelerates the convergence, and that I understand. However, in this case, one can start with small eigenvalues and have quite large below diagonal entries, so at least in the beginning I do not see why it is any better than shifting by a totally random number at each iteration, which would not achieve much (or would it?). So, two questions:

  1. What is the usually recommended shift for the complex case?

  2. Why does my home-made contraption work? ${}{}{}{}{}$

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ We tried an extension of your idea for non symmetric Companion matrices for polynomial roots. We are using several types of shifts, coded as enumerations: 1. Matrix[last][last] 2. Either Wilkinson shift from last 2x2 sub matrix (if real solutions present) OR real eigenvalue of last 3x3 sub matrix 3. Matrix[0][0] 4. Either Wilkinson shift from first 2x2 sub matrix (if real solutions present) OR real eigenvalue of first 3x3 sub matrix After every 200 QR&RQ iterations, the algorithm moves to next type of shift. So far, all cases of non convergence have gone away. $\endgroup$
    – Eteri and Yuri
    Commented Oct 12 at 16:58
  • 1
    $\begingroup$ This is the follow up to our comment from Oct 12, 2024, which we could not edit. We found a lecture by Jim Lambers, implemented this method, and so far it works best for convergence web.stanford.edu/class/cme335/lecture5 $\endgroup$
    – Eteri and Yuri
    Commented Oct 19 at 18:01

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .