Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Some problems in optimally stable Lagrangian differentiation


Author: Herbert E. Salzer
Journal: Math. Comp. 28 (1974), 1105-1115
MSC: Primary 65D25
DOI: https://doi.org/10.1090/S0025-5718-1974-0368391-0
MathSciNet review: 0368391
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In many practical problems in numerical differentiation of a function $ f(x)$ that is known, observed, measured, or found experimentally to limited accuracy, the computing error is often much more significant than the truncating error. In numerical differentiation of the n-point Lagrangian interpolation polynomial, i.e., $ {f^{(k)}}(x) \sim \Sigma _{i = 1}^nL_i^{n(k)}(x)f({x_i})$, a criterion for optimal stability is minimization of $ \Sigma _{i = 1}^n\vert L_i^{n(k)}(x)\vert$. Let $ L \equiv L(n,k,{x_1}, \ldots ,{x_n};x\;{\text{or}}\;{x_0}) = \Sigma _{i = 1}^n\vert L_i^{n(k)}(x\;{\text{or}}\;{x_0})\vert$. For $ {x_i}$ and fixed $ x = {x_0}$ in $ [ - 1,1]$, one problem is to find the n $ {x_i}$'s to give $ {L_0} \equiv {L_0}(n,k,{x_0}) = \min L$. When the truncation error is negligible for any $ {x_0}$ within $ [ - 1,1]$, a second problem is to find $ {x_0} = {x^\ast}$ to obtain $ {L^\ast} \equiv {L^\ast}(n,k) = \min {L_0} = \min \min L$. A third much simpler problem, for $ {x_i}$ equally spaced, $ {x_1} = - 1,{x_n} = 1$, is to find $ \bar x$ to give $ \bar L \equiv \bar L(n,k) = \min L$. For lower values of n, some results were obtained on $ {L_0}$ and $ {L^\ast}$ when $ k = 1$, and on $ \bar L$ when $ k = 1$ and 2 by direct calculation from available tables of $ L_i^{n(k)}(x)$. The relation of $ {L_0},{L^\ast}$ and $ \bar L$ to equally spaced points, Chebyshev points, Chebyshev polynomials $ {T_m}(x)$ for $ m \leqslant n - 1$, minimax solutions, and central difference formulas, considering also larger values of n, is indicated sketchily.


References [Enhancements On Off] (What's this?)

  • [1] L. M. MILNE-THOMSON, Calculus of Finite Differences, Macmillan, London, 1933. MR 0043339 (13:245c)
  • [2] J. F. STEFFENSEN, Interpolation, Williams and Wilkins, Baltimore, Md., 1927, pp. 60-68.
  • [3] H. E. SALZER, "Optimal points for numerical differentiation," Numer. Math., v. 2, 1960, pp. 214-227. MR 22 # 658. MR 0117884 (22:8658)
  • [4] D. L. BERMAN, "The solution of an extremal problem of the theory of interpolation," Dokl. Akad. Nauk SSSR, v. 87, 1952, pp. 167-170. (Russian) MR 14, 542. MR 0051889 (14:542b)
  • [5] T. J. RIVLIN, An Introduction to the Approximation of Functions, Blaisdell, Waltham, Mass., 1969, pp. 117-118. MR 40 #3126. MR 0249885 (40:3126)
  • [6] R. J. DUFFIN & A. C. SCHAEFFER, "A refinement of an inequality of the brothers Markoff," Trans. Amer. Math. Soc., v. 50, 1941, pp. 517-528. MR 3, 235. MR 0005942 (3:235c)
  • [7] D. L. BERMAN, "The solution of an extremal problem of the theory of interpolation," Izv. Vysš. Učebn. Zaved. Matematika (43), v. 6, 1964, pp. 10-14. (Russian) MR 30 #632. MR 0173117 (30:3332)
  • [8] W. MARKOFF, "Über Polynome, die in einem gegebenen Intervalle möglichst wenig von Null abweichen," Math. Ann., v. 77, 1916, pp. 213-258 (translated from the Russian, St. Petersburg Acad., 1892). MR 1511855
  • [9] H. E. SALZER, "Lagrangian interpolation at the Chebyshev points $ {x_{n,v}} \equiv \cos (v\pi /n),v = 0(1)n$; some unnoted advantages," Comput. J., v. 15, 1972, pp. 156-159; ibid., v. 16, 1973, pp. 190, 382. MR 47 #4414. MR 0315865 (47:4414)
  • [10] H. E. SALZER, Table of Coefficients for Obtaining the First Derivative Without Differences, Nat. Bur. Standards, Washington, D. C., Appl. Math. Ser., no. 2, 1948, 20 pp. MR 10, 69. MR 0025808 (10:69a)
  • [11] H. E. SALZER & P. T. ROBERSON, Table of Coefficients for Obtaining the Second Derivative Without Differences, Convair-Astronautics, San Diego, Calif., 1957, 25 pp. MR 19, 689. MR 0089521 (19:689b)
  • [12] W. G. BICKLEY, "Formulae for numerical differentiation," Math. Gaz., v. 25, 1941, pp. 19-27. MR 2, 240. MR 0003580 (2:240a)
  • [13] H. E. SALZER, "Coefficients for numerical differentiation with central differences," J. Math. Phys. Mass. Inst. Tech., v. 22, 1943, pp. 115-135. MR 5, 50. MR 0008720 (5:50h)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65D25

Retrieve articles in all journals with MSC: 65D25


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1974-0368391-0
Keywords: Numerical differentiation, Lagrangian interpolation, optimally stable numerical differentiation, criteria for optimal stability, minimin and minimax solutions, Chebyshev points, Chebyshev polynomials, central difference formulas
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society