Roadmap
- Set up the mesh and the rule.
- Prove the linear interpolation error formula.
- Derive the per-cell bound .
- Sum the cell bounds to get global bounds.
- Prove the exact signed error for .
- Work examples, including nodes .
- Look at what the bound does not control, with caveats about refinement and zero error.
- Implement the rule in MATLAB.
Setup
Let be finite real nodes, with . Write the cell widths as
so that . Let be real-valued and on .
Definition 3.2.1
(Composite trapezoidal rule and signed error)
The composite trapezoidal rule is
The signed error is exact integral minus approximation:
Always check which sign convention a source uses; here . All statements below are about exact real arithmetic.
Linear Interpolation Error
Fix a cell . Let be the linear interpolant with and , and let .
Lemma 3.2.2
(Linear interpolation error)
For each there is a such that
Proof
(Rolle's theorem applied twice)
At the endpoints both sides are zero, so any works. Now take in the open cell. Then , so we can set and define
This is and vanishes at the three distinct points , , and . Rolle's theorem gives two distinct zeros of , and applying Rolle again gives a with . Since and , this says , which is the claim.
Proof X-ray
Why the auxiliary function has three zeros
The proof manufactures a function that vanishes at one more point than the interpolant already does. The constant is chosen exactly so that at the chosen point; the interpolation conditions give the other two zeros for free. Three zeros of yield two of and one of , which is why the error involves the second derivative: the number of derivatives taken equals the number of interpolation nodes. The hypothesis is needed so that exists and Rolle applies the second time; the restriction to the open cell is needed because vanishes at the endpoints, where would not be defined (those points are handled separately and trivially). The point depends on , which is why the next step bounds instead of integrating .
Integrating exactly gives , because the integral of a linear function over an interval is the interval width times the average of the endpoint values. Hence
Per-Cell Bound
Theorem 3.2.3
(Per-cell error bound)
Let be any number for which we have proved that for all . Then
Proof
(Integrating the interpolation bound)
Such a number exists: is continuous on a compact interval, so is attained there. By the lemma, for every in the cell. Both sides are continuous functions, so we can integrate the inequality without worrying about whether is integrable. On the cell, , and with ,
Therefore .
Concept lensAnalytic
The cell error as a weighted integral of the second derivative
Since vanishes at both ends of the cell and , two integrations by parts leave no boundary terms and give
The weight is nonnegative with integral , so is times a weighted average of . Bounding by recovers the per-cell bound, and a sign-definite fixes the sign of : a convex gives , with equality only when is linear on the cell.
Global Bounds
Theorem 3.2.4
(Mesh-adapted and uniform global bounds)
With per-cell bounds ,
If is a proven bound for on all of , then
Proof
(Triangle inequality, then cubed is at most squared times )
The triangle inequality gives , hence the mesh-adapted bound. Use as a valid bound on every cell; previously chosen, possibly loose local bounds need not themselves be at most . Since ,
Each inequality in this chain can only lose sharpness. The middle expression is often much smaller than the last one when the mesh has only a few wide cells.
Exact Signed Error for
Proposition 3.2.5
(Exact error for the square function)
For , on every cell, so . The constant in the per-cell bound cannot be improved.
Proof
(The interpolation error is the node polynomial)
On each cell, is a quadratic with leading coefficient that vanishes at and . A quadratic is determined by its leading coefficient and its two roots, so exactly. Hence . With , the per-cell bound is , which equals exactly, so cannot be improved.
The error is strictly negative, so the rule overestimates every convex quadratic of this form.
Worked Examples
Worked example 3.2.6
(Nodes 0, 1/4, 1 for the square function)
Take . The widths are and , and the function values are , , and .
Check with the exact formula: . Bounds, using :
| Bound | Value | Compare with |
|---|---|---|
| Per-cell sum | equal (sharp) | |
| Global | larger, valid |
Worked example 3.2.7
(The exponential on a uniform mesh)
Take on with nodes , so . Then and , so (the rule overestimates, as for any convex function). On the two cells and , so the per-cell sum is and the global bound with is . Both bounds are valid and the actual error lies below both.
Worked example 3.2.8
(A single cell)
Take , and . Then and , so . Here and , so the bound is . With one cell there is nothing to sum, and the per-cell and global bounds coincide. The bound is valid but loose by a factor of two, because is far from constant on the cell.
What the Bound Does Not Control
Floating-point error. The theorem assumes exact arithmetic and applies to all strictly increasing finite real nodes, including those without an exact binary representation. It does not bound the errors introduced when intended nodes are rounded to stored floating-point values, or when widths, averages and sums are computed in floating point. If the stored nodes are instead treated as exact real numbers and the data are exact function values at those nodes, the theorem applies to that stored-node mesh. Differences from the intended mesh and data still require separate analysis.
Measurement error. Suppose the data are , for example from experiments. Then the bound covers only the part of the error. The noise contribution needs a separate analysis. In exact arithmetic, if , the extra error is at most , but that is an additional argument, not part of the theorem above.
Refinement caveats. Reducing shrinks the bound by a factor of about while stays fixed. It does not guarantee that the actual error decreases at every step. For , splitting a cell always helps, because for positive . For general this can fail.
Counterexample mode
Adding a node can make the error worse
Claim: refining the mesh by adding a node never increases the error. Take on , with exact integral . With nodes we get , so . With nodes :
so . Adding a node made the error worse, because the first mesh was exact only through cancellation of errors from the two halves where has opposite signs. The bound still holds on both meshes; it controls the size of , not its monotone decrease. In particular is not certification of accuracy.
Common mistake
(Reading the sign of E with the wrong convention)
Because , a negative means the rule gave a value that is too large: in the nodes example, and . Under the opposite convention the same computation gives . Check the definition before concluding that the rule over- or underestimates.
MATLAB Implementation
Save the function below as trapz_nonuniform.m. This version accepts only double-precision arrays: accepting all numeric classes would also admit integer arrays, whose arithmetic can round or saturate instead of computing fractional trapezoid averages. Other input types require an explicit conversion and a check that the converted nodes and data still express the intended problem.
function T = trapz_nonuniform(x, y)
%TRAPZ_NONUNIFORM Composite trapezoidal rule on a nonuniform mesh.
% T = TRAPZ_NONUNIFORM(x, y)
% x : 1-by-(n+1) real, finite, strictly increasing DOUBLE ROW vector
% y : 1-by-(n+1) real, finite DOUBLE ROW vector with y(k) = f(x(k))
if ~isa(x, 'double') || ~isa(y, 'double') || ~isrow(x) || ~isrow(y)
error('trapz_nonuniform:orientation', ...
'x and y must be double row vectors.');
end
if numel(x) ~= numel(y)
error('trapz_nonuniform:length', ...
'x and y must have the same number of elements.');
end
if numel(x) < 2
error('trapz_nonuniform:tooFew', 'At least two nodes are required.');
end
if ~isreal(x) || ~isreal(y) || ~all(isfinite(x)) || ~all(isfinite(y))
error('trapz_nonuniform:values', ...
'x and y must be real and finite.');
end
h = diff(x); % 1-by-n cell widths
if any(h <= 0)
error('trapz_nonuniform:order', ...
'Nodes must be strictly increasing (hence distinct).');
end
avg = (y(1:end-1) + y(2:end)) / 2; % 1-by-n endpoint averages
T = dot(h, avg); % sum_i h_i * avg_i
end
Usage with the worked example:
x = [0, 1/4, 1]; % 1-by-3 row vector
f = @(t) t.^2; % elementwise power keeps the row shape
y = f(x); % 1-by-3 row vector
T = trapz_nonuniform(x, y);
% Exact-arithmetic value: T = 13/32, error = 1/3 - 13/32 = -7/96
The test h <= 0 is applied to differences of the stored double-precision nodes. Passing it establishes their increasing order, not that they equal the mathematical values you intended. Finite inputs also do not prevent overflow in diff, the endpoint sums or the dot product; underflow and ordinary rounding remain possible as well. This simple implementation does not detect or certify against those arithmetic errors, and an Inf or NaN result is not a usable quadrature estimate.
Quick checks
Quick check
(For on nodes , compute and .)
Use .
Solution · Answer
, so . This agrees with .
Quick check
(For on with equal cells, what is the smallest for which the global bound with is at most ?)
Here and the bound is .
Solution · Answer
We need , that is . Since , the smallest is .
Quick check
(A computed trapezoidal error is exactly zero. Does this show the rule is accurate for nearby problems?)
Recall the example on .
Solution · Answer
No. holds for every linear , but it can also occur through cancellation when changes sign, as for on with nodes . Adding the node changes the error to .
Checklist
- I can state the setup: strictly increasing finite nodes, , and .
- I can prove the interpolation error formula using Rolle's theorem twice.
- I can compute and derive .
- I can pass from the per-cell bounds to and then to .
- I can prove for .
- I can reproduce , , and the bounds and for nodes .
- I can explain why rounding and measurement errors fall outside the bound.
- I can give a mesh refinement that makes the error worse, and explain why zero error certifies nothing.
- My MATLAB code checks double input type, orientation, lengths, finiteness, and strict monotonicity; these checks do not certify floating-point accuracy or prevent intermediate overflow.
Related note: Lab 03: Interpolation and Trapezoidal Quadrature