Ill-Conditioning

Singular pencils may or may not have eigenvalues. Indeed, the generic case corresponds to a singular pencil that has no eigenvalues. Below we illustrate this with two 3 by 3 examples:

$$A_1 - \lambda B_1 = \left[ \begin{array}{c\vert c\vert c} 1... ...line 0 & 0 & 1\\ 0 & 0 & -\lambda \\ \end{array} \right].$$

Obviously, ${\rm det}(A_1 - \lambda B_1) \equiv 0$ and ${\rm det}(A_2 - \lambda B_2) \equiv 0$ for all $\lambda$. Although both pencils have the same diagonal elements they have very different canonical forms. Indeed, both pencils are in KCF: $A_1 - \lambda B_1 = {\rm diag}(N_1, L_0, L_0^T, J_1(0))$ and $A_2 - \lambda B_2 = {\rm diag}(L_1, L_1^T)$. From top to bottom, the diagonal blocks of $A_1 - \lambda B_1$ correspond to $N_1$, diag($L_0, L_0^T$), and $J_1$. So $A_1 - \lambda B_1$ has a regular part of size $2 \times 2$ with eigenvalues at zero ($J_1(0)$) and infinity ($N_1$) and a singular part of size $1 \times 1$ corresponding to one $L_0$ block (of size $0 \times 1$) and one $L_0^T$ block, while $A_2 - \lambda B_2$ is a generic $3 \times 3$ singular pencil with no regular part.

If $A - \lambda B$ is upper triangular and a zero element appears on the diagonal, then the pencil is singular. We see that both examples have this property (the $(2,2)$ entries of $A_1$ and $B_1$ are zero as well as for $A_2$ and $B_2$). This situation will appear if we apply the QZ algorithm to a square singular pencil in infinite precision. Such a pair ($\alpha$, $\beta$) = (0, 0) is called an indeterminate eigenvalue 0/0. In the presence of roundoff, the QZ algorithm may fail to detect and isolate the singularity due to the ill-conditioning of the problem as illustrated below.

The eigenvalue problem for a singular pair is much more complicated than for a regular pair. Consider, for example, the singular pair

$$A = \left[ \begin{array}{cc} 1 & 0 \\ 0 & 0 \\ \end{arr... ... \begin{array}{cc} 1 & 0 \\ 0 & 0 \\ \end{array} \right],$$

which has one finite eigenvalue 1 and one indeterminate eigenvalue 0/0 (corresponding to a singular part diag($L_0, L_0^T$)). To see that neither the eigenvalue 1 nor the singular part is well determined by the data, consider the slightly perturbed problem

$$A' = \left[ \begin{array}{cc} 1 & \epsilon_1 \\ \epsilon_... ... 1 & \epsilon_3 \\ \epsilon_4 & 0 \\ \end{array} \right],$$

where the $\epsilon_i$ are tiny nonzero numbers. It follows that $\{A', B'\}$ is regular with eigenvalues $\epsilon_1/\epsilon_3$ and $\epsilon_2/\epsilon_4$. Given any two complex numbers $\lambda_1$ and $\lambda_2$, we can find arbitrary tiny $\epsilon_i$ such that $\lambda_1 = \epsilon_1/\epsilon_3$ and $\lambda_2 = \epsilon_2/\epsilon_4$ are the eigenvalues of $\{A', B'\}$. Since, in principle, roundoff could change $\{A,B\}$ to $\{A', B'\}$, we cannot hope to compute accurate or even meaningful eigenvalues of singular problems, without further information. Typically, this information includes restrictions of allowable perturbations so that unperturbed and perturbed problems have similar structural characteristics. For this example the regularization requires that the perturbed pencil also have a $1 \times 1$ regular part and a $1 \times 1$ singular part.

A well-known class of singular pencils is the class of matrix pairs with intersecting null spaces. Let $x \neq 0$ belong to the intersection of the null spaces of $A$ and $B$, i.e., $A x = B x = 0$. Then for any $(\alpha,\beta)$, we have $(\beta A - \alpha B ) x = 0$, implying that the pair $\{A,B\}$ is singular. By inspection we see that $A_1$ and $B_1$ above have a common one-dimensional column (and row) null space spanned by $x = e_2$. The dimensions of the intersecting column and row null spaces, respectively, are the number of $L_0$ and $L_0^T$ blocks, respectively, in the pencils' KCF. Notice that the intersection of null spaces of $A$ and $B$ is a sufficient but not a necessary condition for a pencil to be singular, as illustrated with $A_2 - \lambda B_2$ in the first set of examples.

It is possible for a pair $\{A,B\}$ in Schur form to be very close to singular, and so to have very sensitive eigenvalues, even if no diagonal entries of $A$ or $B$ are small. It suffices for $A$ and $B$ to nearly have a common null space. For example, consider the $16 \times 16$ matrices

$$A'' = \left[ \begin{array}{ccccc} 0.1 & 1 & & & \\ & 0.1 ... ...end{array} \right] \quad\quad \mbox{and} \quad\quad B'' = A''.$$

Then $\{A'', B''\}$ has all eigenvalues at 1. Changing ${A}_{n1}''$ and ${B}_{n1}''$ to $10^{-16}$ makes both $A''$ and $B''$ singular to machine precision, with a common null vector; i.e., there exists a unit vector $x$ such that $\Vert A''x\Vert _2 = \Vert B''x\Vert _2 \approx O(10^{-16})$. Then, using a technique analogous to the one applied to the $2 \times 2$ example above, we can show that there is a perturbation of $A''$ and $B''$ of norm $10^{-16} + \epsilon$, for any $\epsilon> 0$, that makes the 16 perturbed eigenvalues have any prescribed complex values.

With these examples in mind we are ready to introduce the GUPTRI form and the regularization method used to compute meaningful and reliable information.