zbMATH — the first resource for mathematics

Fast algorithms for polynomial interpolation, integration, and differentiation. (English) Zbl 0862.65005
The authors present a group of three algorithms for interpolation, integration and differentiation of functions tabulated at nodes other than Chebyshev.
The interpolation scheme requires \(O(N\log\varepsilon^{-1})\) arithmetic operations, while for the integration and differentiation schemes are required \(O(N\log N+N\log\varepsilon^{-1})\) operations, where \(\varepsilon\) is the precision of computations and \(N\) is the number of nodes. It should be mentioned that the interpolation and integration schemes are stable, while the differentiation scheme has a condition number proportional to \(N^2\).
The authors have written FORTRAN implementations of their algorithms using double precision arithmetic. There are included several experiments in order to illustrate the numerical performance of their fast algorithms.

65D05 Numerical interpolation
65D32 Numerical quadrature and cubature formulas
65D25 Numerical differentiation
65Y20 Complexity and performance of numerical algorithms
Full Text: DOI