1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Accuracy of finding eigenvalues of defective matrix

  1. Nov 6, 2007 #1
    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.

  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?

Similar Discussions: Accuracy of finding eigenvalues of defective matrix
  1. Finding Area (Replies: 0)

  2. Matrix Question (Replies: 0)

  3. Vandermonde matrix (Replies: 0)

  4. Finding Delta (Replies: 0)