In the book

A Multigrid Tutorial - Briggs, Henson. McCormick

in the beginning of Chapter 3, it is mentioned that

...because the convergence factor behaves as 1-$O(h^{2})$, the coarse grid will have a marginally improved convergence rate...

Here, $h$ is the mesh spacing (say from Finite Difference Discretization).


How is this factor of $1-O(h^{2})$ derived ?

Does it mean solution on low resolution grids converges faster than high resolution grids ? But if this is the case then say $h=\frac{1}{2}$, then $1-\frac{1}{4}=\frac{3}{4}$ is the convergence rate.

When $h=\frac{1}{4}$ then the convergence rate is $1-\frac{1}{16}=\frac{15}{16}$.

Clearly the latter is more and hence fine grids have better convergence rates with this approximation. What am I missing ?


1 Answer 1


The convergence rate that is mentioned here is in the sense that the error in iteration $k$ and $k-1$ are related by $$ \| x^{(k)} - x^\ast\| \le r \| x^{(k-1)} - x^\ast\|, $$ which implies that $$ \| x^{(k)} - x^\ast\| \le r^k \| x^{(0)} - x^\ast\|. $$ For this to converge at all, we need that $r<1$, which the statement you quote provides. But for fast convergence, we need that $r$ is not marginally smaller than one, but ideally close to zero -- say, $r=0.1$, in which case you'd reduce the error by a factor of ten in each iteration. On the other hand, $r=1-ch^2$ is close to one if $h$ is small enough, and so it will take a large number of iterations until the reduction $r^k$ over the initial residual is substantial.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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