[Math] Comparing the maximum error between Lagrange, Hermite, and Spline Interpolation Methods

interpolationnumerical methods

I am reading Numerical Analysis by Atkinson. I am curious how do I choose the appropriate number of data points in each method so that I can make fair error comparisons?

Some background: For each of the three methods, I already have formulae describing the maximum error. For example, for the Hermite method, it is:

$$ |f(x) – Q_n(x)| \leq \frac{h_i^4}{384} \max |f^{(4)} (t)|$$

where $t$ lives in the interval $[x_{i-1}, x_i]$.

For a simpler comparison between the Lagrange method and the Hermite method, the book states the Lagrange method requires $3n+1$ data points and the Hermite method requires $2n+2$ data points. I agree with these figures. My understanding, then, is to make a fair comparison between these two techniques, the number of data points must be set equal and $n_i$ must be chosen appropriately. $i$ represents the index of the $i$-th technique. For example, $n_H \approx 1.5 n_L$. I agree with this, since if I want equal data points in both techniques, the number of hermite points must be approximately 1.5 times the number of Lagrange points.

In Spline interpolations, the number of data points is $4n-2$. This can be found on page 167 of Numerical Analysis by Atkinson.

So the running total is:

Lagrange $n \approx 3n_L$

Hermite $n \approx 2n_H$

Spline $n \approx 4n_S$

This seems to imply if I want to compare Hermite error and Spline error, the number of points in Hermite must be twice the number of points in Spline. That is, $n_H = 2 n_S$. However, this is exactly the opposite conclusion I am supposed to reach. I can verify this in two places in the book where $n_H = 0.5 n_S$. I am curious how this was reached.

Thank you in advance for your help.

Best Answer

The number of data points for spline interpolation is $n+1$. If you want to interpolate the function $f$ on the grid $x_0,x_1,\ldots,x_n$, the only data you use is the value of $f$ on the grid points, that is, you require the spline function $s$ to satisfy $$ s(x_i) = f(x_i), \qquad \text{for } i=0,1,\ldots,n. $$ Additionally, the spline function is required to be $C^2$ (twice continuously differentiable). That is, if $s_i$ denotes the restriction of $s$ to the interval $[x_i,x_{i+1}]$, then $$ s_{i-1}(x_i) = s_i(x_i) \quad\text{and}\quad s'_{i-1}(x_i) = s'_i(x_i) \quad\text{and}\quad s''_{i-1}(x_i) = s''_i(x_i) \qquad\text{for } i=1,2,\ldots,n-1. $$ This gives $3(n-1)$ additional conditions, which together with the $n+1$ interpolation conditions yield the total of $4n-2$ quoted by the original poster.

However, the only data used in the $4n-2$ conditions is $f(x_i)$ for $i=0,1,\ldots,n$ and this is $n+1$ pieces of data. The continuity conditions do not use any data from the function $f$.

Related Solutions

[Math] Finding error bounds for hermite interpolation

I think that should be $(x-1)(x-1.05)$ instead of $(x-1)^2(x-1.5)$

[Math] Interpolation of Gaussian function – minimize relative error

Comment (but probably not solution) too long for the comment field: The series of the exponential gives an alternating series for the given function

$$e^{-x^2}=1-x^2+\tfrac12 x^2-\tfrac16x^4+\tfrac1{24}x^8+\dots+\tfrac{1}{k!}(-x^2)^k+\dots$$

By the quantitative statements of the Leibniz criterion,

$$e_{2n-1}(-x^2)\le e_{2n+1}(-x^2)\le e^{-x^2}\le e_{2n}(-x^2),$$

where $e_n$ is the $n$-th partial sum of the exponential series and the estimate is true for $x^2<2n$. This gives an absolute error of

$$\frac1{(2n)!}x^{4n}\left(1-\tfrac{x^2}{2n+1}\right)\le\left|e_{2n-1}(-x^2)- e^{-x^2}\right|\le\frac1{(2n)!}x^{4n}$$

which shows that in terms of polynomial approximation, one can not do much better than the partials of the exponential series. To get a small relative error, one now needs to chose $n$ large enough to get

$$\frac{e^{15^2}(15)^{4n}}{(2n)!}<ϵ$$

or about

$$2n(\ln(2n)-\ln(225e))>225+|\ln(ϵ)|$$

Which means that you need $n=406,...,419$ to get $ϵ=10^{-4},...,10^{-18}$

Using arithmetic rules of the exponential, one notices that $e^{-x^2}=\left(e^{-(\tfrac{x}{m})^2}\right)^{m^2}$, for instance with $m=15$, and the relative error $ϵ$ is guaranteed if the partial sum $e_n$ is taken such that the relative error of $e_n(-x^2)$ to $e^{-x^2}$ on $[-\tfrac{15}m,\tfrac{15}m]$ is smaller than $\tfrac{ϵ}{2m^2}$. With $m=15$ this requires the easier to control inequality

$$\frac{e^1}{(2n)!}<\tfrac{ϵ}{450}$$

which gives the usual precisions for $n=6,...,12$.

$e_{811}(-15^2)$ on Magma has a gross error, instead of ...e-98 it shows 8e73.

$e_{21}(-\tfrac{x^2}{225})^{225}$ has relative error 5e-19 at $x=15$.

If only basic operations are allowed, then we go back to basic divide and conquer or half-and-square in this case. Take in the above calculus $m$ a nice power of $2$, $m=16$ could work, but let's take $m=32$. Then the error estimate is still largest at the interval end, and the condition at the even larger $x=16$ is

$$\frac{e^{\frac14} \left(\frac14\right)^{2n}}{(2n)!}<\tfrac{ϵ}{2048} \iff \frac{\sqrt[4]e}{2^{4n-11}(2n)!}<ϵ$$

Trying out some small values leads to $n=5$ as a likely candidate, and indeed, $e_9(-\tfrac{15^2}{1024})\cdot\exp(15^2)-1\approx -1e-10$

$n=4$ with $e_7$ works as well with an actual error of about $2e-7$, with error bound of actually $1e-6$.

With less than 30 operations, replace 7 by 9 for higher accuracy:

xx=-x*x/1024;
a=xx;
e=1+a;
for k=2 to 7 do a*=xx/k; e+=a; end for;
for k=1 to 10 do e=e*e; end for;
return e

or with a division

xx=x*x/1024;
a=xx;
e=1+a;
for k=2 to 7 do a*=xx/k; e+=a; end for;
e=1/e;
for k=1 to 10 do e=e*e; end for;
return e

Best Answer

Related Solutions

[Math] Finding error bounds for hermite interpolation

[Math] Interpolation of Gaussian function – minimize relative error

Related Question