1
$\begingroup$

When performing QZ iterations on matrices A and B where A is upper hessenberg to begin with and B is upper triangular, how can one tell when the algorithm has converged? I understand that if it consists of only real eigenvalues then the subdiagonal entries of A will approach zero. However, complex eigenvalues remain below the diagonal of A. Is there a way to determine when all of the values below the subdiagonal of A that are supposed to be zero are in fact zero while the ones that are supposed to remain are still there?

$\endgroup$
1
$\begingroup$

The QR and QZ algorithm split the task into subtasks on corresponding upper and lower diagonal blocks whenever one of the subdiagonal entries is deemed to be equal to zero. This recursion stops whenever the block size is 1 or 2.

In blocksize 2, the eigenvalues corresponding to these blocks can be computed by solving the quadratic characteristic equation, typically they should be complex conjugate pairs, but also a real pair can happen. In the latter case, the necessary rotation to diagonal form can be computed from the eigenvalues. And also in the complex case one might rotate the block into the standard matrix representation of a complex number.

See http://www.netlib.org/lapack/lawnspdf/lawn173.pdf‎ on the QZ algorithm using implicit multishift and chasing chains of small bulge-pairs. Discussion of deflation and infinite eigenvalues starts on p.9-10.

$\endgroup$
  • $\begingroup$ But how does one deem that a subdiagonal entry is supposed to go to zero? I can visually see that certain entries start shrinking to zero and others don't (those representing the complex pairs for example). But I can't put a condition saying that all subdiagonals go to zero for example because of the complex pairs. And since A is in upper hessenberg throughout the process, all of the block sizes along the diagonal are either 1 or 2. $\endgroup$ – Travis Mar 3 '14 at 18:13
  • $\begingroup$ The subdiagonal entries converge toward zero with the factor $\frac{|p(λ_{k+1})|}{|p(λ_{k})|}$ where $p$ is the polynomial collecting the current multi-shift pattern and the eigenvalues are ordered so that the sequence of the $|p(λ_{k+1})|$ is decreasing. So the subdiagonal entries will get smaller where these polynomial values are different. Only conjugate complex pairs and multiple eigenvalues will not separate. You can compare the subdiagonal entry to the neighboring diagonal entries, if the relative size is small enough, which sometimes is taken as large as a factor of $10^{-5}$. $\endgroup$ – Lutz Lehmann Mar 3 '14 at 18:26
  • $\begingroup$ That makes sense. Also, I was forgetting the definition of what a quasi-triangular matrix was which means that no two consecutive elements on the subdiagonal are nonzero. As soon as these conditions are both achieved it should be in Schur form correct? $\endgroup$ – Travis Mar 3 '14 at 21:07

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.