Abstract
In this note we deal with two problems: the first regards the efficiency in approximating the inverse of a matrix by the Schultz-type methods, and the second is the problem of evaluating the errors in the approximation of the inverses of the perturbed matrices.
Author
Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)
Keywords
matrix inverse; iterative methods; Schultz method; perturbations; error evaluation.
Cite this paper as:
I. Păvăloiu, On approximating the inverse of a matrix, Creative Math., 12 (2003), pp. 15-20.
About this paper
Journal
Publisher Name
Universitatea Tehnica din Cluj-Napoca
Article on the journal website
Print ISSN
1584-286X
Online ISSN
1843-441X
References
[1] Herzberger J., Explizite Shulz Verfahren hoherer ordrnung zur approximation der reversen matrix, Z. Angew Math. und Mech. 1988, Bd. 68, No. 5, pp. 494-496
[2] Ostrowski M.A., Solution of equations in euclidian and Banach spaces, Academic Press. New York and London (1975)
[3] Stickel E., On a class of high order methods for investing matrices, Z. Angew Math. und Mech. 1987, Bd. 67, No. 7, pp. 334-336
Paper (preprint) in HTML form
On approximating the inverse of a matrix
Abstract
In this note we deal with two problems: the first regards the efficiency in approximating the inverse of a matrix by the Shulz-type methods, and the second is the problem of evaluating the errors in the approximation of the inverses of the perturbed matrices.
1. Introduction
In this note we deal with two problems: the first regards the efficiency in approximating the inverse of a matrix by the Shulz-type methods, and the second is the problem of evaluating the errors in the approximation of the inverses of the perturbed matrices.
As it is well known, given a nonsingular matrix A inR^(m xx m)A \in \mathbb{R}^{m \times m} and a matrix D_(0)inR^(m xx m)D_{0} \in \mathbb{R}^{m \times m} such that
{:(1)||I-AD_(0)|| <= q < 1:}\begin{equation*}
\left\|I-A D_{0}\right\| \leq q<1 \tag{1}
\end{equation*}
with q inRq \in \mathbb{R} and II the mm-th order unit matrix, then, for k inN,k >= 2k \in \mathbb{N}, k \geq 2 fixed, the sequence of matrices (D_(n))_(n >= 0)\left(D_{n}\right)_{n \geq 0} given by
{:[(2)F_(n)=I-AD_(n)],[D_(n+1)=D_(n)(I+F_(n)+F_(n)^(2)+cdots+F_(n)^(k-1))","quad n=0","1","dots]:}\begin{align*}
F_{n} & =I-A D_{n} \tag{2}\\
D_{n+1} & =D_{n}\left(I+F_{n}+F_{n}^{2}+\cdots+F_{n}^{k-1}\right), \quad n=0,1, \ldots
\end{align*}
is convergent and lim_(n rarr oo)D_(n)=A^(-1)\lim _{n \rightarrow \infty} D_{n}=A^{-1}. Moreover, (F_(n))_(n >= 0)\left(F_{n}\right)_{n \geq 0} verifies
{:(3)F_(n+1)=F_(n)^(k)","quad n=0","1","dots:}\begin{equation*}
F_{n+1}=F_{n}^{k}, \quad n=0,1, \ldots \tag{3}
\end{equation*}
The methods of type (2) represent generalizations of the well known Shulz method. Relation (3) shows that the convergence order of sequence (D_(n))_(n >= 0)\left(D_{n}\right)_{n \geq 0} is k,k >= 2k, k \geq 2.
We introduce the notion of efficiency index of method (2). We notice that at each iteration step, the number of the matrix sums required is equal to the number of matrix products which appear in (2). Moreover, for computing the sum I+F_(n)+cdots+F_(n)^(k)I+F_{n}+\cdots+F_{n}^{k} we may use a method similar to the Horner scheme, i.e.
{:(4)I+F_(n)+F_(n)^(2)+cdots+F_(n)^(k-1)={{[(F_(n)+I)F_(n)+I]F_(n)+I}+cdots}:}\begin{equation*}
I+F_{n}+F_{n}^{2}+\cdots+F_{n}^{k-1}=\left\{\left\{\left[\left(F_{n}+I\right) F_{n}+I\right] F_{n}+I\right\}+\cdots\right\} \tag{4}
\end{equation*}
In this way the matrix sums required reduce to sums in which one term is the identity matrix. This remark is also valid for the term F_(n)=I-AD_(n)F_{n}=I-A D_{n}. The operation consisting of one matrix product and one matrix sum (regardless of their order) we call it computing unit.
Definition 1. The efficiency index of method (2) is given by
{:(5)E_(k)=k^(1//s)",":}\begin{equation*}
E_{k}=k^{1 / s}, \tag{5}
\end{equation*}
where s inNs \in \mathbb{N} represents the number of computing units required at each iteration step of method (2).
This definition is given by analogy to the efficiency index introduced by A.M. Ostrowski in [2]. The definition may also be motivated by the following reasoning.
From (3) it follows
{:(6)||F_(n+1)|| <= ||F_(n)||^(k)","quad n=0","1","dots:}\begin{equation*}
\left\|F_{n+1}\right\| \leq\left\|F_{n}\right\|^{k}, \quad n=0,1, \ldots \tag{6}
\end{equation*}
whence
{:(7)||F_(n+1)|| <= ||F_(0)||^(k^(n+1))","quad n=0","1","dots:}\begin{equation*}
\left\|F_{n+1}\right\| \leq\left\|F_{0}\right\|^{k^{n+1}}, \quad n=0,1, \ldots \tag{7}
\end{equation*}
The above inequalities lead to the following error bounds:
{:(8)||A^(-1)-D_(n)|| <= ||A^(-1)||||F_(0)||^(k^(n))","quad n=0","1","dots:}\begin{equation*}
\left\|A^{-1}-D_{n}\right\| \leq\left\|A^{-1}\right\|\left\|F_{0}\right\|^{k^{n}}, \quad n=0,1, \ldots \tag{8}
\end{equation*}
Consider now two methods of type (2), having the convergence orders k_(1)k_{1} and k_(2)k_{2} respectively. Assume that, for achieving the same precision, these methods require n_(1)n_{1} respectively n_(2)n_{2} iteration steps. Then (8) implies
{:(9)k_(1)^(n_(1))=k_(2)^(n_(2)):}\begin{equation*}
k_{1}^{n_{1}}=k_{2}^{n_{2}} \tag{9}
\end{equation*}
The total number of computing units is n_(1)s_(1)n_{1} s_{1} in the first case and n_(2)s_(2)n_{2} s_{2} in the second case.
It is clear now that the method with convergence order k_(1)k_{1} is more efficient than the other if
{:(10)n_(1)s_(1) < n_(2)s_(2):}\begin{equation*}
n_{1} s_{1}<n_{2} s_{2} \tag{10}
\end{equation*}
Relations (9) and (10) lead us to
{:(11)k_(1)^(1//s_(1)) > k_(2)^(1//s_(2)):}\begin{equation*}
k_{1}^{1 / s_{1}}>k_{2}^{1 / s_{2}} \tag{11}
\end{equation*}
Taking into account Definition 1, it follows that among the methods of type (2) for different values of kk, the most efficient is given by the one with high efficiency index.
We shall determine in the following section the optimal method, i.e., having the high efficiency index, when k inN,k >= 2k \in \mathbb{N}, k \geq 2.
2. Optimal efficiency index
Assume that we use (4) at each iteration step in (2). It can be easily seen that for the sum in (4) there are needed k-2k-2 matrix products. Relation (2) shows that 2 more matrix products are required at each iteration step, so in total we need kk matrix products.
Taking into account (5), it follows that the efficiency index of method (2) is given by
{:(12) bar(E)_(k)=k^(1//k):}\begin{equation*}
\bar{E}_{k}=k^{1 / k} \tag{12}
\end{equation*}
Considering the function f:(0,+oo)rarrR,f(x)=x^((1)/(x))f:(0,+\infty) \rightarrow \mathbb{R}, f(x)=x^{\frac{1}{x}}, it can be easily seen that this function attains a maximum value at x=ex=e. Since ff is increasing on ( 0,e0, e ) and decreasing on ( e,+ooe,+\infty ), it follows that bar(E)_(k)\bar{E}_{k} is the largest for k=3k=3.
We have proved the following result.
Theorem 2. Among the methods (2) for k=N,k >= 2k=\mathbb{N}, k \geq 2, the method with highest efficiency index is given by:
Theorem 2. Among the methods (2) for k=N,k >= 2k=\mathbb{N}, k \geq 2, the method with highest efficiency index is given by:
{:(13){[F_(n)=I-AD_(n)],[D_(n+1)=D_(n)(I+F_(n)+F_(n)^(2))","n=0","1","dots]:}:}\left\{\begin{array}{l}
F_{n}=I-A D_{n} \tag{13}\\
D_{n+1}=D_{n}\left(I+F_{n}+F_{n}^{2}\right), n=0,1, \ldots
\end{array}\right.
with D_(0)D_{0} verifying ||I-AD_(0)|| <= q < 1\left\|I-A D_{0}\right\| \leq q<1.
By (4), the above method may be written as
By (4), the above method may be written as
{:[(14)F_(n)=I-AD_(n)],[D_(n+1)=D_(n)[(F_(n)+I)F_(n)+I]","quad n=0","1","dots]:}\begin{align*}
F_{n} & =I-A D_{n} \tag{14}\\
D_{n+1} & =D_{n}\left[\left(F_{n}+I\right) F_{n}+I\right], \quad n=0,1, \ldots
\end{align*}
In this case, (7) becomes
{:(15)||F_(n+1)|| <= ||F_(0)||^(3^(n+1))","quad n=0","1","dots:}\begin{equation*}
\left\|F_{n+1}\right\| \leq\left\|F_{0}\right\|^{3^{n+1}}, \quad n=0,1, \ldots \tag{15}
\end{equation*}
and for the error bounds one has
{:(16)||A^(-1)-D_(n)|| <= ||A^(-1)||||F_(n)|| <= ||A^(-1)||||F_(0)||^(3^(n))","n=0","1","dots.:}\begin{equation*}
\left\|A^{-1}-D_{n}\right\| \leq\left\|A^{-1}\right\|\left\|F_{n}\right\| \leq\left\|A^{-1}\right\|\left\|F_{0}\right\|^{3^{n}}, n=0,1, \ldots . \tag{16}
\end{equation*}
It can be easily seen that under (1), one has the inequality
{:(17)||A^(-1)|| <= (||D_(0)||)/(1-||F_(0)||):}\begin{equation*}
\left\|A^{-1}\right\| \leq \frac{\left\|D_{0}\right\|}{1-\left\|F_{0}\right\|} \tag{17}
\end{equation*}
whence
{:(18)||A^(-1)-D_(n)|| <= ||D_(0)||(||F_(0)||^(3^(n)))/(1-||F_(0)||)","n=0","1","dots:}\begin{equation*}
\left\|A^{-1}-D_{n}\right\| \leq\left\|D_{0}\right\| \frac{\left\|F_{0}\right\|^{3^{n}}}{1-\left\|F_{0}\right\|}, n=0,1, \ldots \tag{18}
\end{equation*}
Analogously, for any method of type (2) one may deduce the evaluation
{:(19)||A^(-1)-D_(n)|| <= ||D_(0)||(||F_(0)||^(k^(n)))/(1-||F_(0)||)","quad n=0","1","dots:}\begin{equation*}
\left\|A^{-1}-D_{n}\right\| \leq\left\|D_{0}\right\| \frac{\left\|F_{0}\right\|^{k^{n}}}{1-\left\|F_{0}\right\|}, \quad n=0,1, \ldots \tag{19}
\end{equation*}
3. Error bounds in case of perturbed matrices
In practice, the elements of the matrix AA are usually obtained as results of certain experiments, measurements, approximations etc. Therefore their values are altered by errors. Consequently we replace AA by the approximation widetilde(A)\widetilde{A}. For a rigorous interpretation of the results, it is necessary to know an error bound epsi > 0\varepsilon>0 for which
{:(20)||A- widetilde(A)|| <= epsi:}\begin{equation*}
\|A-\widetilde{A}\| \leq \varepsilon \tag{20}
\end{equation*}
Instead of sequence (D_(n))_(n >= 0)\left(D_{n}\right)_{n \geq 0} we consider ( widetilde(D)_(n))_(n >= 0)\left(\widetilde{D}_{n}\right)_{n \geq 0}, generated by
{:[(21) widetilde(F)_(n)=I- widetilde(A) widetilde(D)_(n)],[ widetilde(D)_(n+1)= widetilde(D)_(n)(I+ widetilde(F)_(n)+ widetilde(F)_(n)^(2)+cdots+ widetilde(F)_(n)^(k-1))","quad n=0","1","dots]:}\begin{align*}
\widetilde{F}_{n} & =I-\widetilde{A} \widetilde{D}_{n} \tag{21}\\
\widetilde{D}_{n+1} & =\widetilde{D}_{n}\left(I+\widetilde{F}_{n}+\widetilde{F}_{n}^{2}+\cdots+\widetilde{F}_{n}^{k-1}\right), \quad n=0,1, \ldots
\end{align*}
We assume that the matrices widetilde(A)\widetilde{A} and widetilde(D)_(0)\widetilde{D}_{0} above obey
{:(22)||I-( widetilde(A)) widetilde(D)_(0)|| <= bar(q) < 1:}\begin{equation*}
\left\|I-\widetilde{A} \widetilde{D}_{0}\right\| \leq \bar{q}<1 \tag{22}
\end{equation*}
It follows that widetilde(A)\widetilde{A} is invertible: EE widetilde(A)^(-1)\exists \widetilde{A}^{-1} and by (18) we get
{:(23)|| widetilde(A)^(-1)- widetilde(D)_(n)|| <= || widetilde(D)_(0)||(|| widetilde(F)_(0)||^(k^(n)))/(1-|| widetilde(F)_(0)||)","quad n=0","1","dots:}\begin{equation*}
\left\|\widetilde{A}^{-1}-\widetilde{D}_{n}\right\| \leq\left\|\widetilde{D}_{0}\right\| \frac{\left\|\widetilde{F}_{0}\right\|^{k^{n}}}{1-\left\|\widetilde{F}_{0}\right\|}, \quad n=0,1, \ldots \tag{23}
\end{equation*}
We are interested in conditions which ensure that widetilde(A)\widetilde{A} is nonsingular. We consider the identity
I- widetilde(A)^(-1)A= widetilde(A)^(-1)( widetilde(A)-A)I-\widetilde{A}^{-1} A=\widetilde{A}^{-1}(\widetilde{A}-A)
which implies
||I- widetilde(A)^(-1)A|| <= || widetilde(A)^(-1)||epsi\left\|I-\widetilde{A}^{-1} A\right\| \leq\left\|\widetilde{A}^{-1}\right\| \varepsilon
whence, by (17) we get
{:(24)||I- widetilde(A)^(-1)A|| <= (epsi|| widetilde(D)_(0)||)/(1-|| widetilde(F)_(0)||):}\begin{equation*}
\left\|I-\widetilde{A}^{-1} A\right\| \leq \frac{\varepsilon\left\|\widetilde{D}_{0}\right\|}{1-\left\|\widetilde{F}_{0}\right\|} \tag{24}
\end{equation*}
This relation shows that for the existence of the inverse for widetilde(A)^(-1)A\widetilde{A}^{-1} A it suffices that
{:(25)r=(epsi|| widetilde(D)_(0)||)/(1-|| widetilde(F)_(0)||) < 1:}\begin{equation*}
r=\frac{\varepsilon\left\|\widetilde{D}_{0}\right\|}{1-\left\|\widetilde{F}_{0}\right\|}<1 \tag{25}
\end{equation*}
whence for epsi\varepsilon we get the condition
{:(26)epsi < (1-||F_(0)||)/(|| widetilde(D)_(0)||):}\begin{equation*}
\varepsilon<\frac{1-\left\|F_{0}\right\|}{\left\|\widetilde{D}_{0}\right\|} \tag{26}
\end{equation*}
Further,
A^(-1)=( widetilde(A)^(-1)A)^(-1) widetilde(A)^(-1)A^{-1}=\left(\widetilde{A}^{-1} A\right)^{-1} \widetilde{A}^{-1}
whence
||A^(-1)|| <= || widetilde(A)^(-1)|||| widetilde(A)^(-1)A|| <= (|| widetilde(D)_(0)||)/(1-|| widetilde(F)_(0)||-epsi|| widetilde(D)_(0)||)\left\|A^{-1}\right\| \leq\left\|\widetilde{A}^{-1}\right\|\left\|\widetilde{A}^{-1} A\right\| \leq \frac{\left\|\widetilde{D}_{0}\right\|}{1-\left\|\widetilde{F}_{0}\right\|-\varepsilon\left\|\widetilde{D}_{0}\right\|}
and (26) attracts 1-|| widetilde(F)_(0)||-epsi|| widetilde(D)_(0)|| > 01-\left\|\widetilde{F}_{0}\right\|-\varepsilon\left\|\widetilde{D}_{0}\right\|>0.
The following inequality can be easily proved
The following inequality can be easily proved
{:(27)||A^(-1)- widetilde(A)^(-1)|| <= (|| widetilde(D)_(0)||^(2)epsi)/((1-|| widetilde(F)_(0)||)(1-|| widetilde(F)_(0)||-epsi|| widetilde(D)_(0)||)):}\begin{equation*}
\left\|A^{-1}-\widetilde{A}^{-1}\right\| \leq \frac{\left\|\widetilde{D}_{0}\right\|^{2} \varepsilon}{\left(1-\left\|\widetilde{F}_{0}\right\|\right)\left(1-\left\|\widetilde{F}_{0}\right\|-\varepsilon\left\|\widetilde{D}_{0}\right\|\right)} \tag{27}
\end{equation*}
which, together with (23) leads to
{:(28)||A^(-1)- widetilde(D)_(n)|| <= (|| widetilde(D)_(0)||)/(1-|| widetilde(F)_(0)||)[(|| widetilde(D)_(0)||epsi)/(1-|| widetilde(F)_(0)||-epsi|| widetilde(D)_(0)||)+||F_(0)||^(t^(n))]","n=0","1","dots:}\begin{equation*}
\left\|A^{-1}-\widetilde{D}_{n}\right\| \leq \frac{\left\|\widetilde{D}_{0}\right\|}{1-\left\|\widetilde{F}_{0}\right\|}\left[\frac{\left\|\widetilde{D}_{0}\right\| \varepsilon}{1-\left\|\widetilde{F}_{0}\right\|-\varepsilon\left\|\widetilde{D}_{0}\right\|}+\left\|F_{0}\right\|^{t^{n}}\right], n=0,1, \ldots \tag{28}
\end{equation*}
This inequality provides a priori evaluations for the error. If we want to stop the iterations at a certain step bar(n)\bar{n} such that || widetilde(F)_( bar(n))|| <= epsi_(1),epsi_(1) > 0\left\|\widetilde{F}_{\bar{n}}\right\| \leq \varepsilon_{1}, \varepsilon_{1}>0 given, then by (7) and (17) it follows
|| widetilde(A)^(-1)- widetilde(D)_( bar(n))|| <= (|| widetilde(D)_(0)||)/(1-|| widetilde(F)_(0)||)epsi_(1)\left\|\widetilde{A}^{-1}-\widetilde{D}_{\bar{n}}\right\| \leq \frac{\left\|\widetilde{D}_{0}\right\|}{1-\left\|\widetilde{F}_{0}\right\|} \varepsilon_{1}
which, together with (27) lead to
||A^(-1)- widetilde(D)_( bar(n))|| <= (|| widetilde(D)_(0)||)/(1-|| widetilde(F)_(0)||)[epsi_(1)+(epsi|| widetilde(D)_(0)||)/(1-|| widetilde(F)_(0)||-epsi|| widetilde(D)_(0)||)]\left\|A^{-1}-\widetilde{D}_{\bar{n}}\right\| \leq \frac{\left\|\widetilde{D}_{0}\right\|}{1-\left\|\widetilde{F}_{0}\right\|}\left[\varepsilon_{1}+\frac{\varepsilon\left\|\widetilde{D}_{0}\right\|}{1-\left\|\widetilde{F}_{0}\right\|-\varepsilon\left\|\widetilde{D}_{0}\right\|}\right]
which is an a posteriori error bound.
References
[1] Herzberger J., Explizite Shulz Verfahren höherer ordrnung zur approximation der reversen matrix, Z. Angew Math. und Mech. 1988, Bd. 68, No. 5, pp. 494-496
[2] Ostrowski M.A., Solution of equations in euclidian and Banach spaces, Academic Press. New York and London (1975)
[3] Stickel E., On a class of high order methods for investing matrices, Z. Angew Math. und Mech. 1987, Bd. 67, No. 7, pp. 334-336
"T. Popoviciu" Institute of Numerical Analysis
Str. Fântânele, nr.57, Bloc B7, sc.II, etaj 5, ap. 67-68
Cluj-Napoca, Romania
E-mail address: pavaloiu@ictp.acad.ro
[2] Ostrowski M.A., Solution of equations in euclidian and Banach spaces, Academic Press. New York and London (1975)
[3] Stickel E., On a class of high order methods for investing matrices, Z. Angew Math. und Mech. 1987, Bd. 67, No. 7, pp. 334-336
"T. Popoviciu" Institute of Numerical Analysis
Str. Fântânele, nr.57, Bloc B7, sc.II, etaj 5, ap. 67-68
Cluj-Napoca, Romania
E-mail address: pavaloiu@ictp.acad.ro
- Received: 28.02.2003; In revised form: 30.10.2003
Key words and phrases. Inverse of a matrix, perturbed matrix, efficiency in approximating the inverse of a matrix.