Accuracy of eigenvalues vs. their magnitude

Open discussion regarding features, bugs, issues, vendors, etc.

Accuracy of eigenvalues vs. their magnitude

Postby mike.wimmer » Tue Dec 11, 2012 10:52 am

Dear all,

frequently, one finds (especially in non-math publications) statements like "larger eigenvalues are computed more stably than small eigenvalues". In my understanding, such statements might be true for simple power methods. However, looking at the formulas given for the condition of eigenvalues given in the Lapack user guide, the magnitude of the eigenvalues does not enter. Moreover, modern eigenvalue methods use shifts, and hence should not suffer from this problem.

Is there in LAPACK today still any truth to "larger eigenvalues are computed more stably than small eigenvalues"?
mike.wimmer
 
Posts: 6
Joined: Thu Feb 19, 2009 6:27 am

Re: Accuracy of eigenvalues vs. their magnitude

Postby Julien Langou » Tue Dec 11, 2012 2:30 pm

For all current LAPACK symmetric eigensolvers, the error on the i-th eigenvalue
is proportional to machine precison times the largest (in magnitude)
eigenvalue. So the relative error might be large for small (in magnitude)
eigenvalues indeed. This is what people means with the statement
``larger eigenvalues are computed more stably than small eigenvalues''.
It might be better to say ``larger (in magnitude) eigenvalues are computed with
higher relative accuracy than small (in magnitude) eigenvalues''.

This is what is written in Section 4.7.1 of LAPACK Users' Guide in the formula:
Code: Select all
| exact_lambda_i - computed_lambda_i | <= p(n) . epsilon . exact_lambda_max


Note: to get high relative accuracy for each eigenvalue (lambda_i), you would need
to have the exact_lambda_i on the right most side instead of exact_lambda_max.

Note: we have one singular value solver which enables high relative accuracy for
all singular values. This is a contribution from Zlatko Drmac and Kresimir
Veselic and this uses ``Jacobi SVD''. No such method for the symmetric
eigenvalue problem.
Julien Langou
 
Posts: 734
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

Re: Accuracy of eigenvalues vs. their magnitude

Postby mike.wimmer » Tue Dec 11, 2012 4:24 pm

Thank you very much, I had simply overlooked the ||A|| factor. My main interest actually is in the nonsymmetric eigenvalues algorithms, but I see that also those have a global factor proportional to the norm of the matrix. As far as I know, in the nonsymmetric case ||A||_2 >= lambda_max, so the only difference to the symmetric case is the individual factor s_i of each eigenvalue, is that right?
mike.wimmer
 
Posts: 6
Joined: Thu Feb 19, 2009 6:27 am


Return to User Discussion

Who is online

Users browsing this forum: No registered users and 6 guests

cron