Barycentric-Remez algorithms for best polynomial approximation in the chebfun system

Journal article

The Remez algorithm, 75 years old, is a famous method for computing minimax polynomial approximations. Most implementations of this algorithm date to an era when tractable degrees were in the dozens, whereas today, degrees of hundreds or thousands are not a problem. We present a 21st-century update of the Remez ideas in the context of the chebfun software system, which carries out numerical computing with functions rather than numbers. A crucial feature of the new method is its use of chebfun global rootfinding to locate extrema at each iterative step, based on a recursive algorithm combining ideas of Specht, Good, Boyd, and Battles. Another important feature is the use of the barycentric interpolation formula to represent the trial polynomials, which points the way to generalizations for rational approximations. We comment on available software for minimax approximation and its scientific context, arguing that its greatest importance these days is probably for fundamental studies rather than applications. © Springer Science + Business Media B.V. 2009.

Authors: Pachon, R; Trefethen, L

• Publication status: Published
• Journal: BIT NUMERICAL MATHEMATICS
• Volume: 49
• Issue: 4
• Pages: 721-741
• Publication date: 2009-12-01
• DOI: 10.1007/s10543-009-0240-1
• EISSN: 1572-9125
• ISSN: 0006-3835
• Language: English
• Keywords: Barycentric interpolation; Chebfun system; Remez algorithm; Best polynomial approximation