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.

  • $\begingroup$ For people unfamiliar with Atkinson's book, it may be useful to note that the discussion in there assumes piecewise cubic interpolants. $\endgroup$ – Jitse Niesen Sep 19 '11 at 11:10

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$.

  • $\begingroup$ Thank you. My understanding is the number of data points for each technique is the number of data points from the function $f$. $\endgroup$ – jrand Sep 22 '11 at 19:06

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.