Rigorous error bounds for eigenvalue solvers

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.

• "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? Feb 25 '19 at 23:19

1 Answer

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.