# Homework Help: Accuracy of finding eigenvalues of defective matrix

1. Nov 6, 2007

### wu_weidong

1. The problem statement, all variables and given/known data

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)?

3. 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