Rational minimax approximation via adaptive barycentric representations

Computing rational minimax approximations can be very challenging when there are singularities on or near the interval of approximation - precisely the case where rational functions outperform polynomials by a landslide. We show that far more robust algorithms than previously available can be develo...

Full description

Bibliographic Details
Main Authors: Filip, S, Nakatsukasa, Y, Trefethen, L, Beckermann, B
Format: Journal article
Published: Society for Industrial and Applied Mathematics 2018
_version_ 1826289689738346496
author Filip, S
Nakatsukasa, Y
Trefethen, L
Beckermann, B
author_facet Filip, S
Nakatsukasa, Y
Trefethen, L
Beckermann, B
author_sort Filip, S
collection OXFORD
description Computing rational minimax approximations can be very challenging when there are singularities on or near the interval of approximation - precisely the case where rational functions outperform polynomials by a landslide. We show that far more robust algorithms than previously available can be developed by making use of rational barycentric representations whose support points are chosen in an adaptive fashion as the approximant is computed. Three variants of this barycentric strategy are all shown to be powerful: (1) a classical Remez algorithm, (2) a "AAA-Lawson" method of iteratively reweighted least-squares, and (3) a differential correction algorithm. Our preferred combination, implemented in the Chebfun MINIMAX code, is to use (2) in an initial phase and then switch to (1) for generically quadratic convergence. By such methods we can calculate approximations up to type (80, 80) of $|x|$ on $[-1, 1]$ in standard 16-digit floating point arithmetic, a problem for which Varga, Ruttan, and Carpenter required 200-digit extended precision.
first_indexed 2024-03-07T02:32:43Z
format Journal article
id oxford-uuid:a7cc7d2a-b2c7-4dbc-a10c-4583a5f0bda3
institution University of Oxford
last_indexed 2024-03-07T02:32:43Z
publishDate 2018
publisher Society for Industrial and Applied Mathematics
record_format dspace
spelling oxford-uuid:a7cc7d2a-b2c7-4dbc-a10c-4583a5f0bda32022-03-27T02:56:53ZRational minimax approximation via adaptive barycentric representationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:a7cc7d2a-b2c7-4dbc-a10c-4583a5f0bda3Symplectic Elements at OxfordSociety for Industrial and Applied Mathematics2018Filip, SNakatsukasa, YTrefethen, LBeckermann, BComputing rational minimax approximations can be very challenging when there are singularities on or near the interval of approximation - precisely the case where rational functions outperform polynomials by a landslide. We show that far more robust algorithms than previously available can be developed by making use of rational barycentric representations whose support points are chosen in an adaptive fashion as the approximant is computed. Three variants of this barycentric strategy are all shown to be powerful: (1) a classical Remez algorithm, (2) a "AAA-Lawson" method of iteratively reweighted least-squares, and (3) a differential correction algorithm. Our preferred combination, implemented in the Chebfun MINIMAX code, is to use (2) in an initial phase and then switch to (1) for generically quadratic convergence. By such methods we can calculate approximations up to type (80, 80) of $|x|$ on $[-1, 1]$ in standard 16-digit floating point arithmetic, a problem for which Varga, Ruttan, and Carpenter required 200-digit extended precision.
spellingShingle Filip, S
Nakatsukasa, Y
Trefethen, L
Beckermann, B
Rational minimax approximation via adaptive barycentric representations
title Rational minimax approximation via adaptive barycentric representations
title_full Rational minimax approximation via adaptive barycentric representations
title_fullStr Rational minimax approximation via adaptive barycentric representations
title_full_unstemmed Rational minimax approximation via adaptive barycentric representations
title_short Rational minimax approximation via adaptive barycentric representations
title_sort rational minimax approximation via adaptive barycentric representations
work_keys_str_mv AT filips rationalminimaxapproximationviaadaptivebarycentricrepresentations
AT nakatsukasay rationalminimaxapproximationviaadaptivebarycentricrepresentations
AT trefethenl rationalminimaxapproximationviaadaptivebarycentricrepresentations
AT beckermannb rationalminimaxapproximationviaadaptivebarycentricrepresentations