Algorithms for polynomial and rational approximation

Thesis

Robust algorithms for the approximation of functions are studied and developed in this thesis. Novel results and algorithms on piecewise polynomial interpolation, rational interpolation and best polynomial and rational approximations are presented.

Algorithms for the extension of Chebfun, a software system for the numerical computation with functions, are described. These algorithms allow the construction and manipulation of piecewise smooth functions numerically with machine precision. Breakpoints delimiting subintervals are introduced explicitly, implicitly or automatically, the latter method combining recursive subdivision and edge detection techniques.

For interpolation by rational functions with free poles, a novel method is presented. When the interpolation nodes are roots of unity or Chebyshev points the algorithm is particularly simple and relies on discrete Fourier transform matrices, which results in a fast implementation using the Fast Fourier Transform. The method is generalised for arbitrary grids, which requires the construction of polynomials orthogonal on the set of interpolation nodes. The new algorithm has connections with other methods, particularly the work of Jacobi and Kronecker, Berrut and Mittelmann, and Egecioglu and Koc.

Computed rational interpolants are compared with the behaviour expected from the theory of convergence of these approximants, and the difficulties due to truncated arithmetic are explained. The appearance of common factors in the numerator and denominator due to finite precision arithmetic is characterised by the behaviour of the singular values of the linear system associated with the rational interpolation problem.

Finally, new Remez algorithms for the computation of best polynomial and rational approximations are presented. These algorithms rely on interpolation, for the computation of trial functions, and on Chebfun, for the location of trial references. For polynomials, the algorithm is particularly robust and efficient, and we report experiments with degrees in the thousands. For rational functions, we clarify the numerical issues that affect its application.

Authors: Pachon, R

• Publication date: 2010
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: Chebyshev polynomials; Chebfun; best approximation; interpolation
• Subjects: Numerical analysis; Approximations and expansions