# A Matrix Iteration for Finding Drazin Inverse with Ninth-Order Convergence

Authors: A. S. Al-Fhaid; S. Shateyi; M. Zaka Ullah; F. Soleymani
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

The aim of this paper is twofold. First, a matrix iteration for finding approximate inverses of nonsingular square matrices is constructed. Second, how the new method could be applied for computing the Drazin inverse is discussed. It is theoretically proven that the contributed method possesses the convergence rate nine. Numerical studies are brought forward to support the analytical parts.


---

## Body

## 1. Preliminary Notes

Letℂ
n
×
n and ℂ
r
n
×
n denote the set of all complex n
×
n matrices and the set of all complex n
×
n matrices of rank r, respectively. By A
*, ℛ
(
A
), rank
⁡
(
A
), and 𝒩
(
A
), we denote the conjugate transpose, the range, the rank, and the null space of A
∈
ℂ
n
×
n, respectively.Important matrix-valued functionsf
(
A
) are, for example, the inverse A
-
1, the (principal) square root A, and the matrix sign function. Their evaluation for large matrices arising from partial differential equations or integral equations (e.g., resulting from wavelet-like methods) is not an easy task and needs techniques exploiting appropriate structures of the matrices A and f
(
A
).In this paper, we focus on the matrix function of inverse for square matrices. To this goal, we construct a matrix iterative method for finding approximate inverses quickly. It is proven that the new method possesses the high convergence order nine using only seven matrix-matrix multiplications. We will then discuss how to apply the new method for Drazin inverse. The Drazin inverse is investigated in the matrix theory (particularly in the topic of generalized inverses) and also in the ring theory; see, for example, [1].Generally speaking, applying Schröder's general method (often called Schröder-Traub's sequence [2]) to the nonlinear matrix equation A
X
=
I, one obtains the following scheme [3]:
(1)
X
k
+
1
=
X
k
(
I
+
Y
k
+
Y
k
2
+
⋯
+
Y
k
n
-
1
)
=
X
k
(
I
+
Y
k
(
I
+
Y
k
(
⋯
+
Y
k
)
⋯
)
)
,
k
=
0,1
,
2
,
…
,
of order n, requiring n Horner's matrix multiplications, where Y
k
=
I
-
A
X
k.The application of such (fixed-point type) matrix iterative methods is not limited to the matrix inversion for square nonsingular matrices [4, 5]. In fact and under some fair conditions, one may construct a sequence of iterates converging to the Moore-Penrose inverse [6], the weighted Moore-Penrose inverse [7], the Drazin inverse [8], or the outer inverse in the field of generalized inverses. Such extensions alongside the asymptotical stability of matrix iterations in the form (1) encouraged many authors to present new schemes or work on the application of such methods in different fields of sciences and engineering; see, for example, [9–12].Choosingn
=
2 and n
=
3 in (1) reduces to the well-known methods of Schulz [13] and Chebyshev in matrix inversion. Note that any method extracted from Sen-Prabhu scheme (1) requires n matrix-matrix multiplications to achieve the convergence order n. In this work, we are interested in proposing a new scheme, at which a convergence order p can be attained by fewer matrix-matrix multiplications than p.It is of great importance to arrive at the convergence phase by a valid initial valueX
0 in matrix iterative methods. An interesting initial matrix was developed and introduced by Ben-Israel and Greville in [14] as follows:
(2)
X
0
=
α
A
*
,
where 0
<
α
<
2
/
∥
A
∥
2
2, once the user wants to find the Moore-Penrose inverse.The rest of the paper has been organized as follows. Section2 describes a contribution of the paper alongside a convergence analysis, while, in Section 3, we will extend the new method for finding the Drazin inverse as well. Section 4 is devoted to the computational examples. Section 5 concludes the paper.


## 2. A New Method

Let us consider theinverse-finder informational efficiency index [15], which states that if ξ and ϖ stand for the rate of convergence and the number of matrix-by-matrix multiplications in floating point arithmetics for a matrix method in matrix inversion, then the index is
(3)
IIEI
=
ξ
ϖ
.Based on (3), we must design a method, at which the number of matrix-matrix products is fewer than the local convergence order. The first of such an attempt dated back to the earlier works of Ostrowski in [16], wherein he suggested that a robust way for achieving such a goal is in proper matrix factorizing.Now, let us first apply the followingnew nonlinear equation solver:
(4)
y
k
=
x
k
-
f
′
(
x
k
)
-
1
f
(
x
k
)
,
z
k
=
x
k
-
f
(
y
k
)
-
1
[
f
(
x
k
)
-
(
2
3
)
f
(
y
k
)
]
×
(
1
-
(
1
3
)
f
′
(
x
k
)
-
1
f
(
y
k
)
)
,
x
k
+
1
=
z
k
-
f
′
(
z
k
)
-
1
f
(
z
k
)
-
(
1
2
)
[
f
′
(
z
k
)
-
1
f
′′
(
z
k
)
]
[
f
′
(
z
k
)
-
1
f
(
z
k
)
]
2
,
k
=
0,1
,
2
,
…
,
on the matrix equation f
(
x
)
=
x
-
1
-
a. Next, we obtain
(5)
X
k
+
1
=
1
729
X
k
φ
(
k
)
=
1
729
X
k
(
7047
I
-
30726
ψ
k
+
79712
ψ
k
2
-
136638
ψ
k
3
+
162450
ψ
k
4
-
136752
ψ
k
5
+
81684
ψ
k
6
-
34137
ψ
k
7
+
9663
ψ
k
8
-
1746
ψ
k
9
+
180
ψ
k
10
-
8
ψ
k
11
)
,
k
=
0,1
,
2
,
…
,
where ψ
k
=
A
X
k. Note that a background on the construction of iterative methods for solving nonlinear equations and their applications might be found in [17–20].Using proper factorizing, we attain the following iteration for matrix inversion, at whichX
0 is an initial approximation to A
-
1:
(6)
ψ
k
=
A
X
k
,
ζ
k
=
-
29
I
+
ψ
k
(
33
I
+
ψ
k
(
-
15
I
+
2
ψ
k
)
)
,
κ
k
=
ψ
k
ζ
k
,
X
k
+
1
=
-
1
729
X
k
ζ
k
(
243
I
+
κ
k
(
27
I
+
κ
k
)
)
,
k
=
0,1
,
2
,
…
.The scheme (6) falls in the category of Schulz-type methods, which possesses matrix-by-matrix multiplications to provide approximate inverses. Let us prove the rate of convergence for (6), using the theory of matrix analysis [21] in what follows.Theorem 1.
LetA
=
[
a
i
j
]
n
×
n be a nonsingular complex matrix. If the initial value X
0 satisfies
(7)
∥
E
0
∥
=
∥
I
-
A
X
0
∥
<
1
,
then the matrix iterative method (6) converges with ninth order to A
-
1.Proof .
Let (7) hold, and further assume that E
k
=
I
-
A
X
k, k
≥
0. It is straightforward to have
(8)
E
k
+
1
=
1
729
[
343
E
k
9
+
294
E
k
10
+
84
E
k
11
+
8
E
k
12
]
.
The rest of the proof for this theorem is similar to Theorem 2.1 of [22]. It is hence omitted.


## 3. Extension to the Drazin Inverse

The Drazin inverse, named after Drazin [23], is a generalized inverse which has spectral properties similar to the ordinary inverse of a given square matrix. In some cases, it also provides a solution of a given system of linear equations. Note that the Drazin inverse of a matrix A mostly resembles the true inverse of A.Definition 2.
The smallest nonnegative integerK, such that rank
⁡
(
A
K
+
1
)
=
rank
⁡
(
A
K
), is called the index of A and denoted by ind
(
A
).Definition 3.
LetA
∈
ℂ
n
×
n be a complex matrix; the Drazin inverse of A, denoted by A
D, is the unique matrix X satisfying the following: (1)
A
K
+
1
X
=
A
K,
(2)
X
A
X
=
X,
(3)
A
X
=
X
A, where K
=
ind
(
A
) is the index of A.The Drazin inverse has applications in the theory of finite Markov chains, as well as in the study of differential equations and singular linear difference equations and so forth [24]. To illustrate further, the solution of singular systems has been studied by several authors. For instance, in [25], an analytical solution for continuous systems using the Drazin inverse was presented.Note that a projection matrixP, defined as a matrix such that P
2
=
P, has K
=
1 (or 0) and has the Drazin inverse P
D
=
P. Also, if A is a nilpotent matrix (e.g., a shift matrix), then A
D
=
0. See for more [26].In 2004, Li and Wei in [27] proved that the matrix method of Schulz (the case for n
=
2 in (1)) can be used for finding the Drazin inverse of square matrices. They proposed the following initial matrix:
(9)
X
0
=
α
A
l
,
l
≥
ind
(
A
)
=
K
,
where the parameter α must be chosen such that the condition ∥
F
0
∥
=
∥
A
A
D
-
A
X
0
∥
<
1 is satisfied. Using this initial matrix yields a numerically (asymptotical) stable method for finding the famous Drazin inverse with quadratical convergence.Using the above descriptions, it is easy to apply the efficient method (6) for finding the Drazin inverse in what follows.Theorem 4.
LetA
=
[
a
i
j
]
n
×
n be a square matrix and i
n
d
(
A
)
=
K
≥
1. Choosing the initial approximation X
0 as
(10)
X
0
=
2
tr
⁡
(
A
K
+
1
)
A
K
,
or
(11)
X
0
=
1
2
∥
A
∥
*
k
+
1
A
K
,
wherein tr
⁡
(
·
) stands for the trace of an arbitrary square matrix and ∥
·
∥
* is a matrix norm, then the iterative method (6) converges with ninth order to A
D.Proof.
Consider the notationF
0
=
A
A
D
-
A
X
0 and subsequently the residual matrix as F
k
=
A
A
D
-
A
X
k for finding the Drazin inverse. Then similar to (8), we get
(12)
F
k
+
1
=
A
A
D
-
A
X
k
+
1
=
A
A
D
-
I
+
I
-
A
X
k
+
1
=
A
A
D
-
I
+
E
k
+
1
=
A
A
D
-
I
+
1
729
[
343
E
k
9
+
294
E
k
10
+
84
E
k
11
+
8
E
k
12
]
=
A
A
D
-
I
+
1
729
[
343
(
I
-
A
A
D
+
A
A
D
-
A
X
k
)
9
+
294
(
I
-
A
A
D
+
A
A
D
-
A
X
k
)
10
+
84
(
I
-
A
A
D
+
A
A
D
-
A
X
k
)
11
+
8
(
I
-
A
A
D
+
A
A
D
-
A
X
k
)
12
]
=
A
A
D
-
I
+
1
729
[
343
(
I
-
A
A
D
+
F
k
9
)
+
294
(
I
-
A
A
D
+
F
k
10
)
+
84
(
I
-
A
A
D
+
F
k
11
)
+
8
(
I
-
A
A
D
+
F
k
12
)
]
=
1
729
[
343
F
k
9
+
294
F
k
10
+
84
F
k
11
+
8
F
k
12
]
.
By taking an arbitrary matrix norm to both sides of (12), we attain
(13)
∥
F
k
+
1
∥
≤
1
729
[
343
∥
F
k
∥
9
+
294
∥
F
k
∥
10
+
84
∥
F
k
∥
11
+
8
∥
F
k
∥
12
]
.
In addition, since ∥
F
0
∥
<
1 (the result of choosing the appropriate initial matrices (10) and (11)) by relation (13), we obtain that ∥
F
1
∥
≤
∥
F
0
∥
9. Similarly, ∥
F
k
+
1
∥
≤
∥
F
k
∥
9. Using mathematical induction, we obtain
(14)
∥
F
k
∥
≤
∥
F
0
∥
9
k
,
k
≥
0
.
So, the sequence {
∥
F
k
∥
2
} is strictly monotonically decreasing. Now, by considering δ
k
=
A
D
-
X
k, as the error matrix for finding the Drazin inverse, we have
(15)
A
δ
k
+
1
=
A
A
D
-
A
X
k
+
1
=
F
k
+
1
=
1
729
[
343
F
k
9
+
294
F
k
10
+
84
F
k
11
+
8
F
k
12
]
.
Taking into account (12) and using elementary algebraic transformations, we further derive
(16)
∥
A
δ
k
+
1
∥
≤
1
729
[
343
∥
F
k
∥
9
+
294
∥
F
k
∥
10
+
84
∥
F
k
∥
11
+
8
∥
F
k
∥
12
]
≤
∥
F
k
∥
9
=
∥
A
δ
k
∥
9
≤
∥
A
∥
9
∥
δ
k
∥
9
.
It is now easy to find the error inequality of the new scheme (6) using (16) as follows:
(17)
∥
δ
k
+
1
∥
=
∥
X
k
+
1
-
A
D
∥
=
∥
A
D
A
X
k
+
1
-
A
D
A
A
D
∥
=
∥
A
D
(
A
X
k
+
1
-
A
A
D
)
∥
≤
∥
A
D
∥
∥
A
δ
k
+
1
∥
≤
∥
A
D
∥
∥
A
∥
9
∥
δ
k
∥
9
.
Therefore, the inequalities in (17) immediately lead to the conclusion that X
k
→
A
D as k
→
+
∞ with the ninth order of convergence.Theorem 5.
Considering the same assumptions as in Theorem4, the iterative method (6) has asymptotical stability for finding the Drazin inverse.Proof .
The steps of proving the asymptotical stability of (6) are similar to those that have recently been taken for a general family of methods in [28]. Hence, the proof is omitted.Remark 6.
It should be remarked that the generalization of our proposed scheme for generalized outer inverses, that is,A
T
,
S
(
2
), is straightforward according to the recent work [29].Remark 7.
The new iteration (6) is free from matrix power in its implementation and this allows one to apply it for finding generalized inverses easily.


## 4. Numerical Experiments

We herein present several numerical tests to illustrate the efficiency of the new iterative method to compute the approximate inverses.mathematica 8 [30] has been employed in our calculations. We have carried out the numerical tests with machine precision on a computer with characteristics: Microsoft Windows XP Intel(R), Pentium(R) 4 CPU, 3.20 GHz, with 4 GB of RAM.For comparisons, we have used the methods “Schulz” (n
=
2), “Chebyshev” (n
=
3), “KMS” (n
=
9) in (1), and the proposed method (6). As the programs were running in this paper, we found the running time using the command  AbsoluteTiming[] to report the elapsed CPU time (in seconds) for the examples.Example 8.
The computations of approximate inverses for 10 dense random complex matrices of the dimension 100 are considered and compared as follows:n = 100; number = 10; SeedRandom[1234];
Table[A[l] = RandomComplex[{-2. + I,
2. - I}, {n, n}];,{l, number}];Note thatI
=
-
1. For this example, the stopping criterion is ∥
X
k
+
1
-
X
k
∥
2
≤
1
0
-
5 and the maximum number of iterations allowed is set to 100. The initial choice has been constructed using (2) with α
=
1
/
σ
max
⁡
2. The result of comparisons has been presented in Figures 1 and 2. As could be observed, in all the 10 test problems, our iterative method (6) beats the other existing schemes.Figure 1
Comparison of the number of iterations for solving Example8.Figure 2
Comparison of the elapsed time for solving Example8.Example 9.
The computations of approximate inverses for 10 dense random complex matrices of the dimension 200 are considered and compared as follows:n = 200; number = 10; SeedRandom[1234];
Table[A[l] = RandomComplex[{-2. + I,
2. - I}, {n, n}];,{l, number}];Note again thatI
=
-
1. For this test, the stopping criterion for finding the approximate inverse for the generated random matrices is ∥
X
k
+
1
-
X
k
∥
2
≤
1
0
-
5 and the maximum number of iterations allowed is set to 100 by the initial choice as in Example 8. The numerics are provided in Figures 3 and 4. Results are in harmony with the theoretical aspects and show that the new method is efficient in matrix inversion.Figure 3
Comparison of the number of iterations for solving Example9.Figure 4
Comparison of the elapsed time for solving Example9.Example 10.
The computations of approximate inverses for 10 dense random matrices of the size 200 are investigated in what follows:n = 200; number = 10; SeedRandom[1];
Table[A[l] = RandomReal[{0, 1},
{n, n}];, {l, number}];here, the stopping criterion is∥
X
k
+
1
-
X
k
∥
F
≤
1
0
-
8. Results are provided in Figures 5 and 6, which indicate that the new method is better in terms of the number of iterations and behaves similarly to the other well-known schemes of Schulz and Chebyshev in terms of the computational time.Figure 5
Comparison of the number of iterations for solving Example10.Figure 6
Comparison of the elapsed time for solving Example10.The order of convergence and the number of matrix-matrix products are not the only factors to govern the efficiency of an algorithm per computing step in matrix iterations. Generally speaking, the stopping criterion could be reported as one of the important factors, which could indirectly affect the computational time of an algorithm in implementations, especially when trying to find the generalized inverses.Although in the above implementations we considered the stop termination on two successive iterates, this is not a reliable termination when dealing with some large ill-conditioned matrices. For example, the reliable stopping criterion in the above examples is∥
I
-
X
k
A
∥
F
≤
ϵ.Example 11.
The aim of this example is to apply the discussions of Section4, for finding the Drazin inverse of the following square matrix (taken from [27]):(18)
A
=
(
2
0.4
0
0
0
0
0
0
0
0
0
0
-
2
0.4
0
0
0
0
0
0
0
0
0
0
-
1
-
1
1
-
1
0
0
0
0
-
1
0
0
0
-
1
-
1
-
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
-
1
-
1
0
0
-
1
0
0
0
0
0
1
1
-
1
-
1
0
0
0
0
0
0
0
-
1
-
2
0.4
0
0
0
0
0
0
0
0
0
0
2
0.4
0
0
0
0
0
0
0
-
1
0
0
0
0
0
0
1
-
1
-
1
-
1
0
0
0
0
0
0
0
0
-
1
1
-
1
-
1
0
0
0
0
0
0
0
0
0
0
0.4
-
2
0
0
0
0
0
0
0
0
0
0
0.4
2
)
,withK
=
ind
(
A
)
=
3. Using (6) and the stopping termination ∥
X
k
+
1
-
X
k
∥
∞
≤
1
0
-
8 and (10), we could obtain the Drazin inverse as follows:(19)
A
D
=
(
0.25
-
0.25
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
1.25
1.25
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
-
1.66406
-
0.992187
0.25
-
0.25
0
.
0
.
0
.
0
.
-
0.0625
-
0.0625
0
.
0.15625
-
1.19531
-
0.679687
-
0.25
0.25
0
.
0
.
0
.
0
.
-
0.0625
0.1875
0.6875
1.34375
-
2.76367
-
1.04492
-
1.875
-
1.25
-
1.25
1.25
1.25
1.25
1.48438
2.57813
3.32031
6.64063
-
2.76367
-
1.04492
-
1.875
-
1.25
-
1.25
1.25
1.25
1.25
1.48438
2.57813
4.57031
8.51563
14.1094
6.30078
6.625
3.375
5
.
-
3
.
-
5
.
-
5
.
-
4.1875
-
8.5
-
10.5078
-
22.4609
-
19.3242
-
8.50781
-
9.75
-
5.25
-
7.5
4.5
7.5
7.5
6.375
12.5625
15.9766
33.7891
-
0.625
-
0.3125
0
.
0
.
0
.
0
.
0
.
0
.
0.25
-
0.25
-
0.875
-
1.625
-
1.25
-
0.9375
0
.
0
.
0
.
0
.
0
.
0
.
-
0.25
0.25
-
0.875
-
1.625
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
1.25
1.25
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
0
.
-
0.25
0.25
)
.Due to the efficiency of the new method, we did not compare different methods for this test and just bring forward the results of (6). Checking the conditions of Definition 4.2. yields ∥
A
k
+
1
A
D
-
A
k
∥
∞
=
3.69482
×
1
0
-
13,∥
A
D
A
A
D
-
A
D
∥
∞
=
1.00933
×
1
0
-
10, and ∥
A
A
D
-
A
D
A
∥
∞
=
2.31148
×
1
0
-
11, which supports the theoretical discussions.


## 5. Summary

In this paper, we have developed a high order matrix method for finding approximate inverses for nonsingular square matrices. It has been proven that the contributed method reaches the convergence order nine by using seven matrix-matrix multiplications which makes its informational index as9
/
7
≈
1.288
>
1.We have also discussed the importance of the well-known Drazin inverse and how to find it numerically by the proposed method. Numerical examples were also employed to support the underlying theory of the paper.



---

*Source: 137486-2014-04-14.xml*