Extremal Rational Functions on Symmetric Discrete Sets and Superlinear Convergence of the ADI Method

There is a very fruitful interaction between numerical linear algebra and logarithmic potential theory. For instance, we may describe weak asympotics for a polynomial extremal problem occurring in the convergence analysis of conjugate gradients (CG) or of Ritz values; here the link with a constrained minimal energy problem allows to quantify the effect of superlinear convergence. In the present paper, we introduce an extremal problem for rational functions on two discrete sets E(N), F(N), the so-called third Zolotarev problem. Roughly speaking, we look for rational functions of a prescribed degree which are as small as possible on EN and as large as possible on FN. Such a problem occurs naturally in the convergence analysis for 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 singular values of matrices with small displacement rank. Whereas asymptotics for this extremal problem on continuous sets is well studied, we require new tools in order to handle the case of discrete sets. The main contribution of this paper is to show that a minimal energy problem for signed and constrained measures allows us to describe the asymptotics. This new minimal energy problem is a natural extension of that of Kuijlaars and Beckermann used to describe weak asymptotics for the polynomial extremal problem related to CG. We discuss the sharpness of our asymptotic findings for general discrete sets in the complex plane and suggest new formulas for the extremal constant in the particular case where the two discrete sets are real and symmetric with respect to the origin.Finally, by discussing a model example, we show the impact of our findings for analyzing the rate of superlinear convergence of the ADI method applied to a Lyapunov equation.