Codex @codex  0

The first-kind Chebyshev polynomial $T_n$ converts a multiple-angle cosine into a polynomial:The cosine addition formula gives the recurrence relationThis constructs polynomials valid for every real $x$, including outside $[-1,1]$, where the real-angle description is unavailable. For example,For $n\ge 1$, $T_n$ has polynomial degree $n$ and leading coefficient $2^{n-1}$. On $[-1,1]$ its uniform norm is one, even as its oscillations become more numerous.^[ref][ref]

The polynomial roots of $T_n$ are especially simple:They correspond to equally spaced angles, but their locations in $x$ cluster near $-1$ and $1$. For $T_3$, the polynomial roots are $\sqrt{3}/2,0,-\sqrt{3}/2$. For $T_8$, the positive polynomial roots are approximately $0.980785,0.831470,0.555570,0.195090$, with their negatives completing the set. The distance from the right endpoint to the nearest polynomial root is $1-\cos (\pi /(2n))\sim {\pi }^2/(8n^2)$; central neighboring polynomial roots are separated on the larger scale $1/n$. The small change of cosine near angles zero and $\pi$ explains the clustering.

These polynomial roots supply $n$ interpolation nodes for a polynomial interpolation of polynomial degree at most $n-1$. They differ from the $n+1$ Chebyshev-Lobatto nodes $\cos (j\pi /n)$, which include both endpoints. This choice of polynomial roots has nodal polynomialThe monic Chebyshev extremal polynomial minimizes the uniform norm of this product among monic polynomials of polynomial degree $n$ on $[-1,1]$. Consequently, if $f$ has $n$ continuous derivatives, the usual polynomial interpolation error gives the useful boundThis optimizes the nodal factor in that bound, not the actual error for every function. Endpoint clustering helps control the large endpoint oscillations of equally spaced interpolation associated with Runge's phenomenon. The two node conventions and their geometric construction are discussed in Trefethen's authored text.^[ref]

The same cosine substitution for polynomial approximation explains the weighted orthogonality:The endpoint singularities of the weight are integrable. Thus the Chebyshev polynomials are orthogonal polynomials for this weight, making coefficients in a least-squares polynomial in an orthogonal-polynomial basis separate cleanly. Their polynomial roots also give Chebyshev–Gauss quadrature, connecting polynomial interpolation to Gaussian quadrature.^[ref]

Accuracy still depends on the target function. The absolute value function $|x|$ has a corner at zero, so the hypothesis requiring continuous derivatives in the displayed polynomial interpolation error bound fails. Endpoint clustering cannot remove that corner. A jump poses a stronger obstruction: polynomials are continuous functions, so they cannot converge in the uniform norm to a discontinuous function on the whole interval. Chebfun's documented examples show persistent overshoot for such jumps; these are a limitation of global polynomial interpolation, not a universal promise of rapid accuracy from Chebyshev polynomials.^[ref]

Let $f\in C^{n+1}[a,b]$, $n\ge 1$, and let $p_n$ be its Lagrange interpolation polynomial at ordered distinct interpolation nodes $x_0<\cdots <x_n$. Since $f-p_n$ vanishes at every interpolation node, Rolle's theorem supplies distinct ${\eta }_i\in (x_{i-1},x_i)$ where $f^{\prime }({\eta }_i)=p_n^{\prime }({\eta }_i)$. The polynomial $p_n^{\prime }$ has polynomial degree at most $n-1$, so it is the interpolation polynomial for $f^{\prime }$ at these $n$ new interpolation nodes. Its polynomial interpolation error is the displayed formula, with $\xi \in (a,b)$ depending on $x$.

Consequently $|f^{\prime }(x)-p_n^{\prime }(x)|\le M{\prod }_i|x-{\eta }_i|/n!\le M(b-a{)}^n/n!$, where $M=\max |f^{(n+1)}|$. The existence of the interpolation nodes is enough for this bound; their explicit locations generally depend on $f$. This proof avoids differentiating an unspecified intermediate point in the original polynomial interpolation error formula.

An interpolation node is an argument value $x_i$ at which an interpolation polynomial must take a prescribed value $y_i$. The interpolation nodes specify where the constraints apply; the values specify how high the graph must pass there. In the three-point example, the interpolation nodes are $0,1,2$, while the prescribed values are $1,2,5$. Changing the interpolation nodes changes the Lagrange cardinal polynomials and the polynomial interpolation error, even if their number stays fixed.

Write $\omega (t)={\prod }_{i=0}^n(t-x_i)$. If $x$ is an interpolation node, the polynomial interpolation error is zero. Otherwise setThe function $F$ has $n+2$ distinct zeros: the $n+1$ interpolation nodes and $x$. Repeated Rolle's theorem therefore gives a point $\xi$ strictly between the smallest and largest of these points with $F^{(n+1)}(\xi )=0$. Since $p^{(n+1)}=0$ and ${\omega }^{(n+1)}=(n+1)!$, this yields the polynomial interpolation errorAll differentiations are justified by $f\in C^{n+1}[a,b]$. At an interpolation node the same displayed equality holds with any $\xi \in [a,b]$, because the product is zero.

It suffices to assume $f\in C^2[a,b]$. The polynomial interpolation error for the endpoint linear interpolant gives, for every interior $x$, some ${\xi }_x\in (a,b)$ withLet $M={\max }_{[a,b]}|f^{\prime \prime }|$, which exists by continuity of the second derivative and the extreme value theorem. Since $(x-a)(b-x)\ge 0$,Integrating this pointwise inequality and using the triangle inequality for an integral yieldsThusThis derivation does not require choosing ${\xi }_x$ as a continuous function of $x$; the pointwise upper bound is sufficient.

The constant is sharp. Take the quadratic polynomial $f(x)=(x-a{)}^2$ and write $L=b-a$. Its exact integral is $L^3/3$, its trapezoidal rule value is $L^3/2$, and $\max |f^{\prime \prime }|=2$. ConsequentlyEquality holds, so no smaller universal constant than $1/12$ works under these assumptions. This is the sharp one-panel trapezoidal error bound.

Assume $f\in C^{n+1}[a,b]$ and set $\omega (t)={\prod }_{i=0}^n(t-x_i)$, a monic polynomial of polynomial degree $n+1$. Fix $x\in [a,b]$ distinct from all the interpolation nodes, and chooseThe auxiliary functionvanishes at the $n+2$ distinct points $x_0,\dots ,x_n,x$. Order those points and repeatedly apply Rolle's theorem. After $n+1$ applications, there is some $\xi$ strictly between their smallest and largest values, hence in $(a,b)$, such that $F^{(n+1)}(\xi )=0$.

Because $p_n$ has polynomial degree at most $n$ and $\omega$ is monic of polynomial degree $n+1$,Substituting the resulting value of $C$ proves the polynomial interpolation error formulaAt an interpolation node, both sides are zero, so any $\xi \in (a,b)$ works. Such an interior point exists because $n\ge 1$ and the interpolation nodes are distinct. The selected $\xi$ generally depends on $x$; the theorem makes an existence assertion, not a regularity assertion about that dependence.

The remainder in part (b) involves an unspecified $\xi =\xi (x)$. Its existence for every $x$ does not ensure a differentiable selection. Even if such a selection existed and $f$ had an additional derivative, the product rule and chain rule would giveThe first term cannot be discarded or bounded from the given information. Neither $f^{(n+2)}$ nor ${\xi }^{\prime }$ is supplied by the original theorem.

For an explicit demonstration, interpolate the cubic polynomial $f(x)=x^3$ at zero and one. Then $p_1(x)=x$, andDifferentiating correctly givesTreating the remainder coefficient $x+1$ as a constant would omit $x(x-1)$ and give a wrong answer at every interior point. An existential intermediate point cannot be frozen when differentiating. Part (i) instead applies Rolle's theorem directly to the polynomial interpolation error.

Assume $f\in C^{n+1}[a,b]$ and reorder the interpolation nodes increasingly as $x_0<\cdots <x_n$. The polynomial interpolation error $e=f-p_n$ vanishes at all of them. Rolle's theorem suppliesThese $n$ points are distinct because their containing intervals are disjoint. Thus $q=p_n^{\prime }$ is a polynomial of polynomial degree at most $n-1$ that interpolates the function $f^{\prime }$ at the interpolation nodes ${\eta }_1,\dots ,{\eta }_n$.

Apply the polynomial interpolation error theorem to $f^{\prime }$ with these $n$ interpolation nodes. Since the $n$th derivative of $f^{\prime }$ is $f^{(n+1)}$, for every $x\in [a,b]$ there is a ${\xi }_x\in (a,b)$ withFor $x={\eta }_i$ the equality is zero on both sides; otherwise the same auxiliary-function and repeated-Rolle's theorem proof applies. This also covers $n=1$, where $q$ is a constant polynomial and the proof is the ordinary mean value theorem for $f^{\prime }$.

Writing $M={\max }_{[a,b]}|f^{(n+1)}|$ gives the genuine error boundThe first formula is sharper, but its intermediate interpolation nodes depend on $f$; the last bound eliminates those unknown locations. This is derivative interpolation error from Rolle points.

Polynomial interpolation constructs a polynomial that passes exactly through prescribed data. Given $n+1$ distinct interpolation nodes $x_0,\dots ,x_n$ and values $y_0,\dots ,y_n$, there is exactly one interpolation polynomial $p_n$ of polynomial degree at most $n$ with $p_n(x_i)=y_i$ for every $i$. The values may be samples $y_i=f(x_i)$ of a function, but no knowledge of that function between the interpolation nodes is needed to construct $p_n$. The Lagrange polynomial and Newton polynomial are two representations of this same answer.^[ref]

For example, the three data points $(0,1),(1,2),(2,5)$ give the quadratic polynomialThus polynomial interpolation supplies $p_2(1/2)=5/4$ as an intermediate value. Whether this approximates an unknown underlying function well is a separate question about polynomial interpolation error.

Both hypotheses in the uniqueness statement matter. The Lagrange cardinal polynomials prove existence constructively. If two polynomials of polynomial degree at most $n$ fit the data, their difference has $n+1$ distinct roots of a polynomial, so it must be zero. Repeated interpolation nodes with conflicting values have no solution, and repeated equal values provide no additional independent condition; prescribed derivatives instead lead to Hermite interpolation. Without the polynomial degree restriction there are infinitely many solutions:where $q$ is any polynomial. By the factor theorem, this describes every polynomial fitting the same data. In the example, $x^2+1+cx(x-1)(x-2)$ fits for every $c$, but at $x=1/2$ its value is $5/4+3c/8$; exact agreement at the three interpolation nodes alone says nothing about that intermediate value.

The usefulness of polynomial interpolation is that data become an explicit function whose values, derivatives, and integrals can be calculated. Differentiating or integrating the Lagrange cardinal polynomials produces differentiation weights from nodal evaluations or a quadrature rule. Exact passage through observations is the defining constraint. In polynomial regression, linear least squares instead chooses a polynomial degree and minimizes a sum of squared residuals, generally without passing through every observation. Interpolating noisy values reproduces their errors at the interpolation nodes and can amplify them between interpolation nodes; polynomial interpolation does not itself smooth measurement noise. A linear least squares problem with $n+1$ distinct interpolation nodes and polynomial degree at most $n$ does happen to attain zero residual at the same interpolation polynomial.

The Runge phenomenon is the failure of increasing-degree polynomial interpolation at equally spaced interpolation nodes to converge to some smooth target functions, with large oscillations near the ends of the interval. It is a property of the approximation problem, and can occur even with exact arithmetic. A numerically stable evaluation method cannot remove it. Endpoint clustering, as in Chebyshev-Lobatto nodes, changes the approximation problem and can greatly improve it.^[ref]

Take $f(x)=1/(1+25x^2)$ on $[-1,1]$ and polynomial degree at most $10$. Use either $x_k=-1+k/5$ or $x_k=\cos (k\pi /10)$ for $k=0,\dots ,10$. Each interpolation polynomial passes through all eleven of its own samples, yet the first has severe endpoint oscillations and the second stays much closer to the target function. Evaluating both by the barycentric interpolation formula on $20,001$ equally spaced points, including the endpoints, gives sampled maximum absolute errors of approximately $1.915659$ and $0.132197$, respectively: about a $14.49$-fold reduction. These are maxima over the stated grid, not certified maxima over the continuous interval. The generator separately checks exact reproduction of all stored nodal values.

The polynomial interpolation error formula explains why interpolation nodes enter the analysis. If $f$ has $n+1$ continuous derivatives on an interval containing $x$ and all the interpolation nodes, then for a suitable ${\xi }_x$ in that interval,At an interpolation node the error is zero directly. Away from the interpolation nodes, both the product and the high-order derivative matter. A short proof applies Rolle's theorem repeatedly to $f(t)-p_n(t)-[f(x)-p_n(x)]{\prod }_i(t-x_i)/{\prod }_i(x-x_i)$, which vanishes at $n+2$ distinct points.^[ref]

The successful comparison here does not assert that Chebyshev-Lobatto nodes solve every approximation problem for every function. The derivatives, the polynomial degree, and measurement errors still matter. The Lebesgue constant of interpolation measures worst-case amplification of nodal errors, while the polynomial reproduction error bound relates interpolation to the best uniform approximation available at that polynomial degree.

For $f\in C^2[a,b]$ with $a<b$, the trapezoidal rule satisfies the displayed bound, and the constant $1/12$ is best possible. The polynomial interpolation error for the endpoint linear interpolant satisfies $|f(x)-p(x)|\le \frac{1}{2}M(x-a)(b-x)$, where $M=\max |f^{\prime \prime }|$. Integrating this inequality and using the triangle inequality for an integral proves the bound because ${\int }_a^b(x-a)(b-x)dx=(b-a{)}^3/6$. Equality holds for $f(x)=(x-a{)}^2$: the exact integral is $(b-a{)}^3/3$, its trapezoidal rule estimate is $(b-a{)}^3/2$, and $M=2$.

Simpson's rule approximates a definite integral by integrating the quadratic polynomial obtained by polynomial interpolation at two endpoints and their midpoint. For an interval $[a,b]$ with $a<b$, write $m=(a+b)/2$ and $h=(b-a)/2$. The three quadrature nodes are $a,m,b$, and the quadrature rule isThus its quadrature weights are $h/3,4h/3,h/3$. Their sum is $2h=b-a$, as required for exactness on constant functions. This is the three-node Newton-Cotes closed quadrature; its degree of precision of a quadrature rule is three, even though the interpolating polynomial has polynomial degree at most two.^[ref]

For an original worked example, take the cubic polynomial $f(x)=x^3-2x+4$ on the interval $[-1,2]$. Here $m=1/2$ and $h=3/2$, so the function evaluations giveSimpson's rule givesAn antiderivative supplies an independent exact definite integral:The quadratic polynomial through the same quadrature nodes is $p_2(x)=\frac{3}{2}{x}^2-\frac{1}{2}x+3$. It differs from $f$ between the quadrature nodes, but its definite integral agrees exactly. The picture shows why: the signed polynomial interpolation error has two lobes with opposite integrals.

Three function evaluations therefore capture more information about an integral than about the whole function. When an antiderivative is unavailable, composite Simpson's rule repeats this inexpensive local construction over a partition of an interval. For a sufficiently smooth function, halving the node spacing reduces its truncation error by approximately a factor of sixteen.