# Explanation of subspace strategy regarding CG described in Golub's book

I was wondering about the last paragraph in Matrix Computations (4th edition) by Golub, Chapter 11 (11.3.3), specifically his explanation of subspace strategy for Conjugate Gradient.

Note that in Algorithm 11.3.1, the step-k optimization is over the affine space $$x_k + span\{\nabla\phi(x_k)\}$$.

Given that $$Ax_0 \approx b$$, our plan is to produce a nested sequence of subspaces

$$\space S1 \subset S_2 \subset S_3 \subset \cdots$$

that satisfy $$dim(S_k) =k$$ and to solve the problem $$\underset{x\in x_0 + S_k}{min} \phi(x)$$ each step along the way.

If $$x_k$$ is the step-k minimizer, then because of the nesting we have $$\phi(x_1)\geq \phi(x_2) \geq \cdots \phi(x_n)=\phi(x_*)$$. since $$S_n = \mathbb{R}^n$$, we ultimately obtain $$x_* = A^{-1}b$$. Even though this is a finite-step solution framework, it may not be attractive if $$n$$ is extremely large. The challenge is to find a subspace sequence that promotes rapid decrease in the value of $$\phi$$, for then we may be able to terminate the iteration long before $$k$$ equals $$n$$.

With this goal in mind we note that at $$x_k$$ the function $$\phi$$ decreases most rapidly in the direction of the negative gradient. Thus, it makes sense to choose $$S_{k+1}$$ so that it includes $$x_k$$ and the gradient $$g_k = \nabla\phi(x_k) = Ax_k -b$$. This strategy guarantees that $$x_{k+1}$$ is at least as good as a steepest descent update:

$$\underset{x\in x_0 + S_{k+1}}{min} \phi(x_{k+1} \leq \underset{\mu \in \mathbb R}{min}\space \phi(x_k -\mu g_k )$$

If $$x_0$$ is an initial guess and we define $$g_0 = Ax_0 -b$$, then since $$\nabla \phi(x_k) \in span \{x_k,Ax_k\}$$ it follows that the only way to satisfy this requirement is to set:

$$S_k = \mathcal{K}(A,g_0,k) = span\{g_0, Ag_0, A^2g_0,\dots, A^{k-1}g_0\}$$

Why does Golub write that $$\nabla \phi(x_k)\in span(x_k, Ax_k)$$?

I don't understand how this is possible since $$\nabla\phi(x_k) = Ax_k -b$$, how do you get $$b$$ from $$span(x_k, Ax_k)$$?

I think there's something trivial that I'm missing here...

• It might just be some kind of typo. I know that the end result is correct, but with $A=I$ and $x_0 = e_1$, this cannot hold for any $b$. – Thijs Steel Mar 22 '20 at 16:54