Fixed-point accelerated iterative method for solving a nonlinear matrix equation

Abstract

Nonlinear matrix equations $X^p=A+\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i$ have extensive applications in control theory, ladder networks, dynamic programming, and stochastic filtering. In this paper a fixed-point acceleration iteration algorithm is proposed and, based on the basic characteristics of the Thompson metric space, the convergence and error estimator of the proposed algorithm are proved. Numerical comparison experiments show that the proposed algorithm is feasible and effective.

Introduction

Jin and Zhai in [1] discussed using fixed-point iterative algorithms to compute the unique solution of the nonlinear matrix equation

1

$X^p=A+\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i,$ where p and m are positive integer, $M_i(i=1,2,\dots ,m)$ are $n\times n$ nonsingular matrices, A and B are $n\times n$ positive definite matrices. In fact, the nonlinear matrix equation (1) is the generalized version of the nonlinear matrix equation

2

$X^p=A+M^{\ast }{(B+X^{-1})}^{-1}M$ studied by [2], the nonlinear matrix equation

3

$X^p-M^{\ast }XM=Q$ stuidied by [3–6], and the more related matrix equations like $X^n=MX{M}^{\ast }$ and $X^n=A+M{X}^{-1}{M}^{\ast }$ treated in [7–10].

If $p=1$, the matrix equation (2) is a discrete algebraic Riccati equation, which often arises in control theory, ladder networks, dynamic programming, stochastic filtering, see [11–14] and the references therein. It has been proved that a unique positive definite solution exists if A and B are positive definite matrices. For the case $p=1$, the matrix equation (3) is the famous Stein equation that is of great importance in signal processing, system and control theory, and many others [15], and it has a unique positive definite solution if $\rho (M{M}^{\ast })<1$, where $\rho (.)$ denotes the spectral radius. The existence and uniqueness of the Hermitian positive definite solution of the matrix equation (2) has been studied by several scholars. Lee and Lim [16] showed that, for positive semidefinite matrices A and B, $f(X)=A+M{(B+X^{-1})}^{-1}{M}^{\ast }$ is nonexpansive with respect to the Riemannian metric distance. By the nonexpansive property of $f(X)$, Jung, Kim and Lim [17] showed that, when A and B are positive semidefinite matrices, the matrix equation (2) with $p\ge 2$ has a unique positive definite solution.

In this paper, a fixed-point accelerated iterative algorithm to solve the nonlinear matrix equation (1) is proposed, and, based on the basic characteristics of Thompson metric space, the convergence of the proposed algorithm is proved. The error estimation formula of the iterative solution and some numerical example illustrating the effectiveness of the algorithm are given.

Preliminaries

Let $H^n$ denote the set of $n\times n$ Hermitian matrices, $K^n$ denote the set of $n\times n$ Hermitian positive semidefinite matrices, and $P^n$ denote the set of $n\times n$ Hermitian positive definite matrices. The notation $\parallel A\parallel$ represents the Frobenius norm of matrix A. For the matrices B and C, $B\ge C$ means $B-C\in K^n$, $B>C$ means $B-C\in P^n$, $X\in [B,C]$ means $B\le X\le C$. ${\lambda }_1\left(B\right)$, and ${\lambda }_n\left(B\right)$ indicate the maximum and minimum eigenvalues of the $n\times n$ Hermitian matrix respectively, and I indicates the $n\times n$ identity matrix.

Definition 2.1

[18] Let $A,B\in P^n$, the Thompson distance between the Hermitian positive definite matrices A and B is defined as follows: $d(A,B)=max\{logM(A/B),logM(B/A)\},$ where $M(A/B)=inf\{\delta >0:A\le \delta B\}={\lambda }_1\left(B^{-\frac{1}{2}}A{B}^{-\frac{1}{2}}\right).$

A space with a defined Thompson distance is a called Thompson metric space. For a Thompson metric space, the following Lemma 2.1, Lemma 2.2, and Lemma 2.3 hold.

Lemma 2.1

[19, 20] For any nonsingular matricesW, the following equalities and inequalities hold: $\begin{array}{c}d(X,Y)=d(X^{-1},Y^{-1})=d(W^{\ast }XW,W^{\ast }YW),\mathrm{\forall }X,Y\in P^n,\hfill \\ d(W^{\ast }{X}^{r}W,W^{\ast }{Y}^{r}W)\le |r|d(X,Y),r\in [-1,1].\hfill \end{array}$

Lemma 2.2

[19, 20] For any$A,B,C,D\in P^n$, the following equalities hold: $d(A+B,C+D)\le max\{d(A,C),d(B,D)\}.$

Lemma 2.3

[19, 20] For any$A\in K^n$, $X,Y\in P^n$, the following inequality holds$d(A+X,A+Y)\le \frac{\alpha }{\alpha +\beta }d(X,Y),$where$\alpha =max\{{\lambda }_1\left(X\right),{\lambda }_1\left(Y\right)\}$, $\beta ={\lambda }_n\left(A\right)$.

In addition, the following Lemma 2.4 can be obtained by direct calculation according to the Thompson metric space definition.

Lemma 2.4

For the constant$\alpha \ne 0$, $A,B\in P^n$, we have$d(\alpha A,\alpha B)=d(A,B)$.

Lemma 2.5

[21] If$0<X\le Y$, then$0<X^a\le Y^a$for any$a\in (0,1]$, $X,Y\in P^n$. Similarly, if$0<X\le Y$, then$0<Y^a\le X^a$for any$a\in [-1,0)$, $X,Y\in P^n$.

Lemma 2.6

Assume thatXis a positive definite solution of the nonlinear matrix equation (1), then the following inequality holds: $A^{1/p}<X<{(A+\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{A}_i)}^{1/p}.$

Proof

Since X is a positive definite solution of the nonlinear matrix equation (1), that is $X={(A+\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i)}^{1/p}.$ Hence, $X>A^{1/p}$. Furthermore, we have by Lemma 2.5 that $X^{-1}<A^{-1/p},{(B+A^{-1/p})}^{-1}<{(B+X^{-1})}^{-1}<B^{-1}.$ Hence, we have $X={(A+\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i)}^{1/p}<{(A+\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)}^{1/p}.$ Hence, the result holds. □

Lemma 2.7

Assume thatXis a positive definite solution of the nonlinear matrix equation (1), then the inequality$d(M^{\ast }{(B+X^{-1})}^{-1}M,M^{\ast }{(B+Y^{-1})}^{-1}M)\le \frac{{\lambda }_1(A^{-1/p})}{{\lambda }_1(A^{-1/p})+{\lambda }_n(B)}d(X,Y)$holds for any nonsingular matrixAand any positive definite matrixB.

Proof

It is known from Lemma 2.1, Lemma 2.3, Lemma 2.5, and Lemma 2.6 that $\begin{array}{rcl}d(M^{\ast }{(B+X^{-1})}^{-1}M,M^{\ast }{(B+Y^{-1})}^{-1}M)& =& d({(B+X^{-1})}^{-1},{(B+Y^{-1})}^{-1})\\ & =& d(B+X^{-1},B+Y^{-1})\\ & \le & \frac{{\lambda }_1(A^{-1/p})}{{\lambda }_1(A^{-1/p})+{\lambda }_n(B)}d(X^{-1},Y^{-1})\\ & =& \frac{{\lambda }_1(A^{-1/p})}{{\lambda }_1(A^{-1/p})+{\lambda }_n(B)}d(X,Y).\end{array}$ Hence, the result holds. □

Let

4

$G(X)={(A+\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i)}^{1/p},\mathrm{\Omega }=\{X|A^{1/p}<X<{(A+\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i\})}^{1/p}\}.$ Then, we have the following Lemma 2.8.

Lemma 2.8

The matrix function$G\left(X\right)$satisfies the Lipschitz condition on Ω, that is, for any$X,Y\in \mathrm{\Omega }$, we have$d(G(X),G(Y))<Ld(X,Y),$where

5

$0<L=\frac{1}{p}.\frac{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)}{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)+{\lambda }_n(A)}.\frac{{\lambda }_1(A^{-1/p})}{{\lambda }_1(A^{-1/p})+{\lambda }_n(B)}<1.$

Proof

It is known from Lemma 2.1, Lemma 2.2, Lemma 2.3, and Lemma 2.7 that $\begin{array}{rl}& d(G(X),G(Y))\\ & =d({(A+\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i)}^{1/p},{(A+\sum _{i=1}^m{M}_i^{\ast }{(B+Y^{-1})}^{-1}{M}_i)}^{1/p})\\ & \le \frac{1}{p}d(A+\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i,A+\sum _{i=1}^m{M}_i^{\ast }{(B+Y^{-1})}^{-1}{M}_i)\\ & \le \frac{1}{p}.\frac{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)}{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)+{\lambda }_n(A)}d(\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i,\sum _{i=1}^m{M}_i^{\ast }{(B+Y^{-1})}^{-1}{M}_i)\\ & \le \frac{1}{p}.\frac{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)}{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)+{\lambda }_n(A)}max\{d(M_1^{\ast }{(B+X^{-1})}^{-1}{M}_1,M_1^{\ast }{(B+Y^{-1})}^{-1}{M}_1),\\ & d(\sum _{i=2}^m.M_i^{\ast }{(B+X^{-1})}^{-1}{M}_i,\sum _{i=2}^m{M}_i^{\ast }{(B+Y^{-1})}^{-1}{M}_i)\}\\ & \le \frac{1}{p}.\frac{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)}{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)+{\lambda }_n(A)}max\{d(M_1^{\ast }{(B+X^{-1})}^{-1}{M}_1,M_1^{\ast }{(B+Y^{-1})}^{-1}{M}_1),\\ & ...,d(M_m^{\ast }{(B+X^{-1})}^{-1}{M}_m,M_m^{\ast }{(B+Y^{-1})}^{-1}{M}_m)\}\\ & \le \frac{1}{p}.\frac{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)}{{\lambda }_1(\sum _{i=1}^m{M}_i^{\ast }{B}^{-1}{M}_i)+{\lambda }_n(A)}.\frac{{\lambda }_1(A^{-1/p})}{{\lambda }_1(A^{-1/p})+{\lambda }_n(B)}d(X,Y).\end{array}$ Hence, the result holds. □

Lemma 2.9

[22] Ifϕis a compression mapping on the distance space Ω and the compression coefficient$\alpha \in (0,1)$, then the mappingϕhas a unique fixed point on Ω.

According to Lemma 2.8 and Lemma 2.9, the following lemma can be immediately obtained.

Lemma 2.10

The nonlinear matrix equation (1) has a unique positive definite solution, and, furthermore, its unique positive definite solution$X^{\ast }$satisfies$X^{\ast }\in \mathrm{\Omega }$given as (4).

Iterative algorithm and its convergence

In this section we first propose a fixed-point accelerated iterative algorithm for solving the nonlinear matrix equation (1), and then, based on the basic characteristics of the Thompson distance, prove the convergence of the proposed algorithm and the error estimation formula of the iterative solution. Let $F\left(X\right)=G\left(X\right)-X$. we propose a fixed-point acceleration iterative algorithm to solve the nonlinear matrix equation (1), as in Algorithm 1.

[See PDF for image]

Algorithm 1

Fixed-point accelerated algorithm to solve (1)

Theorem 3.1

The nonlinear matrix equation (1) has a unique positive definite solution$X^{\ast }$in Ω given as (4), and for any initial matrix$X_0\in \mathrm{\Omega }$, the matrix sequence$\left\{X_k\right\}$generated by Algorithm 1 converges to the unique positive definite solution$X^{\ast }$. Furthermore, the error-estimation formula of the iteration solution with the true solution of the nonlinear equation (1) can be expressed as

6

$d(X_k,X^{\ast })\le L^{\lfloor \frac{k}{m_k+2}\rfloor +1}d(X_0,X^{\ast }),$where$\lfloor \frac{k}{m_k+2}\rfloor$is the largest integer not exceeding$\frac{k}{m_k+2}$, and$L\in (0,1)$is the compression coefficient of the matrix function$G\left(X\right)={(A+\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i)}^{1/p}$given as Lemma 2.8.

Proof

The result that the nonlinear matrix equation (1) has a unique positive definite solution $X^{\ast }$ in Ω given as (4) can be obtained directly by Lemma 2.10, and hence we do not prove it here. We prove the conclusion (6) by induction. For $1\le k\le m_k+1$, we have by Lemma 2.4 and Lemma 2.8 that $\begin{array}{rl}& d(X_1,X^{\ast })=d(G(X_0),G(X^{\ast }))\le Ld(X_0,X^{\ast }),\\ d(X_2,X^{\ast })& =d({\alpha }_0^{1}G(X_0)+{\alpha }_1^{1}G(X_1),{\alpha }_0^{1}G(X^{\ast })+{\alpha }_1^{1}G(X^{\ast }))\\ & \le max\{d({\alpha }_0^{1}G(X_0),{\alpha }_0^{1}G(X^{\ast })),d({\alpha }_1^{1}G(X_1),{\alpha }_1^{1}G(X^{\ast }))\}\\ & =max\{d(G(X_0),G(X^{\ast })),d(G(X_1),G(X^{\ast }))\}\\ & \le L\cdot max\{d(X_0,X^{\ast }),d(X_1,X^{\ast })\}\\ & \le L\cdot max\{d(X_0,X^{\ast }),Ld(X_0,X^{\ast })\}\\ & \le L\cdot max\{d(X_0,X^{\ast }),d(X_0,X^{\ast })\}\\ & \le Ld(X_0,X^{\ast }),\\ d(X_3,X^{\ast })& =d({\alpha }_0^{2}G(X_0)+{\alpha }_1^{2}G(X_1)+{\alpha }_2^{2}G(X_2),{\alpha }_0^{2}G(X^{\ast })+{\alpha }_1^{2}G(X^{\ast })+{\alpha }_2^{2}G(X^{\ast }))\\ & \le max\{d({\alpha }_0^{2}G(X_0),{\alpha }_0^{2}G(X^{\ast })),d({\alpha }_1^{2}G(X_1)+{\alpha }_2^{2}G(X_2),\\ & {\alpha }_1^{2}G(X^{\ast })+{\alpha }_2^{2}G(X^{\ast }))\}\\ & \le max\{d(G(X_0),G(X^{\ast })),max\{d(G(X_1),G(X^{\ast })),d(G(X_2),G(X^{\ast }))\}\}\\ & \le L\cdot max\{d(X_0,X^{\ast }),d(X_1,X^{\ast }),d(X_2,X^{\ast })\}\\ & \le L\cdot max\{d(X_0,X^{\ast }),Ld(X_0,X^{\ast }),Ld(X_0,X^{\ast })\}\\ & \le Ld(X_0,X^{\ast }),\\ & .........................\\ d(X_{m_k+1},X^{\ast })& =d({\alpha }_0^{m_k}G(X_0)+{\alpha }_1^{m_k}G(X_1)+\cdots +{\alpha }_{m_k}^{m_k}G(X_{m_k}),\\ & {\alpha }_0^{m_k}G(X^{\ast })+{\alpha }_1^{m_k}G(X^{\ast })+\cdots +{\alpha }_{m_k}^{m_k}G(X^{\ast }))\\ & \le max\{d(G(X_0),G(X^{\ast })),d({\alpha }_1^{m_k}G(X_1)+\cdots +{\alpha }_{m_k}^{m_k}G(X_{m_k}),\\ & {\alpha }_1^{m_k}G(X^{\ast })+\cdots +{\alpha }_{m_k}^{m_k}G(X^{\ast }))\}\\ & \le max\{d(G(X_0),G(X^{\ast })),d(G(X_1),G(X^{\ast })),\dots ,d(G(X_{m_k}),G(X^{\ast }))\}\\ & \le max\{Ld(X_0,X^{\ast }),Ld(X_1,X^{\ast }),\dots ,Ld(X_{m_k},X^{\ast })\}\\ & \le L\cdot max\{d(X_0,X^{\ast }),Ld(X_0,X^{\ast }),\dots ,Ld(X_0,X^{\ast })\}\\ & \le L\cdot max\{d(X_0,X^{\ast }),d(X_0,X^{\ast }),\dots ,d(X_0,X^{\ast })\}\\ & \le Ld(X_0,X^{\ast }),\\ d(X_{m_k+2},X^{\ast })& =d({\alpha }_0^{m_k+1}G(X_1)+{\alpha }_1^{m_k+1}G(X_2)+\cdots +{\alpha }_{m_k}^{m_k+1}G(X_{m_k+1}),\\ & {\alpha }_0^{m_k+1}G(X^{\ast })+{\alpha }_1^{m_k+1}G(X^{\ast })+\cdots +{\alpha }_{m_k}^{m_k+1}G(X^{\ast }))\\ & \le max\{d(G(X_1),G(X^{\ast })),d({\alpha }_1^{m_k+1}G(X_2)+\cdots +{\alpha }_{m_k}^{m_k+1}G(X_{m_k+1}),\\ & {\alpha }_1^{m_k+1}G(X^{\ast })+\cdots +{\alpha }_{m_k}^{m_k+1}G(X^{\ast }))\}\\ & \le max\{d(G(X_1),G(X^{\ast })),d(G(X_2),G(X^{\ast })),\dots ,d(G(X_{m_k}),G(X^{\ast }))\}\\ & \le max\{Ld(X_1,X^{\ast }),Ld(X_2,X^{\ast }),\dots ,Ld(X_{m_k},X^{\ast })\}\\ & \le L\cdot max\{Ld(X_0,X^{\ast }),Ld(X_0,X^{\ast }),\dots ,Ld(X_0,X^{\ast })\}\\ & \le L^2\cdot max\{d(X_0,X^{\ast }),d(X_0,X^{\ast }),\dots ,d(X_0,X^{\ast })\}\\ & \le L^{2}d(X_0,X^{\ast }).\end{array}$ Assume that the inequality $d(X_k,X^{\ast })\le L^{\lfloor \frac{k}{m_k+2}\rfloor +1}d(X_0,X^{\ast })=L^{l+1}d(X_0,X^{\ast })$ holds for $k=l(m_k+2)+q,l>1,0<q<m_k+2$. Then, we have again by Lemma 2.4 and Lemma 2.8 that, when $k=(l+1)(m_k+2)$, $\begin{array}{rl}d(X_k,X^{\ast })& =d({\alpha }_0^{k-1}G(X_{k-m_k-1})+\cdots +{\alpha }_{m_k}^{k-1}G(X_{k-1}),{\alpha }_0^{k-1}G(X^{\ast })+\cdots +{\alpha }_{m_k}^{k-1}G(X^{\ast }))\\ & \le max\{d(G(X_{k-m_k-1}),G(X^{\ast })),d(G(X_{k-m_k}),G(X^{\ast })),\dots ,d(G(X_{k-1}),G(X^{\ast }))\}\\ & \le max\{Ld(X_{k-m_k-1},X^{\ast }),Ld(X_{k-m_k},X^{\ast }),\dots ,Ld(X_{k-1},X^{\ast })\}\\ & \le max\{L^{l+2}d(X_0,X^{\ast }),\dots ,L^{l+2}d(X_0,X^{\ast }),L^{l+2}d(X_0,X^{\ast })\}\\ & \le L^{l+2}d(X_0,X^{\ast })\end{array}$ and when $k=(l+1)(m_k+2)+q,0<q<m_k+2$, $\begin{array}{rl}d(X_k,X^{\ast })& =d({\alpha }_0^{k-1}G(X_{k-m_k+1})+\cdots +{\alpha }_{m_k}^{k-1}G(X_{k+1}),{\alpha }_0^{k-1}G(X^{\ast })+\cdots +{\alpha }_{m_k}^{k-1}G(X^{\ast }))\\ & \le max\{d(G(X_{k-m_k-1}),G(X^{\ast })),\dots ,d(G(X_{k-1}),G(X^{\ast }))\}\\ & \le max\{Ld(X_{k-m_k-1},X^{\ast }),\dots ,Ld(X_{k-1},X^{\ast })\}\\ & \le max\{\underset{m_k+1-q}{\underbrace{L^{l+2}d(X_0,X^{\ast }),\dots ,L^{l+2}d(X_0,X^{\ast })}},\underset{q}{\underbrace{L^{l+3}d(X_0,X^{\ast }),\dots ,L^{l+3}(X_0,X^{\ast })}}\}\\ & \le L^{l+2}d(X_0,X^{\ast }).\end{array}$ Hence, by the principle of induction, the inequality $d(X_k,X^{\ast })\le L^{\lfloor \frac{k}{m_k+2}\rfloor +1}d(X_0,X^{\ast })=L^{l+1}d(X_0,X^{\ast })$ holds for k.

Note that for the compression coefficient $L\in (0,1)$, we have $\underset{k\to \mathrm{\infty }}{lim}d(X_k,X^{\ast })=0.$ This means that the matrix sequence $\left\{X_k\right\}$ generated by Algorithm 1 converges to the unique positive definite solution $X^{\ast }$ of the nonlinear matrix equation (1), and the error estimation formula can be expressed as (6). □

Numerical experiments

In this section, some numerical experiments will be tested to illustrate the feasibility and superiority of Algorithm 1. The experiments are divided into two parts. In the first part, the relationship between the backtracking steps $m_k$ and the backconvergence of the Algorithm 1 is analyzed, and the selection ranges of the best backtracking steps are given. In the second part, the comparison of the convergence of Algorithm 1 with thefixed-point iterative algorithm are given. In all the numerical experiments, the matrices $M_i^{\prime }$s, A and B are randomly generated by MATLAB, and furthermore, to make sure the matrix equation (1) has a solution, the matrices A and B are chosen as $A_0=randn(n,n),A=A_0^{\prime }{A}_0+0.2I,B_0=randn(n,n),B=B_0^{\prime }{B}_0+0.1I.$ In all tests, the initial iteration matrix $X_0$ is chosen as $X_0={(A+0.01I)}^{1/p}$. The termination condition is the residual $R(X_k)$ satisfies $R(X_k)=\parallel A+\sum _{i=1}^m{M}_i^{\ast }{(B+X_k^{-1})}^{-1}{M}_i-X_k^p\parallel \le \epsilon .$ In all data results are obtained in the Window10, 64-bit, Matlab R2013a environment.

Selection of the backtracking step $m_k$

Backtracking steps $m_k$ are closely related to the convergence speed of the algorithm 1. Consider the nonlinear matrix equation

7

$X^3=A+M_1^{\ast }{(B+X^{-1})}^{-1}{M}_1+M_2^{\ast }{(B+X^{-1})}^{-1}{M}_2+M_3^{\ast }{(B+X^{-1})}^{-1}{M}_3.$

It can be seen from Fig. 1 that the convergence speed of Algorithm 1 is directly affected by the backtracking step $m_k$. In general, when $m_k$ is chosen as 2 through 10, Algorithm 1 is relatively more efficient than other cases. However, how to select the best backtracking steps $m_k$ is an important problem that should be studied in future.

[See PDF for image]

Figure 1

Backtracking steps $m_k$ and calculation time curve with different matrix sizes

Comparison of convergence with existing algorithms

The fixed-point iterative algorithm [1] used to solve the nonlinear matrix equation (1) has the following iterative formula: $X_{k+1}={(A+\sum _{i=1}^m{M}_i^{\ast }{(B+X_k^{-1})}^{-1}{M}_i)}^{1/p},X_0=A+0.01I,k=0,1,2\cdots .$

Note that Algorithm 1 is most efficient when the backtracking steps $m_k$ are chosen as 2 to 10. Hence, for all of the following tests, the backtracking steps $m_k$ in Algorithm 1 is fixed at 3. In addition, for the convenience of the expression, we use the notations FIXA and FIX denote Algorithm 1 and the fixed-point iterative algorithm proposed in [1], respectively. In all tests, the maximum number of inner iterations (if necessary) and outer iterations are restricted to 20 000, and the error tolerance parameter ε chosen as $\epsilon ={10}^{-9}$.

Table 1 and Fig. 2 report the comparison of FIXA and FIX to solve the nonlinear matrix equation (7) of the iteration numbers (Iter), computing time (Time), and residual ($R(X_k)$) with different matrix sizes.

[See PDF for image]

Figure 2

Compute time comparison of FIXA and FIX under different matrix sizes

Table 1. Numerical comparison of FIXA and FIX with different matrix sizes

n	Algor.	Iter	Time	$R(X_k)$	n	Algor.	Iter	Time	$R(X_k)$
5	FIXA	5	0.0046	7.0154 × 10−10	100	FIXA	6	0.0622	7.8909 × 10−10
	FIX	7	0.0007	7.9109 × 10−11		FIX	7	0.0950	9.3716 × 10−10
10	FIXA	7	0.0025	6.2044 × 10−10	200	FIXA	6	0.3148	8.3435 × 10−10
	FIX	9	0.0015	9.2425 × 10−11		FIX	7	0.4937	9.8527 × 10−10
15	FIXA	7	0.0027	9.4173 × 10−10	400	FIXA	6	1.3501	6.8784 × 10−11
	FIX	8	0.0023	8.7336 × 10−10		FIX	6	1.8175	9.9478 × 10−10
20	FIXA	7	0.0121	7.0154 × 10−11	800	FIXA	6	7.4306	7.8909 × 10−11
	FIX	8	0.0035	7.9109 × 10−10		FIX	6	9.7435	9.3716 × 10−10
25	FIXA	7	0.0075	6.2044 × 10−11	1200	FIXA	6	24.2881	8.3435 × 10−11
	FIX	8	0.0054	9.2425 × 10−10		FIX	6	34.7566	1.1527 × 10−11
30	FIXA	6	0.0115	9.4173 × 10−11	1600	FIXA	6	58.9271	6.8784 × 10−11
	FIX	7	0.0100	8.7336 × 10−10		FIX	6	84.3537	9.9478 × 10−11
50	FIXA	7	0.0252	6.2044 × 10−11	2000	FIXA	5	97.3229	8.3435 × 10−10
	FIX	8	0.0279	9.2425 × 10−11		FIX	6	172.6251	1.1527 × 10−11

Based on the tests reported in Table 1, Fig. 2, and many other performed unreported tests that show similar patterns, we have the following results:

Remark 4.1

The fixed-point iteration method is a very stable algorithm. Especially for the relatively small scale matrix size, the fixed-point iteration method is very effective. As can be seen from Table 1 and Fig. 2, when the matrix dimension is less than 50, the fixed-point iteration method is more effective than Algorithm 1. However, for the large-scale matrix size, especially for the nonlinear matrix equation (1) with positive integer m more than 3, the compute time to solve the nonlinear matrix equation (1) is quite large.

Remark 4.2

As shown in Table 1 and Fig. 2, Algorithm 1 is more effective than the fixed iteration method and the Newton iterative method. In particular, for the nonlinear matrix equation (1) with the large matrix dimensions n and the large positive integer m, Algorithm 1 is still very effective.

Conclusions

In this paper, a fixed-point acceleration iteration algorithm (Algorithm 1) to solve the nonlinear matrix equations $X^p-\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i=A$ is proposed. The convergence and error estimator of the proposed algorithm are proved (Theorem 3.1). Some numerical comparison experiments with existing algorithms are given (Table 1, Fig. 2). For Algorithm 1, the selection of the backtracking steps $m_k$ is discussed. Problems that should be studied in the near future are listed.

Acknowledgements

The authors would like to thank the anonymous referees and editors for their valuable comments and constructive suggestions.

Author contributions

All authors contributed extensively to this manuscript. Jingjing Peng and Siting Yu contributed by writing the main manuscript text. Zhenyun Peng contributed by preparing the figures and tables. All authors read and approved the final manuscript.

Funding information

Research supported by the National Natural Science Foundation of China (11961012) and the Special Research Project for Guangxi Young Innovative Talents (AD20297063).

Data availability

Not applicable.

Declarations

Competing interests

The authors declare that they have no competing interests.

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1. Jin, Z.X., Zhai, C.B.: On the nonlinear matrix equation $X^p=A+\sum _{i=1}^m{M}_i^{\ast }{(B+X^{-1})}^{-1}{M}_i$. Linear Multilinear Algebra. https://doi.org/10.1080/03081087.2021.1882371

2. Meng, J.; Kim, H.M. The positive definite solution of the nonlinear matrix equation $X^p=A+M{(B+X^{-1})}^{-1}{M}^{\ast }$. J. Comput. Appl. Math.; 2017; 322, pp. 139-147.3645824

3. Jia, Z.; Zhao, M.; Wang, M.; Ling, S. Solvability theory and iteration method for one self-adjoint polynomial matrix equation. J. Appl. Math.; 2014; 7, 3208634 681605.

4. Meng, J.; Kim, H.M. The positive definite solution to a nonlinear matrix equation. Linear Multilinear Algebra; 2015; [DOI: https://dx.doi.org/10.1080/03081087.2015.1074650]

5. Ran, A.C.M.; Reurings, M.C.B. On the nonlinear matrix equation $X+A^{\ast }F(X)A+Q$: solution and perturbation theory. Linear Algebra Appl.; 2002; 346, pp. 15-26.1897819

6. Ran, A.C.M.; Reurings, M.C.B.; Rodman, L. A perturbation analysis for nonlinear selfadjoint operator equations. SIAM J. Matrix Anal. Appl.; 2006; 28, pp. 89-104.2218944

7. Bushell, P.J. On solutions of the matrix equation $T^{\prime }AT=A^2$. Linear Algebra Appl.; 1974; 8, pp. 465-469.364296

8. Bushell, P.J. Hilbert’s metric and positive contraction mappings in a Banach space. Arch. Ration. Mech. Anal.; 1973; 52, pp. 330-338.336473

9. Lim, Y. Bushell’s equations and polar decompositions. Math. Nachr.; 2009; 282, pp. 1567-1574.2573466

10. Liu, X.; Gao, H. On the positive definite solutions of the matrix matrix equations $X^s\pm AT{X}^{-t}A=I_n$. Linear Algebra Appl.; 2003; 368, pp. 83-97.1983196

11. Anderson, W.N.; Kleindorfer, G.D.; Kleindorfer, P.R.; Woodroofe, M.B. Consistent estimates of the parameters of a linear system. Ann. Math. Stat.; 1969; 40, pp. 2064-2075.253496

12. Bougerol, P. Kalman filtering with random coefficients and contractions. SIAM J. Control Optim.; 1993; 31, pp. 942-959.1227540

13. Guo, C.H. Convergence rate of an iterative method for nonlinear matrix equations. SIAM J. Control Optim.; 1993; 31, pp. 942-959.1227540

14. Guo, C.H.; Lancaster, P. Iterative solution of two matrix equations. Math. Comput.; 1999; 68, pp. 1589-1603.1651757

15. Abou-Kandil, H.; Freiling, G.; Ionesu, V.; Jank, G. Matrix Riccati Equation in Control and Systems Theory; 2003; Basel, Birkhauser:

16. Lee, H.; Lim, Y. Invariant metrics, contractions and nonlinear matrix equations. Nonlinearity; 2008; 21, pp. 857-878.2399829

17. Jung, C.; Kim, H.M.; Lim, Y. On the solution of the nonlinear matrix equation $X^n=f(X)$. Linear Algebra Appl.; 2009; 430, pp. 2042-2052.2503951

18. Lim, Y. Solving the nonlinear matrix equation $X=Q+\sum _{i=1}^m{M}_i{X}^{{\delta }_i}{M}_i$ via a contraction principle. Linear Algebra Appl.; 2009; 430, 4 pp. 1380-1383.2489400

19. Duan, X.; Chen, H.; Duan, F. Positive definite solutions of the matrix equation $X-{\sum }_{i=1}^m{A}_i^{\ast }{X}^{-1}{A}_i=Q$. Numer. Math. J. Chin. Univ.; 2012; 34, 02 pp. 141-152.

20. Lee, H.; Lim, Y. Invariant metrics, contractions and nonlinear matrix equations. Nonlinearity; 2008; 21, 4 pp. 857-878.2399829

21. Duan, X.; Liao, A. On the existence of Hermitian positive definite solutions of the matrix equation $X^s+A^T{X}^{-t}A=Q$. Linear Algebra Appl.; 2008; 429, pp. 673-687.2428122

22. Sakhnovich, L.A. Interpolation Theory and Its Applications; 2012; Berlin, Springer: