Editing Arnoldi iteration (section)

==Finding eigenvalues with the Arnoldi iteration==

The idea of the Arnoldi iteration as an [[eigenvalue algorithm]] is to compute the eigenvalues in the Krylov subspace. The eigenvalues of ''H''<sub>''n''</sub> are called the ''Ritz eigenvalues''. Since ''H''<sub>''n''</sub> is a Hessenberg matrix of modest size, its eigenvalues can be computed efficiently, for instance with the [[QR algorithm]], or somewhat related, [[QR algorithm#The_implicit_QR_algorithm|Francis' algorithm]]. Also Francis' algorithm itself can be considered to be related to power iterations, operating on nested Krylov subspace. In fact, the most basic form of Francis' algorithm appears to be to choose ''b'' to be equal to ''Ae''<sub>1</sub>, and extending ''n'' to the full dimension of ''A''. Improved versions include one or more shifts, and higher powers of ''A'' may be applied in a single steps.<ref>David S. Watkins. [http://math.wsu.edu/faculty/watkins/slides/ilas10.pdf Francis' Algorithm] Washington State University. Retrieved 14 December 2022</ref>

This is an example of the [[Rayleigh-Ritz method]].

It is often observed in practice that some of the Ritz eigenvalues converge to eigenvalues of ''A''. Since ''H''<sub>''n''</sub> is ''n''-by-''n'', it has at most ''n'' eigenvalues, and not all eigenvalues of ''A'' can be approximated. Typically, the Ritz eigenvalues converge to the largest eigenvalues of ''A''. To get the smallest eigenvalues of ''A'', the inverse (operation) of ''A'' should be used instead. This can be related to the characterization of ''H''<sub>''n''</sub> as the matrix whose characteristic polynomial minimizes ||''p''(''A'')''q''<sub>1</sub>|| in the following way. A good way to get ''p''(''A'') small is to choose the polynomial ''p'' such that ''p''(''x'') is small whenever ''x'' is an eigenvalue of ''A''. Hence, the zeros of ''p'' (and thus the Ritz eigenvalues) will be close to the eigenvalues of ''A''.

However, the details are not fully understood yet. This is in contrast to the case where ''A'' is [[Hermitian matrix|Hermitian]]. In that situation, the Arnoldi iteration becomes the [[Lanczos algorithm|Lanczos iteration]], for which the theory is more complete.

[[File:Arnoldi Iteration.gif|framed|none|Arnoldi iteration demonstrating convergence of Ritz values (red) to the eigenvalues (black) of a 400x400 matrix, composed of uniform random values on the domain [-0.5 +0.5]]]