SOR-based alternately linearized implicit iteration method for nonsymmetric algebraic Riccati equations

1.   Introduction

A nonsymmetric algebraic Riccati equation (NARE) is the matrix equation

for which $A$, $B$, $C$ and $D$ are known matrices whose sizes are $m\times m$, $m\times n$, $n\times m$ and $n\times n$ respectively, and $X \in \mathbb{R}^{m\times n}$ is an unknown matrix to be solved. Let

where $K$ is a nonsingular or an irreducible singular $M$-matrix. This type of nonlinear matrix equation often appears in many fields of application. For instance, in Wiener-Hopf factorization of Markov chains ^[7,20] and stochastic processes^[2]. In addition, in transport theory, changes in the usual set of neutron transport equations ^[3,5,6,14] are formulated as

where $\varphi$ is the neutron flux, $\alpha$ $(0 \leq \alpha < 1)$ is an angular shift, and $c$ is the mean of the number of new particles produced by a collision, which is assumed to be conservative, that is $0 \leq c \leq 1$. Equation ($1.3$) is equivalent to Eq ($1.1$) by proper transformation. In ^[21], Peretz gave sufficient conditions for the existence of contractive solutions for the nonsymmetric algebraic Riccati equation and the sufficient conditions for the unique contractive solution. In ^[8], Guo introduced a new class of nonsymmetric algebraic Riccati equations, which was inspired by the study of linear quadratic differential games. In ^[4], Bai et al. established a class of alternately linearized implicit (ALI) iteration methods for computing the minimal nonnegative solution. In^[11], Guan considered the numerical solution and proposed a modified alternately linearized implicit iteration method (MALI) for computing the minimal nonnegative solution of $M$-matrix algebraic Riccati equations. Because of the importance, the nonsymmetric algebraic Riccati equation has attracted considerable attention from many scholars, and many methods have been studied to solve them in recent years^{[9,10,11,12,13,15,16,17,19]}.

In general, Eq ($1.1$) may have solutions, there may be no solutions, and there may be infinite solutions. In practical applications, we are interested in the minimum nonnegative solution of Eq ($1.1$). Mainly inspired by^[11], in this paper, we propose a class of successive over relaxation (SOR)-based alternately linearized implicit (SORALI) iteration method for computing the minimal nonnegative solution of nonsymmetric algebraic Riccati equations (NARE). It is proved that the matrix sequences generated by the developed iterative algorithm monotonically converge to a minimal nonnegative solution of NARE under appropriate conditions.

For convenience of description, we use the following notations and definitions throughout this paper. For any matrices $A, B \in\mathbb{R}^{m\times n}$ with $A = (a_{ij})$ and $B = (b_{ij})$, $A\leq B$ (or $A < B$) means $a_{ij}\leq b_{ij}$ (or $a_{ij} < b_{ij}$), $\forall i, j$. Thus we can define $A$ is a positive matrix if $A > 0$, similarly we can define $A$ is a nonnegative matrix if $A\geq 0$. A matrix $A\in\mathbb{R}^{n\times n}$ is called a $Z$-matrix if $a_{ij}\leq 0$, $\forall i\neq j$. Obviously, for any $Z$-matrix $A$, it can be written as $A = sI-B$ with $B\geq 0$ and $I$ is the identity matrix. A $Z$-matrix $A = sI-B$ is a nonsingular $M$-matrix if $s > \rho(B)$ and singular $M$-matrix if $s = \rho(B)$, where $\rho(B)$ is the spectral radius of $B$. $\|\cdot\|_{\infty}$ denotes the $\infty$-norm of a matrix.

The remainder of this paper is organized as follows: In Section 2, we give some preliminary knowledge and some previous results. In Section 3, we propose a class of SORALI iteration method for computing the minimal nonnegative solution of NARE, and convergence analysis of this method. In Section 4, we report some numerical results. In Section 5, we conclude the result in this paper and the possible work in the future of this paper is highlighted.

2.   Preliminaries and previous results

In this section, we restate some preliminary knowledge and some previous results. The theory of nonsingular $M$-matrices will play an important role in our analysis, so several important properties of nonsingular $M$-matrices are described in the following lemmas.

Lemma 2.1. (^[1]) Let $A\in\mathbb{R}^{n\times n}$ be a $Z$-matrix, then the following expressions are equivalent:

$(1)$ $A$ is a nonsingular $M$-matrix.

$(2)$ $A^{-1}\geq0$.

$(3)$ $Av > 0$ for some positive vector $v\in\mathbb{R}^{n}$.

$(4)$ All eigenvalues of $A$ have positive real part.

Lemma 2.2. (^[18]) Let $A\in\mathbb{R}^{n\times n}$ be a nonsingular $M$-matrix. If a $Z$-matrix $B\in\mathbb{R}^{n\times n}$ satisfies $B \geq A$, then $B$ is also a nonsingular $M$-matrix.

Remark 2.1. From Lemma $2.2$, we can easily conclude that for any real number $\gamma\geq0$, $B = \gamma I+A$ is a nonsingular $M$-matrix.

Lemma 2.3. (^[1]) Let $A\in\mathbb{R}^{n\times n}$ be a nonsingular $M$-matrix, then any principal sub-matrix of A is also a nonsingular M-matrix.

Remark 2.2. (^[11]) From Lemma $2.3$, we can know that if A is a nonsingular M-matrix and is partitioned as

where $A_{11}$ and $A_{22}$ are square matrices, then $A_{11}$ and $A_{22}$ are also nonsingular M-matrices.

Lemma 2.4. (^[4,9,11,15]) If $K$ in $(1.2)$ is a nonsingular $M$-matrix or an irreducible singular $M$-matrix, then Eq $(1.1)$ has a unique minimal nonnegative solution $S$. If $K$ is nonsingular, then $A$-$SC$ and $D$-$CS$ are also nonsingular $M$-matrices. If $K$ is irreducible, then $S > 0$ and $A$-$SC$ and $D$-$CS$ are also irreducible $M$-matrices.

Many methods for finding the minimal nonnegative solution of NARE have been studied, such as Newton iteration, fixed-point iteration, structure-preserving doubling algorithm, nonlinear block Gauss-Seidel iterative, ALI iteration, MALI iterative and so on ^{[4,7,11,12,13,15]}.

In^[11], the modified alternately linearized implicit iteration (MALI) can be written as follows:

In the above formula, $D = L_D-U_D$, where $L_D$ is the lower triangular part of $D$ and $U_D$ is the strictly upper triangular part of $D$. Similarly, $A = L_A-U_A$, where $L_A$ is the lower triangular part of $A$ and $U_A$ is the strictly upper triangular part of $A$. $\alpha > 0$ and $\beta > 0$ are two known parameters, set $X_0 = 0\in\mathbb{R}^{m\times n}$, computing $X_{k+1}$ from $X_k$ by solving Eq ($2.1$), $k = 0, 1, \cdot\cdot\cdot$, until $\{X_k\}$ converges.

Because of the special structure of coefficient matrices in Eq ($2.1$), the method of MALI costs less CPU time than ALI for solving NARE.

3.   SORALI iteration and convergence analysis of SORALI iteration

Considering the special structure of the coefficient matrices and motivated by ^[11], we use the idea of the SOR iteration to split the matrices A and D respectively. Let

where $D_A$ is the main diagonal part of $A$, $-L_A$ is the strictly lower triangular part of $A$, $-U_A$ is the strictly upper triangular part of $A$, and $\omega$ is the relaxation factor. Similarly, let

where $D_D$ is the main diagonal part of $D$, $-L_D$ is the strictly lower triangular part of $D$, $-U_D$ is the strictly upper triangular part of $D$ and $\omega$ is the relaxation factor. $\omega$ makes the diagonal entries of the matrices $D_A$ and $D_D$ inverted more dominant and thus the related matrices to be inverted have a smaller condition number, leading to more accurate inverses and eventually to a more accurate solution and to a better convergence rate.

Then, we propose the method of SORALI iteration as follows:

where $\alpha, \beta$ are two given positive parameters. Obviously, if $\omega = 1$, $(3.1)$ will be reduced to ($2.1$).

Next, we discuss the convergence of the SORALI iteration. As preparation, we first show several lemmas about the SORALI iteration method.

Lemma 3.1. Let S be the minimal nonnegative solution of the NARE $(1.1)$ and sequence $\{X_k\}$ be generated by the method of the SORALI iteration. Then the following equalities hold for any integer $k\geq 0$:

Proof. We only need to prove (1)–(3), because (4)–(6) can be derived similarly.

We first verify $(1)$. As a matter of fact,

Similar to the first equation in ($3.1$), we have

Thus

$(2)$ Directly calculates the equation to the left

Substituting the first equation of ($3.1$) into the above equation, we get

$(3)$ Subtracts $X_{k+\frac {1}{2}}(\frac {1-\omega}{\omega}D_D+U_D)$ from both sides of the first equation of ($3.1$), we obtain

that is

Thus,

Similarly, we can get (4)–(6). □

Lemma 3.2. Assume that S is the minimal nonnegative solution of the NARE $(1.1)$, $K$ in $(1.2)$ is a nonsingular M-matrix and the matrix sequence $\{X_k\}$ is generated by the method of SORALI iteration. Let $\alpha, \beta$ and $\omega$ be the prescribed parameters of $(3.1)$ such that

where $a_{ii}$ and $d_{ii}$ are the $i$th diagonal elements of the matrices A and D, respectively. Then the following inequalities hold for any integer $k\geq 0$:

Proof. Because $K$ is a nonsingular $M$-matrix, $A$ and $D$ are also nonsingular $M$-matrices by Remark 2.2 and $B$ and $C$ are nonnegative matrices by the definition of $M$-matrix. Therefore, it is known from the splitting of $A$ and $D$ that $\frac {1}{\omega} D_D-L_D$ and $\frac {1}{\omega} D_A-L_A$ are both nonsingular $M$-matrices. We have $\alpha I+\frac {1}{\omega} D_D-L_D$ and $\beta I+\frac {1}{\omega} D_A-L_A$ are both nonsingular $M$-matrices by Remark 2.1, and

by Lemma 2.1.

Next, we prove the conclusion (3.2) according to the mathematical induction principle. When $k = 0$, we get

by Eq (3.1), so

On the other hand, from Lemma 3.1 (1), we obtain

thus

that is

Analogously, from Eq (3.1), we have

thus

From Lemma 3.1 (4), we obtain

From (3.4), we get

that is

So we have shown that

Assume that (3.2) holds for $k = l-1$, that is to say

From Eq (3.1), when $k = l$, we obtain

then

In addition, from Lemma 3.1 (1), we get

then by (3.8)

that is

Analogously, from Eq (3.1), we have

then

In addition, from Lemma 3.1 (4), we obtain

thus

that is

In summary, (3.2) holds for $k = l$. Thus, the proof is completed. □

Lemma 3.3. Suppose that the assumption is as in Lemma $3.2$, and $X_0 = 0$ is the initial matrix such that $\mathcal{R}(X_0)\geq 0$. Then for any integer $k\geq 0$, it holds that

Proof. We prove the Lemma $3.3$ by the mathematical induction principle. In fact, for $k = 0$, $0 = X_0\leq X_{\frac {1}{2}}$ by (3.2). According to Lemma 3.1 (3), we get

By making use of Lemma 3.1 (5), we get

then

that is

From Lemma 3.1 (6), we obtain

by (3.15). Therefore, we we have shown that

Assume that (3.13) holds for $k = l-1$, that is to say

By making use of Lemma 3.1 (2), we get

thus

that is

From Lemma 3.1 (3), we obtain

by (3.19). By Lemma 3.1 (5), we get

thus

that is

From Lemma 3.1 (6), we obtain

In summary, (3.13) holds for $k = l$. Thus, the proof is completed. □

The convergence property of the SORALI can be given by Lemmas 3.2 and 3.3. We show this result by the following theorem.

Theorem 3.1. Let $K$ defined in $(1.2)$ be an $M$-matrix. For the SORALI $(3.1)$, if the parameters are chosen as

then the sequence $\{X_k\}$ generated by the SORALI $(3.1)$ is well defined, monotonically increasing and converges to the unique minimum nonnegative solution S of NARE $(1.1)$.

Proof. According to Lemmas 3.2 and 3.3, we know that $X_k\geq 0$ and is monotonically increasing with upper bound. Suppose there is an $S_*$ that satisfies $\lim_{k\rightarrow \infty} = S_*$. By making use of Lemma 3.2, we obtain $S_*\leq S$. In addition, taking the limit in the SORALI (3.1), we have $S_*$ is a solution of NARE (1.1). Because $S$ is the minimum nonnegative solution of NARE (1.1), we get $S\leq S_*$. Thus $S = S_*$, the proof is completed. □

Remark 3.1. Theorem $3.1$ is only proved theoretically so that the SORALI $(3.1)$ is convergent under $0 < \omega\leq 1$. In fact, it might still be convergent even if $\omega$ is out of $(0, 1]$. Therefore, further research is needed in the selection of the parameter $\omega$. Unfortunately, we did not give an answer in this paper. This will be our future work.

4.   Numerical experiments

In this section, two examples are given to show the effectiveness of the SORALI (3.1). All the experiments are implemented under MATLAB R2016a running on a personal computer with an Intel Core i5 CPU (3.30 GHz) and 4 GB RAM. The numerical behaviours of the SORALI will be compared with the MALI in ^[11] with respect to the number of iterations (IT), CPU time and the relative residue (RES, see^[11]) which is defined to be

The iteration termination condition is $RES < 10^{-12}$ or the number of iterations exceeds $2000$. In both experiments, we all choose $\alpha = max\{a_{ii}\}$, $\beta = max\{d_{ii}\}$ and $\omega = 0.25, 0.5, 0.75, 1, 1.25, 1.5, 1.75, 2,$ respectively to observe the experimental results.

Example 4.1. (^[4]) Considering the SORALI (3.1), for which

are block tridiagonal matrices,

is a tridiagonal matrix, and

such that

is the minimal nonnegative solution of the SORALI (3.1). Here,

and $n = m^2$. For $m = 8$, $m = 10$, $m = 15$ and $m = 30$, the numerical results are listed in Tables 1–9.

Example 4.2. (^[11]) Considering the SORALI (3.1), for which $A$, $B$, $C$ and $D$ are generated by the following rules. Set $R = rand(2n, 2n)$, then set $W = diag(Re)-R$, where $e = (1, 1, \cdot\cdot\cdot, 1)^{T}\in\mathcal{R}^{2n}$; and finally, define

where $I$ is the identity matrix of size $n$. The matrices $A, B, C$ and $D$ generated by the above rules guarantee that $K$ in (1.2) is a nonsingular $M$-matrix. For $n = 50$, $n = 100$, $n = 500$ and $n = 1000$, the numerical results are listed in Tables 10–18.

From the above two numerical examples, we can see that when the size of the matrices become larger, the SORALI has a slight advantage over the MALI in terms of iteration number and CPU time.

5.   Conclusions

In this paper, we propose a class of SORALI iteration method for computing the minimal nonnegative solution of NARE, and have proved the convergence of the method. Finally, two numerical examples illustrate the effectiveness of the proposed method. We hope to continue to study the better range of the parameter $\omega$ in theory in the future.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research is supported by Scientific Research Staring Foundation of Fujian University of Technology (No. GY-Z220203).

Conflict of interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.