§ Krylov subspace method

This is a class of methods used to solve Ax=bAx = b, where AA is sparse. Krylov subspace methods are a class of methods which use the idea of a Krylov subspace. There is conjugate gradient (CG), GMRES (Generalized minimal residual method).
Km(A,v)span{v,Av,A2v,,Amv} K_m(A, v) \equiv span \{ v, Av, A^2v, \dots, A^m v\}
Clearly, KmKm+1K_m \subseteq K_{m+1}, and there is a maximum KNK_N that we can span (the full vector space). We are interested in the smallest index MM such that KM=KM+1K_M = K_{M+1}. We notice that KMK_M is invariant under the action of AA. Now, let's consider:
Km(A,x)span{x,Ax,A2x,Amx}=span{A1b,b,Ab,Am1x}(substitute x=A1b)=Aspan{A1b,b,Ab,Am1b}(Invariance of Krylov subspace)=span{b,Ab,Amb}=Km(A,b) \begin{aligned} K_m(A, x) &\equiv span \{x, Ax, A^2x, \dots A^m x \} \\ &= span \{ A^{-1} b, b, Ab, \dots A^{m-1} x \} \qquad \text{(substitute $x = A^{-1}b$)} \\ &= A span \{ A^{-1} b, b, Ab, \dots A^{m-1} b\} \qquad \text{(Invariance of Krylov subspace)} \\ &= span \{b, Ab, \dots A^m b\} \\ &= K_m(A, b) \end{aligned}
We learnt that Ax=bAx = b has a solution in Km(A,b)K_m(A, b). Using this, we can build solvers that exploit the Krylov subspace. We will describe GMRES and CG.

§ Generalized minimal residual --- GMRES

We wish to solve Ax=bAx = b where AA is sparse and bb is normalized. The nnth Krylov subspace is Kn(A,b)span {b,Ab,A2b,,Anb}K_n(A, b) \equiv span~\{b, Ab, A^2b, \dots, A^nb \}. We approximate the actual solution with a vector xnKn(A,b)x_n \in K_n(A, b). We define the residual as rnAxnbr_n \equiv A x_n - b.

§ Conjugate gradient descent