ON THE MINIMAL NONNEGATIVE SOLUTION OF ONSYMMETRIC ALGEBRAIC RICCATI EQUATION

We study perturbation bound and structured condition number about the minimalnonnegative solution of nonsymmetric algebraic Riccati equation,obtaining a sharp per-turbation bound and an accurate condition number.By using the matrix sign functionmethod we present a new method for finding the minimal nonnegative solution of this al-gebraic Riccati equation.Based on this new method,we show how to compute the desiredM-matrix solution of the quadratic matrix equation X~2-EX-F=0 by connecting itwith the nonsymmetric algebraic Riccati equation,where E is a diagonal matrix and F isan M-matrix.     

The King-Werner method for solving nonsymmetric algebraic Riccati equation

For the nonsymmetric algebraic Riccati equation arising from transport theory, we concern about solving its minimal positive solution. In [1], Lu transferred the equation into a vector form and pointed out that the minimal positive solution of the matrix equation could be obtained via computing that of the vector equation. In this paper, we use the King-Werner method to solve the minimal positive solution of the vector equation and give the convergence and error analysis of the method. Numerical tests show that the King-Werner method is feasible to determine the minimal positive solution of the vector equation.     

A new version of the Smith method for solving Sylvester equation and discrete-time Sylvester equation

Recently, Xue etc. \cite{28} discussed the Smith method for solving Sylvester equation $AX+XB=C$, where one of the matrices $A$ and $B$ is at least a nonsingular $M$-matrix and the other is an (singular or nonsingular) $M$-matrix. Furthermore, in order to find the minimal non-negative solution of a certain class of non-symmetric algebraic Riccati equations, Gao and Bai \cite{gao-2010} considered a doubling iteration scheme to inexactly solve the Sylvester equations. This paper discusses the iterative error of the standard Smith method used in \cite{gao-2010} and presents the prior estimations of the accurate solution $X$ for the Sylvester equation. Furthermore, we give a new version of the Smith method for solving discrete-time Sylvester equation or Stein equation $AXB+X=C$, while the new version of the Smith method can also be used to solve Sylvester equation $AX+XB=C$, where both $A$ and $B$ are positive definite. % matrices. We also study the convergence rate of the new Smith method. At last, numerical examples are given to illustrate the effectiveness of our methods     

A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation

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

A subspace shift technique for nonsymmetric algebraic Riccati equations associated with an M‐matrix

The worst situation in computing the minimal nonnegative solution of a nonsymmetric algebraic Riccati equation associated with an M‐matrix occurs when the corresponding linearizing matrix has two very small eigenvalues, one with positive and one with negative real part. When both eigenvalues are exactly zero, the problem is called critical or null recurrent. Although in this case the problem is ill‐conditioned and the convergence of the algorithms based on matrix iterations is slow, there exist some techniques to remove the singularity and transform the problem to a well‐behaved one. Ill‐conditioning and slow convergence appear also in close‐to‐critical problems, but when none of the eigenvalues is exactly zero, the techniques used for the critical case cannot be applied. In this paper, we introduce a new method to accelerate the convergence properties of the iterations also in close‐to‐critical cases, by working on the invariant subspace associated with the problematic eigenvalues as a whole. We present numerical experiments that confirm the efficiency of the new method.Copyright © 2012 John Wiley & Sons, Ltd.     

Convergence analysis of the Newton–Shamanskii method for a nonsymmetric algebraic Riccati equation

In this paper, we consider the nonsymmetric algebraic Riccati equation arising in transport theory. An important feature of this equation is that its minimal positive solution can be obtained via computing the minimal positive solution of a vector equation. We apply the Newton–Shamanskii method to solve the vector equation. Convergence analysis shows that the sequence of vectors generated by the Newton–Shamanskii method is monotonically increasing and converges to the minimal positive solution of the vector equation. Numerical experiments show that the Newton–Shamanskii method is feasible and effective, and outperforms the Newton method. Copyright © 2008 John Wiley & Sons, Ltd.     

Solving the nonnegative solution for a (shifted) nonsymmetric algebraic Riccati equation in the critical case

We are interested in computing the nonnegative solution of a nonsymmetric algebraic Riccati equation arising in transport theory. The coefficient matrices of this equation have two parameters c and α. There have been some iterative methods presented by Lu in [13] and Bai et al. in [2] to solve the minimal positive solution for or . While the equation has a unique nonnegative solution when c=1 and α=0, all the methods presented by Lu and Bai cannot be used to find the nonnegative solution. To cope with this problem, a shifted technique is used in this paper to transform the original Riccati equation into a new one so that all the methods can be effectively employed to solve the nonnegative solution. Numerical experiments are given to illustrate the results.     

Krylov subspace methods of Hessenberg based for algebraic Riccati equation

In this paper, we propose a class of special Krylov subspace methods to solve continuous algebraic Riccati equation (CARE), i.e., the Hessenberg-based methods. The presented approaches can obtain efficiently the solution of algebraic Riccati equation to some extent. The main idea is to apply Kleinman-Newton"s method to transform the process of solving algebraic Riccati equation into Lyapunov equation at every inner iteration. Further, the Hessenberg process of pivoting strategy combined with Petrov-Galerkin condition and minimal norm condition is discussed for solving the Lyapunov equation in detail, then we get two methods, namely global generalized Hessenberg (GHESS) and changing minimal residual methods based on the Hessenberg process (CMRH) for solving CARE, respectively. Numerical experiments illustrate the efficiency of the provided methods.     

On algebraic Riccati equations associated with M-matrices

We consider the algebraic Riccati equation for which the four coefficient matrices form an M-matrix K. When K is a nonsingular M-matrix or an irreducible singular M-matrix, the Riccati equation is known to have a minimal nonnegative solution and several efficient methods are available to find this solution. In this paper we are mainly interested in the case where K is a reducible singular M-matrix. Under a regularity assumption on the M-matrix K, we show that the Riccati equation still has a minimal nonnegative solution. We also study the properties of this particular solution and explain how the solution can be found by existing methods.     

Backward error,sensitivity, and refinement of computed solutions of algebraic Riccati equations

In this paper, a new backward error criterion, together with a sensitivity measure, is presented for assessing solution accuracy of nonsymmetric and symmetric algebraic Riccati equations (AREs). The usual approach to assessing reliability of computed solutions is to employ standard perturbation and sensitivity results for linear systems and to extend them further to AREs. However, such methods are not altogether appropriate since they do not take account of the underlying structure of these matrix equations. The approach considered here is to first compute the backward error of a computed solution X? that measures the amount by which data must be perturbed so that X? is the exact solution of the perturbed original system. Conventional perturbation theory is used to define structured condition numbers that fully respect the special structure of these matrix equations. The new condition number, together with the backward error of computed solutions, provides accurate estimates for the sensitivity of solutions. Optimal perturbations are then used in an iterative refinement procedure to give further more accurate approximations of actual solutions. The results are derived in their most general setting for nonsymmetric and symmetric AREs. This in turn offers a unifying framework through which it is possible to establish similar results for Sylvester equations, Lyapunov equations, linear systems, and matrix inversions.     

Fast verified computation for solutions of algebraic Riccati equations arising in transport theory

A fast algorithm for enclosing the solution of the nonsymmetric algebraic Riccati equation arising in transport theory is proposed. The equation has a special structure, which is taken into account to reduce the complexity. By exploiting the structure, the enclosing process involves only quadratic complexity under a reasonable assumption. The algorithm moreover verifies the uniqueness and minimal positiveness of the enclosed solution. Numerical results show the efficiency of the algorithm.     

Solution of the matrix Riccati equation for the linear quadratic control problems

This paper is concerned with the solution of the matrix Riccati differential equation with a terminal boundary condition. The solution of the matrix Riccati equation is given by using the solution of the algebraic form of the Riccati equation. An illustrative example for the proposed method is given.     

Sensitivity analysis of the algebraic Riccati equations

Summary. In this paper, some sharp perturbation bounds for the Hermitian positive semi-definite solution to an algebraic Riccati equation are developed. A further analysis for these bounds is done. This analysis shows that there is, presumably, some intrinsic relation between the sensitivity of the solution to the algebraic Riccati equation and the distance of the spectrum of the closed-loop matrix from the imaginary axis. Received December 16, 1994     

关于离散代数Riccati方程的扰动分析

1．引言若不特别说明,以下记号都是常规的,可参见山．在最优控制中占有核心地位的代数Xiccati方程（ARE）有两种基本形式：连续型的ARE（CARE）：离散型的＊＊E（＊＊RE）：其中只兄见NE贮””,GIE皿””m,GZE＊m”m,in＜2,＊T二K＞风＊T二N＞几＊2二＊2＞凡从应用角度看,主要关心＊＊E的对称半正定解．对于＊＊RE,已有大量的研究工作．特别,陈春晖门、徐树方问、Ghwimi－Laub同等研究了扰动理论．对于DARE,它与＊＊＊E的一个明显区别是：＊＊M是二次矩阵方程而＊＊＊E具有高度非线性．这种区别使得DARE远为复杂…     

Solving the algebraic Riccati equation with the matrix sign function

This paper presents some improvements to the matrix-sign-function algorithm for the algebraic Riccati equation. A simple reorganization changes nonsymmetric matrix inversions into symmetric matrix inversions. Scaling accelerates convergence of the basic iteration and yields a new quadratic formula for certain 2-by-2 algebraic Riccati equations. Numerical experience suggests the algorithm be supplemented with a refinement strategy similar to iterative refinement for systems of linear equations. Refinement also produces an error estimate. The resulting procedure is numerically stable. It compares favorably with current Schur vector-based algorithms.     

The double deflating technique for irreducible singular M-matrix algebraic Riccati equations in the critical case

As is known, Alternating-Directional Doubling Algorithm (ADDA) is quadratically convergent for computing the minimal nonnegative solution of an irreducible singular M-matrix algebraic Riccati equation (MARE) in the noncritical case or a nonsingular MARE, but ADDA is only linearly convergent in the critical case. The drawback can be overcome by deflating techniques for an irreducible singular MARE so that the speed of quadratic convergence is still preserved in the critical case and accelerated in the noncritical case. In this paper, we proposed an improved deflating technique to accelerate further the convergence speed – the double deflating technique for an irreducible singular MARE in the critical case. We proved that ADDA is quadratically convergent instead of linearly when it is applied to the deflated algebraic Riccati equation (ARE) obtained by a double deflating technique. We also showed that the double deflating technique is better than the deflating technique from the perspective of dimension of the deflated ARE. Numerical experiments are provided to illustrate that our double deflating technique is effective.     

Delta算子Riccati方程研究的新结果

基于Delta算子描述，统一研究连续时间代数Riccati方程(CARE)和离散时间代数Riccati方程(DARE)的定界估计问题，提出了统一代数Riccati方程(UARE)解矩阵的上下界，给出UARE中P与R和Q的几个基本关系．     

A noniterative algebraic solution for Riccati equations satisfying two-point boundary-value problems

A noniterative algebraic method is presented for solving differential Riccati equations which satisfy two-point boundary-value problems. This class of numerical problems arises in quadratic optimization problems where the cost functionals are composed of both continuous and discrete state penalties, leading to piecewise periodic feedback gains. The necessary condition defining the solution for the two-point boundary value problem is cast in the form of a discrete-time algebraic Riccati equation, by using a formal representation for the solution of the differential Riccati equation. A numerical example is presented which demonstrates the validity of the approach.The authors would like to thank Dr. Fernando Incertis, IBM Madrid Scientific Center, who reviewed this paper and pointed out that the two-point boundary-value necessary condition could be manipulated into the form of a discrete-time Riccati equation. His novel approach proved to be superior to the authors' previously proposed iterative continuation method.     

Monotone convergence of Newton-like methods for M-matrix algebraic Riccati equations

For the algebraic Riccati equation whose four coefficient matrices form a nonsingular M-matrix or an irreducible singular M-matrix K, the minimal nonnegative solution can be found by Newton’s method and the doubling algorithm. When the two diagonal blocks of the matrix K have both large and small diagonal entries, the doubling algorithm often requires many more iterations than Newton’s method. In those cases, Newton’s method may be more efficient than the doubling algorithm. This has motivated us to study Newton-like methods that have higher-order convergence and are not much more expensive each iteration. We find that the Chebyshev method of order three and a two-step modified Chebyshev method of order four can be more efficient than Newton’s method. For the Riccati equation, these two Newton-like methods are actually special cases of the Newton–Shamanskii method. We show that, starting with zero initial guess or some other suitable initial guess, the sequence generated by the Newton–Shamanskii method converges monotonically to the minimal nonnegative solution.We also explain that the Newton-like methods can be used to great advantage when solving some Riccati equations involving a parameter.     

Residual bounds of approximate solutions of the algebraic Riccati equation

Summary. Let approximate the unique Hermitian positive semi-definite solution to the algebraic Riccati equation (ARE) where , is stabilizable, and is detectable. Let be the residual of the ARE with respect to , and define the linear operator by By applying a new forward perturbation bound to the optimal backward perturbation corresponding to the approximate solution , we obtained the following result: If is stable, and if for any unitarily invariant norm , then Received April 28, 1995 / Revised version received August 30, 1995