# Why the iteration steps become twice if the step size reduces half for CG methods?

For CG method for SPD matrices, (Ax = b arising from Poisson equation with homogeneous boundary condition) we know that the convergence theorem: After m steps of iteration, the error $$e^{(m)}=x-x_m$$ satisfies the bound that $$\|e^{(m)}\|_A\leq 2(\frac{\sqrt{k}-1}{\sqrt{k}+1})^m \|e^{(0)}\|_A,$$$$\quad k = cond_2(A)=\lambda_{max}/\lambda_{min}.$$

My question is when the step size $$h$$ reduces half, and the condition number is $$O(h^{-2})$$, why the iteration step increases twice so that the relative error satisfies a pre-selected tolerance $$\epsilon$$? Can someone give me some proof? thanks very much.

Let's say the condition number of the original matrix is $$k_1$$, and the one after refining the mesh is $$k_2=4k_1$$. You then want to compare the number of iterations necessary to reach a tolerance $$\varepsilon$$. So, assuming you are interested in a relative tolerance, in the first case, you get $$\left(\frac{\sqrt{k_1}-1}{\sqrt{k_1}+1}\right)^{m_1} = \varepsilon$$ which yields $$m_1 = \frac{\log\varepsilon}{\log \left(\frac{\sqrt{k_1}-1}{\sqrt{k_1}+1}\right)}.$$ Because generally condition numbers are large, the fraction in the logarithm will be just barely smaller than one, and you can do a Taylor expansion around $$k=\infty$$ to find that $$m_1 \approx -(\log\varepsilon)\sqrt{k_1}.$$ (The negative sign accounts for the fact that for small $$\varepsilon$$, the log is negative.)
By the same argument, you then get $$m_2 \approx -(\log\varepsilon)\sqrt{k_2} = 2 m_1.$$