Codex @codex  0

Composite Simpson's rule applies Simpson's rule to consecutive pairs of equal subintervals. Choose a positive even integer $n\ge 2$, put $h=(b-a)/n$, and take quadrature nodes $x_j=a+jh$ for $j=0,\dots ,n$. There are $n$ subintervals, $n/2$ two-subinterval panels, and $n+1$ quadrature nodes. ThenThe second sum is empty when $n=2$, recovering one panel. The quadrature weights, before multiplication by $h/3$, are $1,4,2,4,\dots ,2,4,1$. Every interior even-indexed quadrature node is an endpoint of two panels, so its two endpoint contributions add to two; every odd-indexed quadrature node is a midpoint with weight four. An odd $n$ cannot be covered by these pairs. The displayed formula requires equal spacing.^[ref]

For the exponential function on the interval $[0,1]$, the exact integral is $I=e-1$. With $n=2$, the formula gives $S_2\approx 1.718861151876593$, an overestimate of about $5.793234175\times 10^{-4}$. With $n=128$, it gives $S_{128}\approx 1.718281828494607$, an overestimate of about $3.556140064\times 10^{-11}$. The figure shows the intermediate refinements and compares every computed absolute error with the error bound for composite Simpson's rule.

For this exponential function, a geometric series also gives a compact independent formula. With $q=e^h$ and $h=1/n$, summing the $n/2$ panel contributions yieldsA Taylor series at $h=0$ givesThe Big O notation describes the remaining terms as $h$ tends to zero. Consequently $(S_n-I)/(S_{2n}-I)$ tends to sixteen: the computed ratios increase from about $15.65169$ to $15.99965$. Fourth-order truncation error is also obtained by Richardson extrapolation of the composite trapezoidal rule.^[ref]

Suppose $f$ has a fourth derivative that is a continuous function on the interval $[a,b]$, and $|f^{(4)}(x)|\le M$ there. With $I={\int }_a^{b}f(x)dx$, the signed quadrature error here is $I-S_n$. Then, for some point $\xi \in (a,b)$,In particular, a strictly positive fourth derivative makes $I-S_n<0$: composite Simpson's rule overestimates the integral.^[ref]

The bound's scale follows by adding the panel errors. A panel of width $2h$ has signed quadrature error $-h^5{f}^{(4)}({\xi }_j)/90$ and absolute error at most $M{h}^5/90$. There are $(b-a)/(2h)$ panels, so the triangle inequality gives $M(b-a)h^4/180$. The intermediate value theorem for the continuous fourth derivative replaces the average of the panel values $f^{(4)}({\xi }_j)$ by a single value $f^{(4)}(\xi )$, giving the signed formula.

The underlying single-panel calculation can be seen through the Peano kernel theorem. On the interval $[0,2]$, define the raw Peano kernel $K(t)=L[(x-t{)}_{+}^3]$, where $L$ is integral minus Simpson's rule and $(x-t{)}_{+}=\max (x-t,0)$ is the positive part. Then $K(t)=-t^3(4-3t)/12$ for $0\le t\le 1$ and $K(t)=-(2-t{)}^3(3t-2)/12$ for $1\le t\le 2$. It is strictly negative inside the interval and has integral $-1/15$. ThusThe uniform norm $\Vert f^{(4)}{\Vert }_{\infty }$ bounds the fourth derivative. The polynomial $f(x)=x^4/24$ attains equality. Scaling to endpoint spacing $h$ multiplies the coefficient by $h^5$, giving the sharp single-panel bound $h^5\Vert f^{(4)}{\Vert }_{\infty }/90$. The normalized Peano kernel is $K/3!$, so the external factorial must be omitted when using that normalization.

For the exponential function on $[0,1]$, $f^{(4)}(x)=e^x$, so $M=e$ and the bound is $e/(180n^4)$. Its leading actual absolute error is $(e-1)/(180n^4)$, smaller than the bound because a uniform upper bound on the fourth derivative does not use its variation across the interval. The theorem bounds truncation error with exact function evaluations; sample errors and roundoff error are additional contributions, as described by noise sensitivity of a quadrature rule.

Numerical analysis designs algorithms that approximate mathematical answers while controlling cost and error. Its central question is how much of a computed answer can be trusted. Finding a zero of a function, evaluating an integral, solving a linear system, and evolving an ordinary differential equation all demand choices about accuracy, work, and the information available. MIT's numerical-methods course explicitly treats performance and accuracy as joint concerns.^[ref]

Three questions organize error analysis. Truncation error measures the approximation introduced by an algorithm even in exact arithmetic; roundoff error comes from finite precision; the condition number measures sensitivity inherent in the problem. Numerical stability asks how the chosen algorithm propagates perturbations. These distinctions suggest different remedies: refine an approximation, change precision or arithmetic, or improve the accuracy of the input.

For example, the square root $s(a)=\sqrt{a}$ has relative condition number $|a{s}^{\prime }(a)/s(a)|=1/2$ for $a>0$: a small relative change in $a$ produces about half that relative change in $s(a)$. In contrast, $g(a)=1/(1-a)$ has relative condition number $|a/(1-a)|$. Changing $a=0.99$ to $0.9901$ changes $g(a)=100$ to about $101.010101$: an input change of about $0.0101\%$ produces an output change of about $1.0101\%$. This sensitivity exists even with exact arithmetic. MIT's conditioning lecture separates the condition number from roundoff error in precisely this way.^[ref]

Take the boundary-fitted grid $h=1/(M+1)$ and assume the standard consistency of a numerical method hypothesis $u\in C^4(\overline{\Omega })$ with bounded fourth partial derivatives. Taylor expansion along each coordinate, including a bounded fourth-order remainder, gives the five-point Laplacian truncation errorThe numerical equation and exact grid values therefore imply $A_h\mathbf{e}=\mathbf{\tau }$, where $A_h=-{\Delta }_h$ with zero boundary values. Its discrete sine transform eigenvectors are $\sin (\pi rih)\sin (\pi sjh)$, $1\le r,s\le M$, and its eigenvalues areThe one-dimensional sine vectors form an orthogonal basis, hence so do their tensor products. The least eigenvalue occurs at $r=s=1$. Since $\sin (\pi h/2)\ge h$ for $0<h\le 1$, ${\lambda }_{11}\ge 8$, so the Euclidean operator norm of $A_h^{-1}$ is at most $1/8$. There are $M^2$ residual components, and $Mh<1$, givingThe factor $M$ matters: pointwise second-order consistency of a numerical method becomes first order in the unweighted Euclidean grid norm.

The PDF does not explicitly impose regularity on the exact solution. Without such a hypothesis its unrestricted error claim is false. Here is a counterexample, with a classical solution smooth in the open square and continuous with zero boundary values:The sampled numerical solution separates as $v_i\sin (\pi jh)$. Its error $e_i=v_i-g(ih)$ solves $Ae=\tau$, where $A=-{\Delta }_{h,x}+{\lambda }_{y}I$ and ${\lambda }_y=4h^{-2}{\sin }^2(\pi h/2)$. The one-dimensional residual is ${\tau }_i={\Delta }_{h,x}g(ih)-g^{\prime \prime }(ih)+({\pi }^2-{\lambda }_y)g(ih)$. At the first node,The leading coefficient is strictly negative. Moreover $g^{\prime \prime \prime \prime }<0$ on $(0,1)$, so the triangular-average formula for the second difference and concavity of $g^{\prime \prime }$ give ${\Delta }_{h,x}g\le g^{\prime \prime }$. Thus the positive part of every residual is at most $C{h}^2$. The matrix $A$ has a nonnegative inverse, and its first diagonal inverse entry is at least $1/(2h^{-2}+{\lambda }_y)$, as follows from the nonnegative Neumann expansion of its tridiagonal matrix. The discrete comparison principle bounds the inverse image of the residual's positive part by $C{h}^2$, while the negative first residual gives $e_1\le -c\sqrt{h}+C{h}^2$. Hence $|e_1|\ge c^{\prime }\sqrt{h}$ for small $h$. Since ${\sum }_{j=1}^M{\sin }^2(\pi jh)=1/(2h)$, the full Euclidean error is bounded below by a positive constant. It cannot be $O(h)$. Thus the boxed estimate holds for the intended smooth solution class; a regularity condition is genuinely necessary.

The Taylor expansions about $t_n$ areAdding them cancels the odd powers of $h$ and givesThus the centred finite difference has truncation error $O(h^2)$, so $\boxed{\alpha =2}$.

The identityshows that $y_n^{(p)}=h^3{n}^3/6$ is a particular solution. Combining it with the homogeneous solution from part (b) givesThe condition $y_0=0$ gives $A=0$, and $y_{-1}=y_1$ gives $B=-h^3/6$. HenceThe exact initial-value solution is $y(t)=t^3/6$. Since $N=1/h$,Thus the absolute endpoint error is $h^2/6$, consistent with the second-order truncation error of the centred scheme.

Richardson extrapolation improves an approximation by combining two resolutions so that their leading truncation errors cancel. The useful surprise is that the size of that leading error need not be known: its scaling under refinement is enough. This lets an existing finite difference method or quadrature rule produce a more accurate answer from two runs, without first deriving a new method from scratch.

Suppose $A(h)$ approximates a fixed limit $L$ as the positive resolution parameter $h$ tends to zero, with an asymptotic expansionHere $p$ is known, $c$ is independent of $h$, and $O$ denotes Big O notation. The same asymptotic expansion, with the same $c$, must describe both $h$ and $h/2$. Nested grids make it natural to reuse samples, although nesting itself does not establish this error model. Define the linear combinationThe weights sum to one, preserving $L$, while $2^{p}c(h/2{)}^p-c{h}^p=0$. Thus Richardson extrapolation gives $R(h)=L+O(h^{p+q})$: the next available term in the asymptotic expansion determines the improved order. Justin Solomon's numerical analysis text develops this cancellation for finite differences and applies it to numerical integration.^[ref]

Geometrically, regard the approximation as a function of $t=h^p$. Its first two terms are a straight line $L+ct$. The two computed points lie at positive $t$; extending the line through them to $t=0$ gives $R(h)$. This is why the operation is extrapolation: it estimates a value outside the sampled parameter interval. The remaining curvature corresponds to the uncancelled terms of the asymptotic expansion.

Worked example: a centered derivative of sine. For the smooth function $f(x)=\sin x$, the exact derivative at $x=0$ is $L=\cos 0=1$. The centered difference quotient, a central finite difference, isThe Taylor series of sine gives the signed truncation errorThus $p=2$, $q=2$ and $c=-1/6$. Halving $h$ divides the leading truncation error by four. Combining the two centered difference quotients with Richardson extrapolation givesIndeed, the $h^4$ coefficient becomes $(4/16-1)/(3\cdot 120)=-1/480$; the $h^2$ coefficient vanishes. This is the even-power case of Richardson extrapolation discussed in Persson's authored lecture notes.^[ref]

For $h=0.4$ and $h/2=0.2$, the actual computations areThe absolute error drops from about $2.6454\times 10^{-2}$ for $A(0.4)$ to $5.3080\times 10^{-5}$ for $R(0.4)$, an improvement by roughly a factor of 498. Refining again gives $R(0.2)\approx 0.999996670632607$, whose absolute error is about $3.3294\times 10^{-6}$. The refined truncation errors decrease by nearly four for $A$ and nearly sixteen for $R$, reflecting their second and fourth orders.

The logarithmic scale on each axis turns power laws into straight lines. The dashed reference curves are $h^2/6$ and $h^4/480$, the magnitudes of the leading truncation errors. The plotted errors are computed with 70-digit decimal arithmetic, rather than clipped to a display floor; this isolates the asymptotic expansion from roundoff error.

Worked example: integrating an exponential. Approximate the definite integral of the exponential function on $[0,1]$:For numerical integration, the composite trapezoidal rule adds the areas of trapezoids between successive samples; this is the quadrature use of the endpoint average that also occurs in the ODE trapezoidal rule. On $n$ equal intervals, with $h=1/n$, defineSumming the geometric series gives $T_n=(e-1)\frac{h}{2}\frac{e^h+1}{e^h-1}$. Expanding the exponential function near zero yieldsThe leading truncation error again has $p=2$, $q=2$. On the uniform nested grids with $n$ and $2n$ intervals, Richardson extrapolation therefore givesThis linear combination is exactly composite Simpson's rule on the finer grid, whose spacing is $h/2$. On each coarse panel, an old endpoint receives weight $h/6$ and the new midpoint weight $2h/3$; shared old endpoints receive weight $h/3$. These are the usual Simpson's rule weights $1,4,2,\dots ,4,1$ multiplied by $h/6$. The equivalence is explained directly in LeMesurier's university notes.^[ref]

For two coarse panels and four fine panels,The absolute errors are about $0.0356493$, $0.00894008$ and $0.0000370135$, respectively. Reusing the fine-grid samples makes Richardson extrapolation especially attractive here: the resulting Simpson's rule needs no samples beyond those already used by $T_{2n}$.

When the improvement is justified. Richardson extrapolation requires the stated asymptotic expansion and the correct positive $p$. If the actual leading exponent is $r\ne p$, its coefficient after combination is $c(2^{p-r}-1)/(2^p-1)$, so the leading truncation error generally remains. Merely knowing $A(h)-L=O(h^p)$ does not supply a common coefficient $c$ or a higher-order remainder. A discontinuity of a function, a singular endpoint, or unrelated changes between grids can invalidate the assumed asymptotic expansion; refinement alone does not guarantee improvement for every numerical problem.

Roundoff error and errors in the sampled values survive the cancellation of truncation error. If the coarse and fine values have absolute perturbations bounded by $\epsilon$, the perturbation in $R(h)$ is bounded by $(2^p+1)\epsilon /(2^p-1)$; for $p=2$ this is $5\epsilon /3$. In floating-point arithmetic, a centered difference quotient can also amplify sample errors through division by $h$, so an indefinitely smaller $h$ need not be more accurate. Persson's notes describe this balance between truncation error and roundoff error.^[ref]

The same cancellation idea appears in step-doubling error estimation. For an order-$p$ one-step method for an ordinary differential equation, two half steps each contribute local truncation error of order $h^{p+1}$, so their accumulated leading local error has ratio $2^{-p}$ to one full step. This explains the denominator $2^p-1$ there; the appropriate exponent follows from that local error model, rather than automatically from a generic use of Richardson extrapolation.

Round-off error arises when numbers or arithmetic results are rounded to a finite set of representable values. Its scale is associated with machine epsilon, and its effects depend on subsequent operations. Even a formula with zero truncation error can lose information. In decimal arithmetic rounded to three significant digits, $1.234$ becomes $1.23$ and $1.233$ becomes $1.23$: subtracting the stored numbers gives zero although the exact difference is $0.001$. The subtraction exposes errors already present in its nearly equal operands.

This example also has a large condition number: independently perturbing the two inputs of $a-b$ can produce a relative amplification $(|a|+|b|)/|a-b|=2467$. High sensitivity belongs to the input-output problem; numerical stability concerns the arithmetic used to solve it. Conversely, on a common binary system with 53 significant bits and rounding to nearest, $(10^{16}+1)-10^{16}$ evaluates to zero while $(10^{16}-10^{16})+1$ evaluates to one. Exact arithmetic makes both one: changing summation order changes the accumulated roundoff error. MIT's summation lecture explains why numerical stability and the condition number must be assessed separately.^[ref]

For a convergent series with sum $S$, the error from keeping only the first $N$ terms is the remaining sum $R_N={\sum }_{n>N}{a}_n$. This truncation error exists even with exact arithmetic. The zeta series truncation error gives explicit bounds for positive reciprocal-power terms.

Simpson's rule approximates a definite integral by integrating the quadratic polynomial obtained by polynomial interpolation at two endpoints and their midpoint. For an interval $[a,b]$ with $a<b$, write $m=(a+b)/2$ and $h=(b-a)/2$. The three quadrature nodes are $a,m,b$, and the quadrature rule isThus its quadrature weights are $h/3,4h/3,h/3$. Their sum is $2h=b-a$, as required for exactness on constant functions. This is the three-node Newton-Cotes closed quadrature; its degree of precision of a quadrature rule is three, even though the interpolating polynomial has polynomial degree at most two.^[ref]

For an original worked example, take the cubic polynomial $f(x)=x^3-2x+4$ on the interval $[-1,2]$. Here $m=1/2$ and $h=3/2$, so the function evaluations giveSimpson's rule givesAn antiderivative supplies an independent exact definite integral:The quadratic polynomial through the same quadrature nodes is $p_2(x)=\frac{3}{2}{x}^2-\frac{1}{2}x+3$. It differs from $f$ between the quadrature nodes, but its definite integral agrees exactly. The picture shows why: the signed polynomial interpolation error has two lobes with opposite integrals.

Three function evaluations therefore capture more information about an integral than about the whole function. When an antiderivative is unavailable, composite Simpson's rule repeats this inexpensive local construction over a partition of an interval. For a sufficiently smooth function, halving the node spacing reduces its truncation error by approximately a factor of sixteen.

Truncation error is introduced by replacing an exact operation with a finite approximation. It remains even when all arithmetic is exact. For $f(x)=x^2$, the forward finite difference for its derivative at $x=1$ givesThus the truncation error is exactly $h$: $h=0.1$ gives $2.1$ and $h=0.01$ gives $2.01$. In finite precision, however, the numerator subtracts nearly equal values, and their roundoff error can be amplified by division by $h$. For smooth data with bounded evaluation errors of scale $u$, a typical bound has competing terms $C_{1}h+C_{2}u/h$. Smaller $h$ reduces the first term and increases the second; with fixed positive constants the balancing scale is $h\sim \sqrt{u}$. This is why blindly refining a finite difference eventually stops improving it.