2
$\begingroup$

I'm not sure that this *overflow is right place to ask.... Sorry if it is off topic.

Does anyone know a citation (scientific article or book) for a numerical trick (method), when we tabulate a right-hand side of given differential equation(s) and use an interpolation in between rows of the lookup table when we numerically integrate PDEs/ODEs.

This trick speeds up computations but, of course, reduces an accuracy.

The method is well known, but I couldn't find any references in scientific literature.

Also any estimation of how to select correct number of points in lookup table to reach required accuracy of solution will be very helpful.

P.S. I have to clarify the question due to a several answer which aren't answer for my question:

If I have $\frac{dx}{dt} = f(x)$, I can create a lookup table of $y_i=f(x_i)$ for some range of $x_i$. This table is in a memory. I can use interpolation between rows in this table instead of evaluation function $f(x)\approx y_i+\frac{y_{i+1}-y_{i}}{x_{i+1}-x_{i}}(x-x_i)$, which is faster than a direct calculation of $f(x)$.

$\endgroup$
  • $\begingroup$ I wouldn't call it a dirty trick but I assume you are talking about piecewise linear interpolation. If the entries in your table are for equally-spaced values of your independent variable, for a given value of the independent variable you can directly find the appropriate index in the table. How accurate this linear interpolation is depends very much on the specific function you are trying to interpolate. $\endgroup$ – Bill Greene Jan 25 '17 at 18:45
  • $\begingroup$ @BillGreene Yes, you are absolutely right! But is there any name for this approach? I gave up to find any references for this method. All my books on numerical methods have nothing inside. Any references? Please! $\endgroup$ – rth Jan 25 '17 at 19:34
  • $\begingroup$ "piecewise linear interpolation" is the only name I recall seeing. I don't have a particular reference in mind but if I google that phrase there are many hits. $\endgroup$ – Bill Greene Jan 25 '17 at 19:48
  • $\begingroup$ @BillGreene Unfortunately "piecewise linear interpolation" gives me references for interpolation, but not for usage it to speed up P/ODE calculations... Sorry it doesn't work! $\endgroup$ – rth Jan 26 '17 at 4:42
  • $\begingroup$ You won't find references because the literature would assume this is elementary. However, if you mean "higher order interpolations", like the dense output for ODEs, then the reference depends on the integration method. $\endgroup$ – Chris Rackauckas Jan 27 '17 at 17:21
2
$\begingroup$

I wouldn't say that it is a trick (interpolation is one of the most basic numerical techniques) and I don't see why it would be "dirty" (though it may be inaccurate). I don't think there is a special name attached to interpolation between solutions of a differential equation.

$\endgroup$
  • $\begingroup$ I need a citation to use it in my paper. I couldn't find any scientific source (article or book), which can be cited. This technique is well known, but have anyone described it in scientific literature? $\endgroup$ – rth Jan 26 '17 at 19:38
  • 1
    $\begingroup$ If you didn't learn about it by reading a paper, I don't think you need a citation to use it in your paper. $\endgroup$ – David Ketcheson Jan 26 '17 at 20:18
  • $\begingroup$ I'm a scientist. I learned about this method from code, but it is really weird that numerical methods guys did not study this method in details. I couldn't believe, it must be in each textbook with estimations of O() and so on. And it is very risky to use method which wasn't properly studied. $\endgroup$ – rth Jan 26 '17 at 20:30
1
$\begingroup$

If I understand the question, the name I have always known for this kind of tabular integration is "numerical quadrature". In the days of calculating machines this was the only way of going about solving differential equations. It was important to minimise the number of points at which you have to calculate the right hand side of $y' = f(x)$.

One very effective method of achieving this was referred to as "Richardson's deferred approach to the limit" in which you can choose two different step sizes, $h_1$ and $h_2$, to define points at which you evaluate $f(x)$. If using these two step sizes results in estimates $f_1$ and $f_2$ for the value at a specific point, you can combine these to produce an answer which is better than if you had picked a finer resolution.

Famously, if $h_1 = 2 h_2$, then $f = f_2 + (f_2 - f_1)/3$ is $O(h^3)$.

In effect, a "free lunch". If the accuracy was still not good enough, you would choose a smaller $h_3$, and so on. There were many papers on the choice of sequence $\{h_i\}$. The method was also adapted for extrapolation and for summing slowly convergent series.

This was first discussed by Richardson and Gaunt, 1926, Phil. Trans. A, 226, 299-361. When solving ODE's we refer to this as Richardson Extrapolation, see Press et al. Numerical Recipes Section 16.4 et. seq. in the context of the important Bulirsch-Stoer method for solving ODE's.

$\endgroup$
  • $\begingroup$ Thank you so much for your efforts and answer. I really apologize, for unclear question (see P.S. to my post). I believe word interpolation triggers incorrect interpretation of my question. I didn't mean interpolation between several step sizes, I mean interpolation instead of evaluation ofr RHS of equation. $\endgroup$ – rth Jan 30 '17 at 21:33
  • $\begingroup$ @rth: It's clear now, thanks. A remark about accuracy: your linear evaluation of f(x) at the required value x requires values at a point either side of x: x(i) and x(i+1) and the corresponding f(i) and f(i+1). If you use two points either side, x(i-1), x(i), x(i+1), x(i+2) (but not necessarily equally spaced) you can use the Richardson-Aitken trick to improve the accuracy at f(x). It's quicker and computationally far cheaper than using local orthogonal polynomial fits, but obviously not as accurate as some other methods involving a greater number of function evaluations. $\endgroup$ – JonesTheAstronomer Jan 31 '17 at 17:03

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.