Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Chebyshev nodes
open-in-new
<h2 id="definition">Definition</h2> <p>For a given positive integer n {\displaystyle n} , the n {\displaystyle n} Chebyshev nodes of the first kind are given by </p><p> x k = cos ( k + 1 2 ) π n , k = 0 , … , n − 1. {\displaystyle x_{k}=\cos {\frac {{\bigl (}k+{\tfrac {1}{2}}{\bigr )}\pi }{n}},\quad k=0,\ldots ,n-1.} </p><p>This is the projection of 2 n {\displaystyle 2n} equispaced points on the unit circle onto the interval [ − 1 , 1 ] {\displaystyle [-1,1]} , the circle's diameter. These points are also the roots of T n {\displaystyle T_{n}} , the Chebyshev polynomial of the first kind with degree n {\displaystyle n} . </p><p>The n + 1 {\displaystyle n+1} Chebyshev nodes of the second kind are given by </p><p> x k = cos k π n , k = 0 , … , n . {\displaystyle x_{k}=\cos {\frac {k\pi }{n}},\quad k=0,\ldots ,n.} </p><p>This is also the projection of 2 n {\displaystyle 2n} equispaced points on the unit circle onto [ − 1 , 1 ] {\displaystyle [-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 T n {\displaystyle T_{n}} in [ − 1 , 1 ] {\displaystyle [-1,1]} , the places where it takes the value ± 1 {\displaystyle \pm 1} .<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> The interior points among the nodes, not including the endpoints, are also the zeros of U n − 1 {\displaystyle U_{n-1}} , a Chebyshev polynomial of the second kind, a rescaling of the derivative of T n {\displaystyle T_{n}} . </p><p>For nodes over an arbitrary interval [ a , b ] {\displaystyle [a,b]} an <a href="/facts/Affine_transformation/BD7yDr10">affine transformation</a> from [ − 1 , 1 ] {\displaystyle [-1,1]} can be used: x ~ k = 1 2 ( a + b ) + 1 2 ( b − a ) x k . {\displaystyle {\tilde {x}}_{k}={\tfrac {1}{2}}(a+b)+{\tfrac {1}{2}}(b-a)x_{k}.} </p> <h2 id="properties">Properties</h2> <p>Both kinds of nodes are always symmetric about zero, the midpoint of the interval. </p> <h2 id="examples">Examples</h2> <p>The node sets for the first few integers n {\displaystyle n} are: roots ( T 0 ) = { } , roots ( U 0 ) = { } , extrema ( T 1 ) = { − 1 , + 1 } , roots ( T 1 ) = { 0 } , roots ( U 1 ) = { 0 } , extrema ( T 2 ) = { − 1 , 0 , + 1 } , roots ( T 2 ) = { − 1 / 2 , + 1 / 2 } , roots ( U 2 ) = { − 1 / 2 , + 1 / 2 } , extrema ( T 3 ) = { − 1 , − 1 / 2 , + 1 / 2 , + 1 } {\displaystyle {\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}}} </p><p>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. </p> <h2 id="approximation">Approximation</h2> <p>The Chebyshev nodes are important in <a href="/facts/Approximation_theory/87AaPXLp">approximation theory</a> because they form a particularly good set of nodes for <a href="/facts/Polynomial_interpolation/DmnuxaKT">polynomial interpolation</a>. Given a function <i>f</i> on the interval [ − 1 , + 1 ] {\displaystyle [-1,+1]} and n {\displaystyle n} points x 1 , x 2 , … , x n , {\displaystyle x_{1},x_{2},\ldots ,x_{n},} in that interval, the interpolation polynomial is that unique polynomial P n − 1 {\displaystyle P_{n-1}} of degree at most n − 1 {\displaystyle n-1} which has value f ( x i ) {\displaystyle f(x_{i})} at each point x i {\displaystyle x_{i}} . The interpolation error at x {\displaystyle x} is f ( x ) − P n − 1 ( x ) = f ( n ) ( ξ ) n ! ∏ i = 1 n ( x − x i ) {\displaystyle f(x)-P_{n-1}(x)={\frac {f^{(n)}(\xi )}{n!}}\prod _{i=1}^{n}(x-x_{i})} for some ξ {\displaystyle \xi } (depending on x) in [−1, 1].<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> So it is logical to try to minimize max x ∈ [ − 1 , 1 ] | ∏ i = 1 n ( x − x i ) | . {\displaystyle \max _{x\in [-1,1]}{\biggl |}\prod _{i=1}^{n}(x-x_{i}){\biggr |}.} </p><p>This product is a <i><a href="/facts/Monic_polynomial/4JzuIJ5R">monic</a></i> polynomial of degree n. It may be shown that the maximum absolute value (maximum norm) of any such polynomial is bounded from below by 21−<i>n</i>. This bound is attained by the scaled Chebyshev polynomials 21−<i>n</i> <i>T</i><i>n</i>, which are also monic. (Recall that |<i>T</i><i>n</i>(<i>x</i>)| ≤ 1 for <i>x</i> ∈ [−1, 1].<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>) Therefore, when the interpolation nodes <i>x</i><i>i</i> are the roots of <i>T</i><i>n</i>, the error satisfies | f ( x ) − P n − 1 ( x ) | ≤ 1 2 n − 1 n ! max ξ ∈ [ − 1 , 1 ] | f ( n ) ( ξ ) | . {\displaystyle \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 [<i>a</i>, <i>b</i>] a change of variable shows that | f ( x ) − P n − 1 ( x ) | ≤ 1 2 n − 1 n ! ( b − a 2 ) n max ξ ∈ [ a , b ] | f ( n ) ( ξ ) | . {\displaystyle \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|.} </p> <h2 id="modified-even-order-nodes">Modified even-order nodes</h2> <p>Some applications for interpolation nodes, such as the design of equally terminated passive <a href="/facts/Chebyshev_filter/bMllKQan">Chebyshev filters</a>, 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:<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p> x ~ k = sgn ( x k ) x k 2 − x n / 2 2 1 − x n / 2 2 {\displaystyle {\tilde {x}}_{k}=\operatorname {sgn} (x_{k}){\sqrt {\frac {x_{k}^{2}-x_{n/2}^{2}}{1-x_{n/2}^{2}}}}} </p><p>For example, Chebyshev nodes of the first kind of order 4 are 0.9239 , 0.3827 , − 0.3827 , − 0.9239 {\displaystyle {0.9239,0.3827,-0.3827,-0.9239}} , with x n / 2 = 0.382683 {\displaystyle x_{n/2}=0.382683} . Applying the transformation yields new nodes 0.910180 , 0 , 0 , − 0.910180 {\displaystyle {0.910180,0,0,-0.910180}} . The modified even-order nodes now include zero twice. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Chebfun/Vn3GfgIa">Chebfun</a></li> <li><a href="/facts/Chebyshev%25E2%2580%2593Gauss_quadrature/dfWEokpd">Chebyshev–Gauss quadrature</a></li> <li><a href="/facts/Lebesgue_constant/MWLd59D4">Lebesgue constant</a></li></ul> <h2 id="notes">Notes</h2> <ul><li>Fink, Kurtis D.; Mathews, John H. (1999). <i>Numerical Methods using MATLAB</i> (3rd ed.). Upper Saddle River NJ: Prentice Hall.</li> <li>Stewart, Gilbert W. (1996). <i>Afternotes on Numerical Analysis</i>. <a href="/facts/Society_for_Industrial_and_Applied_Mathematics/2HY4T5WY">SIAM</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-89871-362-6.</li> <li>Trefethen, Lloyd N. (2013), <a href="https://people.maths.ox.ac.uk/trefethen/ATAP/"><i>Approximation Theory and Approximation Practice</i></a>, SIAM</li></ul> <h2 id="further-reading">Further reading</h2> <ul><li>Burden, Richard L.; Faires, J. Douglas: <i>Numerical Analysis</i>, 8th ed., pages 503–512, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-534-39200-8.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="/wiki/Gaussian_quadrature" target="_blank">/wiki/Gaussian_quadrature</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="/wiki/Rehuel_Lobatto" target="_blank">/wiki/Rehuel_Lobatto</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Trefethen 2013, pp. 7 - Trefethen, Lloyd N. (2013), Approximation Theory and Approximation Practice, SIAM <a href="https://people.maths.ox.ac.uk/trefethen/ATAP/" target="_blank">https://people.maths.ox.ac.uk/trefethen/ATAP/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Fink & Mathews 1999, pp. 236–238 - Fink, Kurtis D.; Mathews, John H. (1999). Numerical Methods using MATLAB (3rd ed.). Upper Saddle River NJ: Prentice Hall. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Trefethen 2013, pp. 14 - Trefethen, Lloyd N. (2013), Approximation Theory and Approximation Practice, SIAM <a href="https://people.maths.ox.ac.uk/trefethen/ATAP/" target="_blank">https://people.maths.ox.ac.uk/trefethen/ATAP/</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Stewart 1996, (20.3) - Stewart, Gilbert W. (1996). Afternotes on Numerical Analysis. SIAM. ISBN 978-0-89871-362-6. <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Stewart 1996, Lecture 20, §14 - Stewart, Gilbert W. (1996). Afternotes on Numerical Analysis. SIAM. ISBN 978-0-89871-362-6. <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>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. <a href="3-87087-070-2" target="_blank">3-87087-070-2</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> </ol>