error of linear interpolation

Question

I have two points $x_1, x_2$ between which I would like to have a linear interpolation $P_1$. Those two points are just points where I know the value of the underlying function $f$. I know that the error at any point between the two will be bounded by the second derivative of the function $\sup_{x\in[x_1,x_2]}f^{''}(x)$ and some multiplying constant. Thus, I have to require that the second derivative exist and bounded. However, assume my underlying function is only continuous, for example $|x|$, so the second derivative exist only in a weak sense, it is defined a.e. except this bad point $0$. So, what is the resulting error then? Does it depend on the fact that $0$ is one of those points $x_1$ or $x_2$, but what if $0\in[x_1,x_2]$? Can I still state some error estimates in this case?

Answer 1

Yes, the error can be estimated without assuming twice differentiability.

If $f$ is Lipschitz continuous with Lipschitz constant $L$, the maximal error for linear interpolation of $f$ in $x_1$ and $x_2$ is $Lh/2$, where $h=|x_2-x_1|$. (The worst case is easily seen to be that of interpolating a linear function with a single kink and slopes $\pm L$, and a little geometry then produces the stated optimal bound.)

Answer 2

While I believe this question would get a more in-depth answer on math.stackexchange.com I'll try to give you a sufficient answer.

Your example with the absolute value may also not be capturing your question entirely, since its first derivative also doesn't exist at the origin.

If you only have a single discontinuity in any of the derivatives (including the first), you can get a rather loose error bound of $M |x_i - x|$ where M is the bound on $f'(x)$ on the interval $[x_i, x]$ and $x_i$ is the endpoint of your interpolating interval chosen so that $[x_i, x]$ does not contain the discontinuity. An analysis showing this is below if you are interested, however it only holds for the single discontinuity case, and is a pretty horrible error bound, considering just using $f(x_0)$ or $f(x_1)$ would give approximately the same provable error bound.

Let's start with a function $f(x)$ from which we know $f(x_0) = y_0$ and $f(x_1) = y_1$. We also know that $f'(x)$ does not exist at a single point, $x_d \in (x_0, x_1)$. We approximates $f(x)$ with the formula $p = y_0 + (y_1 + y_0)/(x_1 + x_0)*(x - x_0)$.

Now we want to estimate $|f(x) - p|$. With a little bit of algebra and the triangle inequality we can show that this value is less than or equal to $|f(x) - y_0| + |-(y_1 + y_0)/(x_1 + x_0)*(x - x_0)|$. The second term here is well known, since we know $x$. All we need to know now is how far $f(x)$ deviates from $f(x_0)$ in the displacement from $x_0$ to $x$.

We also know that $f(x) - f(x_0)= \int_{x_0}^x f'(x)$. If we have that $f'(x)$ is bounded on the interval $[x_0 x]$ by some value $M$, we then know that the maximum value of $\int_{x_0}^x f'(x)$ could be is $M |x - x_0|$. Of course if the discontinuity is in the interval $[x_0, x]$, we then know that it is not in the interval $[x, x_1]$, so you could perform a similar analysis from the $x_1$ point rather than the $x_0$ point.