# error for Conjugate gradient method

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 .

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$.
There is another upper bound for the error: $$\|x_k - x^*\|_A^2 \le \left ( \frac{\lambda_{n - k} - \lambda_1}{\lambda_{n - k} + \lambda_1} \right )^2 \| x_0 - x^* \|_A^2,$$ where $\lambda_n \ge \ldots \ge \lambda_1$.