On inexact Newton methods based on doubling iteration scheme for non-symmetric algebraic Riccati equations. (English) Zbl 1249.65093
Summary: Newton iteration method can be used to find the minimal non-negative solution of a certain class of non-symmetric algebraic Riccati equations. However, a serious bottleneck exists in efficiency and storage for the implementation of the Newton iteration method, which comes from the use of some direct methods in exactly solving the involved Sylvester equations. In this paper, instead of direct methods, we apply a fast doubling iteration scheme to inexactly solve the Sylvester equations. Hence, a class of inexact Newton iteration methods that uses the Newton iteration method as the outer iteration and the doubling iteration scheme as the inner iteration is obtained. The corresponding procedure is precisely described and two practical methods of monotone convergence are algorithmically presented. In addition, the convergence property of these new methods is studied and numerical results are given to show their feasibility and effectiveness for solving the non-symmetric algebraic Riccati equations.
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 15A24 | Matrix equations and identities |
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
Keywords:
non-symmetric algebraic Riccati equation; \(M\)-matrix; Newton iteration method; doubling iteration scheme; inexact iteration; minimal non-negative solution; Sylvester equations; monotone convergence; numerical resultsSoftware:
CAREXReferences:
| [1] | Berman, Nonnegative Matrices in the Mathematical Sciences (1994) · Zbl 0815.15016 · doi:10.1137/1.9781611971262 |
| [2] | Ortega, Iterative Solution of Nonlinear Equations in Several Variables (2000) · Zbl 0949.65053 · doi:10.1137/1.9780898719468 |
| [3] | Bellman, An Introduction to Invariant Embedding (1975) |
| [4] | Juang, Existence of algebraic matrix Riccati equations arising in transport theory, Linear Algebra and its Applications 230 pp 89– (1995) · Zbl 0839.15006 · doi:10.1016/0024-3795(93)00366-8 |
| [5] | Juang, Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices, SIAM Journal on Matrix Analysis and Applications 20 pp 228– (1999) · Zbl 0922.15003 · doi:10.1137/S0895479897318253 |
| [6] | Lu, Solution form and simple iteration of a nonsymmetric algebraic Riccati equation arising in transport theory, SIAM Journal on Matrix Analysis and Applications 26 pp 679– (2005) · Zbl 1072.15016 · doi:10.1137/S0895479801397275 |
| [7] | Lu, Newton iterations for a nonsymmetric algebraic Riccati equation, Numerical Linear Algebra with Applications 12 pp 191– (2005) · Zbl 1164.65386 · doi:10.1002/nla.411 |
| [8] | Bai, Fast iterative schemes for nonsymmetric algebraic Riccati equations arising from transport theory, SIAM Journal on Scientific Computing 30 pp 804– (2008) · Zbl 1166.65065 · doi:10.1137/060675344 |
| [9] | Bai, Alternately linearized implicit iteration methods for the minimal nonnegative solutions of the nonsymmetric algebraic Riccati equations, Numerical Linear Algebra with Applications 13 pp 655– (2006) · Zbl 1174.65381 · doi:10.1002/nla.500 |
| [10] | Guo, Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices, SIAM Journal on Matrix Analysis and Applications 23 pp 225– (2001) · Zbl 0996.65047 · doi:10.1137/S0895479800375680 |
| [11] | Guo, A note on the minimal nonnegative solution of a nonsymmetric algebraic Riccati equation, Linear Algebra and its Applications 357 pp 299– (2002) · Zbl 1017.15005 · doi:10.1016/S0024-3795(02)00431-7 |
| [12] | Guo, On the minimal nonnegative solution of nonsymmetric algebraic Riccati equation, Journal of Computational Mathematics 23 pp 305– (2005) · Zbl 1079.65052 |
| [13] | Guo, On the iterative solution of a class of nonsymmetric algebraic Riccati equations, SIAM Journal on Matrix Analysis and Applications 22 pp 376– (2000) · Zbl 0973.65025 · doi:10.1137/S089547989834980X |
| [14] | Bartels, Solution of the matrix equation AX+XB=C, Communications of the ACM 15 pp 820– (1972) · Zbl 1372.65121 · doi:10.1145/361573.361582 |
| [15] | Golub, A Hessenberg-Schur method for the problem AX+XB=C, IEEE Transactions on Automatic Control AC-24 pp 909– (1979) · Zbl 0421.65022 · doi:10.1109/TAC.1979.1102170 |
| [16] | Laub, A Schur method for solving algebraic Riccati equations, IEEE Transactions on Automatic Control AC-24 pp 913– (1979) · Zbl 0424.65013 · doi:10.1109/TAC.1979.1102178 |
| [17] | Golub, Matrix Computations (1996) |
| [18] | Guo, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numerische Mathematik 103 pp 393– (2006) · Zbl 1097.65055 · doi:10.1007/s00211-005-0673-7 |
| [19] | Feitzinger, Inexact Kleinman-Newton method for Riccati equations, SIAM Journal on Matrix Analysis and Applications 31 pp 272– (2009) · Zbl 1191.49033 · doi:10.1137/070700978 |
| [20] | Kleinman, On an iterative technique for Riccati equation computation, IEEE Transactions on Automatic Control AC-13 pp 114– (1968) · doi:10.1109/TAC.1968.1098829 |
| [21] | Smith, Matrix equation XA+BX=C, SIAM Journal on Applied Mathematics 16 pp 198– (1968) · Zbl 0157.22603 · doi:10.1137/0116017 |
| [22] | Guo, On the doubling algorithm for a (shifted) nonsymmetric algebraic Riccati equation, SIAM Journal on Matrix Analysis and Applications 29 pp 1083– (2007) · Zbl 1157.65025 · doi:10.1137/060660837 |
| [23] | Bai, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM Journal on Matrix Analysis and Applications 24 pp 603– (2003) · Zbl 1036.65032 · doi:10.1137/S0895479801395458 |
| [24] | Bai, Block triangular and skew-Hermitian splitting methods for positive-definite linear systems, SIAM Journal on Scientific Computing 26 pp 844– (2005) · Zbl 1079.65028 · doi:10.1137/S1064827503428114 |
| [25] | Sherman, On Newton-iterative methods for the solution of systems of nonlinear equations, SIAM Journal on Numerical Analysis 15 pp 755– (1978) · Zbl 0396.65019 · doi:10.1137/0715050 |
| [26] | Dembo, Inexact Newton methods, SIAM Journal on Numerical Analysis 19 pp 400– (1982) · Zbl 0478.65030 · doi:10.1137/0719025 |
| [27] | Ypma, Local convergence of inexact Newton methods, SIAM Journal on Numerical Analysis 21 pp 583– (1984) · Zbl 0566.65037 · doi:10.1137/0721040 |
| [28] | Bai, Affine invariant convergence of the inexact Newton method and Broyden’s method, Journal of Electronic Science and Technology of China 23 pp 535– (1994) |
| [29] | Barnett, Some applications of the Lyapunov matrix equation, IMA Journal of Numerical Analysis 4 pp 33– (1968) · Zbl 0155.12902 |
| [30] | Anderson, Second-order convergent algorithms for the steady-state Riccati equation, International Journal of Control 28 pp 295– (1978) · Zbl 0385.49017 · doi:10.1080/00207177808922455 |
| [31] | Wonham, On a matrix Riccati equation of stochastic control, SIAM Journal on Control 6 pp 681– (1968) · Zbl 0182.20803 · doi:10.1137/0306044 |
| [32] | Gajić, Lyapunov Matrix Equation in System Stability and Control (1995) |
| [33] | Guo, Iterative solution of a nonsymmetric algebraic Riccati equation, SIAM Journal on Matrix Analysis and Applications 29 pp 396– (2007) · Zbl 1146.65035 · doi:10.1137/050647669 |
| [34] | Bai, Optimal parameter in Hermitian and skew-Hermitian splitting method for certain two-by-two block matrices, SIAM Journal on Scientific Computing 28 pp 583– (2006) · Zbl 1116.65039 · doi:10.1137/050623644 |
| [35] | Starke, Optimal alternating direction implicit parameters for nonsymmetric systems of linear equations, SIAM Journal on Numerical Analysis 28 pp 1431– (1991) · Zbl 0739.65029 · doi:10.1137/0728074 |
| [36] | Abels J Benner P CAREX - a collection of benchmark examples for continuous-time algebraic Riccati equations (Version 2.0) 1999 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
