# Solvability Theory and Iteration Method for One Self-Adjoint Polynomial Matrix Equation

Authors: Zhigang Jia; Meixiang Zhao; Minghui Wang; Sitao Ling
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The solvability theory of an important self-adjoint polynomial matrix equation is presented, including the boundary of its Hermitian positive definite (HPD) solution and some sufficient conditions under which the (unique or maximal) HPD solution exists. The algebraic perturbation analysis is also given with respect to the perturbation of coefficient matrices. An efficient general iterative algorithm for the maximal or
unique HPD solution is designed and tested by numerical experiments.


---

## Body

## 1. Introduction

In this paper, we consider the following self-adjoint polynomial matrix equation:(1)
X
s
-
A
*
X
t
A
=
Q
,
where s
,
t are positive integers, A
,
Q
∈
ℂ
n
×
n, and Q
>
0. As far as we know, the solvability of (1) is not completely solved untill now.In many fields of applied mathematics, engineering, and economic sciences, (1) plays an important role. The famous discrete-time algebraic Lyapunov equation (DALE) is exactly (1) with s
=
t
=
1. Undoubtedly, DALE is one of the most important mathematical problems in signal processing, system, and control theory and many others (e.g., see the monographs [1, 2]). If A is stable (with respect to the unit circle), DALE has a unique Hermitian positive definite (HPD) solution. Such strong relation between the spectral property of A and the solvability theory is fortunately owned by (1), which can be considered as a nonlinear DALE if s
≠
1 or t
≠
1. What about the following algebraic Riccati equation:
(2)
Y
2
+
B
*
Y
+
Y
B
-
A
*
Y
A
-
R
=
0
,
where A
,
B
,
R
∈
ℂ
n
×
n, B
*
=
B
≥
0, and R
*
=
R
>
0? Defining X
:
=
Y
+
B and Q
:
=
R
+
B
2
-
A
*
B
A, we can immediately get (1) with s
=
2 and t
=
1 as an equivalent form of (2). As we all know, solving algebraic Riccati equations is an important task in the linear-quadratic regulator problem, Kalman filtering, H
∞-control, model reduction problems, and so forth. See [1, 3–5] and the references therein. Many numerical methods have been proposed, such as invariant subspace methods [6], Schur method [7], doubling algorithm [8], and structure-preserving doubling algorithm [9, 10]. At the same time the perturbation theory was developed in [11–15], as well as the unified methods for the discrete-time and continuous-time algebraic Riccati equations [16, 17]. A general iteration method for (1) given in this paper can be seen as a new algorithm for the algebraic Riccati equation (2), setting s
=
2 and t
=
1.Apart from the above applications, (1) is appealing from the mathematical viewpoint since it unifies a large class of systems of polynomial matrix equations. Many nonlinear matrix equations are special cases of (1). For example, nonlinear matrix equations, X
-
A
*
X
q
A
=
Q (see, e.g., [18, 19]), are equivalence models of Y
s
-
A
*
Y
t
A
=
Q and Y
=
X
1
/
s, where s
,
t are positive integers and q
=
t
/
s. In a rather general form, Ran and Reurings [18] investigated X
+
A
*
ℱ
(
X
)
A
=
Q (Q
>
0) for its positive semidefinite solutions under the assumption that the function ℱ
(
·
) is monotone and Q
-
A
*
ℱ
(
Q
)
A is positively definite. Besides, Lee and Lim [20] proved that (1) has a unique HPD solution when |
s
|
≥
1
≥
|
t
| and |
t
/
s
|
<
1. See [21–25] for more recent results on nonlinear matrix equations. To the best of our knowledge, (1) with s
<
t (without monotony in hand) has not been discussed. These facts motivate us to study polynomial matrix equation (1).This paper is organized as follows. In Section2 we deduce the existence and uniqueness conditions of HPD solutions of (1); in Section 3 we derive the algebraic perturbation theory for the unique or maximal solution of (1); finally in Section 4, we provide an iterative algorithm and two numerical experiments.We begin with some notations used throughout this paper.𝔽
m
×
n stands for the set of m
×
n matrices with elements on field 𝔽
(
𝔽
is
ℝ
or
ℂ
). If H is a Hermitian matrix on 𝔽
n
×
n, λ
min
⁡
(
H
) and λ
max
⁡
(
H
) stand for the minimal and the maximal eigenvalues, respectively. Denote the singular values of a matrix A
∈
𝔽
m
×
n by σ
1
(
A
)
≥
⋯
≥
σ
l
(
A
)
≥
0, where l
=
min
⁡
{
m
,
n
}. Suppose that X and Y are Hermitian matrices; we write X
≥
Y
(
X
>
Y
) if X
-
Y is positively semidefinite (definite) and denote the matrices set {
X
∣
X
-
α
I
≥
0
and
β
I
-
X
≥
0
} by [
α
I
,
β
I
].


## 2. Solvability of Self-Adjoint Polynomial Matrix Equation

In this section, we study the solvability theory of (1) assuming that A is nonsingular; that is, λ
min
⁡
(
A
*
A
)
>
0. To do this, we need two simple but useful functions defined on the positive abscissa axis:
(3)
g
1
(
x
)
=
x
s
-
λ
max
⁡
(
A
*
A
)
x
t
-
λ
max
⁡
(
Q
)
,
g
2
(
x
)
=
x
s
-
λ
min
⁡
(
A
*
A
)
x
t
-
λ
min
⁡
(
Q
)
.The following two famous inequalities will be used frequently in the remaining of this paper.Lemma 1 (Löwner-Heinz inequality [26, Theorem 1.1]).
IfA
≥
B
≥
0 and 0
≤
r
≤
1, then A
r
≥
B
r.Lemma 2 (see [27, Theorem 2.1]).
LetA and B be positive operators on a Hilbert space H, such that M
1
I
≥
A
≥
m
1
I
>
0
,
M
2
I
≥
B
≥
m
2
I
>
0, and 0
<
A
≤
B. Then
(4)
A
t
≤
(
M
1
m
1
)
t
-
1
B
t
,
A
t
≤
(
M
2
m
2
)
t
-
1
B
t
hold for any t
≥
1.


### 2.1. Maximal Solution of (1) with s
<
t

Now we derive a necessary condition and a sufficient condition for existence of HPD solutions of (1) with s
<
t. With g
1
(
x
) and g
2
(
x
) in hand, we can easily get the distribution of eigenvalues of the HPD solution X of (1).Theorem 3.
Suppose thatλ
max
⁡
(
A
*
A
)
≤
(
s
/
t
)
(
(
t
-
s
)
/
λ
max
⁡
(
Q
)
t
)
(
t
-
s
)
/
s and X
∈
ℂ
n
×
n is an HPD solution of (1); then for any eigenvalue λ
(
X
) of X,
(5)
β
1
≤
λ
(
X
)
≤
α
1
o
r
α
2
≤
λ
(
X
)
≤
β
2
,
where α
1
,
α
2 are two positive roots of g
1
(
x
) and β
1
,
β
2 are two positive roots of g
2
(
x
).Proof.
From Theorem3.3
.
16(d) in Horn and Johnson [28], one can see that
(6)
σ
i
(
A
*
X
t
A
)
≤
σ
i
(
X
t
)
σ
1
2
(
A
)
,
that
is
,
λ
i
(
A
*
X
t
A
)
≤
λ
i
(
X
t
)
λ
max
⁡
(
A
*
A
)
,
i
=
1
,
…
,
n
.
IfA is nonsingular,
(7)
σ
i
(
X
t
)
=
σ
i
(
(
A
-
1
)
*
A
*
X
t
A
A
-
1
)
≤
σ
n
-
2
(
A
)
σ
i
(
A
*
X
t
A
)
.
That means
(8)
σ
i
(
A
*
X
t
A
)
≥
σ
i
(
X
t
)
σ
n
2
(
A
)
,
that
is
,
λ
i
(
A
*
X
t
A
)
≥
λ
i
(
X
t
)
λ
min
⁡
(
A
*
A
)
,
i
=
1
,
…
,
n
.
The above equations still hold if A is singular, since σ
n
(
A
)
=
0, that is, λ
min
⁡
(
A
*
A
)
=
0, in this case. Applying Weyl theorem in Horn and Johnson [29], X
s
=
Q
+
A
*
X
t
A implies
(9)
λ
(
X
)
s
-
λ
max
⁡
(
A
*
A
)
λ
(
X
)
t
λ
max
⁡
(
Q
)
≤
0
,
λ
(
X
)
s
-
λ
min
⁡
(
A
*
A
)
λ
(
X
)
t
-
λ
min
⁡
(
Q
)
≥
0
.
Define a functionf
(
x
)
=
x
s
-
a
2
x
t
-
q
,
a
>
0
,
q
>
0. Then the only positive stationary point of f
(
x
) is x
0
=
(
(
t
/
s
)
a
2
)
1
/
(
s
-
t
). If a
2
≤
(
s
/
t
)
(
(
t
-
s
)
/
q
t
)
(
t
-
s
)
/
s, f
(
x
) has two positive roots, x
1 and x
2, with q
1
/
s
<
x
1
≤
x
0
≤
x
2
<
a
2
/
(
s
-
t
). So λ
max
⁡
(
A
*
A
)
≤
(
s
/
t
)
(
t
-
s
)
/
λ
max
⁡
(
Q
)
t
(
t
-
s
)
/
s implies that g
1
(
x
) has two roots α
1
,
α
2
>
0 and g
2
(
x
) has two roots β
1
,
β
2
>
0. Since g
2
(
x
)
≥
g
1
(
x
), (
λ
min
⁡
(
Q
)
)
1
/
s
≤
β
1
≤
α
1
≤
α
2
≤
β
2
≤
(
λ
min
⁡
(
A
*
A
)
)
1
/
(
s
-
t
). Then from (9) we obtain (5).If (1) has an HPD solution, its eigenvalues may skip between [
β
1
,
α
1
] and [
α
2
,
β
2
]. Next, what we take more attention on is the HPD solution with its eigenvalues distributed only on one interval.Theorem 4.
Suppose thatλ
max
⁡
(
A
*
A
)
≤
(
s
/
t
)
(
(
t
-
s
)
/
λ
max
⁡
(
Q
)
t
)
(
t
-
s
)
/
s.(1)
Equation (1) has an HPD solution, X
∈
[
β
1
I
,
α
1
I
], and if λ
min
⁡
(
A
*
A
)
>
s
α
1
s
-
1
(
t
β
1
t
-
1
)
-
1 such X exists uniquely.
(2)
Equation (1) has an HPD solution, Z
∈
[
α
2
I
,
β
2
I
], and if λ
min
⁡
(
A
*
A
)
>
s
β
2
s
-
1
(
t
α
2
t
-
1
)
-
1 such Z exists uniquely.Proof.
(1) Leth
1
(
X
)
=
(
Q
+
A
*
X
t
A
)
1
/
s, where X
∈
[
(
λ
min
⁡
(
Q
)
)
1
/
s
I
,
(
s
/
(
λ
max
⁡
(
A
*
A
)
t
)
)
1
/
(
t
-
s
)
I
]. Lemmas 1 and 2 and t
-
s
>
0 imply
(10)
(
λ
min
⁡
(
Q
)
)
1
/
s
I
≤
h
1
(
X
)
≤
{
λ
max
⁡
(
Q
)
+
λ
max
⁡
(
A
*
A
)
[
s
(
λ
max
⁡
(
A
*
A
)
t
)
]
t
/
(
t
-
s
)
}
1
/
s
I
≤
[
s
λ
max
⁡
(
A
*
A
)
t
]
s
/
(
t
-
s
)
×
1
/
s
I
=
[
s
λ
max
⁡
(
A
*
A
)
t
]
1
/
(
t
-
s
)
I
.
Applying Brouwer’s fixed-point theorem, h
1
(
X
) has a fixed point X
∈
[
(
λ
min
⁡
(
Q
)
)
1
/
s
I
,
(
s
/
(
λ
max
⁡
(
A
*
A
)
t
)
)
1
/
(
t
-
s
)
I
]. Then from Theorem 3, X
∈
[
β
1
I
,
α
1
I
].
We now prove the uniqueness ofX under the additional condition that λ
min
⁡
(
A
*
A
)
>
s
α
1
s
-
1
(
t
β
1
t
-
1
)
-
1. Suppose Y
∈
[
(
λ
min
⁡
(
Q
)
)
1
/
s
I
,
(
s
/
(
λ
max
⁡
(
A
*
A
)
t
)
)
1
/
(
t
-
s
)
I
] is another HPD solution of (1) and Y
≠
X. It has been known that
(11)
∥
X
t
-
Y
t
∥
F
=
∥
(
A
-
1
)
*
(
X
s
-
Y
s
)
A
-
1
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
∥
X
s
-
Y
s
∥
F
.
Then from ∥
X
s
-
Y
s
∥
F
≤
s
α
1
s
-
1
∥
X
-
Y
∥
F and ∥
X
t
-
Y
t
∥
F
≥
t
β
1
t
-
1
∥
X
-
Y
∥
F,
(12)
∥
X
-
Y
∥
F
≤
s
α
1
s
-
1
[
t
β
1
t
-
1
λ
min
⁡
(
A
*
A
)
]
-
1
∥
X
-
Y
∥
F
<
∥
X
-
Y
∥
F
,
which is impossible. Hence, X
=
Y.
(2) Leth
2
(
Z
)
=
[
(
A
-
1
)
*
(
Z
s
-
Q
)
A
-
1
]
1
/
t, where Z
∈
[
α
2
I
,
β
2
I
]. h
2
(
Z
) is continuous, and
(13)
h
2
(
α
2
I
)
≤
h
2
(
Z
)
≤
h
2
(
β
2
I
)
because (
A
-
1
)
*
(
α
2
s
I
-
Q
)
A
-
1
≤
(
A
-
1
)
*
(
Z
s
-
Q
)
A
-
1
≤
(
A
-
1
)
*
(
β
2
s
I
-
Q
)
A
-
1. By Lemmas 1 and 2 and Brouwer’s fixed-point theorem, it is sufficient to prove h
2
(
α
2
I
)
≥
α
2
I and h
2
(
β
2
I
)
≤
β
2
I in order for an HPD solution Z
∈
[
α
2
I
,
β
2
I
] to exist. The existence of such Z follows from inequalities
(14)
h
2
(
α
2
I
)
=
[
(
A
-
1
)
*
(
α
2
s
I
-
Q
)
A
-
1
]
1
/
t
≥
[
(
A
-
1
)
*
(
α
2
s
I
-
λ
max
⁡
(
Q
)
I
)
A
-
1
]
1
/
t
≥
[
(
λ
max
⁡
(
A
*
A
)
)
-
1
(
α
2
s
I
-
λ
max
⁡
(
Q
)
I
)
]
1
/
t
=
α
2
I
,
h
2
(
β
2
I
)
=
[
(
A
-
1
)
*
(
β
2
s
I
-
Q
)
A
-
1
]
1
/
t
≤
[
(
A
-
1
)
*
(
β
2
s
I
-
λ
min
⁡
(
Q
)
I
)
A
-
1
]
1
/
t
≤
[
(
λ
min
⁡
(
A
*
A
)
)
-
1
(
β
2
s
I
-
λ
min
⁡
(
Q
)
I
)
]
1
/
t
=
β
2
I
.
Next we prove the uniqueness ofZ under the additional condition that λ
min
⁡
(
A
*
A
)
>
s
β
2
s
-
1
(
t
α
2
t
-
1
)
-
1. Suppose (1) has two different HPD solutions Z and Y on [
α
2
I
,
β
2
I
]. Then
(15)
∥
Z
t
-
Y
t
∥
F
=
∥
(
A
-
1
)
*
(
Z
s
-
Y
s
)
A
-
1
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
∥
Z
s
-
Y
s
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
s
β
2
s
-
1
∥
Z
-
Y
∥
F
.
Moreover, if λ
min
⁡
(
A
*
A
)
>
s
β
2
s
-
1
(
t
α
2
t
-
1
)
-
1, applying the inequality ∥
Z
t
-
Y
t
∥
F
≥
t
α
2
t
-
1
∥
Z
-
Y
∥
F, we have
(16)
∥
Z
-
Y
∥
F
≤
(
t
α
2
t
-
1
λ
min
⁡
(
A
*
A
)
)
-
1
s
β
2
s
-
1
∥
Z
-
Y
∥
F
<
∥
Z
-
Y
∥
F
,
which is impossible. Hence, Y
=
Z.The maximal solution (see, e.g., [30, 31]) of (1) is defined as follows.Definition 5.
An HPD solutionX
M
∈
ℂ
n
×
n of (1) is the maximal solution if, for any HPD solution Y
∈
ℂ
n
×
n of (1), there is X
M
≥
Y.So the second term of Theorem4 implies that the maximal solution of (1) is on [
α
2
I
,
β
2
I
].Theorem 6.
Suppose thatλ
max
⁡
(
A
*
A
)
≤
(
s
/
t
)
(
t
/
(
t
-
s
)
λ
max
⁡
(
Q
)
)
(
s
-
t
)
/
s and λ
min
⁡
(
A
*
A
)
>
s
β
2
s
-
1
(
t
α
2
t
-
1
)
-
1; then (1) has a maximal solution X
max
⁡
∈
[
α
2
I
,
β
2
I
] which can be computed by
(17)
X
i
=
[
(
A
-
1
)
*
(
X
i
-
1
s
-
Q
)
A
-
1
]
1
/
t
,
i
=
1,2
,
…
.
with the initial value X
0
=
β
2
I.Proof.
Letξ
=
(
t
α
2
t
-
1
λ
min
⁡
(
A
*
A
)
)
-
1
s
β
2
s
-
1; then ξ
<
1. From the proof of Theorem 4 (2),
(18)
t
α
2
t
-
1
∥
X
i
+
1
-
X
i
∥
F
≤
∥
X
i
+
1
t
-
X
i
t
∥
F
=
∥
(
A
-
1
)
*
(
X
i
s
-
X
i
-
1
s
)
A
-
1
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
∥
X
i
s
-
X
i
-
1
s
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
s
β
2
s
-
1
∥
X
i
-
X
i
-
1
∥
F
.
Then
(19)
∥
X
i
+
1
-
X
i
∥
F
≤
ξ
∥
X
i
-
X
i
-
1
∥
F
≤
ξ
i
∥
X
1
-
X
0
∥
F
,
which indicates the convergence of matrix series {
X
0
,
X
1
,
X
2
,
…
}, generated by (17).
SetX
0
=
β
2
I. Assuming X
i
∈
[
α
2
I
,
β
2
I
], then from inequalities (14) we have
(20)
α
2
I
≤
h
(
α
2
I
)
≤
X
i
+
1
=
[
(
A
-
1
)
*
(
X
i
s
-
Q
)
A
-
1
]
1
/
t
≤
h
(
β
2
I
)
≤
β
2
I
.
That means, for any i
=
0,1
,
2
,
…
,
X
i
∈
[
α
2
I
,
β
2
I
]. By Theorem 4 (2), we can see that X
max
⁡
=
lim
⁡
i
→
+
∞
X
i is the unique HPD solution of (1) on [
α
2
I
,
β
2
I
].
Now we prove the maximality ofX
max
⁡. Suppose that X is an arbitrary HPD solution of (1); then X
0
≥
X, and Theorem 3 implies X
0
t
≥
X
t (since X
0
=
β
2
I). Assuming that X
i
t
≥
X
t, Lemma 1 with s
/
t
<
1 implies
(21)
X
i
+
1
t
=
(
A
-
1
)
*
[
(
X
i
t
)
s
/
t
-
Q
]
A
-
1
≥
(
A
-
1
)
*
[
(
X
t
)
s
/
t
-
Q
]
A
-
1
=
X
t
.
Then X
max
⁡
t
=
lim
⁡
i
→
+
∞
X
i
t
≥
X
t, which implies that X
max
⁡
≥
X by the Löwner-Heinz inequality.Note that similar iteration formula ever appeared in some papers such as [20, 21] for other nonlinear matrix equations. Here we firstly proved that the iteration form (17) preserves the maximality of X
i over all HPD solutions of (1).


### 2.2.  Unique Solution of (1) with s
≥
t

Ifs
>
t, Lee and Lim [20, Theorem 9.4] show that (1) always has a unique HPD solution, denoted by X
u. Now we give an upper bound and a lower bound of X
u and suggest an iteration method for computing X
u.As defined in (3), g
1
(
x
) and g
2
(
x
) with s
>
t have unique positive roots, denoted by γ
1 and γ
2, respectively.Sinceg
1
(
λ
(
X
u
)
)
≤
0 and g
2
(
λ
(
X
u
)
)
≤
0, γ
2
≤
λ
(
X
u
)
≤
γ
1.Theorem 7.
Ifs
>
t, (1) has a unique HPD solution X
u
∈
[
γ
2
I
,
γ
1
I
]. Let X
0
=
γ
1
I or γ
2
I, then matrix series {
X
0
,
X
1
,
X
2
,
…
} generated by
(22)
X
i
=
(
Q
+
A
*
X
i
-
1
t
A
)
1
/
s
,
i
=
0,1
,
2
,
…
will converge to X
u.Proof.
We only need to prove the convergence of matrix series{
X
0
,
X
1
,
X
2
,
…
}. Set X
0
=
γ
1
I. From (22) we have
(23)
X
1
=
(
Q
+
γ
1
t
A
*
A
)
1
/
s
≤
(
λ
max
⁡
(
Q
)
+
γ
1
t
λ
max
⁡
(
A
*
A
)
)
1
/
s
I
=
γ
1
I
,
and then X
1
s
≤
X
0
s. Assuming that X
i
s
≤
X
i
-
1
s,
(24)
X
i
+
1
s
=
Q
+
A
*
X
i
t
A
=
Q
+
A
*
(
X
i
s
)
t
/
s
A
≤
Q
+
A
*
(
X
i
-
1
s
)
t
/
s
A
=
X
i
s
.
Then for any i
=
0,1
,
2
,
…, we have X
i
+
1
s
≤
X
i
s and then X
i
+
1
≤
X
i by Löwner-Heinz inequality. On the other hand, X
0
≥
γ
2
I implies X
i
≥
γ
2
I for any i
=
0,1
,
2
,
…, because if X
i
-
1
≥
γ
2
I, then
(25)
X
i
=
(
Q
+
A
*
X
i
-
1
t
A
)
1
/
s
≥
(
Q
+
γ
2
t
A
*
A
)
1
/
s
≥
(
λ
min
⁡
(
Q
)
+
γ
2
t
λ
min
⁡
(
A
*
A
)
)
1
/
s
I
=
γ
2
I
.
Then {
X
0
,
X
1
,
X
2
,
…
} with X
0
=
γ
1
I is a decreasingly monotone matrix series with a lower bound γ
2
I. Similarly we can prove that {
X
0
,
X
1
,
X
2
,
…
} generated by (22) with X
0
=
γ
2
I is an increasingly monotone matrix series with an upper bound γ
1
I. Therefore, the convergence of {
X
0
,
X
1
,
X
2
,
…
} has been proved.From the above proof, we can see that the iteration form (22) preserves the minimality (X
0
=
γ
1
I) or maximality (X
0
=
γ
2
I) of X
i in process.Ifs
=
t, (1) can be reduced to a linear matrix equation Y
-
A
*
Y
A
=
Q, which is the discrete-time algebraic Lyapunov equation (DALE) or Hermitian Stein equation, [1, Page 5], assuming that Y
=
X
s. It is well known that if A is d-stable (see [1]), Y
-
A
*
Y
A
=
Q has a unique solution, and matrix series {
Y
0
,
Y
1
,
Y
2
,
…
}, generated by Y
i
+
1
=
Q
+
A
*
Y
i
A with an initial value Y
0, will converge to the unique solution. Besides, it is not difficult to get an expression of the unique solution X
u
=
(
∑
j
=
0
∞
(
A
*
)
j
Q
A
j
)
1
/
s, applying [32, Theorem 1, Section 13.2), [1, Theorem 1.1
.
18], and the results in Section 6.4 in [28].Now we have presented the solvability theory of the self-adjoint polynomial matrix equation (1) in three cases. A general iterative algorithm for its maximal solution (s
<
t) or unique solution (s
≥
t) will be given in Section 4. Before it, we study the algebraic perturbation of the maximal or unique solution of (1).


## 2.1. Maximal Solution of (1) with s
<
t

Now we derive a necessary condition and a sufficient condition for existence of HPD solutions of (1) with s
<
t. With g
1
(
x
) and g
2
(
x
) in hand, we can easily get the distribution of eigenvalues of the HPD solution X of (1).Theorem 3.
Suppose thatλ
max
⁡
(
A
*
A
)
≤
(
s
/
t
)
(
(
t
-
s
)
/
λ
max
⁡
(
Q
)
t
)
(
t
-
s
)
/
s and X
∈
ℂ
n
×
n is an HPD solution of (1); then for any eigenvalue λ
(
X
) of X,
(5)
β
1
≤
λ
(
X
)
≤
α
1
o
r
α
2
≤
λ
(
X
)
≤
β
2
,
where α
1
,
α
2 are two positive roots of g
1
(
x
) and β
1
,
β
2 are two positive roots of g
2
(
x
).Proof.
From Theorem3.3
.
16(d) in Horn and Johnson [28], one can see that
(6)
σ
i
(
A
*
X
t
A
)
≤
σ
i
(
X
t
)
σ
1
2
(
A
)
,
that
is
,
λ
i
(
A
*
X
t
A
)
≤
λ
i
(
X
t
)
λ
max
⁡
(
A
*
A
)
,
i
=
1
,
…
,
n
.
IfA is nonsingular,
(7)
σ
i
(
X
t
)
=
σ
i
(
(
A
-
1
)
*
A
*
X
t
A
A
-
1
)
≤
σ
n
-
2
(
A
)
σ
i
(
A
*
X
t
A
)
.
That means
(8)
σ
i
(
A
*
X
t
A
)
≥
σ
i
(
X
t
)
σ
n
2
(
A
)
,
that
is
,
λ
i
(
A
*
X
t
A
)
≥
λ
i
(
X
t
)
λ
min
⁡
(
A
*
A
)
,
i
=
1
,
…
,
n
.
The above equations still hold if A is singular, since σ
n
(
A
)
=
0, that is, λ
min
⁡
(
A
*
A
)
=
0, in this case. Applying Weyl theorem in Horn and Johnson [29], X
s
=
Q
+
A
*
X
t
A implies
(9)
λ
(
X
)
s
-
λ
max
⁡
(
A
*
A
)
λ
(
X
)
t
λ
max
⁡
(
Q
)
≤
0
,
λ
(
X
)
s
-
λ
min
⁡
(
A
*
A
)
λ
(
X
)
t
-
λ
min
⁡
(
Q
)
≥
0
.
Define a functionf
(
x
)
=
x
s
-
a
2
x
t
-
q
,
a
>
0
,
q
>
0. Then the only positive stationary point of f
(
x
) is x
0
=
(
(
t
/
s
)
a
2
)
1
/
(
s
-
t
). If a
2
≤
(
s
/
t
)
(
(
t
-
s
)
/
q
t
)
(
t
-
s
)
/
s, f
(
x
) has two positive roots, x
1 and x
2, with q
1
/
s
<
x
1
≤
x
0
≤
x
2
<
a
2
/
(
s
-
t
). So λ
max
⁡
(
A
*
A
)
≤
(
s
/
t
)
(
t
-
s
)
/
λ
max
⁡
(
Q
)
t
(
t
-
s
)
/
s implies that g
1
(
x
) has two roots α
1
,
α
2
>
0 and g
2
(
x
) has two roots β
1
,
β
2
>
0. Since g
2
(
x
)
≥
g
1
(
x
), (
λ
min
⁡
(
Q
)
)
1
/
s
≤
β
1
≤
α
1
≤
α
2
≤
β
2
≤
(
λ
min
⁡
(
A
*
A
)
)
1
/
(
s
-
t
). Then from (9) we obtain (5).If (1) has an HPD solution, its eigenvalues may skip between [
β
1
,
α
1
] and [
α
2
,
β
2
]. Next, what we take more attention on is the HPD solution with its eigenvalues distributed only on one interval.Theorem 4.
Suppose thatλ
max
⁡
(
A
*
A
)
≤
(
s
/
t
)
(
(
t
-
s
)
/
λ
max
⁡
(
Q
)
t
)
(
t
-
s
)
/
s.(1)
Equation (1) has an HPD solution, X
∈
[
β
1
I
,
α
1
I
], and if λ
min
⁡
(
A
*
A
)
>
s
α
1
s
-
1
(
t
β
1
t
-
1
)
-
1 such X exists uniquely.
(2)
Equation (1) has an HPD solution, Z
∈
[
α
2
I
,
β
2
I
], and if λ
min
⁡
(
A
*
A
)
>
s
β
2
s
-
1
(
t
α
2
t
-
1
)
-
1 such Z exists uniquely.Proof.
(1) Leth
1
(
X
)
=
(
Q
+
A
*
X
t
A
)
1
/
s, where X
∈
[
(
λ
min
⁡
(
Q
)
)
1
/
s
I
,
(
s
/
(
λ
max
⁡
(
A
*
A
)
t
)
)
1
/
(
t
-
s
)
I
]. Lemmas 1 and 2 and t
-
s
>
0 imply
(10)
(
λ
min
⁡
(
Q
)
)
1
/
s
I
≤
h
1
(
X
)
≤
{
λ
max
⁡
(
Q
)
+
λ
max
⁡
(
A
*
A
)
[
s
(
λ
max
⁡
(
A
*
A
)
t
)
]
t
/
(
t
-
s
)
}
1
/
s
I
≤
[
s
λ
max
⁡
(
A
*
A
)
t
]
s
/
(
t
-
s
)
×
1
/
s
I
=
[
s
λ
max
⁡
(
A
*
A
)
t
]
1
/
(
t
-
s
)
I
.
Applying Brouwer’s fixed-point theorem, h
1
(
X
) has a fixed point X
∈
[
(
λ
min
⁡
(
Q
)
)
1
/
s
I
,
(
s
/
(
λ
max
⁡
(
A
*
A
)
t
)
)
1
/
(
t
-
s
)
I
]. Then from Theorem 3, X
∈
[
β
1
I
,
α
1
I
].
We now prove the uniqueness ofX under the additional condition that λ
min
⁡
(
A
*
A
)
>
s
α
1
s
-
1
(
t
β
1
t
-
1
)
-
1. Suppose Y
∈
[
(
λ
min
⁡
(
Q
)
)
1
/
s
I
,
(
s
/
(
λ
max
⁡
(
A
*
A
)
t
)
)
1
/
(
t
-
s
)
I
] is another HPD solution of (1) and Y
≠
X. It has been known that
(11)
∥
X
t
-
Y
t
∥
F
=
∥
(
A
-
1
)
*
(
X
s
-
Y
s
)
A
-
1
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
∥
X
s
-
Y
s
∥
F
.
Then from ∥
X
s
-
Y
s
∥
F
≤
s
α
1
s
-
1
∥
X
-
Y
∥
F and ∥
X
t
-
Y
t
∥
F
≥
t
β
1
t
-
1
∥
X
-
Y
∥
F,
(12)
∥
X
-
Y
∥
F
≤
s
α
1
s
-
1
[
t
β
1
t
-
1
λ
min
⁡
(
A
*
A
)
]
-
1
∥
X
-
Y
∥
F
<
∥
X
-
Y
∥
F
,
which is impossible. Hence, X
=
Y.
(2) Leth
2
(
Z
)
=
[
(
A
-
1
)
*
(
Z
s
-
Q
)
A
-
1
]
1
/
t, where Z
∈
[
α
2
I
,
β
2
I
]. h
2
(
Z
) is continuous, and
(13)
h
2
(
α
2
I
)
≤
h
2
(
Z
)
≤
h
2
(
β
2
I
)
because (
A
-
1
)
*
(
α
2
s
I
-
Q
)
A
-
1
≤
(
A
-
1
)
*
(
Z
s
-
Q
)
A
-
1
≤
(
A
-
1
)
*
(
β
2
s
I
-
Q
)
A
-
1. By Lemmas 1 and 2 and Brouwer’s fixed-point theorem, it is sufficient to prove h
2
(
α
2
I
)
≥
α
2
I and h
2
(
β
2
I
)
≤
β
2
I in order for an HPD solution Z
∈
[
α
2
I
,
β
2
I
] to exist. The existence of such Z follows from inequalities
(14)
h
2
(
α
2
I
)
=
[
(
A
-
1
)
*
(
α
2
s
I
-
Q
)
A
-
1
]
1
/
t
≥
[
(
A
-
1
)
*
(
α
2
s
I
-
λ
max
⁡
(
Q
)
I
)
A
-
1
]
1
/
t
≥
[
(
λ
max
⁡
(
A
*
A
)
)
-
1
(
α
2
s
I
-
λ
max
⁡
(
Q
)
I
)
]
1
/
t
=
α
2
I
,
h
2
(
β
2
I
)
=
[
(
A
-
1
)
*
(
β
2
s
I
-
Q
)
A
-
1
]
1
/
t
≤
[
(
A
-
1
)
*
(
β
2
s
I
-
λ
min
⁡
(
Q
)
I
)
A
-
1
]
1
/
t
≤
[
(
λ
min
⁡
(
A
*
A
)
)
-
1
(
β
2
s
I
-
λ
min
⁡
(
Q
)
I
)
]
1
/
t
=
β
2
I
.
Next we prove the uniqueness ofZ under the additional condition that λ
min
⁡
(
A
*
A
)
>
s
β
2
s
-
1
(
t
α
2
t
-
1
)
-
1. Suppose (1) has two different HPD solutions Z and Y on [
α
2
I
,
β
2
I
]. Then
(15)
∥
Z
t
-
Y
t
∥
F
=
∥
(
A
-
1
)
*
(
Z
s
-
Y
s
)
A
-
1
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
∥
Z
s
-
Y
s
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
s
β
2
s
-
1
∥
Z
-
Y
∥
F
.
Moreover, if λ
min
⁡
(
A
*
A
)
>
s
β
2
s
-
1
(
t
α
2
t
-
1
)
-
1, applying the inequality ∥
Z
t
-
Y
t
∥
F
≥
t
α
2
t
-
1
∥
Z
-
Y
∥
F, we have
(16)
∥
Z
-
Y
∥
F
≤
(
t
α
2
t
-
1
λ
min
⁡
(
A
*
A
)
)
-
1
s
β
2
s
-
1
∥
Z
-
Y
∥
F
<
∥
Z
-
Y
∥
F
,
which is impossible. Hence, Y
=
Z.The maximal solution (see, e.g., [30, 31]) of (1) is defined as follows.Definition 5.
An HPD solutionX
M
∈
ℂ
n
×
n of (1) is the maximal solution if, for any HPD solution Y
∈
ℂ
n
×
n of (1), there is X
M
≥
Y.So the second term of Theorem4 implies that the maximal solution of (1) is on [
α
2
I
,
β
2
I
].Theorem 6.
Suppose thatλ
max
⁡
(
A
*
A
)
≤
(
s
/
t
)
(
t
/
(
t
-
s
)
λ
max
⁡
(
Q
)
)
(
s
-
t
)
/
s and λ
min
⁡
(
A
*
A
)
>
s
β
2
s
-
1
(
t
α
2
t
-
1
)
-
1; then (1) has a maximal solution X
max
⁡
∈
[
α
2
I
,
β
2
I
] which can be computed by
(17)
X
i
=
[
(
A
-
1
)
*
(
X
i
-
1
s
-
Q
)
A
-
1
]
1
/
t
,
i
=
1,2
,
…
.
with the initial value X
0
=
β
2
I.Proof.
Letξ
=
(
t
α
2
t
-
1
λ
min
⁡
(
A
*
A
)
)
-
1
s
β
2
s
-
1; then ξ
<
1. From the proof of Theorem 4 (2),
(18)
t
α
2
t
-
1
∥
X
i
+
1
-
X
i
∥
F
≤
∥
X
i
+
1
t
-
X
i
t
∥
F
=
∥
(
A
-
1
)
*
(
X
i
s
-
X
i
-
1
s
)
A
-
1
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
∥
X
i
s
-
X
i
-
1
s
∥
F
≤
(
λ
min
⁡
(
A
*
A
)
)
-
1
s
β
2
s
-
1
∥
X
i
-
X
i
-
1
∥
F
.
Then
(19)
∥
X
i
+
1
-
X
i
∥
F
≤
ξ
∥
X
i
-
X
i
-
1
∥
F
≤
ξ
i
∥
X
1
-
X
0
∥
F
,
which indicates the convergence of matrix series {
X
0
,
X
1
,
X
2
,
…
}, generated by (17).
SetX
0
=
β
2
I. Assuming X
i
∈
[
α
2
I
,
β
2
I
], then from inequalities (14) we have
(20)
α
2
I
≤
h
(
α
2
I
)
≤
X
i
+
1
=
[
(
A
-
1
)
*
(
X
i
s
-
Q
)
A
-
1
]
1
/
t
≤
h
(
β
2
I
)
≤
β
2
I
.
That means, for any i
=
0,1
,
2
,
…
,
X
i
∈
[
α
2
I
,
β
2
I
]. By Theorem 4 (2), we can see that X
max
⁡
=
lim
⁡
i
→
+
∞
X
i is the unique HPD solution of (1) on [
α
2
I
,
β
2
I
].
Now we prove the maximality ofX
max
⁡. Suppose that X is an arbitrary HPD solution of (1); then X
0
≥
X, and Theorem 3 implies X
0
t
≥
X
t (since X
0
=
β
2
I). Assuming that X
i
t
≥
X
t, Lemma 1 with s
/
t
<
1 implies
(21)
X
i
+
1
t
=
(
A
-
1
)
*
[
(
X
i
t
)
s
/
t
-
Q
]
A
-
1
≥
(
A
-
1
)
*
[
(
X
t
)
s
/
t
-
Q
]
A
-
1
=
X
t
.
Then X
max
⁡
t
=
lim
⁡
i
→
+
∞
X
i
t
≥
X
t, which implies that X
max
⁡
≥
X by the Löwner-Heinz inequality.Note that similar iteration formula ever appeared in some papers such as [20, 21] for other nonlinear matrix equations. Here we firstly proved that the iteration form (17) preserves the maximality of X
i over all HPD solutions of (1).


## 2.2.  Unique Solution of (1) with s
≥
t

Ifs
>
t, Lee and Lim [20, Theorem 9.4] show that (1) always has a unique HPD solution, denoted by X
u. Now we give an upper bound and a lower bound of X
u and suggest an iteration method for computing X
u.As defined in (3), g
1
(
x
) and g
2
(
x
) with s
>
t have unique positive roots, denoted by γ
1 and γ
2, respectively.Sinceg
1
(
λ
(
X
u
)
)
≤
0 and g
2
(
λ
(
X
u
)
)
≤
0, γ
2
≤
λ
(
X
u
)
≤
γ
1.Theorem 7.
Ifs
>
t, (1) has a unique HPD solution X
u
∈
[
γ
2
I
,
γ
1
I
]. Let X
0
=
γ
1
I or γ
2
I, then matrix series {
X
0
,
X
1
,
X
2
,
…
} generated by
(22)
X
i
=
(
Q
+
A
*
X
i
-
1
t
A
)
1
/
s
,
i
=
0,1
,
2
,
…
will converge to X
u.Proof.
We only need to prove the convergence of matrix series{
X
0
,
X
1
,
X
2
,
…
}. Set X
0
=
γ
1
I. From (22) we have
(23)
X
1
=
(
Q
+
γ
1
t
A
*
A
)
1
/
s
≤
(
λ
max
⁡
(
Q
)
+
γ
1
t
λ
max
⁡
(
A
*
A
)
)
1
/
s
I
=
γ
1
I
,
and then X
1
s
≤
X
0
s. Assuming that X
i
s
≤
X
i
-
1
s,
(24)
X
i
+
1
s
=
Q
+
A
*
X
i
t
A
=
Q
+
A
*
(
X
i
s
)
t
/
s
A
≤
Q
+
A
*
(
X
i
-
1
s
)
t
/
s
A
=
X
i
s
.
Then for any i
=
0,1
,
2
,
…, we have X
i
+
1
s
≤
X
i
s and then X
i
+
1
≤
X
i by Löwner-Heinz inequality. On the other hand, X
0
≥
γ
2
I implies X
i
≥
γ
2
I for any i
=
0,1
,
2
,
…, because if X
i
-
1
≥
γ
2
I, then
(25)
X
i
=
(
Q
+
A
*
X
i
-
1
t
A
)
1
/
s
≥
(
Q
+
γ
2
t
A
*
A
)
1
/
s
≥
(
λ
min
⁡
(
Q
)
+
γ
2
t
λ
min
⁡
(
A
*
A
)
)
1
/
s
I
=
γ
2
I
.
Then {
X
0
,
X
1
,
X
2
,
…
} with X
0
=
γ
1
I is a decreasingly monotone matrix series with a lower bound γ
2
I. Similarly we can prove that {
X
0
,
X
1
,
X
2
,
…
} generated by (22) with X
0
=
γ
2
I is an increasingly monotone matrix series with an upper bound γ
1
I. Therefore, the convergence of {
X
0
,
X
1
,
X
2
,
…
} has been proved.From the above proof, we can see that the iteration form (22) preserves the minimality (X
0
=
γ
1
I) or maximality (X
0
=
γ
2
I) of X
i in process.Ifs
=
t, (1) can be reduced to a linear matrix equation Y
-
A
*
Y
A
=
Q, which is the discrete-time algebraic Lyapunov equation (DALE) or Hermitian Stein equation, [1, Page 5], assuming that Y
=
X
s. It is well known that if A is d-stable (see [1]), Y
-
A
*
Y
A
=
Q has a unique solution, and matrix series {
Y
0
,
Y
1
,
Y
2
,
…
}, generated by Y
i
+
1
=
Q
+
A
*
Y
i
A with an initial value Y
0, will converge to the unique solution. Besides, it is not difficult to get an expression of the unique solution X
u
=
(
∑
j
=
0
∞
(
A
*
)
j
Q
A
j
)
1
/
s, applying [32, Theorem 1, Section 13.2), [1, Theorem 1.1
.
18], and the results in Section 6.4 in [28].Now we have presented the solvability theory of the self-adjoint polynomial matrix equation (1) in three cases. A general iterative algorithm for its maximal solution (s
<
t) or unique solution (s
≥
t) will be given in Section 4. Before it, we study the algebraic perturbation of the maximal or unique solution of (1).


## 3. Algebraic Perturbation Analysis

In this section, we present the algebraic perturbation analysis of the HPD solution of (1) with respect to the perturbation of its coefficient matrices. Similar to [30], we define the perturbed matrix equation of (1) as
(26)
X
^
s
-
A
^
*
X
^
t
A
^
=
Q
^
,
where A
^
=
A
+
Δ
A
∈
ℂ
n
×
n and Q
^
=
Q
+
Δ
Q
∈
ℂ
n
×
n. We always suppose that (1) has a maximal (or unique) solution, denoted by X
M
∈
[
α
2
I
,
β
2
I
], and (26) has a maximal (or unique) solution, denoted by X
^
M
∈
[
α
^
2
I
,
β
^
2
I
].Now we present the perturbation bound forX
M when s
≠
t. Define a function τ:
(27)
τ
(
α
,
β
)
=
s
α
s
-
1
-
t
β
t
-
1
∥
A
∥
2
2
,
(
α
,
β
)
∈
ℝ
2
.Theorem 8.
Letɛ
>
0 be an arbitrary real number, and τ
(
α
^
2
,
β
^
2
)
≥
0. If
(28)
∥
Δ
A
∥
F
<
(
∥
A
∥
2
2
+
2
ɛ
3
τ
(
α
^
2
,
β
^
2
)
∥
X
^
M
∥
2
-
t
)
1
/
2
-
∥
A
∥
2
,
∥
Δ
Q
∥
F
<
1
3
τ
(
α
^
2
,
β
^
2
)
ɛ
,
then
(29)
∥
X
^
M
-
X
M
∥
F
<
ɛ
.Proof.
It is easy to induce that(30)
∥
X
^
M
s
-
X
M
s
∥
F
≥
(
∑
k
=
0
s
-
1
α
^
2
s
-
1
-
k
α
2
k
)
∥
X
^
M
-
X
M
∥
F
≥
s
α
^
2
s
-
1
∥
X
^
M
-
X
M
∥
F
,
∥
X
^
M
t
-
X
M
t
∥
F
≤
(
∑
k
=
0
t
-
1
β
^
2
t
-
1
-
k
β
2
k
)
∥
X
^
M
-
X
M
∥
F
≤
t
β
^
2
t
-
1
∥
X
^
M
-
X
M
∥
F
.
Then from (1) and (26), we have
(31)
τ
(
α
^
2
,
β
^
2
)
∥
X
^
M
-
X
M
∥
F
≤
2
∥
A
∥
2
∥
X
^
M
∥
2
t
∥
Δ
A
∥
F
+
∥
X
^
M
∥
2
t
∥
Δ
A
∥
F
2
+
∥
Δ
Q
∥
F
.
Since τ
(
α
^
2
,
β
^
2
)
>
0,
(32)
∥
X
^
M
-
X
M
∥
F
≤
(
τ
(
α
^
2
,
β
^
2
)
)
-
1
(
2
∥
A
∥
2
∥
X
^
M
∥
2
t
∥
Δ
A
∥
F
+
∥
X
^
M
∥
2
t
∥
Δ
A
∥
F
2
+
∥
Δ
Q
∥
F
)
.
Then for an arbitrary ɛ
>
0, if ∥
Δ
A
∥
F
<
(
∥
A
∥
2
2
+
(
2
ɛ
/
3
)
τ
(
α
^
2
,
β
^
2
)
∥
X
^
M
∥
2
-
t
)
1
/
2
-
∥
A
∥
2 and ∥
Δ
Q
∥
F
<
(
1
/
3
)
τ
(
α
^
2
,
β
^
2
)
ɛ, we have (29).Ifs
=
t, for an arbitrary ɛ
>
0, define
(33)
ϱ
(
ɛ
)
=
∥
A
∥
2
+
(
∥
A
∥
2
2
+
2
ɛ
3
ρ
)
1
/
2
,
where
(34)
ρ
=
∥
X
^
M
∥
2
s
[
s
α
^
2
s
-
1
(
1
-
∥
A
∥
2
2
)
]
-
1
.Theorem 9.
Letɛ
>
0 be an arbitrary real number, and ∥
A
∥
2
<
1. If
(35)
∥
Δ
A
∥
F
<
2
ɛ
3
(
ρ
ϱ
(
ɛ
)
)
-
1
,
∥
Δ
Q
∥
F
<
ɛ
3
ρ
∥
X
^
M
∥
2
s
,
then
(36)
∥
X
^
M
-
X
M
∥
F
<
ɛ
.Proof.
Similar to the proof of Theorem8, we can induce that
(37)
(
1
-
∥
A
∥
2
2
)
∥
X
^
M
s
-
X
M
s
∥
F
≤
2
∥
A
∥
2
∥
X
^
M
∥
2
s
∥
Δ
A
∥
F
+
∥
X
^
M
∥
2
s
∥
Δ
A
∥
F
2
+
∥
Δ
Q
∥
F
.
Then
(38)
∥
X
^
M
s
-
X
M
s
∥
F
≤
(
1
-
∥
A
∥
2
2
)
-
1
(
2
∥
A
∥
2
∥
X
^
M
∥
2
s
∥
Δ
A
∥
F
+
∥
X
^
M
∥
2
s
∥
Δ
A
∥
F
2
+
∥
Δ
Q
∥
F
)
.
With the help of (30) and (34), (38) implies
(39)
∥
X
^
M
-
X
M
∥
F
≤
ρ
(
∥
Δ
A
∥
F
+
2
∥
A
∥
2
∥
Δ
A
∥
F
+
∥
Δ
Q
∥
F
)
.
Then if ∥
Δ
A
∥
F
<
(
2
ɛ
/
3
)
(
ρ
ϱ
(
ɛ
)
)
-
1 and ∥
Δ
Q
∥
F
<
(
ɛ
/
3
ρ
)
∥
X
^
M
∥
2
s, we have (36).Theorems8 and 9 make sure that the perturbation of X
M can be controlled if Δ
A and Δ
Q have a proper upper bound.


## 4. Algorithm and Numerical Experiments

In this section we give a general iterative algorithm for the maximal or unique solutions of (1) and two numerical experiments. All reported results were obtained using MATLAB-R2012b on a personal computer with 2.4 GHz Intel Core i7 and 8 GB 1600 MHz DDR3.Example 10.
Let matricesA
=
rand
(
100
)
×
1
0
-
2 and Q
=
eye
(
100
). With tol
=
1
0
-
12 and not more than 200 iterations, we apply Algorithm 1 to compute the maximal or unique HPD solutions of (1) with s
≠
t and compare the results with those by the iteration method from [33] (denoted by MONO in Table 1).
Table1 shows iterations, CPU times before convergence, and the residues of the computed HPD solution X, defined by
(40)
e
(
s
,
t
)
=
∥
X
s
-
A
*
X
t
A
-
Q
∥
F
∥
[
A
,
Q
]
∥
F
.Table 1
Iteration, CPU time (seconds) and residue for solving (1) with s
≠
t.
(
s
,
t
)
Algorithm1
MONO
Ite
CPU
Res
Ite
CPU
Res
(
2,1
)
9
0.0541
4.5275
e
-
13
200
2.1031
0.0016
(
1,2
)
200
1.0275
2.0297
e
-
07
—
—
—
(
8,5
)
10
0.0716
5.9909
e
-
13
200
2.2284
0.0034
(
5,8
)
200
1.1048
3.1059
e
-
05
—
—
—
(
30,15
)
9
0.0743
5.2317
e
-
13
200
2.3051
0.0029
(
15,30
)
200
1.2865
2.0838
e
-
08
—
—
—
(
300,150
)
10
0.0886
7.9960
e
-
13
200
2.2683
0.0031
(
150,300
)
200
1.4187
2.8384
e
-
07
—
—
—Algorithm 1:Given matrices A
,
Q
∈
ℂ
n
×
n and positive integers s
,
t.
Step  1. Compute  λ
max
⁡
(
A
*
A
), λ
min
⁡
(
A
*
A
), λ
max
⁡
(
Q
), λ
min
⁡
(
Q
).
Step  2. Input (3).
Step  3. If  s
<
t, run Steps  4-5; if  t
<
s, run Steps  6-7; otherwise, run Steps  8-9.
Step  4. Compute the roots  α
1, α
2  of  g
1
(
x
), and  β
1, β
2  of  g
2
(
x
), respectively.
Step  5. Let  X
0
=
β
2
I, run (17).
Step  6. Compute the root  γ
1  of  g
1
(
x
)  and the root  γ
2  of  g
2
(
x
), respectively.
Step  7. Let  Z
0
=
γ
1
I, run (22).
Step  8. Compute the root  δ
1  of  g
1
(
x
)  and the root  δ
2  of  g
2
(
x
), respectively.
Step  9. If  λ
max
⁡
(
A
*
A
)
<
1  and  δ
1
≥
δ
2, then let  X
0
=
δ
1
I  and run (22).From Table1, we can see that it takes more iterations and CPU times to solve the maximal solution of (1) with s
<
t than to solve the unique solution of (1) with s
>
t. At the same time, the accuracy of the latter is better than the former. MONO can not be used to solve (1) with s
<
t, and it costs more iterations and CPU times than Algorithm 1 when solving (1) with s
>
t.Now we use Example 4.1 of [33] to test our method.Example 11.
LetA
=
0.5
B
/
∥
B
∥
∞ with B
=
[
B
i
j
]
n
×
n
,
b
i
j
=
i
+
j
+
1 and let Q
=
eye
(
n
), with n
=
100. We solve (1) with s
=
t and with two different initial solutions. The iterations, CPU times, and the residues of the computation are reported in Table 2.Table 2
Iteration, CPU time (seconds) and residue for solving (1) with s
=
t and different initial solutions.
(
s
,
t
,
X
0
)
Algorithm1
MONO
Ite
CPU
Res
Ite
CPU
Res
(
1,1
,
δ
1
I
n)
20
0.0223
3.4947
e
-
13
20
0.0202
3.4947
e
-
13
(
1,1
,
δ
2
I
n)
31
0.0258
7.3027
e
-
13
31
0.0305
7.3027
e
-
13
(
2,2
,
δ
1
I
n)
20
0.1170
8.9978
e
-
13
200
2.6421
0.0037
(
2,2
,
δ
2
I
n)
43
0.5475
9.6421
e
-
13
200
2.7224
0.0037
(
10,10
,
δ
1
I
n)
29
0.1890
2.9296
e
-
13
200
2.9717
0.0059
(
10,10
,
δ
2
I
n)
157
3.0859
7.1154
e
-
13
200
2.9788
0.0059Table2 shows that for Algorithm 1 the choice X
0
=
δ
1
I
n is better than X
0
=
δ
2
I
n. When s and t rise, MONO might lose its efficiency. It seems not proper to apply the iteration method designed for Y
-
A
*
Y
t
/
s
A
=
Q with Y
=
X
s to solve X
s
-
A
*
X
t
A
=
Q, although they are equivalent to each other in theory.


## 5. Conclusion

In this paper, we considered the solvability of the self-adjoint polynomial matrix equation (1). Sufficient conditions were given to guarantee the existence of the maximal or unique HPD solutions of (1). The algebraic perturbation analysis including perturbation bounds was also developed for (1) under the perturbation of given coefficient matrices. At last a general iterative algorithm with maximality preserved in process was presented for the maximal or unique solution with two numerical experiments reported.



---

*Source: 681605-2014-05-07.xml*