# The Inversion-Free Iterative Methods for Solving the Nonlinear Matrix EquationX+AHX-1A+BHX-1B=I

Authors: Na Huang; Changfeng Ma
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We present two inversion-free iterative methods for computing the maximal positive definite solution of the equationX+AHX-1A+BHX-1B=I. We prove that the sequences generated by the two iterative schemes are monotonically increasing and bounded above. We also present some numerical results to compare our proposed methods with some previously developed inversion-free techniques for solving the same matrix equation.


---

## Body

## 1. Introduction

In this paper, we consider the nonlinear matrix equation:(1)X+AHX-1A+BHX-1B=I,
where A,B∈ℂn×n, I is the identity matrix, and a Hermitian positive definite solution X is required.Specifically, ifB=0, the nonlinear matrix equation (1) reduces to
(2)X+AHX-1A=I.
The nonlinear matrix equation (2) has many applications in nano research, control theory, dynamic programming, statistics, ladder networks, stochastic filtering, and so forth (see [1–7]). The special case (2) has been widely studied by some authors (see [8–27]). Different iterative methods for computing the positive definite solutions of (2) have been proposed, for example, the fixed-point iteration (see [15]), structure-preserving doubling algorithm (see [7, 16]), and some inversion-free iterations (see [17, 20, 23, 27]). Among them, structure-preserving doubling algorithm has been seen as one of the most efficient algorithms as it has quadratic convergence rate.However, very little research has been done on the solutions to (1) in the case B≠0. In [28], Long et al. stated the application background of (1) and presented some conditions for the existence of the positive definite solution of this equation. Moreover, they proposed some iterative algorithms to find the positive definite solution. Popchev et al. made a complete perturbation analysis of (1) (see [29]). In [30], Liu and Chen considered the nonlinear matrix equation Xs+AHX-t1A+BHX-t2B=Q. They studied the existence of the positive definite solution of this equation.Motivated and inspired by the works mentioned above, in this paper, we propose two new inversion-free iterative methods for obtaining the maximal positive definite solution of (1). We prove that the sequences generated by the two iterative schemes are monotonically increasing and bounded above. In addition, we also provide some numerical results to illustrate the effectiveness of the proposed algorithm.Throughout this paper, we use the following notations: forA∈ℂn×n, we write AH, A-1 and ∥A∥ to denote the conjugate transpose, the inverse, and the Frobenius norm of the matrix A, respectively. For any A=(aij), B=(bij), we write A≥B (or B≤A) if A-B is a Hermitian positive semidefinite matrix. And we write A>B (or B<A) if A-B is a Hermitian positive definite matrix. We use 0 to denote the zero matrix of size implied by context and I to denote the identity matrix of size implied by context.This paper is organized as follows. In Section2, we present two new iterative methods to solve the nonlinear matrix equation (1). In Section 3, the convergence analysis of the proposed methods is given. Some numerical experiments are reported in Section 4. Finally, we conclude this paper in Section 5.


## 2. New Inversion-Free Iterative Methods

In this section, we present two new inversion free iterative algorithms for solving problem (1). Let Y=X-1; then the nonlinear matrix equation (1) is equivalent to
(3)Y-1+AHYA+BHYB=I.
Obviously, if Y* is a Hermitian positive definite solution of (3), we have 0<Y*-1≤I. That is, Y*≥I.Premultiplying and postmultiplying byY on (3) simultaneously, we get
(4)Y-Y(I-AHYA-BHYB)Y=0.
Adding Y to both sides of the above equation, we have
(5)Y=2Y-Y(I-AHYA-BHYB)Y.
Obviously, Y solves (5) if Y is a solution of (3). Conversely, if Y is a nonsingular solution of (5), Y solves (3) as well.Thus, we just need to solve the matrix equation (5) if we want to get a Hermitian positive definite solution of (3). By this point, we present the following iterative scheme.Algorithm 1 (an inversion-free iterative algorithm for (1)).
Step 1. Input the matrix A,B∈ℂn×n. Take initial matrix Y0=I and tolerance error ɛ≥0. Set k:=0.
Step 2. Obtain Yk+1 by the following iterative scheme:
(6)Yk+1=2Yk-YkZkYk,
where Zk=I-AHYkA-BHYkB.
Step 3. Stop if ∥Yk+1-Yk∥F≤ɛ. Otherwise, k:=k+1, go to Step 2.Remark 2.
IfB=0, Algorithm 1 reduces to Algorithm 2.1 in [23] with α=1 and Q=I. Moreover, as Y0=I is a Hermitian matrix, from (6) we know that Yk is also a Hermitian matrix, for all k≥0.On the other hand, premultiplying and postmultiplying byY on (3), respectively, we have
(7)I+YAHYA+YBHYB=Y,I+AHYAY+BHYBY=Y.
Adding the above two equations, we can get
(8)2I+YAHYA+YBHYB+AHYAY+BHYBY=2Y.
By some simple calculating, we obtain
(9)Y=I+12×[Y(AHYA+BHYB)+(AHYA+BHYB)Y].
By the above analysis, we know that if Y is a solution of (3), Y is a solution of (9). Now we prove that a Hermitian positive definite solution of (9) is also a solution of (3).Theorem 3.
LetY be a Hermitian positive definite solution of the nonlinear matrix equation (9). Then Y is also a positive definite solution of the nonlinear matrix equation (3).Proof.
By the nonlinear matrix equation (9), we have
(10)Y(Y-1+AHYA+BHYB-I)+(Y-1+AHYA+BHYB-I)Y=0.
This implies that Y-1+AHYA+BHYB-I is a solution of the matrix equation YH+HY=0, where H∈ℂn×n is unknown. Since Y is positive definite, Y and -Y have no common eigenvalue and the matrix equation YH+HY=0 has a unique solution (see [31]). As 0 solves the equation YH+HY=0, we must have Y-1+AHYA+BHYB-I=0. Namely, Y is a positive definite solution of (3).Thus, we just need to solve the matrix equation (9) if we want to get a Hermitian positive definite solution of (3). By this point, we present the following iterative scheme.Algorithm 4 (another inversion free iterative algorithm).
Step
1. Input the matrix A,B∈ℂn×n. Take initial matrix Y0=I and tolerance error ɛ≥0. Set k:=0.
Step
2. Obtain Yk+1 by the following iterative scheme:
(11)Zk=12Yk(AHYkA+BHYkB),Yk+1=I+ZkH+Zk.
Step
3. Stop if ∥Yk+1-Yk∥F≤ɛ. Otherwise, k:=k+1 go to Step 2.Obviously, for allk≥0, sequence {Yk} generated by Algorithm 4 with the initial matrix Y0=I are all Hermitian matrices.


## 3. Convergence Analysis

In this section, we will prove that the sequences{Yk} generated by Algorithms 1 and 4 with the initial matrix Y0=I converge to the minimal positive definite solution of (3). In the first place, we introduce the following lemmas.Lemma 5 (see [28]).
If (1) has a positive definite solution X, then AHA+BHB<I.Lemma 6 (see [23]).
IfC and P are Hermitian matrices of the same order with P>0, then 2C-CPC≤P-1.Lemma 7.
IfM,P∈ℂn×n are both Hermitian positive semidefinite, then MP+PM is a Hermitian positive semidefinite matrix as well.Proof.
Obviously,MP+PM is a Hermitian matrix. If one of M and P is positive definite, without loss of generality, suppose that M>0. Then by the assumption of the lemma, we know that M1/2, P1/2 are well defined and M1/2>0, P1/2≥0. Then we get
(12)MP+PM=M1/2M1/2P+PM1/2M1/2=M1/2(M1/2PM-(1/2)+M-(1/2)PM1/2)M1/2≥0.
Assume that neither of M and P is positive definite. Then for β>0, we have M+βI>0. Thus by the above analysis, we have (M+βI)P+P(M+βI)≥0. Let β→0+; we get MP+PM≥0. This completes the proof.Now we are in a position to prove that{Yk} generated by Algorithm 1 with the initial matrix Y0=I converges to the minimal positive definite solution of (3).Theorem 8.
The nonlinear matrix equation (3) has a positive definite solution and the sequence {Yk} is generated by Algorithm 1 with the initial matrix Y0=I. Let Y~ be the minimal positive definite solution of (3). Then the sequence {Yk} is well defined, Y0≤Y1≤Y2≤⋯<Yk≤⋯≤Y~, and
(13)limk→∞Yk=Y~.Proof.
LetY* be any positive definite solution of (3). Firstly, we will prove 0<Yk≤Yk+1≤Y* for all k≥0 by mathematical induction.
Fork=0, we have Y0=I>0. By (6) we have
(14)Y1=2I-I+AHA+BHB=I+AHA+BHB≥I=Y0.
On the other hand, by Lemma 5, we have I-AHA-BHB>0. This together with Lemma 6 and (3) yields
(15)Y1=2I-I(I-AHA-BHB)I≤(I-AHA-BHB)-1≤(I-AHY*A-BHY*B)-1=Y*,
where the second inequality follows from the fact that Y*≥I. Hence 0<Yk≤Yk+1≤Y* holds for k=0.
Assume that0<Yk≤Yk+1≤Y* holds for k=i≥0. Since
(16)Zi+1=I-AHYi+1A-BHYi+1B≥I-AHY*A-BHY*B=Y*-1>0,
by (6), Lemma 6, and the fact that Yi+1>0, we get
(17)Yi+2=2Yi+1-Yi+1Zi+1Yi+1≤Zi+1-1≤Y*.
Moreover, it follows from (6) that
(18)Yi+2-Yi+1=Yi+1-Yi+1Zi+1Yi+1=Yi+1(Yi+1-1-Zi+1)Yi+1.
As Zi=I-AHYiA-BHYiB≥I-AHYi+1A-BHYi+1B=Zi+1>0, this together with (6) and Lemma 6 follows that
(19)Yi+1=2Yi-YiZiYi≤Zi-1≤Zi+1-1.
This implies that Yi+1-1≥Zi+1. Thus, by (18) and the fact that Yi+1>0, we obtain Yi+2≥Yi+1. Therefore, 0<Yk≤Yk+1≤Y* holds for k=i+1.
By the principle of mathematical induction,0<Yk≤Yk+1≤Y* is true for all k≥0. The sequence {Yk} is now well defined, monotonically increasing, and bounded above. Let limk→∞Yk=Y~. Then Y~ is a positive definite solution of the nonlinear matrix equation (3) by (6). Since Y~≤Y* for any positive definite solution Y* of (3), Y~ is the minimal positive definite solution of (3). This completes the proof.Remark 9.
LetX~ be the maximal positive definite solution of the nonlinear matrix equation (1). By the relationship between (1) and (3), we get that X~-1 is the minimal positive definite solution of (3). So from Theorem 8, we know that the sequence {Yk} generated by Algorithm 1 with the initial matrix Y0=I converges to the inverse of the maximal positive definite solution of (1).Now we consider the convergence theorem of Algorithm4.Theorem 10.
The nonlinear matrix equation (3) has a positive definite solution and the sequence {Yk} is generated by Algorithm 4 with the initial matrix Y0=I. Let Y~ be the minimal positive definite solution of (3). Then the sequence {Yk} is well defined, Y0≤Y1≤Y2<⋯≤Yk≤⋯≤Y~, and limk→∞Yk=Y~.Proof.
LetY* be any positive definite solution of (3). Firstly, we will prove 0<Yk≤Yk+1≤Y* for all k≥0 by induction.
Fork=0, we have Y0=I>0; then Y1=I+AHA+BHB≥I. On the other hand, by the fact that Y*≥I, (3), and Lemma 7, we get
(20)Y1=I+AHA+BHB≤I+AHY*A+BHY*B=I+12(AHY*AI+IAHY*A)+12(BHY*BI+IBHY*B)≤I+12(AHY*AY*+Y*AHY*A)+12(BHY*BY*+Y*BHY*B)=I+12(AHY*A+BHY*B)Y*+12Y*(AHY*A+BHY*B)=I+12(I-Y*-1)Y*+12Y*(I-Y*-1)=Y*.
Hence 0<Yk≤Yk+1≤Y* is true for k=0.
Assume that0<Yk≤Yk+1≤Y* holds for k=i≥0. Then by Lemma 7 we have
(21)Yi+1AHYi+1A+AHYi+1AYi+1≥YiAHYi+1A+AHYi+1AYi≥YiAHYiA+AHYiAYi.
Similarly, we get Yi+1BHYi+1B+BHYi+1BYi+1≥YiBHYiB+BHYiBYi. This together with (11) yields
(22)Yi+2=I+12(Yi+1AHYi+1A+Yi+1BHYi+1B+AHYi+1AYi+1+BHYi+1BYi+1)=I+12(Yi+1AHYi+1A+AHYi+1AYi+1)+12(Yi+1BHYi+1B+BHYi+1BYi+1)≥I+12(YiAHYiA+AHYiAYi)+12(YiBHYiB+BHYiBYi)=I+12(YiAHYiA+YiBHYiB+AHYiAYi+BHYiBYi)=I+12(Zi+ZiH)=Yi+1.
On the other hand, by Lemma 7 we obtain
(23)Yi+1AHYi+1A+AHYi+1AYi+1≤Y*AHYi+1A+AHYi+1AY*≤Y*AHY*A+AHY*AY*.
Similarly, we get
(24)Yi+1BHYi+1B+BHYi+1BYi+1≤Y*BHY*B+BHY*BY*.
Using the above inequalities, we can deduce that
(25)Yi+2=I+12(Yi+1AHYi+1A+AHYi+1AYi+1)+12(Yi+1BHYi+1B+BHYi+1BYi+1)≤I+12(Y*AHY*A+AHY*AY*)+12(Y*BHY*B+BHY*BY*)=I+12Y*(AHY*A+BHY*B)+12(AHY*A+BHY*B)Y*=I+12Y*(I-Y*-1)+12(I-Y*-1)Y*=Y*,
where the first equality follows from (11) and the third equality follows from (3). Hence, 0<Yk≤Yk+1≤Y* holds for k=i+2.
Thus, by the principle of induction,0<Yk≤Yk+1≤Y* is true for all k≥0. The sequence {Yk} is now well defined, monotonically increasing, and bounded above. Let limk→∞Yk=Y~. Then Y~ is a positive definite solution of the nonlinear matrix equation (3) by (11) and Theorem 3. Since Y~≤YH for any positive definite solution YH of (3), Y~ is the minimal positive definite solution of (3). This completes the proof.


## 4. Numerical Experiments

In this section, we will give some numerical examples to support our Algorithms1 and 4. All experiments were run on a PC with Pentium(R) Dual-Core CPU E5800 @2.40 GHz. All the programming is implemented in MATLAB R2011b (7.13). We report the number of required iterations (Iter.), the norm of the residual (Res.) when the process is stopped, the required CPU time (CPU), and the number of matrix-matrix (MM) products required. In our implementation, we stop all considered algorithms when ∥Yk+1-Yk∥F≤10-10 with k≥1. We compare our Algorithm 1 (A1) and Algorithm 4 (A2) with the following inverse-free methods for solving (1).(i)
In [28], for finding positive definite solution of (1), Long et al. proposed the following iteration:
(26)B1:{X0=I,Y0=I,Xk+1=I-AHYkA-BHYkB,Yk+1=Yk(2I-XkYk).(ii)
In [30], for solving positive definite solution of (1), Liu and Chen proposed the following iteration:
(27)B2:{X0=I,Y0=I,Yk+1=Yk(2I-XkYk),Xk+1=I-AHYk+1A-BHYk+1B.Example 11.
For the first experiment, we consider (1) when A and B are given as in Example 4.1 from [28]:
(28)A=(0.010-0.150-0.2590.0150.212-0.0640.025-0.0690.138),B=(0.160-0.0250.020-0.025-0.288-0.0600.004-0.016-0.120).
We could obtain the maximal solution X+ (the first 4 digits) by the iterative schemes A1-A2 and B1–B3. The maximal solution is
(29)X+≈(0.9718-0.0049-0.0046-0.00490.8144-0.0388-0.0046-0.03880.8836).
Our numerical results are reported in Table 1.Table 1
Numerical results of Example11.
Scheme
Iter.
CPU
Res.
MM
A1
14
0.0006
3.5756
e
-
012
84
A2
20
0.0008
2.3117
e
-
011
100
B1
26
0.0011
4.7298
e
-
011
156
B2
15
0.0007
6.7304
e
-
013
90Example 12.
In this test, the matricesA and B are given as in Example 4.2 from [28]:
(30)A=1680(40252335662532274521232728162435451652656621246569),B=1400(11212325322131604233236034182625421844303233263050).
We will obtain the maximal solution X+ (the first 4 digits) by the iterative schemes A1-A2 and B1–B3. The maximal solution is
(31)X+=(0.9437-0.0642-0.0530-0.0691-0.0772-0.06420.9063-0.0739-0.0833-0.0907-0.0530-0.07390.9297-0.0717-0.0763-0.0691-0.0833-0.07170.9080-0.0970-0.0772-0.0907-0.0763-0.09700.8889).
Our numerical results are reported in Table 2.Table 2
Numerical results of Example12.
Scheme
Iter.
CPU
Res.
MM
A1
48
0.0027
2.2801
e
-
011
288
A2
83
0.0040
4.4924
e
-
011
415
B1
92
0.0049
6.4280
e
-
011
552
B2
49
0.0028
1.4600
e
-
011
294Example 13.
In this experiment we solve (1) with the matrices A and B as follows:
(32)A=120(200100120010003010100201101030010012),B=150(216057347130092478853001250217400149).
We could obtain the maximal solution X+ (the first 4 digits) by the iterative schemes A1-A2 and B1–B3. The unique positive definite solution is(33)X+≈(0.9301-0.0443-0.0367-0.0202-0.0411-0.0521-0.04430.9104-0.0395-0.0271-0.0603-0.0781-0.0367-0.03950.9234-0.0110-0.0566-0.0430-0.0202-0.0271-0.01100.9755-0.0224-0.0374-0.0411-0.0603-0.0566-0.02240.9064-0.0858-0.0521-0.0781-0.0430-0.0374-0.08580.8486).The numerical results are listed in Table 3.Table 3
Numerical results of Example13.
Scheme
Iter.
CPU
Res.
MM
A1
28
0.0016
1.4769
e
-
011
168
A2
47
0.0025
2.8856
e
-
011
235
B1
54
0.0032
4.4578
e
-
011
324
B2
29
0.0018
6.6485
e
-
012
174Example 14.
In this test, the matricesA and B are provided with the following forms:
(34)A=110In+12nRn,B=120In+1n2Sn,
where In is n×n identity matrix and Rn=(rij)n×n and Sn=(skl)n×n are randomly generated with entries rij∈(0,1) and skl∈(-1,1). For different matrix dimension (DIM) n, the numerical results are reported in Table 4.Table 4
Numerical results of Example14.
DIM
Scheme
Iter.
CPU
Res.
MM
64
A1
16
0.0050
1.4358
e
-
011
96
A2
24
0.0070
1.4344
e
-
011
120
B1
32
0.0419
3.1053
e
-
011
192
B2
17
0.0064
3.6219
e
-
012
102
128
A1
17
0.0324
4.9074
e
-
012
102
A2
24
0.0620
1.9656
e
-
011
120
B1
32
0.1036
4.0817
e
-
011
192
B2
18
0.0454
1.2594
e
-
012
108
256
A1
17
0.3721
4.4572
e
-
012
102
A2
24
0.4954
1.7529
e
-
011
120
B1
32
0.6902
3.7397
e
-
011
192
B2
18
0.4155
1.1373
e
-
012
108
512
A1
17
2.5991
5.1113
e
-
012
168
A2
24
2.9816
2.0378
e
-
011
235
B1
32
4.4817
4.2332
e
-
011
324
B2
18
2.7676
1.3148
e
-
012
174
1024
A1
17
20.2298
4.9186
e
-
012
168
A2
24
26.0464
1.9494
e
-
011
235
B1
32
36.6167
4.0910
e
-
011
324
B2
18
21.8226
1.2626
e
-
012
174From the above experiments, we find that Algorithm1 has an advantage in the number of iterations and CPU time. Although Algorithm 4 performs worse than B2, it performs better than B1. In Example 14, we can see that the iterations of Algorithms 1 and 4 are invariant with the dimension, which are the same as the performance of B1 and B2. In a word, our algorithms are promising.


## 5. Conclusion

In this paper, we propose two inversion-free iterative algorithms for obtaining the maximal positive definite solution of the equationX+AHX-1A+BHX-1B=I. We prove that the sequences generated by the proposed iterative schemes are monotonically increasing and bounded above. Some numerical results are also reported in the paper, which confirm the good theoretical properties of our approach. Although we prove that the sequence {Yk} generated by Algorithms 1 and 4 with the initial matrix Y0=I converges to the minimal positive definite solution of (3) (or the maximal positive definite solution of (1)), we do not yet give the analysis on the convergence rate of the two methods, which is our work in the future.



---

*Source: 843785-2013-12-03.xml*