8
$\begingroup$

I read this answer, and realized I have been using the difference between sucessive iterates to define a stop criterion for an iterative method of finding eigenvalues/vectors.

What are good stop criteria for iterative methods that converge to eigenvalues and eigenvectors?

$\endgroup$
8
$\begingroup$

Youssef Saad's book Numerical Methods for Large Eigenvalue Problems, 2nd edition uses the norm of the residual vector to define convergence criteria. He defines the residual vector as follows on page 59:

Given a matrix $\mathbf{A} \in \mathbb{C}^{n \times n}$, a putative eigenvalue $\widetilde{\lambda} \in \mathbb{C}$ and a putative eigenvector $\widetilde{\mathbf{u}} \in \mathbb{C}^{n}$ associated with $\widetilde{\lambda}$, the residual vector $\mathbf{r}$ associated with the pair $(\widetilde{\lambda}, \widetilde{\mathbf{u}})$ is

$$\mathbf{r} = \mathbf{A}\widetilde{\mathbf{u}} - \widetilde{\lambda}\widetilde{\mathbf{u}}.$$

Many of the error results in Saad's book are stated in terms of the norm of the residual vector (generally the 2-norm), and he uses the norm of the residual vector as a metric for convergence whenever he presents numerical results. Based on that evidence, the stopping criterion would be

$$\|\mathbf{r}\| < \varepsilon.$$

SLEPc (based on PETSc), appears to use a similar convergence criterion in their hands-on exercises (they use $\|\mathbf{r}\|/\|\widetilde{\lambda}\widetilde{\mathbf{u}}\|$ in Exercises 1 and 2 instead).

However, LAPACK does not necessarily use that metric for convergence (see for instance, in LAPACK working note (LAWN) #15, using Jacobi's method for calculating eigenvectors and eigenvalues of symmetric positive definite matrices). The LAWNs are rather dense (pardon the pun) and technical, but if you're interested in seeing what high-quality implementations use for convergence, perhaps they're worth a detailed read.

$\endgroup$
  • $\begingroup$ From what I understand, for linear systems $Ax=b$, if $A$ is ill-conditioned, the residual can much smaller than the actual error of the solution vector $x$. Is the same true for eigenvalue problems? If so, what can we do to ensure that $u$ and $\lambda$ in our case are reasonably converged when the residual is small? $\endgroup$ – nukeguy Apr 4 '17 at 14:21

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.