Chebyshev nodes

In numerical analysis, Chebyshev nodes of the first and second kind are two sets of specific real algebraic numbers, often used as nodes for polynomial interpolation. Interpolants constructed from these nodes minimize the effect of Runge's phenomenon.^[1]

The Chebyshev nodes are defined as zeroes or extrema of Chebyshev polynomials, and can also be obtained by projections of equispaced points on the unit circle onto the real interval $[-1,1],$ the diameter of the circle.

Definition

Chebyshev nodes of both kinds from $n=2$ to $n=50$ .

The Chebyshev nodes of the first kind, also called Chebyshev points or Chebyshev zeroes, are $x_{k}=\cos \left({\frac {2k+1}{2n}}\pi \right),\quad k=0,\ldots ,n-1.$ These are the roots of $T_{n}$ , the Chebyshev polynomial of the first kind with degree $n\geq 1$ .

The Chebyshev nodes of the second kind, also called Chebyshev-Lobatto points or Chebyshev extrema, are $x_{k}=\cos \left({\frac {k}{n}}\pi \right),\quad k=0,\ldots ,n.$ These are the points where $T_{n+1}$ (for $n\geq 0$ ) takes its extreme values $\pm 1$ .^[2] They include the end points -1 and +1, which are extrema only with respect to the domain [-1,+1]. If we consider $n\geq 1$ and omit the two end points (i.e. restrict $k$ to $1,\ldots ,n-1$ ), then the remaining points are the roots of $U_{n}$ , the Chebyshev polynomial of the second kind with degree $n$ .

Depending on context, unqualified terms like Chebyshev nodes may refer to either the first or the second kind.

Remarks

While the second-kind nodes include the interval end points -1 and +1, the first-kind nodes do not. Both kinds of nodes are symmetric about the midpoint of the interval. The midpoint is a node iff n is odd.

For nodes over an arbitrary interval an affine transformation from [-1,1] to [a,b] can be used: ${\tilde {x}}_{k}={\frac {(a+b)}{2}}+{\frac {(b-a)}{2}}x_{k}.$

Examples

The node sets for the first few integers $n$ are: ${\begin{aligned}{\text{roots}}(T_{0})&=\{\},&{\text{roots}}(U_{0})&=\{\},&{\text{extrema}}(T_{1})&=\{-1,+1\}\\{\text{roots}}(T_{1})&=\{0\},&{\text{roots}}(U_{1})&=\{0\},&{\text{extrema}}(T_{2})&=\{-1,0,+1\}\\{\text{roots}}(T_{2})&=\{-1/{\sqrt {2}},+1/{\sqrt {2}}\},&{\text{roots}}(U_{2})&=\{-1/2,+1/2\},&{\text{extrema}}(T_{3})&=\{-1,-1/2,+1/2,+1\}\\\end{aligned}}$

While these sets are sorted by ascending values, the defining formulas given above generate the Chebyshev nodes in reverse order from the greatest to the smallest.

Approximation

The Chebyshev nodes are important in approximation theory because they form a particularly good set of nodes for polynomial interpolation. Given a function $f$ on the interval $[-1,+1]$ and $n$ points $x_{1},x_{2},\ldots ,x_{n},$ in that interval, the interpolation polynomial is that unique polynomial $P_{n-1}$ of degree at most $n-1$ which has value $f(x_{i})$ at each point $x_{i}$ . The interpolation error at $x$ is $f(x)-P_{n-1}(x)={\frac {f^{(n)}(\xi )}{n!}}\prod _{i=1}^{n}(x-x_{i})$ for some $\xi$ (depending on $x$ ) in $[-1, 1]$ .^[3] So it is logical to try to minimize $\max _{x\in [-1,1]}{\biggl |}\prod _{i=1}^{n}(x-x_{i}){\biggr |}.$

This product is a monic polynomial of degree $n$ . It may be shown that the maximum absolute value (maximum norm) of any such polynomial is bounded from below by $2 1- n$ . This bound is attained by the scaled Chebyshev polynomials $2 1- n T n$ , which are also monic. (Recall that $| T n (x)| \leq 1$ for $x \in [-1, 1]$ .^[4]) Therefore, when the interpolation nodes $x i$ are the roots of $T n$ , the error satisfies $\left|f(x)-P_{n-1}(x)\right|\leq {\frac {1}{2^{n-1}n!}}\max _{\xi \in [-1,1]}\left|f^{(n)}(\xi )\right|.$ For an arbitrary interval [a, b] a change of variable shows that $\left|f(x)-P_{n-1}(x)\right|\leq {\frac {1}{2^{n-1}n!}}\left({\frac {b-a}{2}}\right)^{n}\max _{\xi \in [a,b]}\left|f^{(n)}(\xi )\right|.$

Even order modified Chebyshev nodes

Many applications for Chebyshev nodes, such as the design of equally terminated passive Chebyshev filters, cannot use Chebyshev nodes directly, due to the lack of a root at 0. However, the Chebyshev nodes may be modified into a usable form by translating the roots down such that the lowest roots are moved to zero, thereby creating two roots at zero of the modified Chebyshev nodes.^[5]

The even order modification translation is:

$X_{k}Even={\sqrt {\frac {X_{k}^{2}-X_{n/2}^{2}}{1-X_{n/2}^{2}}}}{\text{ For }}n>2$

The sign of the ${\sqrt {}}$ function is chosen to be the same as the sign of $X_{k}$ .

For example, the Chebyshev nodes for a 4th order Chebyshev function are, {0.92388,0.382683,-0.382683,-0.92388}, and $X_{n/2}^{2}$ is $0.382683^{2}$ , or 0.146446. Running all the nodes through the translation yields $X_{k}Even$ to be {0.910180, 0, 0, -0.910180}.

The modified even order Chebyshev nodes now contains two nodes of zero, and is suitable for use in designing even order Chebyshev filters with equally terminated passive element networks.

Notes

^ Fink & Mathews 1999, pp. 236–238
^ Trefethen 2013, pp. 14
^ Stewart 1996, (20.3)
^ Stewart 1996, Lecture 20, §14
^ Saal, Rudolf (January 1979). Handbook of Filter Design (in English and German) (1st ed.). Munich, Germany: Allgemeine Elektricitäts-Gesellschaft. pp. 25, 26, 56–61, 116, 117. ISBN 3-87087-070-2.

References

Fink, Kurtis D.; Mathews, John H. (1999). Numerical Methods using MATLAB (3rd ed.). Upper Saddle River NJ: Prentice Hall.
Stewart, Gilbert W. (1996). Afternotes on Numerical Analysis. SIAM. ISBN 978-0-89871-362-6.
Trefethen, Lloyd N. (2013), Approximation Theory and Approximation Practice, SIAM