Polynomial approximation and Chebyshev interpolation

Define $h(u)=\sin u-u\cos u$. By [F1], [F2], and [F5], $h$ is differentiable and hence continuous, with $h^{\mathrm{\prime }}(u)=u\sin u\ge 0$ on $(0,\pi \mathrm{/}2)$ by [F4]. For $u>0$, the mean value theorem on $[0,u]$ gives $h(u)\ge h(0)=0$; at $u=0$ equality is immediate.

For $0<u<\pi \mathrm{/}2$, define $r(u)=\sin u\mathrm{/}u$. By the quotient rule, the identity derivative in [F5], and step 1.1, $r^{\mathrm{\prime }}(u)=(u\cos u-\sin u)\mathrm{/}{u}^2=-h(u)\mathrm{/}{u}^2\le 0$. The function $r$ is continuous on $[u,\pi \mathrm{/}2]$ by [F5], so the mean value theorem gives $r(u)\ge r(\pi \mathrm{/}2)=2\mathrm{/}\pi$ by [F3] and [F4]; at $u=\pi \mathrm{/}2$ equality holds. Multiplying by $u$ and checking $u=0$ proves the first inequality.

If $u\mathrm{\ne }v$, sine is continuous on the closed interval between them and differentiable inside by [F1] and [F5]. The mean value theorem gives $\mathrm{\mid }\sin u-\sin v\mathrm{\mid }=\mathrm{\mid }\cos c\mathrm{\mid }\mathrm{\mid }u-v\mathrm{\mid }\le \mathrm{\mid }u-v\mathrm{\mid }$ for some interior $c$, by [F3] and [F4]. If $u=v$, both sides are zero.

Put $z_i=x_{n-i}$, so $z_0<\cdots <z_n$ by [F1]. Under this reverse indexing, the supplier cardinal function at index $n-j$ is ${\mathrm{\ell }}_j$ by the specialization in [F1]. Applying [F3] gives its degree and cardinal values, including the one-node empty-product case $n=0$.

Put $L(x)={\sum }_j\mathrm{\mid }{\mathrm{\ell }}_{j,n}^{\sigma }(x)\mathrm{\mid }$. For every $g$ with $\mathrm{\parallel }g{\mathrm{\parallel }}_{\mathrm{\infty }}\le 1$, the defining sum gives $\mathrm{\mid }{I}_n^{\sigma }g(x)\mathrm{\mid }\le L(x)$, hence ${\mathrm{\Lambda }}_n^{\sigma }\le {\sup }_{x}L(x)$.

Prescribe data $y_i=1$ at $i=n-j$ and $0$ otherwise on the increasingly ordered nodes $z_i$ from step 1.1. The polynomial ${\mathrm{\ell }}_j$ has these data by step 1.1. The supplier uniqueness theorem [F2] makes it the unique degree-at-most-$n$ polynomial with the required cardinal values.

Prescribe $y_i=p(z_i)$ on the ordered nodes in step 1.1. By [F1] and [F3], their cardinal sum is $I_n^{\sigma }p$ and has degree at most $n$. The polynomial $p$ itself interpolates those data, so the supplier uniqueness theorem [F2] gives $I_n^{\sigma }p=p$.

Fix $x$. Define $\mathrm{sgn}(t)=1$ for $t>0$, $-1$ for $t<0$, and $0$ for $t=0$, and prescribe $\mathrm{sgn}({\mathrm{\ell }}_{j,n}^{\sigma }(x))$ at each node. These values lie in $[-1,1]$ and satisfy $\mathrm{sgn}(t)t=\mathrm{\mid }t\mathrm{\mid }$ by cases. Sort nodes increasingly, interpolate these values linearly, and extend constantly to the interval endpoints; each interpolated value is a convex combination of endpoint values, so the resulting continuous $g_x$ has norm at most $1$. The cardinal sum gives $I_n^{\sigma }{g}_x(x)=L(x)$, so ${\mathrm{\Lambda }}_n^{\sigma }\ge \mathrm{\parallel }{I}_n^{\sigma }{g}_x{\mathrm{\parallel }}_{\mathrm{\infty }}\ge L(x)$. Taking the supremum in $x$ and using step 1.2 proves equality. For $n=0$ the same construction is constant on the interval.

By [F1], choose a polynomial $p$ and an integer $m$ with $p\in {\mathcal{P}}_m$ such that $\mathrm{\parallel }f-p{\mathrm{\parallel }}_{\mathrm{\infty }}<\epsilon$; if $p=0$, take $m=0$.

For every $n\ge m$, $p\in {\mathcal{P}}_n$, so [F2] gives $0\le E_n(f)\le \mathrm{\parallel }f-p{\mathrm{\parallel }}_{\mathrm{\infty }}<\epsilon$. Since $\epsilon >0$ was arbitrary, $E_n(f)\to 0$. This conclusion concerns $E_n$ alone; it does not show that $(1+{\mathrm{\Lambda }}_n^{\sigma })E_n(f)\to 0$.

Put $N=n+1$ and ${\theta }_j=(2j+1)\pi \mathrm{/}(2N)$. By [F3], $T_N(\cos {\theta }_j)=0$. Differentiating $T_N(\cos \theta )=\cos (N\theta )$ using [F4]–[F5] gives $\sin \theta T_N^{\mathrm{\prime }}(\cos \theta )=N\sin (N\theta )$, hence $T_N^{\mathrm{\prime }}(\cos {\theta }_j)=N(-1{)}^j\mathrm{/}\sin {\theta }_j\mathrm{\ne }0$ by [F7].

Set ${\omega }_n(x)=(x^2-1)U_{n-1}(x)$. By [F3], ${\omega }_n(\cos \theta )=-\sin \theta \sin (n\theta )$, so it vanishes at every Lobatto node; its degree is $n+1$ by [F4]. For an interior node ${\theta }_j=j\pi \mathrm{/}n$, differentiating this identity gives $-\sin {\theta }_j{\omega }_n^{\mathrm{\prime }}(x_j)=-n\sin {\theta }_j(-1{)}^j$, hence ${\omega }_n^{\mathrm{\prime }}(x_j)=n(-1{)}^j$ by [F7].

Differentiating $U_{n-1}(\cos \theta )\sin \theta =\sin (n\theta )$ at $\theta =0,\pi$ gives $U_{n-1}(1)=n$ and $U_{n-1}(-1)=(-1{)}^{n-1}n$ by [F7]. The product rule then gives ${\omega }_n^{\mathrm{\prime }}(1)=2n$ and ${\omega }_n^{\mathrm{\prime }}(-1)=2n(-1{)}^n$, so at every Lobatto node ${\omega }_n^{\mathrm{\prime }}(x_j)=n(-1{)}^j\mathrm{/}{c}_j$.

By [F6], $T_N(x)\mathrm{/}(x-x_j)$ is a polynomial. Writing $T_N=(x-x_j)Q_j$ and differentiating gives $Q_j(x_j)=T_N^{\mathrm{\prime }}(x_j)$; at every other node $Q_j$ vanishes. Therefore $Q_j\mathrm{/}{T}_N^{\mathrm{\prime }}(x_j)$ is a degree-at-most-$n$ cardinal polynomial, which equals ${\mathrm{\ell }}_{j,n}^R$ by uniqueness [F2]. Substitution of $x=\cos \theta$ and [F3] gives the first formula.

By [F6], write ${\omega }_n(x)=(x-x_j)Q_j(x)$ with $Q_j$ a polynomial. Differentiating this factorization gives $Q_j(x_j)={\omega }_n^{\mathrm{\prime }}(x_j)$; at every other Lobatto node $Q_j$ vanishes because ${\omega }_n$ does. Thus $Q_j\mathrm{/}{\omega }_n^{\mathrm{\prime }}(x_j)$ is a degree-at-most-$n$ cardinal polynomial, hence ${\mathrm{\ell }}_{j,n}^L$ by [F2]. Substitution of ${\omega }_n(\cos \theta )=-\sin \theta \sin (n\theta )$ and $\mathrm{\mid }{\omega }_n^{\mathrm{\prime }}(x_j)\mathrm{\mid }=n\mathrm{/}{c}_j$ gives the second formula.

Fix $p\in {\mathcal{P}}_n$ and put $h=f-p$. By [F2], $I_n^{\sigma }p=p$, so $f-I_n^{\sigma }f=h-I_n^{\sigma }h$. If $\mathrm{\parallel }h{\mathrm{\parallel }}_{\mathrm{\infty }}=0$, then $h=0$ and the asserted bound follows; otherwise $g=h\mathrm{/}\mathrm{\parallel }h{\mathrm{\parallel }}_{\mathrm{\infty }}$ lies in $C[-1,1]$ with $\mathrm{\parallel }g{\mathrm{\parallel }}_{\mathrm{\infty }}=1$, so the definition in [F1] gives $\mathrm{\parallel }{I}_n^{\sigma }h{\mathrm{\parallel }}_{\mathrm{\infty }}=\mathrm{\parallel }h{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{\parallel }{I}_n^{\sigma }g{\mathrm{\parallel }}_{\mathrm{\infty }}\le {\mathrm{\Lambda }}_n^{\sigma }\mathrm{\parallel }h{\mathrm{\parallel }}_{\mathrm{\infty }}$. Pointwise, $\mathrm{\mid }h-I_n^{\sigma }h\mathrm{\mid }\le \mathrm{\mid }h\mathrm{\mid }+\mathrm{\mid }{I}_n^{\sigma }h\mathrm{\mid }$, so taking suprema gives $\mathrm{\parallel }f-I_n^{\sigma }f{\mathrm{\parallel }}_{\mathrm{\infty }}\le (1+{\mathrm{\Lambda }}_n^{\sigma })\mathrm{\parallel }f-p{\mathrm{\parallel }}_{\mathrm{\infty }}$.

Step 1.1 holds for every $p\in {\mathcal{P}}_n$. The unit ball in [F1] contains the zero function and each norm is nonnegative, so ${\mathrm{\Lambda }}_n^{\sigma }\ge 0$ and $1+{\mathrm{\Lambda }}_n^{\sigma }>0$. Taking the infimum of the right-hand side over the nonempty set ${\mathcal{P}}_n$ therefore gives $(1+{\mathrm{\Lambda }}_n^{\sigma })E_n(f)$, proving the claim.

In either angular grid the spacing is $h=\pi \mathrm{/}(n+1)$ for roots and $h=\pi \mathrm{/}n$ for Lobatto nodes. Choose a nearest grid angle ${\theta }_k$ and put $d_j=\mathrm{\mid }\theta -{\theta }_j\mathrm{\mid }$. Then $d_k\le h\mathrm{/}2$; if $\mathrm{\mid }j-k\mathrm{\mid }=r\ge 1$, the triangle inequality gives $d_j\ge rh-d_k\ge (r-\frac{1}{2})h$. At most two indices occur for each $r$.

For $\theta \mathrm{\ne }{\theta }_j$, put $s=(\theta +{\theta }_j)\mathrm{/}2$ and $d=\theta -{\theta }_j$. Since the two angles lie in $[0,\pi ]$, $\mathrm{\mid }d\mathrm{\mid }\mathrm{/}2\le \min (s,\pi -s)$. The addition/subtraction formulas in [F5] give $\sin {\theta }_j,\sin \theta \le \sin s+\mathrm{\mid }\sin (d\mathrm{/}2)\mathrm{\mid }$; the monotonicity and supplementary identity in [F5] then give $\mathrm{\mid }\sin (d\mathrm{/}2)\mathrm{\mid }\le \sin s$, so each numerator is at most $2\sin s$. Those same formulas give $\mathrm{\mid }\cos \theta -\cos {\theta }_j\mathrm{\mid }=2\sin s\sin (\mathrm{\mid }d\mathrm{\mid }\mathrm{/}2)$, and [F4] gives $\sin (\mathrm{\mid }d\mathrm{\mid }\mathrm{/}2)\ge \mathrm{\mid }d\mathrm{\mid }\mathrm{/}\pi$. Thus both ratios $\sin {\theta }_j\mathrm{/}\mathrm{\mid }\cos \theta -\cos {\theta }_j\mathrm{\mid }$ and $\sin \theta \mathrm{/}\mathrm{\mid }\cos \theta -\cos {\theta }_j\mathrm{\mid }$ are at most $\pi \mathrm{/}{d}_j$.

For roots, [F3] and step 2.1 give $\mathrm{\mid }{\mathrm{\ell }}_{j,n}^R(\cos \theta )\mathrm{\mid }\le \pi \mathrm{\mid }\cos ((n+1)\theta )\mathrm{\mid }\mathrm{/}((n+1)d_j)$. At the nearest node $k$, $\cos ((n+1){\theta }_k)=0$, and the cosine addition formula plus [F4] gives $\mathrm{\mid }\cos ((n+1)\theta )\mathrm{\mid }\le (n+1)d_k$, so its term is at most $\pi$. For other nodes use $\mathrm{\mid }\cos ((n+1)\theta )\mathrm{\mid }\le 1$ and step 1.1; summing over at most two nodes per distance rank yields ${\sum }_j\mathrm{\mid }{\mathrm{\ell }}_{j,n}^R(\cos \theta )\mathrm{\mid }\le \pi +2{\sum }_{r=1}^{n}1\mathrm{/}(r-\frac{1}{2})$. At a node the cardinal sum is $1$.

For Lobatto nodes, [F3] and step 2.1 give $\mathrm{\mid }{\mathrm{\ell }}_{j,n}^L(\cos \theta )\mathrm{\mid }\le \pi c_j\mathrm{\mid }\sin (n\theta )\mathrm{\mid }\mathrm{/}(n{d}_j)$. At the nearest node $k$, $\sin (n{\theta }_k)=0$, so [F4] gives $\mathrm{\mid }\sin (n\theta )\mathrm{\mid }\le n{d}_k$ and its term is at most $\pi$ because $c_k\le 1$. For other nodes use $\mathrm{\mid }\sin (n\theta )\mathrm{\mid }\le 1$ and step 1.1; summing over at most two nodes per distance rank yields ${\sum }_j\mathrm{\mid }{\mathrm{\ell }}_{j,n}^L(\cos \theta )\mathrm{\mid }\le \pi +2{\sum }_{r=1}^{n}1\mathrm{/}(r-\frac{1}{2})$. At a node the cardinal sum is $1$.

Since $1\mathrm{/}(r-\frac{1}{2})\le 2\mathrm{/}r$, the shifted sum is at most $2H_n$, where $H_n={\sum }_{r=1}^{n}1\mathrm{/}r$. For $r\ge 2$, $1\mathrm{/}r\le {\int }_{r-1}^{r}dt\mathrm{/}t$, so [F6] gives $H_n\le 1+\log n$. Positivity of the real image of $n$ is [F7], so these logarithms are defined. The integral formula also gives $0=\log 1\le \log n\le \log (n+1)$ and $\log 2\le \log (n+1)$ by integrating $1\mathrm{/}t>0$ over $[1,n]$, $[n,n+1]$, and $[2,n+1]$. Since $\log 2={\int }_1^{2}dt\mathrm{/}t>0$ and $\pi >0$, we have $C>0$ and $1<C\log 2$. Thus both sums are at most $\pi +4+4\log n\le (4+(\pi +4)\mathrm{/}\log 2)\log (n+1)$. By [F8], the angular supremum is over exactly $[-1,1]$; taking it and using [F2] proves both bounds. At $n=0$, each one-node operator has norm $1$ directly.