Romberg integration from tabulated data: 04-BS-5, May 2015, Q5

Question 5: Romberg integration from tabulated data (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Nine tabulated points at $h=1$ spacing over $[0,8]$ (table above).

Find. $\int_0^8 f(x)\,dx$ via the Romberg triangular array $R(k,j)$.

Approach. Build $R(1,1)\ldots R(4,1)$ as composite trapezoid estimates at $h=8,4,2,1$, then apply Richardson extrapolation $R(k,j)=R(k,j-1)+\dfrac{R(k,j-1)-R(k-1,j-1)}{4^{j-1}-1}$.

Column 1 — composite trapezoid at each $h$. $H_1=8$: $R(1,1)=\tfrac{H_1}2[f(0)+f(8)]=4(5+83)=352$. Halving each time ($H_2=4,H_3=2,H_4=1$) and folding in the newly sampled points: $$R(2,1)=\tfrac12\big[R(1,1)+H_1f(4)\big]=\tfrac12[352+8(25)]=276$$ $$R(3,1)=\tfrac12\big[R(2,1)+H_2\big(f(2)+f(6)\big)\big]=\tfrac12[276+4(8+49)]=252$$ $$R(4,1)=\tfrac12\big[R(3,1)+H_3\big(f(1)+f(3)+f(5)+f(7)\big)\big]=\tfrac12[252+2(6+15+36+65)]=248$$
Column 2 — first Richardson extrapolation ($j=2$, divide by $4^1-1=3$). $$R(2,2)=276+\dfrac{276-352}{3}=250.667,\quad R(3,2)=252+\dfrac{252-276}{3}=244,\quad R(4,2)=248+\dfrac{248-252}{3}=246.667$$
Column 3 ($j=3$, divide by $4^2-1=15$). $$R(3,3)=244+\dfrac{244-250.667}{15}=243.556,\quad R(4,3)=246.667+\dfrac{246.667-244}{15}=246.844$$
Column 4 ($j=4$, divide by $4^3-1=63$) — final estimate. $$\boxed{R(4,4)=246.844+\dfrac{246.844-243.556}{63}=246.897}$$

Final results — Question 5 (Romberg array)
	$j=1$	$j=2$	$j=3$	$j=4$
$k=1$	352.000
$k=2$	276.000	250.667
$k=3$	252.000	244.000	243.556
$k=4$	248.000	246.667	246.844	246.897

Topic: Romberg integration (Richardson extrapolation of the composite trapezoid rule).

Key relations: $R(1,1)=\tfrac{H_1}2[f(a)+f(b)]$; $R(k,1)$ halves the step each row; $R(k,j)=R(k,j-1)+\dfrac{R(k,j-1)-R(k-1,j-1)}{4^{j-1}-1}$ removes the leading $O(h^{2j-2})$ error term at each column.

Why this works: the trapezoid rule's error is an even power series in $h$ (Euler–Maclaurin); Richardson extrapolation combines two trapezoid estimates at $h$ and $h/2$ to cancel the leading error term, and repeating the process down the diagonal cancels progressively higher-order terms, converging rapidly even from a coarse table.

Common pitfall: re-using an old function value at the wrong new sample point when halving $h$ (must add exactly the newly-introduced midpoints, not resample everything); dividing by $4^{j}-1$ instead of $4^{j-1}-1$ in the extrapolation formula.

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., §19.5 (Numerical Integration — Romberg).

Question 5 of 7: Romberg integration from tabulated data

Question 5: Romberg integration from tabulated data (20 marks)