Re: Testable Predictions by HdB

In article <1128706142.819204.244630@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> Han.deBruijn@xxxxxxxxxxxxxx writes:
> Han de Bruijn wrote:
>
> > And a norm = 1/sqrt(2.pi.sigma) [ ... ]
>
> Aarghh!
>
> That must be: norm = delta/(sigma.sqrt(2.pi)) .
> Where delta is the (uniform) grid spacing.

Also does not seem to work. But as an afterthought, nothing is wrong
now. See below.

BTW, I did also the problem with the derivative of the 3-point and 5-point
Lagrange interpolation. The function I tested was exp(x), artificially
truncated to single precision. I wanted to calculate the derivative for
x = 1. In the routines all calculations are done in double precision.
I tested starting with a stepsize of 1, halving the stepsize in each try.
For the 3-point interpolation the optimal stepsize is 2^(-8) with an
(absolute) error of 2.10^(-5). For the 5-point interpolation the optimal
stepsize is 2^(-6) with an error of 1.10^(-6).

My implementation of your algorithm on both 5 points and 9 points does not
even come close.

Switching from exp(x) to exp(-x) the results for the Lagrange interpolations
are very similar. And my implementation of your algorithm still is not
very close.

I use 3, 5 and 9 point formulas because that makes the calculations of
the intermediate x values exact, as well as some of the intermediate
values used in your algorithm. So there are really three kinds of error
involved: the inexact function values (exaggerated to show the point),
truncation error (use of a finite formula) and rounding errors. The
influence of the truncation error we see because the 5-point Lagrange
interpolation gives better results than the 3-point interpolation, but
we see also that in the 5-point interpolation rounding errors and
initial errors have a greater influence.

As an afterthought I implemented your algorithm on 17, 33 and 65 points.
Increasing the number of points did increase the precision, except that
an increase from 33 to 65 points had no effect. With exp(x) the optimal
results are as follows:
5 points 9 points 17 points 33 points 65 points
h 2^(0) 2^(-2) 2^(-6) 2^(-10) 2^(-10)
err 1.244e0 2.325e-1 3.335e-4 3.017e-6 3.017e-6

Decreasing h beyond that figure indeed had bad effects on the precision.
Just as I "predicted".

Conclusion: your algorithm works, but straightforward interpolation with
a polynomial works better with less effort. You do need 33 function
evaluation to even get better than the precision of a 3 point polynomial
interpolation, and apparently your algorithm does not beat a 5 point
polynomial interpolation at all. And in *all* algorithms there is an
optimal stepsize, with smaller stepsizes the result is worse.

BTW, changing float to double everywhere (and so reducing the initial
error on function evaluation) gives the following result:
method optimal h error
L-3 p 2^(-19) 1.264e-10
L-5 p 2^(-17) 2.367e-13
HdB 5 p 2^0 1.244e+00
HdB 9 p 2^(-2) 2.326e-01
HdB 17 p 2^(-6) 3.339e-04
HdB 33 p 2^(-20) 2.896e-11
HdB 65 p 2^(-19) 8.563e-12
I do not think I need to change my conclusions.

(For my program see: <http://www.cwi.nl/~***/private/deriv.c>.)
--
3 point interpolation for f'(x) with stepsize h:
(f(x + h) - f(x - h))/(2.h)
5 point interpolation:
(f(x - 2.h) - 8.f(x - h) + 8.f(x + h) - f(x + 2.h))/(12.h)
(The latter formula thanks to Maple.)
--
*** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~***/
.