Romberg Integration

It can be shown that the Composite Trapezoidal Rule has an error term of the form

.

This assumes that the function has continuous derivatives up to order . is used to label a sequence of stepsizes such that .

This result means that Richardson Extrapolation can be applied on the estimates obtained by using the Composite Trapezoidal Rule and doubling the number of intervals.

Take the last example:

> with(student):f:=x->sin(2.*x)*exp(-x);exact:=int(f(x),x=1..3);

Applying Composite Trapezoidal Rule with 1,2,4 and 8 intervals, we obtain:

> for i from 1 to 4 do tr.i:=evalf(trapezoid(f(x),x=1..3,2^i)): err.i:=abs(exact-tr.i): print(tr.i, err.i); od:

Applying Richardson Extrapolation we get

> for i from 1 to 3 do R[1,i]:=(4*tr.(i+1)-tr.i)/3.: err1.i:=abs(exact-R[1,i]): print(R[1,i], err1.i); od:

Another application of Richardson Extrapolation yields:

> for i from 1 to 2 do R[2,i]:=(16*R[1,i+1]-R[1,i])/15.: err2.i:=abs(exact-R[2,i]): print(R[2,i], err2.i); od:

And finally our best possible estimate:

> R[3,1]:=(64*R[2,2]-R[2,1])/63.: err31:=abs(exact-R[3,1]): print(R[3,1], err31);

>

The combination of Composite Trapezoidal Rule and Richardson Extrapolation is known as Romberg Integration .

>