I'm studying polynomial interpolation right now, and the problem below is leading me to believe I might be missing something fundamental. Here's the question, and then I'll explain what's confusing me:
Determine the spacing $h$ in a table of equally spaced values of the function $$f(x) = \sqrt x$$ on $[1,2]$, so that interpolation with a quadratic polynomial will yield an accuracy of $5 × 10^{−8}$ .
Now, I know how to build a degree-$n$ interpolating polynomial, given $n+1$ points. I also know that we can upper bound the error of the interpolating polynomial by
$$E(x) \leq \frac{M}{4(n+1)}*h^{n+1} $$ where $$M = \max_{\xi \in [1,2]}f^{n+1}(\xi)$$
Here is where I'm not sure how to proceed with the problem: If we wish to make the error smaller, our options are to either increase $n$, or decrease $h$. But increasing $n$ means changing the degree of the polynomial, and the question says that we're using a quadratic. However, if we decrease $h$ but retain $n=2$, then our interpolating points will not span $[1,2]$.
The solution says that
For an accuracy of $5*10^{-8}$, we must have $\frac{h^3}{24\sqrt 3} < 5*10^{-8}$, giving $h ≈ 0.01028$ or $N ≈ 79$.
How can we have $n = 79$ if we're using a quadratic interpolation?
To get an approximate value at some argument $x$ from a function table of pairs $(x_k,y_k)$ like this example, you would in first approximation seek the point $x_k$ closest to $x$ and return its value.
To get more precision, you could find the interval so that $x\in[x_{k-1},x_k]$ and use linear interpolation.
To get even more precision, you would again seek the closest $x_k$ and use quadratic interpolation from the pairs at index $k-1,k,k+1$. The error $$ (x-x_k+h)(x-x_k)(x-x_k-h)\frac{f^{(3)}(\xi)}{6} $$ would be largest in its first factor at $x=x_k\pm \frac h2$, so that the error of this procedure is smaller than $$ \frac{M_3h^3}{16} $$ Note that this procedure only needs an error estimate over $[x_k-\frac h2,x_k+\frac h2]$, not for the full interval $[x_{k-1},x_{k+1}]=[x_k-h,x_k+h]$.
Now find $M_3=\sup_{\xi\in[1,2]}|f'''(\xi)|$ and from there compute $h$.