Construct extrapolation table with optimal convergence

[drawar]

Construct extrapolation table with optimal rates of convergence

Homework Statement

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.

Homework Equations

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.

 

[mfb]

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

 

[drawar]

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

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.

 

[mfb]

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

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

 

[drawar]

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

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?

 

[mfb]

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

 

[drawar]

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

What I'm trying to do is to derive a form for the truncation error so that I can apply the Richardson's extrapolation, like what's written in my textbook: http://books.google.com.sg/books?id=zXnSxY9G2JgC&lpg=PP1&pg=PA185#v=onepage&q&f=false

Is there any way I can do that?

 

[mfb]

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

 

[drawar]

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

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.