Arnoldi iteration

An Algorithm to compute a Orthonormal basis for a given Krylov subspace, essentially using a Gramh-Smith procedure

At a certain step $m\le n$ breakdown wil happe, this means $w_m=0$ and the process stops. At every step the orthonormal vectors $v_i$ $i=1,\dots ,k+1$ can be stored in the matrix $V_{k+1}\in {\mathbb{R}}^{n\times (k+1)}$.

When $k<m$, before breakdown, holds:

$$A{V}_k=V_{k+1}{\hat{H}}_k$$

where ${\hat{H}}_k\in {\mathbb{R}}^{(k+1)\times k}$ is the matrix formed by the overlaps $h_{i,j}$. By construction, ${\hat{H}}_k$ is an upper hessember matrix.

To prove the equality above, note that for every $j\le k$, the following holds:

$$A{v}_j=h_{1,j}{v}_1+\cdots +h_{j,j}{v}_j+h_{j+1,j}{v}_{j+1}$$

For $k\le m$ we have:

$$V_k^{T}A{V}_k=H_k$$

where $H_k\in {\mathbb{R}}^{k\times k}$ is the matrix ${\hat{H}}_k$ without the last row. To prove this, first consider the case $k=m$, i.e. breakdow has happened; we have $h_{m+1,m}=0$, so that $A{V}_m=V_m{H}_m$. In general, when $k<m$ $V_k^T{V}_{k+1}=I_{k,k+1}$ (the $k$ identity matrix with an added coulumn of zeros). So in the end:

$$V_k^{T}A{V}_k=V_k^T{V}_{k+1}{\hat{H}}_k=I_{k,k+1}{\hat{H}}_k=H_k$$

We can think of $H_k$ as the projection of $A$ onto the Krylov subspace using the base $V_k$.

Arnoldi iteration to compute eigenvalues §

We can emply arnoldi iteration to approximate eigenvalues of big, sparse, non symmetric matrices.

Let $A\in {\mathbb{R}}^{n\times n}$, consider the eigenvalue problem:

$$Ax=\lambda x,$$

Call the eigenvalues ${\theta }_i$ $i=1,\dots ,k$ of the upper hessemberg matrix $H_k$, called Ritz values of $A$. We can compute them using QR method, exploiting the fact that is upper hessember. The Ritz values are approximation of the eigenvalues of $A$.