# On the Fractional Mean Value

Abdolali Neamaty, Mehdi Nategh
Department of Mathematics, Mazandaran University, Babolsar, Iran
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Abstract

This work, dealt with the classical mean value theorem and took advantage of
it in the fractional calculus. The concept of a fractional critical point is
introduced. Some sufficient conditions for the existence of a critical point
is studied and an illustrative example relevant to the concept of the time
dilation effect is given. The present paper also includes, some connections
between convexity (and monotonicity) with fractional derivative in the
Riemann-Liouville sense.

Keywords: Fractional derivative, Fractional critical point, Fractional mean
value, convexity.

AMS Subject Classification: 26A33, 97I40, 97I50.

##  1 Introduction

Fractional calculus which dates back to more than 300 years ago, has became
one of the thriving areas that is supported by the recent seminal papers
together with some special phenomenological viewpoints. Evidently, there are
many dynamic mechanisms in the universe (such as anomalous diffusion and
fractal dynamics) that are much more better to be described via the fractional
calculus than the classical one (see e.g. [5, 9, 11]).

In the present work, the concept of the mean value is nothing more than one is
given in the classical calculus. However, the prefix fractional, is to emboss
its concept for the next purposes which will be given in sections 2-4. Also it
has been several works in the fractional context that are devoted to this
concept. The generalized mean value theorem was first given in [10] and this
is about a generalized $Taylor$ formula in a fractional case. In [4], the
similar mean value theorem is obtained but it is more likely to the classical
case. This theorem in both mentioned forms have been used in many papers. In
[5], the Cauchy type mean value is obtained. Moreover, the mean value is
studied in a more abstract and operational form. Another generalized mean
value theorem is proved in [1] with slight changes, compared to the one is
obtained in [10].

The accurate relation between convexity and increase of the differential in
local sense, depends on the usual order on the real line. Connecting the
convexity to the differential (in non-local sense) in the same manner, needs
bringing an order on the domains of integrations, since we are dealing with
the integro-differential operators. This is done in section 4. Moreover, a
regularization is introduced, that upon which, the distribution of the
fractional mean values have became uniform. This is because we make use of the
fractional mean value in Theorem 4.5.

This paper is organized as follows: In section 2, some preliminaries on the
concept of the mean value is introduced and an approximation of it as a root
of a polynomial is given.
In section 2, the concept of the fractional critical point as the root of the
fractional derivative is introduced, and sufficient conditions for its
existence are studied. Also, an interpretation of the fractional critical
point is given based on the time dilation effect (according to [7]).
Connections between fractional derivative and convexity (as mentioned above)
and monotonicity are studied in section 3. A fundamental condition for this
connection is introduced. This condition, defines some order on the fractional
derivatives with respect to the orders on the intervals that are being
involved in the Riemann-Liouville integro-differential operator.

##  2 Fractional mean value

Definition 2.1. [2] Let $[a,b]$ be an interval and $f$ be an integrable
function. The left Riemann-Liouville fractional integral and derivative of
order $\alpha\in(0,1)$, (provided they exist) are defined by

$\displaystyle I^{\alpha}_{a^{+}}f(x):$ $\displaystyle=$
$\displaystyle\frac{1}{\Gamma(\alpha)}\int_{a}^{x}\frac{f(t)}{(x-t)^{1-\alpha}}dt\,\,\,\,\,\,\,\forall
x\in(a,b],$ (2.1) $\displaystyle D^{\alpha}_{a^{+}}f(x):$ $\displaystyle=$
$\displaystyle\frac{d}{dx}I^{1-\alpha}_{a^{+}}f(x)=\frac{1}{\Gamma(1-\alpha)}\frac{d}{dx}\int_{a}^{x}\frac{f(t)}{(x-t)^{\alpha}}dt\,\,\,\,\,\,\,\forall
x\in(a,b].$ (2.2)

where $\Gamma(\alpha)$ is the Gamma function. The space
$I^{\alpha}_{a^{+}}(L^{p})$ for $1\leq p\leq\infty$, is defined by

$I^{\alpha}_{a^{+}}(L^{p}):=\Big{\\{}f\,\,\Big{|}\,\,f=I^{\alpha}_{a^{+}}\phi,\,\,\phi\in
L^{p}(a,b)\Big{\\}}.$ (2.3)

The left Caputo fractional derivative of a function $f$ (provided it exists)
is defined by

${}^{C}D^{\alpha}_{a^{+}}f(x):=\frac{1}{\Gamma(1-\alpha)}\int_{a}^{x}\frac{f^{\prime}(t)}{(x-t)^{\alpha}}dt\,\,\,\,\,\,\,\forall
x\in(a,b].$ (2.4)

The set of absolutely continuous functions, that is denoted by $AC[a,b]$, is
the set of all functions $f$, which has representation of the form ([2]):

$f(x)=c+I^{n}_{a^{+}}\phi,\,\,\,\,\,\,\,\,c\in\mathbb{R},\,\,\phi\in L(a,b).$
(2.5)

Proposition 2.2.  [2]

a) If $f\in L^{p}(a,b)$, ($1\leq p<+\infty$), then

$D^{\alpha}_{a^{+}}I^{\alpha}_{a^{+}}f(x)=f(x).$ (2.6)

b) If $f\in L^{1}(a,b)$ and $f_{1-\alpha}=I^{1-\alpha}_{a^{+}}f\in AC[a,b]$,
then

$I^{\alpha}_{a^{+}}D^{\alpha}_{a^{+}}f(x)=f(x)-\frac{f_{1-\alpha}(a)}{\Gamma(\alpha)}(x-a)^{\alpha-1},$
(2.7)

holds almost everywhere on $[a,b]$.

c) If $f\in I^{\alpha}_{a^{+}}(L^{p})$, $(1\leq p\leq\infty)$ then

$I^{\alpha}_{a^{+}}D^{\alpha}_{a^{+}}f(x)=f(x).$ (2.8)

Proposition 2.3. Assume that $f$ is differentiable on $[a,b]$ with $f(a)=0$,
then
$(a)$ [2],

$D^{\alpha}_{a^{+}}f(x)=\,^{C}D^{\alpha}_{a^{+}}f(x)=I^{1-\alpha}_{a^{+}}f^{\prime}(x).$
(2.9)

$(b)$ [6],

$\lim_{\alpha\rightarrow 0^{+}}I^{\alpha}_{a^{+}}f(x)=f(x).$ (2.10)

Proposition 2.4. [8]
$(a)$ If $f\in AC[a,b]$, then $f_{1-\alpha}\in AC[a,b]$.
$(b)$ Abel’s integral equation is solvable in $L^{1}(a,b)$ if and only if
$f_{1-\alpha}\in AC[a,b]$ and we have

$f_{1-\alpha}(x)=\frac{1}{\Gamma(2-\alpha)}\Big{\\{}f(a)(x-a)^{1-\alpha}+\int_{a}^{x}f^{\prime}(t)()^{x-t1-\alpha}dt\Big{\\}}.$
(2.11)

Assumptions 2.5.  We assume that $f\in C^{1}[a,b]$ with $f(a)=0$ and
$D^{\alpha}_{a+}f\in C[a,b]$.

In this paper, all statements except Proposition 4.6, presume Assumption 2.5.
Also  Proposition 2.4, together with Assumption 2.5, yield the existence of
$D^{\alpha}_{a^{+}}f(x)$ for every $\alpha\in(0,1)$, since $C^{1}[a,b]\subset
AC[a,b]$.

Now we begin with this known lemma in the first semester calculus: Let
$\phi:\in L^{1}(a,b)$, then

$\exists\,\xi\in(a,b),\,\,\,\,f(\xi).\int_{a}^{b}\phi(t)dt=\int_{a}^{b}\phi(t)f(t)dt.$
(2.12)

Letting $\phi_{x}(t)=\frac{(x-t)^{-\alpha}}{\Gamma(1-\alpha)}$ we have

$\exists\,\xi\in(a,x),\,\,\,\,f(\xi).\frac{(x-a)^{1-\alpha}}{\Gamma(2-\alpha)}=\frac{1}{\Gamma(1-\alpha)}\int_{a}^{x}\frac{f(t)}{(x-t)^{\alpha}}dt=I^{1-\alpha}_{a^{+}}f(x).$
(2.13)

We name $\xi$ the fractional mean value. Since $\xi$ is not unique, we define

$\xi(x,\alpha):=\sup\Big{\\{}\xi\in(a,x)\,|\,f(\xi)=\Gamma(2-\alpha).\Big{(}I^{1-\alpha}_{a^{+}}f(x)\Big{)}.(x-a)^{\alpha-1}\Big{\\}}.$
(2.14)

In general, all possible $\xi$’s are belonging to the set
$\Lambda(\alpha,f,x)$ which is defined by

$\Lambda(\alpha,f,x):=f^{-1}\Big{\\{}\Gamma(2-\alpha).\Big{(}I^{1-\alpha}_{a^{+}}f(x)\Big{)}.(x-a)^{\alpha-1}\Big{\\}}.$
(2.15)

The set $\Lambda$ is closed, since $f$ is continuous. Let
$g(x):=\Gamma(2-\alpha).\Big{(}I^{1-\alpha}_{a^{+}}f(x)\Big{)}.(x-a)^{\alpha-1}$.
If $f$ is monotone on $(a,b)$, then for $x\in(a,b)$, there exists a unique
$\xi(x,\alpha)\in(a,x)$ for which $f(\xi(x,\alpha))=g(x)$. In other words,
$\forall x\in(a,b)$, $g(x)\in Im(f).$

Proposition 2.6.  Suppose $f$ is monotone on $(a,b)$. Then $\xi(x,\alpha)\in
C^{1}(a,b)$.

The following lemma gives some details about the mean value function $\xi$,
with respect to the variable $x$, but under the certain condition.

Proposition 2.7. Suppose that $h:[a,b]\rightarrow[a,b]$ is differentiable.
Assume that there exists some $x_{0}\in(a,b)$ at which $h$ has a local
extremum and also $h(x_{0})=\xi(x_{0})$, where $\xi(x)\in\Lambda(\alpha,f,x)$.
Then there exists some $x\in(a,b)$, such that

$D^{\alpha}_{a^{+}}f(x)=D\Big{(}f(h(x)).\frac{(x-a)^{1-\alpha}}{\Gamma(2-\alpha)}\Big{)}.$
(2.16)

Proof. In contrary assume that for every $x\in(a,b)$, we have:

$D^{\alpha}_{a^{+}}f(x)\neq
D\Big{(}f(h(x)).\frac{(x-a)^{1-\alpha}}{\Gamma(2-\alpha)}\Big{)}.$ (2.17)

Letting

$F(x,h)=I^{1-\alpha}_{a^{+}}f(x)-f(h(x)).\frac{(x-a)^{1-\alpha}}{\Gamma(2-\alpha)},$

we have $F(x_{0},h(x_{0})=0$ and $\frac{\partial F}{\partial
x}(x_{0},h(x_{0}))\neq 0$. By Implicit Function theorem, $x$ will be a
function of $h$ in the vicinity of $x_{0}$ and this is impossible since
$h^{\prime}(x_{0})=0$. This proves the assertion of the Lemma. $\Box$

Regarding to Proposition 2.7, when a given function $h\in C^{1}([a,b],[a,b])$,
satisfies $(2.17)$ everywhere, one conclude that $h$ is monotone, or
$h(x)\neq\xi(x)$ holds everywhere.

Proposition 2.8. Let $f\in C^{n+1}[a,b]$. Then $\xi(\alpha)$ can be estimated
by finding the roots of the following polynomial

$\displaystyle\forall$ $\displaystyle\delta<b-a,$ (2.18)
$\displaystyle\sum_{j=1}^{n}f^{(j)}(a).\Big{\\{}\frac{\delta^{1-\alpha}}{\Gamma(2-\alpha)j!}x^{j}-\frac{\delta^{j+1-\alpha}}{\Gamma(j+2-\alpha)}\Big{\\}}$
$\displaystyle-\Big{[}I^{n+2-\alpha}_{a^{+}}f^{(n+1)}\Big{]}(a+\delta)+o(\frac{1}{n!})=0,$

where $x=\xi-a$.

Proof. First observe that:

$f(\xi).\frac{\delta^{1-\alpha}}{\Gamma(2-\alpha)}=\Big{[}I^{1-\alpha}_{a^{+}}f\Big{]}(a+\delta)=\sum_{j=0}^{n}f^{(j)}.\frac{\delta^{j+1-\alpha}}{\Gamma(j+2-\alpha)}+\Big{[}I^{n+2-\alpha}_{a^{+}}f^{(n+1)}\Big{]}(a+\delta).$
(2.19)

On the other hand, taking into account the expansion of $f(\xi)$ about the
point $a$ that is:

$f(\xi)=\sum_{j=0}^{n}f^{(j)}(a).\frac{(\xi-a)^{j}}{j!}+o(\frac{1}{n!}),$
(2.20)

and equalizing with $f(\xi)$ in $(2.19)$, gives the result. $\Box$

##  3 Fractional critical point

In this section, the roots of the fractional derivative of a function $f$,
will be studied. This may be thought of as a parallel study to the critical
points in the ordinary calculus. For the similarity, we name the root of
$D^{\alpha}_{a^{+}}f$, the fractional critical point of $f$.

To find the fractional critical point of a function $f$ of order $1-\alpha$,
it is necessary and sufficient to find the nodes, those are intersections of
two curves $(x-a)^{\alpha}$ and $f(\xi(x))$. This can be stated in a rigorous
way as follows:

Lemma 3.1. Suppose $f$ is monotone, then

$f(\xi(x))=(x-a)^{\alpha},\,\,\,\,\,\,\,\,\,\xi(x)\in\Lambda(\alpha,f,x)$
(3.1)

if and only if $D^{1-\alpha}_{a^{+}}f(x)=0$.

Proof. Let $g(x)=f(-\eta(x))$, where $\eta(x)=-\xi(x)$. By Proposition 2.6,
$\eta$ is differentiable. The point $x_{0}\in(a,b)$ satisfies the equation
$g(x_{0})=(x_{0}-a)^{\alpha}$, if and only if it satisfies the following
equation

$(x-a)g^{\prime}(x)-\alpha g(x)=0.$ (3.2)

Multiplying $(3.2)$ by $\frac{(x-a)^{\alpha-1}}{\Gamma(1+\alpha)}$ we get:

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\frac{1}{\Gamma(1+\alpha)}\Big{(}-(x_{0}-a)^{\alpha}f^{\prime}(-\eta(x_{0}))\eta^{\prime}(x_{0})-\alpha(x_{0}-a)^{\alpha-1}f(-\eta(x_{0}))\Big{)}$
(3.3) $\displaystyle=$
$\displaystyle-\frac{d}{dx}\Big{(}\frac{(x-a)^{\alpha}}{\Gamma(1+\alpha)}.f(\xi(x))\Big{)}_{x=x_{0}}$
$\displaystyle=$
$\displaystyle-\frac{d}{dx}I^{\alpha}_{a^{+}}f(x)_{\Big{|}_{x=x_{0}}}$
$\displaystyle=$ $\displaystyle-D^{1-\alpha}_{a^{+}}f(x_{0}).\,\,\,\,\,\Box$

Theorem 3.2. Assume that $f(x)=0$ for some $x\in(a,b)$, then there exists some
$\xi\in(a,x]$ for which $D^{\alpha}_{a^{+}}f(\xi)=0$.

Proof. By $(2.11)$, $f_{1-\alpha}(a)=0$. Also by Proposition 2.2 (b), we have

$\exists\,\xi\in\Lambda(\alpha,D^{\alpha}_{a^{+}}f,x),\,\,D^{\alpha}_{a^{+}}f(\xi(x)).\frac{(x-a)^{\alpha}}{\Gamma(\alpha)}=I^{\alpha}_{a^{+}}D^{\alpha}_{a^{+}}f(x)=f(x)=0,$
(3.4)

$\Box$
Remark 3.3: According to the interpretation of the fractional derivative, that
is introduced in [7], let $v(t)$ be the velocity measured by an individual,
that is trapped in a gravitational field, $V$ be the velocity measured by an
independent observer, and $\tau$ and $t$ be the time in the presence of the
gravitational field and the cosmic time respectively, then we have:

$V(t)=D^{\alpha}_{a^{+}}v(t)=\frac{1}{\Gamma(1-\alpha)}\frac{d}{dt}\int_{a}^{t}\frac{v(\tau)}{(t-\tau)^{\alpha}}d\tau.$
(3.5)

If $v(t)$ vanishes at specific time $t$, then Theorem 3.2 states that, the
independent observer has measured zero velocity, sooner at some time
$\xi(t)\leq t$.

Lemma 3.4. For $x\in[a,b]$, we have

$\left\\{\begin{array}[]{ll}\lim_{\alpha\rightarrow
0^{+}}D^{\alpha}_{a^{+}}f(x)=f(x),\\\ \lim_{\alpha\rightarrow
1^{-}}D^{\alpha}_{a^{+}}f(x)=f^{\prime}(x).\end{array}\right.$ (3.6)

Proof. By assumption we have (Proposition $2.3(a)$)

$D^{\alpha}_{a^{+}}f(x)\,=\,^{C}D^{\alpha}_{a^{+}}f(x)=I^{p}_{a^{+}}f^{\prime}(x)$
(3.7)

where $p=1-\alpha$. Now by Proposition $2.3(b)$

$\lim_{\alpha\rightarrow 1^{-}}D^{\alpha}_{a^{+}}f(x)=\lim_{p\rightarrow
0^{+}}I^{p}_{a^{+}}f^{\prime}(x)==f^{\prime}(x).$ (3.8)

Again by $D^{\alpha}_{a^{+}}f(x)=I^{1-\alpha}_{a^{+}}f^{\prime}(x)$ we have

$\displaystyle\Big{|}I^{1-\alpha}_{a^{+}}f^{\prime}(x)-I^{1}_{a^{+}}f^{\prime}(x)\Big{|}$
$\displaystyle\leq$ $\displaystyle
M\Big{|}\int_{a}^{x}\Big{(}\frac{(x-t)^{-\alpha}}{\Gamma(1-\alpha)}-1\Big{)}dt\Big{|}$
(3.9) $\displaystyle=$ $\displaystyle
M\Big{|}\frac{(x-a)^{1-\alpha}}{\Gamma(2-\alpha)}-(x-a)\Big{|}.$

where $M=\max_{t\in[a,b]}|f^{\prime}(t)|$. Taking the limit $\alpha\rightarrow
0^{+}$, gives the result. $\Box$

Let $X_{\epsilon,\alpha}:=\Big{\\{}r\in
B(x_{0},\epsilon)\,|\,D^{\alpha}_{a^{+}}f(r)=0\Big{\\}}$ and $r(\alpha):=\sup
X_{\epsilon,\alpha}$ ( provided $X_{\epsilon,\alpha}\neq\emptyset$ ), where
$\epsilon\in\mathbb{R}^{+}$, $\alpha\in[0,1)$ and $x_{0}\in[a,b]$. We have the
following statement:

Theorem 3.5. Suppose $x_{0}$ and $x_{1}$ are the unique maximum (minimum) and
root of $f$ in $(a,b]$ respectively, then

$\left\\{\begin{array}[]{ll}\lim_{\alpha\rightarrow 0^{+}}r(\alpha)=x_{1},\\\
\lim_{\alpha\rightarrow 1^{-}}r(\alpha)=x_{0}.\end{array}\right.$ (3.10)

Proof. Without loss of generality, assume the $x_{0}$ is a maximum. For
$t\in(a,b)\backslash\\{x_{0}\\}$ we have

$\lim_{\alpha\rightarrow
1^{-}}D^{\alpha}_{a^{+}}f(t)=\left\\{\begin{array}[]{ll}f^{\prime}(t)>0&t\in(a,x_{0}),\\\
f^{\prime}(t)<0&t\in(x_{0},b).\end{array}\right.$ (3.11)

Since for every $\epsilon\in\mathbb{R}^{+}$, $f^{\prime}$ changes sign over
$B(x_{0},\epsilon)$, for $\alpha$ close enough to 1, $D^{\alpha}_{a^{+}}f$
changes sign too and therefore, $X_{\epsilon,\alpha}$ is nonempty. Let
$r=\limsup_{\alpha\rightarrow 1^{-}}r(\alpha)$. If $r\neq x_{0}$, then by
continuity of $f^{\prime}$ and $\lim_{\alpha\rightarrow
1^{-}}D^{\alpha}_{a^{+}}f(r(\alpha))=f^{\prime}(r(\alpha))$, one obtain

$\displaystyle 0=\limsup_{\alpha\rightarrow
1^{-}}D^{\alpha}_{a^{+}}f(r(\alpha))=f^{\prime}(r)\neq 0.$ (3.12)

Similarly we infer that, $\liminf_{\alpha\rightarrow 1^{-}}r(\alpha)=x_{0}$.
The same result can be obtained in the case $\alpha\rightarrow 0^{+}$. $\Box$

##  4 Convexity

In classical derivative, convexity of a differentiable function is equivalent
to that function has a nondecreasing derivative. In this section, our aim is
to give a similar argument. But first we need an order to give a meaning to
the concept of increase or decrease of the fractional derivative.

Regarding to [7], upon which, the fractional derivative, interpreted as the
real velocity (with respect to cosmic time) is calculated for an event that
happens in the presence of some strong gravitational field (with time dilation
effect), we propose the following:

With respect to the non-locality of the fractional derivative that involves
integrating over a time interval namely $[a,x]$, it seems to be reasonable if
we define an order on the fractional derivative, in such a manner that we fix
a constant length for two different time domains that the integrations are
taken over them, that is:

Definition 4.1. A real valued function $f$ is called $\delta$-increasing, if
for every $x_{0},y_{0},x,y\in\mathbb{R}$ and $\delta>0$ with $x_{0}<x<y_{0}<y$
and $x-x_{0}=y-y_{0}=\delta$ we have

$D^{\alpha}_{x_{0}^{+}}f(x-x_{0})\leq D^{\alpha}_{y_{0}^{+}}f(y-y_{0}).$

Next step is to set a discipline for the mean value corresponding to the
fractional integration of order $1-\alpha$:

Definition 4.2. We say that a continuous function $f$ has the property
$(\textbf{P})$, if for every $x_{0},y_{0},x,y\in\mathbb{R}$ and $\delta>0$
with $x_{0}<x<y_{0}<y$ and $x-x_{0}=y-y_{0}=\delta$, we have

$\xi_{x}-\xi_{y}=y_{0}-x_{0},$

where $\xi_{x_{0}+\delta}\in\Lambda(\alpha,f\circ(x-x_{0}),x_{0}+\delta)$ and
$\xi_{y_{0}+\delta}\in\Lambda(\alpha,f\circ(y-y_{0}),y_{0}+\delta)$.

The property $(\textbf{P})$ is about the independence of the mean value $\xi$
to the initial point $x_{0}$ or $y_{0}$, when we are dealing with the
fractional differentiation that involves integrating and the integration is
taken over two different time intervals of the same length,
$[x_{0},x_{0}+\delta]$ and $[y_{0},y_{0}+\delta]$.

Example 4.3.  Let $f(x)=x^{\beta}$ ( $\beta\in\mathbb{R}$ ), then $f$ is
$\delta$-increasing since

$D^{\alpha}_{x_{0}^{+}}f(x-x_{0})=\frac{\Gamma(1+\beta)}{\Gamma(\beta-\alpha+1)}(x-x_{0})^{\beta-\alpha}=\frac{\Gamma(1+\beta)}{\Gamma(\beta-\alpha+1)}\delta^{\beta-\alpha}.$
(4.1)

Also we have

$I^{1-\alpha}_{x_{0}^{+}}f(x-x_{0})^{\beta}=\frac{\Gamma(\beta)}{\Gamma(\beta-\alpha+1)}(x-x_{0})^{\beta-\alpha+1}=\frac{(x-x_{0})^{1-\alpha}}{\Gamma(2-\alpha)}(\xi(x)--x_{0})^{\beta},$
(4.2)

and we obtain

$\frac{\xi(x)-x_{0}}{x-x_{0}}=\Bigg{\\{}\frac{\Gamma(2-\alpha)\Gamma(\beta)}{\Gamma(\beta-\alpha+1)}\Bigg{\\}}^{\frac{1}{\beta}}.$
(4.3)

For $x_{0}<x<y_{0}<y$ with $x-x_{0}=y-y_{0}=\delta$, we have
$\xi(x)-x_{0}=\xi(y)-y_{0}$ if and only if
$\Bigg{\\{}\frac{\Gamma(2-\alpha)\Gamma(\beta)}{\Gamma(\beta-\alpha+1)}\Bigg{\\}}^{\frac{1}{\beta}}$
is a positive real number and it is equivalent to $f$ satisfies the property
$(P)$.

Remark 4.4. Under the monotonicity assumption of $f$ with property
$(\textbf{P})$ and denoting $\xi(x,a)$ the mean value defined by $(2.14)$, we
have

$\frac{\partial}{\partial
a}\Bigg{\\{}\Gamma(2-\alpha)\Big{(}I^{1-\alpha}_{a^{+}}f\Big{)}(x).(x-a)^{\alpha-1}\Bigg{\\}}=\frac{\partial}{\partial
a}f(\xi(x,a)).$ (4.4)

Indeed because of the independence of $\xi(x)-a$ to the initial point $a$,
there must be a function $h(x)$ such that $\xi(x)=a+h(x)$. So we have

$h(x)=f^{-1}\Bigg{\\{}\Gamma(2-\alpha)\Big{(}I^{1-\alpha}_{a^{+}}f\Big{)}(x).(x-a)^{\alpha-1}\Bigg{\\}}-a.$

Now differentiating with respect to $a$ and utilizing
$(f^{-1})^{\prime}=\frac{1}{f^{\prime}}$, gives $(4.1)$.

Theorem 4.5. Let $f^{\prime}$ satisfies the property $(\textbf{P})$. Then $f$
is convex if and only if it is $\delta$-increasing.

Proof. For $x_{0},y_{0}\in[a,b]$ and positive $\delta$ with $x_{0}<x<y_{0}<y$
and $x-x_{0}=y-y_{0}=\delta$, we have

$\displaystyle
D^{\alpha}_{x_{0}^{+}}f(x-x_{0})-D^{\alpha}_{y_{0}^{+}}f(y-y_{0})$
$\displaystyle=$ $\displaystyle
I^{1-\alpha}_{x_{0}^{+}}f^{\prime}(x-x_{0})-I^{1-\alpha}_{y_{0}^{+}}f^{\prime}(y-y_{0})$
(4.5) $\displaystyle=$
$\displaystyle\frac{\delta^{1-\alpha}}{\Gamma(2-\alpha)}.\Bigg{(}f^{\prime}(\xi(x))-f^{\prime}(\xi(y))\Bigg{)}.$

The fractional derivative is increasing if and only if $f^{\prime}(\xi(x))\leq
f^{\prime}(\xi(y))$ and by continuity of $f^{\prime}$, we infer that
$f^{\prime}$ is increasing and therefore $f$ is convex. $\Box$

For a positive $\tau$, let $\Delta f(x):=f(x+\tau)-f(x)$. If for a constant
$\tau$, we have $\Delta f(x)\geq 0$, then we say that $f$ is increasing up to
the positive constant $\tau$. Next Lemma is about the relationship between the
monotonicity of a function and its fractional derivative.

Proposition 4.6. Let $f\in C[0,b]$ and $f(x)=0$ for
$x\in\mathbb{R}\backslash[0,b]$. Let $D^{\alpha}_{a^{+}}f$ exists and for
$0<\tau<b$, we have $D^{\alpha}_{a^{+}}f(x)\leq D^{\alpha}_{a^{+}}f(x+\tau)$.
Then $f$ is increasing (up to $\tau$) if $\Delta f(0)\geq 0$.

Proof. The difference $\Delta D^{\alpha}_{0^{+}}f(x)$ (that is a function of
$x$ and $\tau$) is positive. Taking the Laplace transform we obtain

$L\Delta
D^{\alpha}_{0^{+}}f(x)=s^{\alpha}\Big{(}Lf(x+\tau)-Lf(x)\Big{)}-\Delta f(0).$
(4.6)

Then taking the inverse gives

$\displaystyle\Delta f(x)$ $\displaystyle=$
$\displaystyle\frac{1}{\Gamma(\alpha)}\Big{(}x^{\alpha-1}\Delta
f(0)+x^{\alpha-1}*\Delta D^{\alpha}_{a^{+}}f(x)\Big{)}$ (4.7) $\displaystyle=$
$\displaystyle\frac{x^{\alpha-1}}{\Gamma(\alpha)}\Delta
f(0)+I^{\alpha}_{a^{+}}\Delta D^{\alpha}_{a^{+}}f(x)\geq 0.,$

where asterisk means convolution. $\Box$

Remark 4.7.
It is easy to verify that, if $D^{\alpha}_{a^{+}}f(x)\leq
D^{\alpha}_{a^{+}}g(x)$ and $f(0)=g(0)$, then $f(x)\leq g(x)$.
Let $f$ be periodic with period $\tau$. Then $(4.7)$ gives
$I^{\alpha}_{a^{+}}\Delta D^{\alpha}_{a^{+}}f(x)=0$ and therefore

$D^{\alpha}_{a^{+}}f(x+\tau)=D^{\alpha}_{a^{+}}f(x).$ (4.8)

In other words, periodic functions have periodic fractional derivatives with
the same period.

Conclusion In this paper, the fractional mean value is introduced and its
approximation as the roots of a polynomial is obtained. Fractional critical
point is introduced, some sufficient conditions for its existence are studied
and an interpretation of such critical point is given with respect to the time
dilation effect in a gravitational field. Moreover, Convexity and monotonicity
and their possible connections to increase of a fractional derivative in the
Riemann-Liouville sense are discussed.

## References

  * [1] K. Diethelm, The mean value theorem and a Nagumo type uniqueness theorem for Caputo’s fractional calculus. Fractional Calculus and Applied Analysis, Volume 15, Number 2 304-313 (2012).
  * [2] A. Kilbas. Theory and application of fractional differential equations. Elsevier (2006).
  * [3] J. Klafter, I. M. Sokolov. Anomalous diffusion spreads its wings. Physics World, August (2005).
  * [4] Z. M. Odibat, N. T. Shawagfeh, Generalized $Taylor$ s formula. Applied Mathematics and Computation 186 286-293 (2007).
  * [5] J. E. Pe cari , I. Peri , H. M. Srivastavac. A family of the $Cauchy$ type mean-value theorems. J. Math. Anal. Appl. 306 730-739 (2005).
  * [6] I. Podlubny, Fractional differential equations. Academic Press (1990).
  * [7] I. Podlubny, Geometric and physical interpretation of fractional integration and fractional differentiation. Journal of Fractional Calculus and Applied Sciences. 307-386 (2002).
  * [8] S. G. Samko, A. A. kilbas, O. I. Marichev. Fractional integral and derivatives. Gordon and Breach Science Publishers. 1993.
  * [9] V. E. Tarasov. Flow of fractal fluid in pipes: Non-intege dimensional space approach. Chaos, Solitons and Fractals 67 26-37 (2014).
  * [10] J. J. Trujillo, M. Rivero, B. Bonilla. On a Riemann Liouville Generalized Taylor s Formula. Journal of Mathematical Analysis and Applications 231, 255-265 (1999).
  * [11] L. Vlahos, H. Laliker, Y. Kominis and K. Hyzanidis. Normal and Anomalous Diffusion: A Tutorial. arXiv:0805.0419v1 [nlin.CD] 5 May 2008.


#  The convergence analysis of an accelerated iteration for solving algebraic
Riccati equations

Chun-Yueh Chiang11footnotemark: 1<EMAIL_ADDRESS>Center for General
Education, National Formosa University, Huwei 632, Taiwan.

###### Abstract

The discrete-time algebraic Riccati equation (DARE) have extensive
applications in optimal control problems. We provide new theoretical supports
to the stability properties of solutions to the DARE and reduce the
convergence conditions under which the accelerated fixed-point iteration
(AFPI) can be applied to compute the numerical solutions of DARE. In
particular, we verify that the convergence of AFPI is R-superlinear when the
spectral radius of the closed-loop matrix is greater than 1, which is shown by
mild assumption and only using primary matrix theories. Numerical examples are
shown to illustrate the consistency and effectiveness of our theoretical
results.

###### keywords:

algebraic Riccati equations, discrete-time asymptotically stable, discrete-
time Lyapunov stable, stabilizing solution, minimal solution, structure-
preserving doubling algorithms, R-superlinear with order $r$

###### MSC:

39B12, 39B42, 47J22, 65H05, 15A24

fn2fn2footnotetext:  The second author was supported by the Ministry of
Science and Technology of Taiwan under grant 108-2115-M-150-002.

##  1 Introduction

The discrete algebraic Riccati equation (DARE) arising in the field of applied
mathematics and many classical problems of control theory has been a subject
of study for a long time, see [2, 11, 8] and the references therein.

In this paper, we are concerned with the discrete-time algebraic Riccati
equation (DARE)

$\displaystyle X=R_{\rm d}(X):=H+A^{\ast}X(I+GX)^{-1}A,$ (1)

where $A\in\mathbb{C}^{n\times n}$, $G$ and $H$ are positive semidefinite
matrices of size $n\times n$, and the $n$-square matrix $X$ is the unknown
Hermitian matrix that is to be determined. Here $\ast$ stands the complex
conjugate transpose. We provide new theoretical supports to the stability
properties of solutions to the DARE (1) and new convergence results for an
iteration method, proposed recently in [12, 13].

In the past few decades, there have developed fruitful theoretical results as
well as a variety of numerical algorithms for the DARE such as the famous
direct method, the Schur method, and some iterative methods including matrix
disk function method, matrix sign function method, Newton iterations (NM) and
structure-preserving doubling algorithm (SDA), as well as those developed in
[2, 11, 8]. Among those methods, NM and SDA, both of which converge
quadratically, are well-known for their fast convergence behaviour. In
contrast to the NM, which requires the computation of the inverse of
Fr$\rm\acute{e}$chet derivatives, two kinds of SDA have attracted much
interests because of its nice numerical behavior, quadratic convergence rates,
low computational costs, and high numerical reliability. See e.g. [8].

Recently, the semigroup property for some binary matrix operations is
investigated in [13] and has been applied to the construction of iterations
for solving DARE. More precisely, applying the semigroup property to a fixed-
point iteration $\mathbb{X}_{k+1}=F(\mathbb{X}_{k},\mathbb{X}_{1})$, one can
obtain an accelerated iteration(AFPI) with at least the R-convergence rate of
any desired order $r$. Moreover, this iterative method can be reduced to SDA
when $r=2$.

A Hermitian solution $X$ of Eq. (1) is called stabilizing (respectively,
almost stabilizing) if all the eigenvalues of the closed-loop matrix
$T_{X}:=(I+GX)^{-1}A$ are in the open (respectively, closed) unit disk. The
stability property plays important role in the analysis of the convergence
behaviour of SDA. In the previous works, the convergence analysis of SDA are
concerned with “the regular case”, that is, $\rho(T_{X})<1$ and “the critical
case” when $\rho(T_{X})=1$. It has been proved that the SDA has quadratic
convergence in the regular case, while for the critical case, the convergence
speed is usually linear under some additional assumptions [4, 5, 7, 14, 2].
For example, in the critical case, it was proved in [4] that the SDA converges
linearly to an almost stabilizing solution $X_{+}$ with rate at least $1/2$ if
each unimodular eigenvalue of $T_{X_{+}}$ has a half of the partial
multiplicity of $\mathcal{M}-\lambda\mathcal{L}$, where

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

is a matrix pencil associated with the Eq. (1). Note that
$\mathcal{M}\begin{bmatrix}I\\\ X\end{bmatrix}=\mathcal{L}\begin{bmatrix}I\\\
X\end{bmatrix}T_{X}$ if and only if $X$ is a Hermitian solution of Eq. (1).
One contribution in this paper is shown that the SDA still converges
quadratically when solving equations of type (1) even in the critical case.

As mentioned above the convergence assumptions in the critical case are highly
related to the distribution of the partial multiplicity of the unimodular
eigenvalue of $\mathcal{M}-\lambda\mathcal{L}$, which is very sensitive to
perturbations and difficult to compute. Therefore, the convergence criterion
is not easy to discriminate due to the ill-posed problem, which must be solved
at this end. In the practical implementations it is expected to avoid
computing the elementary divisors corresponding to the eigenvalues of
$\mathcal{M}-\lambda\mathcal{L}$ on the unit circle. By the way, we are
interested in the case where some eigenvalues of
$\mathcal{M}-\lambda\mathcal{L}$ are outside the unit circle and we study the
convergence behaviors of the SDA when $\rho(T_{X})>1$.

The main contribution of this paper is to show that, under ceratin conditions,
the quadratic convergence of AFPI still holds in the critical case and even
$\rho(T_{X_{+}})>1$. we show that the assumption on the partial multiplicities
of unimodular eigenvalue can be reduced to any size, which has not been
discussed in the previous works.

This paper is organized as follows. In Section 2, we provide some
preliminaries used in solving matrix equations; In Section 3, we describe how
to use a congruent transformation in order to reduce the compact structure of
Eq. (1) and provide a fixed-point iteration with R-linearly convergence to
compute the minimal positive definite solution, including but not limited to
$\rho(T_{X})<1$; An R-superlinearly convergent iterative method with order
$r>1$ is discussed and two numerical experiments show that the reliability and
efficiency of the proposed method in Section 4. Finally, concluding remarks
are given in Section 6.

In the subsequent discussion, the symbols $\mathbb{C}^{n\times n}$,
$\mathbb{H}_{n}$, $\mathbb{N}_{n}$ and $\mathbb{P}_{n}$ stand for the set of
$n\times n$ complex matrices, Hermitian matrices, positive semidefinite
matrices and positive definite matrices, respectively. We denote, the open
unit disk by $\mathbb{D}$, the closed unit disk by $\bar{\mathbb{D}}$ and the
unit disk by $\mbox{bd}(\mathbb{D})$, the $m\times m$ identity matrix by
$I_{m}$, the conjugate matrix of $A$ by $\overline{A}$, the conjugate
transpose matrix of $A$ by $A^{\ast}$, the spectrum of $A$ by $\sigma(A)$ and
use $\rho(A)$ to denote the spectral radius of a square matrix $A$, and
$\mbox{nullity}(A)$ stands for the dimension of the kernel of a matrix $A$. We
use the symbol $A>0$ (or $A\geq 0$) to represent that $A$ is a Hermitian
positive definite matrix (or a Hermitian positive semidefinite matrix) and the
Loewner order $A>B$ (or $A\geq B$ ) with two Hermitian matrices $A$ and $B$ if
$A-B>0$ (or $A-B\geq 0$). We use $[A,B]$ to denote the subset
$\\{C\in\mathbb{H}_{n}|A\leq C\leq B\\}$ and use $A\oplus B$ to denote the
direct sum of two square matrices $A$ and $B$. A Hermitian solution $X_{+}$ of
Eq.(1) is called maximal (or minimal) if $X_{+}\geq S$ (or $X_{+}\leq S$) for
every Hermitian solution $S$.

##  2 Preliminaries

We start this section by recalling some useful definitions and theoretical
results concerning Eq.(1). As one of the most important evaluations of an
iterative method, the speed of convergence is usually measured by the R-order
convergence, which is introduced in [15, 10, 16, 2].

######  Definition 2.1.

Given a sequence $\\{X_{k}\\}\subseteq\mathbb{C}^{n\times n}$ and an induced
matrix norm $\|.\|$, then $X_{k}$ converges R-linearly to $X_{\star}$ if

$\displaystyle\limsup\limits_{k\rightarrow\infty}\sqrt[k]{\|X_{k}-X_{\star}\|}\leq\sigma,\quad\sigma\in(0,1),$

and $X_{k}$ converges R-superlinearly to $X_{\star}$ with at least order $r$
if

$\displaystyle\limsup\limits_{k\rightarrow\infty}\sqrt[r^{k}]{\|X_{k}-X_{\star}\|}\leq\sigma,\quad\sigma\in(0,1),$

where $r>1$ is an integer.

The following result is a generalization of the completeness of real number.

######  Lemma 2.1.

[1][Proposition 8.6.3] Let $\\{A_{i}\\}_{i=1}^{\infty}$ be a sequence of
positive semidefinite matrices satisfying $A_{j}\geq A_{i}\geq 0$ if $j\geq
i$, and assume that $B$ is another positive semidefinite matrix satisfying
$B\geq A_{i}$ for all $i>0$. Then, $A=\lim\limits_{i\rightarrow\infty}A_{i}$
exists and $B\geq A\geq 0$.

A matrix operator $f:\mathbb{H}_{n}\rightarrow\mathbb{H}_{n}$ is order
preserving (resp. reversing) if $f(A)\geq f(B)$ (resp. $f(A)\leq f(B)$) when
$A\geq B$ and $A,B\in\mathbb{H}_{n}$. The first proposition is vital and
elementary.

######  Proposition 2.1.

Under the assumptions on the coefficients $A$, $G$, and $H$, the matrix
operator $R_{\rm d}:\mathbb{N}_{n}\rightarrow\mathbb{N}_{n}$ is order
preserving on $\mathbb{N}_{n}$.

###### Proof.

We prove the result by showing that

$\displaystyle(I_{n}+AC)^{-1}A\geq(I_{n}+BC)^{-1}B$ (2)

if $A\geq B$ for any positive semidefinite matrices $A$,$B$ and $C$ of size
$n$. Let $A_{\epsilon}:=A+\epsilon I_{n}$ and $B_{\epsilon}:=B+\epsilon I_{n}$
for $\epsilon>0$. It is evident that

$\displaystyle(I_{n}+A_{\epsilon}C)^{-1}A_{\epsilon}=(A_{\epsilon}^{-1}+C)^{-1}\geq(B_{\epsilon}^{-1}+C)^{-1}=(I_{n}+B_{\epsilon}C)^{-1})B_{\epsilon},$
(3)

Take the limit as $\epsilon$ goes to zero from the right on both sides of (3),
which promptly yields (2) by continuity argument.

This proposition immediately follows from the below inequality,

$R_{\rm d}(X)-R_{\rm d}(Y)=A^{\ast}[(I_{n}+XG)^{-1}X-(I_{n}+YG)^{-1}Y]A\geq
0,$

if $X\geq Y$. ∎

Consider the matrix equation

$\displaystyle X=F(X),$ (4)

where $F$ is a monotone matrix operator on $\mathbb{H}_{n}$. The following
theorem shows the existence of extreme Hermitian solutions of Eq. (4).

######  Theorem 2.1.

Assume that the matrix operator $F:\mathbb{H}_{n}\rightarrow\mathbb{H}_{n}$ is
order preserving. Let $S_{1}:=\\{X\in\mathbb{H}_{n}|X\geq F(X)\\}$ and
$S_{2}:=\\{X\in\mathbb{H}_{n}|X\leq F(X)\\}.$ Consider the fixed-point
iteration defined by

$\displaystyle X_{k+1}=F(X_{k}),$

with an initial matrix $X_{1}\in\mathbb{H}_{n}$. Suppose that there is
$\widehat{X}_{1}\in S_{1}$ and $\widehat{X}_{2}\in S_{2}$ such that
$\widehat{X}_{1}\geq\widehat{X}_{2}$. Then, we have the following statements:

  * (1a).

$F([\widehat{X}_{2},\widehat{X}_{1}])\subseteq[\widehat{X}_{2},\widehat{X}_{1}]$
and there is a $X\in[\widehat{X}_{2},\widehat{X}_{1}]$ solving Eq. (4) if $F$
is continuous on $[\widehat{X}_{2},\widehat{X}_{1}]$.

  * (1b).

The sequence $\\{X_{k}^{-}\\}$ with $X_{1}^{-}=\widehat{X}_{2}$ is
monotonically nondecreasing and converges to a solution $X_{\star}^{-}$ of Eq.
(4) and $X_{\star}^{-}\leq\widehat{X}_{1}$.

  * (1c).

The sequence $\\{X_{k}^{+}\\}$ with $X_{1}^{+}=\widehat{X}_{1}$ is
monotonically nonincreasing and converges to a solution $X_{\star}^{+}$ of Eq.
(4) and $X_{\star}^{+}\geq\widehat{X}_{2}$.

  * (1d).

For any positive integer $k$, we have

$\widehat{X}_{2}\leq X_{k}^{-}\leq X_{k+1}^{-}\leq X_{\star}^{-}\leq
X_{\star}^{+}\leq X_{k+1}^{+}\leq X_{k}^{+}\leq\widehat{X}_{1}.$

Furthermore, $X_{\star}^{+}$ is the maximal Hermitian solution of (4) if
$\widehat{X}_{1}$ is an upper bound of $S_{2}$, and $X_{\star}^{-}$ is the
minimal Hermitian solution of (4) if $\widehat{X}_{2}$ is a lower bound of
$S_{1}$.

###### Proof.

Concerning part (1a), since $F$ is order preserving, it can be easily seen
that
$F(X)\in[F(\widehat{X}_{2}),F(\widehat{X}_{1})]\subseteq[\widehat{X}_{2},\widehat{X}_{1}]$
for any $X\in[\widehat{X}_{2},\widehat{X}_{1}]$. If $F$ is continuous, then
$F$ has a fixed point in $[\widehat{X}_{2},\widehat{X}_{1}]$ from the Brouwer
fixed point theorem.

Parts (1b) and (1c) can be proved easily by an induction on $k$. Concerning
part (1b), we have
$\widehat{X}_{1}-X_{1}^{-}=\widehat{X}_{1}-\widehat{X}_{2}\geq 0$ and
${X}_{2}^{-}-X_{1}^{-}=F(\widehat{X}_{2})-\widehat{X}_{2}\geq 0$. From the
inductive assumption $\widehat{X}_{1}-X_{k}^{-}\geq 0$ and
${X}_{k+1}^{-}-X_{k}^{-}\geq 0$, we derive the following inequalities

$\displaystyle\widehat{X}_{1}-X_{k+1}^{-}$ $\displaystyle\geq
F(\widehat{X}_{1})-F(X_{k}^{-})\geq 0,$
$\displaystyle{X}_{k+2}^{-}-X_{k+1}^{-}$
$\displaystyle=F({X}_{k+1}^{-})-F(X_{k}^{-})\geq 0,$

which completes the induction process. Part (1c) can be proved analogously.

For the inequalities in part (1d), we only need to prove $X_{\star}^{-}\leq
X_{\star}^{+}$ since the rest is a direct consequence of parts (1b) and (1c).
Observe that $\widehat{X}_{2}\leq\widehat{X}_{1}$ so that
$F^{(k)}(\widehat{X}_{2})\leq F^{(k)}(\widehat{X}_{1})$, which implies
$X_{\star}^{-}=\lim\limits_{k\rightarrow\infty}F^{(k)}(\widehat{X}_{2})\leq\lim\limits_{k\rightarrow\infty}F^{(k)}(\widehat{X}_{1})=X_{\star}^{+}$.

For the rest of the statement, it is easily seen that $S_{2}$ contains all
Hermitian solution of Eq. (4). Let $X\in S_{2}$. Observe that
$X_{1}^{+}=\widehat{X}_{1}\geq X$ and $X_{k+1}^{+}=F(X_{k}^{+})\geq F(X)\geq
X$ if $X_{k}^{+}\geq X$ for any integer $k\geq 1$. One may easily prove by
induction that $X_{k}^{+}\geq X$ for all integer $k\geq 1$. Thus,
$X_{\star}^{+}=\lim\limits_{k\rightarrow\infty}X_{k}^{+}\geq X$ with all
Hermitian solution $X$ of Eq. (4). The same argument is applied to the proof
of the minimal Hermitian solution $X_{\star}^{-}$.

∎

As previously mentioned, the convergence behavior of SDA for solving DARE (1)
is highly related to the distance between the unit circle and the spectral
radius of the closed-loop matrix, which is characterized by the stability
properties of the solution of equation (1).

A useful tool in the estimation of $\rho(T_{X})$ is the inertia theorems for
Stein matrix equation (SME). In stability theory and its applications many
results for SME has attracted great attentions for its theoretical and
practical significance in systems control [11]. Let the Stein matrix operator
$S_{A}:\mathbb{N}_{n}\rightarrow\mathbb{H}_{n}$ associated with a matrix
$A\in\mathbb{C}^{n\times n}$ be defined by

$\displaystyle S_{A}(X):=X-A^{\ast}XA,$ (5)

for any $X\in\mathbb{N}_{n}$. In general, the operator $S_{A}$ is neither
order preserving nor order reversing. However, under the assumption that
$\rho(A)<1$ the operator $S^{-1}_{A}:\mathbb{N}_{n}\rightarrow\mathbb{N}_{n}$
exists, and $S^{-1}_{A}$ is order preserving since
$S_{A}^{-1}(X)=\sum\limits_{k=0}^{\infty}(A^{k})^{\ast}XA^{k}\geq\sum\limits_{k=0}^{\infty}(A^{k})^{\ast}YA^{k}=S_{A}^{-1}(Y)$
for $X\geq Y$.

In the rest of the section, we propose the stability properties of a discrete-
time Lyapunov operator and equation. We begin with the definitions of Lyapunov
stability and asymptotic stability of a matrix.

######  Definition 2.2.

[1, Definition 11.8.1.] Let $A\in\mathbb{C}^{n\times n}$. The notation ${\rm
ind}_{\lambda}(A)$ denotes the size of the largest Jordan block corresponding
the eigenvalue $\lambda$ of $A$. Furthermore,

  1. 1.

A is discrete-time asymptotically stable if $\rho(A)<1$.

  2. 2.

A is discrete-time Lyapunov stable if $\rho(A)\leq 1$ and ${\rm
ind}_{\lambda}(A)=1$ for all unimodular eigenvalues of $A$.

In analogy with [1][Proposition 11.10.5], we have the following similar
result, the proof can be found in the Appendix.

######  Lemma 2.2.

Let $S_{A}:\mathbb{N}_{n}\rightarrow\mathbb{H}_{n}$ be the Stein matrix
operator defined in (5). Then, we have the following statements:

  1. 1.

there exists a matrix $X_{0}\in\mathbb{P}_{n}$ such that $S_{A}(X_{0})>0$ if
and only if $A$ is discrete-time asymptotically stable.

  2. 2.

there exists a matrix $X_{0}\in\mathbb{P}_{n}$ such that $S_{A}(X_{0})\geq 0$
if and only if $A$ is discrete-time Lyapunov stable. Furthermore, the numbers
of unimodular eigenvalues (counting multiplicities) is the nullity of
$S_{A}(X_{0})$.

As a consequence of Lemma 2.2, we have

######  Corollary 2.1.

For a matrix $A\in\mathbb{C}^{n\times n}$, $A$ is discrete-time asymptotically
(or Lyapunov) stable if exactly one of the following possibilities occurs.

  1. 1.

Let the Stein matrix equation with sign “-” be defined by

$\displaystyle X-A^{\ast}XA=Q,$ (6a)

where $A\in\mathbb{C}^{n\times n}$ and $Q>0$ (or $Q\geq 0$). Assume that there
exists a solution $X\in\mathbb{P}_{n}$ solving (6a).

  2. 2.

Let the Stein matrix equation with sign “+” be defined by

$\displaystyle X+A^{\ast}XA=Q,$ (6b)

where $A\in\mathbb{C}^{n\times n}$ and $Q>0$. Assume that $Q>A^{\ast}QA$ (or
$Q\geq A^{\ast}QA$) and there exists a solution $X\in\mathbb{P}_{n}$ solving
(6b).

###### Proof.

Part 1 is a direct consequence of Lemma 2.2. Concerning part 2, let $X>0$ be a
solution of Eq. (6b), then $X-(A^{\ast})^{2}XA^{2}=Q-A^{\ast}QA{>0\ (\geq
0)}$, the proof is completed by applying Lemma 2.2. ∎

The following simple result is useful, which is used to obtain the main
result.

######  Lemma 2.3.

Let $J$ be the Jordan canonical matrix with size $n\times n$. If $\rho(J)\geq
1$ and $S_{J}(X_{\rm p})\geq 0$ for some $X_{\rm p}\geq 0$, then, we have the
following statements:

  1. 1.

$S_{J}(X_{\rm p})=0$. In other words, $S_{J}(N_{n})\cap N_{n}=0_{n}$.

  2. 2.

$X_{\rm p}=0$ if $\rho(J)>1$ and $X_{\rm p}=xe_{n}e_{n}^{\top}$ if
$\rho(J)=1$, where $x\geq 0$.

###### Proof.

For the sake of simplicity, the notation $[A]_{i,j}$ denotes $(i,j)$ entry of
a matrix $A\in\mathbb{C}^{m\times m}$ for $1\leq i,j\leq m$. For any positive
semidefinite matrix $A$, it is clear that some diagonal entry $[A]_{i,i}=0$ if
and only if the row and the column containing $[A]_{i,i}$ consist entirely of
0.

According to the assumption, we write $J=aI_{n}+N$, where $|a|\geq 1$ and $N$
is a $n\times n$ nilpotent matrix. Let $Y_{\rm p}=S_{J}(X_{\rm p})=X_{\rm
p}-J^{\ast}X_{\rm p}J$. In the case of $|a|>1$, we have $0\leq[Y_{\rm
p}]_{1,1}=[X_{\rm p}]_{1,1}-|a|^{2}e_{1}^{\top}X_{\rm p}e_{1}\leq 0$ and thus
$0=[Y_{\rm p}]_{1,1}=[X_{\rm p}]_{1,1}$. If $|a|=1$, it is immediate that
$[Y_{\rm p}]_{1,1}=[X_{\rm p}]_{1,1}-e_{1}^{\top}X_{\rm p}e_{1}=0$. Since
$Y_{\rm p}\geq 0$, we have $[Y_{p}]_{1,j}=[Y_{\rm p}]_{j,1}=0$ for
$j=2,\ldots,n$. so that, $0=[Y_{\rm p}]_{1,2}=[X_{\rm
p}]_{1,2}-(\bar{a}e_{1}^{\top})X_{\rm p}(e_{1}+ae_{2})=-\bar{a}[X_{\rm
p}]_{1,1}$. It follows that $[X_{\rm p}]_{1,1}=0$ and thus $[X_{\rm
p}]_{1,j}=[X_{\rm p}]_{j,1}=0$ for $1\leq j\leq n$.

For $2\leq k\leq n-1$, we observe that

$\displaystyle[Y_{\rm p}]_{k,k+1}$ $\displaystyle=(1-|a|^{2})[X_{\rm
p}]_{k,k+1}-([X_{\rm p}]_{k-1,k}+\bar{a}[X_{\rm p}]_{k,k}+a[X_{\rm
p}]_{k-1,k+1}),$ (7a) $\displaystyle[Y_{\rm p}]_{k,k}$
$\displaystyle=(1-|a|^{2})[X_{\rm p}]_{k,k}-([X_{\rm
p}]_{k-1,k-1}+2\mbox{Re}(a[X_{\rm p}]_{k-1,k})).$ (7b)

Note that (7b) also holds for $k=n$. Let $k=2$ and $|a|=1$. Substituting
$[X_{\rm p}]_{1,1}=[X_{\rm p}]_{1,2}=0$ into (7b) yields $[Y_{\rm p}]_{2,2}=0$
so that $[Y_{p}]_{2,j}=[Y_{p}]_{j,2}=0$ for $1\leq j\leq n$. Substituting
$[Y_{\rm p}]_{2,3}=[X_{\rm p}]_{1,2}=[X_{\rm p}]_{1,3}=0$ into (7a) yields
$[X_{\rm p}]_{2,2}=0$. Repeat this procedure we have $[X_{\rm
p}]_{k,k}=[Y_{\rm p}]_{k,k}=0$ for $1\leq k\leq n-1$. Hence, $X_{\rm
p}=0\oplus[X_{\rm p}]_{n,n}\geq 0$ and $Y_{\rm p}=0$.

On the other hand, let $k=2$ and $|a|>1$. Substituting $[X_{\rm
p}]_{1,1}=[X_{\rm p}]_{1,2}=0$ into (7b) we have $0\leq[Y_{\rm
p}]_{2,2}=(1-|a|^{2})[X_{\rm p}]_{2,2}$ so that $[Y_{\rm p}]_{2,2}=[X_{\rm
p}]_{2,2}=0$. Repeating the procedure on $k$, we obtain $[Y_{\rm
p}]_{k,k}=[X_{\rm p}]_{k,k}=0$ for $k>2$. Hence, $X_{\rm p}=Y_{\rm p}=0$. ∎

##  3 Main results on the DARE

To make our main results more clearly and explicitly, the rest of the section
is divided into two parts, respectively: One is the sufficient condition for
the existence of extreme solutions of DARE and the other is new convergence
results to a fixed point iteration $X_{k+1}=R_{\rm d}(X_{k})$.

###  3.1 New results on the extreme solutions of DARE

First of all, we consider the extreme solutions of DARE (1). Inspired by the
results of Theorem 2.1, we introduce two subsets on $\mathbb{N}_{n}$:

$\displaystyle\mathbb{R}_{\geq}:=\\{X\in\mathbb{N}_{n}|X\geq R_{\rm
d}(X)\\},\,\mathbb{R}_{\leq}:=\\{X\in\mathbb{N}_{n}|X\leq R_{\rm d}(X)\\}.$

Then we have the following result concerning the existence of minimal and
maximal positive semidefinite solutions of Eq. (1).

######  Lemma 3.1.

Let $\mathbb{S}_{\geq}:=\\{X\in\mathbb{N}_{n}|S_{A}(X)\geq H\\}$ and
$\mathbb{S}_{\leq}:=\\{X\in\mathbb{N}_{n}|S_{A}(X)\leq H\\}$. Consider the
fixed-point iteration $X_{k+1}=R_{\rm d}(X_{k})$ with an initial $X_{1}$. Then
we have the following statements:

  1. 1.

Assume that $\mathbb{R}_{\geq}\neq\phi$ and let $X_{1}\in[0,H]$. Then, the
sequence $\\{X_{k}\\}$ converges increasingly to the minimal positive
semidefinite solution of Eq. (1).

  2. 2.

Assume that $\mathbb{S}_{\geq}\neq\phi$ and let $X_{1}\in\mathbb{S}_{\geq}$,
then the sequence $\\{X_{k}\\}$ converges decreasingly to a positive
semidefinite solution of Eq. (1).

  3. 3.

Assume that $\rho(A)<1$. Then, $\mathbb{S}_{\geq}\neq\phi$ and the sequence
$\\{X_{k}\\}$ with $X_{1}\in\mathbb{S}_{\geq}$ converges decreasingly to the
maximal positive semidefinite solution of Eq. (1).

###### Proof.

Applying the Woodbury identity, we have $X(I+GX)^{-1}=X-XG(I+XG)^{-1}X$, it is
then easily seen that $X-R_{\rm d}(X)=S_{A}(X)-H+A^{\ast}XG(I+XG)^{-1}XA$,
from which we know $\mathbb{S}_{\geq}\subseteq\mathbb{R}_{\geq}$ and
$\mathbb{R}_{\leq}\subseteq\mathbb{S}_{\leq}$.

For part 1, observe that $X_{1}\in\mathbb{R}_{\leq}$ and $X_{1}\leq H\leq X$
for any $X\in\mathbb{R}_{\geq}$, this implies that $X_{1}\in\mathbb{R}_{\leq}$
is a lower bound of $\mathbb{R}_{\geq}$. It follows from Theorem 2.1 that the
sequence $\\{X_{k}\\}$ is monotonically increasing and converges to the
minimal positive semidefinite solution of Eq. (1).

Concerning part 2, it follows from $X_{1}\in\mathbb{S}_{\geq}$ that
$X_{1}\in\mathbb{R}_{\geq}$, so that $X_{1}\geq H$. Analogous to Theorem 2.1,
one can prove that the sequence $\\{X_{k}\\}$ is monotonically decreasing and
converges to a positive definite solution of Eq. (1).

For part 3, observe that for any $X\in\mathbb{R}_{\leq}$ we have
$X\in\mathbb{S}_{\leq}$, which yields $S_{A}(X_{1})\geq H\geq S_{A}(X)$, the
first inequality holds since $X_{1}\in\mathbb{S}_{\geq}$. Hence, $X_{1}\geq X$
since $\rho(A)<1$. That is, $X_{1}\in\mathbb{R}_{\geq}$ is an upper bound of
$\mathbb{R}_{\leq}$, which, together with part (1d) of Theorem 2.1, shows that
the sequence $\\{X_{k}\\}$ with $X_{1}\in\mathbb{S}_{\geq}$ converges
decreasingly to the maximal positive semidefinite solution of Eq. (1). ∎

We also notice that the proof of the final part of Lemma 3.1 was motivated by
[6][Theorem 5.1]. It seems that the assumption $\mathbb{R}_{\geq}\neq\phi$ is
not easy to check. An useful sufficient condition on the coefficient matrices
for the existence of the positive semidefinite solution of Eq.(1) can be
written as follows.

######  Corollary 3.1.

Assume that the matrices $A\in\mathbb{C}^{n\times n}$, $G\in\mathbb{N}_{n}$
and $H\in\mathbb{N}_{n}$ satisfy one of the following two conditions:

  1. 1.

$G$ is nonsingular, i.e., $G>0$.

  2. 2.

$G$ is singular and $\rho(A^{\ast}A)\leq 1$.

Then, there exists a positive semidefinite solution to (1) and thus
$\mathbb{R}_{\geq}\neq\phi$.

###### Proof.

Let $h=\max\limits_{\lambda\in\sigma(H)}\lambda=\rho(H)$,
$g=\min\limits_{\lambda\in\sigma(G)}\lambda$ and
$a=\max\limits_{\lambda\in\sigma(A^{\ast}A)}\lambda=\|A\|_{2}^{2}$. It can be
shown that the quadratic inequality

$gx^{2}+(1-a-hg)x-h\geq 0$

has a nonnegative solution $x_{c}$ if $g\neq 0$ or $g=0$ and $a<1$. In each
assumption we have

$x_{c}I_{n}\geq(h+\frac{ax_{c}}{1+gx_{c}})I_{n}\geq R_{\rm d}(x_{c}I_{n}).$

Thus, $\mathbb{R}_{\geq}$ is nonempty. From Theorem 3.2, there exists a
positive semidefinite solution of (1).

∎

By the way, we are concerned with the (almost) stabilizing solution based on
the following observation. Let $X\in\mathbb{R}_{\geq}$, then we have

$\displaystyle X-(T_{X})^{\ast}XT_{X}$ $\displaystyle\geq
H+(T_{X})^{\ast}(X+XGX)T_{X}-(T_{X})^{\ast}XT_{X}$
$\displaystyle=H+(T_{X})^{\ast}XGXT_{X}\geq 0.$

In view of part 2 of Lemma 2.2, we know that $\rho(T_{X})\leq 1$ and ${\rm
ind}_{\lambda}(T_{X})=1$ for all
$\lambda\in\sigma(A)\cap\mbox{bd}(\mathbb{D})$ if and only if $X>0$. Moreover,
$\rho(T_{X})<1$ if $H>0$. The above conclusion is summarized as follows.

######  Theorem 3.1.

Under the typical assumption that $H\geq 0$ and $G\geq 0$, any positive
definite solution $X$ of (1) is an almost stabilizing solution. Furthermore,
$X$ is a stabilizing solution if $H>0$.

###  3.2 New results on the convergence of a fixed point iteration

In this subsection, combine Lemma 2.3, and Lemma 3.3, we will now examine the
convergence behaviour of the fixed-point iteration $X_{k+1}=R_{\rm d}(X_{k})$
with $X_{1}=H$. Assume that $\mathbb{R}_{\geq}\neq\phi$. From Lemma 3.1 we
know that $\\{X_{k}\\}$ converges to the minimal positive semidefinite
solution $X_{\star}$.

Our main result includes the convergence in the case where
$\rho(T_{X_{\star}})\geq 1$, so that generalizes the previous result in [8],
where only the convergence in the case where $\rho(T_{X_{\star}})<1$ is
considered. The concepts of convergence speed of fixed-point iteration for
solving DARE (1) are related by the following result; see e.g.,
[12][Appendix].

######  Lemma 3.2.

Let $Z_{k+1}=R_{\rm d}(Z_{k})$ be the fixed point iteration of (1) with an
initial matrix $Z_{1}$. If $Z_{k}$ converges to $Z_{\star}$, then

$\limsup\limits_{k\rightarrow\infty}\sqrt[k]{\|{Z}_{\star}-{Z}_{k}\|}\leq\rho(T_{Z_{\star}})^{2}.$

Lemma 3.2 shows that the fixed-point iteration works well if
$\rho(T_{Z_{\star}})<1$, while the efficiency for the case where
$\rho(T_{Z_{\star}})\geq 1$ is difficult to tell. The aims of this subsection
is to verity the R-linear convergence of $\\{X_{k}\\}$ under the case that
$\rho(T_{X_{\star}})<1$.

Before proceeding with the main result of this section, we also require the
following lemma, which is the original DARE divided into three DAREs with
small scale.

######  Lemma 3.3.

Assume that there exists a matrix $X_{+}\in\mathbb{R}_{\geq}$. Let
$J_{T_{X_{+}}}=P^{-1}T_{X_{+}}P$ be the Jordan canonical form of $T_{X_{+}}$.
Suppose that $J_{T_{X_{+}}}=J_{1}\oplus J_{u}\oplus J_{s}$, where
$J_{1}\in\mathbb{C}^{m_{1}\times m_{1}}$ with $\sigma(J_{1})\subseteq{\rm
bd}(\mathbb{D})$, $J_{u}\in\mathbb{C}^{m_{2}\times m_{2}}$ with
$\sigma(J_{u})\cap\bar{\mathbb{D}}=\phi$ and $J_{s}\in\mathbb{C}^{m_{3}\times
m_{3}}$ with $\sigma(J_{s})\subseteq\mathbb{D}$. Namely, $|\lambda|=1$ for all
$\lambda\in\sigma(J_{1})$, $\rho(J_{u}^{-1})<1$ and $\rho(J_{s})<1$. Then, we
have the following statements:

  * (a)

We have nullity$(H)\geq m_{1}+m_{2}$. Furthermore, $H$ is congruent to a block
diagonal matrix $0_{m_{1}+m_{2}}\oplus\widehat{H}_{s}$, where
$\widehat{H}_{s}\in\mathbb{C}^{m_{3}\times m_{3}}$.

  * (b)

Suppose that $X_{+}=R_{\rm d}(X_{+})$. Then, $X_{+}$ is congruent to the block
diagonal matrix $X_{+,1}\oplus X_{+,u}\oplus X_{+,s}$, where $X_{+,1}$,
$X_{+,u}$ and $X_{+,s}$ are respectively positive semidefinite solution of
DARE: $X=R_{\rm d,1}(X)$, $X=R_{\rm d,u}(X)$ and $X=R_{\rm d,s}(X)$.
Furthermore, $T_{X_{+,1}}=J_{1}$, $T_{X_{+,u}}=J_{u}$ and $T_{X_{+,s}}=J_{s}$.

###### Proof.

Let $Y_{+}=P^{\ast}X_{+}P$, $\widehat{A}=P^{-1}AP$,
$\widehat{G}=P^{-1}GP^{-\ast}\geq 0$, and $\widehat{H}=P^{\ast}HP\geq 0$. Note
that $n=m_{1}+m_{2}+m_{3}$. For the sake of convenience, we partition any
$\mathcal{A}\in\mathbb{C}^{n\times n}$ as a $3\times 3$ block matrix
$\mathcal{A}=[[\mathcal{A}]_{i,j}]$, where
$[\mathcal{A}]_{i,j}\in\mathbb{C}^{m_{i}\times m_{j}}$ and $1\leq i,j\leq 3$.
The notation $[\mathcal{A}]_{[i_{1},i_{2}]\times[j_{1},j_{2}]}$ denotes the
block submatrix of $\mathcal{A}$ consisting of the
$i_{1},i_{1}+1,\ldots,i_{2}$ rows and the $j_{1},j_{1}+1,\ldots,j_{2}$
columns. We use $[\mathcal{A}]_{[i_{1},i_{2}]}$ for short if $i_{1}=j_{1}$ and
$i_{2}=j_{2}$. As a consequence,
$[\mathcal{A}]_{i,i}=[\mathcal{A}]_{[i,i]}\geq 0$ if $\mathcal{A}\geq 0$ for
$i=1,2,3$.

Concerning part (a), the inequality $X_{+}\geq R_{\rm d}(X_{+})$ is equivalent
to the inequality

$\displaystyle
Y_{+}\geq\widehat{H}+J_{T_{X_{+}}}^{\ast}Y_{+}J_{T_{X_{+}}}+J_{T_{X_{+}}}^{\ast}\widehat{G}_{Y_{+}}J_{T_{X_{+}}},$
(8)

where $\widehat{G}_{Y_{+}}{=}Y_{+}\widehat{G}Y_{+}$. A direct computation of
the upper left corner $(m_{1}+m_{2})\times(m_{1}+m_{2})$ block of (8) yields

$\displaystyle[Y_{+}]_{[1,2]}-(J_{1}\oplus
J_{u})^{\ast}[Y_{+}]_{[1,2]}(J_{1}\oplus J_{u})$
$\displaystyle\geq[\widehat{H}]_{[1,2]}+(J_{1}\oplus
J_{u})^{\ast}[\widehat{G}_{Y_{+}}]_{[1,2]}(J_{1}\oplus J_{u})\geq 0.$

From Lemma 2.3 we have

$\displaystyle[Y_{+}]_{[1,2]}=(J_{1}\oplus
J_{u})^{\ast}[Y_{+}]_{[1,2]}(J_{1}\oplus J_{u}),$ (9)

and thus $[\widehat{H}]_{[1,2]}+(J_{1}\oplus
J_{u})^{\ast}[\widehat{G}_{Y_{+}}]_{[1,2]}(J_{1}\oplus J_{u})=0$, from which
we deduce that $[\widehat{H}]_{[1,2]}$ and $[\widehat{G}_{Y_{+}}]_{[1,2]}$ are
null, and we obtian

$\displaystyle\widehat{H}=\begin{bmatrix}0_{m_{1}+m_{2}}&0\\\
0&[\widehat{H}]_{3,3}\\\ \end{bmatrix},\
\widehat{G}_{Y_{+}}=\begin{bmatrix}0_{m_{1}+m_{2}}&0\\\
0&[\widehat{G}_{Y_{+}}]_{3,3}\\\ \end{bmatrix}.$ (10)

Concerning part (b), observe that the original DARE (1) with respect to the
unknown $X$ is equivalent to the following equation with respect to the
unknown $Y=P^{\ast}XP$,

$\displaystyle
Y=\widehat{H}+J_{T_{X}}^{\ast}YJ_{T_{X}}+J_{T_{X}}^{\ast}\widehat{G}_{Y}J_{T_{X}}.$
(11)

We claim that Eq. (11) has a positive semidefinite solution ${Y}_{+}$ such
that ${Y}_{+}=[{Y}_{+}]_{1,1}\oplus[{Y}_{+}]_{2,2}\oplus[{Y}_{+}]_{3,3}$ if
there exists a $X_{+}\geq 0$ such that $R_{\rm d}(X_{+})=X_{+}$, where
${[Y_{+}]}_{1,1}\in\mathbb{N}_{m_{1}}$, ${[Y_{+}]}_{2,2}\in\mathbb{N}_{m_{2}}$
and ${[Y_{+}]}_{[3,3]}\in\mathbb{N}_{m_{3}}$. Indeed, substituting (10) into
(11) we have
${[Y_{+}]}_{[1]\times[2,3]}=J_{1}^{\ast}{[Y_{+}]}_{[1]\times[2,3]}(J_{u}\oplus
J_{s})$, which implies
${[Y_{+}]}_{[1]\times[2,3]}=({[Y_{+}]}_{[2,3]\times[1]})^{\ast}=0$ since
$\bar{\lambda}\mu\neq 1$ for any $\lambda\in\sigma(J_{1})$ and
$\mu\in\sigma(J_{u}\oplus J_{s})$. Combining these with (9) we can assert that
$[Y_{+}]_{1,1}=J_{1}^{\ast}[Y_{+}]_{1,1}J_{1}$ and
$[Y_{+}]_{2,2}=J_{u}^{\ast}[Y_{+}]_{2,2}J_{u}$. From Lemma 2.3 it follows
easily immediately that $[Y_{+}]_{2,2}=0$ since $\rho(J_{u}^{-1})<1$. We
conclude that $Y_{+}$ is a block diagonal matrix.

On the other hand, since

$\displaystyle 0$
$\displaystyle=[\widehat{G}_{Y_{+}}]_{1,1}=[Y_{+}\widehat{G}Y_{+}]_{1,1}=[(\widehat{G}^{1/2}Y_{+})^{\ast}(\widehat{G}^{1/2}Y_{+})]_{1,1}$
$\displaystyle=[(\widehat{G}^{1/2}Y_{+})^{\ast}]_{1,1}[\widehat{G}^{1/2}Y_{+}]_{1,1}+{[\widehat{G}^{1/2}Y_{+}]_{[2,3]\times[1]}^{\ast}}[\widehat{G}^{1/2}Y_{+}]_{[2,3]\times[1]}\geq
0,$

it follows that
$[\widehat{G}^{1/2}]_{1,1}[Y_{+}]_{1,1}=[\widehat{G}^{1/2}Y_{+}]_{1,1}=0$ and
$[\widehat{G}^{1/2}]_{[2,3]\times[1]}[Y_{+}]_{1,1}=[\widehat{G}^{1/2}Y_{+}]_{[2,3]\times[1]}=0$.
Thus, we see that

$\displaystyle[\widehat{G}]_{1,1}[Y_{+}]_{1,1}$
$\displaystyle=(([\widehat{G}^{1/2}]_{1,1})^{2}+[\widehat{G}^{1/2}]_{[1]\times[2,3]}[\widehat{G}^{1/2}]_{[2,3]\times[1]})[Y_{+}]_{1,1}=0,$
(12a) $\displaystyle[\widehat{G}]_{[2,3]\times[1]}[Y_{+}]_{1,1}$
$\displaystyle=([\widehat{G}^{1/2}]_{[2,3]\times[1]}[\widehat{G}^{1/2}]_{1,1}+[\widehat{G}^{1/2}]_{[2,3]\times[2,3]}[\widehat{G}^{1/2}]_{[2,3]\times[1]})[Y_{+}]_{1,1}=0.$
(12b)

It implies that the matrix $\widehat{G}Y_{+}$ can be partitioned according to
the block structure

$\displaystyle\widehat{G}Y_{+}$
$\displaystyle=\begin{bmatrix}[\widehat{G}]_{1,1}[Y_{+}]_{1,1}&[\widehat{G}]_{[1]\times[2,3]}[Y_{+}]_{[2,3]}\\\
[\widehat{G}]_{[2,3]\times[1]}[Y_{+}]_{1,1}&[\widehat{G}]_{[2,3]}[Y_{+}]_{[2,3]}\\\
\end{bmatrix}$
$\displaystyle=\begin{bmatrix}0_{m_{1}}&[\widehat{G}]_{[1]\times[2,3]}[Y_{+}]_{[2,3]}\\\
0_{(m_{2}+m_{3})\times m_{1}}&[\widehat{G}]_{[2,3]}[Y_{+}]_{[2,3]}\\\
\end{bmatrix}=\begin{bmatrix}0_{m_{1}}&0_{m_{1}\times
m_{2}}&[\widehat{G}]_{1,3}[Y_{+}]_{[3,3]}\\\ 0_{m_{2}\times
m_{1}}&0_{m_{2}}&[\widehat{G}]_{2,3}[Y_{+}]_{[3,3]}\\\ 0_{m_{3}\times
m_{1}}&0_{m_{3}\times m_{2}}&[\widehat{G}]_{3,3}[Y_{+}]_{[3,3]}\end{bmatrix}.$

It follows that

$\displaystyle(I_{n}+\widehat{G}Y_{+})^{-1}=\begin{bmatrix}I_{m_{1}}&0_{m_{1}\times
m_{2}}&-[\widehat{G}]_{1,3}[Y_{+}]_{[3,3]}(I_{m_{3}}+[\widehat{G}]_{3,3}[Y_{+}]_{3,3})^{-1}\\\
0_{m_{2}\times
m_{1}}&I_{m_{2}}&-[\widehat{G}]_{2,3}[Y_{+}]_{[3,3]}(I_{m_{3}}+[\widehat{G}]_{3,3}[Y_{+}]_{3,3})^{-1}\\\
0_{m_{3}\times m_{1}}&0_{m_{3}\times
m_{2}}&(I_{m_{3}}+[\widehat{G}]_{3,3}[Y_{+}]_{3,3})^{-1}\end{bmatrix}.$

Observe that

$\displaystyle J_{{T_{X_{+}}}}=J_{1}\oplus J_{u}\oplus J_{s}$
$\displaystyle=P^{-1}(I+GX_{+})^{-1}AP=(I_{n}+\widehat{G}Y_{+})^{-1}\widehat{A},$
(13)

Compared the $(3,1)$ and $(3,2)$ positions with two sides of (13), we obtain

$\displaystyle(I_{m_{3}}+[\widehat{G}]_{3,3}[Y_{+}]_{3,3})^{-1}[\widehat{A}]_{[3]\times[1,2]}$
$\displaystyle=0_{m_{3}\times(m_{1}+m_{2})},$

and we deduce that
$[\widehat{A}]_{[3]\times[1,2]}=0_{m_{3}\times(m_{1}+m_{2})}$. Similarly,
compared the $(2,1)$ and $(1,2)$ positions with two sides of (13) immediately
lead to $[\widehat{A}]_{[1,2]}=0_{m_{1}\times m_{2}}$ and
$[\widehat{A}]_{[2,1]}=0_{m_{2}\times m_{1}}$. That is, $\widehat{A}$ is an
upper triangular block matrix. Comparing block matrices $(1,1)$, $(2,2)$ and
$(3,3)$ of two sides of (13) yields

$\displaystyle
J_{1}=[\widehat{A}]_{1,1},\,J_{u}=[\widehat{A}]_{2,2},\,J_{s}=(I_{m_{3}}+[\widehat{G}]_{3,3}[Y_{+}]_{3,3})^{-1}[\widehat{A}]_{3,3}.$
(14)

Let

$\displaystyle R_{\rm d,1}([Y_{+}]_{1,1})$
$\displaystyle:=[\widehat{H}]_{1,1}+([\widehat{A}]_{1,1})^{\ast}[Y_{+}]_{1,1}(I_{m_{1}}+[\widehat{G}]_{1,1}[Y_{+}]_{1,1})^{-1}[\widehat{A}]_{1,1},$
$\displaystyle R_{\rm d,u}([Y_{+}]_{2,2})$
$\displaystyle:=[\widehat{H}]_{2,2}+([\widehat{A}]_{2,2})^{\ast}[Y_{+}]_{2,2}(I_{m_{3}}+[\widehat{G}]_{2,2}[Y_{+}]_{2,2})^{-1}[\widehat{A}]_{2,2},$
$\displaystyle R_{\rm d,s}([Y_{+}]_{3,3})$
$\displaystyle:=[\widehat{H}]_{3,3}+([\widehat{A}]_{3,3})^{\ast}[Y_{+}]_{3,3}(I_{m_{3}}+[\widehat{G}]_{3,3}[Y_{+}]_{3,3})^{-1}[\widehat{A}]_{3,3}.$

Summarizing, together with $[\widehat{H}]_{[1,2]}=0_{m_{1}+m_{2}}$,
$[Y_{+}]_{2,2}=0_{m_{2}}$, (12a), (11) and (14) we can now formulate our main
results in part (b):

$\displaystyle[Y_{+}]_{1,1}$
$\displaystyle=J_{1}^{\ast}[Y_{+}]_{1,1}J_{1}=R_{\rm d,1}([Y_{+}]_{1,1}),$
$\displaystyle[Y_{+}]_{2,2}$
$\displaystyle=J_{u}^{\ast}[Y_{+}]_{2,2}J_{u}=R_{\rm d,u}([Y_{+}]_{2,2}),$
$\displaystyle[Y_{+}]_{3,3}$
$\displaystyle=[\widehat{H}]_{3,3}+J_{s}^{\ast}[Y_{+}]_{3,3}(I_{m_{3}}+[\widehat{G}]_{3,3}[Y_{+}]_{3,3})J_{s}=R_{\rm
d,s}([Y_{+}]_{3,3}),$

with $T_{[Y_{+}]_{1,1}}=J_{1}$, $T_{[Y_{+}]_{2,2}}=J_{u}$ and
$T_{[Y_{+}]_{3,3}}=J_{s}$.

∎

Now, we are ready to present the main result of this subsection. The following
theorem gives a sharper bound on the convergent speed of the fixed point
iteration, which works both for the regular case and the critical case.

######  Theorem 3.2.

Assume that $\mathbb{R}_{\geq}\neq\phi$ and $H\neq 0$. Then, the sequence
$X_{k+1}=R_{\rm d}(X_{k})$ with an initial matrix $X_{1}=H$ converges
R-linearly to the minimal positive semidefinite solution $X_{\star}$ of (1).
Moreover, the convergence rate can be shown as the following:

$\underset{k\rightarrow\infty}{\lim{\rm
sup}}\sqrt[k]{\|X_{k}-X_{\star}\|}\leq\max\\{|\lambda|^{2};\lambda\in\sigma(T_{{X}_{\star}})\cap{\mathbb{D}}\\}<1.$

Note that the $X_{\star}=X_{k}=0$ for all $k\geq 1$ and
$\rho(T_{{X}_{\star}})=\rho(A)$ when $H=0$.

###### Proof.

In view of part 1 of Lemma 3.1, the sequence $\\{X_{k}\\}$ converges to the
minimal positive semidefinite solution of equation (1). It is left to prove
that the convergence is R-linear. Let $T_{X_{\star}}=PJ_{T_{X_{\star}}}P^{-1}$
be the Jordan canonical decomposition of $T_{X_{\star}}=(I+GX_{\star})^{-1}A$.
Set $\widehat{X}_{k}=P^{\ast}X_{k}P$, we have

$\displaystyle\widehat{X}_{k+1}=\widehat{H}+\widehat{A}^{\ast}\widehat{X}_{k}(I+\widehat{G}\widehat{X}_{k})^{-1}\widehat{A}.$
(15)

Together with $\widehat{X}_{1}=\widehat{H}=0_{m_{1}+m_{2}}\oplus[H]_{3,3}$, we
derive that the sequence
$\widehat{X}_{k}=\widehat{X}_{k,1}\oplus\widehat{X}_{k,u}\oplus\widehat{X}_{k,s}$
is divided three sequences according to

$\displaystyle\widehat{X}_{k+1,1}$ $\displaystyle=R_{\rm
1}(X_{k,1})=[\widehat{H}]_{1,1}+[\widehat{A}]_{1,1}^{\ast}\widehat{X}_{k,1}(I_{m_{1}}+[\widehat{G}]_{1,1}\widehat{X}_{k,1})^{-1}[\widehat{A}]_{1,1},$
$\displaystyle\widehat{X}_{k+1,u}$ $\displaystyle=R_{\rm
u}(X_{k,u})=[\widehat{H}]_{2,2}+[\widehat{A}]_{2,2}^{\ast}\widehat{X}_{k,u}(I_{m_{2}}+[\widehat{G}]_{2,2}\widehat{X}_{k,u})^{-1}[\widehat{A}]_{2,2},$
$\displaystyle\widehat{X}_{k+1,s}$ $\displaystyle=R_{\rm
s}(X_{k,s})=[\widehat{H}]_{3,3}+[\widehat{A}]_{3,3}^{\ast}\widehat{X}_{k,s}(I_{m_{3}}+[\widehat{G}]_{2,2}\widehat{X}_{k,s})^{-1}[\widehat{A}]_{3,3}.$

The conditions $\widehat{X}_{1,1}=[\widehat{H}]_{1,1}=0$ and
$\widehat{X}_{1,u}=[\widehat{H}]_{1,1}=0$ implies that $\widehat{X}_{k,1}=0$
and $\widehat{X}_{k,u}=0$ for all positive integers $k$. By the way,
$\widehat{X}_{k}=\widehat{X}_{k,1}=0$ if $H=0$.

Let $H$ be a nonzero positive semidefinite matrix. Under the hypotheses of
Lemma 3.3, there exists a positive definite solution $\widehat{X}_{\star,s}$
of DARE $X=R_{\rm d,s}(X)$ and $\rho(T_{\widehat{X}_{\star,s}})<1$. Overall,
let
$X_{\star}=P^{-H}(\lim\limits_{k\rightarrow\infty}\widehat{X}_{k})P^{-1}=P^{-H}(0\oplus\widehat{X}_{\star,s})P^{-1}$.
Applying Lemma 3.2 we have

$\displaystyle\underset{k\rightarrow\infty}{\lim{\rm
sup}}\sqrt[k]{\|X_{k}-X_{\star}|}$
$\displaystyle=\underset{k\rightarrow\infty}{\lim{\rm
sup}}\sqrt[k]{\|P^{-H}(0\oplus\widehat{X}_{k,s}-0\oplus\widehat{X}_{\star,s})P^{-1}\|}$
$\displaystyle\leq\rho(T_{\widehat{X}_{\star,s}})=\max\\{|\lambda|^{2};\lambda\in\sigma(T_{{X}_{\star}})\cap{\mathbb{D}}\\}.$

∎

######  Remark 3.1.

Let $n=1$, $G>0$ and $H=0$. Namely, Eq. (1) has two positive semidefinite
solutions $X_{1}=0$ with $T_{X_{1}}=A$ and $X_{2}=\frac{|A|^{2}-1}{G}$ with
$T_{X_{2}}=\frac{1}{|A|}$. In this case, $X_{k}=X_{1}=H=0$ for all $k$ and
$\rho(T_{X_{\star}})=|A|$ can be made arbitrarily large.

The following result provides a sufficient condition under which the sequence
$\\{X_{k}\\}$ converges $R$-linearly.

######  Corollary 3.2.

Assume that there exists a positive definite solution $X=X_{+}$ of (1). Then,
$X_{k}$ converges R-linearly to the minimal positive semidefinite solution
$X_{\star}$ of Eq.(1) such that $T_{X_{\star}}$ is discrete-time Lyapunov
stable.

###### Proof.

Suppose that there exists $X_{+}>0$ such that $X_{+}\in\mathbb{R}_{\geq}$.
Observe that $S_{A}(X_{+})=H+T_{X_{+}}^{\ast}X_{+}GX_{+}T_{X_{+}}\geq 0$. From
Lemma 2.2 we know that $\rho(T_{X_{+}})\leq 1$ and all the unimodular
eigenvalues are semisimple. Consequently, $\mathbb{R}_{\geq}\neq\phi$ and thus
$X_{+}$ converges to $X_{\star}$ R-linearly by Theorem 3.2. ∎

##  4 An accelerated iteration and numerical experiments

In this section, for any integer $r>1$, we first show that an accelerated of
fixed-point iteration (referred as AFPI) with R-superlinear convergence order
$r$ is capable of computing the minimal positive semidefinite solution of
equation (1). It has been proved in [13, 3] that if $\rho(T_{X_{\star}})<1$
the AFPI has convergence rate of any desired order $r$. We verify that the
convergence speed remains invariant even $\rho(T_{X_{\star}})\geq 1$. It is
worth mentioning that AFPI includes SDA as a special $r=2$ case [13], so that
the quadratic convergence of SDA when $\rho(T_{X_{\star}})\geq 1$ still holds
and this acts as a complementary to the existing results on the convergence of
SDA.

Two numerical examples are then demonstrated to test the accuracy of the
computation and the convergence speed of AFPI under different situation; the
first one show that the proposed algorithm converges suplinearly with no
difficulty in the value of $\rho{(T_{X_{\star}})}$ less than, greater than, or
equal to 1, respectively. The latter example comes from [9] which consider a
DARE (1) with a negative definite matrix $H$. It is interesting to observe
that our approach is still valid.

###  4.1 Acceleration of fixed-point iteration

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

######  Definition 4.1.

[13] Let $D\subseteq\mathbb{C}^{n\times m}$ and $F:D\times D\rightarrow D$ be
a binary matrix operator. We call that an iteration

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

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

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

for any $Y,Z$ and $W$ in $D$.

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

$\displaystyle{\mathbb{X}}_{k+\ell}=F({\mathbb{X}}_{k},{\mathbb{X}}_{\ell}),$
(18)

for any two positive integers $k$ and $\ell$. Now, we construct a fixed point
iteration that has the semigroup property so that the fixed point iteration
can be accelerated by applying the procedure as in [13][Algorithm 3.1]. To
this end, we have

$\displaystyle X=R_{\rm d}^{(k)}(R_{\rm d}(X))=R_{\rm
d}^{(k+1)}(X)=H_{k+1}+A_{k+1}^{\ast}{X}(I+G_{k+1}{X})^{-1}A_{k+1},$

$A_{k}$, $G_{k}$, and $H_{k}$, for $k=1,2,\ldots$, are matrices given by the
following iteration

$\displaystyle\begin{bmatrix}A_{k+1}\\\ G_{k+1}\\\
H_{k+1}\end{bmatrix}=F(\begin{bmatrix}A_{k}\\\ G_{k}\\\
H_{k}\end{bmatrix}):=\begin{bmatrix}A_{1}\Delta_{G_{k},{H_{1}}}A_{k}\\\
G_{1}+A_{1}\Delta_{G_{k},{H_{1}}}G_{k}A_{1}^{\ast}\\\
H_{k}+A_{k}^{\ast}H_{1}\Delta_{G_{k},{H_{1}}}A_{k}\end{bmatrix},$

where $G_{1}=G\geq 0$, $H_{1}=H\geq 0$, $A_{1}=A$, and
$\Delta_{G_{k},{H_{1}}}=I+G_{k}H_{1}$. An induction argument proves that
$G_{k}\geq 0$ and $H_{k}\geq 0$ and thus $I+G_{k}H_{1}$ is invertible.
Therefore, the sequence of matrices
$\mathbb{X}_{k}=\begin{bmatrix}A_{k}^{\top}&G_{k}^{\top}&H_{k}^{\top}\end{bmatrix}^{\top}$
generated by

$\displaystyle\mathbb{X}_{k+1}=F(\mathbb{X}_{k},\mathbb{X}_{1}),$ (19)

is well defined with
$\mathbb{X}_{1}=\begin{bmatrix}A_{1}^{\top}&G_{1}^{\top}&H_{1}^{\top}\end{bmatrix}^{\top}$
for $k\geq 1$.

Let $\mathbb{K}_{n}:=\mathbb{C}_{n}\times\mathbb{N}_{n}\times\mathbb{N}_{n}$.
We consider the mapping
$F:\mathbb{K}_{n}\times\mathbb{K}_{n}\rightarrow\mathbb{K}_{n}$ as an action
defined by

$\displaystyle F(Y,Z)=\begin{bmatrix}Z_{1}\Delta_{Y_{2},Z_{3}}Y_{1}\\\
Z_{2}+Z_{1}\Delta_{Y_{2},Z_{3}}Y_{2}Z_{1}^{\ast}\\\
Y_{3}+Y_{1}^{\ast}Z_{3}\Delta_{Y_{2},Z_{3}}Y_{1}\end{bmatrix},$ (20)

where
$Y=\begin{bmatrix}Y_{1}^{\top}&Y_{2}^{\top}&Y_{3}^{\top}\end{bmatrix}^{\top}$,
$Z=\begin{bmatrix}Z_{1}^{\top}&Z_{2}^{\top}&Z_{3}^{\top}\end{bmatrix}^{\top}\in\mathbb{K}_{n}$
and $\Delta_{Y_{2},Z_{3}}=(I+Y_{2}Z_{3})^{-1}$. Note that
$\Delta_{Y_{2},Z_{3}}$ is well defined since all eigenvalues of $I+Y_{2}Z_{3}$
are positive. It has been proved in [13, Example 4.4] that the binary operator
$F$ satisfies the associative rule (17) holds, that is, the iteration
$\mathbb{X}_{k+1}=F(\mathbb{X}_{k},\mathbb{X}_{1})$ has the semigroup
property. As a consequence,
${\mathbb{X}}_{k+1}=F(\mathbb{X}_{1},\mathbb{X}_{k})$ for any positive
integers $k$ and we deduce that

$H_{k+1}=H_{1}+A_{1}^{\ast}H_{k}\Delta_{G_{1},{H_{k}}}A_{1}.$

from which we see that the sequence $\\{H_{k}\\}$ coincides with the sequence
$\\{X_{k}\\}$ generated by the fixed point iteration $X_{k+1}=R_{\rm
d}(X_{k})$ since $X_{1}=H_{1}=H$. Applying the discrete flow property (18) to
the iteration (19) we obtain the following accelerated fixed point iteration
(AFPI).

######  Algorithm 4.1.

_(An accelerated of fixed-point iteration (AFPI) to solve DARE. ( 1))_

  1. 1.

Given a positive integer $r>1$, let
$\widehat{\mathbb{X}}_{1}={\mathbb{X}}_{1}=\begin{bmatrix}A_{1}^{\top}&G_{1}^{\top}&H_{1}^{\top}\end{bmatrix}^{\top}$;

  2. 2.

For $k=1,\ldots,$ iterate

$\displaystyle\widehat{\mathbb{X}}_{k+1}$
$\displaystyle=F(\widehat{\mathbb{X}}_{k},\mathbb{X}_{k}^{(r-1)}),$

until convergence, where $F$ is defined in (20) and $\mathbb{X}_{k}^{(r-1)}$
is defined in step 3.

  3. 3.

For $\ell=1,\ldots,r-2$, iterate

$\displaystyle\mathbb{X}_{k}^{(\ell+1)}$
$\displaystyle=F(\widehat{\mathbb{X}}_{k},\mathbb{X}_{k}^{(\ell)}),$

with
$\mathbb{X}_{k}^{(1)}=\widehat{\mathbb{X}}_{k}=\begin{bmatrix}\widehat{A}_{k}^{\top}&\widehat{G}_{k}^{\top}&\widehat{H}_{k}^{\top}\end{bmatrix}^{\top}$.

Concerning Algorithm 4.1, worth mentioning is that it can be reduced to SDA
iteration when $r=2$ [14, 8]. The following result provides the same
sufficient conditions in Theorem 3.2 that guarantees the R-superlinear
convergence of the sequence $\\{\widehat{H}_{k}\\}$.

######  Theorem 4.1.

Assume that $\mathbb{R}_{\geq}\neq\phi$ and $H\neq 0$. Then, the sequence
$\\{\widehat{H}_{k}\\}$ generated by Algorithm 4.1 converges R-superlinearly
to the minimal positive semidefinite solution $X_{\star}$ of (1). Moreover,
the convergence rate can be shown as the following.

$\underset{k\rightarrow\infty}{\lim{\rm
sup}}\sqrt[r^{k}]{\|\widehat{H}_{k}-X_{\star}\|}\leq\max\\{|\lambda|^{2};\lambda\in\sigma(T_{{X}_{\star}})\cap{\mathbb{D}}\\}.$

###### Proof.

From the above discussion, the sequence $\\{\mathbb{X}_{k}\\}$ has the
semigroup property. Thus, $\\{\mathbb{X}_{k}\\}$ satisfies the discrete flow
property (18), which together with the construction of $\widehat{H}_{k}$ lead
to

$\widehat{H}_{k}={H}_{r^{k}}={X}_{r^{k}}$

for all integers $k\geq 1$ [12][Remark 4.1]. The proof is straightforward from
Theorem 3.2. ∎

###  4.2 Numerical examples

In this subsection, all computations were performed in MATLAB/version 2016a on
a PC with an Intel Core i5-8279U GHZ processor and 8 GB main memory, using
IEEE double-precision floating-point arithmetic ( eps $=2^{-52}\approx
2.22\times 10^{-16}$).

######  Example 4.1.

Let $A=A_{1}\bigoplus A_{2}$, $G=G_{1}\bigoplus G_{2}$ and $H=H_{1}\bigoplus
H_{2}$, where $(A_{i},G_{i},H_{i})$ is a set of matrix coefficients
corresponding to a DARE (1) for $i=1$ or $2$. Consider the first set of matrix
coefficients $(A_{1},G_{1},H_{1})$ depending on four parameters and is defined
as $A_{1}=\left(\begin{array}[]{ccc}\epsilon&1&0\\\ 0&0&0\\\
0&0&0\end{array}\right),G_{1}=\left(\begin{array}[]{ccc}g&0&0\\\ 0&0&0\\\
0&0&0\end{array}\right),$ $H_{1}=\left(\begin{array}[]{ccc}0&0&0\\\ 0&a&b\\\
0&\bar{b}&c\end{array}\right)$, where $a,c,g,\epsilon>0$ and $b\in\mathbb{C}$
satisfies $ac\geq|b|^{2}$. The second set of matrix coefficients
$(A_{2},G_{2},H_{2})$ is constructed by applying some MATLAB functions
according to the following steps
$A_{2}=\verb!crand!(2,2)$,$G_{2}=U^{\ast}\verb!diag!([2,1])U$ and
$H_{2}=V^{\ast}\verb!diag(rand(2,1))!V$, where $U=\verb!orth(rand(2,2))!$ and
$V=\verb!orth(rand(2,2))!$.

It can be shown that $\rho(T_{H_{1}})=|\epsilon|$, $G_{1}H_{1}=0$ and
$X=H_{1}$ solves DARE (1) with coefficients $(A_{1},G_{1},H_{1})$ and thus has
a minimal positive semidefinite solution $X=X_{1}$ by Theorem 3.2, while
applying Corollary 3.1 the minimal positive semidefinite solution $X_{2}$ of
DARE (1) with coefficients $(A_{2},G_{2},H_{2})$ exists since $G_{2}>$ and
$\rho(T_{X_{2}})<1$. We conclude that $X_{m}=X_{1}\bigoplus X_{2}$ is the
minimal positive semidefinite solution of Eq. (1) with coefficients $(A,B,C)$.

Figure 1: Convergence behaviour of AFPI iteration with $\epsilon=0.5,1,1.5$,
respectively.

Now, we set $g=2$, $a=4,c=1$ and $b=\verb!crand!$. It can be easily proved
that $\rho(T_{X_{m}})=\max(\rho(T_{X_{1}}),\rho(T_{X_{2}}))$, then
$\rho(T_{X_{m}})=\rho(T_{X_{1}})=\epsilon\geq 1$ if $|\epsilon|\geq 1$ and
$\rho(T_{X_{m}})<1$ if $|\epsilon|<1$. By choosing $\epsilon=0.5,1,1.5$,
respectively, Figures 1 show the efficiency of the accelerated algorithm with
$r=2,3$, respectively.

######  Example 4.2.

This example is inspired by [9][Example 5.2]. Let

$A=\left(\begin{array}[]{ccc}-1&-1/2\\\ 0&-1\\\
\end{array}\right)\bigoplus\left(\begin{array}[]{ccc}-1&-1/2&-1/8\\\
0&-1&-1/2\\\ 0&0&-1\\\
\end{array}\right)\bigoplus\left(-\frac{2}{3}I_{2}\right),$
$G=\left(\begin{array}[]{ccc}\frac{1}{32}&\frac{1}{8}\\\
\frac{1}{8}&\frac{1}{2}\\\
\end{array}\right)\bigoplus\left(\begin{array}[]{cccc}\frac{1}{512}&\frac{1}{128}&\frac{1}{32}\\\
\frac{1}{128}&\frac{1}{32}&\frac{1}{8}\\\
\frac{1}{32}&\frac{1}{8}&\frac{1}{2}\\\
\end{array}\right)\bigoplus\left(\frac{2}{9}I_{2}\right),$

and $H=-3.5I_{7}$.

If $r=1$, that is, the original fixed point iteration, does not converge to
the solution within 1000 iterations, while for $r\geq 3$, the accelerated
iteration converges to a negative solution linearly. Figure 2 reports the
convergence behaviour of the accelerated iteration with $r=3,4,5,6,7$. In this
example, $H$ is a negative definite matrix. In other words, the assumption for
the positivity of $H$ is not satisfied. However, the similar convergent result
of AFPI with $r\geq 3$ under weaker conditions appears in Figure 2. By the
way, the authors illustrate the superior performance of AFPI with $r=2$ as
compared to NM and matrix disk function method (MDFM) in the numerical
experiments ([9][Example 5.2]), which show that AFPI with $r=2$ perform
feasibility and reliably. We believe AFPI may still converge even if $H$ is
indefinite. How to apply the accelerated techniques in the work under other
suitable conditions leads to the work in future.

Figure 2: Convergence behaviour of APFI with $r=3,4,5,6,7,8$, respectively.

##  5 Concluding remarks

This paper concerns comprehensive convergence analysis of the most recent and
advanced algorithms including SDA and its variants AFPI for solving DARE (1).
Our contribution fills in an existing gap in the minimal positive semidefinite
solution $X_{\star}$ of the DARE (1), concerning the magnitude
$\rho(T_{X_{\star}})\geq 1$. More precisely, we have proved the convergence
for the AFPI, when the eigenvalues of $T_{X_{\star}}$ are inside, on or
outside the open unit circle. The theoretical result is confirmed by a
randomness numerical example. Consequently, our results are more general than
those in the past works, which considered only eigenvalues lies in the closed
unit disk. The techniques of Proposition 2.1 and Theorem 3.2 can be adopted in
the convergence analysis of AFPI. We believe the results we obtain are novel
on this topic and could provide considerable insights into the study of other
nonlinear matrix equations.

## Acknowledgment

The author wish to thank Dr.Jie Meng and four anonymous referees for many
interesting and valuable suggestions on the manuscript. This research work is
partially supported by the Ministry of Science and Technology and the National
Center for Theoretical Sciences in Taiwan. The author would like to thank the
support from the Ministry of Science and Technology of Taiwan under the grant
MOST 108-2115-M-150-002.

## Appendix : An alternating iteration

###### Proof.

  1. 1.

First, for a positive definite matrix $Q$ it is fairly easy to see that
$E_{k}:=\sum\limits_{j=0}^{k-1}(A^{k})^{\ast}QA^{k}$ is a Cauchy sequence if
and only if $\rho(A)<1$.

Assume that $S_{A}(X_{0})>0$ for some $X_{0}>0$. Then, there exists a positive
number $\epsilon$ such that $X_{0}>\epsilon
I_{n}+A^{\ast}X_{0}A\geq\epsilon\sum\limits_{j=0}^{k}(A^{j})^{\ast}A^{j}$ for
any positive integer $k$. It immediately implies that $\rho(A)<1$. Conversely,
$X=X_{0}:=\sum\limits_{j=0}^{\infty}(A^{k})^{\ast}QA^{k}>0$ solves the
equation $S_{A}(X)=Q$ if $\rho(A)<1$, where $Q$ is any positive definite
matrix.

  2. 2.

Assume that there exists a $X\in\mathbb{P}_{n}$ such that $Q:=S_{A}(X)\geq 0$.
It can be shown that there exists a nonsingular matrix
$S\in\mathbb{C}^{n\times n}$ such that $S^{\ast}XS=I_{n}$ and
$S^{\ast}QS=Q_{r}\oplus 0_{n-r}$ with a $r\times r$ positive diagonal matrix
$Q_{r}$ [1][Theorem 8.3.1]. We transform (5) into the following equation

$0\leq\widehat{A}^{\ast}\widehat{A}=(I_{r}-Q_{r})\oplus I_{n-r}\leq I_{n},$

where $\widehat{A}=S^{-1}AS$. It is immediately that $\widehat{A}$ is
semicontractive [1][Definition 3.1.2] and thus $A$ is discrete-time Lyapunov
stable [1][Fact 11.21.4]. Namely, $\rho({A})\leq 1$, and if $\rho({A})=1$,
then all unimodular eigenvalues of ${A}$ is semisimple.

Conversely, if there exists nonsingular matrix $P$ such that
$PAP^{-1}=J_{s}\oplus J_{1}$ where $J_{s}$ is a Jordan canonical form of
$k\times k$ matrix satisfying $\rho(J_{s})<1$ and $J_{1}$ is a
$(n-k)\times(n-k)$ diagonal matrix satisfying $\rho(J_{1})=1$. Let
$\widehat{X}:=P^{\ast}XP$ and $\widehat{Q}:=P^{\ast}QP$. We partition two
matrices $\widehat{X}$ and $\widehat{Q}$ as $2\times 2$ block matrices
$\begin{bmatrix}\widehat{X}_{i,j}\end{bmatrix}$ and
$\begin{bmatrix}\widehat{Q}_{i,j}\end{bmatrix}$, respectively, where
$\widehat{X}_{1,1},\widehat{Q}_{1,1}\in\mathbb{C}^{k\times k}$ and
$\widehat{X}_{2,2},\widehat{Q}_{2,2}\in\mathbb{C}^{(n-k)\times(n-k)}$. We have

$\displaystyle\widehat{X}_{1,1}$
$\displaystyle=\widehat{Q}_{1,1}+J_{s}^{\ast}\widehat{X}_{1,1}J_{s},$ (21a)
$\displaystyle\widehat{X}_{2,1}$
$\displaystyle=\widehat{Q}_{2,1}+J_{s}^{\ast}\widehat{X}_{2,1}J_{1},$ (21b)
$\displaystyle\widehat{X}_{2,2}$
$\displaystyle=\widehat{Q}_{2,2}+J_{1}^{\ast}\widehat{X}_{2,2}J_{1}.$ (21c)

It is obtained $\widehat{Q}=I_{k}\oplus 0_{n-k}$ by choosing
$Q=P^{-H}(I_{k}\oplus 0_{n-k})P^{-1}$. It is easily to check that there exist
two unique solution $\widehat{X}_{11}\in\mathbb{P}_{n}$ and
$\widehat{X}_{21}=0_{k\times(n-k)}\in\mathbb{C}^{k\times(n-k)}$ to the
corresponding Stein matrix equations (21a) and (21b). Let $\widehat{X}_{22}$
be a diagonal matrix whose diagonal elements are all nonnegative. Then, the
matrix
$X=P^{-H}(\widehat{X}_{11}\oplus\widehat{X}_{22})P^{-1}\in\mathbb{N}_{n}$
satisfies $S_{A}(X)=Q\geq 0$. Moreover, a positive definite matrix $X$ can be
chosen by setting $\widehat{X}_{22}>0$.

∎

## References

  * [1] D. S. Bernstein.  Matrix Mathematics: Theory, Facts, and Formulas.  Princeton University Press, Princeton, NJ, second edition, 2009.
  * [2] D. A. Bini, B. Iannazzo, and B. Meini.  Numerical Solution of Algebraic Riccati Equations, volume 9 of Fundamentals of Algorithms.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2012.
  * [3] C.-Y. Chiang.  An accelerated technique for solving the positive definite solutions of a class of nonlinear matrix equations.  J. Franklin Inst., 354(15):7088–7118, 2017.
  * [4] C.-Y. Chiang, E. K.-W. Chu, C.-H. Guo, T.-M. Huang, W.-W. Lin, and S.-F. Xu.  Convergence analysis of the doubling algorithm for several nonlinear matrix equations in the critical case.  SIAM J. Matrix Anal. Appl., 31(2):227–247, 2009.
  * [5] 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(3A):933–954, 2010.
  * [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(3):632–645, 2002.
  * [7] 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(2):279–294, 1999.
  * [8] T.-M. Huang, R.-C. Li, and W.-W. Lin.  Structure-preserving doubling algorithms for nonlinear matrix equations, volume 14 of Fundamentals of Algorithms.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2018.
  * [9] T.-M. Huang and W.-W. Lin.  Structured doubling algorithms for weakly stabilizing hermitian solutions of algebraic riccati equations.  Linear Algebra Appl., 430(5):1452 – 1478, 2009.
  * [10] C. T. Kelley.  Iterative methods for linear and nonlinear equations, volume 16 of Frontiers in Applied Mathematics.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995.
  * [11] P. Lancaster and L. Rodman.  Algebraic Riccati equations.  Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1995.
  * [12] 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:91 – 110, 2018.
  * [13] M. M. Lin and C.-Y. Chiang.  On the semigroup property for some structured iterations.  J. Comput. Appl. Math., page 112768, 2020.
  * [14] W.-W. Lin and S.-F. Xu.  Convergence analysis of structure-preserving doubling algorithms for Riccati-type matrix equations.  SIAM J. Matrix Anal. Appl., 28(1):26–39, 2006.
  * [15] J. Ortega and W. Rheinboldt.  Iterative Solution of Nonlinear Equations in Several Variables.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000.
  * [16] F. A. Potra.  On $Q$-order and $R$-order of convergence.  J. Optim. Theory Appl., 63(3):415–431, 1989.