Homework Help: Construct extrapolation table with optimal convergence

1. Mar 23, 2013

drawar

Construct extrapolation table with optimal rates of convergence

1. The problem statement, all variables and given/known data

Let $S$ be a cubic spline interpolant that approximates a function $f$ on the given nodes $x_{0},x_{1},...,x_{n}$ with the boundary conditions: $S''(x_{0})=0$ and $S'(x_{n})=f'(x_{n})$. Use $S$ to estimate $f(0.1234567)$ where $f(x)=xe^{x}$ and the nodes are $n+1$ uniformly distributed points on $[-1;1]$ for $n=20, 40, 80, 160, 320$. Construct an extrapolation table with optimal rates of convergence using these estimates.

2. Relevant equations

3. The attempt at a solution

I've already computed the approximation to $f(0.1234567)$ using various choices of nodes, the results are listed below:
0.139678933961527 0.139678959983576 0.139679035306608 0.139679035488050 0.139679035532356

I just don't know how to do the last part, that is, find the extrapolation table with optimal convergence. I'm supposed to use Richardson's extrapolation to generate such a table but what hinders me is the truncation error involved in the cubic spline approximation. From what I've learned, extrapolation is applied only when the truncation error has a predictable form, like $M = {N_1}(h) + {K_1}h + {K_2}{h^2} + {K_3}{h^3} + ...$.

edit:
Well after some searches (http://www.alglib.net/interpolation/spline3.php#header4) I've found out that the errors for clamped and natural cubic splines are $O({h^4})$ and $O({h^2})$ respectively, but have no idea how they are derived. My cubic spline is something kind of in-between, like half-clamped and half-natural.

Last edited: Mar 23, 2013
2. Mar 23, 2013

Staff: Mentor

Did you plot (interpolation value)-(real value) as function of your node distances? A logarithmic scale can be useful.

3. Mar 23, 2013

drawar

Yes. Here it is:

E is the absolute error and h is the distance between nodes (h=2/n for n=20,40,80,160,320)

The slope (and maybe the rate of convergence?) is 1.9993.

4. Mar 23, 2013

Staff: Mentor

Exactly (well, the exact value is 2 and not 1.9993).

5. Mar 23, 2013

drawar

Thanks. So is it safe to say that the error for my cubic spline is $O({h^2})$ because the rate of convergence is 2? If it is, then how the error form would look like, is it $M = {N_1}(h) + {K_1}{h^2} + {K_2}{h^3} + {K_3}{h^4} + ...$ or something else?

6. Mar 24, 2013

Staff: Mentor

I don't know what that formula expresses, but if N1 has no linear term, this looks reasonable.

7. Mar 24, 2013

drawar

8. Mar 24, 2013

Staff: Mentor

I cannot access the link, and I don't know about Richardson's extrapolation.

9. Mar 24, 2013

drawar

Well, then hopefully you can access this: https://docs.google.com/viewer?a=v&...ymKG3t&sig=AHIEtbR1oV9rtANIhNQFrQOQFusrck0_rA . It's pretty much the same as the previous one, both serve as introductions to Richardson's extrapolation.

What I need is the behavior of truncation error, something like Eq.(24.1) in the article, without which I cannot apply the formulas to construct an extrapolation table.