Skip to main content
SpringerLink
Log in

Convergence analysis of the extended Krylov subspace method for the Lyapunov equation

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Antoulas A.C.: Approximation of large-scale dynamical systems. SIAM, Philadelphia (2005)

    Book  MATH  Google Scholar 

  2. Beckermann B.: Image numérique, GMRES et polynômes de Faber. C. R Acad. Sci. Paris Ser. I 340, 855–860 (2005)

    MathSciNet  MATH  Google Scholar 

  3. Beckermann B., Reichel L.: Error estimation and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal. 47(5), 3849–3883 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Benner, P., Mehrmann, V., Sorensen, D. (eds): Dimension reduction of large-scale systems. Lecture notes in computational science and engineering. Springer-Verlag, Berlin (2005)

    Google Scholar 

  5. Bultheel A., González-Vera P., Hendriksen E., Njåstad O.: Orthogonal rational functions. Cambridge University Press, Cambridge (1999)

    Book  MATH  Google Scholar 

  6. Crouzeix M.: Numerical range and numerical calculus in Hilbert space. J. Funct. Anal. 244, 668–690 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  7. 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)

    Article  MathSciNet  Google Scholar 

  8. 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)

    Article  MathSciNet  MATH  Google Scholar 

  9. 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)

    Article  MathSciNet  MATH  Google Scholar 

  10. 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)

    MathSciNet  MATH  Google Scholar 

  11. Ellacott S.W.: On the Faber transformation and efficient numerical rational approximation. SIAM J. Numer. Anal. 20(5), 989–1000 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gaier D.: The Faber operator and its boundedness. J. Approx. Theory 101(2), 265–277 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  13. Godunov, S.K.: Lectures on modern aspects of linear algebra. Nauchnaya Kniga (IDMI), Novosibirsk, (In Russian) (2002)

  14. Goluzin G.M.: Geometric theory of functions of a complex variable. American Mathematical Society, Providence, RI (1969)

    MATH  Google Scholar 

  15. Hochbruck M., Lubich C.: On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 34(5), 1911–1925 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  16. Hochbruck M., Starke G.: Preconditioned Krylov subspace methods for Lyapunov matrix equations. SIAM Matrix Anal. and Appl. 16(1), 156–171 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  17. Jagels C., Reichel L.: The extended Krylov subspace method and orthogonal Laurent polynomials. Lin. Alg. Appl. 431, 441–458 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Jaimoukha I.M., Kasenally E.M.: Krylov subspace methods for solving large Lyapunov equations. SIAM J. Numer. Anal. 31(1), 227–251 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  19. Jbilou K., Riquet A.J.: Projection methods for large Lyapunov matrix equations. Lin. Algebra Appl. 415(2–3), 344–358 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  20. 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)

    MathSciNet  Google Scholar 

  21. 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)

    MATH  Google Scholar 

  22. Kressner, D., Tobler., C.: Krylov subspace methods for linear systems with tensor product structure. Technical Report SAM-2009-16, ETH Zurich (2009)

  23. Kressner D., Tobler C.: Krylov subspace methods for linear systems with tensor product structure. SIAM J. Matrix Anal. Appl. 31(4), 1688–1714 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  24. Lancaster P.: Explicit solutions of linear matrix equations. SIAM Review 12(4), 544–566 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  25. Lu A., Wachspress E.: Solution of Lyapunov equations by Alternating Direction Implicit iteration. Comput. Math. Appl. 21(9), 43–58 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  26. 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)

  27. Penzl T.: A cyclic low-rank Smith method for large sparse Lyapunov equations. SIAM J. Sci. Comput. 21(4), 1401–1418 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  28. 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)

  29. Schilders W.H.A., van der Vorst H.A., Rommes J.: Model order reduction: theory, research aspects and applications. Springer-Verlag, Berlin (2008)

    Book  MATH  Google Scholar 

  30. 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)

    Article  MathSciNet  MATH  Google Scholar 

  31. Simoncini V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29(3), 1268–1288 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  32. Suetin P.K.: Series of Faber Polynomials (Analytical Methods and Special Functions). Gordon and Breach Science Publishers, Amsterdam, Translated by E.V. Pankratiev (1998)

  33. 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)

    MathSciNet  Google Scholar 

  34. Takenaka S.: On the orthogonal functions and a new formula for interpolation. Jpn. J. Math. 2, 129–145 (1925)

    Google Scholar 

  35. Walsh, J.L.: Interpolation and Approximation by Rational Functions in the Complex Plane. Amer. Math. Soc., Providence, RI (1965)

Download references

Author information

Authors and Affiliations

  1. Central Geophysical Expedition, house 38, building 3, Narodnogo opolcheniya St., 123298, Moscow, Russia

    L. Knizhnerman

  2. Dipartimento di Matematica, CIRSA, Università di Bologna, Piazza di Porta S. Donato 5, 40127, Bologna, Ravenna, Italy

    V. Simoncini

Authors
  1. L. Knizhnerman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. V. Simoncini
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. Simoncini.

Additional information

Version of 20 December, 2010.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-011-0366-3

Mathematics subject classification

Search

Navigation