A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation | Numerische Mathematik Skip to main content
Springer Nature Link
Log in

A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

In this paper, we propose a structure-preserving doubling algorithm (SDA) for the computation of the minimal nonnegative solution to the nonsymmetric algebraic Riccati equation (NARE), based on the techniques developed for the symmetric cases. This method allows the simultaneous approximation to the minimal nonnegative solutions of the NARE and its dual equation, requiring only the solutions to two linear systems and several matrix multiplications per iteration. Similar to Newton's method and the fixed-point iteration methods for solving NAREs, we also establish global convergence for SDA under suitable conditions, using only elementary matrix theory. We show that sequences of matrices generated by SDA are monotonically increasing and quadratically convergent to the minimal nonnegative solutions of the NARE and its dual equation. Numerical experiments show that the SDA algorithm is feasible and effective, and outperforms Newton's iteration and the fixed-point iteration methods.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anderson, B.: Second-order convergent algorithm for the steady-state Riccati equation. Int. J. Control 28, 295–306 (1978)

    MATH  Google Scholar 

  2. Bai, Z., Demmel, J., Gu, M.: An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems. Numer. Math. 76, 279–308 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  3. Barlow, M., Rogers, L., Williams, D.: Wiener-Hopf factorization of matrices. In: Séminaire de Probabilités XIV, no. 784, Lecture Notes in Math., Springer-Verlag, 1980, pp. 324–331

  4. Bartels, R., Stewart, G.: Solution of the matrix equation AX+XB=C. Comm. ACM 15, 820–826 (1972)

    Article  Google Scholar 

  5. Bazarra, M., Sheraii, H., Shetty, C.: Nonlinear programming. John Wiley & Sons, 1993

  6. Benner, P.: Contributions to the numerical solutions of algebraic Riccati equations and related eigenvalue problems. PhD Dissertation, Fakultät für Mathematik, TU Chemnitz-Zwickau, Chemnitz, Germany, 1997

  7. Benner, P., Byers, R.: Disk functions and their relationship to the matrix sign function. In: Proc. European Control Conf. ECC 97, Paper 936, (CD-ROM). Waterloo, Belgium, 1997, BELWARE Information Technology

  8. Benner, P., Byers, R.: Evaluating products of matrix pencils and collapsing matrix products. Num. Lin. Alg. Appl. 8, 357–380 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  9. Berman, A., Plemmons, R.: Nonnegative Matrices in the Mathematical Sciences. Academic Press, 1979

  10. Chu, E.-W., Fan, H.-Y., Lin, W.-W.: structure-preserving doubling algorithm for cotinuous-time algebraic Riccati equations. Lin. Alg. Appl. 396, 55–80 (2005)

    Article  MATH  Google Scholar 

  11. Chu, E.-W., Fan, H.-Y., Lin, W.-W., Wang, C.-S.: Structure-preserving doubling algorithms for periodic discrete-time algebraic Riccati equations. Int. J. Control 77, 767–788 (2004)

    Article  MATH  Google Scholar 

  12. Golub, G., Nash, S., Van Loan, C.: A Hessenberg-Schur method for the problem AX+XB=C. IEEE Trans. Auto. Control 24, 909–913 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  13. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd ed. The Johns Hopkins University Press, 1996

  14. Guo, C.-H.: Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices. SIAM J. Matrix Analy. Appl. 23, 225–242 (2001)

    Article  MATH  Google Scholar 

  15. Guo, C.-H., Laub, A.: On the iterative solution of a class of nonsymmetric algebraic Riccati equations. SIAM J. Matrix Analy. Appl. 22, 376–391 (2000)

    Article  MATH  Google Scholar 

  16. Juang, J.: Existence of algebraic matrix Riccati equations arising in transport theory. Lin. Alg. Appl. 230, 89–100 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  17. Juang, J., Lin, W.-W.: Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices. SIAM J. Matrix Analy. Appl. 20, 228–243 (1999)

    Article  MathSciNet  Google Scholar 

  18. Lin, W.-W., Xu, S.-F.: Analysis of structure-preserving doubling algorithms for Riccati-type matrix equations. SIAM J. Matrix Analy. Appl. 2005, to appear

  19. London, R., Mckean, H., Rogers, L., Williams, D.: A martingale approach to some Wiener-Hopf problems II. In: Séminaire de Probabilités XVI. no. 920, Lecture Notes in Math., Springer-Verlag, 1982, pp. 68–90

  20. Rogers, L.: Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains. Ann. Appl. Probab. 4, 390–413 (1994)

    MATH  MathSciNet  Google Scholar 

  21. Rogers, L., Shi, Z.: Computing the invariant law of a fluid model. J. Appl. Probab. 31, 885–896 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  22. Sun, X., Quintana-Ortí, E.: Spectral division methods for block generalized Schur decompositions. Math. Comp. 73, 1827–1847 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  23. Varga, R.: Matrix iterative analysis. Prentice-Hall, 1962

  24. Williams, D.: A ``potential-theoretic'' note on the quadratic Wiener-Hopf equation for Q-matrices. In: Séminaire de Probabilités XVI. no. 920, Lecture Notes in Math., Springer-Verlag, 1982, pp. 91–94

Download references

Author information

Authors and Affiliations

  1. State Key Laboratory of Scientific/Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, P.O. Box 2719, Beijing, 100080, China

    Xiao-Xia Guo

  2. Department of Mathematics, National Tsing Hua University, Hsinchu, 300, Taiwan

    Wen-Wei Lin

  3. LMAM, School of Mathematical Sciences, Peking University, Beijing, 100871, China

    Shu-Fang Xu

Authors
  1. Xiao-Xia Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wen-Wei Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shu-Fang Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiao-Xia Guo.

Additional information

This research was supported in part by RFDP (20030001103) & NSFC (10571007) of China and the National Center for Theoretical Sciences in Taiwan.

This author's research was supported by NSFC grant 1057 1007 and RFDP grant 200300001103 of China.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Guo, XX., Lin, WW. & Xu, SF. A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation. Numer. Math. 103, 393–412 (2006). https://doi.org/10.1007/s00211-005-0673-7

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-005-0673-7

Keywords

Search

Navigation