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.     

Semiconvergence of extrapolated iterative methods for singular linear systems

In this paper, we discuss convergence of the extrapolated iterative methods for solving singular linear systems. A general principle of extrapolation is presented. The semiconvergence of an extrapolated method induced by a regular splitting and a nonnegative splitting is proved whenever the coefficient matrix A is a singular M-matrix with ‘property c’ and an irreducible singular M-matrix, respectively. Since the (generalized, block) JOR and AOR methods are respectively the extrapolated methods of the (generalized, block) Jacobi and SOR methods, so the semiconvergence of the (generalized, block) JOR and AOR methods for solving general singular systems are proved. Furthermore, the semiconvergence of the extrapolated power method, the (block) JOR, AOR and SOR methods for solving Markov chains are discussed.     

Convergence of the solution of a nonsymmetric matrix Riccati differential equation to its stable equilibrium solution

We consider the initial value problem for a nonsymmetric matrix Riccati differential equation, where the four coefficient matrices form an M-matrix. We show that for a wide range of initial values the Riccati differential equation has a global solution X(t) on [0,∞) and X(t) converges to the stable equilibrium solution as t goes to infinity.     

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.     

On the Minimal Nonnegative Solution of Nonsymmetric Algebraic Riccati Equation

We study perturbation bound and structured condition number about the minimal nonnegative solution of nonsymmetric algebraic Riccati equation, obtaining a sharp perturbation bound and an accurate condition number. By using the matrix sign function method we present a new method for finding the minimal nonnegative solution of this algebraic Riccati equation. Based on this new method, we show how to compute the desired M-matrix solution of the quadratic matrix equation X^2 - EX - F = 0 by connecting it with the nonsymmetric algebraic Riccati equation, where E is a diagonal matrix and F is an M-matrix.     

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

A note on factorizations of singular M-matrices

Supposing that M is a singular M-matrix, we show that there exists a permutation matrix P such that PMP^T = LU, where L is a lower triangular M-matrix and U is an upper triangular singular M-matrix. An example is given to illustrate that the above result is the best possible one.     

Nonnegativity of principal minors of generalized inverses of M-matrices

The result of principal interest established in this paper is that if A is an n × n singular irreducible M-matrix, then a large class of generalized inverses of A possesses the property that each of its elements has all its principal minors nonnegative. The class contains both the group and the Moore-Penrose generalized inverses of A. In an application of our results it is shown that the fundamental matrix of a continuous (in time) ergodic Markov chain on a finite state space has all its principal minors nonnegative.     

Nonnegativity of principal minors of generalized inverses of P0-matrices

We derive a necessary and sufficient condition under which a reflexive generalized inverse of a singular P₀-matrix is again a P₀-matrix. Simpler conditions are obtained when the rank of the matrix is n?1, where n is the order of the matrix. We then consider the application of these results to singular M-matrices of order n and rank n?1. In particular, for this case we prove that the Moore-Penrose inverse is a P₀-matrix.     

The Schur complement and the inverse M-matrix problem

It is well known that if M is a nonnegative nonsingular inverse M-matrix and if A is a nonsingular block in the upper left hand corner, then the Schur complement of A in M, (M ? A), is an inverse M-matrix. The converse of this is generally false. In this paper we give added restrictions on M or A to insure the converse, and give some necessary and sufficient conditions for HMH^?1, where H = I⊕(?I), to be an M-matrix.     

Quadratic programming with M-Matrices

In this paper, we study the problem of quadratic programming with M-matrices. We describe (1) an effective algorithm for the case where the variables are subject to a lower-bound constraint, and (2) an analogous algorithm for the case where the variables are subject to lower-and-upper-bound constraints. We demonstrate the special monotone behavior of the iterate and gradient vectors. The result on the gradient vector is new. It leads us to consider a simple updating procedure which preserves the monotonicity of both vectors. The procedures uses the fact that an M-matrix has a nonnegative inverse. Two new algorithms are then constructed by incorporating this updating procedure into the two given algorithms. We give numerical examples which show that the new methods can be more efficient than the original ones.     

On the first and second order derivatives of the Perron vector

In a previous work [5] the authors developed formulas for the second order partial derivatives of the Perron root as a function of the matrix entries at an essentially nonnegative and irreducible matrix. These formulas, which involve the group generalized inverse of an associated M-matrix, were used to investigate the concavity and convexity of the Perron root as a function of the entries. The authors now combine the above results together with an approach taken in an earlier joint paper [6] of the second author with L. Elsner and C. Johnson, and they develop formulas for the second order derivatives of an appropriately normalized Perron vector with respect to the matrix entries, which again are given in terms the group generalized inverse of an associated M-matrix. Convexity properties of the Perron vector as a function of the entries of the matrix are then examined. In addition, formulas for the first derivative of the Perron vector resulting from different normalizations of this eigenvector are also given. A by-product of one of these formulas yields that the group generalized inverse of a singular and irreducible M-matrix can be diagonally scaled to a matrix which is entrywise column diagonally dominant.     

A comparison of asymptotic analytical formulae with finite-difference approximations for pricing zero coupon bond

In this paper we solve numerically a degenerate parabolic equation with dynamical boundary condition for pricing zero coupon bond and compare numerical solution with asymptotic analytical solution. First, we discuss an approximate analytical solution of the model and its order of accuracy. Then, starting from the divergent form of the equation we implement the finite-volume method of Song Wang (IMA J Numer Anal 24:699–720, 2004) to discretize the differential problem. We show that the system matrix of the discretization scheme is a M-matrix, so that the discretization is monotone. This provides the non-negativity of the price with respect to time if the initial distribution is nonnegative. Numerical experiments demonstrate second order of convergence for difference scheme when the node is not too close to the point of degeneration.     

Two class of synchronous matrix multisplitting schemes for solving linear complementarity problems

Many problems in the areas of scientific computing and engineering applications can lead to the solution of the linear complementarity problem LCP (M,q). It is well known that the matrix multisplitting methods have been found very useful for solving LCP (M,q). In this article, by applying the generalized accelerated overrelaxation (GAOR) and the symmetric successive overrelaxation (SSOR) techniques, we introduce two class of synchronous matrix multisplitting methods to solve LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Also the monotone convergence of the new methods is established. Finally, the numerical results show that the introduced methods are effective for solving the large and sparse linear complementary problems.     

Classes of general H-matrices

Let M(A) denote the comparison matrix of a square H-matrix A, that is, M(A) is an M-matrix. H-matrices such that their comparison matrices are nonsingular are well studied in the literature. In this paper, we study characterizations of H-matrices with either singular or nonsingular comparison matrices. The spectral radius of the Jacobi matrix of M(A) and the generalized diagonal dominance property are used in the characterizations. Finally, a classification of the set of general H-matrices is obtained.     

Convergence of SSOR methods for linear complementarity problems

In this paper, by applying the SSOR splitting, we propose two new iterative methods for solving the linear complementarity problem LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Finally, two numerical examples are given to show the efficiency of the presented methods.     

On the inverse mean first passage matrix problem and the inverse M-matrix problem

The inverse mean first passage time problem is given a positive matrix M∈R^n,n, then when does there exist an n-state discrete-time homogeneous ergodic Markov chain C, whose mean first passage matrix is M? The inverse M-matrix problem is given a nonnegative matrix A, then when is A an inverse of an M-matrix. The main thrust of this paper is to show that the existence of a solution to one of the problems can be characterized by the existence of a solution to the other. In so doing we extend earlier results of Tetali and Fiedler.     

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.     

Theorems on M-splittings of a singular M-matrix which depend on graph structure

Let $\text{A=M?Nε}\text{R}{}^{\mathrm{n\; n}}$ be a splitting. We investigate the spectral properties of the iteration matrix M^-1N by considering the relationships of the graphs of A, M, N, and M^-1N. We call a splitting an M-splitting if M is a nonsingular M-matrix and N?0. For an M-splitting of an irreducible Z-matrix A we prove that the circuit index of M^-1N is the greatest common divisor of certain sets of integers associated with the circuits of A. For M-splittings of a reducible singular M-matrix we show that the spectral radius of the iteration matrix is 1 and that its multiplicity and index are independent of the splitting. These results hold under somewhat weaker assumptions.