Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method. (English) Zbl 1208.30036
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.
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.
Reviewer: Zywomir Dinew (Kraków)
MSC:
| 30E10 | Approximation in the complex plane |
| 41A20 | Approximation by rational functions |
| 65F10 | Iterative numerical methods for linear systems |
| 65E05 | General theory of numerical methods in complex analysis (potential theory, etc.) |
Software:
mftoolboxReferences:
| [1] | Achieser, N.I.: Theory of Approximation. Ungar, New York (1956) · Zbl 0072.28403 |
| [2] | Akhieser, N.I.: Elements of the Theory of Elliptic Functions. Transl. of Math. Monographs, vol. 79. AMS, Providence (1990) |
| [3] | Beckermann, B.: On a conjecture of E.A. Rakhmanov. Constr. Approx. 16, 427–448 (2000) · Zbl 1092.33009 · doi:10.1007/s003659910018 |
| [4] | Beckermann, B.: Singular values of small displacement rank matrices. Talk at conference Structured Numerical Linear Algebra Problems: Algorithms and Applications, Cortona, 2004 |
| [5] | Beckermann, B.: Discrete orthogonal polynomials and superlinear convergence of Krylov subspace methods in numerical linear algebra. In: Marcellan, F., Van Assche, W. (eds.) Orthogonal Polynomial and Special Functions. Lecture Notes in Mathematics, vol. 1883, pp. 119–185. Springer, Berlin (2006) · Zbl 1103.65311 |
| [6] | Beckermann, B., Kuijlaars, A.B.J.: Superlinear convergence of conjugate gradients. SIAM J. Numer. Anal. 39, 300–329 (2001) · Zbl 0997.65058 · doi:10.1137/S0036142999363188 |
| [7] | Beckermann, B., Kuijlaars, A.B.J.: On the sharpness of an asymptotic error estimate for conjugate gradients. BIT 41, 856–867 (2001) · doi:10.1023/A:1021964506568 |
| [8] | Beckermann, B., Kuijlaars, A.B.J.: Superlinear CG convergence for special right-hand sides. Electron. Trans. Numer. Anal. 14, 1–19 (2002) · Zbl 1024.65102 |
| [9] | Birkhoff, G., Varga, R.S.: Implicit alternating direction methods. Trans. Am. Math. Soc. 92, 13–24 (1959) · Zbl 0093.31201 · doi:10.1090/S0002-9947-1959-0105814-4 |
| [10] | Braess, D.: Nonlinear Approximation Theory. Springer Series in Computational Mathematics, vol. 7. Springer, Berlin (1980) · Zbl 0493.41016 |
| [11] | Braess, D.: Rational approximation of Stieltjes functions by the Carathéodory–Fejer method. Constr. Approx. 3, 43–50 (1987) · Zbl 0626.41007 · doi:10.1007/BF01890552 |
| [12] | Buyarov, V., Rakhmanov, E.A.: Families of equilibrium measures with external field on the real axis. Mat. Sb. 190, 791–802 (1999) · Zbl 0933.31002 · doi:10.1070/SM1999v190n06ABEH000407 |
| [13] | Dragnev, P.D., Saff, E.B.: Constrained energy problems with applications to orthogonal polynomials of a discrete variable. J. Anal. Math. 72, 223–259 (1997) · Zbl 0898.31003 · doi:10.1007/BF02843160 |
| [14] | Driscoll, T.A., Toh, K.-C., Trefethen, L.N.: From potential theory to matrix iteration in six steps. SIAM Rev. 40, 547–578 (1998) · Zbl 0930.65020 · doi:10.1137/S0036144596305582 |
| [15] | Fisher, S.D., Saff, E.B.: The asymptotic distribution of minimal Blaschke products. J. Approx. Theory 98, 104–116 (1999) · Zbl 0923.30022 · doi:10.1006/jath.1998.3280 |
| [16] | Golub, G.H., Van Loan, F.: Matrix Computations, 3rd edn. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (1996) |
| [17] | Gonchar, A.A.: On the speed of rational approximation of some analytic functions. Mat. Sb. 34, 131–145 (1978) · Zbl 0407.30027 · doi:10.1070/SM1978v034n02ABEH001152 |
| [18] | Higham, H.J.: Functions of Matrices: Theory and Computation. SIAM, Philadelphia (2008) · Zbl 1167.15001 |
| [19] | Kuijlaars, A.B.J.: Which eigenvalues are found by the Lanczos method? SIAM J. Matrix Anal. Appl. 22, 306–321 (2000) · Zbl 0969.65028 · doi:10.1137/S089547989935527X |
| [20] | Kuijlaars, A.B.J.: Convergence analysis of Krylov subspace iterations with methods from potential theory. SIAM Rev. 48, 3–40 (2006) · Zbl 1092.65031 · doi:10.1137/S0036144504445376 |
| [21] | Kuijlaars, A.B.J., Dragnev, P.D.: Equilibrium problems associated with fast decreasing polynomials. Proc. Am. Math. Soc. 127, 1065–1074 (1999) · Zbl 1050.31002 · doi:10.1090/S0002-9939-99-04590-6 |
| [22] | Lapik, M.A.: Support of the extremal measure in a vector equilibrium problem. Mat. Sb. 197, 1205–1219 (2006) · Zbl 1148.31005 · doi:10.1070/SM2006v197n08ABEH003795 |
| [23] | Levenberg, N., Reichel, L.: A generalized ADI iterative method. Numer. Math. 66, 215–233 (1993) · Zbl 0797.65030 · doi:10.1007/BF01385695 |
| [24] | Levin, A.L., Lubinsky, D.S.: Green equilibrium measures and representations of an external field. J. Approx. Theory 113, 298–323 (2001) · Zbl 0987.31004 · doi:10.1006/jath.2001.3618 |
| [25] | Levin, A.L., Saff, E.B.: The distribution of zeros and poles of asymptotically extremal rational functions for Zolotarev’s problem. J. Approx. Theory 110, 88–108 (2001) · Zbl 0988.41010 · doi:10.1006/jath.2000.3551 |
| [26] | Levin, A.L., Saff, E.B.: Potential theoretic tools in polynomial and rational approximation in harmonic analysis and rational approximation. In: Fournier, Grimm, Leblond, Partington (eds.) Lecture Notes in Control and Information Sciences, vol. 327, pp. 71–94. Springer, Berlin (2006) · Zbl 1146.41001 |
| [27] | Mhaskar, H.N., Saff, E.B.: Where does the sup norm of a weighted polynomial live? (A generalization of incomplete polynomials). Constr. Approx. 1, 71–91 (1985) · Zbl 0582.41009 · doi:10.1007/BF01890023 |
| [28] | Nikishin, E.M., Sorokin, V.N.: Rational Approximations and Orthogonality. AMS Translations of Mathematical Monographs, vol. 92. AMS, Providence (1991) · Zbl 0733.41001 |
| [29] | Peaceman, D., Rachford, H.: The numerical solution of elliptic and parabolic differential equations. J. Soc. Ind. Appl. Math. 3, 28–41 (1955) · Zbl 0067.35801 · doi:10.1137/0103003 |
| [30] | Penzl, T.: Eigenvalue decay bound for solutions of Lyapounov equations: the symmetric case. Syst. Control Lett. 40, 139–144 (2000) · Zbl 0977.93034 · doi:10.1016/S0167-6911(00)00010-4 |
| [31] | Rakhmanov, E.A.: Equilibrium measure and the distribution of zeros of the extremals polynomials of a discrete variable. Mat. Sb. 187, 1213–1228 (1996) · Zbl 0873.42014 · doi:10.1070/SM1996v187n08ABEH000153 |
| [32] | Ransford, T.: Potential Theory in the Complex Plane. London Math. Soc. Student Text, vol. 28. Cambridge University Press, Cambridge (1995) · Zbl 0828.31001 |
| [33] | Saff, E.B., Totik, V.: Logarithmic Potentials with External Fields. A Series of Comprehensive Studies in Mathematics, vol. 316. Springer, Berlin (1997) · Zbl 0881.31001 |
| [34] | Trefethen, L.N.: Approximation theory and numerical linear algebra. In: Mason, J.C., Cox, M.G. (eds.) Algorithms for Approximation II. Chapman & Hall, London (1990) · Zbl 0747.41005 |
| [35] | Trefethen, L.N., Bau, D. III: Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0874.65013 |
| [36] | van den Eshof, J., Frommer, A., Lippert, Th., Schilling, K., van der Vorst, H.A.: Numerical methods for the QCD overlap operator: I. Sign-function and error bounds. Comput. Phys. Commun. 146, 203–224 (2002) · Zbl 1008.81508 · doi:10.1016/S0010-4655(02)00455-1 |
| [37] | Wachspress, E.L.: Extended application of alternating direction implicit iteration model problem theory. J. Soc. Ind. Appl. Math. 11, 994–1016 (1963) · Zbl 0244.65045 · doi:10.1137/0111073 |
| [38] | Wachspress, E.L.: Solution of the generalized ADI minmax problem. In: Information Processing 68 (Proc. IFIP Congress, Edinburgh, 1968). Mathematics Software, vol. 1, pp. 99–105. North-Holland, Amsterdam (1969) |
| [39] | Zolotarev, E.I.: Collected Work, vol. 2. USSR Acad. Sci., Moscow (1932) (in Russian) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
