# Some Matrix Iterations for Computing Matrix Sign Function

Authors: F. Soleymani; E. Tohidi; S. Shateyi; F. Khaksar Haghani
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Some iterative methods are introduced and demonstrated for finding the matrix sign function. It is analytically shown that the new schemes are asymptotically stable. Convergence analysis along with the error bounds of the main proposed method is established. Different numerical experiments are employed to compare the behavior of the new schemes with the existing matrix iterations of the same type.


---

## Body

## 1. Introduction

Recently, the theory of matrix functions becomes an active topic of research in the field of advanced numerical linear algebra (see, e.g., [1–4]). In fact, the most common matrix function is the matrix inverse or the Moore-Penrose generalized inverse, routinely used in the scientific problems [5]. General matrix functions as well as the specific cases have been extensively discussed and developed in [6].This paper is concerned with a special case known as matrix sign function, which is of clear importance in the theory of matrix functions [7]. Let us, as Higham considered in the fifth Chapter of [6], assume throughout this paper that the matrix A
∈
C
n
×
n has no eigenvalues on the imaginary axis. This assumption implies that the matrix sign function,
(1)
S
=
sign
⁡
(
A
)
,
can be uniquely defined, whereas A is a nonsingular square matrix. In order to define S, we remember the matrix sector function, for any positive integer p, can be defined by
(2)
sect
p
(
A
)
=
A
(
A
p
)
-
1
/
p
.Choosingp
=
2 in the matrix sector function will yield in the matrix sign function as S
=
A
(
A
2
)
-
1
/
2. This also clearly puts on show the importance and the relevance of this matrix function to the other important matrix functions such as matrix square root.Bini et al. in [8] proved that the principal pth root of the matrix A is a multiple of the (2,1)-block of the matrix sign function, sign
⁡
(
C
), for the following block companion matrix
(3)
C
=
(
0
I
0
I
⋱
⋱
⋱
I
A
0
)
∈
C
p
n
×
p
n
.The matrixS has the following properties.(1)
S
2
=
I (S is involutory).
(2)
S is diagonalizable with eigenvalues ±
1.
(3)
S
A
=
A
S.
(4)
IfA is real, then S is real.
(5)
(
I
+
S
)
/
2 and (
I
-
S
)
/
2 are projectors onto the invariant subspaces associated with the eigenvalues in the right half-plane and left half-plane, respectively.AlthoughS has eigenvalues of ±
1, its norm can be arbitrarily large. Note that, for diagonalizable A, eigenvectors of A are eigenvectors of S, with eigenvalues of -
1 and 1, respectively. For more, see [9].There are some other definitions forS in the literature based on the Jordan canonical form and the integral representation. As indicated in [6], one of the most useful and widely applicable methods for computing S is the matrix iteration of Newton given by
(4)
X
k
+
1
=
1
2
(
X
k
+
X
k
-
1
)
.In 1991, a fundamental family of matrix iterations for finding the matrix sign functionS was introduced in [10] using Padé approximants to f
(
ξ
)
=
(
1
-
ξ
)
-
1
/
2 and the following characterization:
(5)
sign
⁡
(
z
)
=
s
=
z
(
z
2
)
1
/
2
=
z
(
1
-
ξ
)
1
/
2
,
where ξ
=
1
-
z
2. Let the (
m
,
n
)-Padé approximant to f
(
ξ
) be P
m
,
n
(
ξ
)
/
Q
m
,
n
(
ξ
), and m
+
n
≥
1. The iteration
(6)
z
k
+
1
=
z
k
P
m
,
n
(
1
-
z
k
2
)
Q
m
,
n
(
1
-
z
k
2
)
∶
=
φ
2
m
+
1,2
n
has been proved to be convergent to 1 and −1 with order of convergence m
+
n
+
1 form m
≥
n
-
1. We remark that iterative methods of the type z
k
P
m
,
n
(
1
-
z
k
2
)
/
Q
m
,
n
(
1
-
z
k
2
) are fixed-point type iterations, and if z
k
P
m
,
n
(
1
-
z
k
2
)
/
Q
m
,
n
(
1
-
z
k
2
) does not converge then its reciprocal; that is, Q
m
,
n
(
1
-
z
k
2
)
/
z
k
P
m
,
n
(
1
-
z
k
2
) converges to the sign matrix (e.g., forthcoming iterations (7) and (8)). Generally speaking, the iterations of Kenney and Laub (6), generated by the [
h
/
h
] and [
(
h
-
1
)
/
h
] Padé approximants, are globally convergent and their orders depend on h. A discussion about such iterations was given in [11–13].A lot of known methods could be extracted from the Padé family (6). For example, the well-known Halley’s matrix iteration of order three can be deduced as follows:
(7)
X
k
+
1
=
[
I
+
3
X
k
2
]
[
X
k
(
3
I
+
X
k
2
)
]
-
1
.
Another fourth-order method could be attained as follows:
(8)
X
k
+
1
=
[
I
+
6
X
k
2
+
X
k
4
]
[
4
X
k
(
I
+
X
k
2
)
]
-
1
.Note that, for lower order methods such as (4), the convergence is slow; that is, initially convergence can be slow if |
x
k
|
≫
1. Hence, a scaling approach (a.k.a. norm scaling) to accelerate the beginning of this phase is necessary and can be done in what follows [6]:
(9)
X
0
=
A
,
μ
k
=
∥
X
k
-
1
∥
∥
X
k
∥
,
X
k
+
1
=
1
2
(
μ
k
X
k
+
μ
k
-
1
X
k
-
1
)
.Such an approach could be done to refine the initial matrix and to provide a much more robust initial matrix to arrive at the convergence phase rapidly.The rest of this paper has been organized as follows. Section2 gives the basic idea of obtaining other higher order solvers for computing S, while a fourth-order family of methods has been introduced. Section 3 is devoted to find the best method of this family in terms of the lowest computational cost. An analysis will be given to show that the new matrix iteration is asymptotically stable with local quartic convergence. To find a method with fourth order and global convergence, we also give another matrix iteration therein. Convergence analysis along with the error bounds of the proposed method is established. Numerical studies will be included in Section 4 to compare the efficiency and the stability of the schemes for finding S using different tests. Finally, a short conclusion of the study will be drawn in Section 5.


## 2. Basic Idea

The connection between the matrix iteration of Newton and Newton’s root-finding method may not be clear at the first sight. Generally speaking, in the theory of matrix functions, many of the matrix functions could effectively be calculated by the existing iterative methods for finding the solution of nonlinear equations [14].To illustrate further, apply Newton’s method on the following matrix equation:(10)
X
2
=
I
,
in which I is the identity matrix of the appropriate size; it would yield in the matrix Newton’s iteration (4). Note that S is one solution of (10). Note that, in the last decade, many efficient higher-order iterative methods have been developed for solving nonlinear equations [15], and some of them have been extended to solve nonlinear matrix equation; see, for example, [16, 17]. But our work is the first to discuss the application of high order root solvers for matrix sign function.Let us consider the following fourth-order family of iterative methods [18]:
(11)
y
k
=
x
k
-
f
′
(
x
k
)
-
1
f
(
x
k
)
,
x
k
+
1
=
y
k
-
[
f
′
(
x
k
)
-
1
f
(
y
k
)
]
×
[
1
+
2
f
(
x
k
)
-
1
f
(
y
k
)
+
β
(
f
(
x
k
)
-
1
f
(
y
k
)
)
2
]
,
wherein β is a free parameter in R. Applying the uniparametric family (11) on matrix equation (10) results in the following novel family of matrix iterations:
(12)
X
k
+
1
=
[
128
X
k
7
]
-
1
×
[
-
β
(
-
I
+
X
k
2
)
4
+
8
(
X
k
2
-
5
X
k
4
+
15
X
k
6
+
5
X
k
8
)
]
.The free parameterβ plays an important role in the next section to derive the best possible matrix iteration out of (12).


## 3. Main Results

In order to reduce the computational complexity of (12), the parameter β must be chosen as if the number of matrix-matrix products gets down along the number of matrix inversions.Choosingβ
=
0 will simplify the whole family into the following method with reasonable computational cost in contrast to its convergence order:
(13)
X
k
+
1
=
[
16
X
k
5
]
-
1
[
I
-
5
X
k
2
+
15
X
k
4
+
5
X
k
6
]
.We now rewrite obtained iteration (13) as efficiently as possible to reduce the number of matrix-matrix multiplications in what follows:
(14)
X
k
+
1
=
1
16
[
Y
k
5
-
5
Y
k
3
+
15
Y
k
+
5
X
k
]
,
where Y
k
=
X
k
-
1 and X
0
=
A.Definition 1 (stability [6]).
Consider an iterationX
k
+
1
=
g
(
X
k
) with a fixed point X. Assume that g is Fréchet differentiable at X. The iteration is stable in a neighborhood of X if the Fréchet derivative L
g
(
X
) has bounded powers; that is, there exists a constant c such that ∥
L
g
i
(
X
)
∥
≤
c for all i
>
0.Now, we first investigate the stability of (14) for the matrix sign function in a neighborhood of the solution of (10). In fact, we analyze how a small perturbation at the kth iterate is amplified or damped along the iterates. Note that a general way for assessing the stability of some matrix iterations has been studied by Iannazzo in [19]. The forthcoming approach follows these results of [19].Lemma 2.
The sequence{
X
k
}
k
=
0
k
=
∞ generated by (14) is asymptotically stable.Proof.
Stability concerns behavior close to convergence and so is an asymptotic property. LetΔ
X
k be the numerical perturbation introduced at the kth iterate of (14). Next, one has
(15)
X
~
k
=
X
k
+
Δ
X
k
.
Here, we perform a first-order error analysis; that is, we formally neglect quadratic terms such as (
Δ
X
k
)
2. This formal manipulation is meaningful if Δ
X
k is sufficiently small. We have
(16)
X
~
k
+
1
=
1
16
[
Y
~
k
5
-
5
Y
~
k
3
+
15
Y
~
k
+
5
X
~
k
]
=
1
16
[
X
~
k
-
5
-
5
X
~
k
-
3
+
15
X
~
k
-
1
+
5
X
~
k
]
=
1
16
[
(
X
k
+
Δ
X
k
)
-
5
-
5
(
X
k
+
Δ
X
k
)
-
3
+
15
(
X
k
+
Δ
X
k
)
-
1
+
5
(
X
k
+
Δ
X
k
)
]
≈
1
16
[
(
X
k
-
1
-
X
k
-
1
Δ
X
k
·
X
k
-
1
)
5
-
5
(
X
k
-
1
-
X
k
-
1
Δ
X
k
·
X
k
-
1
)
3
+
15
(
X
k
-
1
-
X
k
-
1
Δ
X
k
·
X
k
-
1
)
+
5
(
X
k
+
Δ
X
k
)
]
,
where the following identity has been used (for any nonsingular matrix B and the matrix C):
(17)
(
B
+
C
)
-
1
≈
B
-
1
-
B
-
1
C
B
-
1
.
Note that the commutativity betweenX
k and Δ
X
k is not used throughout this paper because it does not hold. Further simplifying yields to
(18)
X
~
k
+
1
≈
S
+
1
2
Δ
X
k
-
1
2
S
Δ
X
k
S
,
where S
2
=
I, S
-
1
=
S, and for large enough k we have X
k
≈
sign
⁡
(
A
)
=
S, and (
Δ
X
k
)
i, i
≥
2 is close to zero (matrix) and can be neglected by choosing (
Δ
X
k
)
i
≈
0. After some algebraic manipulation and using Δ
X
k
+
1
=
X
~
k
+
1
-
X
k
+
1, we conclude that
(19)
Δ
X
k
+
1
≈
1
2
Δ
X
k
-
1
2
S
Δ
X
k
S
.
Applying (19) recursively, and after some algebraic manipulations, we have
(20)
∥
Δ
X
k
+
1
∥
≤
1
2
k
+
1
∥
Δ
X
0
-
S
Δ
X
0
S
∥
.
From (20), we can conclude that the perturbation at the iterate k
+
1 is bounded. Therefore, the sequence {
X
k
} generated by (14) is asymptotically stable.Remark 3.
IfX
0 is a function of A, then the iterates from (14) or (23) are all functions of A and hence commute with A.The proposed matrix iteration requires one matrix inverse per iteration along four matrix-matrix products to achieve the convergence order four, while Halley’s method requires one matrix inversion and three matrix-matrix products to reach order three.The basins of attraction for the two iterative methods of (4) and (14) to solve x
2
-
1
=
0 in the complex plane have been drawn in Figure 1. It shows that the new scheme has larger basins due to its higher convergence order. Note that the roots have been identified with two white points.The basins of attraction for (4) (a) and fourth-order method (14) (b) for the polynomial x
2
-
1
=
0 (shaded by the number of iterations to obtain the solution).
(a)
(b)Iannazzo in [20] discussed that the matrix convergence is governed by scalar convergence. That is to say, the fourth-order convergence of new method (14) might not be global unlike Newton’s iteration (4). To illustrate further, if one chooses a matrix A (in Figure 1(b)) with one eigenvalue with negative real part, but in a yellow petal, then the matrix iteration will not converge to S. Therefore, it could be mentioned that scheme (14) converges with local fourth order. This restriction has encouraged us to propose another fourth-order method with global convergence in what follows and leave behind the previous iteration with interest in terms of theoretical analysis only.Let us apply the following fourth-order nonlinear solver [16] on matrix equation (10):
(21)
y
k
=
x
k
-
2
-
1
f
′
(
x
k
)
-
1
f
(
x
k
)
,
z
k
=
x
k
-
f
′
(
y
k
)
-
1
f
(
x
k
)
,
x
k
+
1
=
z
k
-
[
(
z
k
-
y
k
)
-
1
(
f
(
z
k
)
-
f
(
y
k
)
)
]
-
1
f
(
z
k
)
,
which reads the error equation
(22)
e
k
+
1
=
(
c
2
3
2
-
c
2
c
3
8
)
e
k
4
+
O
(
e
k
5
)
,
wherein c
j
=
f
(
j
)
(
α
)
/
j
!
f
′
(
α
) and  e
k
=
x
k
-
α, and then to obtain its corresponding matrix iteration, as follows
(23)
X
k
+
1
=
(
I
+
18
Y
k
+
13
Z
k
)
[
X
k
(
7
I
+
Y
k
)
(
I
+
3
Y
k
)
]
-
1
,
where Y
k
=
X
k
X
k,  Z
k
=
Y
k
Y
k, and X
0
=
A. Figure 2 shows the basins of attraction for new method (23) and scheme (7), while both reveal global convergence. The higher order of convergence for (23) made its basins larger and lighter.The basins of attraction for (7) (a) and method (23) (b) for the polynomial x
2
-
1
=
0 (shaded by the number of iterations to obtain the solution).
(a)
(b)Remark 4.
In this paper, we restrict the analyses to asymptotically small perturbations; that is, we use the differential error analysis.Lemma 5.
The sequence{
X
k
}
k
=
0
k
=
∞ generated by (23) is asymptotically stable.Proof.
Using the same assumptions as in the Proof of Lemma2 (perturbations are restricted to a neighborhood of the solution), we can write the following:
(24)
X
~
k
+
1
=
(
I
+
18
Y
~
k
+
13
Z
~
k
)
[
X
~
k
(
7
I
+
Y
~
k
)
(
I
+
3
Y
~
k
)
]
-
1
=
(
I
+
18
X
~
k
2
+
13
X
~
k
4
)
×
[
(
I
+
3
X
~
k
)
-
1
(
7
I
+
X
~
k
)
-
1
X
~
k
-
1
]
≈
(
I
+
18
(
S
+
Δ
X
k
S
)
2
+
13
(
S
+
Δ
X
k
S
)
4
)
×
[
(
I
+
3
(
S
+
Δ
X
k
S
)
)
-
1
(
7
I
+
(
S
+
Δ
X
k
S
)
)
-
1
×
(
S
+
Δ
X
k
S
)
-
1
(
I
+
3
(
S
+
Δ
S
)
)
-
1
]
.
Further simplifying and by considering the terminology of Lemma 2, we attain
(25)
Δ
X
k
+
1
≈
(
I
+
11
8
S
Δ
X
k
)
(
S
-
15
8
S
Δ
X
k
S
-
15
8
Δ
X
k
)
≈
-
1
2
Δ
X
k
-
1
2
S
Δ
X
k
S
.
It shows that the main proposed iterative scheme (23) is asymptotically stable, since recursively one has ∥
Δ
X
k
+
1
∥
≤
(
1
/
2
k
+
1
)
∥
Δ
X
0
+
S
Δ
X
0
S
∥. The proof is complete.Remark 6.
The analysis done does not take into account the influence of the rounding errors on the convergence. Sometimes these errors may lead to slower convergence or even to the failure of the method. We remark concerning this potential danger for problems solving in single precision arithmetic or in lower precision.Theorem 7.
LetA
∈
C
n
×
n have no pure imaginary eigenvalues. Then, for the proposed iterates {
X
k
}
k
=
0
k
=
∞ in (23), (
X
k
(
7
I
+
Y
k
)
(
I
+
3
Y
k
)
)
-
1 is defined per stage.Proof.
We must show thatX
k
(
7
I
+
Y
k
)
(
I
+
3
Y
k
) which is obtained at each iteration is nonsingular, since the inverse of the matrix X
k
(
7
I
+
Y
k
)
(
I
+
3
Y
k
) must be computed per computing step. Toward this goal, it is enough to show that the eigenvalues of the computed matrix at the end of each iteration are in the open half-plane.
Using the initial matrixX
0
=
A and based on the fact that A has no eigenvalues on the imaginary axis, the eigenvalues of the initial matrix are in the open half-plane. Let λ be the eigenvalue of the matrix X
k in the kth iterate. We have λ
=
r
exp
⁡
i
θ, where i
=
-
1. Hence,
(26)
λ
+
λ
-
1
=
(
r
+
r
-
1
)
cos
⁡
(
θ
)
+
i
(
r
-
r
-
1
)
sin
(
θ
)
,
(
λ
1
(
7
+
λ
2
)
(
1
+
3
λ
2
)
)
-
1
=
(
cos
⁡
⁡
(
θ
)
-
i
sin
⁡
(
θ
)
)
3
r
(
22
r
2
+
(
7
+
3
r
4
)
cos
⁡
⁡
(
2
θ
)
+
i
(
-
7
+
3
r
4
)
sin
⁡
(
2
θ
)
)
=
1
7
e
i
θ
r
+
22
e
3
i
θ
r
3
+
3
e
5
i
θ
r
5
,
and consequently
(27)
(
1
+
18
λ
2
+
13
λ
4
)
(
λ
1
(
7
+
λ
2
)
(
1
+
3
λ
2
)
)
-
1
=
(
r
4
(
cos
⁡
⁡
(
θ
)
-
i
sin
⁡
(
θ
)
)
×
(
18
r
2
+
(
1
+
13
r
4
)
cos
⁡
⁡
(
2
θ
)
+
i
(
-
1
+
13
r
4
)
sin
⁡
(
2
θ
)
)
)
×
(
r
(
(
7
+
r
2
)
cos
⁡
⁡
(
θ
)
+
i
(
-
7
+
r
2
)
sin
⁡
(
θ
)
)
×
(
(
1
+
3
r
2
)
cos
⁡
⁡
(
θ
)
+
i
(
-
1
+
3
r
2
)
sin
⁡
(
θ
)
)
)
-
1
.
Therefore, the eigenvalues of X
k
(
7
I
+
Y
k
)
(
I
+
3
Y
k
) remain in their open half-plane under mapping (23). And X
k
(
7
I
+
Y
k
)
(
I
+
3
Y
k
) is defined and is nonsingular for all k.Theorem 8.
LetA
∈
C
n
×
n has no pure imaginary eigenvalues. Then, the proposed iterates {
X
k
}
k
=
0
k
=
∞ of (23) converge to the sign matrix S.Proof.
For our analysis, we assume thatA is diagonalizable; that is, there exists a nonsingular matrix V such that
(28)
V
-
1
A
V
=
Λ
=
diag
⁡
(
λ
1
,
λ
2
,
…
,
λ
n
)
,
where λ
1
,
λ
2
,
…
,
λ
n are the eigenvalues of A. Note that we know that [10]
(29)
sign
⁡
(
Λ
)
=
sign
⁡
(
V
-
1
A
V
)
=
V
-
1
sign
⁡
(
A
)
V
,
for any nonsingular matrix V. On the other hand, if we define D
k
=
V
-
1
X
k
V, then we have from (23) that
(30)
D
k
+
1
=
(
I
+
18
D
k
2
+
13
D
k
4
)
[
D
k
(
7
I
+
D
k
2
)
(
I
+
3
D
k
2
)
]
-
1
.
Notice that if D
0 is a diagonal matrix, then all successive D
k are diagonal too. From (30), it is enough to prove that {
D
k
} converges to the sign of Λ  and then ensure the convergence of the sequence generated by (23) to sign
⁡
(
A
).
Therefore, we can write (30) as n uncoupled scalar iterations to solve g
(
x
)
=
0, with g
(
x
)
=
x
2
-
1, given by
(31)
d
k
+
1
i
=
1
+
18
d
k
i
2
+
13
d
k
i
4
d
k
i
(
7
I
+
d
k
i
2
)
(
I
+
3
d
k
i
2
)
,
where d
k
i
=
(
D
k
)
i
,
i and 1
≤
i
≤
n. On the other hand, sign
⁡
(
D
k
)
=
sign
⁡
(
Λ
), for all k
≥
0. From (30) and (31), it is enough to study the convergence of {
d
k
i
} to the sign of λ
i, for all 1
≤
i
≤
n.
From (31) and since the eigenvalues of A are not pure imaginary, we have that sign
⁡
(
λ
i
)
=
s
i
=
±
1. Thus, we attain
(32)
d
k
+
1
i
-
1
d
k
+
1
i
+
1
=
-
6
+
18
d
k
i
-
22
d
k
i
2
+
13
d
k
i
3
-
3
d
k
i
4
8
+
18
d
k
i
+
22
d
k
i
2
+
13
d
k
i
3
+
3
d
k
i
4
.
Since |
d
0
i
|
=
|
λ
i
|
>
0, we obtain
(33)
lim
⁡
k
→
∞
|
d
k
+
1
i
-
1
d
k
+
1
i
+
1
|
=
1
,
and lim
⁡
k
→
∞
|
d
k
i
|
=
1
=
|
sign
⁡
(
λ
i
)
|. This shows that {
d
k
i
} is convergent. Now, it could be easy to conclude that lim
⁡
k
→
∞
D
k
=
sign
⁡
(
Λ
). Recalling D
k
=
V
-
1
X
k
V, we have
(34)
lim
⁡
k
→
∞
X
k
=
V
(
lim
⁡
k
→
∞
D
k
)
V
-
1
=
V
sign
⁡
(
Λ
)
V
-
1
,
and subsequently the convergence is established. The proof is complete.Remark 9.
It is clear that convergence will be slow if eitherρ
(
A
)
≫
1 or A has eigenvalues close to the imaginary axis. Hence, it is better to first construct a robust seed by scaled method (9).Theorem 10.
LetA
∈
C
n
×
n have no pure imaginary eigenvalues. Then, new method (23) has fourth order to find the sign matrix S.Proof.
Clearly, theX
k are rational functions of A and hence, like A, commute with S. On the other hand, we know that S
2
=
I, S
-
1
=
S, S
2
j
=
I, and S
2
j
+
1
=
S, j
≥
1. Choosing B
k
=
X
k
(
7
I
+
Y
k
)
(
I
+
3
Y
k
) (for the sake of simplicity), we have
(35)
X
k
+
1
-
S
=
(
I
+
18
Y
k
+
13
Z
k
)
B
k
-
1
-
S
=
[
I
+
18
X
k
2
+
13
X
k
4
-
S
B
k
]
B
k
-
1
=
[
I
+
18
X
k
2
+
13
X
k
4
-
7
X
k
S
-
22
X
k
3
S
-
3
X
k
5
S
]
B
k
-
1
=
[
(
X
k
-
S
)
4
-
3
X
k
5
S
5
+
12
X
k
4
S
4
-
18
X
k
3
S
+
12
X
k
2
S
2
-
X
k
S
3
]
B
k
-
1
=
[
(
X
k
-
S
)
4
-
3
X
k
S
×
(
X
4
-
4
X
k
3
S
+
6
X
k
2
S
2
-
4
X
k
S
3
+
I
)
]
B
k
-
1
=
[
(
X
k
-
S
)
4
-
3
X
k
S
(
X
k
-
S
)
4
]
B
k
-
1
=
(
X
k
-
S
)
4
[
I
-
3
X
k
S
]
B
k
-
1
.
Now, using a matrix operator norm from both sides of (35), we attain
(36)
∥
X
k
+
1
-
S
∥
≤
(
∥
B
k
-
1
∥
∥
I
-
3
X
k
S
∥
)
∥
X
k
-
S
∥
4
.
This reveals the fourth order of convergence for new method (23). The proof is ended.


## 4. Numerical Results

This section addresses issues related to the numerical precision of the computation of matrix sign function using Mathematica 8 built-in precision [21, 22]. The value of machine precision that produced the results included here is 15.96 digits, which corresponds to a 53-digit binary double precision number with a mantissa [23].For numerical comparisons in this section, we have used methods (4) denoted by “Newton,” (7) denoted by “Halley,” (8) denoted by “M4,” (14) denoted by “PM1,” and (23) denoted by “PM2.”It must be noted that the Newton-Schulz iteration, which replaces the inverse of the matrixX
k in each iteration of (4) by the Schulz inverse-finder [6] and can be written as
(37)
X
k
+
1
=
1
2
X
k
(
3
I
-
X
k
2
)
,
will not be considered in the numerical comparisons. Because due to the use of Schulz iteration instead of the matrix inversion, though the quadratic convergence of (4) will remain unchanged, it fully demands a good initial matrix and might be more risky to diverge in contrast to scheme (4). In fact, its convergence is guaranteed only if ∥
I
-
A
2
∥
<
1; see Figure 3(a).The basins of attraction for (37) and (a) for the complex polynomial x
2
-
1
=
0 (shaded by the number of iterations to obtain the solution) and the distribution of the eigenvalues of A
[
1
] for Example 1.
(a)
(b)We report the running time using the commandAbsoluteTiming[
] for the elapsed CPU time (in seconds) in the experiments. The computer specifications are Microsoft Windows XP Intel(R), Pentium(R) 4, and CPU 3.20 GHz, with 4 GB of RAM.Example 1.
The aim of this example is to compare different methods for finding the matrix sign function of a randomly generated dense600
×
600 matrix as follows: n = 600; SeedRandom[
22
];
A[
1
] = RandomReal[{-100, 100}, {n, n}].In this test example, the prescribed tolerance is ∥
X
k
2
-
I
∥
F
≤
1
0
-
8 and the maximum number of iterations is set to 100.The results of comparisons in terms of the number of iterations and the computational time have been reported in Table1, for various matrix iterations in finding the matrix sign function numerically. Note that whatever the eigenvalues of a matrix are closer to the imaginary axis, the speed of convergence for the different methods becomes slower and more risky to face with singular matrices X
k, whose inverse could not be computed; see Figure 3(b).Table 1
Results of comparisons for Example1.
Methods
Newton
Halley
PM1
PM2
Number of iterations
21
14
18
9
Time
6.68
7.53
14.12
7.02Note that method (13) is not competitive in terms of computational cost and local convergence and hence we will remove it from further consideration. Unlike it, new method (23) has global convergence with asymptotical stability and could be considered as an alternative over the existing iterative methods for finding S.Example 2.
In this example, 15 random dense120
×
120 matrices are considered to compare the behavior of different methods in what follows: n = 120; number = 15; SeedRandom[
1
];
Table[A[l] = RandomReal[{-5, 5},
{n, n}];, {l, number}].For this test, the prescribed tolerance is ∥
X
k
+
1
-
X
k
∥
2
≤
1
0
-
12 and the maximum number of iterations is set to 100.The results of comparisons are reported in Figure4. New method (23) beats its competitors in terms of the number of iterations, while both (23) and (8) are the best iterations in terms of the computational time. Note that, in the last two examples, we have used double precision arithmetic in our calculations.The comparisons of different matrix iterations in terms of the number of iterations and the computational time for 15 different test matrices in Example2.
(a)
(b)Although this example showed the robustness of new method (23), there is an approach to observe the order of convergence of different iteration methods numerically. To be more precise, the computational order of convergence for matrix iterations in finding the matrix sign function can be estimated by
(38)
COC
=
log
⁡
(
∥
X
k
+
1
2
-
I
∥
/
∥
X
k
2
-
I
∥
)
log
⁡
(
∥
X
k
2
-
I
∥
/
∥
X
k
-
1
2
-
I
∥
)
,
wherein X
k
-
1
,
X
k
,
X
k
+
1 are the last three approximations for finding S in the convergence phase.Example 3 (an academical test).
Let us find the computational order of convergence for different methods when finding the matrix sign for the well-known Wilson matrix as follows:(39)
A
=
(
10
7
8
7
7
5
6
5
8
6
10
9
7
5
9
10
)
.
In order to find the COC, we herein apply 64-digit fixed point arithmetic in our calculations.The convergence history along the COCs (in the infinity norm) using formula (38) for different methods is illustrated in Figure 5 and Table 2, applying the stopping termination ∥
X
k
2
-
I
∥
∞
≤
1
0
-
16. Results show that new method (23) is quite fast and its computational order of convergence for academical tests in high precision computing environment is around 4.Table 2
Results of comparisons for Example3.
Methods
Newton
Halley
M4
PM2
Number of iterations
12
8
7
6
COC
1.99999
2.99561
4.04145
4.03896Figure 5
Convergence history based on the logarithm of the residuals∥
X
k
2
-
I
∥
∞ in Example 3.


### 4.1.  Scaling

Main proposed iteration (23) is quite fast and reliable due to the discussions in Sections 3 and 4. However, a way is open for speeding up its initial phase of convergence.An effective way to enhance the initial speed of convergence is to scale the iterates prior to each iteration; that is,X
k is replaced by μ
k
X
k. Such an approach can simply be done in what follows:
(40)
X
0
=
A
,
μ
k
=
∥
X
k
-
1
∥
∥
X
k
∥
,
X
k
+
1
=
(
I
+
18
μ
k
2
Y
k
+
13
μ
k
4
Z
k
)
×
[
μ
k
X
k
(
7
I
+
μ
k
2
Y
k
)
(
I
+
3
μ
k
2
Y
k
)
]
-
1
,
where lim
⁡
k
→
∞
μ
k
=
1 and lim
⁡
k
→
∞
X
k
=
S.


## 4.1.  Scaling

Main proposed iteration (23) is quite fast and reliable due to the discussions in Sections 3 and 4. However, a way is open for speeding up its initial phase of convergence.An effective way to enhance the initial speed of convergence is to scale the iterates prior to each iteration; that is,X
k is replaced by μ
k
X
k. Such an approach can simply be done in what follows:
(40)
X
0
=
A
,
μ
k
=
∥
X
k
-
1
∥
∥
X
k
∥
,
X
k
+
1
=
(
I
+
18
μ
k
2
Y
k
+
13
μ
k
4
Z
k
)
×
[
μ
k
X
k
(
7
I
+
μ
k
2
Y
k
)
(
I
+
3
μ
k
2
Y
k
)
]
-
1
,
where lim
⁡
k
→
∞
μ
k
=
1 and lim
⁡
k
→
∞
X
k
=
S.


## 5. Discussion

A function of a matrix can be defined and computed in several ways, such as Cauchy integral, polynomial interpolation, and Jordan canonical form. However, another approach is to use iteration methods for such computations. Several matrix functions can be computed by iterationX
k
+
1

=

g
(
X
k
), with an appropriate initial matrix X
0 where, for reasons of computational cost, g is usually a polynomial or a rational function.Under this motivation, in this paper we have introduced and demonstrated some fourth-order matrix methods for finding the matrix sign function. The proposed methods consist of one matrix inversion per cycle and are asymptotically stable. The consistency and efficiency of the contributed methods have also been tested numerically for finding the matrix sign functions to support the theoretical parts.



---

*Source: 425654-2014-07-09.xml*