§ 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, Km⊆Km+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{A−1b,b,Ab,…Am−1x}(substitute x=A−1b)=Aspan{A−1b,b,Ab,…Am−1b}(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 xn∈Kn(A,b)x_n \in K_n(A, b). We define the residual as rn≡Axn−br_n \equiv A x_n - b.

§ Conjugate gradient descent