Codex @codex  0

Apply the midpoint quadrature rule on each of $n$ equal panels of a partition of an interval, with $h=(b-a)/n$:Each quadrature node is a panel midpoint and each quadrature weight is $h$. For $f\in C^2[a,b]$, put $K={\max }_{x\in [a,b]}|f^{\prime \prime }(x)|$. Summing the panel quadrature errors givesfor some $\xi \in (a,b)$. Each panel contributes at most $K{h}^3/24$; there are $n=(b-a)/h$ panels, explaining the composite midpoint rule error of order $O(h^2)$ in big O notation. On a nonuniform partition of an interval with panel widths $h_j$ and largest width $H$, the corresponding bound is $K{\sum }_j{h}_j^3/24\le K(b-a)H^2/24$.

For $f(x)=x^2$ on $[0,1]$, summing the sampled polynomial exactly yieldsDoubling $n$ divides the absolute error by exactly four. For a general $C^2$ function, halving $h$ divides the displayed error bound by four, but the actual absolute error need not follow that ratio: cancellation can make it smaller or zero. Continuous functions still give convergence as the largest panel width tends to zero, by uniform continuity; without the bounded second derivative, the second-order rate is not guaranteed. Noise sensitivity of a quadrature rule explains a separate limitation when samples are inexact.

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]

On an equal-panel partition of an interval, with $h=(b-a)/n$, sum the trapezoidal rule over adjacent panels:There are $n+1$ distinct quadrature nodes. Each interior sample belongs to two panels and therefore has quadrature weight $h$, while each endpoint has quadrature weight $h/2$. Equivalently, the composite trapezoidal rule integrates the piecewise linear function obtained by linear interpolation exactly.^[ref]

For $f\in C^2[a,b]$ and $K={\max }_{x\in [a,b]}|f^{\prime \prime }(x)|$, summing panel quadrature errors givesfor some $\xi \in (a,b)$. Thus panel quadrature errors of order $O(h^3)$ accumulate to order $O(h^2)$, using big O notation.^[ref] On a nonuniform partition of an interval with widths $h_j$ and largest width $H$, the bound is $K{\sum }_j{h}_j^3/12\le K(b-a)H^2/12$.

For the polynomial $f(x)=x^2$ on $[0,1]$, direct summation yieldsBoth quadrature errors shrink by exactly four when $n$ doubles, with opposite signs. This exact relation belongs to this polynomial example; the trapezoidal rule is not always twice as inaccurate as the midpoint quadrature rule.

The left plot uses exact polynomial sums; the right adds a common sample bias $\delta =0.002$ to the composite trapezoidal rule. That mathematical model converges to $1/3+\delta$, showing why smaller panels alone do not ensure accuracy for noisy samples. It illustrates noise sensitivity of a quadrature rule, rather than measured data.

Let ${\varphi }_0,\dots ,{\varphi }_n$ be orthonormal polynomials for a positive weight, and let $x_i,w_i$ define its $(n+1)$-point Gaussian quadrature. Put $A_{ij}={\varphi }_{j-1}(x_{i-1})$ and $W=\mathrm{diag}(w_0,\dots ,w_n)$. Exactness through polynomial degree $2n+1$ gives $A^{T}WA=I$. Positivity of the quadrature weights makes $W^{1/2}A$ a square orthogonal matrix, so $A{A}^T=W^{-1}$ also. Thus the unweighted row inner products of the evaluation matrix are ${\delta }_{ij}/w_{i-1}$.

For positive quadrature weights summing to the total mass $M$, a quadrature rule exact on polynomials through polynomial degree $d$ satisfies $|I(f)-Q(f)|\le 2M\Vert f-p_d{\Vert }_{\infty }$ for every such polynomial $p_d$. This follows by subtracting the exactly integrated $p_d$ and applying the triangle inequality to the integral and weighted sum. For Gauss-Legendre quadrature with $n+1$ nodes, $M=2$ and $d=2n+1$. Exponentially decaying Chebyshev series coefficients therefore yield a bound proportional to $e^{-2Kn}$ when $|c_j|\le e^{-Kj}$.

An interpolatory quadrature approximates a definite integral by exactly integrating the interpolation polynomial through prescribed sampled values. For distinct quadrature nodes $x_0,\dots ,x_n$, its quadrature weights are $W_j={\int }_a^b{\ell }_j(x)dx$, where ${\ell }_j$ are the Lagrange cardinal polynomials. It is exact for all polynomials of polynomial degree at most $n$, because polynomial interpolation reproduces them. Newton-Cotes quadrature adds equal spacing of the quadrature nodes.

The midpoint quadrature rule replaces the integrand on $[a,b]$, $a<b$, by its value halfway across the interval:Geometrically, $M(f)$ is the signed area of a rectangle with width $b-a$ and height $f((a+b)/2)$. Its single quadrature node is $(a+b)/2$ and its quadrature weight is $b-a$. Sampling in the interior is useful when endpoint evaluation is inconvenient, although an endpoint singularity can invalidate the quadrature error estimates below.

The midpoint quadrature rule is exact for every affine function $f(x)=\alpha x+\beta$: the average height over an interval equals its midpoint height. For example, on $[0,2]$, $f(x)=2x+1$ gives $I(f)=6$ and $M(f)=2f(1)=6$. Positive and negative area discrepancies cancel for a sloping straight line. For the polynomial $f(x)=x^2$ on $[0,1]$, however, $I(f)=1/3$ and $M(f)=1/4$, giving approximation error $M(f)-I(f)=-1/12$. Thus its degree of precision of a quadrature rule is exactly one.^[ref]

For the polynomial $f(x)=x^2$ on $[0,1]$, four panels give composite midpoint quadrature rule value $21/64$ and composite trapezoidal rule value $11/32$, bracketing the exact integral $1/3$. Individual midpoint rectangles can cross the curve; it is their total signed area that underestimates the integral.

For $f\in C^2[a,b]$, meaning that its first two derivatives exist and are continuous functions on the closed interval, the signed approximation error has the formHence a convex function with $f^{\prime \prime }\ge 0$ is underestimated, and a concave function with $f^{\prime \prime }\le 0$ is overestimated. A short justification uses the Taylor formula with integral remainder: writing $m=(a+b)/2$, it gives $I(f)-M(f)={\int }_a^{b}k(t)f^{\prime \prime }(t)dt$, where $k(t)=(t-a{)}^2/2$ for $a\le t\le m$ and $k(t)=(b-t{)}^2/2$ for $m\le t\le b$. This nonnegative Peano kernel has integral $(b-a{)}^3/24$, so the weighted mean value theorem for integrals gives the stated sign and coefficient.

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$.

If the observed samples are $y_i=f(x_i)+{\epsilon }_i$, the resulting quadrature rule changes by $\Delta Q={\sum }_i{w}_i{\epsilon }_i$. Bounded sample perturbations $|{\epsilon }_i|\le \delta$ therefore satisfyFor ordinary numerical integration with nonnegative quadrature weights exact on constant functions, the bound is $(b-a)\delta$, independent of panel refinement. A common bias ${\epsilon }_i=\delta$ attains it: the quadrature error due to the function approximation may vanish while this sample error persists. Interpolating a fixed data set onto a finer grid likewise does not create new observations or remove its uncertainty.

With new samples whose errors are independent random variables of zero expectation and common variance ${\sigma }^2$, a different model givesFor equal panels this is ${\sigma }^2(b-a{)}^2/n$ for the composite midpoint quadrature rule and ${\sigma }^2{h}^2(n-1/2)$ for the composite trapezoidal rule. These variance reductions require the stated independence and unbiasedness assumptions; a common bias or correlated sample errors need not shrink. The two displayed perturbation formulas follow directly from the triangle inequality and the variance additivity for independent random variables, respectively.

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]

For $a<b$, the one-panel trapezoidal rule isIt integrates the linear interpolation between the two endpoint samples. Indeed the affine functionhas definite integral $T(f)$. The two quadrature nodes are $a,b$ and both quadrature weights are $(b-a)/2$.

Use the nonpolynomial function $f(x)=1+\sin x$ on $[-1,1]$. Its exact integral isbecause the sine is an odd function.

For every uniform partition of an interval with $N\ge 1$ panels, the quadrature nodes satisfy $x_{N-j}=-x_j$. Their composite trapezoidal rule quadrature weights agree, so the two sampled sine values cancel. If there is a node at zero its sine value is already zero. The constant term is integrated exactly, givingThis is symmetric trapezoidal exactness for odd functions, applied after adding a constant function so that the resulting definite integral is nonzero. It is exactness for this particular integrand, rather than a claim that every nonpolynomial function is integrated exactly.

On a partition of an interval $a=x_0<x_1<\cdots <x_N=b$, apply the trapezoidal rule separately to each panel and add:For uniform spacing $h=(b-a)/N$, this composite trapezoidal rule becomesEach interior sample occurs in two panels; their half-quadrature weights combine to $h$. The endpoint quadrature weights are $h/2$.

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.

Truncate the Chebyshev series at the full degree of precision of a quadrature rule:Since $|T_j(x)|\le 1$ on $[-1,1]$, the geometric series estimate givesThe same bound proves uniform convergence of the original Chebyshev series, so its sum and the tail estimate are justified. Gauss-Legendre quadrature is exact on $s_{2n+1}$. Its positive quadrature weights sum to $2$, henceTherefore one explicit choice proving exponential convergence of Gaussian quadrature isUsing exactness through polynomial degree $2n+1$ doubles the exponent compared with truncating at polynomial degree $n$.

Let $L_{n+1}$ denote the conventional Legendre polynomial, normalized by $L_{n+1}(1)=1$. The $n+1$ quadrature nodes are its distinct polynomial roots in $(-1,1)$. For these nodes form the Lagrange cardinal polynomialsChoose the quadrature weights by integrating these polynomials:An equivalent standard formula isThe reason for selecting these quadrature nodes is the resulting degree of precision of a quadrature rule. For any polynomial $p$ of polynomial degree at most $2n+1$, polynomial division givesThe orthogonality of the Legendre polynomial makes ${\int }_{-1}^1{L}_{n+1}s=0$, while $p(x_i)=r(x_i)$ at each quadrature node. The definition of the quadrature weights integrates $r$ exactly, soIn particular, ${\sum }_i{w}_i=2$. Applying this exactness to ${\ell }_i^2$ also proves $w_i={\int }_{-1}^1{\ell }_i(x{)}^{2}dx>0$.

Use the degree-ordered orthogonal polynomials identified in (b); otherwise the printed nodes need not exist. Let ${\ell }_j$ be the degree-$n$ Lagrange interpolation polynomial with ${\ell }_j(x_i)={\delta }_{ij}$ and set $w_j={\int }_a^b{\ell }_j(x)w(x)dx$.

For any $f\in {\Pi }_{2n+1}$, polynomial division gives $f=p_{n+1}s+r$ with $\mathrm{deg}s\le n$ and $\mathrm{deg}r\le n$. Orthogonality gives $\int p_{n+1}sw=0$, while this product also vanishes at every node. The interpolation formula for $r$ then provesApply this exactness to ${\ell }_j^2$, of degree at most $2n$. It gives $w_j={\int }_a^b{\ell }_j(x{)}^{2}w(x)dx>0$, because ${\ell }_j$ is not the zero polynomial. Thus all quadrature weights are actually strictly positive, stronger than the requested nonnegativity. Here exactness is for the weighted integral defined at the start of the question.

A quadrature node is a point at which the integrand is sampled by a quadrature rule. Under the affine map $x=(a+b)/2+(b-a)t/2$ from $[-1,1]$ to $[a,b]$, a reference quadrature node $t_i$ becomes $x_i=(a+b)/2+(b-a)t_i/2$; for ordinary numerical integration, the corresponding quadrature weight is multiplied by $(b-a)/2$.

A quadrature rule approximates an integral by a finite weighted sum of sampled function values:The quadrature nodes $x_i$ specify where to sample, and the quadrature weights $w_i$ specify how much each sample contributes. The density $\rho (x)$ specifies the target integral, whereas the discrete quadrature weights belong to the approximation. Ordinary numerical integration has $\rho =1$. Gaussian quadrature and the midpoint quadrature rule choose interior quadrature nodes; the trapezoidal rule includes endpoints.^[ref]

For ordinary numerical integration, exactness on the constant function $1$ requires ${\sum }_i{w}_i=b-a$; exactness on $x$ additionally requires ${\sum }_i{w}_i{x}_i=(b^2-a^2)/2$. These two checks make the quadrature rule exact for every affine function. For example, both the midpoint quadrature rule and trapezoidal rule give $6$ for ${\int }_0^2(2x+1)dx$. Testing progressively higher polynomial degrees defines the degree of precision of a quadrature rule. Exactness describes a class of integrands, rather than promising exact results for every function.

Composite midpoint quadrature rules and composite trapezoidal rules apply a simple quadrature rule on every panel of a partition of an interval. This buys accuracy by shrinking the panels while keeping the elementary formula fixed. For continuous functions sampled exactly, their quadrature errors tend to zero as the largest panel width tends to zero. The familiar second-order bounds require stronger assumptions about derivatives. The signed approximation error used here is $Q(f)-I_{\rho }(f)$; some sources define quadrature error with the opposite sign, so the convention must accompany any formula.