1

When some quantity $x$ (e.g., the values of a solution of a PDE, using a finite difference method) is calculated numerically, we get its approximate value $x^*$. The error is $|x-x^*|$. But since we don't know $x$ itself, how is it possible to find the rrror?

C.HICHAM
  • 13

1 Answers1

2

Typically, the accuracy of the numerical approximation hinges on a parameter $h>0$ such as the time step when integration ordinary differential equations or the spacing between grid points when solving the Laplace equation on a square using the standard five point finite difference stencil with a fixed step size. You will frequently have an asymptotic error expansion of the form \begin{equation} T - A_h = \alpha h^p + \beta h^q + O(h^r), \quad p < q < r. \end{equation} Here $T$ is your target, i.e. the number which you which to compute, $A_h$ is the approximation obtained used the parameter $h$, $\alpha$ and $\beta$ are constants which depend on the target, but are independent of $h$ and the numbers $p < q < r$ reflect the properties of you method. You can estimate the principal error term, i.e. $\alpha h^p$ as follows \begin{equation} \alpha h^p \approx \frac{A_h - A_{2h}}{2^p - 1} \end{equation} provided that $h$ is sufficiently small. This can be judged by evaluating the fraction \begin{equation} F_h = \frac{A_{2h}- A_{4h}}{A_h - A_{2h}} \end{equation} which tends to $2^p$ and is close to $2^p$ precisely when the above approximation is good.

Carl Christian
  • 12,583
  • 1
  • 14
  • 37
  • thank you so much Calr christian – C.HICHAM May 12 '16 at 22:35
  • Note that you need to know $p$ to use the extrapolation procedure and you haven't actually stated how to get that. – Ian May 12 '16 at 23:16
  • @Ian: The order of accuracy $p$ in many cases can be derived theoretically and is valid for a class of "sufficiently smooth" functions. The a posteriori estimate of error depends on "higher order" derivatives of the function being approximated, and these are not ordinarily available (since the function itself is unknown). – hardmath May 12 '16 at 23:33
  • @Ian: I have told the OP how to estimate $2^p$ using numerical data, i.e. $A_h$, $A_{2h}, A_{4h}$. – Carl Christian May 13 '16 at 06:34
  • @CarlChristian It's actually a bit misleading; Richardson extrapolation would view that term as actually exactly canceling when you take the extrapolated combination. Still, I get your point. Nice approach. – Ian May 13 '16 at 15:47
  • 1
    @Ian: Thank you very much. I sincerely do not understand what you it is that you perceive as misleading. The number $A_h$ is the original approximation. The extrapolated value is $G_h = A_h + (A_h - A_{2h})/(2^p-1)$. Certainly, it is possible to say much, much more about the behavior of Richardson's fraction both in exact and in floating point arithmetic but that is not what you are mean, right? One can argue that I should half the step size rather than doubling it, but in my experience it makes for a more messy analysis which does not work well during the initial presentation. – Carl Christian May 13 '16 at 22:06
  • @CarlChristian Oh, I'm sorry, I didn't notice that you were not using the weighted forms of the $A_h,A_{2h},A_{4h}$ in the error estimate. Never mind, it's fine. – Ian May 13 '16 at 22:26
  • @Ian. Great, no worries then. Enjoy your weekend. – Carl Christian May 13 '16 at 22:35
  • @CarlChristian Hello! Just reviewing you answer along side my class notes. My notes use the half-step size as you mentioned in an above comment. The derivation for this looks quite simple and has been working for me on my homework. I was wondering what you meant by "does not work well during the initial presentation."? – rocksNwaves Apr 06 '18 at 12:39
  • @rocksNwaves: There are two aspects to consider. The first is the trivial matter of clarity and speed of deriviation when you are working at the board in front of the class. It is simpler to deal with integers than fractions and all students can follow you. More importantly is a the following much more subtle point. You have computed $A_h$ at great computational cost. How well did you do? You need $A_{2h}$ to estimate your error. Can you afford that? Certainly: in the case of numerical integration it is often free, because you recycle old data. At worst, it costs around 50% of the time ... – Carl Christian Apr 06 '18 at 14:37
  • @rocksNwaves: ... of the time you have already spent. Probably, you can afford that as well. If you develop the theory in the other direction, this point becomes less clear, at least in my opinion and experience. – Carl Christian Apr 06 '18 at 14:40
  • @CarlChristian wonderful explanation, thank you! – rocksNwaves Apr 07 '18 at 15:43