Content deleted Content added
Line 15:
===On the choice of initialization===
The reason for the Chebyshev nodes being a common choice for the initial approximation is in its hehavior in the theory of polynomial interpolation.
For the initialization of the optimization problem for function ''f'' by the Lagrange interpolant ''L''<sub>n</sub>(''f''), it can be shown that this initial approximation is bounded by
:<math>\lVert f - L_n(f)\rVert_\infty \le (1 + \lVert L_n\rVert_\infty) \inf_{p \in P_n} \lVert f - p\rVert</math>
with the norm or [[Lebesgue constant (interpolation)|Lebesgue constant]] of the Lagrange interpolation operator ''L''<sub>''n''</sub> of the nodes (''t''<sub>1</sub>, ..., ''t''<sub>''n'' + 1</sub>) being
:<math>\overline{\Lambda}_n(T) = \max_{-1 \le x \le 1} \lambda_n(T; x),</math>
<math>\lVert L_n\rVert_\infty = \left\| \Lambda_t \right\|, \quad \Lambda_t = \sum_{j = 1}^{n + 1} \left| \prod_{\stackrel{i = 1}{i \ne j}}^{n + 1} \frac{(\cdot - t_i)}{(t_j - t_i)}\right|</math>▼
''T'' being the zeros of the Chebyshev polynomials, and the Lebesgue functions being
▲:<math>\
Kilgore<ref>[http://dx.doi.org/10.1016/0021-9045(78)90013-8 T. A. Kilgore, "A characterization of the Lagrange interpolating projection with minimal Tchebycheff norm", J. Approx. Theory 24, 273 (1978).]</ref> and de Boor & Pinkus<ref>[http://dx.doi.org/10.1016/0021-9045(78)90014-X C. de Boor and A. Pinkus, "Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation", J. Approx. Theory 24, 289 (1978).]</ref>
For Chebyshev nodes, which provides a suboptimal, but analytically explicit choice, the asymptotic behavior is known as<ref>F. W. Luttmann and T. J. Rivlin, "Some numerical experiments in the theory of polynomial interpolation", IBM J. Res. Develop. 9, 187 (1965).</ref>
:<math>\overline{\Lambda}_n(T) = \frac{2}{\pi} \log(n + 1) + \frac{2}{\pi}\left(\gamma + \log\frac{8}{\pi}\right) + \alpha_{n + 1}</math>
(''γ'' being the [[Euler's constant]]) with
:<math>0 < \alpha_n < \frac{\pi}{72 n^2}</math> for <math>n \ge 1,</math>
and upper bound<ref>T. Rivlin, "The Lebesgue constants for polynomial interpolation", in ''Proceedings of the Int. Conf. on Functional Analysis and Its Application'', edited by H. G. Garnier ''et al.'' (Springer-Verlag, Berlin, 1974), p. 422; ''The Chebyshev polynomials'' (Wiley-Interscience, New York, 1974).</ref>
:<math>\overline{\Lambda}_n(T) \le \frac{2}{\pi} \log(n + 1) + 1</math>
Lev Brutman<ref>[http://dx.doi.org/10.1137/0715046 L. Brutman, "On the Lebesgue Function for Polynomial Interpolation", SIAM J. Numer. Anal. 15, 694 (1978).]</ref> obtained the bound for <math>n \ge 3</math>, and <math>\hat{T}</math> being the zeros of the expanded Chebyshev polynomials:
:<math>\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < \overline{\Lambda}_3 - \frac{1}{6} \cot \frac{\pi}{8} + \frac{\pi}{64} \frac{1}{\sin^2(3\pi/16)} - \frac{2}{\pi}(\gamma - \log\pi)\approx 0.201.</math>
Rüdiger Günttner<ref>[http://dx.doi.org/10.1137/0717043 R. Günttner, "Evaluation of Lebesgue Constants", SIAM J. Numer. Anal. 17, 512 (1980).]</ref> obtained from a sharper estimate for <math>n \ge 40</math>
:<math>\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < 0.0196.</math>
▲Kilgore<ref>[http://dx.doi.org/10.1016/0021-9045(78)90013-8 T. A. Kilgore, "A characterization of the Lagrange interpolating projection with minimal Tchebycheff norm", J. Approx. Theory 24, 273 (1978).]</ref> and de Boor & Pinkus<ref>[http://dx.doi.org/10.1016/0021-9045(78)90014-X C. de Boor and A. Pinkus, "Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation", J. Approx. Theory 24, 289 (1978).]</ref> prooved that there exists an unique ''t''<sub>''i''</sub> for each ''L''<sub>''n''</sub>, although not known explicitly for (ordinary) polynomials.
==Variants==
| |||