error for Conjugate gradient method

Question

Suppose A is a real symmetric 805*805 matrix with eigenvalues 1.00, 1.01, 1.02, ... , 8.89,8.99, 9.00 and also 10, 12, 16, 36 . At least how many steps of conjugate gradient iterations must you take to be sure of reducing the initial error ||e0||A by a factor of 10^-5 .

Answer 1

There is one well-known upper bound for the error estimate on the conjugate gradient solutions. Let $A$ be a positive definite matrix, and define the norm $\|v\|_{A} = \sqrt{v^{\ast} Av}$. If $x$ is the true solution and $x_n$ is the approximate solution after $n$ conjugate gradient iterations, and if the error is given by $e_n = x - x_n$, then

$$ \frac{ \|e_n\|_A}{\|e_0\|_A} \le \frac{2}{\left[ \left( \frac{\sqrt{\kappa} + 1}{\sqrt{\kappa} -1} \right)^n + \left( \frac{\sqrt{\kappa} + 1}{\sqrt{\kappa} -1} \right)^{-n} \right]}, $$

where $\kappa = \kappa_2(A)$ is the $2$-norm condition number of $A$, which is also equal to $|\lambda_{max}/\lambda_{min}|$, the ratio of the largest to smallest eigenvalues of $A$.

For a tighter estimate I think you would need to know a lot more about the structure of $A$ as it relates to $b$, if you're solving $Ax = b$.