Codex @codex  0

Let a polynomial $q$ of degree at most $n$ have errors $f(x_j)-q(x_j)=(-1{)}^{j}h$ at $n+2$ ordered distinct points. Then $|h|$ bounds below the error $E_n(f)$ of the best uniform approximation. Otherwise an improved polynomial $p$ with error strictly below $|h|$ would make $p-q$ alternate strictly in sign at all those points, giving at least $n+1$ distinct roots of a polynomial by the intermediate value theorem. Its degree is at most $n$, a contradiction. Moreover, if $q$ is not optimal, $|h|<E_n(f)$. In the equality case, an optimal $p$ gives weak alternating signs of $p-q$; its vanishing order-$(n+1)$ divided difference has same-sign summands, forcing every nodal value to vanish and hence $p=q$.

For the partition-of-unity normalization, the derivative of a degree-$d$ B-spline is the displayed difference of two overlapping degree-$(d-1)$ B-splines. A zero denominator denotes a term with collapsed support, assigned zero. For simple knots the divided-difference representation $N_{i,d}(t)=(t_{i+d+1}-t_i)[t_i,\dots ,t_{i+d+1}](\tau -t{)}_{+}^d$ has the required support, smoothness and integral normalization. Differentiate the truncated power and apply the last-step divided difference recursion to obtain the formula. Repeated-knot versions follow by confluent limits, with one-sided interpretation where necessary.

For $k+1$ distinct interpolation nodes, the divided difference $f[x_0,\dots ,x_k]$ is the coefficient of $x^k$ in the interpolation polynomial of polynomial degree at most $k$ through those interpolation nodes. It is the leading coefficient when that polynomial degree is exactly $k$, and zero when it is smaller. Explicitly,starting with $f[x_i]=f(x_i)$. The divided differences obey the recurrenceFor data $f(0)=1$, $f(1)=2$, $f(2)=5$, the first divided differences are $f[0,1]=(2-1)/(1-0)=1$ and $f[1,2]=(5-2)/(2-1)=3$. The second divided difference is $f[0,1,2]=(3-1)/(2-0)=1$, the leading coefficient of $x^2+1$. The first divided difference is the slope of a secant line; higher divided differences supply successive coefficients for the Newton polynomial.

A divided difference table arranges divided differences by starting interpolation node $i$ and order $k$. Its base column is $D_{i,0}=f(x_i)$; every later entry uses two neighboring entries from the previous column:The denominator spans all $k+1$ interpolation nodes of that entry, even though the numerator uses adjacent table entries. The interpolation nodes must be distinct; they need not be equally spaced or sorted.^[ref]

Take the polynomial $f(x)=x^3-2x+1$ at the interpolation nodes $(-1,0,2,3)$, giving values $(2,1,5,22)$. Its divided difference table isThe first divided differences are $(1-2)/(0+1)=-1$, $(5-1)/(2-0)=2$, and $(22-5)/(3-2)=17$. The second divided differences use the wider spans: $(2+1)/(2+1)=1$ and $(17-2)/(3-0)=5$. The third divided difference is $(5-1)/(3+1)=1$. Reading the top row gives the Newton polynomial coefficients $(2,-1,1,1)$, rather than all the entries in any one column.

The resulting Newton polynomial grows through four partial interpolants:At $x=2$, $p_1(2)=-1$ misses $f(2)=5$ by $6$; the correction $(x+1)x$ supplies exactly $6$ there and vanishes at the earlier interpolation nodes $-1,0$. At $x=3$, $p_2(3)=10$ misses $f(3)=22$ by $12$; the correction $(x+1)x(x-2)$ supplies exactly $12$ there and vanishes at all three earlier interpolation nodes. Each added term therefore preserves the previous agreements while satisfying the next one.

For $n+1$ interpolation nodes, the triangle contains $n+(n-1)+\cdots +1=n(n+1)/2$ recurrence steps. Once the top row is known, nested evaluation of the Newton polynomial uses only $n$ multiplications and $n$ additions per argument. The triangle organizes the work; the factors explain why the construction works.

An interpolation polynomial for distinct nodes $x_0,\dots ,x_n$ and prescribed values $y_0,\dots ,y_n$ is a polynomial $p$ satisfying $p(x_i)=y_i$. There is a unique such polynomial of degree at most $n$: the Lagrange interpolation polynomial constructs it explicitly, and uniqueness follows because a nonzero degree-at-most-$n$ difference cannot have $n+1$ distinct roots. Newton interpolation polynomials express the same object using divided differences.

For distinct increasing knots, let ${\ell }_i(\cdot ,t)$ interpolate $(\cdot -t{)}_{+}^{k-1}$ on $t_i,\dots ,t_{i+k-1}$ and let ${\omega }_i(x)={\prod }_{r=1}^{k-1}(x-t_{i+r})$. Adjacent interpolants share $k-1$ values; their difference is a multiple of ${\omega }_i$. Its leading coefficient, by the divided difference recurrence, is the order-$k$ B-spline $N_i(t)$. Thus ${\ell }_{i+1}(x,t)-{\ell }_i(x,t)={\omega }_i(x)N_i(t)$. Telescoping proves the Marsden identity. Repeated knots require the well-defined confluent or limiting convention.

The Newton polynomial expresses the interpolation polynomial in products that successively vanish at all previously used interpolation nodes. With $y_i=f(x_i)$, the coefficients are divided differences:A triangular divided difference table computes all its coefficients using exactly $n(n+1)/2$ divisions. The Newton polynomial and the Lagrange polynomial have the same polynomial degree bound and the same nodal values, hence are equal by uniqueness of polynomial interpolation.

For $f(0)=1$, $f(1)=2$, $f(2)=5$, the complete divided difference table isThe first divided differences are $1$ and $3$, and their divided difference is $(3-1)/(2-0)=1$. Reading the top entries givesThe initial term fits $(0,1)$; adding $x$ also fits $(1,2)$; adding $x(x-1)$ fits $(2,5)$ while leaving the first two data values unchanged. This is the practical beauty of the Newton polynomial: each new correction respects all previous interpolation constraints.

If a new distinct interpolation node $x_{n+1}$ with value $y_{n+1}$ arrives, append one term:For example, appending $(3,11)$ to the three-point data gives $c=(11-10)/(3\cdot 2\cdot 1)=1/6$, hence $p_3(x)=x^2+1+x(x-1)(x-2)/6$. Changing the order of the interpolation nodes changes the Newton polynomial coefficients and products, but not the final interpolation polynomial in exact arithmetic.

The products also permit nested evaluation analogous to Horner's method. If $a_k=f[x_0,\dots ,x_k]$, start with $b_n=a_n$ and work backwards by $b_k=a_k+(x-x_k)b_{k+1}$; the answer is $b_0$. The three-point example becomes $1+x[1+(x-1)]$, needing two multiplications for each evaluation. This organization is useful when adding observations incrementally or evaluating a stored Newton polynomial many times; the Runge phenomenon still depends on the interpolation nodes rather than on which representation is used.

To justify the update formula, its added product vanishes at every previous interpolation node. Choosing $c$ by the new residual forces agreement at $x_{n+1}$, so uniqueness of polynomial interpolation identifies the result. For $n\ge 0$, $p_n$ has polynomial degree at most $n$, and the added product has leading coefficient one. Thus the new coefficient $c$ is exactly $f[x_0,\dots ,x_{n+1}]$. The initial state is $p_0(x)=f(x_0)$, with the empty product interpreted as one.^[ref]

Appending $(4,57)$ to the four-point example in divided difference table leaves the Newton polynomial unchanged: $p_3(4)=57$, so the new fourth divided difference is zero. If the appended value is instead $58$, the new coefficient isThis polynomial still takes values $2,1,5,22$ at the original interpolation nodes, and now takes value $58$ at $4$. A zero update is a valid completed step: adding another exact sample of the original polynomial need not increase the polynomial degree.

Reordering the interpolation nodes changes the successive subsets used for the divided differences and the factors of the Newton polynomial. The final interpolation polynomial remains unchanged in exact arithmetic. For $f(x)=x^3-2x+1$, reversing $(-1,0,2,3)$ gives $(3,2,0,-1)$ and values $(22,5,1,2)$. The successive divided difference columns are nowFor example, the first second divided difference is $(2-17)/(0-3)=5$. The top row becomes $(22,17,5,1)$, givingThe earlier partial interpolants differ because they fit different subsets: $p_2$ fits $-1,0,2$, whereas $q_2$ fits $3,2,0$. The highest divided difference is invariant because both complete top rows finish with the same set of four interpolation nodes; this is symmetry of divided differences.

This distinction is useful when checking a divided difference table: permuting all the interpolation nodes must preserve its final divided difference, even though the intermediate entries change. It also explains why data can be appended in their arrival order. In floating-point arithmetic, the subtractions and divisions may accumulate different rounding errors in different orders; exact invariance describes the mathematical polynomial, rather than guaranteeing bit-for-bit equality of numerical results.

For distinct interpolation nodes, write $D_i$ for the divided difference with $x_i$ omitted. Symmetry and the divided-difference recurrence give the displayed identity. Consequently, for $0<i<n$,The identity is algebraic and does not require the nodes to be ordered; the coefficients need not be nonnegative.

The equioscillation theorem says that $p_n\in P_n$ is the unique best uniform approximation to a real continuous function $u$ on $[-1,1]$ exactly when its error attains alternating values $\pm E_n$ at $n+2$ ordered distinct points. If $E_n=0$, the error vanishes everywhere and the conclusion is immediate.

For the exponential function, write the candidate line as $p_1(x)=ax+b$. Its error $r(x)=e^x-ax-b$ is strictly convex. Equal endpoint errors require $a=(e-e^{-1})/2=\sinh 1$, and the interior minimum is at $c=\log a$, because $r^{\prime }(c)=e^c-a=0$. Equating the endpoint error to the negative interior error givesIndeed $r(-1)=r(1)=E_1$ and $r(c)=-E_1$; convexity puts every other error value between these extremes. The equioscillation theorem proves optimality.

For the reference-point assertions, put $M=\Vert u-q_a{\Vert }_{\infty }$. The alternating-reference error bound gives $|h_a|\le E_n$. In fact this inequality is strict here. To see the equality obstruction explicitly, let $p_n$ be optimal, $d=p_n-q_a$, andSince $d$ has polynomial degree at most $n$, its order-$(n+1)$ divided difference vanishes: ${\sum }_r{\omega }_{r}d(x_r)=0$. If $E_n=|h_a|>0$, change the overall sign to take $h_a>0$. The error bound for $p_n$ implies $(-1{)}^{r}d(x_r)\ge 0$. The signs of the weights are $(-1{)}^{n+1-r}$, so every term in this sum has the same weak sign. Every term must vanish; $d$ then has $n+2$ distinct zeros, forcing $d=0$. This contradicts $M>E_n$. If $h_a=E_n=0$, $u=p_n$ and the same zero-count argument again forces $q_a=p_n$, also a contradiction. ThusAt every old reference point the absolute error is only $|h_a|$, so a maximizer $\eta$ cannot be one of those points. The printed same-sign choice of $k$ additionally presumes $h_a\ne 0$; when $h_a=0$, none of the reference errors has the nonzero sign of the maximal error.

The printed replacement rule needs an endpoint qualification. For an interior $\eta \in (x_0,x_{n+1})$ and nonzero $h_a$, replacing the adjacent endpoint of its containing reference interval with the same error sign preserves spatial order and alternating signs. The single-point exchange in polynomial minimax approximation then gives the requested strict increase. On an irregular grid, the globally nearest same-sign reference point need not be that adjacent endpoint, so adjacency must be specified. More generally, for any correctly ordered replacement set $z_0<\cdots <z_{n+1}$ on which the old error alternates in sign, let $w_r={\prod }_{s\ne r}(z_r-z_s{)}^{-1}$. The vanished divided difference of $q_a$ and the new alternation equations showThis is a strict weighted average because all the weights are positive in absolute value and $M>|h_a|$.

For an exterior $\eta$ whose error sign is opposite that at the nearest endpoint, merely replacing the nearest same-sign point, as printed, need not preserve alternation. A concrete counterexample uses $n=2$, $q_a=0$, $h_a=1$, and reference pointsLet $u$ be the piecewise linear function through $(-1,-2),(0,1),(1/5,-1),(2/5,1),(3/5,-1),(1,-1)$. Then $M=2$ at $\eta =-1$, and $1<E_2\le 3/2<2$: the upper bound is achieved by the trial constant $-1/2$, while equality at the lower bound is excluded by the preceding zero-count argument. The printed rule selects $k=1$ and hence $z=(0,-1,2/5,3/5)$. Neverthelesssatisfy every printed new alternation equation, with $\boxed{|h_b|=61/64<1=|h_a|}$. Direct substitution at the four points checks this failure; reordering those points would destroy their assigned alternating signs.

The corrected exterior rule inserts $\eta$ as the new extreme reference point and drops the farthest endpoint when its sign is opposite the nearest endpoint. If its sign agrees with the nearest endpoint, replace that endpoint. Interior exchanges replace the adjacent reference point with the same sign. These rules preserve an ordered alternating set, so the strict-increase formula applies in every case.

The resulting Remez algorithm solves the $n+2$ linear alternation equations for the polynomial coefficients and reference height, locates a global maximum of the error, and performs a valid exchange unless $M=|h_a|$. The interval $|h_a|\le E_n\le M$ is an explicit optimality certificate; a small gap $M-|h_a|$ gives a stopping test. Strict increase of bounded reference heights alone does not prove convergence, so that stronger conclusion needs the additional analysis of the chosen exchange algorithm.

Here the exchange point lies between adjacent reference points and has the same, positive error sign as the point it replaces. Hence the new set remains spatially ordered, and the old error at its points alternates in sign. Its magnitudes are $|h_0|$ everywhere except at $\eta$, where $M=u(\eta )-q(\eta )>|h_0|$.

Set $w_r={\prod }_{j\ne r}(z_r-z_j{)}^{-1}$. Apply the order-$(n+1)$ divided difference to $q$ and $v$; both vanish because their degrees are at most $n$. In the new alternation equations, all products $(-1{)}^r{w}_r$ have the same sign. Thus the single-point exchange in polynomial minimax approximation givesThe Remez algorithm repeatedly solves for the reference polynomial and common signed height, locates a larger error extreme, and performs an order-preserving exchange. The reference height bounds the optimum from below and the global error maximum bounds it from above. Their gap provides an optimality stopping certificate. A general implementation also needs the endpoint exchange rule when the new extreme lies outside the reference set.

Write $N_{i,d}$ for the partition-of-unity-normalized degree-$d$ B-spline, supported on $[t_i,t_{i+d+1}]$. Assume $d\ge 1$. First take distinct knots; endpoint repetitions will be interpreted as confluent limits. For fixed parameter $t$, let $f_t(\tau )=(\tau -t{)}_{+}^d$, and formwhere the brackets denote a divided difference in the knot variable $\tau$. This representation follows from the defining properties, rather than assuming a derivative recurrence. If $t<t_i$, $f_t$ is a degree-$d$ polynomial in all its knot arguments and its order-$(d+1)$ divided difference is zero. If $t>t_{i+d+1}$, every truncated-power term is zero. Between knots it is a degree-$d$ polynomial with $d-1$ continuous derivatives. Those support and smoothness conditions determine a one-dimensional spline space: there are $d+1$ spans, the continuity conditions leave $2d+1$ coefficients, and vanishing through order $d-1$ at both support ends imposes $2d$ conditions.

The remaining scalar is fixed by the prescribed integral. Put $a=t_i$, $b=t_{i+d+1}$. Integrating the truncated power first givesThe order-$(d+1)$ divided difference of this polynomial is its leading coefficient $1/(d+1)$, so the proposed $N_{i,d}$ has integral $(b-a)/(d+1)$, exactly the specified normalization.

Now differentiate with respect to $t$ and apply the final recursion for a divided difference:In terms of normalized lower-degree B-splines, this is the B-spline differentiation formulaA zero denominator corresponds to a collapsed-support basis term and contributes zero. Repeated knots follow by coalescing distinct knots; at knots where the classical derivative is discontinuous, read the formula on each open span or one-sided. The stated maximal interior continuity corresponds to simple interior knots, while the clamped endpoint repetitions do not affect the interior argument.

Let the control-point abscissae be the Greville abscissaeCollect the coefficient of $N_{i,d-1}$ after differentiating:The difference of the two consecutive knot averages telescopes toso every noncollapsed coefficient is one. The lower-degree basis on the endpoint-trimmed knot vector has partition of unity; equivalently the outer lower-degree basis functions on the original vector have collapsed support. Therefore $X^{\prime }(t)=1$ on the parameter interval. With $d+1$ repeated left endpoint knots at $a$, the clamped basis has $N_{0,d}(a)=1$, all other values zero, and ${\xi }_0=a$. Thus $X(a)=a$ fixes the constant of integration. Continuity and endpoint limits now giveThis is linear precision at Greville abscissae. It requires neither equal knot spacing nor a restriction on the other control-point coordinates; those determine the remaining coordinates of the parametric curve.

For distinct interpolation nodes $x_0,\dots ,x_n$, let $p_n$ be the unique polynomial of degree at most $n$ satisfying $p_n(x_i)=f(x_i)$. Existence follows from the Lagrange polynomial expressionuniqueness follows because the difference of two interpolants has $n+1$ distinct zeros but degree at most $n$.

Define the divided difference $f[x_0,\dots ,x_n]$ to be the coefficient of $x^n$ in $p_n$, even when that coefficient is zero. For $n=0$ this gives $f[x_0]=f(x_0)$. Permuting the nodes does not change the interpolation conditions, so it does not change their unique interpolant or this coefficient. The divided difference is symmetric in all the nodes. Equivalently its symmetric expression is

For $n\ge 1$, let $p_L,p_R$ be the interpolation polynomials of degree at most $n-1$ on nodes $x_0,\dots ,x_{n-1}$ and $x_1,\dots ,x_n$, respectively. The polynomialhas degree at most $n$. At $x_0$ it equals $p_L(x_0)$; at $x_n$ it equals $p_R(x_n)$. At each common node both interpolants equal $f$, and the displayed weights sum to one, so $p$ also equals $f$ there. Thus it is the full interpolant by uniqueness.

Its coefficient of $x^n$ is the difference of the leading coefficients of $p_R,p_L$ divided by $x_n-x_0$. By the definition of a divided difference,

Write $D=f[x_0,\dots ,x_n]$ and let $D_i$ be the divided difference with $x_i$ omitted. By symmetry from part (a), reorder the full list so that its first node is $x_i$ and its last is $x_j$. The recurrence from part (b) then has first omitted-node term $D_i$ and second omitted-node term $D_j$, and givesThis proves the requested identity for every pair $i\ne j$ and fixes its sign explicitly; it is one of the omitted-node identities for divided differences.

The ordinary interpolation formulation is unambiguous for strictly increasing knots; repeated knots require specified confluent interpolation or a limiting convention. First take distinct knots and $k\ge 2$, and for fixed $t$ write $F_t(u)=(u-t{)}_{+}^{k-1}$. The two degree-at-most-$k-1$ Lagrange interpolation polynomials ${\ell }_i(\cdot ,t)$ and ${\ell }_{i+1}(\cdot ,t)$ agree at the $k-1$ shared knots $t_{i+1},\dots ,t_{i+k-1}$. Their difference is thereforeThis remains valid if their difference has lower degree: the coefficient is then zero. The leading coefficient of a degree-at-most-$k-1$ interpolant is its order-$(k-1)$ divided difference. Comparing leading coefficients and using the divided-difference recursion givesConsequently the Lee interpolation identity holds for every real $x,t$:No differentiability of the truncated power in its argument was needed for this distinct-node proof.

Sum the identity over $i=1,\dots ,n$. The right side telescopes, giving ${\sum }_i{\omega }_i(x)N_i(t)={\ell }_{n+1}(x,t)-{\ell }_1(x,t)$. When $t_k<t<t_{n+1}$, all the nodes for ${\ell }_1$ lie below $t$, so its interpolation data are zero and ${\ell }_1\equiv 0$. All the nodes for ${\ell }_{n+1}$ lie above $t$, where $F_t(u)=(u-t{)}^{k-1}$ is already a polynomial of the admissible degree. Uniqueness of polynomial interpolation gives ${\ell }_{n+1}(x,t)=(x-t{)}^{k-1}$. Therefore the Marsden identity isFor order one the empty product is one, the interpolants are constants and a consistent half-open interval convention for $(u-t{)}_{+}^0$ gives the same telescoping proof. Nondecreasing repeated-knot sequences can be treated by the appropriate confluent or limiting convention wherever that definition is valid; merely specifying repeated data values does not uniquely determine the interpolation polynomials. The basic open knot interval in the Marsden identity avoids endpoint convention ambiguity.

Assume the spline knot sequence is ordered and its relevant support spans satisfy $t_{i+k}>t_i$. For distinct knots, the divided difference is a finite linear combination of evaluations, so it commutes with integration. With $u\in [a,b]$,Taking the order-$k$ divided difference in $u$ givesIndeed, the order-$k$ divided difference of a degree-$k$ polynomial is its leading coefficient, here $1/k$. This proves the unit-integral normalization of a B-spline. Admissible repeated knots follow by coalescing knots, with the usual one-sided endpoint conventions.

For fixed $t$, put $g_t(u)=(u-t{)}_{+}^{k-1}$, a truncated power function. Begin with distinct increasing knots. The two interpolation polynomials ${\ell }_i(\cdot ,t)$ and ${\ell }_{i+1}(\cdot ,t)$ agree at their $k-1$ shared knots. Their difference has degree at most $k-1$, soFor $k=1$ the empty product is one and the same assertion holds for constant interpolants. The leading coefficient of a degree-at-most-$k-1$ interpolant on $k$ nodes is its order-$k-1$ divided difference, by the Newton interpolation polynomial. ThereforeThis proves the Lee interpolation identityThe identity holds for every real $x,t$, with the usual convention for the order-zero truncated power. Admissible repeated knots are handled by the corresponding confluent divided differences and consistent one-sided limits at breakpoints; taking these limits preserves the Lee interpolation identity.

Sum over $i$ to telescope:If $t_k<t<t_{n+1}$, the first $k$ knot values of $g_t$ are zero, so ${\ell }_1=0$. At the last $k$ knots $t_{n+1},\dots ,t_{n+k}$, the function $g_t$ agrees with the polynomial $(u-t{)}^{k-1}$, so uniqueness of polynomial interpolation gives ${\ell }_{n+1}(x,t)=(x-t{)}^{k-1}$. Thus the Marsden identity is

For order $k\ge 2$, set $g(u)=(u-t{)}_{+}^{k-2}$. Then $(u-t)g(u)=(u-t{)}_{+}^{k-1}$. Apply the given divided difference product identity with nodes $t_i,\dots ,t_{i+k}$ and multiply by the length $t_{i+k}-t_i$ of their knot interval:Using the definition of each lower-order normalized B-spline, the two divided differences are $N_{i,k-1}(t)/(t_{i+k-1}-t_i)$ and $N_{i+1,k-1}(t)/(t_{i+k}-t_{i+1})$. Hence the Cox-de Boor recurrence isFor completeness, the product identity itself follows fromand the ordinary divided difference recurrence. Substitution yields the stated convex combination of the two order-$k-1$ divided differences.

The initial order-one splines are the indicators $N_{i,1}(t)=1_{[t_i,t_{i+1})}(t)$. For repeated knots, a term with zero knot-span denominator is defined as zero; this agrees with the standard limiting basis convention. The recurrence uses the partition of unity normalization with $0\le N_{i,k}\le 1$, not a separate rescaling of each spline to make its actual supremum exactly one. The original PDF recurrence has the denominators above; several of these indices and signs were corrupted in the converted TeX.

The successive divided differences for nodes $-1,0,1,3$ areThus the Newton interpolation polynomial isExpanding the products gives the power formThe four values verify the data. Uniqueness follows because the difference of two degree-at-most-three interpolants would have four distinct roots.