2
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, even the first derivative doesn't exist, but since the local error depends on the second derivative that's the one I am concerned about. So the second term in the bound for the error is always $O(x_1-x_0)$, but what you tell me for the first part $|f(x)-y_0|$ is choose the side which doesn't have discontinuity and establish boundedness of the derivative there therefore making the error again $O(x_1-x_0)$, thus the discontinuity of the first derivative lowers the order of interpolation from 2 to 1? $\endgroup$ – Kamil Jul 9 '12 at 13:11
  • $\begingroup$ Actually, if the derivative is bounded and there is no discontinuity at all I still get first order without choice of which point to take for the analysis? $\endgroup$ – Kamil Jul 9 '12 at 13:20
  • $\begingroup$ I am not saying that the method is first order, I am saying that even in a much worse case, you still get at least first order. $\endgroup$ – Godric Seer Jul 9 '12 at 18:31

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.