Krylov methods for sparse systems

3 main methods:

• CG: conjugate gradients; for symmetric positive definite matrices
• MINRES: for symmetric matrices
• GMRES: for general matrices

Compared to classical iterative methods based on splitting, Krylov methods get much more accurate estimates by using the Krylov subspace:

$$\mathcal{K}(A,b,k)=\text{span}\{b,Ab,A^{2}b,\dots ,A^{k-1}b\}$$

The goal of these methods is to find an “optimal” solution in the Krylov subspace.

We search for solutions of the form

$$x^{(k)}=Q_k{y}_k$$

where $Q_k$ is an orthogonal basis of the Krylov subspace $K_k$. Vector $y_k$ is defined as

$$y_k={\mathrm{argmin}}_y\Vert x-Q_{k}y\Vert$$

What norm should we use?

The naive choice is

$$\Vert x-x^{(k)}{\Vert }_2=\Vert x-Q_k{y}_k{\Vert }_2$$

But solving the least-squares problem requires knowing $Q_k^{T}x$. This is not possible, unfortunately. So other ideas are required.