Natural cubic spline interpolation error estimate
I am looking for an error estimation for natural (one with $s''(a) = s''(b) = 0$ boundary conditions) cubic spline interpolation on an evenly spaced grid. The best result I've found was $O(h^2)$ without any clarification what the actual constant in $O(\cdot)$ is. Intuitively, the error should have the form of $$\max_{x\in[a,b]}|f(x) - s(x)| < Ch^2 \max_{x\in[a,b]}|f''(x)|,$$ maybe with some higher order terms of $O(h^4)$ magnitude.
UPD. As @alex-ravsky suggested we can consider $g(x)$ such that $g''(a) = g''(b) = 0$ and $g(x_i) = f(x_i)$. Thus $$ |f(x) - s(x)| \leqslant |f(x) - g(x)| + |g(x)-s(x)| \leqslant |f(x)-g(x)| + \frac{5}{384}h^4 \max |g^{(4)}(x)| $$ Still, estimating $|f(x)-g(x)|$ is not obvious. $\varepsilon(x) \equiv f(x)-g(x)$ vanishes at every node $x_i$ and has known second derivatives at endpoints $\varepsilon''(a) = f''(a), \varepsilon''(b) = f''(b)$.
One can estimate $\max_{x\in[a,b]} |\varepsilon(x)|$ as $$ \max |\varepsilon(x)| \leq |f''(a)| \max_{x\in[a,b]} |\eta_L(x)| + |f''(b)| \max_{x\in[a,b]} |\eta_R(x)| = \left(|f''(a)| + |f''(b)|\right) \max_{x\in[a,b]} |\eta(x)|, $$ where $\eta(x)$ is a spline satisfying $$ \eta(x_i) = 0,\quad \eta''(a) = 1, \quad \eta''(b) = 0. $$ But it is not obvious how to do the estimation on $\max_{x\in[a,b]} |\eta(x)|$.
Solution 1:
I hope this helps.
We assume $f\in C^2([a,b])$. Since $s''(x)=s''(x_i)\frac{x_{i+1}-x}{h_i}+s''(x_{i+1})\frac{x-x_i}{h_i}$, for $x\in [x_{i},x_{i+1})$, $0\leq i\leq n-1$, it holds $$ \begin{array}{rcl} f''(x)-s''(x)&=&\left[(f''(x)-f''(x_i))+(f''(x_i)-s''(x_i))\right]\tfrac{x_{i+1}-x}{h_i}\\[0.75pc] &&+\left[(f''(x)-f''(x_{i+1}))+(f''(x_{i+1})-s''(x_{i+1})]\right)\tfrac{x-x_i}{h_i}, \end{array} $$ for $x\in [x_{i},x_{i+1})$, $0\leq i\leq n-1$. Hence, $$\parallel f''-s''\parallel_\infty\leq \omega_{h}(f'')+M_{\Delta_n},$$ being $\omega_h(f'')$ the modulus of continuity of $f''$ of size $h=\displaystyle\max_{0\leq i\leq n} x_{i+1}-x_i$ and $$M_{\Delta_n}:=\displaystyle\max_{0\leq i\leq n} |f''(x_i)-s''(x_i)|.$$ Now, let $d:=f-s\in C^2([a,b])$, with $d(x_i)=0$, $0\leq i\leq n$, and by Rolle's Theorem, $d'(\xi_{i})=0$, with $\xi_{i}\in (x_i,x_{i+1})$, $0\leq i\leq n-1$. Let $\widehat{x}, \widetilde{x}\in [a,b]$ such that $\parallel d \parallel_\infty=|d(\widehat{x})|$ and $\parallel d' \parallel_\infty=|d'(\widetilde{x})|$, respectively. There exist indexes $i,j$ such that $|\widehat{x}-x_i|\leq \frac{h}{2}$ and $|\widetilde{x}-\xi_j|\leq h$. Then $$ \parallel d \parallel_\infty=|d(\widehat{x})|=\left| \int_{x_i}^{\widehat{x}} d'(x)dx\right|\leq \tfrac{h}{2} \parallel d' \parallel_\infty, \quad \parallel d'\parallel_\infty =|d'(\widetilde{x})|=\left| \int_{\xi_j}^{\widetilde{x}} d''(x)dx\right|\leq h\parallel d''\parallel_\infty. $$
It remains to study the size of $M_{\Delta_n}$. For the natural and the complete cubic splines (even for the periodic one if $f$ extends periodically to a $C^2$ function on $\mathbb{R}$), it holds $$ \begin{array}{rcl} \widehat{\delta}_i&:=&\tfrac{h_{i-1}}{6(h_{i-1}+h_i)}f''(x_{i-1})+\frac{1}{3}f''(x_i)+\tfrac{h_i}{6(h_{i-1}+h_i)}f''(x_{i+1})-f[x_{i-1},x_i,x_{i+1}] \\[0.75pc] &&\tfrac{h_{i-1}}{6(h_{i-1}+h_i)}f''(x_{i-1})+\frac{1}{3}f''(x_i)+\tfrac{h_i}{6(h_{i-1}+h_i)}f''(x_{i+1})-\tfrac{f''(\widehat{\zeta}_i)}{2},\quad \widehat{\zeta}_i\in[x_{i-1},x_{i+1}], \\[0.75pc] &&\tfrac{h_{i-1}}{6(h_{i-1}+h_i)}(f''(x_{i-1})-f''(\widehat{\zeta}_i))+\frac{1}{3}(f''(x_i)-f''(\widehat{\zeta}_i))+\tfrac{h_i}{6(h_{i-1}+h_i)}(f''(x_{i+1})-f''(\widehat{\zeta}_i)), \end{array} $$ and $|\widehat{\delta}_i|\leq \frac{1}{6}\omega_{2h}(f'')+\frac{1}{3}\omega_{h}(f'')\leq \frac{2}{3}\omega_{h}(f'')$, $0\leq i\leq n$ (with the convention, $h_{-1}:=0$, $x_{-1}:=x_0$, for $i=0$; for $i=n$, $h_n:=0$, $x_{n+1}=x_n$ in case of the complete spline, and $h_n:=h_0$, $x_{n+1}=x_n+h_n$, with $f(x_{n+1}):=f(x_1)$, for the periodic one).
If $AM=b$ denotes the linear system for the spline momenta ($s''(x_i)$) and $F''$ is the corresponding vector of second derivatives of $f$ at the grid points, then $A(F''-M)=AF''-b=\widehat{\delta}$, where $\widehat{\delta}$ is the corresponding vector with coefficients $\widehat{\delta}_i$. Since $\parallel A^{-1}\parallel_\infty \leq \frac{1}{1-\parallel I-A\parallel_\infty}=\frac{1}{1-\frac{5}{6}}=6$, this gives $$ M_{\Delta_n}=\parallel F''-M \parallel_\infty\leq \parallel A^{-1} \parallel_\infty \parallel\widehat{\delta} \parallel_\infty\leq 4\omega_{h}(f''). $$
This gives $\parallel f^{(j)}-s^{(j)} \parallel_\infty=o(h^{2-j})$, $j=0,1,2$ for the three splines above considered. If $f$ does not extend to a $C^2$ periodic function, then the above argument only gives for the periodic spline $\parallel f^{(j)}-s^{(j)} \parallel_\infty=\mathcal{O}(h^{2-j}/h_{\rm min})$, $j=0,1$, with $h_{\rm min}=\displaystyle \min_{0\leq i\leq n} x_{i+1}-x_i$.
Solution 2:
It seems the following.
I think that a key question is: how far from zero can be a function $f$ which has the zero approximation? The answer depends on by which characteristics of $f$ we bound its norm $\|f\|=\max_{x\in [a,b]} f(x)$. For instance, suppose that $a=x_0<x_1<...<x_m=b$, $f\in C^2[a,b]$ (or satisfies some weaker smoothness conditions), $f”(a)= f”(b)=0$ and $f(x_i)=0$ for each $i$. Let $h=\max|x_{i+1} – x_i|$. There can be following conditions imposed on derivatives of the function $f$.
- $\|f’\|= A$. Then $\|f\|\le Ah/2$.
- $\|f’’\|= A$. Then $\|f’\| \le A(b-a)/2$, and so $\|f\|\le Ah(b –a)/4$. But it seems that we can obtain a bound $\|f\|\le Ah^2/4$.
- $\|f’’’\|= A$. Then ...
Solution 3:
Based on suggestion of Alex, I discovered a better better way to estimate this. Define a $C^{\infty}$ polynomial with $$P_0(x_0)=P_0'(x_0)=0, P_0''(x_0)=-f''(x_0), P_0(x_1)=P_0'(x_1)=P_0''(x_1)=P_0'''(x_1)=P_0^{(4)}(x_1)=0$$ and another "identical" $C^{\infty}$ polynomial with $$P_{n-1}(x_{n})=P_{n-1}'(x_{n})=0, P_{n-1}''(x_{n})=-f''(x_{n}), P_{n-1}(x_{n-1})=P_{n-1}'(x_{n-1})=P_{n-1}''(x_{n-1})=P_{n-1}'''(x_{n-1})=P_{n-1}^{(4)}(x_{n-1})=0.$$ Note that $$(f+P_0)''(x_0)=0=S''(x_0)$$ and $$(f+P_{n-1})''(x_{n})=0=S''(x_{n}).$$
Now we can efine a function $g \in C^4$ such that $$g(x)=P_0(x),$$ for $ x_0 \leq x \leq x_1 $, $$g(x)=0$$ for $x_1 \leq x \leq x_{n-1} $ and $$g(x)=P_{n-1}(x),$$ for $x_{n-1} \leq x \leq x_{n}$. This implies that $S$ is the interpolating cubic spline for $f+g,$ hence $$|(f-S)(x)|=|(f+g-g-S)(x)|\leq |(f+g-S)(x)|+|g(x)| \leq \dfrac{5 h^4 }{384} \max_{x \in [a,b]} |(f^{(4)}+g^{(4)})(x)| + |g(x)|.$$
At this moment note that $P_0$ has a zero of degree 2 at $x_0$ and other zero of degree 4 at $x_1$ which implies that $|P_0(x)| \leq K h^4$ for all $x\in [x_0,x_1]$, for some $K>0.$ Applying the same argument for $P_{n-1}$, is possible to obtain that $|P_{n-1}(x)| \leq K^{'} h^4,$ for some $K'$ and all $x\in [x_{n-1},x_{n}].$ This two observations implies that $|g(x)|\leq (K+K') h^4.$ Furthermore, since $g$ is $C^{4}$, $|g^{(4)}_0(x)| \leq L $ for all $x\in [x_0,x_n]$, for some $L>0.$ The last three observations implies that there exist some $M>0$ such that $$|f(x)-S(x)| \leq M h^{4}.$$ Of course, explicitly calculations of $M$ can be done with this construction.