Motivation
The central difference needs a value on each side of , and such values are often unavailable. At the first recorded time of an experiment there is no earlier measurement. At the edge of the region on which a model is defined, a formula on the other side has no meaning. Recorded samples are also frequently uneven, because readings were taken irregularly or some were discarded. In each case we must estimate from values at points that lie on one side of and need not be equally spaced.
The principle of the preceding note still applies: interpolate the samples by a polynomial and differentiate the interpolant. What changes is the bookkeeping. The weights lose their symmetry, some of them are large, and the error constants depend on where the nodes sit. We derive the weights once in general, prove a bound that keeps the truncation error and the effect of data errors apart, and then treat the stencil , , completely.
Setting and assumptions
Definition 13.1.1
(One-sided stencil)
Fix an integer and distinct real numbers , the dimensionless node offsets. Fix a target point and a scale ; the sample points are . The stencil is one-sided when all (or all ). Usually , so that itself is sampled. “Unequal” only means that the need not form an arithmetic progression; distinctness is the sole structural requirement.
Let be the smallest closed interval containing and all sample points:
For a one-sided stencil, is an endpoint of . Then is a one-sided derivative, understood as in the earlier note through continuous extension from the interior.
Definition 13.1.2
(Derivative rule and exactness on )
A derivative rule on the stencil is a formula
with real, dimensionless weights . It is exact on if for every polynomial of degree at most .
The data model is deterministic. We receive , where for a known , and the errors may have any signs and any mutual dependence. The reported value is , computed in exact arithmetic. Nothing below bounds rounding in forming , in evaluating , or in forming the weighted sum. If a separate argument bounds the evaluation errors, they may be absorbed into . The arithmetic of the combination remains outside this analysis.
The smoothness hypothesis has two parts. First, . Second, there is a number such that for every . This is information about the function on the whole interval, and it must be supplied from outside the data.
The general theorem
Theorem 13.1.3
(Unique exact weights and a two-part error bound)
Let be the Lagrange basis polynomials for the nodes , so that equals when and otherwise.
(i) Exactly one weight vector makes exact on , namely . It depends neither on nor on . It is characterized by the moment equations
(ii) Under the smoothness hypothesis and the data model above,
For a fixed stencil and arbitrary admissible data errors, the term cannot be reduced.
Proof
Proof
(Exact weights and the two-part bound)
Change of variable. For a polynomial , set . Then exactly when , and the samples are . The chain rule gives . Hence is exact on precisely when
holds for every . Neither nor appears in .
Existence. By uniqueness of interpolation, each coincides with its own interpolant: . Differentiating at yields . So satisfies .
Uniqueness. Suppose two weight vectors satisfy . Their difference satisfies for every . Choosing gives for each .
Moments. The polynomials span , and both sides of are linear in . Hence is equivalent to its instances for . These instances are the moment equations, because is for and otherwise. In matrix form they read . Here is the Vandermonde matrix, and has entry at and zeros elsewhere. The argument above shows this system has exactly one solution. This is another way of seeing that is invertible for distinct nodes.
Truncation. Take . The segment from to lies in , and Taylor's theorem with Lagrange remainder gives
for some between and . For the remainder term vanishes, so the same identity holds with any . Multiply by and sum over . The term with index contributes
By the moment equations, this equals for and vanishes otherwise. Therefore
The points are unknown and generally different, so we bound each term separately. This gives .
Data errors. By linearity, . The triangle inequality bounds its absolute value by . Now write
One more triangle inequality proves the bound. Finally, is admissible and makes exactly. So that term cannot be reduced.
Proof X-ray
Where each hypothesis is used
Distinctness of the offsets is used only to build the Lagrange basis, and that basis delivers both existence and uniqueness. The moment equations do all the cancellation. They remove every Taylor term except the one carrying . The proof bounds the remainder by a constant times . The first moment left unprescribed is the one with , but it may vanish for a particular stencil; extra cancellation can improve the order under suitable additional smoothness.
The bound must hold on all of . A remainder point may lie anywhere between and the farthest node.
The data bound is never combined with smoothness. The term would be identical for a function about which nothing is known. So it describes the formula, not .
The stencil , ,
Worked example 13.1.4
(Weights for the stencil )
Take and . These are three nodes to the right of , separated by gaps and . The Lagrange basis is
The derivatives are , and . Evaluating at gives
The moments confirm this:
- ;
- ;
- .
The next moment is . So the rule is not exact on cubics.
Proposition 13.1.5
(Error bound for the stencil )
Let , and on . Suppose each of the three supplied values has absolute error at most , and is the rule above evaluated exactly on them. Then
Proof
(Specializing the general bound)
Here . The general remainder, with and , is
Bounding each third derivative by gives , so . The absolute weights sum to , so . The general theorem then yields the proposition.
The constant arises from letting the two remainder terms take opposite signs at full size. The argument does not claim that is the smallest valid constant. The exercise on the family below shows that the smallest valid constant for this rule is at least .
Choosing from the bound
Write and suppose and . Then . It is negative for and positive for , where
The value of follows because at that point.
This minimizer is meaningful only when it is admissible. In practice is known on some interval , so ranges over .
- If , then minimizes on .
- If , then is decreasing throughout , and the bound-based choice is . Using would sample where is not known, and would not be a proved bound at all.
If and , the bound decreases as decreases and has no minimizer on . If and , then agrees with a quadratic on the interval, so the rule is exact for exact samples; the bound is minimized at . If , the bound is zero for every admissible , so every such minimizes it.
When and is admissible, it minimizes an upper bound, not the unknown actual error. The rounding errors excluded from the model can also matter when is very small.
A cubic: actual error against the bound
Worked example 13.1.6
(Exact samples of a cubic)
Let , and . Then . The samples are , and . Hence
The signed error is .
The same number follows structurally. Take at a general . Expanding the three samples gives . Polynomials of degree at most two are differentiated exactly. Hence, for any cubic with leading coefficient , the signed error is exactly . Here and .
With , the proposition guarantees only . That is twice the actual error. The remainder formula explains the gap: gives . The two remainder terms partly cancel, whereas the bound adds their magnitudes.
The sign is also informative. This rule underestimates the derivative of every cubic with , always by .
Noise amplification and conditioning
The term is the price of differencing. The weights are of moderate size and sum to zero, so a constant offset in the data cancels exactly. The weighted sum of errors is divided by : its worst-case amplification grows as , although some non-constant error patterns also cancel. For this stencil, the errors realize the worst case. They add exactly to the output, whatever is.
In the language of conditioning, is the exact worst-case amplification factor for this rule and this error model. It maps the largest absolute data error to the absolute error of the reported derivative. It is not a relative condition number: when is close to zero, a relative error statement can be much worse. Nor does it describe the typical behavior of random errors, which may partly cancel.
What the bound guarantees is two-sided:
- no admissible data error moves the output by more than ;
- some admissible data error moves it by exactly that amount.
Worked example 13.1.7
(Comparing with the equally spaced stencil )
Node placement affects both constants. For the equally spaced stencil , the moment equations read , and . Subtracting the last two gives , hence and . Then , the same truncation constant, while . At the same , the stencil has the smaller noise constant. However, it samples up to rather than , so its hypothesis concerns a longer interval and possibly a larger .
The exercise on the stencil below shows that moving the middle node away from can enlarge the truncation constant substantially. Comparisons between stencils are meaningful only when the interval and the smoothness assumption are held fixed.
Why smoothness must be assumed
Counterexample mode
Identical samples, different derivatives
Take and . Then , which are the same three samples as the zero function. Yet
Both functions are polynomials and hence infinitely differentiable. Any procedure that sees only the three values must report the same number for both. So it misstates at least one of the derivatives and by at least .
Replacing by makes the discrepancy , which is unbounded as varies. No exact general recovery of from these samples is possible.
The repair is a quantitative hypothesis. Since , the assumption on forces . Within this family, each derivative differs from zero by at most ; the range of possible derivatives has diameter .
The lesson holds at every target point. Differentiability, even infinite differentiability, yields no error guarantee from finitely many samples. Adding to any function leaves its samples at unchanged and shifts its derivative at by . So the data are consistent with every real value of the derivative.
A bound on over all of restricts this family. A bound valid only near does not suffice, because may lie near . Such a bound has to come from knowledge of how the data arose, for example from a model or a differential equation that the function satisfies. It cannot be read off the samples.
Common mistakes
Common mistake
(Bounding the third derivative only near the target)
A bound on over , or only near , does not justify the proposition. The remainder point for the farthest node may lie anywhere in , so must bound on all of .
Common mistake
(Reading the bound-optimal step as error-optimal)
The step minimizes a worst-case upper bound, and only when it is admissible. It is not the step that minimizes the actual error, which depends on the unknown function and on the particular data errors.
Common mistake
(Rescaling equally spaced weights)
Weights for an uneven stencil are not obtained by rescaling those of an equally spaced one. They must be recomputed for the actual offsets, from the moment equations or from the Lagrange basis.
Summary
For distinct offsets, exactly one rule is exact on . Its weights are , and they satisfy the moment equations.
Assume a bound on over the whole sampled interval and a bound on each data error. Then the exact-arithmetic error is at most , and the data term is attained.
For the stencil , the bound is . For a cubic with nonzero leading coefficient , choosing the tight bound makes the truncation term twice the actual absolute error; a larger valid makes the ratio larger. Without a quantitative smoothness bound, the samples do not determine the derivative.
Exercises
Quick check
(Consider the one-sided stencil .)
(a) Solve the moment equations for the weights exact on . Confirm one weight with the Lagrange basis.
(b) Compute and . State the resulting error bound together with its hypotheses.
(c) Find the signed error for a cubic with leading coefficient , and compare it with the stencil .
Solution
(a) The moment equations for are
The third equation gives . Substituting into the second gives . Hence
The solution is unique because the nodes are distinct, by the theorem. Equivalently, the Vandermonde determinant is nonzero.
As a check, , so .
(b) The noise constant is . For the truncation constant, and , so .
The resulting statement: if with there, and the data errors are at most , then in exact arithmetic
(c) The remainder is . For a cubic, , so the signed error is .
Directly, for at :
The stencil gives . Both stencils span and have . However, leaving a gap of next to doubles the cubic error and raises the proved truncation constant from to .
Quick check
(Let , and .)
(a) Consider any procedure that reports a number from the three exact samples at . Show that, for some function with on , its error is at least .
(b) Show that the rule of the stencil has error exactly for . What does this say about the constant in ?
Solution
(a) Each vanishes at , exactly as does. By the computation in the counterexample, . Since , the choice satisfies the hypothesis, as does the zero function.
A procedure receiving the samples reports a single number for both functions. Its errors are and . Their sum is at least , so the larger of the two is at least .
(b) applied to zero data gives , while . So the error is exactly . This agrees with the cubic formula at .
Consequently, for this rule, no bound of the form valid for all admissible can have . The proved constant is therefore at most twice the best possible constant for . By part (a), no rule based on these samples can guarantee a constant below .
Quick check
(Let , and . Use the stencil .)
(a) Supply the data errors and compute .
(b) Repeat with the errors .
(c) Explain what these two computations show about the bound .
Solution
(a) The exact samples are . Then
as exactness on requires. The data errors add
So , and the error equals .
(b) The errors add . So , and the reported derivative is correct.
(c) Since , one may take . The proposition then gives exactly , which part (a) attains, so the data term is sharp. Part (b) shows that data errors of the same size can be harmless.
The bound is a worst-case guarantee over all sign patterns, not a prediction of the error for a particular pattern. In (a), for fixed , the error grows without bound as .
Quick check
(Use the stencil . Suppose and every sample has absolute error at most .)
(a) Compute and , assuming the derivative bound holds on .
(b) Now suppose the bound is known only on . Find the admissible that minimizes , and the value of the bound.
(c) Evaluate and comment.
Solution
(a) We have , so . The two parts of the bound are and . Hence .
(b) Admissibility requires , that is, . Since , the function is decreasing on . The best admissible choice is therefore , with
The smaller value from (a) is not available. At , the node lies outside the interval on which is known.
(c) . This is about times the bound at . Reducing below the admissible optimum shrinks the truncation part but lets the data part dominate. All three numbers are bounds under exact arithmetic, not observed errors.
Remaining scope
This note treats only:
- the first derivative;
- rules with exactly nodes and exactness on ;
- worst-case bounded data errors;
- exact arithmetic.
Several topics are not analyzed here:
- rounding in the abscissae or in the weighted sum;
- sharp error constants. The integral form of the Taylor remainder can improve the constant for the stencil , and the exercise on shows it cannot go below ; that refinement is not proved here;
- how the weights behave as nodes cluster or as grows;
- least-squares rules that use more samples than unknowns;
- statistical noise models;
- second and higher derivatives on uneven stencils.
These are natural next notes, and none of them is implied by the bounds proved above.