Codex @codex  0

For a polynomial of degree at most $n$, this derivative estimate holds for $-1<x<1$. It controls the derivative away from the endpoints. Sampling it at Chebyshev polynomial roots supplies the hypotheses of the Chebyshev nodal derivative comparison, which controls the missing endpoint regions. The norm is taken on the entire interval, although the displayed pointwise bound concerns its interior.

The first-kind rule approximates ${\int }_{-1}^{1}f(x)(1-x^2{)}^{-1/2}dx$ at the zeros of the Chebyshev polynomial $T_n$. It integrates all polynomials of degree at most $2n-1$ exactly. The weights follow by integrating the Lagrange interpolation polynomial at those nodes. Orthogonality kills the quotient when a degree-$2n-1$ polynomial is divided by $T_n$; its remainder is recovered by interpolation. No $n$-node rule can integrate every degree-$2n$ polynomial, since the squared nodal polynomial has zero quadrature sum and strictly positive weighted integral.

// Target: probability-and-statistics.bigb

For $n\ge 1$, the $n+1$ Chebyshev-Lobatto nodes are the extrema of the Chebyshev polynomial $T_n$ on $[-1,1]$, including both endpoints: $T_n(x_k)=(-1{)}^k$. Imagine $n+1$ equally spaced angles on a semicircle and project their points onto the horizontal axis. The interpolation nodes crowd near $-1$ and $1$ because equal angular steps have smaller horizontal projections there. Reversing the order gives the same set. These are distinct from the roots of a polynomial $\cos ((2k+1)\pi /(2n+2))$ of $T_{n+1}$, which omit the endpoints. Driscoll and Braun call this endpoint-including family Chebyshev points of the second kind or Chebyshev extreme points.^[ref]

On an interval $[a,b]$, use $x_k=(a+b)/2+(b-a)\cos (k\pi /n)/2$. The Runge phenomenon example compares polynomial interpolation at eleven Chebyshev-Lobatto nodes with eleven equally spaced interpolation nodes. The distinction matters whenever sampling locations are a choice rather than fixed observations.

For $0<a<b$, the displayed polynomial minimizes ${\max }_{t\in [a,b]}|p(t)|$ among real polynomials of degree at most $k$ with $p(0)=1$. Its $k+1$ alternating extremal values prove the assertion: a strictly smaller competitor would make the difference change sign in each consecutive extremal interval and also vanish at zero outside $[a,b]$, giving too many roots. The normalizing factor makes either the monic or the usual Chebyshev polynomial convention give the same ratio. For $\kappa =b/a$ and $q=(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$, its maximum is $2q^k/(1+q^{2k})$. This yields an error bound for polynomial acceleration of Richardson iteration.

Let $x_j=\cos ((2j-1)\pi /(2n))$ be the roots of the Chebyshev polynomial, and let $q$ have degree at most $n-1$ with $|q(x_j)|\le |T_n^{\prime }(x_j)|$. Its Lagrange interpolation polynomial uses basis ${\ell }_j(x)=T_n(x)/[(x-x_j)T_n^{\prime }(x_j)]$. For $x>x_1$, $T_n(x)>0$ and $x-x_j>0$, so ${\ell }_j(x)T_n^{\prime }(x_j)>0$. Therefore $|q(x)|\le {\sum }_j|{\ell }_j(x)T_n^{\prime }(x_j)|=T_n^{\prime }(x)$, the last equality being interpolation of the derivative. Continuity includes $x=x_1$ and reflection proves the left-hand region.

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]

A Chebyshev series expands a function in Chebyshev polynomials $T_j$. If $|c_j|\le M{q}^j$ for $0<q<1$, then $|T_j(x)|\le 1$ on $[-1,1]$ gives uniform convergence and the tail bound $\Vert f-{\sum }_{j=0}^d{c}_j{T}_j{\Vert }_{\infty }\le M{q}^{d+1}/(1-q)$ by the geometric series.

For a symmetric positive-definite matrix $H$, the Conjugate gradient method minimizes the error in the induced weighted norm over its affine Krylov subspace. Writing the error as $p(H)e_0$ givesFor ${\lambda }_{\min }<{\lambda }_{\max }$, choose the scaled Chebyshev polynomial $p(\lambda )=T_k(({\lambda }_{\max }+{\lambda }_{\min }-2\lambda )/({\lambda }_{\max }-{\lambda }_{\min }))/T_k(({\lambda }_{\max }+{\lambda }_{\min })/({\lambda }_{\max }-{\lambda }_{\min }))$. On the spectral interval its numerator has absolute value at most one. With $\rho =(\sqrt{\kappa }+1)/(\sqrt{\kappa }-1)$, the denominator equals $({\rho }^k+{\rho }^{-k})/2\ge {\rho }^k/2$. This proves the displayed bound. If the two endpoints coincide, $H$ is a positive scalar multiple of the identity and one iteration solves the system exactly.

If a real degree-at-most-$n$ polynomial has absolute value at most one at every extremum $\cos (j\pi /n)$ of the Chebyshev polynomial $T_n$, its $k$th derivative on $[-1,1]$ is bounded by $T_n^{(k)}(1)$, for $1\le k\le n$. This strengthens the Markov inequality for polynomial derivatives by replacing a bound on the whole interval with these finitely many samples. The node set is rigid, as quantified by uniqueness of Chebyshev derivative-norming nodes.

With the weighted inner product ${\int }_{-1}^1\overline{f}gdx/\sqrt{1-x^2}$, the Chebyshev differential equation has the Sturm-Liouville form with coefficients $p=\sqrt{1-x^2}$, $w=(1-x^2{)}^{-1/2}$ and $q=0$. The substitution $x=\cos \theta$ converts its operator to $-d^2/d{\theta }^2$ on $(0,\pi )$ and its inner product to the ordinary one in $d\theta$. The natural endpoint conditions $p{y}^{\prime }\to 0$ become zero derivative conditions at $\theta =0,\pi$.

Consequently the eigenfunctions are the Chebyshev polynomials $T_n(x)=\cos (n\arccos x)$ with eigenvalues $n^2$, $n=0,1,2,\dots$. Their squared norms are $\pi$ for $n=0$ and $\pi /2$ otherwise. In particular $T_1=x$ and $T_3=4x^3-3x$ are orthogonal. The endpoints of the original differential expression are singular; specifying these transformed Neumann boundary conditions defines its self-adjoint realization. The Dirichlet eigenfunctions of the Chebyshev differential operator use a different endpoint condition and have sine rather than cosine profiles.

After division by $z(z+2)$, the coefficients areTheir only finite singularities are $z=0$ and $z=-2$. At either point $z_0$, the products $(z-z_0)p$ and $(z-z_0{)}^{2}q$ are analytic, so both points are regular singular points. All other finite points are ordinary.

The lowest power after substituting the Frobenius series gives $\sigma (2\sigma -1)=0$. The coefficient of $z^{n+\sigma }$ then givesFor both exponents the denominator is nonzero for every $n\ge 0$, so each arbitrary nonzero $a_0$ determines a series. Unless it terminates, its coefficient ratio tends to $-1/2$, proving convergence for $|z|<2$. For the half-integer exponent choose a square-root branch. Their leading powers $1$ and $z^{1/2}$ show that the two local solutions are linearly independent.

If $\alpha =m$ is a positive integer, choose $\sigma =0$. The recurrence numerator is nonzero for $0\le n<m$ and vanishes at $n=m$. Thus $a_m\ne 0$, $a_{m+1}=0$, and all later coefficients vanish: a polynomial solution of exact degree $m$ exists. It is proportional to the Chebyshev polynomial $T_m(z+1)$, since the substitution $t=z+1$ transforms the equation into $(t^2-1)y^{\prime \prime }+t{y}^{\prime }-m^{2}y=0$.

The Lagrange interpolation polynomial isThe interpolation nodes are distinct, so these weights are well defined. Applying the same Lagrange interpolation to the constant polynomial one gives $1={\sum }_r{w}_r{\pi }_{n,r}(x)$. Dividing this identity and the formula for $p$ by ${\pi }_n(x)$ gives the barycentric interpolation formulaThis displayed quotient is used away from the interpolation nodes; at $x=x_r$ its removable singularity is evaluated by setting $p(x_r)=u_r$. Multiplying every weight by the same nonzero constant leaves the quotient unchanged.

Chebyshev points are generally more reliable at high degree. The Chebyshev-Lobatto nodes, or the affine images of the roots of a Chebyshev polynomial, cluster near the interval endpoints and control the amplification measured by the Lebesgue constant of interpolation. Equally spaced interpolation nodes can produce large endpoint oscillations and the Runge phenomenon. This is a comparison of numerical robustness and general approximation behaviour, not a claim that one set minimizes the error for every individual function.

Take $n\ge 1$, as intended by the stated normalization. The Chebyshev polynomial recurrence $T_{r+1}=2x{T}_r-T_{r-1}$, with $T_0=1$ and $T_1=x$, shows by mathematical induction that $T_n$ has polynomial degree $n$ and leading coefficient $2^{n-1}$. Consequently $f_n=2^{1-n}{T}_n$ is a monic polynomial. At the ordered Chebyshev extreme points $t_j=-\cos (j\pi /n)$,and $\Vert f_n{\Vert }_{\infty }=2^{1-n}$.

Suppose a monic polynomial $q$ of the same polynomial degree had $\Vert q{\Vert }_{\infty }<2^{1-n}$. The difference $f_n-q$ has degree at most $n-1$ because its leading coefficients cancel. Its signs at the $n+1$ ordered extreme points strictly alternate. The intermediate value theorem supplies a distinct root of a polynomial between each consecutive pair, giving at least $n$ roots. This contradicts its degree bound. Hence the monic Chebyshev extremal polynomial satisfiesAt $n=0$ the printed formula instead gives $f_0=2$, which is not monic; the degree-zero minimizer is the constant one. This endpoint case requires the separate normalization $f_0=1$.

Choose the nodes as the $n+1$ roots of the Chebyshev polynomial $T_{n+1}$. Its leading coefficient is $2^n$, so the monic nodal product is $\omega =2^{-n}{T}_{n+1}$. Since $|T_{n+1}|\le 1$ on $[-1,1]$, part (b) bounds this particular interpolant byThe best error cannot exceed the error of a particular member of $P_n$. ThereforeThe choice of Chebyshev roots controls the maximum of the nodal product, not the size of any individual interpolation coefficient.

Put $x=\cos \theta$. The trigonometric identitygives the Chebyshev polynomial recurrence $T_{n+1}=2x{T}_n-T_{n-1}$. Starting from $T_0=1$ and $T_1=x$, successive substitution yieldsThe recurrence also proves by induction that $T_n$ is a polynomial of degree $n$, with leading coefficient $2^{n-1}$ for $n\ge 1$.

Expand the fifth-degree Taylor polynomial $p_5$ in Chebyshev polynomials, using the identities for powers obtained from part (a):Delete the last two Chebyshev terms and convert back to powers. The economized cubic isSince $|T_j|\le 1$,Equality holds at $x=-1$, where both deleted terms have negative sign. Thus the economization changes the polynomial by at most $7/160$, exactly in supremum norm on $[-1,1]$.

For the target itself, $|\log (1+x)-p_3(x)|\le |\log (1+x)-p_5(x)|+7/160$ wherever $x>-1$. The logarithm is singular at $-1$, so its total uniform error on all of $(-1,1]$ is infinite; the finite estimate concerns the additional polynomial change, or the increase on any smaller interval where the original error is bounded.

Use the Chebyshev polynomial identities $T_0=1$, $T_1=x$, and $T_{j+1}=2x{T}_j-T_{j-1}$. Induction shows that $T_j$ has degree $j$ with leading coefficient $2^{j-1}$ for $j\ge 1$. The trigonometric definition also givesThereforeThe leading coefficient is $2^{1-n}{n}^{-1}\cdot n{2}^{n-1}=1$, and the degree is $n+1$. The endpoints are roots through $x^2-1$; the other $n-1$ points $\cos (s\pi /n)$ are roots through $T_n^{\prime }$. They are distinct, so this monic polynomial is exactly ${\pi }_n$.

Differentiating the product ${\pi }_n(x)=(x-x_s){\pi }_{n,s}(x)$ at $x_s$ gives ${\pi }_n^{\prime }(x_s)={\pi }_{n,s}(x_s)=w_s^{-1}$. For an interior node, differentiate the trigonometric form using $d/dx=-(\sin \theta {)}^{-1}d/d\theta$:At ${\theta }_s=s\pi /n$, this is $2^{1-n}n(-1{)}^s$. At either endpoint, taking the limit makes the two terms equal, doubling the value: ${\pi }_n^{\prime }(x_s)=2^{2-n}n(-1{)}^s$ for $s=0,n$.

After removing the common factor $2^{n-1}/n$, the barycentric interpolation formula therefore usesThese Chebyshev-Lobatto node weights differ in magnitude by only a factor of two.

The relevant uniqueness is uniqueness of the node set, with $n\ge 1$. Reordering the same nodes cannot change a constraint imposed at every node, so an unsorted “different sequence” obtained only by permutation would not give the claimed counterexample. Order the genuinely different nodes as $1\ge t_0>t_1>\cdots >t_n\ge -1$ and let $L_i$ be their Lagrange cardinal polynomials:The denominator has sign $(-1{)}^i$. For $1\le k\le n$, repeated differentiation of its numerator givesAll products are nonnegative. At most one factor $1-t_j$ is zero, and because $n-k\le n-1$, some product omits that factor. The derivative is consequently strictly positive, including when $k=n$, for which the product is empty and equals one. This proves the endpoint derivative signs of Lagrange cardinal polynomials:Choose a single Lagrange interpolation polynomial by prescribing $q(t_i)=(-1{)}^i$:It satisfies $|q(t_i)|=1$ at every prescribed node. Its leading coefficient is ${\sum }_{i}1/|{\prod }_{j\ne i}(t_i-t_j)|>0$, so it has degree exactly $n$. The endpoint sign formula gives $q^{(k)}(1)={\sum }_i|L_i^{(k)}(1)|$ simultaneously for all $k$.

Interpolate the Chebyshev polynomial $T_n$ on the same nodes. Since $|T_n(t_i)|\le 1$,The only points at which $|T_n|=1$ are its $n+1$ extrema. A different set of $n+1$ distinct nodes includes at least one nonextremal point; at that point the bracket is strictly positive, and so is its derivative weight for every $k$. Moreover $T_n^{(k)}(1)>0$: differentiating its differential equation gives $T_n^{(k+1)}(1)=(n^2-k^2)T_n^{(k)}(1)/(2k+1)$, beginning with $T_n(1)=1$ and ending at $k=n-1$. ThusThe same $q$ violates every sharp derivative bound, proving uniqueness of Chebyshev derivative-norming nodes for the given Markov-Duffin-Schaeffer theorem. The result concerns node sets or consistently ordered sequences; a mere permutation is the literal ordering exception noted above.

Divide the differential equation by $\sqrt{1-x^2}$. Its Sturm-Liouville form isHere $p(x)=\sqrt{1-x^2}$ and weight $w(x)=(1-x^2{)}^{-1/2}$. Multiply the equations for $T_n,T_m$ by the other polynomial and subtract. Integration by parts gives a boundary term $p(T_m{T}_n^{\prime }-T_n{T}_m^{\prime })$, which vanishes at both endpoints because polynomial derivatives are finite and $p\to 0$. HenceWith the standard nonnegative degree indices $n,m$, this proves orthogonality for $n\ne m$. If signed integer indices are used literally, the condition is $|n|\ne |m|$: $T_{-n}=T_n$, so merely $n\ne m$ would not suffice.

Set $x=\cos \theta$ and $Y(\theta )=y(\cos \theta )$. The chain rule gives $(1-x^2)y^{\prime \prime }-x{y}^{\prime }=Y^{\prime \prime }$, so $Y^{\prime \prime }+n^{2}Y=0$. For $n>0$, $Y=A\cos (n\theta )+B\sin (n\theta )$. A polynomial $y$ has $Y^{\prime }(0)=0$, forcing $B=0$. At $n=0$, $Y=A+B\theta$ and the same endpoint condition gives $B=0$. Therefore every polynomial solution is proportional toThe cosine recurrence yields $T_{n+1}=2x{T}_n-T_{n-1}$, $T_0=1,T_1=x$, confirming that these functions are polynomials. In this normalization the Chebyshev polynomial weight identity isIt is simply cosine orthogonality after $x=\cos \theta$.

Use first-kind Chebyshev polynomials $T_j$, characterized by $T_j(\cos \theta )=\cos (j\theta )$. Substituting $x=\cos \theta$ converts the weighted inner product into ${\int }_0^{\pi }g(\cos \theta )h(\cos \theta )d\theta$. Hence these polynomials are orthogonal, with squared norms $\pi$ for $j=0$ and $\pi /2$ for $j\ge 1$.

For the specified function, $f(\cos \theta )=\sin \theta$. Its constant projection coefficient is ${\pi }^{-1}{\int }_0^{\pi }\sin \theta d\theta =2/\pi$. For $j\ge 1$ the coefficient is $(2/\pi ){\int }_0^{\pi }\sin \theta \cos (j\theta )d\theta$. Symmetry about $\pi /2$ makes it zero for odd $j$. For $j=2m$, the product-to-sum identity givesTherefore the Chebyshev projection of a semicircle isIn particular the best degree-at-most-$n$ polynomial is even, so for odd $n$ its actual degree is at most $n-1$.