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

Abstract

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.