Abstract
The extended Krylov subspace method has recently arisen as a competitive method for solving large-scale Lyapunov equations. Using the theoretical framework of orthogonal rational functions, in this paper we provide a general a priori error estimate when the known term has rank-one. Special cases, such as symmetric coefficient matrix, are also treated. Numerical experiments confirm the proved theoretical assertions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Antoulas A.C.: Approximation of large-scale dynamical systems. SIAM, Philadelphia (2005)
Beckermann B.: Image numérique, GMRES et polynômes de Faber. C. R Acad. Sci. Paris Ser. I 340, 855–860 (2005)
Beckermann B., Reichel L.: Error estimation and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal. 47(5), 3849–3883 (2009)
Benner, P., Mehrmann, V., Sorensen, D. (eds): Dimension reduction of large-scale systems. Lecture notes in computational science and engineering. Springer-Verlag, Berlin (2005)
Bultheel A., González-Vera P., Hendriksen E., Njåstad O.: Orthogonal rational functions. Cambridge University Press, Cambridge (1999)
Crouzeix M.: Numerical range and numerical calculus in Hilbert space. J. Funct. Anal. 244, 668–690 (2007)
Van Deun J., Deckers K., Bultheel A., Weideman J.A.C.: Algorithm 882: Near best fixed pole rational interpolation with applications in spectral methods. ACM Trans. Math. Softw. 35(2), 14:1–14:21 (2008)
Druskin V., Knizhnerman L.: Extended Krylov subspaces: approximation of the matrix square root and related functions. SIAM J. Matrix Anal. Appl. 19(3), 755–771 (1998)
Druskin V., Knizhnerman L., Zaslavsky M.: Solution of large scale evolutionary problems using rational Krylov subspaces with optimized shifts. SIAM J. Sci. Comput. 31(5), 3760–3780 (2009)
Dzhrbashyan M.M.: On decomposition of analytic functions in a series in rational functions with a given set of poles. Izv. AN Arm. SSR, ser. fiz.-matem. n. 10(1), 21–29 (1957)
Ellacott S.W.: On the Faber transformation and efficient numerical rational approximation. SIAM J. Numer. Anal. 20(5), 989–1000 (1983)
Gaier D.: The Faber operator and its boundedness. J. Approx. Theory 101(2), 265–277 (1999)
Godunov, S.K.: Lectures on modern aspects of linear algebra. Nauchnaya Kniga (IDMI), Novosibirsk, (In Russian) (2002)
Goluzin G.M.: Geometric theory of functions of a complex variable. American Mathematical Society, Providence, RI (1969)
Hochbruck M., Lubich C.: On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 34(5), 1911–1925 (1997)
Hochbruck M., Starke G.: Preconditioned Krylov subspace methods for Lyapunov matrix equations. SIAM Matrix Anal. and Appl. 16(1), 156–171 (1995)
Jagels C., Reichel L.: The extended Krylov subspace method and orthogonal Laurent polynomials. Lin. Alg. Appl. 431, 441–458 (2009)
Jaimoukha I.M., Kasenally E.M.: Krylov subspace methods for solving large Lyapunov equations. SIAM J. Numer. Anal. 31(1), 227–251 (1994)
Jbilou K., Riquet A.J.: Projection methods for large Lyapunov matrix equations. Lin. Algebra Appl. 415(2–3), 344–358 (2006)
Knizhnerman L., Simoncini V.: A new investigation of the extended Krylov subspace method for matrix function evaluations. Num. Lin. Algebra Appl. 17(4), 615–638 (2010)
Kocharyan G.S.: On approximation by rational functions in the complex domain. Izv. AN Arm. SSR, ser. fiz.-matem. n. 11(4), 53–77 (1958)
Kressner, D., Tobler., C.: Krylov subspace methods for linear systems with tensor product structure. Technical Report SAM-2009-16, ETH Zurich (2009)
Kressner D., Tobler C.: Krylov subspace methods for linear systems with tensor product structure. SIAM J. Matrix Anal. Appl. 31(4), 1688–1714 (2010)
Lancaster P.: Explicit solutions of linear matrix equations. SIAM Review 12(4), 544–566 (1970)
Lu A., Wachspress E.: Solution of Lyapunov equations by Alternating Direction Implicit iteration. Comput. Math. Appl. 21(9), 43–58 (1991)
Malmquist, F.: Sur la détermination d’une class de fonctions analytiques par leur valeurs dans un ensemble donné de points. In Comptes Rendus du Sixième Congrès (1925) des mathématiciens scandinaves, pp. 253–259. Kopenhagen (1926)
Penzl T.: A cyclic low-rank Smith method for large sparse Lyapunov equations. SIAM J. Sci. Comput. 21(4), 1401–1418 (2000)
Saad Y.: Numerical solution of large Lyapunov equations. In: Kaashoek, M. A., van Schuppen, J. H., and Ran, A. C., (eds,) Signal Processing, Scattering, Operator Theory, and Numerical Methods. Proceedings of the international symposium MTNS-89, vol III, pp. 503–511, Boston, Birkhauser (1990)
Schilders W.H.A., van der Vorst H.A., Rommes J.: Model order reduction: theory, research aspects and applications. Springer-Verlag, Berlin (2008)
Simoncini V., Druskin V.: Convergence analysis of projection methods for the numerical solution of large Lyapunov equations. SIAM J. Numer. Anal. 47(2), 828–843 (2009)
Simoncini V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29(3), 1268–1288 (2007)
Suetin P.K.: Series of Faber Polynomials (Analytical Methods and Special Functions). Gordon and Breach Science Publishers, Amsterdam, Translated by E.V. Pankratiev (1998)
Suetin S.P.: On the Montessus de Ballore theorem for nonlinear Padé approximations of orthogonal expansions and Faber series. Dokl. AN SSSR 253(6), 1322–1325 (1980)
Takenaka S.: On the orthogonal functions and a new formula for interpolation. Jpn. J. Math. 2, 129–145 (1925)
Walsh, J.L.: Interpolation and Approximation by Rational Functions in the Complex Plane. Amer. Math. Soc., Providence, RI (1965)
Author information
Authors and Affiliations
Corresponding author
Additional information
Version of 20 December, 2010.
Rights and permissions
About this article
Cite this article
Knizhnerman, L., Simoncini, V. Convergence analysis of the extended Krylov subspace method for the Lyapunov equation. Numer. Math. 118, 567–586 (2011). https://doi.org/10.1007/s00211-011-0366-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-011-0366-3