Sharpness in rates of convergence for CG and symmetric Lanczos methods

Conjugate Gradient (CG) method is often used to solve a positive definite linear system Ax = b. Existing bounds suggest that the residual of the kth approximate solution by CG goes to zero like [( κ − 1)/(√κ+ 1)]k, where κ ≡ κ(A) = ‖A‖2‖A−1‖2 is A’s spectral condition number. It is well-known that for a given positive definite linear system, CG may converge (much) faster, known as superlinear convergence. The question is “do the existing bounds tell the correct convergence rate in general?”. An affirmative answer is given here by examples whose CG solutions have errors comparable to the error bounds for all k. A similar question for the convergence rate of Lanczos algorithm for symmet-ric eigenvalue problems is addressed and answered firmly, too. Conceivably examples devised here may be good testing problems for linear system and eigensystem solvers. 1This report is available on the web a