Convergence with conjugate steps

Recall that the cost function in CG is quadratic:

$$\Vert x-x^{(k)}{\Vert }_A^2=(x-x^{(k)}{)}^{T}A(x-x^{(k)}).$$

After scaling by $A^{1/2}$, the level curves of the cost function become simple circles. At each step, we make an incremental correction to the solution that is orthogonal to all the previous steps (with the $A^{1/2}$ scaling). This is illustrated in the figure below.

Corollary. We obtain the exact solution in at most $n$ steps, where $n$ is the size of matrix $A$.