Trapezoidal Rule Integration

This documentation was generated with the assistance of AI. Please report any inaccuracies.

The extended trapezoidal rule is the simplest quadrature rule in the com.irurueta.numerical.integration package, and the building block that Simpson’s rule and Romberg integration refine to get faster convergence. It is described in Press et al., 2007, Sections 4.1 and 4.2 (pages 156–165), and implemented as TrapezoidalQuadrature / TrapezoidalMatrixQuadrature, consumed directly by TrapezoidalQuadratureIntegrator / TrapezoidalQuadratureMatrixIntegrator.

Problem statement

Given equally spaced abscissas spaced apart by step , with , the two-point trapezoidal rule approximates the integral over a single interval as:

Applying this repeatedly over consecutive intervals and summing gives the extended trapezoidal rule:

This is a closed formula — it evaluates the integrand at both endpoints and — and requires the integrand to be well-behaved (no singularities) over the whole finite interval ].

(a) Closed formulas such as the trapezoidal rule evaluate the integrand at both endpoints, while open formulas (used for improper integrals, see midpoint integration) evaluate only interior points; (b) each refinement stage of the extended trapezoidal rule reuses every previous evaluation and adds only the new midpoints

Incremental refinement

The key practical property of the extended trapezoidal rule is that doubling the number of intervals reuses every previous function evaluation — only the new midpoints need to be computed:

  • Stage 1: the crudest possible estimate, averaging the two endpoints:

  • Stage : adds the new interior points that lie exactly halfway between the points already used, and combines them with the previous estimate:

Each call to next() therefore doubles the resolution at the cost of only the newly added evaluations, not a full re-evaluation from scratch.

Why this rule matters beyond its own accuracy

The extended trapezoidal rule converges slowly (error ) on its own, but it has a "deep" property that makes it the ideal starting point for higher-order methods: its error, given by the Euler-Maclaurin summation formula, is a series containing only even powers of — there is no term, only terms with coefficients built from Bernoulli numbers. This is exactly the property that Simpson’s Rule Integration and Romberg Integration exploit via Richardson extrapolation to cancel out the leading error terms and converge much faster than the trapezoidal rule itself.

Algorithm

flowchart TD A["Stage 1: s = (b-a)/2 * (f(a) + f(b))"] --> B["Stage n: add 2^(n-2) new midpoints\nof the previous stage's intervals"] B --> C["s = 0.5 * (s_prev + (b-a) * sum(new points) / 2^(n-2))"] C --> D{"|s - s_prev| < eps * |s_prev| ?\n(checked after 5 stages, up to 35)"} D -->|No| B D -->|Yes| E["Return s"]

Library implementation

TrapezoidalQuadrature implements Quadrature.next() exactly as above; TrapezoidalQuadratureIntegrator wraps it with a plain convergence loop — no extrapolation — checking, after a minimum of 5 refinement stages and up to a maximum of 35, whether successive estimates agree to within a relative tolerance eps (default 1e-10). TrapezoidalMatrixQuadrature and TrapezoidalQuadratureMatrixIntegrator provide the same algorithm for matrix-valued integrands, evaluated via MatrixSingleDimensionFunctionEvaluatorListener.

This plain, non-extrapolating integration method corresponds to IntegratorType.QUADRATURE and QuadratureType.TRAPEZOIDAL, and can also be obtained through the package’s factory method:

final var integrator = Integrator.create(
        a, b, listener, IntegratorType.QUADRATURE, QuadratureType.TRAPEZOIDAL);
final var result = integrator.integrate();

TrapezoidalQuadrature is also the rule plugged into SimpsonTrapezoidalQuadratureIntegrator (Simpson’s Rule Integration) and RombergTrapezoidalQuadratureIntegrator (Romberg Integration), which reuse the same refinement loop but combine successive stages far more efficiently.

IntegratorType.QUADRATURE is a robust fallback for integrands that are not smooth (e.g. a function linearly interpolated between measured data points), but it is unsophisticated: if it needs too many stages to reach the requested eps, accumulated roundoff error can prevent it from ever converging. Prefer Simpson’s Rule Integration or Romberg Integration whenever the integrand is smooth enough to benefit from extrapolation.

Example

final var listener = new SingleDimensionFunctionEvaluatorListener() {
    @Override
    public double evaluate(final double point) {
        return Math.sin(point);
    }
};

final var integrator = new TrapezoidalQuadratureIntegrator(0.0, Math.PI, listener);
final var result = integrator.integrate(); // approximately 2.0