2
$\begingroup$

Suppose I have a PDE in a rectangular domain that I am solving numerically via a finite difference method. How do I answer the question, "How fine do I need to make the grid to so that my solution is within $\epsilon$ of the true solution?" We can assume some basic interpolation scheme is used to fill in the points outside of the grid.

For a concrete example, we might consider solving a 2-d heat equation with Crank-Nicolson. But I'd like methods that apply more broadly.

My understanding is that for finite element methods, there is a well-developed theory of "a posteriori" estimates that answer my question. Does a theory providing rigorous error bounds exist for finite difference methods?

$\endgroup$
2
  • $\begingroup$ It may be useful for this to check out the Richardson extrapolation idea, en.wikipedia.org/wiki/Richardson_extrapolation $\endgroup$ May 24 at 23:03
  • $\begingroup$ @MaximUmansky I may be mistaken, but my undestanding is that Richardson extrapolation will not offer full rigorous error bounds, because the error estimates it provides rely on unknown constants in the a priori bounds for the FD method. (I suppose one could in principle follow the proofs to find those constants, however, but I have never seen this done.) $\endgroup$
    – alligator
    May 25 at 20:25

1 Answer 1

3
$\begingroup$

If the grid is fine enough, the numerical solution should depend on the grid spacing β„Ž as $𝑓(β„Ž)=𝑓_{𝑒π‘₯π‘Žπ‘π‘‘}+π΄β„Ž^𝑛$ where there are three unknown parameters $𝑓_{𝑒π‘₯π‘Žπ‘π‘‘}$, $𝐴$, $𝑛$ (the last one may be known apriori from the numerical algorithms used in the code). But even with three unknown parameters, with numerical solutions on three different grids, say with grid spacing $h$, $2h$, $4h$, you'll have three equations, that's enough to determine those three unknown parameters. After that, you'll know how small β„Ž has to be to make the error $\epsilon=π΄β„Ž^𝑛$ smaller than the tolerance.

$\endgroup$
5
  • 2
    $\begingroup$ I think this is essentially Richardson extrapolation? I agree for practical purposes this is excellent. However I think it is not enough for fully rigorous control, because really we have $f(h) = f_{\mathrm{exact}} + A h^n + B h^m + \dots$ where $m > n$, so the unknown $B$ is still there an uncontrolled. It can only be a serious problem if it huge, but I do not know of a proof that it is not huge... $\endgroup$
    – alligator
    May 25 at 21:35
  • 3
    $\begingroup$ Yes, this is the Richardson extrapolation idea. For a fine enough grid, only the smallest exponent would matter. $\endgroup$ May 25 at 21:39
  • $\begingroup$ Again, I agree in practice that is the case. However, I do not believe this method provides a rigorous and computable error guarantee, like a posterori methods do. Please correct me if I am wrong. $\endgroup$
    – alligator
    May 29 at 4:55
  • $\begingroup$ What posteriori methods are those? If you have in mind something specific, we should look at it and compare. $\endgroup$ May 29 at 5:05
  • $\begingroup$ Consider the following estimate, which I found in Sergey Repin's "A Posteriori Estimates for Partial Differential Equations," chapter 3. Consider Poisson's equation $\Delta u + f = 0$ on some domain $\Omega$ with boundary condition identically $0$. For a Galerkin approximation $u_h$ to the true solution $u$, we have $\| \nabla( u - u_h) \| \le C \| \Delta u_h + f \|$. Here $C$ is a constant from Friedirchs inequality for $\Omega$, which is easy to determine explicitly. Hence we obtain a rigorous error estimate with no uncontrolled constants. $\endgroup$
    – alligator
    May 29 at 5:18

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.