# Upper bounding polynomial interpolation error

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?

• Could you find out how "interpolation with a quadratic polynomial" is done on the table? The most natural way would be to take 3 consecutive values, but this would cover each sub-interval twice. Or seen differently, after finding the interval that the argument falls into, how to chose the additional value from the table? Split the interval in the middle and chose the closest one? Mar 15, 2017 at 8:49

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