The QR Steps with Perfect Shifts

In this paper we revisit the problem of performing a QR-step on an unreduced Hessenberg matrix H when we know an "exact" eigenvalue ?0 of H. Under exact arithmetic, this eigenvalue will appear on diagonal of the transformed Hessenberg matrix H~ and will be decoupled from the remaining part of the Hessenberg matrix, thus resulting in a deflation. But it is well known that in finite precision arithmetic the so-called perfect shift can get blurred and that the eigenvalue ?0 can then not be deflated and/or is perturbed significantly. In this paper, we develop a new strategy for computing such a QR step so that the deflation is almost always successful. We also show how to extend this technique to double QR-steps with complex conjugate shifts.