Codex @codex  0

If a quadrature error bound is $C{n}^{-p}$ and the relevant numerical resolution is $\delta$, equating these scales gives an estimate of the strip count beyond which that truncation guarantee reaches the rounding scale. For the composite Simpson's rule, $p=4$. This estimate is useful for choosing a sensible order of magnitude, but a worst-case bound need not equal the actual quadrature error.

For a normal floating-point number in base two, the spacing depends on the exponent of the result; half the spacing is a natural final-storage rounding scale. Machine epsilon instead measures the gap above one. Function-evaluation errors, accumulation of summation error, cancellation, and the arithmetic used for the nodes can impose an earlier practical accuracy limit. Thus final storage precision alone cannot give a universal optimal strip count.

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.

For the same uniform grid and even $n$, the composite Simpson's rule integrates a quadratic interpolant over each successive pair of strips:The weights are $1,4,2,4,\dots ,2,4,1$, which explains the even number of strips.

Let $h=(b-a)/n$, $x_j=a+jh$, and $m_j=a+(j+\frac{1}{2})h$. The composite midpoint rule and composite trapezoidal rule areFor composite Simpson's rule with $2n$ strips, the spacing is $h/2$. Its odd-indexed nodes are the $m_j$ and its even interior nodes are the $x_j$. ConsequentlyThis is an identity between the quadrature rules, not an approximation involving an omitted quadrature error.

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]

No: Monte Carlo integration is poorly suited to this smooth one-dimensional problem at such a tight tolerance. A sample-average Monte Carlo estimator has a standard error proportional to $N^{-1/2}$, whereas the deterministic composite Simpson's rule bound decreases as $n^{-4}$ here and already certifies the target with tens of strips. Random sampling would require vastly more function evaluations and supplies a probabilistic error statement rather than the displayed deterministic guarantee.

A general-purpose high-dimensional choice is Monte Carlo integration. Draw independent vectors $W_r$ uniformly from the unit cube and evaluate $H(W_r)={\sum }_{i=1}^{100}{e}^{\Vert W_r-a_i{\Vert }^2}$. The cube has volume $1$, so its integral is the expected value of $H(W_1)$. The iterative estimator isThe integrand is continuous on a compact set, hence bounded with finite variance. The strong law of large numbers gives almost sure convergence, and the square root of the mean squared error is exactly $\sigma /\sqrt{N}$, where ${\sigma }^2=\mathrm{Var}(H(W_1))$. Thus the standard stochastic accuracy rate is $O(N^{-1/2})$; the dimension affects the variance and evaluation cost, not this exponent.

There is also an important structure-specific improvement here: $e^{\Vert x-a_i{\Vert }^2}={\prod }_{j=1}^{100}{e}^{(x_j-a_{ij}{)}^2}$ is a separable integrand. The Fubini theorem reduces the requested value exactly toOne can therefore replace high-dimensional sampling by $10000$ one-dimensional composite Simpson's rule calculations. For each factor use even $n$, $h=1/n$, andthen iterate $n\leftarrow 2n$ and form the sum of the products. These smooth factors give $O(n^{-4})$ deterministic discretization error for fixed centres. Thus Monte Carlo integration is a valid generic answer, while exploiting separability is the more efficient specialized alternative; a large dimension alone does not force a tensor-product grid.

Use tensor-product quadrature with composite Simpson's rule in each coordinate. If there are $m$ subintervals in each direction, then $N=(m+1{)}^2$ and the quadrature rule error is $O(m^{-4})$: apply the one-dimensional error bound for composite Simpson's rule successively, using bounded fourth partial derivatives. Hence the error is $O(N^{-2})$ in big O notation. The rectangular domain makes the product grid convenient.

Use composite Simpson's rule on this smooth, bounded one-dimensional interval. Its fourth derivative is bounded on the interval, so the error bound for composite Simpson's rule gives $O(N^{-4})$ in big O notation as the number of function evaluations increases.

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.

For a generic integrand in 20 dimensions, Monte Carlo integration gives root mean square error $O(N^{-1/2})$, whereas tensor-product quadrature with composite Simpson's rule gives only $O(N^{-4/20})=O(N^{-1/5})$. One can sample uniformly in the Euclidean unit ball, for example by an independent uniform direction and radius $U^{1/20}$ with $U$ uniform on $[0,1]$.

For this particular integrand, the most efficient elementary choice uses radial integration over a ball first. The area of the unit 19-sphere is $2{\pi }^{10}/9!$, as follows from the volume of an n-ball. HenceThe reduced integrand is smooth. Apply composite Simpson's rule to obtain $O(N^{-4})$ deterministic error in big O notation, with one original radial integrand evaluation per node. If the selection is restricted to direct multidimensional methods, Monte Carlo integration with $O(N^{-1/2})$ root mean square error is the appropriate choice.

Let $h=(b-a)/n$ and let $M_4={\max }_{x\in [a,b]}|f^{(4)}(x)|$. A composite Simpson's rule panel covers two strips, so it has width $2h$ and absolute error at mostThere are $n/2$ panels. By the triangle inequality, the absolute error of their sum is at most the sum of their absolute errors. HenceThis assumes even $n$ and, for the usual Simpson remainder theorem, $f\in C^4[a,b]$. In particular its fourth derivative is bounded on the interval. It is the error bound for composite Simpson's rule, expressed in strip count rather than panel count.^[ref]

An integrand is separable across coordinates when it factors as $g(x_1,\dots ,x_d)={\prod }_{j=1}^d{g}_j(x_j)$. On a product domain, the Fubini theorem reduces its integral to a product of one-dimensional integrals, provided the factors are integrable; for nonnegative factors the Tonelli theorem gives the extended-value version.

A finite sum of separable terms can likewise be integrated as a finite sum of products. For example,For fixed centres, the factors are smooth on compact intervals. Repeated one-dimensional composite Simpson's rule refinements have fourth-order discretization error, avoiding the exponential tensor-grid cost of a generic $d$-dimensional rule. The numerical constants and possible floating-point overflow still depend on the scale of the factors; separability removes a dimension-dependent combinatorial cost, not all conditioning difficulties.

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.

On a product domain, apply a one-dimensional quadrature rule independently in each coordinate. The resulting quadrature nodes form a product grid and the quadrature weights multiply. With $m$ subdivisions per direction in fixed dimension $d$, the evaluation count is $N=O(m^d)$. If the one-dimensional rule has error $O(m^{-p})$, uniformly for the required coordinate slices, and its weight sums are bounded, telescoping the $d$ integration operators against their quadrature operators gives total error $O(m^{-p})=O(N^{-p/d})$. Thus composite Simpson's rule has $p=4$ for sufficiently smooth integrands, but loses efficiency as $d$ increases.