I am looking for an approximation method for a typical 1-dimensional approximation problem, that has stability constant 1.

The setting

We have

  • an interval $[a,b]$
  • an unknown function $f$ on $[a,b]$ that is sufficiently smooth
  • a partitioning of the interval $a=x_0\le x_1 \le \dots \le x_n=b$.
  • known values of $f$ at knots: $y_i=f(x_i)\ (i=0\dots n)$
  • Use the notation $\overline{x}=(x_0,x_1,\dots,x_n)$ and $\overline{y}=(y_0,y_1,\dots,y_n)$

We want

  • An approximating function $F_{\overline{x},\overline{y}}(x)$ on interval $[a,b]$
  • $F_{\overline{x},\overline{y}}(x)$ as a function of $x$ can be given in closed form, this closed form is as simple as possible (eg a spline) and can be calculated efficiently from inputs $\overline{x},\overline{y}$
  • The approximation method has stability constant 1: $$\|\overline{y}-\overline{y}^\star\|_\infty\le\epsilon \ \Longrightarrow \|F_{\overline{x},\overline{y}}-F_{\overline{x},\overline{y}^\star}\|_\infty\le\epsilon$$ where the latter norm is taken on interval $[a,b]$
  • $F_{\overline{x},\overline{y}}(x)$ approximates $f(x)$ to as high order of precision as possible

What I know

  • Linear interpolation does this to second-order precision, so what I am looking for is a method that has more than second order precision.
  • Natural cubic spline approximates to fourth-order precision but the stability condition is absolutely not satisfied even for uniform partitions.


  • The reason I need the stability condition is that I have an algorithm which repeatedly applies this approximation so the algorithm will become unstable if the approximation technique may increase errors.
  • I don't care about smoothness of the result although I guess it is necessary for the accuracy.
  • I don't need the method to be an interpolation, it can be an approximation even at knots. Of course, if it is an interpolation technique, even better.
  • $\begingroup$ Perhaps this helps? korf.co.uk/spline.pdf $\endgroup$ – strider Aug 31 '17 at 13:22
  • $\begingroup$ @strider Thanks! I have seen that article but I am not sure whether their method fulfills my criteria. They don't prove either a stability or an accuracy result. The method guarantees that if all samples are at most epsilon, then the whole curve is at most epsilon. But since the method is nonlinear, this does not guarantee stability in general. $\endgroup$ – balazs.g Sep 1 '17 at 12:16
  • $\begingroup$ @strider: By running some tests I found that the constrained spline described in the above paper is somewhat more accurate than linear interpolation, but it is not stable. $\endgroup$ – balazs.g Sep 15 '17 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.