Mathematics of Computation, 53 (1989), pp. 246-264

Ömer Egecioglu and Cetin K. Koc

A Fast Algorithm for Rational Interpolation via Orthogonal Polynomials

Abstract. A new algorithm for rational interpolation is proposed. Given the data set, the algorithm generates a set of orthogonal polynomials by the classical three-term recurrence relation and then uses Newton interpolation to find the numerator and the denominator polynomials of the rational interpolating function. The number of arithmetic operations of the algorithm to find a particular rational interpolant is $O(N^2)$ where N+1 is the number of data points. A variant of this algorithm that avoids Newton interpolation can be used to construct all rational interpolants using only $O(N^2)$ arithmetic operations.