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

  • $\begingroup$ 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. $\endgroup$
    – sunshine
    Oct 28 '19 at 5:28
  • $\begingroup$ @Zhen-WeiSun: That's a separate question -- ask it separately on StackExchange. $\endgroup$ Oct 29 '19 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.