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?

Improve this question
$\endgroup$
2
  • $\begingroup$ It may be useful for this to check out the Richardson extrapolation idea, en.wikipedia.org/wiki/Richardson_extrapolation $\endgroup$
    – Maxim Umansky
    Commented May 24, 2022 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
    Commented May 25, 2022 at 20:25

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented May 25, 2022 at 21:35
  • 3
    $\begingroup$ Yes, this is the Richardson extrapolation idea. For a fine enough grid, only the smallest exponent would matter. $\endgroup$
    – Maxim Umansky
    Commented May 25, 2022 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
    Commented May 29, 2022 at 4:55
  • $\begingroup$ What posteriori methods are those? If you have in mind something specific, we should look at it and compare. $\endgroup$
    – Maxim Umansky
    Commented May 29, 2022 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
    Commented May 29, 2022 at 5:18

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.