Arnoldi process

We now use the algorithm to compute $Q_k$ and $H_k$ to approximate the eigenvectors and eigenvalues of $A$.

We approximate the eigenvalues of $A$ using the eigenvalues of $H_k$:

$$\lambda (A)\approx \lambda (H_k).$$

We briefly outline why this is a reasonable idea. Consider the eigenvectors and eigenvalues of $H_k$:

$$H_k=X_k{\Lambda }_k{X}_k^{-1}$$

Use the previous equation with $Q_k$ and $h_{k+1,k}$:

$$Q_k(X_k{\Lambda }_k{X}_k^{-1})+h_{k+1,k}{q}_{k+1}{e}_k^T=A{Q}_k$$

Multiply by $X_k$ to the right:

$$A(Q_k{X}_k)=(Q_k{X}_k){\Lambda }_k+h_{k+1,k}{\mathbf{q}}_{k+1}{\mathbf{x}}_{k,}$$

We see that we have approximate eigenvectors and eigenvalues of $A$ assuming that $h_{k+1,k}$ is small:

$$A(Q_k{X}_k)\approx (Q_k{X}_k){\Lambda }_k$$

• ${\Lambda }_k$ are called the Ritz eigenvalues.
• $Q_k{X}_k$ are the approximate eigenvectors.

Arnoldi algorithm:

• Step 1: compute $H_k$ using the iteration starting from $q_1$.
• Step 2: Compute the eigenvalue of $H_k$.

$A{q}_j$ and $q_k^{T}A{q}_j$ only required!

Low flop count if $A$ is sparse.