Editing Chebyshev nodes

{{Short description|Roots of the Chebyshev polynomials of the first kind}}
[[File:Chebyshev nodes from the circle.png|thumb|Chebyshev zeros (solid dots, red lines) and extrema (hollow squares, blue lines) are the projection of two sets of equispaced points on the unit circle onto the {{mvar|x}}-axis. {{math|2''n''}} equispaced points on the circle project onto {{mvar|n}} Chebyshev zeros or {{mvar|n+1}} Chebyshev extrema. (Here {{math|1=''n'' = 5}}.)]] 
[[File:Chebyshev nodes.png|thumb|The Chebyshev zeros (solid dots) are roots of a Chebyshev polynomial of the first kind (red). The Chebyshev extrema (hollow squares) are roots of a Chebyshev polynomial of the second kind (blue), and also the extrema (crosses) of a Chebyshev polynomial of the first kind.]]

In [[numerical analysis]], '''Chebyshev nodes''' (also called '''Chebyshev points''' or a '''Chebyshev grid''') are a set of specific [[algebraic number]]s used as nodes for [[polynomial interpolation]] and [[numerical integration]]. They are the [[Projection (linear algebra)|projection]] of a set of equispaced points on the [[unit circle]] onto the [[real interval]] <math>[-1, 1]</math>, the circle's [[diameter]].

There are two kinds of Chebyshev nodes. The {{tmath|n}} ''Chebyshev nodes of the first kind'', also called the '''Chebyshev–Gauss nodes'''<ref>The name ''Chebyshev–Gauss nodes'' comes from the use of Chebyshev zeros in numerical integration, which can be seen as a variant of [[Gaussian quadrature]].</ref> or '''Chebyshev zeros''', are the [[Zero of a function|zeros]] of a [[Chebyshev polynomial]] of the first kind, {{tmath|T_n}}. The corresponding {{tmath|n+1}} ''Chebyshev nodes of the second kind'', also called the '''Chebyshev–Lobatto nodes'''<ref>The name ''Chebyshev–Lobatto nodes'' comes from [[Rehuel Lobatto]], who made a variant of Gaussian quadrature, known as ''[[Lobatto quadrature]]'', whose nodes included the ends of the interval, a feature shared by the Chebyshev extrema.</ref> or '''Chebyshev extrema''', are the [[Maximum and minimum|extrema]] of {{tmath|T_n}}, which are also the zeros of a Chebyshev polynomial of the second kind, {{tmath|U_{n-1} }}, along with the two endpoints of the interval. Both types of numbers are commonly referred to as ''Chebyshev nodes'' or ''Chebyshev points'' in literature.<ref>{{harvnb|Trefethen|2013|pp=7}}</ref> They are named after 19th century Russian mathematician [[Pafnuty Chebyshev]], who first introduced Chebyshev polynomials.

Unlike some other interpolation nodes, the Chebyshev nodes "nest": the existing nodes are retained when doubling the number of nodes, reducing computation for each grid refinement by half. Polynomial interpolants constructed from Chebyshev nodes minimize the effect of [[Runge's phenomenon]].<ref>{{harvnb|Fink|Mathews|1999|pp=236–238}}</ref> They can be easily converted to a representation as a weighted sum of Chebyshev polynomials using the [[fast Fourier transform]].

==Definition==
[[File:ChebyshevNodes2.jpg|thumb|Chebyshev nodes of both kinds from <math>n=2</math> to <math>n=50</math>.]]

For a given positive integer <math>n</math>, the {{tmath|n}} Chebyshev nodes of the first kind are given by

<math display="block">x_k = \cos\frac{\bigl(k+\tfrac12\bigr)\pi}{n}, \quad k = 0, \ldots, n-1.</math>

This is the projection of {{tmath|2n}} equispaced points on the unit circle onto the interval {{tmath|[-1, 1]}}, the circle's diameter. These points are also the roots of {{tmath|T_n}}, the Chebyshev polynomial of the first kind with degree {{tmath|n}}.

The {{tmath|n+1}} Chebyshev nodes of the second kind are given by

<math display="block">x_k = \cos\frac{k\pi}{n}, \quad k = 0, \ldots, n.</math>

This is also the projection of {{tmath|2n}} equispaced points on the unit circle onto {{tmath|[-1, 1]}}, this time including the endpoints of the interval, each of which is only the projection of one point on the circle rather than two. These points are also the extrema of {{tmath|T_n}} in {{tmath|[-1, 1] }}, the places where it takes the value {{tmath|\pm1}}.<ref>{{harvnb|Trefethen|2013|pp=14}}</ref> The interior points among the nodes, not including the endpoints, are also the zeros of {{tmath|U_{n-1} }}, a Chebyshev polynomial of the second kind, a rescaling of the derivative of {{tmath|T_n}}.

For nodes over an arbitrary interval <math>[a,b]</math> an [[affine transformation]] from <math>[-1,1]</math> can be used:
<math display="block">\tilde{x}_k = \tfrac12(a + b) + \tfrac12(b - a) x_k.</math>

== Properties ==

Both kinds of nodes are always symmetric about zero, the midpoint of the interval.

==Examples==

The node sets for the first few integers <math>n</math> are:
<math display="block">\begin{align}
\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{align}</math>

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 {{math|''f''}} on the interval <math>[-1,+1]</math> and <math>n</math> points <math>x_1,  x_2, \ldots , x_n,</math> in that interval, the interpolation polynomial is that unique polynomial <math>P_{n-1}</math> of degree at most <math>n - 1</math> which has value <math>f(x_i)</math> at each point <math>x_i</math>. The interpolation error at <math>x</math> is
<math display="block">f(x) - P_{n-1}(x) = \frac{f^{(n)}(\xi)}{n!} \prod_{i=1}^n (x-x_i) </math>
for some <math>\xi</math> (depending on {{mvar|x}}) in {{closed-closed|−1, 1}}.<ref>{{harvnb|Stewart|1996|loc= (20.3)}}</ref> So it is logical to try to minimize
<math display="block">\max_{x \in [-1,1]} \biggl| \prod_{i=1}^n (x-x_i) \biggr|. </math>

This product is a ''[[monic polynomial|monic]]'' polynomial of degree {{mvar|n}}.  It may be shown that the maximum absolute value (maximum norm) of any such polynomial is bounded from below by {{math|2<sup>1−''n''</sup>}}.  This bound is attained by the scaled Chebyshev polynomials {{math|2<sup>1−''n''</sup> ''T''<sub>''n''</sub>}}, which are also monic. (Recall that {{math|{{!}}''T''<sub>''n''</sub>(''x''){{!}} ≤ 1}} for {{math|''x'' ∈ [−1, 1]}}.<ref>{{harvnb|Stewart|1996|loc= Lecture 20, §14}}</ref>) Therefore, when the interpolation nodes {{math|''x''<sub>''i''</sub>}} are the roots of {{math|''T''<sub>''n''</sub>}}, the error satisfies
<math display="block">\left|f(x) - P_{n-1}(x)\right| \le \frac{1}{2^{n - 1}n!} \max_{\xi \in [-1,1]} \left| f^{(n)} (\xi) \right|.</math>
For an arbitrary interval [''a'', ''b''] a change of variable shows that
<math display="block">\left|f(x) - P_{n-1}(x)\right| \le \frac{1}{2^{n - 1}n!} \left(\frac{b-a}{2}\right)^n \max_{\xi \in [a,b]} \left|f^{(n)} (\xi)\right|.</math>

== Modified even-order nodes ==
Some applications for interpolation nodes, such as the design of equally terminated passive [[Chebyshev filter]]s, cannot use even-order Chebyshev nodes directly due to the lack of a root at 0. Instead, the Chebyshev nodes can be moved toward zero, with a double root at zero directly, using a transformation:<ref name=":02">{{Cite book |last=Saal |first=Rudolf |url=https://archive.org/details/handbuchzumfilte0000saal |title=Handbook of Filter Design |publisher=Allgemeine Elektricitäts-Gesellschaft |date=January 1979 |isbn=3-87087-070-2 |edition=1st |location=Munich, Germany |pages=25, 26, 56-61, 116, 117 |language=English, German}}</ref>

<math display=block>\tilde{x}_k = \operatorname{sgn}(x_k)\sqrt{\frac{x_k^2-x_{n/2}^2}{1-x_{n/2}^2}}</math>

For example, Chebyshev nodes of the first kind of order 4 are <math>{0.9239,0.3827,-0.3827,-0.9239}</math>, with <math>x_{n/2} = 0.382683</math>. Applying the transformation yields new nodes <math>{0.910180, 0, 0, -0.910180}</math>. The modified even-order nodes now include zero twice.

== See also ==
* [[Chebfun]]
* [[Chebyshev–Gauss quadrature]]
* [[Lebesgue constant]]

== Notes ==
{{reflist|colwidth=30em}}

==References==
{{refbegin}}
* {{ cite book | last1 = Fink | first1 = Kurtis D. | first2 = John H. | last2 = Mathews | title = Numerical Methods using MATLAB | location = Upper Saddle River NJ | publisher = Prentice Hall | year = 1999 | edition = 3rd }}
* {{ cite book | last1 = Stewart | first1 = Gilbert W. | title = Afternotes on Numerical Analysis | publisher = [[Society for Industrial and Applied Mathematics|SIAM]] | isbn = 978-0-89871-362-6 | year = 1996 }}
* {{ citation | first = Lloyd N. | last = Trefethen | title = Approximation Theory and Approximation Practice | publisher = SIAM | year = 2013 | url = https://people.maths.ox.ac.uk/trefethen/ATAP/ }}
{{refend}}

==Further reading==
*Burden, Richard L.; Faires, J. Douglas: ''Numerical Analysis'', 8th ed., pages 503–512, {{ISBN|0-534-39200-8}}.

{{Algebraic numbers}}

[[Category:Numerical analysis]]
[[Category:Algebraic numbers]]