remarkRemark exampleExample hypothesisHypothesis claimClaim An Efficient
Iteration for Extremal Solutions of DAREC.-Y. Chiang and H.-Y. Fan

# An efficient iteration for the extremal solutions of discrete-time algebraic
Riccati equations

Chun-Yueh Chiang Center for General Education, National Formosa University,
Huwei 632, Taiwan, R.O.C<EMAIL_ADDRESS>Hung-Yuan Fan Department of
Mathematics, National Taiwan Normal University, Taipei 116325, Taiwan, R.O.C.
<EMAIL_ADDRESS>
###### Abstract

Algebraic Riccati equations (AREs) have been extensively applicable in linear
optimal control problems and many efficient numerical methods were developed.
The most attention of numerical solutions is the (almost) stabilizing solution
in the past works. Nevertheless, it is an interesting and challenging issue in
finding the extremal solutions of AREs which play a vital role in the
applications. In this paper, based on the semigroup property, an accelerated
fixed-point iteration (AFPI) is developed for solving the extremal solutions
of the discrete-time algebraic Riccati equation. In addition, we prove that
the convergence of the AFPI is at least R-suplinear with order $r>1$ under
some mild assumptions. Numerical examples are shown to illustrate the
feasibility and efficiency of the proposed algorithm.

###### keywords:

discrete-time algebraic Riccati equation, extremal solution, stabilizing
solution, antistabilizing solution, accelerated fixed-point iteration,
semigroup property

39B12, 39B42, 65H05, 15A24

##  1 Introduction

In this paper we are mainly concerned with the extremal solutions of the
discrete-time algebraic Riccati equation (DARE)

(1a) $\displaystyle X=A^{H}XA-A^{H}XB(R+B^{H}XB)^{-1}B^{H}XA+C^{H}C,$ or its
equivalent expression (1b) $\displaystyle X=A^{H}X(I+GX)^{-1}A+H,$

where $A\in\mathbb{C}^{n\times n}$, $B\in\mathbb{C}^{n\times m}$,
$R\in\mathbb{C}^{m\times m}$ is positive definite, $C\in\mathbb{C}^{l\times
n}$ with $m,l\leq n$, $I$ is the identity matrix of compatible size,
$G:=BR^{-1}B^{H}$ and $H=C^{H}C$, respectively, and the $n$-square matrix $X$
is the unknown Hermitian matrix that is to be determined. For the sake of
simplicity, the matrix operator
$\mathcal{R}:\mbox{dom}(\mathcal{R})\rightarrow\mathbb{H}_{n}$ is defined by
$\mathcal{R}(X):=A^{H}X(I+GX)^{-1}A+H$ , which is used to rewrite the equation
Eq. 1b into the compact expression $X=\mathcal{R}(X)$, where $\mathbb{H}_{n}$
is the set of all $n\times n$ Hermitian matrices and
$\mbox{dom}(\mathcal{R}):=\\{X\in\mathbb{H}_{n}\,|\,\det(R+B^{H}XB)\neq 0\\}$.
The following sets

$\displaystyle\mathcal{R}_{=}:=\\{X\in\mbox{dom}(\mathcal{R})\,|\,X=\mathcal{R}(X)\\},\quad\mathcal{R}_{\geq}:=\\{X\in\mbox{dom}(\mathcal{R})\,|\,X\geq\mathcal{R}(X)\\},$

will play an important role in our main results given below.

The nonlinear matrix equation of the form Eq. 1a arises from the linear-
quadratic (LQ) optimal control problem that minimizes the cost functional

$\mathcal{J}(u):=\sum_{k=0}^{\infty}(y_{k}^{H}y_{k}+u_{k}^{H}Ru_{k})$

subject to the linear discrete-time system

$x_{k+1}=Ax_{k}+Bu_{k},\quad y_{k}=Cx_{k},\quad k\geq 0,$

where $x_{k}\in\mathbb{C}^{n}$ is the state variable, $u_{k}\in\mathbb{C}^{m}$
is the control variable and $y_{k}$ is the output variable, respectively.  Let
$F_{X}=(R+B^{H}XB)^{-1}B^{H}XA$ and $T_{X}=A-BF_{X}$ for any Hermitian
solution $X$ of Eq. 1. Note that $T_{X}\equiv(I+GX)^{-1}A$. If $(A,B)$ is
stabilizable and $(A,C)$ is detectable,  it is well-known that there exists an
optimal state feedback control

$u_{k}^{*}:=-F_{X_{\rm s}}x_{k},\quad k\geq 0$

such that the cost functional $\mathcal{J}(u_{k}^{*})=x_{0}^{H}{X_{\rm
s}}x_{0}$ is minimized and the corresponding closed-loop system

$x_{k+1}:=T_{X_{\rm s}}x_{k},\quad k\geq 0$

is asymptotically stable, i.e., all eigenvalues of the close-loop matrix
$T_{X_{\rm s}}$ are inside the open unit disk $\mathbb{D}$ in the complex
plane, where ${X_{\rm s}}\geq 0$ is the unique stabilizing solution of the
DARE Eq. 1a, see, e.g., [1, 13]. Here, we denote $M\geq 0$ (resp. $M>0$) if
$M\in\mathbb{C}^{n\times n}$ is a Hermitian positive semidefinite (resp.
positive definite) matrix. Analogously, we denote $M\leq 0$ (resp. $M<0$) if
$M$ is a Hermitian negative semidefinite (resp. negative definite) matrix. A
matrix operator $f:\mathbb{H}_{n}\rightarrow\mathbb{H}_{n}$ is order
preserving (resp. reversing) on $\mathbb{H}_{n}$ if $f(A)\geq f(B)$ (resp.
$f(A)\leq f(B)$) when $A\geq B$ and $A,B\in\mathbb{H}_{n}$. It is proved that
the operator $\mathcal{R}(\cdot)$ is order preserving. Throughout the paper
the set of all $n\times n$ Hermitian positive semidefinite (resp. negative
semidefinite) matrices is denoted by $\mathbb{N}_{n}$ (resp.
$-\mathbb{N}_{n}$). For any $M,N\in\mathbb{H}_{n}$, we write $M\geq N$ (resp.
$M\leq N$) if $M-N\geq 0$ (resp. $M-N\leq 0$). Moreover, $\sigma(M)$ and
$\rho(M)$ are the spectrum and the spectral radius of the square matrix $M$,
respectively, and define the quantities

$\mu(M):=\min\\{|\lambda|\ |\
\lambda\in\sigma(M)\\},\quad\rho_{\mathbb{D}}(M):=\max\\{|\lambda|\ |\
\lambda\in\sigma(M)\cap\mathbb{D}\\},$

which will be used below. We also denote the closed unit disk by
$\bar{\mathbb{D}}$, the boundary of $\mathbb{D}$ by $\partial\mathbb{D}$, the
region outside the open unit disk by $\mathbb{D}^{c}$, and the spectral or
Euclidean norm for matrices and vectors in the context by $\|\cdot\|$ ,
respectively.

If $(A,B)$ is stabilizable and $(A,C)$ is detectable, which are standard
assumptions in the LQ optimal control problem mentioned previously, then
$\mathcal{R}_{\geq}\cap\mathbb{N}_{n}=\\{X_{\rm s}\\}$. In this case, there
are dozens of numerical methods for solving the DAREs with small to medium
sizes in the literature, see, e.g., [5, 7, 11, 14, 15, 20, 21] and the
references therein. The standard way for computing the stabilizing solution is
to utilize the Schur method [7, 15], which solves the stable deflating
subspace $\mathcal{V}=\mathrm{span}\big{(}\begin{bmatrix}X_{1}\\\
X_{2}\end{bmatrix}\big{)}$ of the associated symplectic pencil

$M-\lambda L:=\begin{bmatrix}A&0\\\
-H&I\end{bmatrix}-\lambda\begin{bmatrix}I&G\\\ 0&A^{H}\end{bmatrix}$

using the ordered QZ algorithm, and thus $X=X_{2}X_{1}^{-1}\geq 0$ is the
unique stabilizing solution of the DARE Eq. 1b.

On the other hand, regarding the DARE Eq. 1a or Eq. 1b as a nonlinear matrix
equation, it is natural to apply Newton’s method for finding the unique
stabilizing solution $X_{\rm s}$ under the stabilizability and detectability
conditions, see, e.g., [14, 18]. Moreover, since $H=C^{H}C\geq 0$, it follows
from Theorem 1.1 of [8] that $X_{\rm s}$ is also the maximal solution to the
DARE Eq. 1b satisfying $X_{\rm s}\geq S$ for all $S\in\mathcal{R}_{=}$, see
also [14, Theorem 13.1.1]. In addition, stating with some initial
$X_{0}\in\mathbb{H}_{n}$, the author proposed the theoretical
characterizations for the linearly convergent behavior of Newton’s method when
solving the DARE Eq. 1b with all unimodular eigenvalues of $T_{X}$ being
semisimple. Inspired by the doubling algorithm [2, 11], starting from the
coefficient matrices $A$, $G$ and $H$, Chu et. al. proposed structure-
preserving doubling algorithms (SDAs) [5] for solving the DARE Eq. 1b and
periodic DAREs, respectively. When the control weighting matrix
$R\in\mathbb{H}_{n}$ is singular, we developed a variant of the structured
doubling algorithm for computing the stabilizing solution to the DARE Eq. 1a,
please refer to [4].

It is well known that the set $\mathcal{R}_{\geq}\cap\mathbb{N}_{n}$
associated with the DARE Eq. 1b, equipped with the partial ordering “$\geq$”,
forms a complete lattice if $(A,B)$ is stabilizable and $(A,C)$ is not
detectable, see, e.g., [12, 22]. Under the same assumptions the DARE Eq. 1b
might have the almost stabilizing solution $X_{s}\geq 0$ with
$\rho(T_{X_{s}})\leq 1$, which is the maximal element of the solution set
$\mathcal{R}_{=}$, and the optimizing solution $Y\geq 0$ with the cost
functional $\mathcal{J}(u_{k}^{*})=x_{0}^{H}Yx_{0}$ being minimized, which is
the minimal element of the solution set
$\mathcal{R}_{\geq}\cap\mathbb{N}_{n}$. On the other hand, it follows from
[10, 23] that the DARE Eq. 1b has a unique almost antistabilizing solution
$\widehat{X}\in-\mathbb{N}_{n}$ with $\mu(T_{\widehat{X}})\geq 1$, which is
the minimal element of the solution set $\mathcal{R}_{=}$ satisfying
$\widehat{X}\leq S$ for all $S\in\mathcal{R}_{=}$, if $A$ is nonsingular and
$\mathrm{rank}\left[A-\lambda I,B\right]=n$ for all
$\lambda\in\bar{\mathbb{D}}\backslash\\{0\\}$. Under the same assumptions, it
is shown in Theorem 3.1 of [24] that $\widehat{Y}=-\widetilde{Y}$ is the
maximal element of the solution set $\mathcal{R}_{=}\cap-\mathbb{N}_{n}$ if
and only if $\widetilde{Y}$ is the minimal positive semidefinite solution to
the dual DARE of first kind

(2)
${X}=\widetilde{A}^{H}\widetilde{X}\widetilde{A}-(\widetilde{C}^{H}+\widetilde{A}^{H}{X}\widetilde{B})(\widetilde{R}+\widetilde{B}^{H}{X}\widetilde{B})^{-1}(\widetilde{C}+\widetilde{B}^{H}{X}\widetilde{A})+\widetilde{H},$

where the coefficient matrices are geiven by

(3)
$\widetilde{A}=A^{-1},\quad\widetilde{B}=A^{-1}B,\quad\widetilde{H}=(A^{-1})^{H}HA^{-1},\quad\widetilde{C}=B^{H}\widetilde{H},\quad\widetilde{R}=R+\widetilde{C}B,$

respectively. The Riccati equation Eq. 2 is also called the reverse discrete-
time algebraic Riccati equation presented in [9], and a numerically stable
algorithm was proposed in [19] for computing the minimal and antistabilizing
solution $\widehat{X}\in-\mathbb{N}_{n}$ to the DARE Eq. 1a with nonsingular
$A$.

Recently, it is shown in Theorem 5.1 of [24] that the existence and uniqueness
of the minimal solution to the DARE Eq. 1a can be constructed iteratively,
through a Newton-type iteration for computing the maximal solution to the dual
DARE Eq. 2, when $\mathrm{rank}\left[A-\lambda I,B\right]=n$ for all
$\lambda\in\bar{\mathbb{D}}\backslash\\{0\\}$ and $A$ is nonsingular. In this
paper, applying the methodology of the fixed-point iteration (FPI), we we will
give constructive proofs for the existence (or uniqueness) theorems of these
four extremal solutions to the DARE under some wild and reasonable
assumptions. More restrictive assumptions have been addressed in [6] for the
uniqueness of the maximal solution to the DARE Eq. 1bunder the framework of
the FPI. Starting with some appropriate initial matrices, we will develop the
accelerated fixed-point iteration (AFPI), based on the semigroup property of
the DARE with an integer parameter $r\geq 2$ [17], for computing the extermal
elements $(X,Y)$ of the set $\mathcal{R}_{\geq}\cap\mathbb{N}_{n}$
simultaneously. Specifically, the AFPI with the initial $X_{0}=0$ is just the
SDA presented in [5] when $r=2$. In analogous way, a variant of the AFPI will
be derived from the dual DARE Eq. 2 for solving the extremal elements
$(\widehat{X},\widehat{Y})$ of the set $\mathcal{R}_{=}\cap-\mathbb{N}_{n}$
simultaneously, if $(A,B)$ is antistabilizable and $A$ is nonsingular.

The paper is organized as follows. In Section 2 we present some preliminary
lemmas that will be used in our main theorems. Under some wild assumptions,
the existence (or uniqueness) of the extremal solutions to the DARE will be
constructed iteratively via the standard FPI in Section 3. Moreover, based on
the framework of the semigroup property for the DARE Eq. 1b, two accelerated
variants of the FPI will be proposed for computing the extremal elements of
$\mathcal{R}_{=}\cap\mathbb{N}$ and $\mathcal{R}_{=}\cap-\mathbb{N}_{n}$,
respectively, and will discuss the rate of convergence for the AFPI presented
in this section. In Section 4 some illustrate examples are presented for
demonstrating the feasibility and efficiency of the proposed AFPI($r$) with
different values of $r$. Finally, we conclude this paper in Section 5.

##  2 Preliminaries

In this section we introduce some definitions and auxiliary results that will
be used below. Firstly, the concepts of R-linear and R-superlinear convergence
of a sequence will be used in the following sections, see, e.g., Definition
1.1 of [17].

######  Definition 2.1.

Let $\\{X_{k}\\}_{k=0}^{\infty}$ be a sequence of $n\times n$ complex matrices
and $\|\cdot\|$ be an induced matrix norm.

  1. (a)

$\\{X_{k}\\}_{k=0}^{\infty}$ converges at least R-linearly to
$X_{*}\in\mathbb{C}^{n\times n}$, if there exists a scalar $\sigma\in(0,1)$
such that

$\limsup_{k\rightarrow\infty}\sqrt[k]{\|X_{k}-X_{*}\|}\leq\sigma.$

  2. (b)

$\\{X_{k}\\}_{k=0}^{\infty}$ converges at least R-superlinearly to
$X_{*}\in\mathbb{C}^{n\times n}$ with order $r>1$, if there exists a scalar
$\sigma\in(0,1)$ such that

$\limsup_{k\rightarrow\infty}\sqrt[r^{k}]{\|X_{k}-X_{*}\|}\leq\sigma.$

Let the Stein operator
$\mathcal{S}_{A}:\mathbb{H}_{n}\rightarrow\mathbb{H}_{n}$ associated with a
matrix $A\in\mathbb{C}^{n\times n}$ be defined by

(4) $\displaystyle\mathcal{S}_{A}(X):=X-A^{H}XA,$

for all $X\in\mathbb{H}_{n}$. In general, the operator $\mathcal{S}_{A}$ is
neither order-preserving nor order-reversing. However, under the assumption
that $\rho(A)<1$, the inverse operator $\mathcal{S}^{-1}_{A}$ exists and it is
order-preserving, since
$\mathcal{S}_{A}^{-1}(X)=\sum\limits_{k=0}^{\infty}(A^{k})^{H}XA^{k}\geq\sum\limits_{k=0}^{\infty}(A^{k})^{H}YA^{k}=\mathcal{S}_{A}^{-1}(Y)$
for all $X\geq Y$. For the sake of clarity the results in this section can be
separated into three major parts.

###  2.1 Some useful identities

The following lemma provides some identities with respect to the Stein matrix
operator defined by Eq. 4, which will play an important role in our main
results below.

######  Lemma 2.2.

Let $X,\widehat{X}\in\mbox{dom}(\mathcal{R})$. The following identities hold,
which state the relationship between DARE and a specific Stein matrix
equation:

  1. (i)

If $A_{F}:=A-BF$ for any $F\in\mathbb{C}^{m\times n}$ and $H_{F}:=H+F^{H}RF$,
then

(5a) $\displaystyle X-\mathcal{R}(X)$
$\displaystyle=\mathcal{S}_{A_{F}}(X)-H_{F}+K_{F}(X),$

where $K_{F}(X):=(F-F_{X})^{H}(R+B^{H}XB)(F-F_{X})$.

  2. (ii)

If $K(\widehat{X},X):=K_{F_{\widehat{X}}}(X)$ and
$H_{\widehat{X}}:=H+F_{\widehat{X}}^{H}RF_{\widehat{X}}$, then (5a) can be
rewritten as

(5b) $\displaystyle X-\mathcal{R}(X)$
$\displaystyle=\mathcal{S}_{T_{\widehat{X}}}(X)-H_{\widehat{X}}+K(\widehat{X},X).$

Furthermore, we also have

(5c) $\displaystyle
X-\mathcal{R}(X)=\mathcal{S}_{T_{\widehat{X}}}(X)-H+\left[K(\widehat{X},X)-K(\widehat{X},0)\right].$

  3. (iii)

If $U_{\widehat{X}}:=\widehat{X}T_{\widehat{X}}$, then
$B^{H}U_{\widehat{X}}=RF_{\widehat{X}}$,
$H_{\widehat{X}}=H+U_{\widehat{X}}^{H}GU_{\widehat{X}}$ and thus (5b) can be
rewritten as

(5d) $\displaystyle X-\mathcal{R}(X)$
$\displaystyle=\mathcal{S}_{T_{\widehat{X}}}(X)-H_{\widehat{X}}+(U_{\widehat{X}}-U_{X})^{H}(G+GXG)(U_{\widehat{X}}-U_{X}).$

######  Proof 2.3.

  1. (i)

Observe that

$X-\mathcal{R}(X)=\Gamma_{1}(X)+\Gamma_{2}(X),$

where $\Gamma_{1}(X):=\mathcal{S}_{A}(X)-H$ and
$\Gamma_{2}(X):=A^{H}XB(R+B^{H}XB)^{-1}B^{H}XA$. A direct computation yields

$\displaystyle\Gamma_{2}(X)=F_{X}^{H}(R+B^{H}XB)F_{X}=K_{F}(X)+[F^{H}(R+B^{H}XB)F_{X}$
$\displaystyle+F_{X}^{H}(R+B^{H}XB)F]-F^{H}(R+B^{H}XB)F$
$\displaystyle=K_{F}(X)-F^{H}RF+[F^{H}B^{H}XA+A^{H}XBF-F^{H}B^{H}XBF]$
$\displaystyle=K_{F}(X)-F^{H}RF+\mathcal{S}_{A_{F}}(X)-\mathcal{S}_{A}(X).$

We conclude that

$\displaystyle X-\mathcal{R}(X)$
$\displaystyle=(\mathcal{S}_{A}(X)-H)+(K_{F}(X)-F^{H}RF+\mathcal{S}_{A_{F}}(X)-\mathcal{S}_{A}(X))$
$\displaystyle=\mathcal{S}_{A_{F}}(X)-H_{F}+K_{F}(X).$

  2. (ii)

The first result is clearly true from (5a). For the proof of the remaining
part, an easy computation shows that

$\displaystyle RF_{\widehat{X}}$
$\displaystyle=B^{H}\widehat{X}(I+BR^{-1}B^{H}\widehat{X})^{-1}A=B^{H}\widehat{X}T_{\widehat{X}},$
$\displaystyle F_{\widehat{X}}^{H}RF_{\widehat{X}}$
$\displaystyle=(RF_{\widehat{X}})^{H}R^{-1}(RF_{\widehat{X}})=(\widehat{X}T_{\widehat{X}})^{H}G(\widehat{X}T_{\widehat{X}}).$

We immediately obtain this formula due to
$K(\widehat{X},0)=F_{\widehat{X}}^{H}RF_{\widehat{X}}$.

  3. (iii)

A trivial verification shows that

$\displaystyle B^{H}U_{\widehat{X}}$
$\displaystyle=B^{H}\widehat{X}T_{\widehat{X}}=(R+B^{H}\widehat{X}B)^{-1}B^{H}\widehat{X}A=RF_{\widehat{X}},$
$\displaystyle H_{\widehat{X}}$
$\displaystyle=H+F_{\widehat{X}}^{H}RF_{\widehat{X}}=H+U_{\widehat{X}}^{H}BRB^{H}U_{\widehat{X}}=H+U_{\widehat{X}}^{H}GU_{\widehat{X}}.$

The result (5d) follows from (5b) immediately.

In addition, under different setting, Eq. (5c) can be reformulated as follows.

  1. 1.

If $X=\widehat{X}\in\mathbb{H}_{n}$, then

(6a)
$\mathcal{S}_{T_{\widehat{X}}}(\widehat{X})=\widehat{X}-\mathcal{R}(\widehat{X})+H+K(\widehat{X},0).$

  2. 2.

If $X\in\mathcal{R}_{=}$ and $\widehat{X}\in\mathbb{H}_{n}$, then

(6b)
$\mathcal{S}_{T_{\widehat{X}}}(X)=H+\left[K(\widehat{X},0)-K(\widehat{X},X)\right].$

  3. 3.

If $X=\widehat{X}\in\mathcal{R}_{=}$, then

(6c) $\mathcal{S}_{T_{X}}(X)=H+K(X,0).$

For any $X,\widehat{X}\in\mathbb{H}_{n}$, consider a subset of
$\mathbb{H}_{n}$ defined by

(7)
$\mathcal{S}_{=}:=\\{Y\in\mathbb{H}_{n}\,|\,\mathcal{S}_{T_{\widehat{X}}}(Y)=K(\widehat{X},X)\\}.$

Clearly, from (6a), the solution set $\mathcal{R}_{=}$ has the equivalent
expression given by

(8)
$\mathcal{R}_{=}=\\{Y\in\mathbb{H}_{n}\,|\,\mathcal{S}_{T_{Y}}(Y)=H+K(Y,0)\\}.$

The relationship between these two sets $\mathcal{R}_{=}$ and
$\mathcal{S}_{=}$ is characterized in the following lemma, which will be used
in the proof of Theorem 3.4 later on.

######  Lemma 2.4.

For $\mathcal{S}_{=}$ and $\mathcal{R}_{=}$ defined by (7)–(8), the following
statements hold:

  1. (i)

If $X,\widehat{X}\in\mathcal{R}_{=}$, then $\widehat{X}-X\in\mathcal{S}_{=}$.

  2. (ii)

If $X\in\mathcal{R}_{=}$ and $\widehat{X}-X\in\mathcal{S}_{=}$, then
$\widehat{X}\in\mathcal{R}_{=}$.

  3. (iii)

If $\widehat{X}\in\mathcal{R}_{=}$ and $\widehat{X}-X\in\mathcal{S}_{=}$, then
${X}\in\mathcal{R}_{=}$.

######  Proof 2.5.

With the aid of (6), the results are proven as follows.

  1. (i)

From (6b) and (6c) we obtain

$\displaystyle\mathcal{S}_{T_{\widehat{X}}}(\widehat{X}-X)$
$\displaystyle=\mathcal{S}_{T_{\widehat{X}}}(\widehat{X})-\mathcal{S}_{T_{\widehat{X}}}(X)$
$\displaystyle=H+K(\widehat{X},0)-\left[H+K(\widehat{X},0)-K(\widehat{X},X)\right]=K(\widehat{X},X).$

That is, $\widehat{X}-X\in\mathcal{S}_{=}$.

  2. (ii)

From (6b) we obtain

$\displaystyle\mathcal{S}_{T_{\widehat{X}}}(\widehat{X})$
$\displaystyle=\mathcal{S}_{T_{\widehat{X}}}(X)+K(\widehat{X},X)$
$\displaystyle=H+K(\widehat{X},0)-K(\widehat{X},X)+K(\widehat{X},X)=H+K(\widehat{X},0)).$

That is, $\widehat{X}\in\mathcal{R}_{=}$.

  3. (iii)

From (6c) and (5c) we obtain

$\displaystyle\mathcal{S}_{T_{\widehat{X}}}({X})$
$\displaystyle=\mathcal{S}_{T_{\widehat{X}}}(\widehat{X})-K(\widehat{X},X)$
$\displaystyle=H+K(\widehat{X},0)-K(\widehat{X},X)=\mathcal{S}_{T_{\widehat{X}}}({X})-\left[X-\mathcal{R}(X)\right].$

That is, $X=\mathcal{R}(X)$ or ${X}\in\mathcal{R}_{=}$.

###  2.2 Some useful facts and properties

For any $M\in\mathbb{C}^{n\times n}$, the generalized eigenspace of $M$
corresponding an eigenvalue $\lambda$ is defined by
$E_{\lambda}(M)=\mathrm{Ker}(M-\lambda I)^{n}$. The following lemma
characterizes the inheritance of (almost) stability property under the setting
of a Stein inequality.

######  Lemma 2.6.

Let $B\in\mathbb{C}^{n\times n}$ and $Q\geq 0$. If $X_{0}$ is a positive
semidefinite solution of the Stein inequality $\mathcal{S}_{B}(X)\geq Q$, and
$\mathrm{Ker}(Q)\subseteq\mathrm{Ker}(B-A)$ for some $A\in\mathbb{C}^{n\times
n}$, then $\rho(B)\leq\max\\{1,\rho(A)\\}$. Furthermore, we have

  1. (i)

$\rho(B)\leq 1$ if $\rho(A)\leq 1$.

  2. (ii)

$\rho(B)<1$ if $\rho(A)<1$ or $\mathrm{Ker}(Q)\cap E_{\lambda}(B)=\\{0\\}$ for
some $\lambda\in\sigma(B)$.

######  Proof 2.7.

Let $\lambda\in\sigma(B)$ and a nonzero vector $x\in E_{\lambda}(B)$. Then
$x^{H}\mathcal{S}_{B}(X_{0})x=(1-|\lambda|^{2})(x^{H}X_{0}x)\geq x^{H}Qx\geq
0$. If $x\not\in\mathrm{Ker}(Q)$, then $x\not\in\mathrm{Ker}(X_{0})$ and thus
$|\lambda|<1$. Otherwise, $x\in\mathrm{Ker}(Q)$ implies that
$Ax=Bx+(A-B)x=\lambda x$ and thus $|\lambda|\leq\rho(A)$. We complete the
proof.

According to the following theorem, the positive semidefiniteness of the
operator $K(\cdot,\cdot)$ defined by (5b) might depend on the positive
definiteness of the matrix $R+B^{H}XB$ for any $X\in\mathcal{R}_{\geq}$.

######  Theorem 2.8.

Let $X\in\mathcal{R}_{\geq}$. Then $R+B^{H}XB>0$ and $K(\widehat{X},X)\geq 0$
for any $\widehat{X}\in\mathbb{H}_{n}$.

######  Proof 2.9.

We first notice that $X\in\mathcal{R}_{\geq}$ is equivalent to $X\geq
H+T_{X}^{H}(X+XGX)T_{X}$. Let $R=\widehat{R}\widehat{R}^{H}$ for some
$\widehat{R}>0$, e.g., the Cholesky decomposition of $R$ , and
$\widehat{B}:=\widehat{R}^{-H}B$. Then $G=\widehat{B}\widehat{B}^{H}$ and a
direct computation yields

$\displaystyle\begin{bmatrix}R&-B^{H}XT_{X}\\\
-T_{X}^{H}XB^{H}&X-T_{X}^{H}XT_{X}\end{bmatrix}$
$\displaystyle\geq\begin{bmatrix}R&-B^{H}XT_{X}\\\
-T_{X}^{H}XB^{H}&T_{X}^{H}XGXT_{X}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\widehat{R}\\\
-T_{X}^{H}X\widehat{B}\end{bmatrix}\begin{bmatrix}\widehat{R}^{H}&-\widehat{B}^{H}XT_{X}\end{bmatrix}\geq
0.$

Therefore, we see that

(9) $\displaystyle\begin{bmatrix}R+B^{H}XB&0\\\ 0&X\end{bmatrix}$
$\displaystyle\geq\begin{bmatrix}B^{H}XB&B^{H}XT_{X}\\\
T_{X}^{H}XB&T_{X}^{H}XT_{X}\end{bmatrix}=U^{H}XU,$

where $U:=\begin{bmatrix}B&T_{X}\end{bmatrix}\in\mathbb{C}^{n\times(m+n)}$.
Next, we shall deduce that $R+B^{H}XB\geq 0$. If not, there is a nonzero
$x_{1}\in\mathbb{C}^{m}$ such that $x_{1}^{H}(R+B^{H}XB)x_{1}<0$. Choose a
scalar $\lambda\not\in\sigma(T_{X})$ with $|\lambda|=1$, and let
$x_{2}:=(\lambda I-T_{X})^{-1}Bx_{1}$ and $x:=\begin{bmatrix}x_{1}\\\
x_{2}\end{bmatrix}$, respectively. It is easily seen that $Ux=\lambda x_{2}$
and hence, from (9), we immediately obtain

$x_{1}^{H}(R+B^{H}XB)x_{1}+x_{2}^{H}Xx_{2}\geq|\lambda|^{2}(x_{2}^{H}Xx_{2})=x_{2}^{H}Xx_{2}.$

Then $x_{1}^{H}(R+B^{H}XB)x_{1}\geq 0$, contradicting to the assumption of
$x_{1}$. Thus, we conclude that $R+B^{H}XB\geq 0$ is nonsingular or
$R+B^{H}XB>0$ for any $X\in\mathcal{R}_{\geq}$. The remaining part immediately
follows from the definition of the operator $K(.,.)$ in Lemma 2.2.

######  Remark 2.10.

From Theorem 2.8, we see that $I+GX=I+BR^{-1}B^{H}X$ is nonsingular if
$X\in\mathcal{R}_{\geq}$ (since $I+R^{-1}B^{H}XB$ is nonsingular).

Based on the following lemma, the uniqueness of the almost stabilizing
solution to the DARE (1) will be established in Theorem 3.4 below.

######  Lemma 2.11.

Let $\rho(A)\leq 1$ and $Q_{1}\geq 0$. If $X_{0}\in\mathbb{H}_{n}$ is a
solution of the matrix inequality $\mathcal{S}_{A}(X)\geq(XA)^{H}Q_{1}(XA)$,
and the generalized eigenspaces of $A^{H}$ satisfy

(10) $\displaystyle E_{\bar{\lambda}}(A^{H})\cap\mathrm{Ker}(Q_{1})=\\{0\\}$

for all $\lambda\in\sigma(A)$ with $|\lambda|=1$, then $X_{0}\geq 0$.

######  Proof 2.12.

For the sake of convenience, we factorize $Q_{1}$ as the Cholesky
decomposition $Q_{1}=Q_{2}Q_{2}^{H}$. Note that
$\mathrm{Ker}(Q_{1})=\mathrm{Ker}(Q_{2}^{H})$. Let ${\lambda}\in\sigma(A)$
with $|\lambda|=1$ and $Av_{1}=\lambda v_{1}$ for some nonzero
$v_{1}\in\mathbb{C}^{n}$. Then we see that

$0=v_{1}^{H}\mathcal{S}_{A}(X_{0})v_{1}=(Q_{2}^{H}X_{0}v_{1})^{H}(Q_{2}^{H}X_{0}v_{1})=(v_{1}^{H}X_{0}Q_{2})(v_{1}^{H}X_{0}Q_{2})^{H},$

and this implies that

$0=v_{1}^{H}A^{H}X_{0}Q_{2}=\bar{\lambda}v_{1}^{H}X_{0}Q_{2},\quad
0=v_{1}^{H}\mathcal{S}_{A}(X_{0})=\bar{\lambda}v_{1}^{H}X_{0}(\lambda I-A).$

Thus, it follows from the assumption (10) that $X_{0}v_{1}=0$. Let $(A-\lambda
I)v_{2}=v_{1}$. Observe that the quadratic form
$v_{2}^{H}\mathcal{S}_{A}(X_{0})v_{2}$ again satisfies

$v_{2}^{H}(X_{0}-A^{H}X_{0}A)v_{2}=-(\lambda
v_{1}^{H}X_{0}v_{2}+\bar{\lambda}v_{2}^{H}X_{0}v_{1}+v_{1}^{H}X_{0}v_{1})=0,$

and we then have

$0=v_{2}^{H}AX_{0}Q_{2}=\bar{\lambda}v_{2}^{H}X_{0}Q_{2},\quad
0=v_{2}^{H}\mathcal{S}_{A}(X_{0})=\bar{\lambda}v_{2}^{H}X_{0}(\lambda I-A).$

Therefore, $X_{0}v_{2}=0$ by using the assumption (10). Inductively, we can
show that $X_{0}v_{j}=0$ for a Jordan chain $\\{v_{j}\\}$ corresponding to the
unimodular eigenvalue $\lambda$ of $A$.

Let $J_{A}=P^{-1}AP$ be the Jordan canonical form of $A$. Suppose that
$J_{A}=J_{1}\oplus J_{s}$, where $J_{1}\in\mathbb{C}^{m_{1}\times m_{1}}$ with
$\sigma(J_{1})\subseteq\partial\mathbb{D}$ and
$J_{s}\in\mathbb{C}^{m_{2}\times m_{2}}$ with
$\sigma(J_{s})\subseteq\mathbb{D}$. If we let
$Y_{0}:=\mathcal{S}_{A}({X}_{0})$, then
$Y_{0}\geq(X_{0}A)^{H}Q_{1}(X_{0}A)\geq 0$ and one deduces that

$\mathcal{S}_{A}(\widehat{X}_{0})=\widehat{X}_{0}-J_{A}^{H}\widehat{X}_{0}J_{A}=\widehat{Y}_{0},$

where $\widehat{X}_{0}:=P^{H}X_{0}P$ and $\widehat{Y}_{0}:=P^{H}Y_{0}P\geq 0$.
From the above discussion we have
$\widehat{X}_{0}=0_{m_{1}}\oplus\widehat{X}_{0,s}$,
$\widehat{Y}_{0}=0_{m_{1}}\oplus\widehat{Y}_{0,s}$ and
$\widehat{X}_{0,s}\in\mathbb{H}_{m_{2}}$ satisfies the Stein equation
$\mathcal{S}_{J_{s}}(\widehat{X}_{0,s})=\widehat{Y}_{0,s}\geq 0$. Therefore,
$X_{0}=P^{-H}(0_{m_{1}}\oplus\widehat{X}_{0,s})P^{-1}\geq 0$, since the matrix
$\widehat{X}_{0,s}=\mathcal{S}_{J_{s}}^{-1}(\widehat{Y}_{0,s})$ is positive
semidefinite if $\rho(J_{s})<1$.

In Lemma 3.7, the dual DARE of second kind will possess a positive definite
stabilizing solution if the sufficient conditions of the following lemma are
fulfilled, in which $\mathbb{D}^{c}=\\{z\in\mathbb{C}\,|\,|z|\geq 1\\}$ is the
complement of the open unit disk $\mathbb{D}$.

######  Lemma 2.13.

Assume that $X_{0}$ is a positive semidefinite solution of the Stein
inequality $\mathcal{S}_{A}(X)\geq BB^{H}$ with $B\in\mathbb{C}^{n\times m}$.
Then

  1. (i)

$\rho(A)<1$ if $\mathrm{Ker}(A-\lambda I)\cap\mathrm{Ker}(B^{H})=\\{0\\}$ for
$\lambda\in\sigma(A)\cap\mathbb{D}^{c}$ or, equivalently,
$\mathrm{rank}\begin{bmatrix}B^{H}\\\ A-\lambda I\end{bmatrix}=n$ for
$\lambda\in\sigma(A)\cap\mathbb{D}^{c}$.

  2. (ii)

$X_{0}>0$ if $\mathrm{Ker}(A-\lambda I)\cap\mathrm{Ker}(B^{H})=\\{0\\}$ for
$\lambda\in\sigma(A)$ or, equivalently, $\mathrm{rank}\begin{bmatrix}B^{H}\\\
A-\lambda I\end{bmatrix}=n$ for $\lambda\in\sigma(A)$.

######  Proof 2.14.

Under slightly different conditions, the results are derived as follows.

  1. (i)

Let $u\in\mathrm{Ker}(A-\lambda I)$ with $u\neq 0$ for
$\lambda\in\sigma(A)\cap\mathbb{D}^{c}$. Then

$\displaystyle 0$
$\displaystyle\geq(1-|\lambda|^{2})u^{H}X_{0}u\geq(B^{H}u)^{H}(B^{H}u)\geq 0.$

From the assumption we conclude that $u\in\mathrm{Ker}(A-\lambda
I)\cap\mathrm{Ker}(B^{H})=\\{0\\}$, which leads to a contradiction with $u\neq
0$. Thus, $|\lambda|<1$ for all $\lambda\in\sigma(A)$ or, equivalently,
$\rho(A)<1$.

  2. (ii)

Let $\lambda\in\sigma(A)$. For any $v_{1}\in\mathrm{Ker}(A-\lambda
I)\cap\mathrm{Ker}(X_{0})$, we see that

$0=(1-|\lambda|^{2})v_{1}^{H}X_{0}v_{1}\geq(B^{H}v_{1})^{H}(B^{H}v_{1})\geq
0.$

Then $v_{1}\in\mathrm{Ker}(A-\lambda I)\cap\mathrm{Ker}(B^{H})=\\{0\\}$ and
thus $v_{1}=0$. This implies that $\mathrm{Ker}(A-\lambda
I)\cap\mathrm{Ker}(X_{0})=\\{0\\}$. Suppose that $\mathrm{Ker}(A-\lambda
I)^{i}\cap\mathrm{Ker}(X_{0})=\\{0\\}$ for $1\leq i\leq k$ and
$k\in\mathbb{N}$. For any $v_{k+1}\in\mathrm{Ker}(A-\lambda
I)^{k+1}\cap\mathrm{Ker}(X_{0})$, let $v_{k}:=(A-\lambda I)v_{k+1}$ or
$Av_{k+1}=v_{k}+\lambda v_{k+1}$. Thus, we further obtain

$\displaystyle 0$ $\displaystyle\geq-
v_{k}^{H}X_{0}v_{k}=v_{k+1}^{H}X_{0}v_{k+1}-(v_{k}^{H}+\bar{\lambda}v_{k+1}^{H})X_{0}(v_{k}+\lambda
v_{k+1})$
$\displaystyle=v_{k+1}^{H}\mathcal{S}_{A}(X_{0})v_{k+1}\geq(B^{H}v_{k+1})^{H}(B^{H}v_{k+1})\geq
0.$

This leads to $X_{0}v_{k}=0$ and hence $v_{k}\in\mathrm{Ker}(A-\lambda
I)^{k}\cap\mathrm{Ker}(X_{0})=\\{0\\}$ or $v_{k}=0$. Then
$v_{k+1}\in\mathrm{Ker}(A-\lambda I)\cap\mathrm{Ker}(B^{H})=\\{0\\}$ or
$v_{k+1}=0$. That is, $\mathrm{Ker}(A-\lambda
I)^{k+1}\cap\mathrm{Ker}(X_{0})=\\{0\\}$. It follows from mathematical
induction that $\mathrm{Ker}(A-\lambda
I)^{\ell}\cap\mathrm{Ker}(X_{0})=\\{0\\}$ for each $\ell\in\mathbb{N}$.
Therefore,
$\mathrm{Ker}(X_{0})=\mathrm{Ker}(X_{0})\cap\mathbb{C}^{n}=\mathrm{Ker}(X_{0})\cap\Big{(}\bigoplus\limits_{\lambda\in\sigma(A)}E_{\lambda}(A)\Big{)}=\\{0\\}$
or, equivalently, $X_{0}\geq 0$ is nonsingular.

###  2.3 The formulation of the dual DARE

Let $A$ be nonsingular through this subsection. The positive semidefinite
solutions of dual DARE play a central role in the set of negative semidefinite
solutions of the original DARE. For the DARE (1b) of the compact form, we
shall provide the construction of two kinds of dual DARE (12) and (17), in
terms of the coefficient matrices $A$, $G$ and $H$, in this subsection.

####  2.3.1 The first kind of dual DARE

For the sake of simplicity the matrix products $A^{-H}XA^{-1}$ is denoted by
$X^{(A)}$ for any $X\in\mathbb{C}^{n\times n}$. Note that $I+GH^{(A)}$ is
nonsingular since $G,\,H^{(A)}\geq 0$. Then Eq. (1b) is equivalent to

$\displaystyle(I+GX)^{-1}$ $\displaystyle=I-G(X-H)^{(A)}=I+GH^{(A)}-GX^{(A)}$
$\displaystyle=(I+GH^{(A)})A(I-A^{-1}(I+GH^{(A)})^{-1}GA^{-H}X)A^{-1}$
$\displaystyle=\widehat{A}^{-1}(I-\widehat{G}X)A^{-1}.$

We immediately obtain $I-\widehat{G}X$ is nonsingular and

(11) $\displaystyle[(I+GX)^{-1}A]\times[(I+\widehat{G}Y)^{-1}\widehat{A}]=I$

, where $Y=-X$, $\widehat{A}=A^{-1}(I+H^{(A)})^{-1}$ and
$\widehat{G}=((I+GH^{(A)})^{-1}G)^{(A^{H})}=\widehat{A}GA^{-H}$. Eq. (11)
provides the formulation of the first kind of dual DARE

(12) $\displaystyle
Y=\mathcal{D}_{1}(Y):=\widehat{H}+\widehat{A}^{H}Y(I+\widehat{G}Y)^{-1}\widehat{A},$

where

$\displaystyle\widehat{H}$
$\displaystyle=-X+\widehat{A}^{H}X(I-\widehat{G}X)^{-1}\widehat{A}=-X+\widehat{A}^{H}XA^{-1}(I+GX)$
$\displaystyle=-X+\widehat{A}^{H}HA^{-1}(I+GX)+(I+H^{(A)}G)^{-1}X$
$\displaystyle=\widehat{A}^{H}HA^{-1}+\Big{[}-I+\widehat{A}^{H}HA^{-1}G+(I+H^{(A)}G)^{-1}\Big{]}X$
$\displaystyle=\widehat{A}^{H}HA^{-1}+\Big{[}-I+(I+H^{(A)}G)^{-1}H^{(A)}G+(I+H^{(A)}G)^{-1}\Big{]}X$
$\displaystyle=\widehat{A}^{H}HA^{-1}.$

Notice that if we write $G=BR^{-1}B^{H}$, then it is easily seen that

(13a) $\displaystyle\widehat{A}$
$\displaystyle=A^{-1}-\widehat{B}\widehat{R}^{-1}B^{H}H^{(A)},$ (13b)
$\displaystyle\widehat{G}$
$\displaystyle=\widehat{B}\widehat{R}^{-1}\widehat{B}^{H}\geq 0,$ (13c)
$\displaystyle\widehat{H}$
$\displaystyle=H^{(A)}-B^{H}H^{(A)}\widehat{R}^{-1}H^{(A)}B,$

where $\widehat{B}=A^{-1}B$ and $\widehat{R}=R+B^{H}H^{(A)}B>0$. (13) are the
same as the coefficient matrices defined in [9, Theorem 3.1]. More precisely,
we have

$\widehat{A}=\widetilde{A}-\widetilde{B}\widetilde{R}^{-1}\widetilde{C},\widehat{H}=\widetilde{H}-\widetilde{C}^{H}\widetilde{R}^{-1}\widetilde{C}.$

Finally, it is straightforward to verify

(14)
$\displaystyle(\mathcal{R}(X)-X)^{(A)}=(\mathcal{D}_{1}(Y)-Y)(I+GH^{(A)}),$

i.e., $Y=-X$ is a solution of dual DARE (12) if and only if $X$ is a solution
of DARE (1b). Notice that from (11) we have

$\displaystyle\sigma((I+\widehat{G}Y)^{-1}\widehat{A})=\sigma(T_{X}^{-1}).$

####  2.3.2 The second kind of dual DARE

Let $X$ be a Hermitian solution of the DARE (1b), then $X-H$ is nonsingular
and

(15) $\left[X(I+GX)^{-1}A\right]\times\left[(X-H)^{-1}A^{H}\right]=I.$

Furthermore, if $X$ is nonsingular, it follows from (15) that $Y:=-X^{-1}$
satisfies

(16) $\left[X(I+GX)^{-1}A\right]\times\left[Y(I+HY)^{-1}A^{H}\right]=-I$

or, equivalently,
$\left[Y(I+HY)^{-1}A^{H}\right]\times\left[X(I+GX)^{-1}A\right]=-I$. It thus
implies that $Y$ is a Hermitian solution to the second kind of dual DARE

(17) $Y=\mathcal{D}_{2}(Y):=AY(I+HY)^{-1}A^{H}+G.$

In addition, it is easily seen that the Hermitian matrices $X$ and $Y$ also
fulfill

(18a) $\displaystyle Y-\mathcal{D}_{2}(Y)$
$\displaystyle=A\left[(X-H)^{-1}-(\mathcal{R}(X)-H)^{-1}\right]A^{H}$ (18b)
$\displaystyle X-\mathcal{R}(X)$
$\displaystyle=A^{H}\left[(Y-G)^{-1}-(\mathcal{D}_{2}(Y)-G)^{-1}\right]A,$

i.e., $Y=-X^{-1}$ is a nonsingular solution of dual DARE (17) if and only if
$X=-Y^{-1}$ is a nonsingular solution of DARE (1b). Notice that from (16) we
have

(19)
$\displaystyle\sigma(((I+HY)^{-1}A^{H}))=\sigma(XT_{X}^{-1}X^{-1})=\sigma(T_{X}^{-1}).$

Analogously, let
$\mbox{dom}(\mathcal{D}_{1}):=\\{X\in\mathbb{H}_{n}\,|\,\det(I+\widehat{G}X)\neq
0\\}$ , $\mbox{dom}(\mathcal{D}_{2}):=\\{X\in\mathbb{H}_{n}\,|\,\det(I+HX)\neq
0\\}$ and
$\mathcal{D}_{\geq}^{(i)}:=\\{X\in\mbox{dom}(\mathcal{D}_{i})\,|\,X\geq\mathcal{D}_{i}(X)\\}$,
with $i=1,2$ for the sake of explanation.

##  3 Extremal solutions of the DARE

In this section, the existence of extremal solutions to the DARE (1) will be
established iteratively through the FPI given by

(20) $X_{k+1}=\mathcal{R}(X_{k}),\quad k\geq 0,$

with a suitable initial matrix $X_{0}\in\mathbb{N}_{n}$.

According to the formulations (14) and (18), when $A$ is nonsingular, it is
shown that $X\in\mathbb{H}_{n}$ is a solution of the DARE (1) if and only if
$-X\in\mathbb{H}_{n}$ is a solution of its dual DARE of first kind (14), and
$X\in\mathbb{H}_{n}$ is a nonsingular solution of the DARE (1) if and only if
$-X^{-1}\in\mathbb{H}_{n}$ is a solution of its dual DARE (17) of second kind.
With this reason, we thus consider two FPIs defined by

(21a) $\displaystyle Y_{k+1}$ $\displaystyle=\mathcal{D}_{1}(Y_{k}),\quad
k\geq 0,$ (21b) $\displaystyle Z_{k+1}$
$\displaystyle=\mathcal{D}_{2}(Z_{k}),\quad k\geq 0,$

with $Y_{0},Z_{0}\in\mathbb{N}_{n}$ being the initial guesses.

For the sake of explanation, $X_{+,M}$, $X_{+,m}$, $X_{-,M}$ and $X_{-,m}$
denote the maximal positive semidefinite solution, minimal positive
semidefinite solution, maximal negative semidefinite solution and minimal
negative semidefinite solution of DARE, respectively, if they exist. For the
sake of clarity, posive semidefinite and negative semidefinite extremal
solutions of the DARE (1) will be discussed separately in the following
subsections.

###  3.1 Positive semidefinite extremal solutions

The following theorem, quoted from [3, Theorem 3.2], guarantees the existence
of the minimal solution $X_{+,m}\in\mathbb{N}_{n}$ to the DARE (1b), i.e.,
$X_{+,m}\leq S$ for all $S\in\mathcal{R}_{\geq}\cap\mathbb{N}_{n}$, under
reasonable assumptions.

######  Theorem 3.1.

[3] If $\mathcal{R}_{\geq}\cap\mathbb{N}_{n}\neq\emptyset$, then the FPI (20)
generates a nondecreasing sequence of positive semidefinite matrices
$\\{X_{k}\\}_{k=0}^{\infty}$ with $0\leq X_{0}\leq H$, which converges at
least R-linearly to the minimal element $X_{+,m}$ of the solution set
$\mathcal{R}_{\geq}\cap\mathbb{N}_{n}$ with the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[k]{\|X_{k}-X_{+,m}\|}\leq\rho_{\mathbb{D}}(T_{X_{+,m}})^{2}<1.$

As a special case of Theorem 1.1 in [8], if $(A,B)$ is stabilizable and $H\geq
0$, then the DARE (1a) has a unique almost stabilizing $X_{\rm
s}\in\mathbb{H}_{n}$, which is the maximal element of the solution set
$\mathcal{R}_{=}$ satisfying $R+B^{H}X_{\rm s}B>0$. In the following theorem
the existence and uniqueness of the almost stabilizing solution to the DARE
(1) can be established under the framework of the fixed-point iteration.

######  Theorem 3.2.

If there exists $X_{\star}\in\mathbb{H}_{n}$ satisfying
$\rho(T_{X_{\star}})<1$, then the following statements hold:

  1. (i)

$\mathcal{S}_{\geq}=\\{X\in\mathbb{H}_{n}\,|\,\mathcal{S}_{T_{X_{\star}}}(X)\geq
H_{X_{\star}}\\}$ is a nonempty subset of
$\mathcal{R}_{\geq}\cap\mathbb{N}_{n}$, where
$H_{X_{\star}}=H+F_{X_{\star}}^{H}RF_{X_{\star}}$.

  2. (ii)

The FPI (20) generates a nonincreasing sequence of positive semidefinite
matrices $\\{X_{k}\\}_{k=0}^{\infty}$ with
$X_{0}=\mathcal{S}_{T_{X_{\star}}}^{-1}(H_{X_{\star}})$, which converges at
least R-linearly to the maximal element $X_{+,M}$ of
$\mathcal{R}_{\geq}\cap\mathbb{N}_{n}$ with the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[k]{\|X_{k}-X_{+,M}\|}\leq\rho(T_{+,M})^{2},$

provided that $\rho(T_{+,M})<1$.

  3. (iii)

For each $k\geq 0$, $\rho(T_{X_{k}})<1$ and thus $\rho(T_{+,M})\leq 1$.

######  Proof 3.3.

Notice that the operator $\mathcal{S}_{T_{X_{\star}}}$ is invertible because
$\rho(T_{X_{\star}})<1$.

  1. (i)

Since $H_{X_{\star}}\geq 0$, it follows from Lemma 2.2 that
$X_{0}=\mathcal{S}_{T_{X_{\star}}}^{-1}(H_{X_{\star}})\in\mathcal{S}_{\geq}\cap\mathbb{N}_{n}$,
and we further deduce that

$X-\mathcal{R}(X)=\mathcal{S}_{T_{X_{\star}}}(X)-H_{X_{\star}}+K(X_{\star},X)\geq
0$

and $X\geq 0$ for all $X\in\mathcal{S}_{\geq}$, since $K(X_{\star},X)\geq 0$
in (5b) for $X\geq 0$.

  2. (ii)

Because $X_{0}=\mathcal{S}_{T_{X_{\star}}}^{-1}(H_{X_{\star}})\geq 0$ is an
element of the set $\mathcal{R}_{\geq}$ and $H\geq 0$, we see tat
$X_{0}\geq\mathcal{R}(X_{0})=X_{1}\geq 0$ and hence it is easily seen that
$X_{k}\geq X_{k+1}\geq 0$ for $k\geq 1$ by induction, since the operator
$\mathcal{R}(\cdot)$ is order preserving. Thus, $\\{X_{k}\\}_{k=0}^{\infty}$
generated by the FPI (20) is a nonincreasing sequence of positive semidefinite
matrices, which converges to a limit $X_{+,M}\in\mathbb{N}_{n}$ eventually. On
the other hand, for any $X_{+}\in\mathcal{R}_{=}$, it follows from Theorem 2.8
and (5b) that $K(X_{\star},X_{+})\geq 0$ and
$H_{X_{\star}}=\mathcal{S}_{T_{X_{\star}}}(X_{+})+K(X_{\star},X_{+})\geq\mathcal{S}_{T_{X_{\star}}}(X_{+})$.
Since the inverse of $\mathcal{S}_{T_{X_{\star}}}$ is order preserving, we see
that $X_{0}=\mathcal{S}_{T_{X_{\star}}}^{-1}(H_{X_{\star}})\geq X_{+}$.
Suppose that $X_{i}\geq X_{+}$ for $i=0,1,2,\ldots,k$. Then
$X_{k+1}-X_{+}=\mathcal{R}(X_{k})-\mathcal{R}(X_{+})\geq 0$ and we thus deduce
that $X_{k}\geq X_{+}$ for all $k$. This yields
$X_{\infty}:=\lim\limits_{k\rightarrow\infty}X_{k}\geq X_{+}$ for all
$X_{+}\in\mathcal{R}_{=}$, i.e., the limit of $\\{X_{k}\\}_{k=0}^{\infty}$
must be the maximal element of the solution set $\mathcal{R}_{=}$ or
$X_{+,M}=X_{\infty}$. Moreover, the proof of the rate of convergence for
$\\{X_{k}\\}_{k=0}^{\infty}$ follows from the Appendix of [16].

  3. (iii)

For each $k\geq 0$, from (5b) we see that

(22a) $\displaystyle X_{k}-X_{k+1}$
$\displaystyle=\mathcal{S}_{T_{X_{k}}}(X_{k})-H_{X_{k}}$ (22b)
$\displaystyle=\mathcal{S}_{T_{X_{k-1}}}(X_{k})-H_{X_{k-1}}+K(X_{k-1},X_{k}),$

if we let $X_{-1}:=X_{\star}\in\mathbb{H}_{n}$. According to the Eq. (22a),
one deduces that $X_{k+1}=T_{X_{k}}^{H}X_{k}T_{X_{k}}+H_{X_{k}}$ for $k\geq
0$, and it follows from (22b) that

$\mathcal{S}_{T_{X_{k-1}}}(X_{k})-H_{X_{k-1}}\geq
X_{k}-T_{X_{k-1}}^{H}X_{k-1}T_{X_{k-1}}-H_{X_{k-1}}=0$

for all $k\geq 1$. Therefore, this yields the following Stein inequality

$\mathcal{S}_{T_{X_{k}}}(X_{k})\geq H_{X_{k}}+K(X_{k-1},X_{k})\geq 0$

for each $k\geq 0$, where the equality holds for $k=0$. Furthermore, we also
have

$\displaystyle\mathrm{Ker}\left(K(X_{k-1},X_{k})\right)$
$\displaystyle=\mathrm{Ker}\left(B^{H}(U_{X_{k-1}}-U_{X_{k}})\right)=\mathrm{Ker}(F_{X_{k-1}}-F_{X_{k}})$
$\displaystyle\subseteq\mathrm{Ker}(BF_{X_{k-1}}-BF_{X_{k}})=\mathrm{Ker}(T_{X_{k-1}}-T_{X_{k}}).$

Applying Lemma 2.6, we conclude that $\rho(T_{X_{k}})<1$, if
$\rho(T_{X_{k-1}})<1$, for each $k\geq 0$.

Now, in the following theorem, we will give some equivalent conditions for the
stabilizability of the pair $(A,B)$ from a differnt point of view.

######  Theorem 3.4.

The following statements are equivalent:

  1. (i)

The pair $(A,B)$ is stabilizable.

  2. (ii)

Tere exists a matrix $X_{\star}\in\mathbb{H}_{n}$ satisfying
$\rho(T_{X_{\star}})<1$.

  3. (iii)

The DARE (1) has a unique almost stabilizing solution $X\in\mathbb{H}_{n}$.

  4. (iv)

The DARE (1) has a maximal and almost stabilizing solution
$X\in\mathbb{H}_{n}$.

######  Proof 3.5.

The equivalence of these statements is given as follows.

  1. (i)$\Rightarrow$(ii):

If $(A,B)$ is stabilizable, then $A_{F}=A-BF$ is d-stable, i.e.,
$\rho(A_{F})<1$, for some $F\in\mathbb{C}^{m\times n}$. Recall that
$H_{F}=H+F^{H}RF\geq 0$, then $X_{\star}=\mathcal{S}_{A_{F}}^{-1}(H_{F})\geq
0$ and we further have

$\displaystyle\mathcal{S}_{T_{X_{\star}}}(X_{\star})$
$\displaystyle=(F-F_{X_{\star}})^{H}(I+B^{H}X_{\star}B)(F-F_{X_{\star}})+H+F_{X_{\star}}^{H}F_{X_{\star}}$
$\displaystyle\geq(F-F_{X_{\star}})^{H}(I+B^{H}X_{\star}B)(F-F_{X_{\star}})\geq
0,$

Since
$\mathrm{Ker}(F-F_{X_{\star}})\subseteq\mathrm{Ker}(A_{F}-T_{X_{\star}})$, it
follows from Lemma 2.6 and $\rho(A_{F})<1$ that the closed-loop matrix
associated with $X_{\star}\in\mathbb{H}_{n}$ is also d-stable, i.e.,
$\rho(T_{X_{\star}})<1$.

  2. (i)$\Leftarrow$(ii):

Suppose that the statement (ii) holds. If we let
$F=(R+B^{H}X_{\star}B)^{-1}B^{H}X_{\star}A$, then
$\rho(A-BF)=\rho(T_{X_{\star}})<1$ and hence $(A,B)$ is stabilizable.

  3. (i)$\Rightarrow$(iii):

Suppose that $(A,B)$ is stabilizable. Firstly, it follows from Theorem 3.2
that the DARE (1) has an almost stabilizing solution $X\geq 0$, which is the
maximal element of the solution set $\mathcal{R}_{=}$, if either the statement
(i) or (ii) holds. For the uniqueness of the solution $X$, we assume that the
DARE (1) has another solution $\widehat{X}\in\mathbb{H}_{n}$ with
$\rho(T_{\widehat{X}})\leq 1$. It is clear that $\widehat{X}\leq X$ because of
the maximality of $X$. On the other hand, from Lemma 2.11 and let
$\Delta:=\widehat{X}-X$, we have
$\mathcal{S}_{T_{\widehat{X}}}(\Delta)=K(\widehat{X},X)$. From
$F_{\widehat{X}}-F_{X}=(R+B^{H}{X}B)^{-1}B^{H}\Delta T_{{X}}$ we deduce that

$\mathcal{S}_{T_{\widehat{X}}}(\Delta)=K(\widehat{X},X)=T_{\widehat{X}}^{H}\Delta
Q_{1}\Delta T_{\widehat{X}},$

with $Q_{1}:=B(R+B^{H}XB)^{-1}B^{H}\geq 0$. Since $(A,B)$ is stabilizable and
$T_{\widehat{X}}=A-BF_{\widehat{X}}$, it follows that
$\mathrm{rank}[T_{\widehat{X}}-\lambda I\ B]=n$ for all
$\lambda\in\mathbb{D}^{c}$, and hence $\Delta\geq 0$ or $\widehat{X}\geq X$
follows from Lemma 2.11. Therefore, the DARE (1) must have a unique almost
stabilizing solution $X=\widehat{X}$.

  4. (i)$\Leftarrow$(iii):

Suppose that the statement (iii) holds and that $(A,B)$ is not stabilizable.
Then $\mathrm{rank}[A-\lambda I,B]<n$ for some $\lambda\in\mathbb{C}$ with
$|\lambda|\geq 1$. If $|\lambda|>1$ , then $\mathrm{rank}(A-BF_{X}-\lambda
I)<n$ or $\det(T_{X}-\lambda I)=0$, and we thus have
$\lambda\in\sigma(T_{X})$, which leads a contradiction with $\rho(T_{X})\leq
1$. On the other hand, if $\mathrm{rank}[A-\lambda I,B]<n$ for some
$\lambda\in\mathbb{C}$ with $|\lambda|=1$, there is a nonzero
$y\in\mathbb{C}^{n}$ such that $y^{H}[A-\lambda I\ B]=0$. Hence this implies
that $\Delta:=yy^{H}$ satisfies the following equation

$\mathcal{S}_{T_{X}}(\Delta)=T_{\Delta}^{H}\Delta BR^{-1}B^{H}\Delta
T_{\Delta}=K(\Delta,0).$

Therefore, it follows from Lemma 2.4 that
$\widehat{X}:=X+\Delta\in\mathbb{H}_{n}$ is also a solution of the DARE (1)
with $\sigma(T_{\widehat{X}})=\sigma(T_{X})\subseteq\bar{\mathbb{D}}$, which
leads to a contradiction with the uniqueness of the almost stabilizing
solution $X$ to the DARE (1). Consequently, the pair $(A,B)$ must be
stabilizable.

  5. (i)$\Rightarrow$(iv):

This follows from Theorem 3.2 directly, since the statements (i) and (ii) are
equivalent.

  6. (i)$\Leftarrow$(iv):

Assume that the DARE (1) has an almost stabilizing and maximal solution
$X\in\mathbb{H}_{n}$. If $(A,B)$ is not stabilizable, applying the similar
arguments described previously, there exist a nonzero $y\in\mathbb{C}$ and a
matrix $\Delta=yy^{H}\geq 0$ such that $X+\Delta$ is also an almost
stabilizing solution of the DARE (1a). Because of the maximality of $X$, we
obtain $X+\Delta\leq X$ and hence $\Delta=0$, which leads to a contradiction
with $y\neq 0$. Thus $(A,B)$ is stabilizable.

###  3.2 Negative semidefinite extremal solutions

In this section, when $A\in\mathbb{R}^{n\times n}$ is assumed to be
nonsingular, the existence of the negative semidefinite extremal solutions to
the DARE (1) will be addressed under the framework of two FPIs (21).

####  3.2.1 The first approach

Recall that the matrices $\widehat{A}$ and $\widehat{B}$ are defined by (13).
For a nonzero $\lambda$, the block row matrix
$\begin{bmatrix}\widehat{A}-\lambda I&\widehat{B}\end{bmatrix}$ can be
decomposed into

$\begin{bmatrix}\widehat{A}-\lambda
I&\widehat{B}\end{bmatrix}=A^{-1}\begin{bmatrix}A-\frac{1}{\lambda}I&B\end{bmatrix}\begin{bmatrix}-\lambda
I&0\\\ 0&I\end{bmatrix}\begin{bmatrix}I&0\\\
-\widehat{R}^{-1}B^{H}H^{(A)}&0\end{bmatrix}.$

Thus, we see that the pair $(\widehat{A},\widehat{B})$ is stabilizable if and
only if $\mathrm{rank}[A-\lambda I\ B]=n$ for
$\lambda\in\bar{\mathbb{D}}\backslash\\{0\\}$. Suppose that
$\mathrm{rank}[A-\lambda I\ B]=n$ for all
$\lambda\in\bar{\mathbb{D}}\backslash\\{0\\}$. Due to the stabilizability of
$(\widehat{A},\widehat{B})$ there exists a $\widehat{F}\in\mathbb{C}^{m\times
n}$ such that the matrix
$\widehat{A}_{\widehat{F}}:\widehat{A}-\widehat{B}\widehat{F}$ satisfies
$\sigma(\widehat{A}_{\widehat{F}})\subseteq\mathbb{D}$.

The following results can be proven by applying the similar arguments
described in the previous sections. Therefore, we state two theorems without
proof as follows.

######  Theorem 3.6.

Assume that $\widehat{H}\geq 0$. Then the following statements hold:

  * (i)

If $\mathcal{D}_{\geq}^{(1)}\cap\mathbb{N}_{n}\neq\emptyset$, then FPI (21a)
generates a nondecreasing sequence of positive semidefinite matrices
$\\{{Y}_{k}\\}_{k=0}^{\infty}$ with $0\leq{Y}_{0}\leq\widehat{H}$, which
converges at least R-linearly to $-X_{-,M}$ with the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[k]{\|{Y}_{k}+X_{-,M}\|}\leq\rho_{\mathbb{D}}(T_{X_{-,M}}^{-1})^{2}<1.$

  * (ii)

If $\mathrm{rank}[A-\lambda I\ B]=n$ for all
$\lambda\in\bar{\mathbb{D}}\backslash\\{0\\}$, then the FPI (21) generates a
nonincreasing sequence of positive semidefinite matrices
$\\{{Y}_{k}\\}_{k=0}^{\infty}$ with
${Y}_{0}=\mathcal{S}_{\widehat{A}_{\widehat{F}}}(\widehat{H}_{\widehat{F}})\geq
0$, which converges to $-X_{-,m}$ with the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[k]{\|{Y}_{k}+X_{-,m}\|}\leq\rho(T_{X_{-,m}}^{-1})^{2}=\mu(T_{X_{-,m}})^{2}\leq
1,$

where $\widehat{H}_{\widehat{F}}=\widehat{H}+\widehat{F}^{H}R\widehat{F}$.

####  3.2.2 The second approach

For solving the dual DARE (17) of second kind, we will apply FPI (21b) given
by

$Z_{k+1}=\mathcal{D}_{2}(Z_{k})=AZ_{k}(I+HZ_{k})^{-1}A^{H}+G,\quad k\geq 0,$

where $Z_{0}\geq 0$ is some initial matrix, $G=BR^{-1}B^{H}$ and $H\geq 0$,
respectively. The following result guarantees that the limit of the sequence
$\\{Z_{k}\\}_{k=0}^{\infty}$, if it exists, will be a unique (almost)
stabilizing solution of the dual DARE (17) under wild assumptions.

######  Lemma 3.7.

Assume that $D_{\geq}^{(2)}\cap\mathbb{N}_{n}\neq\emptyset$. Let
$\\{Z_{k}\\}_{k=0}^{\infty}$ be a sequence generated by the FPI (21b). Then
the following statements hold:

  1. (i)

If $0\leq Z_{0}\leq G$, then $\\{Z_{k}\\}_{k=0}^{\infty}$ is a nondecreasing
sequence of positive semidefinite matrices, which converges to the minimal
element $Z_{\infty}$ of the set $D_{\geq}^{(2)}\cap\mathbb{N}_{n}$.

  2. (ii)

Assume that $(A,B)$ is controllable, where $A\in\mathbb{C}^{n\times n}$ and
$B\in\mathbb{C}^{n\times m}$. Then $Z_{k}>0$ for $k\geq n$ if $Z_{0}=0$, and
$Z_{k}>0$ for $k\geq n-1$ if $Z_{0}=G$. Moreover, the dual DARE (17) has a
unique almost stabilizing solution $Z_{\infty}>0$.

  3. (iii)

If $0\leq Z_{0}\leq G$ and $(A(I+Z_{\infty}H)^{-1},B)$ is controllable, where
$Z_{\infty}$ is the minimal element of $D_{\geq}^{(2)}\cap\mathbb{N}_{n}$,
then $Z_{\infty}$ is a positive definite stabilizing solution to the dual DARE
(17).

######  Proof 3.8.

  1. (i)

This statement follows from Theorem 3.1 directly.

  2. (ii)

Suppose that the pair $(A,B)$ is controllable. It is well known that the
matrix $B_{n}:=[B,AB,\cdots,A^{n-1}B]$ has full rank. Now, if $Z_{0}=0$, then
$Z_{1}=BB^{H}:=B_{1}R_{1}^{-1}B_{1}^{H}$, where $B_{1}=B$ and $R_{1}=I_{m}$ is
the $m\times m$ identity matrix. Thus we further see that

$\displaystyle Z_{2}$
$\displaystyle=\mathcal{D}_{2}(Z_{1})=AB_{1}R_{1}^{-1}B_{1}^{H}(I+HB_{1}R_{1}^{-1}B_{1}^{H})^{-1}A^{H}+BB^{H}$
$\displaystyle=BB^{H}+AB_{1}(R_{1}+B_{1}^{H}HB_{1})^{-1}B_{1}^{H}A^{H}$
$\displaystyle=\begin{bmatrix}B_{1}&AB_{1}\end{bmatrix}\begin{bmatrix}R_{1}&0\\\
0&R_{1}+B_{1}^{H}HB_{1}\end{bmatrix}^{-1}\begin{bmatrix}B_{1}^{H}\\\
B_{1}^{H}A^{H}\end{bmatrix}:=B_{2}R_{2}^{-1}B_{2},$

with $B_{2}:=[B_{1}\ AB_{1}]=[B\ AB]$ and
$R_{2}:=R_{1}\oplus(R_{1}+B_{1}^{H}HB_{1})>0$. Inductively, we obtain
$Z_{k+1}=B_{k+1}R_{k+1}^{-1}B_{k+1}^{H}$, where $B_{k+1}:=[B_{1}\ AB_{k}]=[B\
AB\ A^{2}B\ \cdots\ A^{k}B]$ and
$R_{k+1}:=R_{1}\oplus(R_{k}+B_{k}^{H}HB_{k})>0$ for $k\geq 1$. In particular,
when $k=n-1$, we see that $Z_{n}=B_{n}R_{n}^{-1}B_{n}^{H}$ with
$\mathrm{rank}(B_{n})=n$. Let $B_{n}^{H}=Q\begin{bmatrix}L^{H}\\\
0\end{bmatrix}$ be the QR-decomposition with $Q\in\mathbb{C}^{mn\times mn}$
and $L\in\mathbb{C}^{n\times n}$ being unitary and nonsingular lower-
triangular matrices, respectively. This implies that $Z_{n}=[L\
0](Q^{H}R_{n}^{-1}Q)\begin{bmatrix}L^{H}\\\ 0\end{bmatrix}>0$. Furthermore,
continuing this process, it is still valid that $Z_{k}>0$ for each $k\geq n$.
For the case that $Z_{0}=G$, the result can be shown similarly. Since
$\\{Z_{k}\\}_{k=0}^{\infty}$ is a nondecreasing sequence, we see that
$Z_{k}\geq Z_{k_{0}}>0$ for some positive integer $k_{0}$ and thus
$Z_{\infty}=\lim\limits_{k\rightarrow\infty}Z_{k}\geq Z_{k0}>0$. Let
$W_{Z_{\infty}}:=(I+HZ_{\infty})^{-1}A^{H}$ be the closed-loop matrix
associated with $Z_{\infty}$ and we shall prove that $\rho(W_{Z_{\infty}})\leq
1$. If not, there is a $\lambda\in\mathbb{C}$ and a nonzero
$y\in\mathbb{C}^{n}$ such that $|\lambda|=\rho(W_{Z_{\infty}})>1$ and
$W_{Z_{\infty}}y=\lambda y$. Note that the matrix $Z_{\infty}>0$ also
satisfies

(23)
$\mathcal{S}_{W_{Z_{\infty}}}(Z_{\infty})=W_{Z_{\infty}}^{H}(Z_{\infty}+Z_{\infty}HZ_{\infty})W_{Z_{\infty}}+BR^{-1}B^{H}\geq
BB^{H}.$

Thus this implies $0>(1-|\lambda|^{2})(y^{H}Z_{\infty}y)\geq
y^{H}(BR^{-1}B^{H})y$, which leads to a contradiction with the positive
semiidefiniteness of $G=BR^{-1}B^{H}$. Consequently, $Z_{\infty}>0$ is the
unique almost stabilizing solution of the dual DARE (17).

  3. (iii)

Let $W_{Z_{\infty}}$ be the closed-loop matrix defined previously. Since
$(W_{Z_{\infty}}^{H},B)$ is controllable by the assumption, it follows that
$\mathrm{rank}\begin{bmatrix}W_{Z_{\infty}}-\lambda I\\\ B^{H}\end{bmatrix}=n$
for all $\lambda\in\sigma(W_{Z_{\infty}})$. Thus, from Lemma 2.13 and (23), we
obtain $\rho(W_{Z_{\infty}})<1$ and $Z_{\infty}>0$ immediately.

Based on (i) and (ii) of Lemma 3.7 and (19), the minimal negative semidefinite
solution of the DARE (1.1) can be obtained from the limit of
$\\{Z_{k}\\}_{k=0}^{\infty}$, which is summarized in the following theorem.

######  Theorem 3.9.

Assume that $D_{\geq}^{(2)}\cap\mathbb{N}_{n}\neq\emptyset$. If $(A,B)$ is
controllable, then FPI (21b) generates a nondecreasing sequence of positive
semidefinite matrices $\\{{Z}_{k}\\}_{k=0}^{\infty}$ with ${Z}_{0}=0$, which
converges at least R-linearly to a positive definite matrix $Z_{\infty}$ with
the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[k]{\|{Z}_{k}-Z_{\infty}\|}\leq\rho_{\mathbb{D}}(T_{Z_{\infty}}^{-1})^{2}<1.$

Furthermore, the minimal negative semidefinite solution of DARE (1) can be
obtained by $X_{-,m}=-Z_{\infty}^{-1}$.

Finally, the relationship between the almost stabilizabing solution and
positive semidefinite extremal solutions of DARE (1b) is summarized in the
following proposition without proof.

######  Proposition 3.10.

If $X_{s}$ is the unique almost stabilizabing solution of the DARE (1b), then

  1. (i)

$X_{+,M}$ exists and $X_{s}=X_{+,M}\geq 0$.

  2. (ii)

$X_{+,m}$ exists. Moreover, $X_{+,M}=X_{+,m}$ if $\rho(T_{X_{+,m}})\leq 1$,
and $X_{+,m}\neq X_{+,M}$ if $\rho(T_{X_{+,m}})>1$.

##  4 Acceleration of fixed-point iteration

In previous sections we have addressed the convergence of fixed-point
iteration $X_{k+1}=\mathcal{R}(X_{k})$, $k\geq 0$, for the existence of the
extremal solutions to DARE (1b), in which $X_{0}\in\mathbb{H}_{n}$ is some
appropriate initial guess. Since the FPI is usually linearly convergent, a
numerical method of higher order of convergence is always required in the
practical computation and many real-life applications. In this section, for
any positive integer $r>1$, we will revisit an accelerated FPI (AFPI) of the
form

(24a) $\displaystyle\widehat{X}_{k+1}$
$\displaystyle=\mathcal{R}^{(r^{k+1}-r^{k})}(\widehat{X}_{k}),\quad k\geq 1,$
(24b) $\displaystyle\widehat{X}_{1}$
$\displaystyle=\mathcal{R}^{(r)}(\widehat{X}_{0}),\quad k=1$

with $\widehat{X}_{0}=X_{0}$, for solving the numerical solutions of DARE
(1b). Here $\mathcal{R}^{(\ell)}(\cdot)$ denotes the composition of the
operator $\mathcal{R}(\cdot)$ itself for $\ell$ times, where $\ell\geq 1$ is a
positive integer. Theoretically, the iteration of the form (24) is equivalent
to the formula

(25) $\displaystyle\widehat{X}_{k}$
$\displaystyle=\mathcal{R}^{(r^{k})}(\widehat{X}_{0}),\quad k\geq 1,$

with $\widehat{X}_{0}=X_{0}$, and we see that

(26) $\displaystyle\widehat{X}_{k}=X_{r^{k}}$

for each $k\geq 1$. Therefore, it is an interesting and chanllenging issue to
make sure that the explicit expression of $\widehat{X}_{k}$ is of the form
(26) for each $k\geq 1$. In the following sections we will show that the AFPI
algorithm is more efficient than the iteration (25), or even some Newton-type
methods [8, 24], for solving the extremal solutions of the DARE (1b).

###  4.1 Equivalent formulation of the fixed-point iteration

The following definition  modifies the semigroup property of the iteration
associated a binary operator.

######  Definition 4.1.

[17] Let $\mathbb{K}_{n}\subseteq\mathbb{C}^{p\times q}$ and
$F:\mathbb{K}_{n}\times\mathbb{K}_{n}\rightarrow\mathbb{K}_{n}$ be a binary
matrix operator, where $p$ and $q$ are positive integers. We call that an
iteration

$\mathbb{X}_{k+1}=F(\mathbb{X}_{k},\mathbb{X}_{0}),\quad k\geq 0,$

has the semigroup property if the operator $F$ satisfies the following
associative rule:

$\displaystyle F(F(Y,Z),W)=F(Y,F(Z,W))$

for any $Y,Z$ and $W$ in $\mathbb{K}_{n}$.

It is interesting to point out that the sequence $\\{{\mathbb{X}}_{k}\\}$
satisfies the so-called discrete flow property [17], that is,

(27) $\displaystyle{\mathbb{X}}_{i+j+1}=F({\mathbb{X}}_{i},{\mathbb{X}}_{j})$

for any nonnegative integers $i$ and $j$.  Here the subscript of (27) is an
equivalent adjustment to the original formula [17, Theorem 3.2].

For the FPI defined by $X_{k+1}=\mathcal{R}(X_{k})$, in which
$X_{0}\in\mathbb{H}_{n}$ is an initial matrix and the operator
$\mathcal{R}(\cdot)$ is defined by (1b), it is shown in [16] that the fixed-
point iteration can be rewritten as the following formulation

(28)
$X_{k+1}=\mathcal{R}^{(k)}(\mathcal{R}(X_{0}))=\mathcal{R}^{(k+1)}(X_{0})=H_{k}+A_{k}^{H}X_{0}(I+G_{k}X_{0})^{-1}A_{k},$

where the sequence of matrices $\\{(A_{k},G_{k},H_{k})\\}_{k=0}^{\infty}$ is
generated by the following iteration

(29)
$\mathbb{X}_{k+1}=F(\mathbb{X}_{k},\mathbb{X}_{0}):=\begin{bmatrix}A_{0}\Delta_{G_{k},{H_{0}}}A_{k}\\\
G_{0}+A_{0}\Delta_{G_{k},{H_{0}}}G_{k}A_{0}^{H}\\\
H_{k}+A_{k}^{H}H_{0}\Delta_{G_{k},{H_{0}}}A_{k}\end{bmatrix},$

with $\mathbb{X}_{k}:=\left[A_{k}^{H}\ G_{k}\ H_{k}\right]^{H}$ and
$\mathbb{X}_{0}:=\left[A^{H}\ G\ H\right]^{H}$ for each $k\geq 0$, provided
that the matrices $\Delta_{G_{i},H_{j}}:=(I+G_{i}H_{j})^{-1}$ exists for all
$i,j\geq 0$. Notice that
$F:\mathbb{K}_{n}\times\mathbb{K}_{n}\rightarrow\mathbb{K}_{n}$ is a binary
operator with $\mathbb{K}_{n}:=\mathbb{C}^{n\times
n}\times\mathbb{H}_{n}\times\mathbb{H}_{n}$. Moreover, it has been shown in
Theorem 4.2 of [17] that the iteration (29) has the semigroup property and
thus satisfies (27). Based on the equivalent expression of the FPI (28), we
shall develop an accelerated FPI for computing the extremal solutions to the
DARE (1b).

######  Remark 4.2.

From the FPI (21b) and (29), it is worth mentioning that $Z_{k}=G_{k}$ for
each $k\geq 0$ when $Z_{0}=G_{0}=G$. Analogously, it follows from the discrete
flow property (27) and iteration (29) that $X_{k}=H_{k}$ for each $k\geq 0$ if
$X_{0}=H_{0}=H$.

###  4.2 The accelerated fixed-point iteration

In this section, we will mainly aim at some efficient ways for generating the
sequence of matrices $\\{(A_{k},G_{k},H_{k})\\}_{k=0}^{\infty}$ presented in
the FPI (28), where it may converge linearly. For the sake of simplicity, the
operator $\mathbf{F}_{\ell}:\mathbb{K}_{n}\rightarrow\mathbb{K}_{n}$ is
defined recursively by

(30)
$\mathbf{F}_{\ell+1}(\mathbb{X})=F(\mathbb{X},\mathbf{F}_{\ell}(\mathbb{X})),\quad\ell\geq
1,$

with $\mathbf{F}_{1}(\mathbb{X})=\mathbb{X}$ for all
$\mathbb{X}\in\mathbb{K}_{n}$ and $F(\cdot,\cdot)$ being defined by (29).
Furthermore, if we let $\mathbf{X}_{k}:=\left[\mathbf{A}_{k}^{H}\
\mathbf{G}_{k}\ \mathbf{H}_{k}\right]^{H}\in\mathbb{K}_{n}$ for $k\geq 0$ and
$\mathbf{X}_{0}:=\mathbb{X}_{0}$ be defined as in (29), then the sequence
$\\{\mathbf{A}_{k},\mathbf{G}_{k},\mathbf{H}_{k}\\}$ generated by the
iteration

(31)
$\mathbf{X}_{k+1}=F(\mathbf{X}_{k},\mathbf{X}_{k})=\mathbf{F}_{2}(\mathbf{X}_{k}),\quad
k\geq 0,$

which is equivalent to the doubling or strctured doubling algorithms [2, 5].
Indeed, according the semigroup and discrete flow property (27), we have
$\mathbf{A}_{k}=A_{2^{k}-1}$, $\mathbf{G}_{k}=G_{2^{k}-1}$ and
$\mathbf{H}_{k}=H_{2^{k}-1}$ for each $k\geq 0$. That is, under the iteration
(31), the sequence of matrices $\\{(A_{k},G_{k},H_{k})\\}_{k=0}^{\infty}$
proceeds rapidly with their subscripts being the exponential numbers of base
number $r=2$. From the theoretical point of view, staring with a suitable
matrix $X_{0}\in\mathbb{H}_{n}$, the sequence $\\{X_{k}\\}_{k=0}^{\infty}$
generated by (28) might also converge rapidly to its limit, if the limit
exists.

Analogously, when the base number is $r=3$, it is suggested in [17] to
consider an accelerated iteration of the form

$\mathbf{X}_{k+1}=F(\mathbf{X}_{k},F(\mathbf{X}_{k},\mathbf{X}_{k}))=\mathbf{F}_{3}(\mathbf{X}_{k}),\quad
k\geq 0,$

with $\mathbf{X}_{0}=\mathbb{X}_{0}$, and we have
$\\{\mathbf{A}_{k},\mathbf{G}_{k},\mathbf{H}_{k}\\}=\\{A_{3^{k}-1},G_{3^{k}-1},H_{3^{k}-1}\\}$
for each $k\geq 0$.

Recently, for any positive integer $r>1$, Lin and Chiang proposed an efficient
iterative method for generating the sequence
$\\{(A_{k},G_{k},H_{k})\\}_{k=0}^{\infty}$ with order $r$ of R-convergence,
provided that the operator $F(\cdot,\cdot)$ in (29) is well-defined, see,
e.g., Algorithm 3.1 in [17]. Theoretically, this algorithm utilizes the
following accelerated iteration

(32) $\mathbf{X}_{k+1}=\mathbf{F}_{r}(\mathbf{X}_{k}),\quad k\geq 0,$

with $\mathbf{X}_{0}:=\left[A^{H}\ G\ H\right]^{H}$ and
$\mathbf{F}_{r}(\cdot)$ being the operator defined by (30), for constructing
$\mathbf{A}_{k}=A_{r^{k}-1}$, $\mathbf{G}_{k}=G_{r^{k}-1}$ and
$\mathbf{H}_{k}=H_{r^{k}-1}$, respectively. Therefore, combining (28) and
(32), we obtain the pseudocode of AFPI summarized in Algorithm 1.

Algorithm 1 The Accelerated Fixed-Point Iteration with $r$ (AFPI($r$)) for
solving  $X=H_{0}+A_{0}^{H}X(I_{n}+G_{0}X)^{-1}A_{0}.$

$\mathbf{A}_{0}=A_{0}\in\mathbb{C}^{n\times n}$,
$\mathbf{G}_{0}=B_{0}R_{0}^{-1}B_{0}^{H}\geq 0$, $\mathbf{H}_{0}=H_{0}\geq 0$,
$(A_{0},B_{0})$ is stabilizable, initial matrix
$\widehat{X}_{0}\in\mathbb{H}_{n}$ and $r>1$.

the maximal positive semidefinite solution $\widehat{X}_{k_{1}}$ and the
minimal positive semidefinite solution $\mathbf{H}_{k_{2}}$.

for $k=0,1,2,\ldots$ do

$A_{k}^{(1)}=\mathbf{A}_{k}$, $G_{k}^{(1)}=\mathbf{G}_{k}$,
$H_{k}^{(1)}=\mathbf{H}_{k}$;

for $l=1,2,\ldots,r-2$ do

$A_{k}^{(l+1)}=A_{k}^{(l)}(I+\mathbf{G}_{k}H_{k}^{(l)})^{-1}\mathbf{A}_{k}$;

$G_{k}^{(l+1)}=G_{k}^{(l)}+A_{k}^{(l)}(I+\mathbf{G}_{k}H_{k}^{(l)})^{-1}\mathbf{G}_{k}(A_{k}^{(l)})^{H}$;

$H_{k}^{(l+1)}=\mathbf{H}_{k}+\mathbf{A}_{k}^{H}H_{k}^{(l)}(I+\mathbf{G}_{k}H_{k}^{(l)})^{-1}\mathbf{A}_{k}$;

end for

$\mathbf{A}_{k+1}=A_{k}^{(r-1)}(I+\mathbf{G}_{k}H_{k}^{(r-1)})^{-1}\mathbf{A}_{k}$;

$\mathbf{G}_{k+1}=G_{k}^{(r-1)}+A_{k}^{(r-1)}(I+\mathbf{G}_{k}H_{k}^{(r-1)})^{-1}\mathbf{G}_{k}(A_{k}^{(r-1)})^{H}$;

$\mathbf{H}_{k+1}=\mathbf{H}_{k}+\mathbf{A}_{k}^{H}H_{k}^{(r-1)}(I+\mathbf{G}_{k}H_{k}^{(r-1)})^{-1}\mathbf{A}_{k}$;

$\widehat{X}_{k+1}=\mathbf{A}_{k+1}^{H}\widehat{X}_{0}(I+\mathbf{G}_{k+1}\widehat{X}_{0})^{-1}\mathbf{A}_{k+1}+\mathbf{H}_{k+1}$;

if $\widehat{X}_{k_{1}}$ and $\mathbf{H}_{k_{2}}$ satisfy the stoping
criterion for some positive $k_{1},k_{2}$ then

return the positive semidefinite matrices $\widehat{X}_{k_{1}}$ and
$\mathbf{H}_{k_{2}}$;

end if

end for

Due to the property presented in (26), it seems that the superlinear
convergence of the AFPI algorithm would be expected in practical computation.
In our numerical experiments, we adopted $\mathbf{A}_{0}=A$, $B_{0}=B$,
$R_{0}=R$ and $\mathbf{H}_{0}=H$ in Algorithm 1 for computing the positive
semidefinite extremal solutions of the DARE (1). On the other hand, the posive
semidefinite extremal solutions of the dual DARE (12) were computed if we
adopted $\mathbf{A}_{0}=\widehat{A}$, $B_{0}=\widehat{B}$, $R_{0}=\widehat{R}$
and $\mathbf{H}_{0}=\widehat{H}$ defined by (13), respectively, as the initial
data in Algorithm 1.

###  4.3 Convergence analysis of the AFPI

As for Algorithm 1, worth mentioning is that it can be reduced to SDA
iteration when $r=2$ [5]. The following theorem guarantees, under the same
sufficient conditions as in Theorem 3.2 and the equivalent conditions
presented in Theorem 3.4, the R-superlinear convergence of
$\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$ and
$\\{\mathbf{H}_{k}\\}_{k=0}^{\infty}$ generated by Algorithm 1.

######  Theorem 4.3.

Let the sequences $\\{\mathbf{H}_{k}\\}_{k=0}^{\infty}$ and
$\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$ be generated by Algorithm 1 with
$\mathbf{A}_{0}=A$, $\mathbf{G}_{0}=G$ and $\mathbf{H}_{0}=H$, respectively.
If the hypotheses of Theorem 3.2 are satisfied, then

  1. (i)

$\\{\mathbf{H}_{k}\\}_{k=0}^{\infty}$ converges at least R-superlinearly to
$X_{+,m}$ with the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[r^{k}]{\|\mathbf{H}_{k}-X_{+,m}\|}\leq\rho_{\mathbb{D}}(T_{X_{+,m}})^{2}<1.$

  2. (ii)

$\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$ converges at least R-superlinearly to
$X_{+,M}$ with the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[r^{k}]{\|\widehat{X}_{k}-X_{+,M}\|}\leq\rho(T_{X_{+,M}})^{2},$

provided that $\rho(T_{X_{+,M}})<1$.

######  Proof 4.4.

From the AFPI (32) with $r>1$, the sequence
$\\{\mathbf{X}_{k}\\}_{k=0}^{\infty}$ generated by Algorithm 1 has the
semigroup property and thus satisfies the discrete flow property (27). With
the construction of these two sequences, we see that
$\mathbf{H}_{k}={H}_{r^{k}-1}$ and
$\widehat{X}_{k}=\mathcal{R}^{(r^{k}-1)}(X_{0})$ for each $k\geq 0$, see,
e.g., Remark 4.1 of [16]. The proof is straightforward from Theorem 3.1 and
Theorem 3.2.

In Theorem 4.3, there is no further conclusion for the sequence
$\\{\mathbf{G}_{k}\\}_{k=0}^{\infty}$ produced by Algorithm 1 under the
stabilizability assumption. As mentioned in Lemma 3.7 and Remark 4.2, this
sequence will also converge at least R-superlinearly under the controllability
of the pair $(A,B)$, which is stated without proof as follows.

######  Corollary 4.5.

Let $\\{\mathbf{G}_{k}\\}_{k=0}^{\infty}$,
$\\{\mathbf{H}_{k}\\}_{k=0}^{\infty}$ and
$\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$ be sequences generated by Algorithm 1
with $\mathbf{A}_{0}=A$, $\mathbf{G}_{0}=G$ and $\mathbf{H}_{0}=H$,
respectively. If $(A,B)$ is controllable and
$D_{\geq}^{(2)}\cap\mathbb{N}_{n}\neq\emptyset$, then the following statements
hold:

  1. (i)

$\mathbf{G}_{k}=Z_{r^{k}-1}$ for $k\geq 0$, where the sequence
$\\{Z_{k}\\}_{k=0}^{\infty}$ is generated by (21b) with
$\mathbf{G}_{0}=Z_{0}=G$. Moreover, $\\{\mathbf{G}_{k}\\}_{k=0}^{\infty}$
converges at least R-superlinearly to the unique almost stabilizing solution
$G_{\infty}>0$ of the dual DARE (17) with the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[r^{k}]{\|\mathbf{G}_{k}-G_{\infty}\|}\leq\rho_{\mathbb{D}}(T^{-1}_{G_{\infty}})^{2}<1.$

If, in addition, $A$ is nonsingular, then $X_{-,m}=-G_{\infty}^{-1}\leq 0$ is
the unique almost antistabilizing solution to the DARE (1b).

  2. (ii)

$\\{\mathbf{H}_{k}\\}_{k=0}^{\infty}$ and
$\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$ have the same results as Theorem 4.3.

When $A$ is nonsingular, according to Theorem 3.6 , it is possible to
characterize the R-superlinear convergence of Algorithm 1, with
$\mathbf{A}_{0}=\widehat{A}$, $\mathbf{G}_{0}=\widehat{G}$ and
$\mathbf{H}_{0}=\widehat{H}$, for computing the negative semidefinite extremal
solutions of the DARE (1b). It will be stated without proof as follows.

######  Theorem 4.6.

Let the sequences $\\{\mathbf{H}_{k}\\}_{k=0}^{\infty}$ and
$\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$ be generated by Algorithm 1 with
$\mathbf{A}_{0}=\widehat{A}$, $\mathbf{G}_{0}=\widehat{G}$ and
$\mathbf{H}_{0}=\widehat{H}$ being defined by (13), respectively. If the
hypotheses of Theorem 3.6 are satisfied, then

  1. (i)

$\\{\mathbf{H}_{k}\\}_{k=0}^{\infty}$ converges at least R-superlinearly to
$-X_{-,M}$ with the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[r^{k}]{\|\mathbf{H}_{k}+X_{-,M}\|}\leq\rho_{\mathbb{D}}(T_{X_{-,M}}^{-1})^{2}<1.$

  2. (ii)

$\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$ converges at least R-superlinearly to
$-X_{-,m}$ with the rate of convergence

$\limsup_{k\rightarrow\infty}\sqrt[r^{k}]{\|\widehat{X}_{k}+{X}_{-,m}\|}\leq\rho(T_{{X}_{-,m}}^{-1})^{2}=\mu(T_{{X}_{-,m}})^{-2},$

provided that $\rho(T_{{X}_{-,m}}^{-1})<1$ or $\mu(T_{{X}_{-,m}})>1$.

######  Remark 4.7.

  1. (i)

Under the hypotheses of Corollary 4.5, the sequences
$\\{G_{k}\\}_{k=0}^{\infty}$ and $\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$
obtained in Theorem 4.6 might have different speed of convergence, even though
the minimal solution $X_{-,m}$ can be computed from their limits. It can be
seen that the convergence of $\\{G_{k}\\}_{k=0}^{\infty}$ is at least
R-superlinear, but the convergence of $\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$
is unclear if $\mu(T_{X_{-,m}})=1$.

  2. (ii)

Although the statement (ii) in either Theorem 4.3 or Theorem 4.6 is
inconclusive when $\rho(T_{X_{+,M}})=1$ or $\mu(T_{X_{-,m}})=1$, it is
observed from our numerical experiments that the sequence
$\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$ may converge R-linearly with at least
the rate $1/r$, which will be investigated in the future and report the
theoretical results elsewhere.

##  5 Numerical examples

In this section, we present four examples to illustrate the accuracy and
efficiency of the AFPI($r$) in Algorithm 1 for solving the extremal solutions
of the DARE (1b). In the first three examples we compared the AFPI algorithm,
through the sequence $\\{\widehat{X}_{k}\\}_{k=0}^{\infty}$ starting with some
suitable initial $\widehat{X}_{0}$, with Newton’s method (NTM) [8] for solving
the maximal and (almost) stabilizing solution $X_{+,M}\geq 0$ of DARE (1b).
Here $\widehat{X}_{0}\geq 0$ is the unique solution of Stein matrix equation

(33) $\mathcal{S}_{A_{F}}(X):=X-A_{F}^{H}XA_{F}=H+F^{H}RF,$

which can be computed by MATLAB command dlyap directly, if $A_{F}=A-BF$ is
d-stable for some $F\in\mathbb{C}^{m\times n}$. Moreover, we assume $R=I$ in
all numerical examples.

As a byproduct, the sequence $\\{\mathbf{H}_{k}\\}_{k=0}^{\infty}$ generated
by Algorithm 1 converges at least R-superlinearly to the minimal positive
semidefinite solution $X_{+,m}$ of the DAREs in Example 5.1 and Example 5.2,
which is shown theoretically in Theorem 4.3. Moreover, we also demonstrate the
ability of the AFPI algorithm for computing the negative semidefinite extremal
solutions to the DARE in Example 5.4. Starting with $\widehat{A}$,
$\widehat{G}$, $\widehat{H}$ and $\widehat{X}_{0}$ defined as in (13), it is
seen in Theorem 4.6 that the AFPI produces two sequnces of matrices
$\\{-\widehat{X}_{k}\\}_{k=0}^{\infty}$ and
$\\{-\mathbf{H}_{k}\\}_{k=0}^{\infty}$ converging to the minimal negative
semidefinite solution $X_{-,m}$ and the maximal negative semidefinite solution
$X_{-,M}$ of the DARE (1b), respectively.

For an approximate solution $Z$ to the DARE (1), we will report its normalized
residual

$NRes(Z):=\frac{\|Z-\mathcal{R}(Z)\|}{\|Z\|+\|A^{H}Z(I+GZ)^{-1}A\|+\|H\|},$

and one of the following two quantities associated with $T_{Z}:=(I+GZ)^{-1}A$

$\rho(T_{Z}):=\max\\{|\lambda|\ |\
\lambda\in\sigma(T_{Z})\\},\quad\mu(T_{Z}):=\min\\{|\lambda|\ |\
\lambda\in\sigma(T_{Z})\\}$

in the tables below. We terminated the numerical methods AFPI and NTM when
$NRes\leq 1.0\times 10^{-15}$ in Examples 5.1–5.3, and the AFPI algorithm
terminated when $NRes\leq 1.0\times 10^{-12}$ in Example 5.4, respectively.
All numerical experiments were performed on ASUS laptop (ROG
GL502VS-0111E7700HQ), using Microsoft Windows 10 operating system and MATLAB
Version R2019b, with Intel Core i7-7700HQ CPU and 32 GB RAM.

######  Example 5.1.

Let the coefficient matrices of DARE (1b) be given by

$A=\begin{bmatrix}3&0\\\ 0&1/2\end{bmatrix},\quad B=\begin{bmatrix}1\\\
0\end{bmatrix},\quad C=\begin{bmatrix}0&1\end{bmatrix}.$

Then it is easily seen that the pair $(A,B)$ is stabilizable, but $(A,C)$ is
not detectable. Moreover, this DARE (1b) has only two positive semidefinite
solutions, namely,

$X_{+,M}=\begin{bmatrix}8&0\\\ 0&4/3\end{bmatrix},\quad
X_{+,m}=\begin{bmatrix}0&0\\\ 0&4/3\end{bmatrix},$

with $H=C^{H}C$. The matrix $X_{+,M}$ is the maximal and stabilizing solution
of the DARE such that the eigenvalues of $T_{X_{+,M}}=(I+GX_{+,M})^{-1}A$ are
$1/3$ and $1/2$, and $\sigma(T_{X_{+,m}})=\sigma(A)$, respectively. Thus,
$X_{+,m}$ is the minimal positive semidefinite solution of the DARE (1b) with
the property $\rho(T_{X_{+,m}})=3>1$.

If we choose $F=[3,0]$ so that $A_{F}=A-BF$ is d-stable and $\widehat{X}_{0}$
is determined by (33), then the numerical results of AFPI(2) and NTM are
presented in Table 1 and Table 2, respectively, where $\mathbf{A}_{0}=A$,
$\mathbf{G}_{0}=BB^{H}$ and $\mathbf{H}_{0}=H$ are required matrices for
Algorithm 1. Notice that our algorithm AFPI(2) generates two highly accurate
approximations to the extremal solutions $X_{+,M}$ and $X_{+,m}$
simultaneously, with the relative errors being $2.3\times 10^{-16}$ and
$0.0\times 10^{0}$ respectively, even though $\|\mathbf{A}_{k}\|$ increases
rapidly as $k$ proceeds. Nevertheless, starting from the same initial matrix
$X_{0}$, the NTM only produces an accurate approximation to the solution
$X_{+,M}$.

$k$ | $NRes(\widehat{X}_{k})$ | $NRes(\mathbf{H}_{k})$ | $\rho(T_{\widehat{X}_{k}})$ | $\rho(T_{\mathbf{H}_{k}})$ | $\|\mathbf{A}_{k}\|$
---|---|---|---|---|---
$1$ | $5.7\times 10^{-4}$ | $2.4\times 10^{-2}$ | $5.0\times 10^{-1}$ | $3.0\times 10^{0}$ | $9.0\times 10^{0}$
$2$ | $7.1\times 10^{-6}$ | $1.5\times 10^{-3}$ | $5.0\times 10^{-1}$ | $3.0\times 10^{0}$ | $8.1\times 10^{1}$
$3$ | $1.1\times 10^{-9}$ | $5.7\times 10^{-6}$ | $5.0\times 10^{-1}$ | $3.0\times 10^{0}$ | $6.6\times 10^{3}$
$4$ | $1.0\times 10^{-16}$ | $8.7\times 10^{-11}$ | $5.0\times 10^{-1}$ | $3.0\times 10^{0}$ | $4.3\times 10^{7}$
$5$ |  | $0.0\times 10^{0}$ |  | $3.0\times 10^{0}$ | $1.9\times 10^{15}$
Table 1: Numerical results of AFPI(2) for Example 5.1. $k$ | $NRes(X_{k})$ | $\rho(T_{X_{k}})$
---|---|---
$1$ | $5.7\times 10^{-4}$ | $5.0\times 10^{-1}$
$2$ | $8.7\times 10^{-8}$ | $5.0\times 10^{-1}$
$3$ | $2.1\times 10^{-15}$ | $5.0\times 10^{-1}$
$4$ | $0.0\times 10^{0}$ | $5.0\times 10^{-1}$
Table 2: Numerical results of NTM for Example 5.1.

######  Example 5.2.

In this example we consider the DARE (1b) with its $5\times 5$ coefficient
matrices being defined by

$A=\begin{bmatrix}2.9&1&0&0&0\\\ 0&2.9&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&1\end{bmatrix},\quad H=\begin{bmatrix}0&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&200&-0.5&0\\\ 0&0&-0.5&200&0\\\ 0&0&0&0&1\end{bmatrix}$

and $B=\mathrm{diag}(\sqrt{2},1,0,0,1)$, respectively. It can be shown that
the minimal positive semidefinite solution $X_{+,m}$ of the DARE (1b) is

$X_{+,m}=\begin{bmatrix}0&0&0&0&0\\\ 0&0&0&0&0\\\ 0&0&200&-0.5&0\\\
0&0&-0.5&200&0\\\ 0&0&0&0&(1+\sqrt{5})/2\end{bmatrix},$

which is almost the same as $H$ except the $(5,5)$-entry. If we let
$F=\mathrm{diag}(2,3,0,0,0.5)$ so that $\rho(A_{F})<1$ and $\widehat{X}_{0}$
is determined by (33), the numerical results of AFPI(2) and NTM are reported
in Table 3 and Table 4, respectively, for solving the DARE (1b) from the same
initial $\widehat{X}_{0}\geq 0$.

$k$ | $NRes(\widehat{X}_{k})$ | $NRes(\mathbf{H}_{k})$ | $\rho(T_{\widehat{X}_{k}})$ | $\rho(T_{\mathbf{H}_{k}})$ | $\|\mathbf{A}_{k}\|$
---|---|---|---|---|---
$1$ | $9.0\times 10^{-5}$ | $2.5\times 10^{-4}$ | $3.8\times 10^{-1}$ | $2.9\times 10^{0}$ | $1.2\times 10^{1}$
$2$ | $1.7\times 10^{-6}$ | $5.6\times 10^{-6}$ | $3.8\times 10^{-1}$ | $2.9\times 10^{0}$ | $1.3\times 10^{2}$
$3$ | $7.1\times 10^{-10}$ | $2.6\times 10^{-9}$ | $3.8\times 10^{-1}$ | $2.9\times 10^{0}$ | $1.5\times 10^{4}$
$4$ | $7.2\times 10^{-17}$ | $5.2\times 10^{-16}$ | $3.8\times 10^{-1}$ | $2.9\times 10^{0}$ | $1.4\times 10^{8}$
Table 3: Numerical results of AFPI(2) for Example 5.2. $k$ | $NRes(X_{k})$ | $\rho(T_{X_{k}})$
---|---|---
$1$ | $3.4\times 10^{-4}$ | $3.8\times 10^{-1}$
$2$ | $1.3\times 10^{-6}$ | $3.8\times 10^{-1}$
$3$ | $2.6\times 10^{-11}$ | $3.8\times 10^{-1}$
$4$ | $2.3\times 10^{-18}$ | $3.8\times 10^{-1}$
Table 4: Numerical results of NTM for Example 5.2.

Notice that, after $4$ iterations, the AFPI(2) generates accurate
approximations to the maximal and minimal positive semidefinite solutions of
the DARE (1b) simultaneously, but NTM merely computes an approximation to the
solution $X_{+,M}$. Since the exact maximal solution is unknown, we may apply
the MATLAB command dare to produce the accurate approximation of $X_{+,M}$.
The relative errors of the $4$th iterates computed by AFPI(2) are

$\frac{\|\widehat{X}_{4}-X_{+,M}\|}{\|X_{+,M}\|}\approx 1.6\times
10^{-16},\quad\frac{\|\mathbf{H}_{4}-X_{+,m}\|}{\|X_{+,m}\|}\approx 1.2\times
10^{-15},$

respectively, which shows the feasibility of our proposed algorithm.

######  Example 5.3.

This example is modified from Example 6.2 of [8]. For $\varepsilon\geq 0$, the
coefficient matrices of DARE (1b) are defined by

$\displaystyle A$ $\displaystyle=\mathrm{diag}\left(\begin{bmatrix}-1&0&0\\\
0&1&\varepsilon\\\
0&0&1\end{bmatrix},\begin{bmatrix}\frac{\sqrt{3}}{2}&\frac{1}{2}\\\
\frac{-1}{2}&\frac{\sqrt{3}}{2}\end{bmatrix},\begin{bmatrix}\frac{1}{2}&1&0\\\
0&\frac{1}{2}&1\\\ 0&0&\frac{1}{2}\end{bmatrix}\right),$ $\displaystyle B$
$\displaystyle=\begin{bmatrix}1&0&0&0&0&0&0&0\\\ 1&1&\varepsilon&0&0&0&0&0\\\
0&1&1&0&0&0&0&0\\\ 0&0&1&1&0&0&0&0\\\ 0&0&0&1&1&0&0&0\\\ 0&0&0&0&1&1&0&0\\\
0&0&0&0&0&1&1&0\\\ 0&0&0&0&0&0&1&1\end{bmatrix},\quad
H=C^{H}C=0\in\mathbb{R}^{8\times 8}.$

Then this DARE has a unique positive semidefinite solution
$X_{+,M}=X_{+,m}=0$, where $X_{+,M}$ is the almost stabilizing solution with
$\sigma(T_{X_{+,M}})=\sigma(A)$ for all $\varepsilon\geq 0$. Note that this
DARE (1b) is just the same as the one appeared in Example 6.2 of [8] when
$\varepsilon=0$, in which all unimodular eigenvalues of $A$ are semisimple.

If we choose $F=\mathrm{diag}(-1,1,1,1,1,0.1,0.1,0.1)$ for any
$\varepsilon\geq 0$, then $A_{F}=A-BF$ is d-stable so that the initial matrix
$\widehat{X}_{0}$ is the unique positive semidefinite solution to the Stein
equation (33). With $\mathbf{H}_{0}=H=0$, the AFPI($r$) generates
$\mathbf{H}_{k}=0$ for all $k\geq 0$ and $r\geq 2$. When $\varepsilon=0$, the
convergence histories of NTM and AFPI($r$) are presented in Fig. 1 for
$r=2,4,8$ and $100$, respectively. Moreover, the CPU times of these numerical
methods are reported in Table 5.

Method | Iter. No. | CPU Time (sec.)
---|---|---
AFPI(2) | $50$ | $8.78\times 10^{-3}$
AFPI(4) | $25$ | $1.45\times 10^{-2}$
AFPI(8) | $17$ | $1.35\times 10^{-2}$
AFPI(100) | $8$ | $1.51\times 10^{-2}$
NTM | $50$ | $3.08\times 10^{-2}$
Table 5: The CPU times of numerical methods for Example 5.3 with
$\varepsilon=0$. Figure 1: Convergence histories of numerical methods for
Example 5.3 with $\varepsilon=0$.

As for $\varepsilon=1$, the matrix $A$ contains an $2\times 2$ Jordan block
corresponding to the eigenvalue $\lambda=1$, and the other unimodular
eigenvalues are semisimple. In this case, the NTM encountered a breakdown
after $54$ iterations, due to the stagnation of dlyap for solving the
corresponding Stein equation. It requires about $3.16\times 10^{-2}$ second to
achieve the absolute error $\|X_{k}-X_{+,M}\|\approx 5.4\times 10^{-9}$. On
the other hand, the AFPI(100) produced a highly accurate approximation to the
solution $X_{+,M}=0$ with $\|\widehat{X}_{k}-X_{+,M}\|\approx 2.0\times
10^{-14}$ after $7$ iterations, starting from the same initial matrix
$\widehat{X}_{0}$ determined as NTM by (33). Moreover, the numerical results
of AFPI(100) are reported in Table 6. From the third column of Table 6 it
seems that the AFPI(100) converges linearly with rate of convergence being
$\frac{1}{r}=1.00\times 10^{-2}$ approximately, but this phenomenon will be
further investigated in the future and reported elsewhere.

$k$ | $\|\widehat{X}_{k}-X_{+,M}\|$ | $\frac{\|\widehat{X}_{k}-X_{+,M}\|}{\|\widehat{X}_{k-1}-X_{+,M}\|}$ | $\rho(T_{\widehat{X}_{k}})$ | $\|\mathbf{A}_{k}\|$
---|---|---|---|---
$1$ | $2.0\times 10^{-2}$ | $1.06\times 10^{-3}$ | $9.90\times 10^{-1}$ | $1.0\times 10^{2}$
$2$ | $2.0\times 10^{-4}$ | $1.02\times 10^{-2}$ | $1.0\times 10^{0}$ | $1.0\times 10^{4}$
$3$ | $2.0\times 10^{-6}$ | $1.00\times 10^{-2}$ | $1.0\times 10^{0}$ | $1.0\times 10^{6}$
$4$ | $2.0\times 10^{-8}$ | $1.00\times 10^{-2}$ | $1.0\times 10^{0}$ | $1.0\times 10^{8}$
$5$ | $2.0\times 10^{-10}$ | $1.00\times 10^{-2}$ | $1.0\times 10^{0}$ | $1.0\times 10^{10}$
$6$ | $2.0\times 10^{-12}$ | $1.00\times 10^{-2}$ | $1.0\times 10^{0}$ | $1.0\times 10^{12}$
$7$ | $2.0\times 10^{-14}$ | $1.00\times 10^{-2}$ | $1.0\times 10^{0}$ | $1.0\times 10^{14}$
Table 6: Numerical results of AFPI(100) for Example 5.3 with $\varepsilon=1$.

######  Example 5.4.

This example will demonstrate the feasibility of our AFPI algorithm for
solving the negative semidefinite extremal solutions of the DARE (1b). As
quoted from Example 6.2 of [24], the coefficient matrices of DARE (1b) are
given by

$A=\begin{bmatrix}4&3\\\ \frac{-9}{2}&\frac{-7}{2}\end{bmatrix},\quad
B=\begin{bmatrix}6\\\ -5\end{bmatrix},\quad H=\begin{bmatrix}9&6\\\
6&4\end{bmatrix}.$

Moreover, the authors in [24] suggested that the given DARE (1b) should be
transformed into its dual DARE (2) for computing the negative semidefinite
extremal solutions of the DARE (1b), where

$\widetilde{A}=\begin{bmatrix}7&6\\\
-9&-8\end{bmatrix},\quad\widetilde{B}=\begin{bmatrix}12\\\
-14\end{bmatrix},\quad\widetilde{C}=\begin{bmatrix}24&16\end{bmatrix},\quad\widetilde{R}=65,\quad\widetilde{H}=H.$

It is shown in [24] that the given DARE (1b) has three extremal solutions,
namely,

$X_{+,M}=X_{+,m}=\begin{bmatrix}\frac{9}{2}+\frac{9}{8}\sqrt{17}&3+\frac{3}{4}\sqrt{17}\\\\[4.30554pt]
3+\frac{3}{4}\sqrt{17}&2+\frac{\sqrt{17}}{2}\end{bmatrix}$

and

$X_{-,M}=\begin{bmatrix}\frac{9}{2}-\frac{9}{8}\sqrt{17}&3-\frac{3}{4}\sqrt{17}\\\\[4.30554pt]
3-\frac{3}{4}\sqrt{17}&2-\frac{\sqrt{17}}{2}\end{bmatrix},\quad
X_{-,m}=\begin{bmatrix}\frac{-103}{12}-\frac{\sqrt{17}}{8}&\frac{-39}{4}-\frac{\sqrt{17}}{4}\\\\[4.30554pt]
\frac{-39}{4}-\frac{\sqrt{17}}{4}&\frac{-43}{4}-\frac{\sqrt{17}}{2}\end{bmatrix},$

where $X_{+,M}\geq 0$ is the maximal and stabilizing solution, $X_{-,M}$ is
the maximal negative semidefinite solution and $X_{-,m}\leq 0$ is the minimal
sesolution, respectively.

Since it can be checked that
$90I\in\mathcal{D}_{\geq}^{(2)}\cap\mathbb{N}_{n}$ and $(A,B)$ is
controllable, the sufficient conditions of Corollary 4.5 are satisfied. If we
let $F=[-0.58,-0.68]$ so that $A_{F}$ is d-stable, then the AFPI(2), with
$\mathbf{A}_{0}=A$, $\mathbf{G}_{0}=G$, $\mathbf{H}_{0}=H$ and
$\widehat{X}_{0}$ being determined by (33), produced highly accurate
approximations to $X_{+,M}$ and $X_{-,m}$ with relative errors being
$1.8\times 10^{-16}$ and $5.9\times 10^{-14}$, respectively, after $5$
iterations.

In addition, for computing the negative semidefinite extremal solutions to the
DARE (1b), we consider the dual DARE (12) with $\widehat{B}=\widetilde{B}$,
$\widehat{R}=\widetilde{R}$,
$\widehat{A}=\widetilde{A}-\widehat{B}\widehat{R}^{-1}\widetilde{C}$,
$\widehat{G}=\widehat{B}\widehat{R}^{-1}\widehat{B}^{H}$ and
$\widehat{H}=\widetilde{H}-\widetilde{C}^{H}\widehat{R}^{-1}\widetilde{C}$,
respectively. Since the pair $(\widehat{A},\widehat{B})$ is stabilizable, we
may choose $\widehat{F}=[0.62,0.52]$ so that the matrix
$\widehat{A}_{\widehat{F}}:=\widehat{A}-\widehat{B}\widehat{F}$ is d-stable.
Let $\widehat{X}_{0}\geq 0$ be the unique solution to the Stein equation

$\mathcal{S}_{\widehat{A}_{\widehat{F}}}(X)=\widehat{H}+\widehat{F}^{H}\widehat{R}\widehat{F}\geq
0.$

Applying Algorithm 1 with $\mathbf{A}_{0}=\widehat{A}$,
$\mathbf{G}_{0}=\widehat{G}$, $\mathbf{H}_{0}=\widehat{H}$ and
$\widehat{X}_{0}$, the AFPI(4) generates highly accurate approximations
$\mathbf{H}_{3}\approx-X_{-,M}$ and $\widehat{X}_{3}\approx-X_{-,m}$ with
relative errors being $4.1\times 10^{-14}$ and $7.4\times 10^{-16}$,
respectively, after $3$ iterations. Moreover, the numerical results of AFPI(4)
are reported in Table 7. From the $5$th column of Table 7, we see that our
AFPI can provide a good approximation to the minimal and antistabilizing
solution $X_{-,m}$ of the DARE (1).

$k$ | $NRes(-\mathbf{H}_{k})$ | $NRes(-\widehat{X}_{k})$ | $\mu(T_{-\mathbf{H}_{k}})$ | $\mu(T_{-\widehat{X}_{k}})$ | $\|\mathbf{A}_{k}\|$
---|---|---|---|---|---
$1$ | $2.1\times 10^{-13}$ | $9.5\times 10^{-1}$ | $5.0\times 10^{-1}$ | $2.0\times 10^{0}$ | $5.7\times 10^{1}$
$2$ | $2.1\times 10^{-13}$ | $5.1\times 10^{-8}$ | $5.0\times 10^{-1}$ | $2.0\times 10^{0}$ | $2.3\times 10^{5}$
$3$ | $2.1\times 10^{-13}$ | $7.4\times 10^{-13}$ | $5.0\times 10^{-1}$ | $2.0\times 10^{0}$ | $1.3\times 10^{-1}$
Table 7: Numerical results of AFPI(4) for Example 5.4.

##  6 Concluding remarks

In most of the past works, it is always assumed that the DARE has a unique
maximal positive semidefinite solution $X$ with $\rho(T_{X})\leq 1$ and
another meaningful solutions are lacking in brief discussion. Our contribution
fills in the existing gap in finding four extremal solutions of the DARE. More
precisely, we have studied the existence of minimal and maximum solutions
under mild assumptions. It is important to note that we no longer need the
traditional assumptions on the distribution of the spectrum of the symplectic
matrix pencil or Popov matrix function, but give mathematical conditions from
different point of view.

This paper concerns comprehensive convergence analysis of the most recent
advanced algorithms AFPI, including its variant SDA, for solving the extremal
solutions of DARE. We verify that the AFPI works efficiently and the
convergence speed is R-superlinear under the mild assumptions. As compared to
the previous works, the theoretical results presented here are merely deduced
from the framework of the fixed-point iteration, using basic assumptions and
elementary matrix theory. We believe the results we obtain are novel on this
topic and could provide considerable insights into the study of unmixed
solutions of DARE.

## References

  * [1] J. Ackermann, Sampled-Data Control Systems: Analysis and Synthesis, Robust System Design, Springer Berlin Heidelberg, Berlin, Heidelberg, 1985.
  * [2] B. D. O. Anderson, Second-order convergent algorithms for the steady-state Riccati equation, in 1977 IEEE Conference on Decision and Control Including the 16th Symposium on Adaptive Processes and A Special Symposium on Fuzzy Set Theory and Applications, New Orleans, LA, USA, Dec. 1977, IEEE, pp. 948–953.
  * [3] C.-Y. Chiang, The convergence analysis of an accelerated iteration for solving algebraic Riccati equations, J. Franklin Inst., In Press (2021).
  * [4] C.-Y. Chiang, H.-Y. Fan, and W.-W. Lin, A structured doubling algorithm for discrete-time algebraic Riccati equations with singular control weighting matrices, Taiwanese J. Math., 14 (2010), pp. 933–954.
  * [5] E. K.-W. Chu, H.-Y. Fan, W.-W. Lin, and C.-S. Wang, Structure-preserving algorithms for periodic discrete-time algebraic Riccati equations, Int. J. Control, 77 (2004), pp. 767–788.
  * [6] S. M. El-Sayed and A. C. M. Ran, On an iteration method for solving a class of nonlinear matrix equations, SIAM J. Matrix Anal. & Appl., 23 (2002), pp. 632–645.
  * [7] T. Gudmundsson, C. Kenney, and A. Laub, Scaling of the discrete-time algebraic Riccati equation to enhance stability of the Schur solution method, IEEE Trans. Automat. Contr., 37 (1992), pp. 513–518.
  * [8] C.-H. Guo, Newton’s method for discrete algebraic Riccati equations when the closed-loop matrix has eigenvalues on the unit circle, SIAM J. Matrix Anal. & Appl., 20 (1998), pp. 279–294.
  * [9] V. Ionescu, Reverse discrete-time Riccati equation and extended Nehari’s problem, Linear Algebra Appl., 236 (1996), pp. 59–94.
  * [10] E. Jonckheere, On the existence of a negative semidefinite, antistabilizing solution to the discrete-time algebraic Riccati equation, IEEE Trans. Automat. Control, 26 (1981), pp. 707–712.
  * [11] M. Kimura, Convergence of the doubling algorithm for the discrete-time algebraic Riccati equation, Int. J. Syst. Sci., 19 (1988), pp. 701–711.
  * [12] V. Kučera, The discrete Riccati equation of optimal control, Kybernetika, 8 (1972), pp. 430–447.
  * [13] H. Kwakernaak and R. Sivan, Linear Optimal Control Systems, Wiley Interscience, New York, 1972.
  * [14] P. Lancaster and L. Rodman, Algebraic Riccati Equations, Oxford Science Publications, Clarendon Press ; Oxford University Press, Oxford : New York, 1995.
  * [15] A. Laub, A Schur method for solving algebraic Riccati equations, IEEE Trans. Automat. Contr., 24 (1979), pp. 913–921.
  * [16] M. M. Lin and C.-Y. Chiang, An accelerated technique for solving one type of discrete-time algebraic Riccati equations, J. Comput. Appl. Math., 338 (2018), pp. 91–110.
  * [17] , On the semigroup property for some structured iterations, J. Comput. Appl. Math., 374 (2020), p. 112768.
  * [18] V. Mehrmann, The Autonomous Linear Quadratic Control Problem: Theory and Numerical Solution, no. 163 in Lecture Notes in Control and Information Sciences, Springer, Berlin, 1991.
  * [19] C. Oară, Stabilizing solution to the reverse discrete-time Riccati equation: A matrix-pencil-based approach, Linear Algebra Appl., 246 (1996), pp. 113–130.
  * [20] T. Pappas, A. Laub, and N. Sandell, On the numerical solution of the discrete-time algebraic Riccati equation, IEEE Trans. Automat. Contr., 25 (1980), pp. 631–641.
  * [21] P. Van Dooren, A generalized eigenvalue approach for solving Riccati equations, SIAM J. Sci. and Stat. Comput., 2 (1981), pp. 121–135.
  * [22] H. Wimmer, The set of positive semidefinite solutions of the algebraic Riccati equation of discrete-time optimal control, IEEE Trans. Automat. Contr., 41 (1996), pp. 660–671.
  * [23] H. K. Wimmer, On the existence of a least and negative-semidefinite solution of the discrete-time algebraic Riccati equation, J. Math. Systems Estim. Control, 5 (1995), pp. 445–457.
  * [24] L. Zhang, M. Z. Q. Chen, and C. Li, The dual algebraic Riccati equations and the set of all solutions of the discrete-time Riccati equation, Int. J. Control, 90 (2017), pp. 1371–1388.