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]

Polynomial interpolation makes Simpson's rule exact for every polynomial of polynomial degree at most two. To understand the extra polynomial degree, centre the coordinate at the midpoint: $y=x-m$, with endpoints $-h,h$. For any cubic polynomial $p$, let $p_2$ be its interpolating quadratic polynomial. The polynomial $p-p_2$ vanishes at all three quadrature nodes, sowhere $A$ is the coefficient of $x^3$ in $p$. As a function of $y$, this is an odd function, whose integral over the symmetric interval $[-h,h]$ is zero. Hence integrating $p_2$ also integrates $p$ exactly. This is the symmetry mechanism in the nodal-polynomial criterion for quadrature exactness.

In the worked example, the polynomial difference factors asIts definite integrals on $[-1,1/2]$ and $[1/2,2]$ are respectively $81/64$ and $-81/64$. Their cancellation concerns signed integrals, rather than pointwise accuracy of polynomial interpolation.

The degree of precision of a quadrature rule stops at three: on the same interval, the monomial $x^4$ gives $S(x^4)=69/8$, whereas ${\int }_{-1}^2{x}^{4}dx=33/5$. Their difference, exact integral minus approximation, is $-81/40$.

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.

A Newton-Cotes quadrature is an interpolatory quadrature rule whose quadrature nodes are equally spaced. Integrating the Lagrange interpolation polynomial gives quadrature weights $W_j={\int }_a^b{\ell }_j(x)dx$. A Newton-Cotes closed quadrature includes both endpoints; an open rule uses interior quadrature nodes. Simpson's rule is the closed rule with three quadrature nodes. Its quadrature weights are $(b-a)(1,4,1)/6$.

Numerical integration approximates a definite integral using finitely many sampled function values. For an integrand $f$ on a finite interval $[a,b]$, $a<b$, a quadrature rule has the formThe quadrature nodes $x_j$ tell us where to evaluate $f$; the quadrature weights $w_j$ turn those values into an approximation to the accumulated signed area. The exact definite integral depends on the integrand throughout the interval, whereas the quadrature rule sees only these samples. Integrating a chosen interpolant exactly still generally approximates the original integrand's integral.^[ref]

The fundamental theorem of calculus evaluates $I(f)$ as $F(b)-F(a)$ when an antiderivative $F$ is available. Numerical integration is useful when no convenient antiderivative is known, or each evaluation of the integrand requires an expensive computation. The task then becomes choosing informative quadrature nodes and controlling the quadrature error with as few evaluations as possible. Fixed data also permit a quadrature rule, but refinement cannot supply new information between observations.^[ref]

For an exact comparison, take the polynomial $f(x)=x^2$ on $[0,1]$. Its antiderivative $x^3/3$ gives $I(f)=1/3$. On a partition of an interval into $n\ge 1$ equal panels, the composite midpoint quadrature rule uses $n$ midpoint samples, each with quadrature weight $1/n$; the composite trapezoidal rule uses $n+1$ endpoint samples, with outer quadrature weights $1/(2n)$ and interior quadrature weights $1/n$. The existing derivations under these two quadrature rules giveIn particular, $M_1=1/4$ and $T_1=1/2$ already bracket $1/3$; two panels give $M_2=5/16$ and $T_2=3/8$. The convex function $x^2$ explains the opposite signs. A midpoint rectangle can cross the curve within its panel, so its total signed area, rather than pointwise ordering, determines the underestimate.

Define the signed approximation error as $E_n=Q_n(f)-I(f)$. In this example the absolute errors are $1/(12n^2)$ and $1/(6n^2)$: doubling $n$ reduces each by exactly four. A plot with both axes on a logarithmic scale therefore has slope $-2$, expressing order two with respect to panel refinement. This is an exact calculation for this polynomial, including $n=1$, rather than an observed rate extrapolated from a few computed answers.

For a general integrand, the composite midpoint quadrature rule and composite trapezoidal rule give second-order quadrature error bounds when $f$ has two continuous derivatives on $[a,b]$ and a known bound on $|f^{\prime \prime }|$. These hypotheses describe behavior between samples. A formal error formula containing an unknown derivative is not a numerical accuracy certificate or a justified sample count. Finite samples do not certify quadrature accuracy makes the missing information explicit. Errors in the evaluations and roundoff error must also be considered; noise sensitivity of a quadrature rule treats the former.

More elaborate choices exploit other information: Gaussian quadrature obtains high polynomial exactness from carefully chosen quadrature nodes, and Simpson's rule uses a quadratic interpolant. Adaptive numerical integration compares approximations and concentrates samples where they disagree, often saving evaluations. Such a difference is an error estimate, not a certified bound without further assumptions: both approximations can miss the same feature.^[ref]

Assume $L$ is linear, annihilates all polynomials of degree at most $k$, is defined on the truncated-power kernels and permits interchange with the remainder integral. For $k\ge 1$, a convenient sufficient condition is that $L$ be a bounded linear functional on $C[a,b]$; more general approximation functionals need the corresponding continuity/interchange property on their domain. Taylor's integral remainder givesApplying $L$, the polynomial terms vanish, and the Peano kernel theorem givesHere $t_{+}=\max (t,0)$. This is the printed raw-kernel convention; the normalized Peano kernel includes $1/k!$ inside its definition instead, and then has no factorial outside the integral. The interchange is justified by boundedness applied to the limit of Riemann sums of the continuous kernel-valued integrand. For a kernel with $k=0$, its discontinuity requires a function space/interchange assumption accommodating the step functions as well.

For the specified Simpson's rule error, direct evaluation on $1,x,x^2,x^3$ gives zero, so $k=3$. For $0\le \theta \le 2$,Simplifying separately on the two halves givesBoth pieces are strictly negative in the open interval; they agree at the midpoint. Their integral is $-1/15$, as direct polynomial integration shows. ThusThis is optimal, not merely an upper bound. For $f(x)=x^4/24$, the fourth derivative is identically one and $L(f)=-1/90$, so the minimum constant is $\rho =1/90$.

A Newton-Cotes quadrature integrates a Lagrange interpolation polynomial at equally spaced quadrature nodes. For the Newton-Cotes closed quadrature, the endpoints are included: write $x_j=a+jh$, $h=(b-a)/n$, and useThese quadrature weights depend on the quadrature nodes, not on the sampled function. Open Newton-Cotes quadrature uses equally spaced interior quadrature nodes instead.

For Simpson's rule, use $n=2$ and set $x=a+ht$, so $0\le t\le 2$. The Lagrange cardinal polynomials becomeIntegrating these quadratic polynomials gives $1/3$, $4/3$, $1/3$, respectively. The change of variable contributes $h$, soIts degree of precision of a quadrature rule is three: it integrates every quadratic polynomial by construction, and also the cubic nodal polynomial $(x-a)(x-a-h)(x-b)$, whose integral vanishes by odd symmetry about $a+h$. Any cubic polynomial differs from its quadratic polynomial interpolant by a constant multiple of this nodal polynomial.

Read the differential order $dxdy$ literally: take quadrature nodes $X=(c,(c+d)/2,d)$ in $x$ and $Y=(a,(a+b)/2,b)$ in $y$. Applying Simpson's rule first in $x$ and then in $y$ multiplies the one-dimensional quadrature weights. With $s=(1,4,1)$, this tensor-product quadrature isEquivalently, the nine sampled function values have the quadrature weight arraywith rows indexed by the $x$ quadrature nodes and columns by the $y$ quadrature nodes. The quadrature weights sum to the rectangle's area. If the intended coordinate assignment is instead $x\in [a,b]$, $y\in [c,d]$, exchange $X$ and $Y$ in the formula. Both conventions give the same calculation on the unit square used below.

For the separable integrand, tensor-product quadrature factors into two one-dimensional applications of Simpson's rule:soThe exact double integral, evaluated by Fubini's theorem and the power rule for integration, isThe $x$ factor is always integrated exactly. All quadrature error therefore comes from applying Simpson's rule to the $y$ factor.

At $q=4$,This is an overestimate, with signed quadrature errorThe relative error is $(1/720)/(1/30)=1/24$, approximately $4.17\%$. The quartic polynomial $y^4$ lies beyond the degree of precision of a quadrature rule of Simpson's rule, so the exactness of the previous cases no longer applies.

At $q=3$,The $y$ factor is now a cubic polynomial. Simpson's rule still integrates it exactly because its degree of precision of a quadrature rule is three. Exactness of tensor-product quadrature depends on the polynomial degree in each variable, rather than their sum.

At $q=2$, the preceding tensor-product quadrature givesBoth factors of the separable integrand are quadratic polynomials, so exactness follows directly from the construction of Simpson's rule.

Apply the first Richardson extrapolation step to the two computed approximations:The exact integral is $I={\int }_0^1{x}^{4}dx=1/5$, so the actual absolute error isThus the requested strict error bound is verified directly. This first extrapolation of trapezoidal approximations is also the one-panel Simpson's rule value on the three nodes $0,1/2,1$.

Richardson extrapolation combines approximations with a known leading error power to cancel that error. If $A(h)=I+c{h}^p+O(h^{p+q})$, then $(2^{p}A(h)-A(2h))/(2^p-1)$ removes $c{h}^p$.

Let $x_j=a+jh$ for an even number $n$ of equal subintervals, with $x_n=b$. The composite trapezoidal rule isThe Simpson's rule isAssume an error expansion $T_h=I+c_2{h}^2+O(h^4)$, with the same coefficient $c_2$ on refined uniform meshes; $f\in C^4([a,b])$ is sufficient for this form. The coarser rule is $T_{2h}=h[f_0+f_n+2{\sum }_{\mathrm{even}}{f}_j]$. Direct coefficient collection givesThe leading $h^2$ errors cancel, leaving $S_h=I+O(h^4)$. The identity of the numerical integration weights is exact; the error-order conclusion additionally uses the smoothness and even-power error assumptions.

With the same three cosine values, Simpson's rule givesUsing the table's $n=12$ row gives $0.2618+4(0.1851)=1.0022$, with the same final rounding. That table row refers to the prefactor $\pi /12$; it does not change the specified number of strips.

With unit strip width, the composite trapezoidal rule givesFor Simpson's rule, the even integer arguments are the odd-numbered interior grid positions. ThereforeThe requested two-decimal answers are $T_{24}\approx 0.79$ and $S_{24}\approx 0.75$. The supplied component sums are individually rounded; they should not be treated as exact simultaneous identities. Computing from the original function gives approximately $0.786685$ and $0.748700$, respectively, with the same two-decimal results.

Take $n$ to be a positive even integer, as required by composite Simpson's rule. There are $n/2$ two-strip panels, each of width $2/n$. Applying the supplied panel bound with the global fourth-derivative minimum $0$ and maximum $1$, and summing, givesHere $E_n$ is the nonnegative absolute error. In this example Simpson's rule overestimates the integral, so $E_n=S_n-I$. Each panel has that same sign because its fourth derivative is nonnegative; cancellation is not being assumed.^[ref]

Choose equation (1), evaluated by refined composite Simpson's rule. It gives $y$ directly as a one-dimensional definite integral with fixed endpoints and a smooth integrand. It therefore avoids root finding altogether. Before evaluating, use the trigonometric identityThis equivalent integrand is nonnegative throughout $[0,\pi /2]$, avoiding cancellation between the original two terms. Equation (2) instead subtracts two potentially large exponential functions, while equation (3) would ordinarily put a numerical integration inside a root finding loop.

For even $n$, let $h=(\pi /2)/n$, $\varphi (x)=2\sin x\cos ((\pi /4)\cos x)$, and computeThen double $n$. The integrand has bounded derivatives of every fixed order on the integration interval; in the fourth-order error regime, the estimated remaining truncation error in $Y_{2n}$ is $|Y_{2n}-Y_n|/15$. The factor $15$ follows by eliminating the leading term $C{h}^4$ between the two mesh widths.^[ref]

Stop when this estimate is comparable to ${\epsilon }_{\mathrm{mach}}\max (1,|Y_{2n}|)$ and further refinement shows stagnation at the roundoff error scale. Check that the differences previously decreased consistently with fourth-order convergence; differences alone are not a rigorous error certificate if cancellation or roundoff error dominates. Compensated summation helps keep the summation error near the precision limit. Refining indefinitely after this point increases work without reliably adding meaningful digits. This answers the requested choice and termination strategy without requiring an explicit value of $y$.

Use Simpson's rule: the cubic exactness of Simpson's rule includes every quadratic integrand, so three function evaluations already give the exact answer. Thus the error is zero. For a general smooth integrand the corresponding composite Simpson's rule has error $O(N^{-4})$ in big O notation, but that bound is unnecessarily weak here.

A convenient choice for this irregular region is Monte Carlo integration. The region is contained in $[-1,1{]}^2$. For independent uniform points $U_j$ in that square, letThe indicator random variable incorporates the curved boundary directly. This estimator is unbiased; the integrand is bounded on the square, so its variance is finite. The variance of a sum of independent terms gives root mean square error $O(N^{-1/2})$ in big O notation. This is a stochastic error rate. Applying a rectangular Simpson's rule to the indicator-weighted integrand would lose the smoothness required for its fourth-order error bound.

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.