From a picture to an error estimate
Let with and . Divide it into columns and rows of equal widths and , where are positive integers. In each cell choose its midpoint , and define the midpoint sum
Definition 7.1.1
(Lipschitz function on a rectangle)
A function is Lipschitz with constant in the Euclidean norm if for all .
A Lipschitz function is continuous on the compact rectangle, hence Riemann integrable. The estimate below uses only the standard integral comparison and additivity over cells.
Theorem 7.1.2
(Midpoint-grid error bound)
If is Lipschitz on with constant , then
Control one cell, then add
Every point in a cell is at Euclidean distance at most half the cell diagonal from its midpoint. The bound then holds cell by cell and is added over the grid.
Proof
(Local half-diagonal bound, then summation over cells)
The farthest point of the closed cell from its midpoint is a corner, at distance . Thus for ,
Since , additivity of the integral over the cells gives
Each cell term has absolute value at most times the bound above (integral comparison). Add over the cells and use the triangle inequality: the total area is , which gives the claimed estimate.
Proof X-ray
Where the Lipschitz hypothesis enters
The one non-obvious move is to subtract the constant cell by cell: the midpoint sum is exactly the integral of a step function, so the error is a sum of integrals of , each of which is small because cannot move far from its value at .
The Lipschitz hypothesis is used exactly once, in the pointwise bound, and the choice of midpoint is used exactly once as well: it halves the diagonal. For an arbitrary sample point in the cell the same proof gives the full diagonal and a bound twice as large. Integrability is used only to split and compare integrals. The argument closes because every cell contributes the same bound times its own area, and the areas add up to . Since the final bound tends to zero as both widths do, no second-order accuracy of the midpoint rule is assumed or needed.
Worked examples
Worked example 7.1.3
(A square grid for a polynomial)
On , take . For two points in the square,
so works. For an grid, the general bound is . The exact integral, computed by iterated integration, is .
For this particular polynomial the midpoint sum can be computed more sharply. The midpoint average of is , while
The identity follows by expanding the square and using the finite sums for and . Hence . For the actual error is , while the general bound is . A bound valid for an entire class need not be sharp for a particular function.
Worked example 7.1.4
(A kink on a cell boundary)
On let , which is Lipschitz with but not differentiable along . The integral is . With the only sample is , where , so and the error is ; the bound is . With , the midpoints have , both with , and , , so : the sum is exact. The kink lies on the shared edge of the two cells, so is affine on each cell, and the midpoint rule is exact for affine functions. The bound, , is valid but pessimistic.
Worked example 7.1.5
(A non-square rectangle)
On take with , , so , . Since , take . The midpoints are and , so
while . The actual error is . The theorem gives . The bound is large because the tall cells () make the half-diagonal large, although does not depend on at all. The bound controls the worst direction in the cell, not the actual variation of .
Counterexample mode
A midpoint sum is not exact for every function
Claim: sampling at each cell's center makes the midpoint sum equal to the integral. Take on , whose integral is . For the only sample is at and the sum is . For the sum is , against . In general the error is for every . Repair: the midpoint rule is exact for affine functions, since on a cell the deviation integrates to zero by symmetry, but the term is curved and leaves a positive error. For general Lipschitz functions only the bound above is available.
The explorer below computes the exact midpoint sum for three functions on any grid of and compares the true error with the Lipschitz bound .
Checks and exercises
Quick check
(What is the cell area for an grid on ?)
Multiply the two cell widths.
Solution · Answer
.
Quick check
(In the first worked example, compute .)
Use .
Solution · Answer
.
Quick check
(Does the general bound alone promise an error on square grids?)
Look at how the bound scales with and .
Solution · Answer
No. On an grid, and are proportional to , so the displayed Lipschitz bound is . Faster decay, as for where the error is , needs more information about .
Quick check
(If is constant, can be used? What does the bound say?)
A constant function has no variation.
Solution · Answer
Yes, since . The bound then gives zero error, which is correct: every midpoint sum of a constant equals the integral.