## Arnoldi's method

Arnoldi’s method is an algorithm that was originally used to reduce an
arbitrary matrix to Hessenberg form.
However, it can also be used to approximate eigenvalues as shown in the
following.

The following pseudocode illustrates Arnoldi’s method:

```
choose initial vector v(1) with ||v(1)|| = 1
for j = 1,...,m
w = A*v(j)
for i = 1,...,j
h(i,j) = <w, v(i)>
w = w - h(i,j)*v(i)
h(j+1,j) = ||w||_2
v(j+1) = w / h(j+1,j)
```

The procedure starts with an arbitrary normalized vector .
Then it iteratively computes a *Krylov subspace* . The whole
system of Krylov vectors is orthogonalized using Gram-Schmidt
orthogonalization.

Projecting the matrix $`A`

$ onto this Krylov subspace then yields

where is the matrix containing the Krylov vectors computed by the
Arnoldi method and is an upper Hessenberg matrix of dimension .
Since the dimension of the Hessenberg matrix is usually much smaller than that
of the original matrix the eigenvalues of can efficiently
computed by the QR method. The obtained eigenvalues are called *Ritz
eigenvalues* and they converge to the largest eigenvalues of .

Related programs:
Related disciplines:
Eigenvalue problems ·