Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method
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.
- scientific article; zbMATH DE number 3366466
- On an extremal problem in the theory of rational approximation
- scientific article; zbMATH DE number 3886501
- Discrete l1 Approximation by Rational Functions
- On a sharp inequality of Adimurthi-Druet type and extremal functions
- Adaptive rational approximation in Bergman space on bounded symmetric domain
- A class of maximally singular sets for rational approximation
- Extremal inequalities for rational functions bounded in the mean on the line
- On the extremizers of an adjoint Fourier restriction inequality
- An extremal problem for algebraic polynomials in the symmetric discrete Gegenbauer--Sobolev space
- A generalized ADI iterative method
- Constrained energy problems with applications to orthogonal polynomials of a discrete variable
- Convergence Analysis of Krylov Subspace Iterations with Methods from Potential Theory
- Discrete orthogonal polynomials and superlinear convergence of Krylov subspace methods in numerical linear algebra
- Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case
- Equilibrium measure and the distribution of zeros of the extremal polynomials of a discrete variable
- Equilibrium problems associated with fast decreasing polynomials
- Extended Application of Alternating Direction Implicit Iteration Model Problem Theory
- Families of equilibrium measures in an external field on the real axis
- From Potential Theory to Matrix Iterations in Six Steps
- Functions of Matrices
- Green equilibrium measures and representations of an external field
- scientific article; zbMATH DE number 3120956 (Why is no real title available?)
- scientific article; zbMATH DE number 5295869 (Why is no real title available?)
- scientific article; zbMATH DE number 19432 (Why is no real title available?)
- scientific article; zbMATH DE number 51140 (Why is no real title available?)
- scientific article; zbMATH DE number 739279 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 1077997 (Why is no real title available?)
- Implicit Alternating Direction Methods
- Numerical methods for the QCDd overlap operator. I: Sign-function and error bounds
- On a conjecture of E. A. Rakhmanov
- ON THE SPEED OF RATIONAL APPROXIMATION OF SOME ANALYTIC FUNCTIONS
- Rational approximation of Stieltjes functions by the Carathéodory-Fejér method
- Superlinear CG convergence for special right-hand sides
- Superlinear convergence of conjugate gradients
- Support of the extremal measure in a vector equilibrium problem
- The asymptotic distribution of zeros of minimal Blaschke products
- The distribution of zeros and poles of asymptotically extremal rational functions for Zolotarev's problem
- The Numerical Solution of Parabolic and Elliptic Differential Equations
- Where does the sup norm of a weighted polynomial live? (A generalization of incomplete polynomials)
- Which eigenvalues are found by the Lanczos method?
- Zur Rationalen Approximation von e-x auf [0,infinity]
- Optimal ray sequences of rational functions connected with the Zolotarev problem
- Fejér-Walsh points for rational functions and their use in the ADI iterative method
- Condensers with touching plates and constrained minimum Riesz and Green energy problems
- Constrained minimum Riesz energy problems for a condenser with intersecting plates
- A concept of weak Riesz energy with application to condensers with touching plates
- On rational approximation of Markov functions on finite sets
- Minimum Riesz energy problems for a condenser with touching plates
- Superlinear convergence of the rational Arnoldi method for the approximation of matrix functions
- Solving rank-structured Sylvester and Lyapunov equations
- On the singular values of matrices with displacement structure
- A low-rank technique for computing the quasi-stationary distribution of subcritical Galton-Watson processes
- Bounds on the singular values of matrices with displacement structure
- Non-standard green energy problems in the complex plane
- Conditioning of solutions to the Sylvester equation
This page was built for publication: Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607489)
