Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method (Q607489)

The authors introduce an extremal problem for rational functions on two discrete subsets of the complex plane, \(E_{N}, F_{N}\), the so-called third Zolotarev problem. Roughly speaking, the authors look for rational functions of a prescribed degree (with constraints on the degree of both the numerator and denominator) which are as small as possible on \(E_{N}\) and as large as possible on \(F_{N}\). This problem has a long history and occurs naturally in the convergence analysis of the so-called alternating direction implicit (ADI) method for solving Lyapunov equations, but also in the approximation of particular matrix functions, and in the decay rate of the singular values of matrices with small displacement rank. While it is easy to reduce the problem to compact sets \(E_{N}\) and \( F_{N}\), the novelty of the paper consists in the study of the discrete setting. It seems that it was very common to assume that both \(E_{N}\) and \(F_{N}\) are solid, and if this was not the case, instead the convex hulls were considered. The authors provide some convincing numerical calculations that show that such a treatment can give results which do not have the desired and expected asymptotics. The authors define the quantity \[ Z_{n}(E_{N},F_{N})=\min_{r}\| r\| _{L^{\infty}(E_{N })}\| r^{-1}\| _{L^{\infty}(F_{N })}, \] where the minimum is taken over all rational functions \(r\) such that the degrees of the numerator and denominator are both bounded by \(n\). The result is: \[ \limsup_{n,N\to\infty, n/N\to t} Z_{n}(E_{N},F_{N})^{1/N}\leq e^{-(F_{1}^{t}+F_{2}^{t})}, \] under mild additional assumptions (mainly that the sets \(E_{N}\) and \(F_{N}\) are separated in a suitable sense). Under stronger assumptions equality holds. Here \(F_{1}^{t}\) and \(F_{2}^{t}\) are real non-negative constants depending on \(E_{N}\) and \(F_{N}\) by means of some potential-theoretic functions. This gives the precise asymptotic of the studied quantities. In the special case when the sets are real and symmetric with respect to the origin, some explicit calculations are also provided. Finally the authors show the impact of their results for analyzing the rate of superlinear convergence of the ADI method applied to a Lyapunov equation.