Motivation
The Lagrange formula answers an existence question: a unique polynomial of the prescribed degree matches distinct-node data. It leaves several practical questions open. If another sample arrives, must we rebuild the polynomial? Can we evaluate a high-degree interpolant without expanding its monomial coefficients? If the samples can be taken anywhere, which locations should we choose? These questions concern different parts of the numerical problem, so one formula should not be expected to answer all of them.
Newton form makes the effect of adding a node explicit. Barycentric form reorganizes the same polynomial into a convenient evaluation formula. Chebyshev nodes reduce a particular worst-case node product in the interpolation remainder. None of these changes the fact that uncertain samples can be amplified. We will therefore distinguish approximation of an unknown function, conditioning of the interpolation map, and arithmetic used to evaluate its result.
Definitions
Definition 5.1.1
(Divided differences and Newton form)
Let be distinct real nodes. For supplied data , define divided differences recursively by
These are finite data expressions; the notation does not presume that a differentiable function has been supplied. The Newton polynomial is
The product for is one. Nested evaluation starts with the last coefficient and repeatedly multiplies by before adding the next coefficient. It avoids a separate conversion to monomials. If the data arrive in node order, the existing coefficients are kept and only the new row of divided differences must be computed.
Definition 5.1.2
(Barycentric weights and the second barycentric formula)
Write and define barycentric weights
All weights are nonzero. Multiplying them all by the same nonzero constant does not change the second barycentric formula
At a node the definition is ; a program should return that supplied value directly. The apparent singularities belong to this representation, not to the polynomial itself.
There is a useful cost distinction. Building a full divided-difference table uses a triangular number of differences and divisions, hence a quadratic number of operations in the node count. Once its coefficients are available, Newton evaluation needs only a linear number of operations at each target. Computing general barycentric weights by their product definition is likewise quadratic preprocessing, followed by linear work per target. These counts describe arithmetic operations, not accuracy or bit complexity. Reusing precomputed weights is useful when many data vectors share the same nodes, but those weights must be recomputed or updated when the nodes change.
Definition 5.1.3
(Lebesgue constant and best-approximation error)
For a compact interval containing the nodes, let denote interpolation of a continuous function and put
The Lagrange functions are determined by the nodes. The Lebesgue constant is the operator norm for the uniform data norm: it measures the largest absolute sample-error amplification on . It is not a bound on floating-point evaluation error. The quantity asks how well the best polynomial of degree at most can do; that best polynomial need not pass through the samples.
Concept lensStructural
Representation, operator, and approximation
Newton and barycentric forms represent the same linear interpolation operator. The Lebesgue constant measures that operator's sensitivity. Best approximation asks how close any degree- polynomial can come to the unknown function. The inequality with in the theorem below connects these two questions without identifying them. This separation prevents an efficient formula from being mistaken for an accuracy theorem.
Theorem/Proposition
Theorem 5.1.4
(Newton coefficients and barycentric identity)
The Newton polynomial interpolates the data. Its coefficient of the product is the divided difference on the first nodes. The second barycentric formula equals that unique polynomial wherever it is written above, and its exact denominator is , hence is nonzero at every nonnode.
For continuous on ,
If samples have errors bounded by , add at most to this approximation bound.
Theorem 5.1.5
(Chebyshev nodes minimize the monic node product)
For an integer , define by . It is a degree- polynomial with leading coefficient (also valid for ). Among real monic degree- polynomials on , the smallest possible uniform norm is , attained by . Its roots are
Consequently these nodes minimize . On the corresponding value is . If and , interpolation at these nodes has error at most
This last statement optimizes a derivative-based bound with fixed. It neither bounds as increases nor establishes that this bound tends to zero for every smooth function. Minimizing a node product and minimizing the Lebesgue constant are also different optimization problems.
Here is the number of nodes: in the earlier notation , so the interpolant has degree at most and may be denoted . The degree- object being minimized is its node product, not the interpolant.
The hypotheses should guide how an estimate is used. If a function is only known to have three continuous derivatives, a bound requiring its eleventh derivative is unavailable, regardless of how many samples we collect. Even an infinitely differentiable function can have rapidly growing derivative maxima. Conversely, a very pessimistic derivative bound does not prove that the observed interpolant is poor: a sufficient bound may fail to certify an accurate calculation. An accuracy report should identify whether it contains a proved upper bound, an observed comparison, or a heuristic expectation.
Proof sketch or proof idea
Why divided differences are the Newton coefficients
Proof
(Leading coefficients obey the divided-difference recursion)
For nodes , the coefficient of in their Lagrange interpolant is
This expression obeys the divided-difference recursion. To check an interior coefficient , subtract the expression on from the one on and divide by . Factoring the common product leaves
The endpoint coefficients satisfy the same identity directly. Starting from , induction identifies . The interpolants on the first and first nodes differ by a polynomial vanishing at . It is therefore a constant times their degree- node product. Its leading coefficient is , because the earlier interpolant has smaller degree. Inducting gives Newton form. This also proves that the divided difference is symmetric in its node-value pairs, although the triangular table uses one chosen order.
Why the rational-looking formula is a polynomial
Proof
(Dividing two Lagrange identities by the node polynomial)
The identity gives the numerator formula after division by . Interpolation reproduces the constant one, so . Dividing this equality by gives the denominator . Taking the quotient proves the identity without assuming a numerically computed denominator has the same behavior. Near nodes, exact numerator and denominator both grow; returning the node value directly removes the need to form the formal infinite terms.
Proof
(Interpolation reproduces every polynomial of degree at most )
For any , interpolation reproduces . Therefore
The norm of the second term is at most . The triangle inequality and then the infimum over prove the approximation estimate. Applying the same absolute-weight bound to perturbed samples proves the data term. The statement makes no independence or random-sign assumption about those perturbations.
Counterexample mode
Interpolation is not best approximation
A tempting claim is that the interpolant is itself the best uniform approximation from , so the factor is unnecessary. Take on , and nodes . Then and , attained at . A line with would need , impossible since ; the constant has error exactly , so . With , the theorem's bound holds with equality. The nodes instead interpolate by the constant and attain : the gap depends on the nodes.
Why the Chebyshev product is extremal
Proof
(Alternation forces too many roots)
The cosine addition identity gives , starting with . This proves polynomial degree and leading coefficient by induction. On , , and at its values alternate between and .
Suppose a monic polynomial had norm strictly below . The polynomial has degree at most because leading terms cancel. At the successive extrema its signs alternate, opposite to those of , since . The intermediate value theorem produces a distinct root in each adjacent interval: roots in total. This contradicts the degree bound. Thus no smaller norm is possible, and attains the minimum. Its displayed roots are distinct, so it is precisely their monic node product. An affine change of variable multiplies a monic degree- product by . The earlier interpolation remainder then gives the stated error bound.
Proof X-ray
What the alternation argument actually optimizes
Three ingredients carry the argument, each at a definite place. Monicity is used once: it makes the leading terms of and cancel, so has degree at most . Equioscillation supplies the points , where . The strict hypothesis then makes nonzero with sign . With only , some could vanish and the sign count would need a separate argument.
The intermediate value theorem then places one root in each of the disjoint open intervals between consecutive . A polynomial of degree at most with distinct roots is identically zero, so . Its norm is exactly , contradicting the strict inequality: this is how the argument closes. The transfer to uses only an affine change of variable and the derivative remainder. The proof therefore optimizes the node product in the uniform norm and nothing more: it says nothing about Lebesgue constants or floating-point evaluation.
Worked examples
Worked example 5.1.6
(Appending one sample without restarting)
At nodes , data give divided difference and . Append . The new first difference is and the second difference is . Thus
Only one new Newton term is needed. At , nested evaluation gives . An incremental formula saves work; it does not remove sensitivity when nodes are clustered or data are uncertain.
Worked example 5.1.7
(Barycentric weights and cancellation)
For nodes , weights are ; rescale them to if desired. At , the unscaled denominator is , and with data the numerator is . Their quotient is . The corresponding Lagrange weights are , so data errors bounded by can cause an error . A convenient evaluation formula has not changed this conditioning.
Worked example 5.1.8
(Three nodes, two node products)
The roots of are . Their product is , with norm on . Equally spaced nodes instead give , whose extrema at have magnitude . If , the Chebyshev error bound is , while the equally spaced product gives about . This compares guaranteed bounds under the same derivative assumption; a particular quadratic has zero error with either node set.
Common mistakes
Counterexample mode
Increasing equally spaced degree can worsen approximation
For on , interpolate at equally spaced nodes. At , degree four gives approximately , whereas degree ten gives approximately ; the true value is approximately . The absolute error has increased from about to . This explicit finite comparison illustrates the Runge phenomenon; it is not itself a proof of asymptotic divergence. It already disproves the unconditional claim that increasing degree improves every interpolation value.
Three further errors concern how the formulas are used rather than what they state.
Common mistake
(Treating “barycentric” as a stability certificate)
The name of a formula is not an error analysis. Computing weights by long products can overflow or underflow, near-node evaluation needs care, and rounded nodes define a perturbed problem. Node design addresses approximation and conditioning; a stable implementation must address arithmetic too.
Common mistake
(Rescaling individual barycentric weights)
Only a common factor may be removed. For nodes and data , the scaled weights give at , the correct value. Changing just the last weight to gives . The altered quotient is in general a rational function, not the interpolating polynomial.
Common mistake
(Carrying interval bounds into extrapolation)
The Lebesgue constant and the remainder bounds are maxima over an interval containing the nodes. They say nothing beyond it. For nodes , the absolute Lagrange weights sum to one everywhere on , but to two at ; extrapolation needs its own analysis.
Summary
Divided differences support incremental Newton construction. Barycentric evaluation follows from exact Lagrange identities and requires explicit node handling. The Lebesgue constant controls deterministic sample uncertainty and relates interpolation to best polynomial approximation. Chebyshev roots minimize the monic node product and hence a fixed-degree derivative-based error bound. Degree growth, data conditioning, and floating-point stability still need their own arguments.
Exercises
Quick check
(Use nodes and data . Construct the divided-difference table, write Newton form, and evaluate at . Explain what happens if these data come from a quadratic.)
Two first differences, then one second difference.
Solution · Answer
The first differences are and . The second difference is . Hence , and . A quadratic producing these samples equals this interpolant everywhere by polynomial uniqueness; no unknown derivative remainder remains for that quadratic.
Quick check
(Find barycentric weights for nodes . At , compute the interpolated value and sharp absolute data-error amplification. What amplification occurs at ?)
Evaluate the two Lagrange functions at each target.
Solution · Answer
The weights are , up to common scaling. At zero the Lagrange coefficients are , so the value is the average and amplification is one. At two the coefficients are , so amplification is two. Errors attain there. Extrapolation has already increased sensitivity in this linear example.
Quick check
(Find the two Chebyshev roots on and their monic node product. If there, find the uniform interpolation bound from the theorem. Compare with endpoint nodes .)
Map the roots of affinely onto .
Solution · Answer
Mapping to gives . The product is , of norm . The remainder bound is . Endpoint nodes give product , of norm one and bound four. These are upper bounds, not assertions that every function attains them.
Quick check
(Suppose , , and each sample has absolute error at most . Give a combined uniform bound. Does using another exact representation of the same polynomial improve this bound?)
Use the combined inequality from the first theorem.
Solution · Answer
The approximation term is and the sample term is , totaling . Another exact representation leaves the operator and its norm unchanged. It can change computational cost and arithmetic error, which this bound has not included.