Motivation
Suppose a function can be evaluated only at selected points. Interpolation replaces it by a polynomial agreeing with those values; quadrature replaces an integral by a weighted sum of values. The two tasks are connected: integrating an interpolating polynomial produces a quadrature formula. This connection explains the weights and the degrees of exactness, but does not by itself guarantee that a high-degree polynomial is a good approximation between its nodes.
Three kinds of error should be kept distinct. Interpolation error compares the exact function with the exact polynomial through exact data. Quadrature truncation error compares an exact integral with an exact weighted sum. Floating-point error and errors in measured data can affect either computation even if the analytical error is small. The bounds below concern exact arithmetic and assume the stated derivatives exist and are bounded; they do not certify a program's rounding error.
Definitions
Definition 7.1.1
(Interpolating polynomial and Lagrange basis)
Given distinct nodes and values , the interpolating polynomial is the polynomial of degree at most satisfying . Define
Each equals one when and zero otherwise. Distinctness of the nodes makes every denominator nonzero. If two degree-at-most- polynomials match the same data, their difference has distinct roots and is identically zero; existence and uniqueness follow.
Definition 7.1.2
(Divided differences and Newton form)
For distinct nodes, let and recursively set
The same interpolant has the Newton representation
The coefficients depend on the ordering of the nodes, but the final polynomial does not. Newton form is convenient when a new node arrives: the earlier terms are retained and one new divided-difference term is appended.
Aitken–Neville interpolation computes a single value without first displaying the polynomial. Set and, for ,
Both lower-order interpolants equal at each shared node , and the two weights there sum to one; at each remaining endpoint the appropriate coefficient vanishes. Inductively has degree at most , so it interpolates the data from through and uniqueness proves the recurrence. When only one target value is needed, the triangular array can be useful; evaluating many targets may favor a reusable representation.
Computing a Neville table
The recurrence is most useful when we can turn it into a reliable sequence of updates. Fix the target and write . Start with the data . Then calculate all entries with , followed by those with , and so on, until is reached. Each new entry combines two results from the preceding level. There are updates, so one target costs arithmetic operations; the count excludes obtaining the original data. A new target requires a new table.
Theorem 7.1.3
(In-place Neville update)
Let the nodes be pairwise distinct and let initially hold . For each , update in increasing order by
Then after level every with equals , so the final is , and only storage locations are used.
Proof
(Induction over the levels)
Before level we have . Suppose that before level we have for . Earlier updates in this level changed only entries with index less than , so just before is updated, and . The recurrence therefore places in . Induction over both indices proves that the final is the required value. The argument assumes exact arithmetic and pairwise distinct nodes, so every denominator is nonzero; it does not prove a floating-point error bound.
Worked example 7.1.4
(A complete table at one target)
Use nodes and values , and evaluate at . The first level gives
The next level gives . Indeed the data lie on , whose value at is . In the one-array implementation, the successive active entries are , , and . Updating the first level from right to left would overwrite the old by before it is used for : it would give and ultimately , a different and incorrect answer.
What the table does and does not measure
The difference compares two interpolants using different data sets. It can be a useful warning that the displayed value changed when a node was added, but it is not a guaranteed error bound for the unknown function. For example, let at every node and take . Every table entry is zero, while away from the nodes. A certified function error needs further information such as the derivative bound in the remainder theorem below.
Even exact evaluation can magnify errors in the input data. If , linearity and the Lagrange formula imply
For the worked nodes at the three weights are , so the factor is ; perturbations of equal magnitude with the signs of these weights attain that bound. The target lies inside the full node range, yet one weight is negative. This data-sensitivity statement concerns the exact interpolant; rounding in the table is an additional issue. In particular, a small change between levels or a target inside the node range does not by itself certify accuracy.
Quick check
(For nodes with values , compute the Neville table at . What changes if every datum is increased by ?)
Compute the two first-level entries, then combine them.
Solution · Answer
The first level is , ; then . The weights at are and sum to , so adding to every datum increases the result by exactly in exact arithmetic. This common shift is not the worst-case perturbation: independent errors bounded by can change the value by as much as .
Quadrature exactness
Definition 7.1.5
(Degree of exactness)
A quadrature rule on has degree of exactness if it integrates every polynomial of degree at most exactly and fails for at least one polynomial of degree . Exactness for polynomials is an algebraic property. A bound for a general function additionally requires regularity and an estimate of the relevant derivative.
Theorem/Proposition
Theorem 7.1.6
(Interpolation remainder)
Let be distinct points in , and let . For every that is not a node, some in the interior of the smallest interval containing and the nodes satisfies
At a node the error is zero. Consequently, if on , its absolute value is at most .
Theorem 7.1.7
(Composite trapezoidal and Simpson rules)
Let , , and . The composite trapezoidal rule is
If and , then
For even , composite Simpson's rule is
If and , then
A rule's order refers to behavior as the mesh is refined while the interval and derivative bound remain fixed. Halving reduces these upper bounds by factors four and sixteen, respectively; it need not reduce a particular actual error by exactly those factors. Symmetry gives Simpson's rule exactness through degree three, even though it is obtained by integrating a quadratic interpolant.
Theorem 7.1.8
(Two-point Gauss–Legendre rule)
On , the rule
is exact for every polynomial of degree at most three. If , some satisfies
For , substitute and multiply the rule by . If , its error is for some .
Proof sketch or proof idea
Proof
(Interpolation error by repeated Rolle's theorem)
Fix distinct from all nodes and put . Choose and define . This function has the interpolation nodes and as distinct zeros. Repeated Rolle's theorem gives a point in their convex hull at which . Since and , the stated remainder follows. The point can depend on the target ; it is generally not one fixed point for all targets.
For Newton form, first use the Neville recurrence inductively: the coefficient of in is the difference of the leading coefficients of and divided by , hence equals . Subtracting the interpolant through from leaves a degree-at-most- polynomial with those roots, so it is this leading coefficient times . Induction gives Newton form and uniqueness identifies it with the Lagrange interpolant.
Proof
(Integrating local errors)
On one interval , integrate the line interpolating at its endpoints to obtain the trapezoidal rule. The interpolation remainder and give the local bound . Sum intervals of width to obtain the composite bound. No cancellation between local errors is assumed.
For Simpson's rule on one panel with midpoint , the quadratic interpolant integrates to . To prove the fourth-derivative error, use instead the cubic Hermite polynomial matching at and also matching at . The rule applied to equals the rule applied to because their three sampled values agree. Since the rule integrates the cubic exactly, the error is . Generalized Rolle's theorem gives
The product is nonpositive inside the panel and has integral . The factor has a fixed nonpositive sign. The minimum and maximum of continuous bound the quotient pointwise wherever the denominator is nonzero. Integrating these bounds against the nonnegative weight given by minus that factor, then applying the intermediate value theorem, yields a single for the integrated error; no continuity or measurability of the chosen is assumed:
There are panels of width , so summing absolute local bounds gives . The fourth derivative is needed for this estimate; a function with fewer derivatives may still be approximated but this formula gives no certificate.
Proof X-ray
Why the midpoint is doubled
The quadratic interpolant at has remainder , whose kernel changes sign at ; that supports only an estimate with the third derivative. Adding the condition turns the kernel into , which keeps one sign on the panel. Two facts make this legitimate. The added cubic term is a multiple of , which is odd about and integrates to zero, so the rule gives the same number for and for . And a one-signed kernel is exactly what lets the minimum and maximum of pin the integrated error to a single value . Without the doubled root the sign change blocks that step, and the argument would give only a weaker estimate involving .
Proof
(Nodes and remainder of the two-point rule)
For the two-point Gaussian rule, impose the symmetric ansatz of equal weights at nodes . Odd monomials then integrate and sum to zero. Matching the constant and quadratic moments gives and , hence weights one and nodes , so all degrees through three are exact. For the error, let be the cubic matching and at both nodes. The Hermite remainder has factor . The rule evaluates and equally, and exactness integrates exactly. Since the factor integrates to , the same minimum–maximum argument gives error . For this error is , proving that the degree of exactness is exactly three. Moving the nodes and weights gives more exactness per evaluation than fixing equally spaced nodes, but it does not eliminate approximation or rounding errors.
Worked examples
Worked example 7.1.9
(One interpolant in three forms)
For nodes and values , the divided differences are , , and . Newton form gives
At this gives . Neville's first row at this target is and ; the recurrence then gives . Lagrange's formula produces the same polynomial by uniqueness. The value uses extrapolation from nodes to , even though the final target lies inside the full node range.
Worked example 7.1.10
(A certified Simpson estimate)
Take on and , so . Simpson's rule gives
Since , the error is at most . The exact integral is , so the actual error is about ; the estimate is a bound rather than an exact prediction. Here Simpson's value is larger than the integral, consistent with the negative sign of the one-panel error .
Worked example 7.1.11
(Two Gauss nodes on a new interval)
For on , the change of variables gives
The exact integral is , so . This agrees with the remainder applied to , whose fourth derivative is : . The rule integrates cubics exactly but not every quartic.
Even a unique interpolant can behave poorly between nodes. For the Runge function on , high-degree interpolation at equally spaced nodes can develop large oscillations near the endpoints. Changing the nodes or using piecewise low-degree interpolation can improve behavior. The remainder bound exposes one factor, , but an increasing derivative bound can also make the estimate uninformative; a small nodal error alone does not control the whole interval.
Common mistakes
Common mistake
(Exact at nodes does not mean accurate between them)
Every interpolating polynomial has zero residual at the data nodes, regardless of its error between them. Check smoothness, node placement and the magnitude of the remainder; for computed data also assess sensitivity to perturbations. A bound involving an unknown or enormous derivative is not an effective numerical certificate.
Common mistake
(Confusing exactness with an error rate)
Simpson's rule is exact for cubics and has a fourth-derivative error bound under regularity. Exactness alone does not imply the displayed constant for an arbitrary function. Likewise, a Gauss rule's degree of exactness concerns polynomials, not a promise of exact integration for all smooth functions.
Summary
Lagrange, Newton and Neville describe the same unique interpolant. The remainder theorem connects approximation error to derivatives and node geometry. Integrating local interpolants yields Newton–Cotes rules; Gaussian quadrature selects nodes to increase polynomial exactness. Error estimates require the stated regularity, and neither truncation bounds nor exactness alone quantify floating-point error.
Exercises
Quick check
(Interpolate the data in Newton form and evaluate the polynomial at .)
Compute the divided differences first.
Solution · Answer
The first divided differences are and , so . Thus , and .
Quick check
(For on , find an upper bound for the composite trapezoidal error with . State whether the trapezoidal approximation lies above or below the integral.)
Bound and use concavity.
Solution · Answer
Here and , giving . Because is concave on this interval, its chords lie below its graph; hence .
Quick check
(Use the two-point Gauss rule on for and compare with the exact integral.)
Evaluate at .
Solution · Answer
The rule gives , whereas . The error agrees with .
Quick check
(A Simpson calculation uses on and . Give a certified absolute error bound. What bound follows after doubling ?)
Use in the Simpson bound.
Solution · Answer
With , the bound is . Doubling halves and divides the bound by , giving . The actual error need not change by exactly this factor.
Reusing nodes: trapezoid, midpoint, and Simpson
The midpoint approximation on the coarse panels is ; and are the trapezoid and Simpson quantities defined above.
Fix an integer , an interval with , and . Halving the step to produces the grid for . Even indices give the old nodes . Odd indices give the midpoints . If we separate these two kinds of node in the definition of , we get
Composite Simpson on subintervals of width multiplies everything by . It gives weight to the endpoints, to the odd nodes, and to the interior even nodes:
Substituting yields .
These are algebraic identities. They hold for every function that can be evaluated at the grid nodes. They make no claim about convergence or smoothness.
Computation. Store the values already used by . Refinement then needs only the new midpoint values to form . After that, and follow without repeating any evaluation. In floating-point arithmetic the identities hold only up to rounding error, which is a separate question.
Example. Take on with . Then , , , and .
Quick check
(Take on with . Verify that , , , and .)
Evaluate at , and first.
Solution · Answer
The sampled values are , and . Substitution gives and ; the identities then yield and .
Counterexample mode
Agreeing estimates do not certify accuracy
Agreement between two estimates does not certify accuracy. Let on . This function vanishes at , so . Yet , as the substitution shows. The sampled values cannot detect what happens between the nodes. One example also cannot demonstrate convergence. Any claim that reduces the error requires regularity assumptions on ; the identity alone does not provide it.
Newton–Cotes: where the weights come from
The trapezoidal and Simpson rules are members of a larger family. A Newton–Cotes rule integrates the interpolating polynomial through equally spaced nodes. In a closed rule the nodes include both endpoints; in an open rule they lie strictly inside the interval. The latter is useful when endpoint values are unavailable, but this alone gives no guarantee of accuracy near a singular endpoint.
For and an integer , in a closed rule put and for . If are the Lagrange basis polynomials for these nodes, define
Indeed . Therefore it integrates every polynomial of degree at most exactly, because its interpolant is itself. The open rule is constructed in the same way using interior nodes , . The midpoint rule is the open case ; the trapezoid and one-panel Simpson rules are closed cases and .
Why is Simpson also exact for cubics? Both node sets are symmetric about . Reflecting the nodes swaps their Lagrange basis polynomials, so . If is even, the centered monomial is odd: its integral and its quadrature sum are both zero. Every polynomial of degree at most is a multiple of this monomial plus a polynomial of degree at most . Thus either family has at least degree when is even. This symmetry argument concerns exact arithmetic; it is not an error bound for an arbitrary function.
Worked example 7.1.12
(Deriving and using the closed three-eighths rule)
Take four nodes . Integrating their Lagrange bases gives weights . For instance,
The reflected endpoint has the same weight. The two interior weights are equal by symmetry; since the weights sum to , each is . The change of variables with and yields
It is exact through degree three by interpolation. For on , however, it gives , while the integral is ; the signed error . Hence its degree of exactness is exactly three. The example also shows why exactness for low-degree polynomials is not exactness for every smooth function.
Quick check
(On , construct the open rule using the two nodes . Apply it to and compare the result with the integral.)
Integrate each Lagrange basis polynomial over .
Solution · Answer
The basis polynomials are and . Each integrates to , so . The integral is ; the signed error is . The rule is exact for constants and linear functions, but this example shows it is not exact for every quadratic.