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.
omer@cs.ucsb.edu