Lloyd N. Trefethen

Silviu-Ioan Filip, Yuji Nakatsukasa, Lloyd N. Trefethen et al.

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.

Abinand Gopal, Lloyd N. Trefethen

New numerical algorithms based on rational functions are introduced that can solve certain Laplace and Helmholtz problems on two-dimensional domains with corners faster and more accurately than the standard methods of finite elements and integral equations. The new algorithms point to a reconsideration of the assumptions underlying existing numerical analysis for partial differential equations.

Jared L. Aurentz, Lloyd N. Trefethen

Chebfun and related software projects for numerical computing with functions are based on the idea that at each step of a computation, a function $f(x)$ defined on an interval $[a,b]$ is "rounded" to a prescribed precision by constructing a Chebyshev series and chopping it at an appropriate point. Designing a chopping algorithm with the right properties proves to be a surprisingly complex and interesting problem. We describe the chopping algorithm introduced in Chebfun Version 5.3 in 2015 after many years of discussion and the considerations that led to this design.

Abinand Gopal, Lloyd N. Trefethen

The traditional view in numerical conformal mapping is that once the boundary correspondence function has been found, the map and its inverse can be evaluated by contour integrals. We propose that it is much simpler, and 10-1000 times faster, to represent the maps by rational functions computed by the AAA algorithm. To justify this claim, first we prove a theorem establishing root-exponential convergence of rational approximations near corners in a conformal map, generalizing a result of D. J. Newman in 1964. This leads to the new algorithm for approximating conformal maps of polygons. Then we turn to smooth domains and prove a sequence of four theorems establishing that in any conformal map of the unit circle onto a region with a long and slender part, there must be a singularity or loss of univalence exponentially close to the boundary, and polynomial approximations cannot be accurate unless of exponentially high degree. This motivates the application of the new algorithm to smooth domains, where it is again found to be highly effective.

Lloyd N. Trefethen

At the ANZIAM conference in Hobart in February, 2018, there were several talks on the solution of Laplace problems in multiply connected domains by means of conformal mapping. It appears to be not widely known that such problems can also be solved by the elementary method of series expansions with coefficients determined by least-squares fitting on the boundary. (These are not convergent series; the coefficients depend on the degree of the approximation.) Here we give a tutorial introduction to this method, which converges at an exponential rate if the boundary data are sufficiently well-behaved. The mathematical foundations go back to Runge in 1885 and Walsh in 1929. One of our examples involves an approximate Cantor set with up to 2048 components.

Anthony P. Austin, Lloyd N. Trefethen

The trigonometric interpolants to a periodic function $f$ in equispaced points converge if $f$ is Dini-continuous, and the associated quadrature formula, the trapezoidal rule, converges if $f$ is continuous. What if the points are perturbed? With equispaced grid spacing $h$, let each point be perturbed by an arbitrary amount $\le αh$, where $α\in [\kern .5pt 0,1/2)$ is a fixed constant. The Kadec 1/4 theorem of sampling theory suggests there may be be trouble for $α\ge 1/4$. We show that convergence of both the interpolants and the quadrature estimates is guaranteed for all $α<1/2$ if $f$ is twice continuously differentiable, with the convergence rate depending on the smoothness of $f$. More precisely it is enough for $f$ to have $4α$ derivatives in a certain sense, and we conjecture that $2α$ derivatives is enough. Connections with the Fejér--Kalmár theorem are discussed.

Yuji Nakatsukasa, Lloyd N. Trefethen

Let $E_{kk}^{(n)}$ denote the minimax (i.e., best supremum norm) error in approximation of $x^n$ on $[\kern .3pt 0,1]$ by rational functions of type $(k,k)$ with $k<n$. We show that in an appropriate limit $E_{kk}^{(n)} \sim 2\kern .3pt H^{k+1/2}$ independently of $n$, where $H \approx 1/9.28903$ is Halphen's constant. This is the same formula as for minimax approximation of $e^x$ on $(-\infty,0\kern .3pt]$.

Oscar P. Bruno, Manuel A. Santana, Lloyd N. Trefethen

This paper presents a novel algorithm, based on use of rational approximants of a randomly scalarized boundary integral resolvent in conjunction with an adaptive search strategy and an exponentially convergent secant-method termination stage, for the evaluation of acoustic and electromagnetic resonances in open and closed cavities. The desired cavity resonances are obtained as the poles of associated rational approximants; both the approximants and their poles are obtained by means of the recently introduced AAA rational-approximation algorithm. In fact, the proposed resonance-search method applies to any nonlinear eigenvalue problem associated with a given function $F: U \to \mathbb{C}^{d\times d}$, wherein, denoting $F(k) = F_k$, a complex value $k$ is sought for which $F_kw = 0$ for some nonzero $w\in \mathbb{C}^d$. For the scattering problems considered in this paper, $F_k$ is taken to equal a spectrally discretized version of a Green function-based boundary integral operator at spatial frequency $k$. In all cases, the scalarized resolvent is given by an expression of the form $u^* F_k^{-1} v$, where $u,v \in \mathbb{C}^d$ are fixed random vectors. The proposed adaptive search strategy relies on use of a rectangular subdivision of the resonance search domain which is locally refined to ensure that all resonances in the domain are captured. The approach works equally well in the case in which the search domain is an interval of the real line, in which case the rectangles used degenerate into subintervals of the search domain. A variety of numerical results are presented, including comparisons with well-known methods based on complex contour integration, and a discussion of the asymptotics that result as open cavities approach closed cavities -- in all, demonstrating the accuracy provided by the method, for low- and high-frequency states alike.

Yuji Nakatsukasa, Olivier Sète, Lloyd N. Trefethen

We introduce a new algorithm for approximation by rational functions on a real or complex set of points, implementable in 40 lines of Matlab and requiring no user input parameters. Even on a disk or interval the algorithm may outperform existing methods, and on more complicated domains it is especially competitive. The core ideas are (1) representation of the rational approximant in barycentric form with interpolation at certain support points and (2) greedy selection of the support points to avoid exponential instabilities. The name AAA stands for "adaptive Antoulas--Anderson" in honor of the authors who introduced a scheme based on (1). We present the core algorithm with a Matlab code and nine applications and describe variants targeted at problems of different kinds. Comparisons are made with vector fitting, RKFIT, and other existing methods for rational approximation.

Lloyd N. Trefethen

A theorem is proved concerning approximation of analytic functions by multivariate polynomials in the $s$-dimensional hypercube. The geometric convergence rate is determined not by the usual notion of degree of a multivariate polynomial, but by the {\it Euclidean degree,} defined in terms of the 2-norm rather than the 1-norm of the exponent vector $\bf k$ of a monomial $x_1^{k_1}\cdots \kern .8pt x_s^{k_s}$.

Grady B. Wright, Mohsin Javed, Hadrien Montanelli et al.

Algorithms and underlying mathematics are presented for numerical computation with periodic functions via approximations to machine precision by trigonometric polynomials, including the solution of linear and nonlinear periodic ordinary differential equations. Differences from the nonperiodic Chebyshev case are highlighted.