3
$\begingroup$

I computed the first four eigenvalues of a quite large ($2^{24}\times 2^{24}$) but very sparse matrix. I used pythons in-build function sparse.linalg.eigsh to compute them. I need a validation that the results are correct up to an error of at most $10^{-3}$.

Very specifically I want to ask if there is a rigorous error-analysis involving rounding errors up to machine precision in each step.

More generally: Are there other practical algorithms for eigenvalues with such a rigorous error analysis.

$\endgroup$
  • 1
    $\begingroup$ "The results are correct up to an error of at most $10^{−3}$". Please define how to measure the error. For example, is it absolute error or relative error in $L^1$ or $L^2$ or $L^\infty$? Or just any reasonable interpretation? $\endgroup$ – John L. Feb 25 '19 at 23:19
2
$\begingroup$

It might suffice to ask the solver to give you both the eigenvalue $\lambda$ and the corresponding eigenvector $v$. Then you can verify for yourself how much error there is. Note that if $\lambda$ is the eigenvalue corresponding to eigenvector $v$, for matrix $M$, then we have $Mv=\lambda v$. So if you know $M$ and $v$ exactly, and you have a claim that $\hat{\lambda}$ is within $\epsilon$ of the true eigenvalue $\lambda$, it suffices to check that

$$(\hat{\lambda}-\epsilon)v \le Mv \le (\hat{\lambda}+\epsilon)v$$

where $\le$ is to be interpreted separately for each index, i.e., you should check that $(\hat{\lambda}-\epsilon)v_i \le (Mv)_i \le (\hat{\lambda}+\epsilon)v_i$ holds for each index.

If there is some error in the eigenvector $\hat{v}$ returned by the solver, then there is the possibility that the above check might fail, even if $\hat{\lambda}$ is indeed a true eigenvalue of the matrix. I don't know whether there's a nice way to adapt the above calculation to address this issue. If the operator norm $\|M\|_1$ is small, then it might work to check that

$$(\hat{\lambda}-\epsilon)\hat{v}_i -c \le M\hat{v} \le (\hat{\lambda}+\epsilon)\hat{v} + c$$

where $c = \|M - \hat{\lambda} \text{Id}\|_1 \times c'$ and $c'$ is an upper bound on the amount of error in $v$ (measured in $L_1$ distance) that you're willing to tolerate. I'm not sure if this is exactly right; there might be issues in this last criterion, so check it yourself before believing in it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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