Английская Википедия:Chebyshev nodes
In numerical analysis, Chebyshev nodes are a set of specific real algebraic numbers, used as nodes for polynomial interpolation. They are the projection of equispaced points on the unit circle onto the real interval <math>[-1, 1],</math> the diameter of the circle.
The Chebyshev nodes of the first kind, also called the Chebyshev zeros, are the zeros of the Chebyshev polynomials of the first kind. The Chebyshev nodes of the second kind, also called the Chebyshev extrema, are the extrema of the Chebyshev polynomials of the first kind, which are also the zeros of the Chebyshev polynomials of the second kind. Both of these sets of numbers are commonly referred to as Chebyshev nodes in literature.[1] Polynomial interpolants constructed from these nodes minimize the effect of Runge's phenomenon.[2]
Definition
For a given positive integer Шаблон:Mvar the Chebyshev nodes of the first kind in the open interval Шаблон:Open-open are <math display="block">x_k = \cos\left(\frac{2k-1}{2n}\pi\right), \quad k = 1, \ldots, n.</math>
These are the roots of the Chebyshev polynomials of the first kind with degree Шаблон:Mvar. For nodes over an arbitrary interval Шаблон:Closed-closed an affine transformation can be used: <math display="block">x_k = \frac{1}{2} (a + b) + \frac{1}{2} (b - a) \cos\left(\frac{2k-1}{2n}\pi\right), \quad k = 1, \ldots, n.</math>
Similarly, for a given positive integer Шаблон:Mvar the Chebyshev nodes of the second kind in the closed interval Шаблон:Closed-closed are <math display="block">x_k = \cos\left(\frac{k-1}{n-1}\pi\right), \quad k = 1, \ldots, n.</math>
These are the roots of the Chebyshev polynomials of the second kind with degree Шаблон:Mvar. For nodes over an arbitrary interval Шаблон:Closed-closed an affine transformation can be used as above. The Chebyshev nodes of the second kind are also referred to as Chebyshev-Lobatto points or Chebyshev extreme points.[3] Note that the Chebyshev nodes of the second kind include the end points of the interval while the Chebyshev nodes of the first kind do not include the end points. These formulas generate Chebyshev nodes which are sorted from greatest to least on the real interval.
Both kinds of nodes are always symmetric about the midpoint of the interval. Hence, for odd Шаблон:Mvar, both kinds of nodes will include the midpoint. Geometrically, for both kinds of nodes, we first place Шаблон:Mvar points on the upper half of the unit circle with equal spacing between them. Then the points are projected down to the Шаблон:Mvar-axis. The projected points on the Шаблон:Mvar-axis are called Chebyshev nodes.
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 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) in Шаблон:Closed-closed.[4] So it is logical to try to minimize <math display="block">\max_{x \in [-1,1]} \left| \prod_{i=1}^n (x-x_i) \right|. </math>
This product is a monic polynomial of degree Шаблон:Mvar. It may be shown that the maximum absolute value (maximum norm) of any such polynomial is bounded from below by Шаблон:Math. This bound is attained by the scaled Chebyshev polynomials Шаблон:Math, which are also monic. (Recall that Шаблон:Math for Шаблон:Math.[5]) Therefore, when the interpolation nodes Шаблон:Math are the roots of Шаблон:Math, 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>
Notes
References
Further reading
- Burden, Richard L.; Faires, J. Douglas: Numerical Analysis, 8th ed., pages 503–512, Шаблон:ISBN.