A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation (Q2494373): Difference between revisions

The authors consider the nonsymmetric algebraic Riccati equation (NARE) in \(X\in{\mathbb R}^{m\times n}\): \(XCX-XD-AX+B=0\) and its dual equation in \(Y\in{\mathbb R}^{n\times m}\): \(YBY-YA-DY+C=0\), where \(A\in{\mathbb R}^{m\times m}\), \(D\in{\mathbb R}^{n\times n}\), \(B\) and \(C^T\in{\mathbb R}^{m\times n}\). For NARE and its dual equation to have a minimal nonnegative solution \(X\) and \(Y\) the following sufficient condition is assumed: \({\mathcal K}= \left[\begin{matrix} \phantom{-}D& -C \\ -B &\phantom{-}A\end{matrix}\right]\) is a nonsingular \(M\)-matrix. This condition implies that \(D-CX\) and \(A-BY\) are nonsingular \(M\)-matrices. The proposed generalized structure-preserving doubling algorithm (SDA) for computing the minimal nonnegative solution \(X\) and \(Y\) requires, at each step, only two \(LU\)-factorizations and several matrix computations which amount to \((64/3)n^3\) flops (assuming \(m=n\)). The convergence theory is established and a practical implementation and some error estimates are discussed. Numerical experiments using MATLAB show that SDA is about 2 to 10 times more efficient than Newton's iteration method, and about 2 to 60 times more efficient than the fixed-point iteration methods. SDA can be easily implemented in parallel computer environments.