1

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.

Happy
  • 961
  • 4
  • 11

1 Answers1

4

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

Wolfgang Bangerth
  • 55,373
  • 59
  • 119
  • 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. – Happy Oct 28 '19 at 05:28
  • @Zhen-WeiSun: That's a separate question -- ask it separately on StackExchange. – Wolfgang Bangerth Oct 29 '19 at 20:59