Why use a mesh?
A single high-degree polynomial couples every sample to the entire interval. Adding a point changes that polynomial everywhere, and on poorly chosen nodes increasing its degree need not improve the answer. A simpler alternative is to join neighboring samples by straight segments. This sacrifices smooth slopes at the nodes, but each value depends only on its two neighboring observations. It is especially useful when samples are naturally unevenly spaced.
Throughout, calculations with the supplied samples are exact. Measurement error and floating-point arithmetic are different questions.
Definition and local weights
Definition 5.3.1
(Piecewise-linear interpolant on a mesh)
Let , with . Given values , define on by
At a shared node both adjacent formulas give , so is continuous. On each open panel its slope is . The weights are nonnegative and sum to one inside the panel. Hence the value lies between the two endpoint data, even if those data are negative. This does not mean the interpolant is differentiable at a node: adjacent slopes can differ.
For a function , write for the interpolant with and set . The subscript describes the entire partition, not necessarily a uniform step.
Theorem 5.3.2
(Error and sensitivity on an uneven mesh)
If and , then for ,
Inside that panel,
If every supplied sample differs from by at most , then the resulting interpolant satisfies
The derivative estimate applies in open panels; at a knot the interpolant may have no derivative. If , all approximation bounds above hold with zero error.
Proof: two different kinds of error
Proof
(Remainder, averaged slope, and convex data weights)
For an interior point of one panel, the two-node interpolation remainder gives
for some . It follows from Rolle's theorem by subtracting a suitable multiple of to create a third zero. At the endpoints the error is zero. The product of the nonnegative distances to the endpoints is at most , proving the first bound.
For the slope, use the fundamental theorem of calculus:
Since , integrating this inequality and splitting at yields the displayed derivative bound. In particular the worst pointwise bound follows because the sum of the two squared distances is at most . This argument also describes the one-sided limiting slopes at knots; it does not invent a derivative where the two slopes disagree.
Finally, if the sample errors are , then on a panel the difference between the noisy and exact-data interpolants is the same convex combination of . Its absolute value is at most . The triangle inequality adds this data term to the approximation bound. The constant one is attained when all errors equal ; more nodes do not reduce an adversarial error bound unless the data improve.
Proof X-ray
Why the function and slope converge at different rates
The proof uses in two different ways. For values, Rolle's theorem is applied twice inside one panel, so only on that panel matters; the factor is a product of two distances, which is where comes from. For slopes, the key move is the identity expressing the panel slope as the average of over the panel. The slope error is then an average of , and enters only as a Lipschitz constant for : one distance, one power of .
The data term rests on a third fact. The value weights are nonnegative and sum to one, so sample errors are averaged and never amplified. The data slope is a difference quotient with weights , which have no such property. That is why the derivative bound needs exact samples, and why the alternating-error counterexample below succeeds. The triangle inequality closes the argument by adding the two contributions.
Worked example: an uneven partition
Worked example 5.3.3
(Interpolate a quadratic)
Take with nodes . On the interpolant is ; on it is . At it reports instead of . Here , , and the local value bound is attained. The left and right slopes at are and , so the interpolant has a corner even though the original function is smooth.
At , the slope error is . At points approaching the left end of the second panel it approaches , the upper bound . This example shows both constants are sharp as uniform bounds under these hypotheses, although the supremum of the slope error can occur at a one-sided endpoint limit.
Worked example 5.3.4
(A linear function with noisy samples)
Let on with nodes , and suppose the recorded samples are , so the errors are . This is the edge case : with exact data the interpolant would equal . The value bound is therefore the data term alone, . On the first panel the slope is , so the interpolant is and its error stays in . The slope error is , the largest value allowed by the data perturbation. No refinement of the mesh can remove an error that is already in the samples.
Worked example 5.3.5
(Choosing a uniform mesh for a tolerance)
To interpolate on with exact samples and uniform error at most , use . The theorem asks for , that is
Thus uniform panels suffice: gives , while gives about and fails the test. The proof uses only inside each panel, so may be replaced by the panel maximum . Near that maximum is close to one, so an uneven mesh may use panels up to about there.
Integrating the interpolant
Integrating each straight segment gives the nonuniform composite trapezoidal rule
Proposition 5.3.6
(Error of the nonuniform composite trapezoidal rule)
If , and , then
If instead for every , the right-hand side increases by at most .
Proof
(Integrate the pointwise remainder bound)
For exact samples, integrate the pointwise error bound rather than multiply its maximum by the panel length. With ,
If , positive quadrature weights sum to , so add at most .
These are absolute worst-case estimates. A small observed change between two meshes is not by itself an error certificate.
Counterexample mode
A good value approximation need not have a good slope
On , take and exact samples perturbed alternately by on a uniform mesh of spacing . The interpolant remains within of zero everywhere, but its panel slopes have magnitude . Holding fixed while refining increases this derivative error. Sample accuracy and mesh size must be considered together; the earlier derivative theorem assumes exact sample values.
Common mistakes
Common mistake
(Using the average spacing in an uneven-mesh bound)
The value bound is governed by the widest panel, not by . For on nodes , the average spacing would suggest , yet the error at is . Use , or better the panel-by-panel bound .
Common mistake
(Assigning a derivative to the interpolant at a knot)
The interpolant is continuous at every node but usually has two one-sided slopes there. In the quadratic example the slopes at are and , so does not exist. The derivative estimate is a statement on open panels; at a knot, report the one-sided limits.
Practice
Quick check
(For on and nodes , calculate the interpolant at , its actual error there, and the local theorem bound.)
Locate the panel containing first.
Solution · Answer
The endpoint values on the second panel are and . The fraction from to is , so the interpolant is . The error is . The pointwise bound with is ; the panel-wide bound is .
Quick check
(The same function is interpolated on nodes . Compute the composite trapezoidal approximation to its integral over , then compare with the exact integral and the sum-of-cubes bound.)
Two panels, of lengths one and two.
Solution · Answer
The rule gives . The integral is , so the error is . With the bound is , attained here.
Quick check
(Suppose on , sample errors are at most , and . Give a uniform value bound. Can it certify an error below ?)
Add the approximation term and the data term.
Solution · Answer
The bound is . It cannot certify an error below ; it is an upper bound, not proof that the actual error exceeds that threshold.
Quick check
(If each node error is at most , bound the slope perturbation on a panel of length . Show that the bound is attainable.)
The slope of a panel is a difference quotient of two samples.
Solution · Answer
The noisy slope differs by , whose magnitude is at most . Opposite errors and attain it.