Does Wilkinson's shift need to be discontinuous?

Question

Given a symmetric Hessenberg matrix $A = \left[\begin{matrix}\ddots& \vdots & \vdots\\\dotsb & a & b\\\dotsb& b & c\end{matrix}\right]$, the Wilkinson shift $\mu$ employed in some eigenvalue solvers is given by $$\mu = c - \frac{b^{2} \operatorname{sign}{\left(\delta \right)}}{\sqrt{b^{2} + \delta^{2}} + \left|{\delta}\right|}$$ where $\delta = (a-c)/2$, and $\operatorname{sign}{\left(0 \right)}$ is $1$ or $-1$ (it doesn't matter which). This is discontinuous in $A$, as is easy to verify. And it always produces one of the two eigenvalues of the bottom-right $2 \times 2$ submatrix of $A$. Does the shift need to be discontinuous? Could it not simply take the smaller of the two eigenvalues of the bottom-right submatrix, which would indeed be continuous in $A$?

Answer 1

It must be discontinuous to ensure that all fixed points are attractive.

We make the following assumptions about iterative eigenvalue algorithms over PSD matrices:

1. They consist of iterating some function $f$,
2. $f(M)$ is orthogonally similar to $M$
3. The sequence $(f^n(M))_{n\in\mathbb N}$ converges for every $M$. Obviously, this converges to a fixed point of $f$.
4. A fixed point can only be a diagonal matrix.

We now make the following additional assumptions:

5. All fixed points of $f$ are attractive. (Note that this is a highly desirable property because it bounds the computation time.)
6. $f$ is continuous. (For critical analysis.)

We restrict the domain and codomain of $f$ to the set of matrices orthogonally similar to some PSD matrix $M$, where $M$ is not a multiple of the identity matrix. The fact that we can do this follows from condition 2. We show that $f$ has at least two fixed points under assumptions 5 and 6: Assume it only has one fixed point $x$. It must be attractive by condition 5. By condition 3, all points attract to $x$. This results in the space of matrices orthogonally similar to $M$ being a contractible space, which it surely isn't. We get a contradiction. Therefore $f$ has at least two fixed points orthogonally similar to $M$.

Now we show that under assumptions 5 and 6, one of these two fixed points is not attractive, so that 5 and 6 cannot hold simultaneously. The space of matrices orthogonally similar to some arbitrary matrix $M$ is connected. The set of points which attract to some attractive fixed point is always open. The basins of attraction of the attractive fixed points are disjoint, so by topological connectivity there are points not in their union, which are the points which don't attract to an attractive fixed point. Therefore the Wilkinson shift must be discontinuous to make all fixed points attractive.