# 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.$$

• thanks Prof, I get it. Furthernore, I want to ask another question about fast solver to the Poisson equation. I have known that in 1D and 2D about Poisson, matlab 'A\b' is very fast and I have tested in matlab, but in 3D 'A\b' tends to be slow for large sparse matrix A. I have heard that in matlab, there is a function 'fft'(fast fourier transformation) can solve Ax=b quickly, but I can not understand that. Can you give me the matlab impelementation codes that I can easily understand how matlab use 'fft' (or other fast methods) to solve this Ax=b quickly? Thanks vey much, my Professor. – sunshine Oct 28 '19 at 5:28
• @Zhen-WeiSun: That's a separate question -- ask it separately on StackExchange. – Wolfgang Bangerth Oct 29 '19 at 20:59