Convergence of the Conjugate Gradients

Like the Lanczos process, the convergence of CG is well understood.

The convergence is very fast and, to some extent, “optimal.” We can prove that:

$$\Vert x-x^{(k)}{\Vert }_2\le 2\Vert r^{(0)}{\Vert }_{A^{-1}}(\frac{1-{\kappa }^{-1/2}}{1+{\kappa }^{-1/2}}{)}^k$$

where $\kappa$ is the condition number of $A$.

The number of iterations is: $k=O(\sqrt{\kappa }\ln {ϵ}^{-1}).$

The matrix sizes in this benchmark are equal to 512. Below are the condition numbers for each test case.

	Condition Number
well-conditioned	101
3D Laplacian	33k
2D Laplacian	54k