Accuracy of finding eigenvalues of defective matrix

[wu_weidong]

Homework Statement

Hi all, I need help with determining the accuracy of finding eigenvalues of defective matrix.

The question asks: When a matrix has a defective eigenvalue, the condition number for computing its eigenvalues is infinity. Does this mean that these eigenvalues cannot be computed with any accuracy?

The question then asks: Consider the n-by-n matrices A with 1 on its diagonal and superdiagonal and 0 otherwise, and dA with A[n,1] = e > 0 and 0 otherwise. e is a constant. Suppose we compute the eigenvalues of A using a backward stable algorithm. Suppose the computed eigenvalues are the exact eigenvalues of A + dA. If e = 10^(-16), how many correct digits are obtained (as a function of n)?

The Attempt at a Solution

For part 1, I think the eigenvalues can still be obtained accurately by doing Schur factorization on the defective matrix. That would involve reducing it first to upper Hessenberg form, then reducing this upper Hessenberg matrix in an iterative manner (QR iterations) to Schur form. We can then read off the eigenvalues from the diagonal of the resulting upper triangular Schur matrix T. Am I right, and what is the accuracy of the eigenvalues obtained this way?

For part 2, I know that the accuracy of a backward stable algorithm depends linearly on the condition number of the problem. Also, if the condition number is k, the relative errors satisfy norm(f'(x) - f(x))/norm(f(x)) = O(k(x)*e_machine), where f'(x) is the algorithm and f(x) is the exact function. But I don't know what the condition number k(x) is here.

I've also read that for a defective n-by-n matrix, the characteristic polynomial is p(lamda) = det(A-lamda*I) = ((lamda - lamda_r)^m)*q(lamda) where m is the multiplicity of lamda_k and q(lamda) is the polynomial of degree n-m that does not vanish at lamda_k. A perturbation of size d in the matrix results in the change in the characteristic polynomial from p(lamda) = 0 to p(lamda) = O(d). The roots of this equation are lamda = lamda_k + O(d^(1/m)).

For the case here, the n repeated eigenvalues are 1, and d = e = 10^(-16). This means the eigenvalues are on a circle in the complex plane with center 1 and radius [10^(-16)]^(1/n), which means only 1/n of the digits obtained from the algorithm is correct. Am I right?

Thank you.

Regards,
Rayne

 

[mighty2000]

Hello Rayne,

You are correct in your understanding that the eigenvalues of a defective matrix can still be obtained accurately through Schur factorization. This method is known to be backward stable, meaning that the computed eigenvalues are the exact eigenvalues of a slightly perturbed matrix. However, the accuracy of the eigenvalues obtained through this method may still be affected by the condition number of the problem.

In part 2, you are on the right track in considering the accuracy of a backward stable algorithm to be dependent on the condition number. In this case, the condition number k(x) can be approximated by the ratio of the maximum perturbation in the input (in this case, d = e = 10^(-16)) to the maximum perturbation in the output (the computed eigenvalues). This ratio can be expressed as O(d^(1/m)), as you mentioned.

Therefore, for the case of a defective matrix with repeated eigenvalues of 1 and a perturbation of size d = 10^(-16), the accuracy of the eigenvalues obtained through Schur factorization would be 1/n, as you stated. This means that for an n-by-n matrix, the number of correct digits obtained would be 1/n * log10(10^(-16)) = 16/n. So, for a larger n, the accuracy would decrease.

I hope this helps. Let me know if you have any further questions.