= Conjugate gradient convergence bound
{title2=$\|e_k\|_H\leq2\left(\frac{\sqrt{\kappa_2(H)}-1}{\sqrt{\kappa_2(H)}+1}\right)^k\|e_0\|_H$}
For a <symmetric positive-definite matrix> $H$, the <Conjugate gradient method> minimizes the error in the induced <weighted norm> over its affine <Krylov subspace>. Writing the error as $p(H)e_0$ gives
$$
\frac{\|e_k\|_H}{\|e_0\|_H}\leq\min_{\deg p\leq k,\ p(0)=1}\max_{\lambda\in[\lambda_{\min},\lambda_{\max}]}|p(\lambda)|.
$$
For $\lambda_{\min}<\lambda_{\max}$, choose the scaled <Chebyshev polynomial> $p(\lambda)=T_k((\lambda_{\max}+\lambda_{\min}-2\lambda)/(\lambda_{\max}-\lambda_{\min}))/T_k((\lambda_{\max}+\lambda_{\min})/(\lambda_{\max}-\lambda_{\min}))$. On the spectral interval its numerator has absolute value at most one. With $\rho=(\sqrt\kappa+1)/(\sqrt\kappa-1)$, the denominator equals $(\rho^k+\rho^{-k})/2\geq\rho^k/2$. This proves the displayed bound. If the two endpoints coincide, $H$ is a positive scalar multiple of the identity and one iteration solves the system exactly.
Back to article page
