1
$\begingroup$

The (generalized) eigenvalue problems with a multiple eigenvalue are the ill-posed ones. I have two questions that should be simple for experts: (1) Is the eigenvalue problem much more sensitive to errors for matrices with a cluster of eigenvalues close to each other or for matrices with multiple eigenvalues?

(https://apps.dtic.mil/sti/tr/pdf/AD0766916.pdf) this suggests if one knows multiplicities in advance, it's not a big problem. But we usually don't know multiplicities in advance.

(2) In my small experiments, Octave was able to detect multiple eigenvalues perfectly. Since the problem should be ill-posed in this case, how is this possible?
(I hope you do not suggest I follow 20 steps in LAPACK code and see trick for myself :) )

Improve this question
$\endgroup$
5
  • $\begingroup$ Whether ill-posedness is a problem depends on the algorithm. What algorithm do you use for finding eigenvalues? $\endgroup$
    – Wolfgang Bangerth
    Jul 22 at 16:07
  • 1
    $\begingroup$ By "ill-posed ones" do you mean your matrix has a nontrivial Jordan block? Most eigenvalue algorithms are extremely sensitive to perturbations that teeter on the edge of diagonalizability. A single element perturbation of order $\epsilon$ can yield changes in eigenvalues estimates of order $\epsilon^{1/p}$, where $p$ is the size of the Jordan block $\endgroup$
    – whpowell96
    Jul 22 at 17:13
  • 2
    $\begingroup$ @WolfgangBangerth According to Demmel's book ill conditioned locus is a feature of the problem rather than the algorithm. Demmel also gives a geometric perspective on the matter: link.springer.com/article/10.1007/BF01400115 So, I'm a bit confused by your comment. If you happen to have a few mins, could you explain a little bit? Many Thanks in advance $\endgroup$
    – alpx
    Jul 22 at 19:41
  • $\begingroup$ Right. Whether or not something is ill-conditioned is inherent in the problem. Whether that is a problem depends on the algorithm. For example, standard Gauss elimination suffers when the matrix is ill-conditioned. But with pivoting, you're generally fine. $\endgroup$
    – Wolfgang Bangerth
    Jul 23 at 1:25
  • $\begingroup$ I still need to understand this better: I thought for Gaussian elimination it was simply the condition number definition was wrong and Skeel's condition number (bionum.cs.purdue.edu/79Skee.pdf) solved that issue. It seems to me that if the problem is inherently ill-conditioned, there is no way around it. Do you have any references that would help me to understand this better? $\endgroup$
    – alpx
    Jul 23 at 18:20

1 Answer 1

Reset to default
2
$\begingroup$

(1) [EDIT: fixed significantly with respect to the first version] Let $\lambda$ be an eigenvalue of $A$, and $\tilde{\lambda}$ the closest eigenvalue of a perturbed matrix $A+E$. If $A=VDV^{-1}$ is diagonalizable, then $|\tilde{\lambda}-\lambda| \leq \kappa(V) \|E\|$. (Bauer-Fike theorem.)

If $A$ not diagonalizable, and $\lambda$ has multiplicity $k$, then $|\tilde{\lambda}-\lambda| = O(\|E\|^{1/k})$. In particular, this implies that the sensitivity is lower if the eigenvalues are distinct, since in one case the eigenvalues are locally Lipschitz and in the other they are not. However, $\kappa(V)$ may be very large; in particular, it has to diverge for a sequence of matrices that converge to a Jordan block, or a matrix with multiple eigenvalues. In this sense, matrices with multiple eigenvalues have worse sensitivity, but in practice there is little difference between a Jordan block and a small perturbation of it.

The additional problem is that you can't reliably tell those two cases apart, in floating-point arithmetic. For instance, the matrix $A = \begin{bmatrix}1 & -1/3 \\ 3 & -1 \end{bmatrix}$ has a Jordan block of size 2, but in any neighborhood of it there are infinite matrices with a cluster of two distinct eigenvalues. When one stores $A$ as a floating-point matrix the value $-1/3$ gets approximated, turning it into a nearby matrix $A+E$ with two distinct eigenvalues and $\kappa(V)\approx 3\cdot 10^{20}$. Even in cases when a matrix is exactly representable in floating point, the standard backward stable eigenvalue algorithms guarantee only that they compute the exact eigenvalues of a matrix $A + E$ with $\|E\| / \|A\| = O(u)$, where $u$ is the machine precision; so in presence of clusters they can't answer the question if eigenvalues are equal or not, and not even the question of checking if they are equal up to machine precision.

Knowing in advance that the multiplicity is high makes it an entirely different problem. "Compute the eigenvalues of a $2\times 2$ matrix $A$, knowing that it has a double eigenvalue" is a very simple problem; its condition number is 1, and it can be solved trivially by the algorithm lambda = trace(A) / 2.

(2) Show us your experiments and maybe we might be able to tell you why.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I have an algebraic variety where the randomly sampled matrices coming from the variety are $3 \times 3$ and have a double eigenvalue by construction. So I knew the matrices had a double eigenvalue beforehand, and but they were otherwise randomly created by sampling. Then we feed random matrices to Octave (several times with different seeding), Octave always spitted out the double eigenvalue up to 4th digit in single and double precision. I'll accept your answer since the backward-stable part answers my question. $\endgroup$
    – alpx
    Jul 22 at 19:44
  • 2
    $\begingroup$ That's exactly what is supposed to happen according to the perturbation theory. If you take a size-$k$ Jordan block $A$ and add a perturbation $E$ of norm equal to the machine precision $u$, the resulting matrix $A+E$ has (generically) $k$ eigenvalues at distance $O(u^{1/k})$ from the original eigenvalue. So four correct digits is what you're expecting to see in single precision for a double eigenvalue. Note that this is not "perfectly", you lose half of the significant digits. $\endgroup$
    – Federico Poloni
    Jul 22 at 21:36
  • 1
    $\begingroup$ @alpx I have expanded on the first part, including more quantitative bounds and correcting my earlier assertion that the two cases are equal. $\endgroup$
    – Federico Poloni
    Jul 22 at 22:15
  • $\begingroup$ Thanks! One part of your answer is interesting though: If $\kappa(V) ||E|| > ||E||^{\frac{1}{k}}$ the bound that does not use condition number at all is better. Given that you later claim it's practically not possible to distinguish, what should one do? As soon $\kappa(V) ||E|| > ||E||^{\frac{1}{2}}$ should we just declare it's a double root (since it's practically indistinguishable) and go with $ ||E||^{\frac{1}{2}}$ bound? $\endgroup$
    – alpx
    Jul 23 at 18:25
  • $\begingroup$ True. There is a constant in front of the $\|E\|^{1/k}$ but I don't know its exact value. I guess the only thing one can do is declare "possibly a double root" when the computed eigenvalues are at a distance less than $2\kappa(V)u$. Or, also, accept that this is an unanswerable question and try to use algorithms that don't require this distinction. Or switch to higher precision / exact computations. In the end, this is not different from many other questions in linear algebra, like "what is the rank of this matrix". $\endgroup$
    – Federico Poloni
    Jul 23 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.