Rational minimax approximation via adaptive barycentric representations

DOI10.1137/17M1132409zbMATH Open1396.41011arXiv1705.10132WikidataQ129414204 ScholiaQ129414204MaRDI QIDQ4580291FDOQ4580291

Authors: Silviu-Ioan Filip, Yuji Nakatsukasa, Lloyd N. Trefethen, Bernhard Beckermann 

Publication date: 14 August 2018

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1705.10132

Recommendations

• Barycentric-Remez algorithms for best polynomial approximation in the chebfun system
• An algorithm for real and complex rational minimax approximation
• An algorithm for best rational approximation based on barycentric rational interpolation
• scientific article; zbMATH DE number 2065333
• The AAA algorithm for rational approximation

zbMATH Keywords

Remez algorithmbarycentric formularational minimax approximationdifferential correction algorithmAAA algorithmLawson algorithm

Mathematics Subject Classification ID

Algorithms for approximation of functions (65D15) Approximation by rational functions (41A20)

Cites Work

• Algorithm 715: SPECFUN–a portable FORTRAN package of special function routines and test drivers
• The RKFIT algorithm for nonlinear rational approximation
• The AAA algorithm for rational approximation
• Title not available (Why is that?)
• Piecewise-smooth chebfuns
• Title not available (Why is that?)
• Title not available (Why is that?)
• Barycentric Lagrange Interpolation
• Approximation theory and approximation practice
• Best rational approximation of functions with logarithmic singularities
• Accuracy and Stability of Numerical Algorithms
• The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
• Title not available (Why is that?)
• Rational functions for guaranteed and experimentally well-conditioned global interpolation
• Barycentric rational interpolation with no poles and high rates of approximation
• Title not available (Why is that?)
• The numerical stability of barycentric Lagrange interpolation
• Some New Aspects of Rational Interpolation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rate of Convergence of Lawson's Algorithm
• The Carathéodory–Fejér Method for Real Rational Approximation
• The Differential Correction Algorithm for Rational $\ell _\infty $-Approximation
• Computing near-best fixed pole rational interpolants
• Rational approximation to \(|x|\)
• A framework for the solution of the generalized realization problem
• THE COLLEAGUE MATRIX, A CHEBYSHEV ANALOGUE OF THE COMPANION MATRIX
• Title not available (Why is that?)
• Padé-type rational and barycentric interpolation
• Matrices for the direct determination of the barycentric weights of rational interpolation
• Newton interpolation at Leja points
• Barycentric-Remez algorithms for best polynomial approximation in the chebfun system
• NUMERICAL RESULTS ON BEST UNIFORM RATIONAL APPROXIMATION OF $ \vert x\vert$ ON $ \lbrack-1,\,+1\rbrack$
• A robust implementation of the Carathéodory-Fejér method for rational approximation
• Two new algorithms for rational approximation
• Linear Chebyshev Approximation in the Complex Plane Using Lawson's Algorithm
• Die konstruktive Ermittlung der Tschebyscheff-Approximierenden im Bereich der rationalen Funktionen
• How bad are Vandermonde matrices?
• The FUNPACK Package of Special Function Subroutines
• Tschebyscheff-Approximation im Bereich der rationalen Funktionen bei Vorliegen einer guten Ausgangsnäherung
• An Algorithm for General Restricted Rational Chebyshev Approximation
• Further Remarks on the Differential Correction Algorithm
• Title not available (Why is that?)
• BEST UNIFORM RATIONAL APPROXIMATION OF $ \vert x\vert$ ON $ \lbrack-1,\,1\rbrack$
• Title not available (Why is that?)
• The Construction of Minimax Rational Approximations to Functions
• On the singular values of matrices with displacement structure
• Computing Fundamental Matrix Decompositions Accurately via the Matrix Sign Function in Two Iterations: The Power of Zolotarev's Functions
• Rational Function Approximation As a Well-Conditioned Matrix Eigenvalue Problem

Cited In (37)

• The AAA algorithm for rational approximation
• A robust implementation of the Carathéodory-Fejér method for rational approximation
• A Newton's method for best uniform polynomial approximation
• Rational approximation of 𝐱ⁿ
• Exponential node clustering at singularities for rational approximation, quadrature, and PDEs
• Exponential asymptotics of woodpile chain nanoptera using numerical analytic continuation
• A Lagrange interpolation with preprocessing to nearly eliminate oscillations
• A comprehensive study of the mathematical methods used to approximate the inverse Langevin function
• AAA Rational Approximation on a Continuum
• Barycentric-Remez algorithms for best polynomial approximation in the chebfun system
• The p-AAA Algorithm for Data-Driven Modeling of Parametric Dynamical Systems
• Iterative Stability Enforcement in Adaptive Antoulas–Anderson Algorithms for \({\boldsymbol{\mathcal{H}_2}}\) Model Reduction
• An algorithm for real and complex rational minimax approximation
• The \(L_q\)-weighted dual programming of the linear Chebyshev approximation and an interior-point method
• 6 The Loewner framework for system identification and reduction
• Reducing the truncation error in Taylor model multiplication
• Numerical evaluation of Mittag-Leffler functions
• Data-driven algorithms for signal processing with trigonometric rational functions
• Pseudospectra of Loewner matrix pencils
• Title not available (Why is that?)
• Spectacularly large expansion coefficients in Müntz's theorem
• An algorithm for best rational approximation based on barycentric rational interpolation
• Unitarity of some barycentric rational approximants
• On the rational approximation of Markov functions, with applications to the computation of Markov functions of Toeplitz matrices
• Numerical continued fraction interpolation
• Exact reconstruction of sparse non-harmonic signals from their Fourier coefficients
• Determination of electronic resonances by analytic continuation using barycentric formula
• Treating the Gibbs phenomenon in barycentric rational interpolation and approximation via the S-Gibbs algorithm
• Barycentric formulae for some optimal rational approximants involving Blaschke products
• Chebyshev approximation by a rational expression for functions of many variables
• Practical algorithms for multivariate rational approximation
• Title not available (Why is that?)
• Generalised rational approximation and its application to improve deep learning classifiers
• Numerical analysis of the blow-up of one-dimensional polymer fluid flow with a front
• On rational Krylov and reduced basis methods for fractional diffusion
• Extended barycentric rational schemes for functions of singularities
• A Newton method for best uniform rational approximation

Uses Software

• SPECFUN
• CVX
• Mosek
• mctoolbox
• Chebfun
• RKToolbox
• FUNPACK
• AAA

This page was built for publication: Rational minimax approximation via adaptive barycentric representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580291)