ON EIGENVALUE BOUNDS AND ITERATION METHODS FOR DISCRETE ALGEBRAIC RICCATI EQUATIONS

doi:10.4208/jcm.1010-m3258

Journal of Computational Mathematics ›› 2011, Vol. 29 ›› Issue (3): 341-366.DOI: 10.4208/jcm.1010-m3258

• Original Articles • Previous Articles

ON EIGENVALUE BOUNDS AND ITERATION METHODS FOR DISCRETE ALGEBRAIC RICCATI EQUATIONS

Hua Dai¹, Zhong-Zhi Bai²

1. Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China;
2. LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

Received:2009-11-11 Revised:2010-09-14 Online:2011-05-15 Published:2011-05-15
Supported by:
This work was started when the first author was visiting State Key Lab-oratory of Scientific/Engineering Computing, Chinese Academy of Sciences, during March-May in 2008. The support and hospitality from LSEC are very much appreciated. Supported by The National Basic Research Program (No. 2005CB321702), The China Outstanding Young Scien-tist Foundation (No. 10525102), and The National Natural Science Foundation for Innovative Research Groups (No. 11021101), P.R. China.

PDF ( 327 ) Cited

Hua Dai, Zhong-Zhi Bai. ON EIGENVALUE BOUNDS AND ITERATION METHODS FOR DISCRETE ALGEBRAIC RICCATI EQUATIONS[J]. Journal of Computational Mathematics, 2011, 29(3): 341-366.

We derive new and tight bounds about the eigenvalues and certain sums of the eigen-values for the unique symmetric positive definite solutions of the discrete algebraic Riccati equations. These bounds considerably improve the existing ones and treat the cases that have been not discussed in the literature. Besides, they also result in completions for the available bounds about the extremal eigenvalues and the traces of the solutions of the discrete algebraic Riccati equations. We study the fixed-point iteration methods for com-puting the symmetric positive definite solutions of the discrete algebraic Riccati equations and establish their general convergence theory. By making use of the Schulz iteration to partially avoid computing the matrix inversions, we present effective variants of the fixed-point iterations, prove their monotone convergence and estimate their asymptotic convergence rates. Numerical results show that the modified fixed-point iteration methods are feasible and effective solvers for computing the symmetric positive definite solutions of the discrete algebraic Riccati equations.

Key words: Discrete algebraic Riccati equation, Symmetric positive definite solution, Eigenvalue bound, Fixed-point iteration, Convergence theory

CLC Number:

[1] B.D.O. Anderson, Second-order convergent algorithms for the steady-state Riccati equation,Intern. J. Control, 28 (1978), 295-306.

[2] B.D.O. Anderson and J.B. Moore, Optimal Filtering, Prentice-Hall, Englewood Cliffs, New Jersey,1979.

[3] W.F. Arnold III and A.J. Laub, Generalized eigenproblem algorithms and software for algebraicRiccati equations, Proc. IEEE, 72 (1984), 1746-1754.

[4] A.Y. Barraud, A numerical algorithm to solve A^TXA-X = Q, IEEE Trans. Automat. Control,AC-22 (1977), 883-885.

[5] P. Benner, A.J. Laub and V. Mehrmann, A Collection of Benchmark Examples for the NumericalSolution of Algebraic Riccati Equations II: Discrete-Time Case, Technical Report SPC 95-23,Faculty of Mathematics, TU Chemnitz-Zwickau, D-09107 Chemnitz, December 1995.

[6] P. Benner, V. Mehrmann and H.-G. Xu, A numerically stable, structure preserving method forcomputing the eigenvalues of real Hamiltonian or symplectic pencils, Numer. Math., 78 (1998),329-358.

[7] H. Dai, The Theory of Matrices, Science Press, Beijing, 2001.

[8] R. Davies, P. Shi and R. Wiltshire, New upper solution bounds of the discrete algebraic Riccatimatrix equation, J. Comput. Appl. Math., 213 (2008), 307-315.

[9] J. Garloff, Bounds for the eigenvalues of the solution of the discrete Riccati and Lyapunovequations and the continuous Lyapunov equation, Intern. J. Control, 43 (1986), 423-431.

[10] G.H. Golub and C.F. Van Loan, Matrix Computations, 3rd Edition, The Johns Hopkins UniversityPress, Baltimore and London, MD, 1996.

[11] C.-H. Guo, Newton's method for discrete algebraic Riccati equations when the closed-loop matrixhas eigenvalues on the unit circle, SIAM J. Matrix Anal. Appl., 20 (1998), 279-294.

[12] T.-M. Hwang, E.K.-W. Chu and W.-W. Lin, A generalized structure-preserving doubling algo-rithm for generalized discrete-time algebraic Riccati equations, Intern. J. Control, 78 (2005),1063-1075.

[13] S.W. Kim, P. Park and W.H. Kwon, Lower bounds for the trace of the solution of the discretealgebraic Riccati equation, IEEE Trans. Automat. Control, 38 (1993), 312-314.

[14] M. Kimura, Convergence of the doubling algorithm for the discrete-time algebraic Riccati equation,Intern. J. Systems Sci., 19 (1988), 701-711.

[15] G. Kitagawa, An algorithm for solving the matrix equation X = FXF^T + S, Intern. J. Control,25 (1977), 745-753.

[16] N. Komaroff, Upper bounds for the eigenvalues of the solution of the Lyapunov matrix equation,IEEE Trans. Automat. Control, 35 (1990), 737-739.

[17] N. Komaroff, Upper bounds for the solution of the discrete Riccati equation, IEEE Trans.Automat. Control, 37 (1992), 1370-1372.

[18] N. Komaroff, Iterative matrix bounds and computational solutions to the discrete algebraic Riccatiequation, IEEE Trans. Automat. Control, 39 (1994), 1676-1678.

[19] N. Komaroff and B. Shahian, Lower summation bounds for the discrete Riccati and Lyapunovequations, IEEE Trans. Automat. Control, 37 (1992), 1078-1080.

[20] V.S. Kouikoglou and Y.A. Phillis, Trace bounds on the covariances of continuous-time systemswith multiplicative noise, IEEE Trans. Automat. Control, 38 (1993), 138-142.

[21] H. Kwakernaak and R. Sivan, Linear Optimal Control Systems, John Wiley & Sons, New York,1972.

[22] B.H. Kwon, M.J. Youn and Z. Bien, On bounds of the Riccati and Lyapunov matrix equations,IEEE Trans. Automat. Control, AC-30 (1985), 1134-1135.

[23] W.H. Kwon, Y.S. Moon and S.C. Ahn, Bounds in algebraic Riccati and Lyapunov equations: asurvey and some new results, Intern. J. Control, 64 (1996), 377-389.

[24] P. Lancaster and L. Rodman, Algebraic Riccati Equations, The Clarendon Press, Oxford andNew York, 1995.

[25] A.J. Laub, A Schur method for solving algebraic Riccati equations, IEEE Trans. Automat.Control, AC-24 (1979), 913-921.

[26] C.-H. Lee, On the matrix bounds for the solution matrix of the discrete algebraic Riccati equation,IEEE Trans. Circuits Systems-I: Fundamental Theory Appl., 43 (1996), 402-407.

[27] C.-H. Lee, Upper matrix bound of the solution for the discrete Riccati equation, IEEE Trans.Automat. Control, 42 (1997), 840-842.

[28] C.-H. Lee, Upper and lower bounds of the solutions of the discrete algebraic Riccati and Lyapunovmatrix equations, Intern. J. Control, 68 (1997), 579-598.

[29] C.-H. Lee, Simple stabilizability criteria and memoryless state feedback control design for time-delay systems with time-varying perturbations, IEEE Trans. Circuits Systems-I: FundamentalTheory Appl., 45 (1998), 1211-1215.

[30] C.-H. Lee, Matrix bounds of the solutions of the continuous and discrete Riccati equations-aunified approach, Intern. J. Control, 76 (2003), 635-642.

[31] W.-W. Lin and C.-S. Wang, On computing stable Lagrangian subspaces of Hamiltonian matricesand symplectic pencils, SIAM J. Matrix Anal. Appl., 18 (1997), 590-614.

[32] W.-W. Lin and S.-F. Xu, Convergence analysis of structure-preserving doubling algorithms forRiccati-type matrix equations, SIAM J. Matrix Anal. Appl., 28 (2006), 26-39.

[33] L.-Z. Lu and W.-W. Lin, An iterative algorithm for the solution of the discrete-time algebraicRiccati equation, Linear Algebra Appl., 188/189 (1993), 465-488.

[34] L.-Z. Lu, W.-W. Lin, and C.E.M. Pearce, An efficient algorithm for the discrete-time algebraicRiccati equation, IEEE Trans. Automat. Control, 44 (1999), 1216-1220.

[35] A.W. Marshall and I. Olkin, Inequalities: Theory of Majorization and Its Applications, AcademicPress, New York and London, 1979.

[36] V. Mehrmann, The Autonomous Linear Quadratic Control Problem: Theory and NumericalSolution, in Lecture Notes in Control and Information Sciences 163, Springer-Verlag, Berlin,1991.

[37] T. Mori and I.A. Derese, A brief summary of the bounds on the solution of the algebraic matrixequations in control theory, Intern. J. Control, 39 (1984), 247-256.

[38] T. Mori, N. Fukuma and M. Kuwahara, On the discrete Riccati equation, IEEE Trans. Automat.Control, AC-32 (1987), 828-829.

[39] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables,SIAM, Philadelphia, PA, 2000.

[40] T. Pappas, A.J. Laub and N.R. Sandell, On the numerical solution of the discrete-time algebraicRiccati equation, IEEE Trans. Automat. Control, AC-25 (1980), 631-641.

[41] G. Schulz, Iterative berechnung der reziproken matrix, Z. Angew. Math. Mech., 13 (1933), 57-59.

[42] M.T. Tran and M.E. Sawan, On the discrete Riccati matrix equation, SIAM J. Alg. Disc. Meth.,6 (1985), 107-108.

[43] S.-S. Wang, B.-S. Chen and T.-P. Lin, Robust stability of uncertain time-delay systems, Intern.J. Control, 46 (1987), 963-976.

[44] W.M. Wonham, Linear Multivariable Control: A Geometric Approach, 2nd Edition, Springer-Verlag, New York and Berlin, 1979.

[45] K. Yasuda and K. Hirai, Upper and lower bounds on the solution of the algebraic Riccati equation,IEEE Trans. Automat. Control, AC-24 (1979), 483-487.

[46] X.-Z. Zhan, Computing the extremal positive definite solutions of a matrix equation, SIAM J.Sci. Comput., 17 (1996), 1167-1174.

[1]	Zhi-Ru Ren. BANDED TOEPLITZ PRECONDITIONERS FOR TOEPLITZMATRICES FROM SINC METHODS [J]. Journal of Computational Mathematics, 2012, 30(5): 533-543.
[2]	Caifang Wang, Tie Zhou. LOCAL CONVERGENCE OF AN EM-LIKE IMAGE RECONSTRUCTION METHOD FOR DIFFUSE OPTICAL TOMOGRAPHY [J]. Journal of Computational Mathematics, 2011, 29(1): 61-73.
[3]	Zhong Zhi BAI,YU Guang HUANG. A CLASS OF ASYNCHRONOUS PARALLEL MULTISPLITTING RELAXATION METHODS FOR LARGE SPARSE LINEAR COMPLEMENTARITY PROBLEMS$^*1$ [J]. Journal of Computational Mathematics, 2003, 21(6): 773-790.
[4]	Zhong-zhi Bai,Tin-zhu Huang. ON THE CONVERGENCE OF THE RELAXATION METHODS FOR POSITIVE DEFINITELINEAR SYSTEMS [J]. Journal of Computational Mathematics, 1998, 16(6): 527-538.

Viewed

Full text

Abstract

ON EIGENVALUE BOUNDS AND ITERATION METHODS FOR DISCRETE ALGEBRAIC RICCATI EQUATIONS

扫码分享