Gauss–Arnoldi quadrature for $\bigl\langle(zI-A)^{-1}\varphi,\varphi\bigr\rangle$ and rational Padé-type approximation for Markov-type functions

L. A. Knizhnerman

Sbornik. Mathematics, Tome 199 (2008) no. 2, pp. 185-206

Résumé

The efficiency of Gauss–Arnoldi quadrature for the calculation of the quantity $\bigl\langle(zI-A)^{-1}\varphi,\varphi\bigr\rangle$ is studied, where $A$ is a bounded operator in a Hilbert space and $\varphi$ is a non-trivial vector in this space. A necessary and a sufficient conditions are found for the efficiency of the quadrature in the case of a normal operator. An example of a non-normal operator for which this quadrature is inefficient is presented. It is shown that Gauss–Arnoldi quadrature is related in certain cases to rational Padé-type approximation (with the poles at Ritz numbers) for functions of Markov type and, in particular, can be used for the localization of the poles of a rational perturbation. Error estimates are found, which can also be used when classical Padé approximation does not work or it may not be efficient. Theoretical results and conjectures are illustrated by numerical experiments. Bibliography: 44 titles.

Bibliographie

[1] W. E. Arnoldi, “The principle of minimized iterations in the solution of the matrix eigenvalue problem”, Quart. Appl. Math., 9 (1951), 17–29 | MR | Zbl

[2] Kh. D. Ikramov, Nesimmetrichnaya problema sobstvennykh znachenii. Chislennye metody, Nauka, M., 1991 | MR | Zbl

[3] A. Ruhe, “The two-sided Arnoldi algorithm for nonsymmetric eigenvalue problems”, Matrix pencils, Proceedings of the Conference (Pite Havsbad, Sweden, 1982), Lect. Notes in Math., 973, Springer-Verlag, Berlin–Heidelberg, 1982, 104–120 | DOI | MR | Zbl

[4] Y. Saad, “Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices”, Linear Algebra Appl., 34 (1980), 269–295 | DOI | MR | Zbl

[5] Y. Saad, “Krylov subspace methods for solving large unsymmetric linear systems”, Math. Comp., 37:155 (1981), 105–126 | DOI | MR | Zbl

[6] Y. Saad, M. H. Schultz, “GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems”, SIAM J. Sci. Statist. Comput., 7:3 (1986), 856–869 | DOI | MR | Zbl

[7] H. C. Elman, Y. Saad, P. E. Saylor, “A hybrid Chebyshev Krylov subspace algorithm for solving nonsymmetric systems of linear equations”, SIAM J. Sci. Statist. Comput., 7:3 (1986), 840–855 | DOI | MR | Zbl

[8] D. Ho, F. Chatelin, M. Bennani, “Arnoldi–Tchebychev procedure for large scale nonsymmetric matrices”, RAIRO Modél. Math. Anal. Numér., 24:1 (1990), 53–65 | MR | Zbl

[9] P. N. Brown, Y. Saad, “Hybrid Krylov methods for nonlinear systems of equations”, SIAM J. Sci. Statist. Comput., 11:3 (1990), 450–481 | DOI | MR | Zbl

[10] C. W. Gear, Y. Saad, “Iterative solution of linear equations in ODE codes”, SIAM J. Sci. Statist. Comput., 4:4 (1983), 583–601 | DOI | MR | Zbl

[11] E. Gallopoulos, Y. Saad, “Efficient solution of parabolic equations by Krylov approximation methods”, SIAM J. Sci. Statist. Comput., 13:5 (1992), 1236–1264 | DOI | MR | Zbl

[12] M. Hochbruck, Ch. Lubich, “On Krylov subspace approximations to the matrix exponential operator”, SIAM J. Numer. Anal., 34:5 (1997), 1911–1925 | DOI | MR | Zbl

[13] Y. Saad, “Analysis of some Krylov subspace approximations to the matrix exponential operator”, SIAM J. Numer. Anal., 29:1 (1992), 209–228 | DOI | MR | Zbl

[14] M. Hochbruck, Ch. Lubich, H. Selhofer, “Exponential integrators for large systems of differential equations”, SIAM J. Sci. Comput., 19:5 (1998), 1552–1574 | DOI | MR | Zbl

[15] L. A. Knizhnerman, “Calculation of functions of unsymmetric matrices using Arnoldi's method”, U.S.S.R. Comput. Math. and Math. Phys., 31:1 (1991), 1–9 | MR | Zbl

[16] L. A. Knizhnerman, “Error bounds in Arnoldi's method: the case of a normal matrix”, Comput. Math. Math. Phys., 32:9 (1992), 1199–1211 | MR | Zbl

[17] L. Knizhnerman, On adaptation of the Arnoldi method to the spectrum, Technical report, Schlumberger-Doll Research Report #EMG-001-96-03, 1996 | Zbl

[18] L. Knizhnerman, “Error bounds for the Arnoldi method: a set of extreme eigenpairs”, Linear Algebra Appl., 296:1–3 (1999), 191–211 | DOI | MR | Zbl

[19] E. M. Nikishin, V. N. Sorokin, Rational approximations and orthogonality, Transl. Math. Monogr., 92, Amer. Math. Soc., Providence, RI, 1991 | MR | MR | Zbl | Zbl

[20] G. W. Stewart, J. G. Sun, Matrix perturbation theory, Comput. Sci. Sci. Comput., Academic Press, Boston, 1990 | MR | Zbl

[21] A. Markoff, “Deux démonstrations de la convergence de certaines fractions”, Acta Math., 19:1 (1895), 93–104 | DOI | MR | Zbl

[22] H. Stahl, V. Totik, General orthogonal polynomials, Encyclopedia Math. Appl., 43, Cambridge Univ. Press, Cambridge, 1992 | MR | Zbl

[23] L. Knizhnerman, On adaptation of the Lanczos method to the spectrum, Technical report, Schlumberger-Doll Research, Res. Note EMG-001-95-12, 1995

[24] A. A. Gončar, “On convergence of Padé approximants for some classes of meromorphic functions”, Math. USSR-Sb., 26:4 (1975), 555–575 | DOI | MR | Zbl

[25] E. A. Rahmanov, “On the asymptotics of the ratio of orthogonal polynomials”, Math. USSR-Sb., 32:2 (1977), 199–213 | DOI | MR | Zbl | Zbl

[26] E. A. Rakhmanov, “On the asymptotics of the ratio of orthogonal polynomials. II”, Math. USSR-Sb., 46:1 (1983), 105–117 | DOI | MR | Zbl | Zbl

[27] E. A. Rahmanov, “The convergence of diagonal Padé approximants”, Math. USSR-Sb., 33:2 (1977), 243–260 | DOI | MR | Zbl | Zbl

[28] A. A. Gonchar, S. P. Suetin, “Ob approksimatsiyakh Pade meromorfnykh funktsii markovskogo tipa”, Sovr. probl. matem., 5 (2004), 3–67 | DOI | MR | Zbl

[29] S. P. Suetin, “Padé approximants and efficient analytic continuation of a power series”, Russian Math. Surveys, 57:1 (2002), 43–141 | DOI | MR | Zbl

[30] S. P. Suetin, “Uniform convergence of Padé diagonal approximants for hyperelliptic functions”, Sb. Math., 191:9 (2000), 1339–1373 | DOI | MR | Zbl

[31] S. P. Suetin, “Convergence of Chebyshëv continued fractions for elliptic functions”, Sb. Math., 194:12 (2003), 1807–1835 | DOI | MR | Zbl

[32] P. Lancaster, Theory of matrices, Academic Press, New York–London, 1969 | MR | MR | Zbl | Zbl

[33] D. Calvetti, S.-M. Kim, L. Reichel, “Quadrature rules based on the Arnoldi process”, SIAM J. Matrix Anal. Appl., 26:3 (2005), 765–781 | DOI | MR | Zbl

[34] R. W. Freund, M. Hochbruck, “Gauss quadratures associated with the Arnoldi process and the Lanczos algorithm”, Linear algebra for large scale and real-time applications, Proceedings of the NATO Advanced Study Institute (Leuven, Belgium, 1992), NATO Adv. Sci. Inst. Ser. E Appl. Sci., 232, Kluwer Acad. Publ., Dordrecht, 1993, 377–380 | MR | Zbl

[35] D. H. Bailey, “A Fortran 90-based multiprecision system”, ACM Trans. Math. Software, 21:4 (1995), 379–387 | DOI | Zbl

[36] W. Rudin, Functional analysis, McGraw-Hill, New York–Düsseldorf–Johannesburg, 1973 | MR | MR | Zbl

[37] A. Ambroladze, H. Wallin, “Convergence rates of Padé and Padé-type approximants”, J. Approx. Theory, 86:3 (1996), 310–319 | DOI | MR | Zbl

[38] H. S. Shapiro, The Schwarz function and its generalization to higher dimensions, Univ. Arkansas Lecture Notes Math. Sci., 9, Wiley, New York, 1992 | MR | Zbl

[39] D. Gaier, Lectures on complex approximation, Birkhäuser, Boston–Basel–Stuttart, 1987 ; D. Gaier, Lektsii po teorii approksimatsii v kompleksnoi oblasti, Mir, M., 1986 | MR | Zbl | MR | Zbl

[40] A. Ambroladze, “On exceptional sets of asymptotic relations for general orthogonal polynomials”, J. Approx. Theory, 82:2 (1995), 257–273 | DOI | MR | Zbl

[41] M. He, “The Faber polynomials for circular arcs”, Mathematics of computation, 1943-1993: a half- century of computational mathematics (Vancouver, Canada, 1993), Proc. Sympos. Appl. Math., 48, Amer. Math. Soc., Providence, RI, 1994, 301–304 | MR | Zbl

[42] S. Lang, Algebra, Addison-Wesley, Reading, MA, 1965 | MR | Zbl | Zbl

[43] G. H. Golub, Ch. F. van Loan, Matrix computations, Johns Hopkins Ser. Math. Sci., 3, Johns Hopkins Univ. Press, Baltimore, MD, 1989 | MR | Zbl

[44] L. A. Knizhnerman, “Adaptation of the Lanczos and Arnoldi methods to the spectrum, or why the two Krylov subspace methods are powerful”, Chebyshevskii sb., 3:2 (2002), 141–164 | MR | Zbl