Comparing the maximum error between Lagrange, Hermite, and Spline Interpolation 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.
 A: 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$. 
