On approximating the inverse of a matrix

Ion Păvăloiu
(original), html, paper

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.

PDF

PDF file.

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

Creative Mathematics

Publisher Name

Universitatea Tehnica din Cluj-Napoca

Article on the journal website

https://www.creative-mathematics.cunbm.utcluj.ro/article/on-approximating-the-inverse-of-matrix/

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

2003-094-Pavaloiu-Creative-Math.-On-approx-the-inv-matrix-15-07-15

On approximating the inverse of a matrix

Ion Păvăloiu

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 ∈ R m × m A ∈ R m × m A inR^(m xx m)A \in \mathbb{R}^{m \times m}A∈Rm×m and a matrix D 0 ∈ R m × m D 0 ∈ R m × m D_(0)inR^(m xx m)D_{0} \in \mathbb{R}^{m \times m}D0∈Rm×m such that
(1) ‖ I − A D 0 ‖ ≤ q < 1 (1) I − A D 0 ≤ q < 1 {:(1)||I-AD_(0)|| <= q < 1:}\begin{equation*} \left\|I-A D_{0}\right\| \leq q<1 \tag{1} \end{equation*}(1)‖I−AD0‖≤q<1
with q ∈ R q ∈ R q inRq \in \mathbb{R}q∈R and I I III the m m mmm-th order unit matrix, then, for k ∈ N , k ≥ 2 k ∈ N , k ≥ 2 k inN,k >= 2k \in \mathbb{N}, k \geq 2k∈N,k≥2 fixed, the sequence of matrices ( D n ) n ≥ 0 D n n ≥ 0 (D_(n))_(n >= 0)\left(D_{n}\right)_{n \geq 0}(Dn)n≥0 given by
(2) F n = I − A D n D n + 1 = D n ( I + F n + F n 2 + ⋯ + F n k − 1 ) , n = 0 , 1 , … (2) F n = I − A D n D n + 1 = D n I + F n + F n 2 + ⋯ + F n k − 1 , n = 0 , 1 , … {:[(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*}(2)Fn=I−ADnDn+1=Dn(I+Fn+Fn2+⋯+Fnk−1),n=0,1,…
is convergent and lim n → ∞ D n = A − 1 lim n → ∞   D n = A − 1 lim_(n rarr oo)D_(n)=A^(-1)\lim _{n \rightarrow \infty} D_{n}=A^{-1}limn→∞Dn=A−1. Moreover, ( F n ) n ≥ 0 F n n ≥ 0 (F_(n))_(n >= 0)\left(F_{n}\right)_{n \geq 0}(Fn)n≥0 verifies
(3) F n + 1 = F n k , n = 0 , 1 , … (3) F n + 1 = F n k , n = 0 , 1 , … {:(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*}(3)Fn+1=Fnk,n=0,1,…
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 D n n ≥ 0 (D_(n))_(n >= 0)\left(D_{n}\right)_{n \geq 0}(Dn)n≥0 is k , k ≥ 2 k , k ≥ 2 k,k >= 2k, k \geq 2k,k≥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 + ⋯ + F n k I + F n + ⋯ + F n k I+F_(n)+cdots+F_(n)^(k)I+F_{n}+\cdots+F_{n}^{k}I+Fn+⋯+Fnk we may use a method similar to the Horner scheme, i.e.
(4) I + F n + F n 2 + ⋯ + F n k − 1 = { { [ ( F n + I ) F n + I ] F n + I } + ⋯ } (4) I + F n + F n 2 + ⋯ + F n k − 1 = F n + I F n + I F n + I + ⋯ {:(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*}(4)I+Fn+Fn2+⋯+Fnk−1={{[(Fn+I)Fn+I]Fn+I}+⋯}
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 − A D n F n = I − A D n F_(n)=I-AD_(n)F_{n}=I-A D_{n}Fn=I−ADn. 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 , (5) E k = k 1 / s , {:(5)E_(k)=k^(1//s)",":}\begin{equation*} E_{k}=k^{1 / s}, \tag{5} \end{equation*}(5)Ek=k1/s,
where s ∈ N s ∈ N s inNs \in \mathbb{N}s∈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 , n = 0 , 1 , … (6) F n + 1 ≤ F n k , n = 0 , 1 , … {:(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*}(6)‖Fn+1‖≤‖Fn‖k,n=0,1,…
whence
(7) ‖ F n + 1 ‖ ≤ ‖ F 0 ‖ k n + 1 , n = 0 , 1 , … (7) F n + 1 ≤ F 0 k n + 1 , n = 0 , 1 , … {:(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*}(7)‖Fn+1‖≤‖F0‖kn+1,n=0,1,…
The above inequalities lead to the following error bounds:
(8) ‖ A − 1 − D n ‖ ≤ ‖ A − 1 ‖ ‖ F 0 ‖ k n , n = 0 , 1 , … (8) A − 1 − D n ≤ A − 1 F 0 k n , n = 0 , 1 , … {:(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*}(8)‖A−1−Dn‖≤‖A−1‖‖F0‖kn,n=0,1,…
Consider now two methods of type (2), having the convergence orders k 1 k 1 k_(1)k_{1}k1 and k 2 k 2 k_(2)k_{2}k2 respectively. Assume that, for achieving the same precision, these methods require n 1 n 1 n_(1)n_{1}n1 respectively n 2 n 2 n_(2)n_{2}n2 iteration steps. Then (8) implies
(9) k 1 n 1 = k 2 n 2 (9) k 1 n 1 = k 2 n 2 {:(9)k_(1)^(n_(1))=k_(2)^(n_(2)):}\begin{equation*} k_{1}^{n_{1}}=k_{2}^{n_{2}} \tag{9} \end{equation*}(9)k1n1=k2n2
The total number of computing units is n 1 s 1 n 1 s 1 n_(1)s_(1)n_{1} s_{1}n1s1 in the first case and n 2 s 2 n 2 s 2 n_(2)s_(2)n_{2} s_{2}n2s2 in the second case.
It is clear now that the method with convergence order k 1 k 1 k_(1)k_{1}k1 is more efficient than the other if
(10) n 1 s 1 < n 2 s 2 (10) n 1 s 1 < n 2 s 2 {:(10)n_(1)s_(1) < n_(2)s_(2):}\begin{equation*} n_{1} s_{1}<n_{2} s_{2} \tag{10} \end{equation*}(10)n1s1<n2s2
Relations (9) and (10) lead us to
(11) k 1 1 / s 1 > k 2 1 / s 2 (11) k 1 1 / s 1 > k 2 1 / s 2 {:(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*}(11)k11/s1>k21/s2
Taking into account Definition 1, it follows that among the methods of type (2) for different values of k k kkk, 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 ∈ N , k ≥ 2 k ∈ N , k ≥ 2 k inN,k >= 2k \in \mathbb{N}, k \geq 2k∈N,k≥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 − 2 k − 2 k-2k-2k−2 matrix products. Relation (2) shows that 2 more matrix products are required at each iteration step, so in total we need k k kkk matrix products.
Taking into account (5), it follows that the efficiency index of method (2) is given by
(12) E ¯ k = k 1 / k (12) E ¯ k = k 1 / k {:(12) bar(E)_(k)=k^(1//k):}\begin{equation*} \bar{E}_{k}=k^{1 / k} \tag{12} \end{equation*}(12)E¯k=k1/k
Considering the function f : ( 0 , + ∞ ) → R , f ( x ) = x 1 x f : ( 0 , + ∞ ) → R , f ( x ) = x 1 x f:(0,+oo)rarrR,f(x)=x^((1)/(x))f:(0,+\infty) \rightarrow \mathbb{R}, f(x)=x^{\frac{1}{x}}f:(0,+∞)→R,f(x)=x1x, it can be easily seen that this function attains a maximum value at x = e x = e x=ex=ex=e. Since f f fff is increasing on ( 0 , e 0 , e 0,e0, e0,e ) and decreasing on ( e , + ∞ e , + ∞ e,+ooe,+\inftye,+∞ ), it follows that E ¯ k E ¯ k bar(E)_(k)\bar{E}_{k}E¯k is the largest for k = 3 k = 3 k=3k=3k=3.
We have proved the following result.
Theorem 2. Among the methods (2) for k = N , k ≥ 2 k = N , k ≥ 2 k=N,k >= 2k=\mathbb{N}, k \geq 2k=N,k≥2, the method with highest efficiency index is given by:
(13) { F n = I − A D n D n + 1 = D n ( I + F n + F n 2 ) , n = 0 , 1 , … (13) F n = I − A D n D n + 1 = D n I + F n + F n 2 , n = 0 , 1 , … {:(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.(13){Fn=I−ADnDn+1=Dn(I+Fn+Fn2),n=0,1,…
with D 0 D 0 D_(0)D_{0}D0 verifying ‖ I − A D 0 ‖ ≤ q < 1 I − A D 0 ≤ q < 1 ||I-AD_(0)|| <= q < 1\left\|I-A D_{0}\right\| \leq q<1‖I−AD0‖≤q<1.
By (4), the above method may be written as
(14) F n = I − A D n D n + 1 = D n [ ( F n + I ) F n + I ] , n = 0 , 1 , … (14) F n = I − A D n D n + 1 = D n F n + I F n + I , n = 0 , 1 , … {:[(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*}(14)Fn=I−ADnDn+1=Dn[(Fn+I)Fn+I],n=0,1,…
In this case, (7) becomes
(15) ‖ F n + 1 ‖ ≤ ‖ F 0 ‖ 3 n + 1 , n = 0 , 1 , … (15) F n + 1 ≤ F 0 3 n + 1 , n = 0 , 1 , … {:(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*}(15)‖Fn+1‖≤‖F0‖3n+1,n=0,1,…
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 , … . (16) A − 1 − D n ≤ A − 1 F n ≤ A − 1 F 0 3 n , n = 0 , 1 , … . {:(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*}(16)‖A−1−Dn‖≤‖A−1‖‖Fn‖≤‖A−1‖‖F0‖3n,n=0,1,….
It can be easily seen that under (1), one has the inequality
(17) ‖ A − 1 ‖ ≤ ‖ D 0 ‖ 1 − ‖ F 0 ‖ (17) A − 1 ≤ D 0 1 − F 0 {:(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*}(17)‖A−1‖≤‖D0‖1−‖F0‖
whence
(18) ‖ A − 1 − D n ‖ ≤ ‖ D 0 ‖ ‖ F 0 ‖ 3 n 1 − ‖ F 0 ‖ , n = 0 , 1 , … (18) A − 1 − D n ≤ D 0 F 0 3 n 1 − F 0 , n = 0 , 1 , … {:(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*}(18)‖A−1−Dn‖≤‖D0‖‖F0‖3n1−‖F0‖,n=0,1,…
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 ‖ , n = 0 , 1 , … (19) A − 1 − D n ≤ D 0 F 0 k n 1 − F 0 , n = 0 , 1 , … {:(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*}(19)‖A−1−Dn‖≤‖D0‖‖F0‖kn1−‖F0‖,n=0,1,…

3. Error bounds in case of perturbed matrices

In practice, the elements of the matrix A A AAA are usually obtained as results of certain experiments, measurements, approximations etc. Therefore their values are altered by errors. Consequently we replace A A AAA by the approximation A ~ A ~ widetilde(A)\widetilde{A}A~. For a rigorous interpretation of the results, it is necessary to know an error bound ε > 0 ε > 0 epsi > 0\varepsilon>0ε>0 for which
(20) ‖ A − A ~ ‖ ≤ ε (20) ‖ A − A ~ ‖ ≤ ε {:(20)||A- widetilde(A)|| <= epsi:}\begin{equation*} \|A-\widetilde{A}\| \leq \varepsilon \tag{20} \end{equation*}(20)‖A−A~‖≤ε
Instead of sequence ( D n ) n ≥ 0 D n n ≥ 0 (D_(n))_(n >= 0)\left(D_{n}\right)_{n \geq 0}(Dn)n≥0 we consider ( D ~ n ) n ≥ 0 D ~ n n ≥ 0 ( widetilde(D)_(n))_(n >= 0)\left(\widetilde{D}_{n}\right)_{n \geq 0}(D~n)n≥0, generated by
(21) F ~ n = I − A ~ D ~ n D ~ n + 1 = D ~ n ( I + F ~ n + F ~ n 2 + ⋯ + F ~ n k − 1 ) , n = 0 , 1 , … (21) F ~ n = I − A ~ D ~ n D ~ n + 1 = D ~ n I + F ~ n + F ~ n 2 + ⋯ + F ~ n k − 1 , n = 0 , 1 , … {:[(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*}(21)F~n=I−A~D~nD~n+1=D~n(I+F~n+F~n2+⋯+F~nk−1),n=0,1,…
We assume that the matrices A ~ A ~ widetilde(A)\widetilde{A}A~ and D ~ 0 D ~ 0 widetilde(D)_(0)\widetilde{D}_{0}D~0 above obey
(22) ‖ I − A ~ D ~ 0 ‖ ≤ q ¯ < 1 (22) I − A ~ D ~ 0 ≤ q ¯ < 1 {:(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*}(22)‖I−A~D~0‖≤q¯<1
It follows that A ~ A ~ widetilde(A)\widetilde{A}A~ is invertible: ∃ A ~ − 1 ∃ A ~ − 1 EE widetilde(A)^(-1)\exists \widetilde{A}^{-1}∃A~−1 and by (18) we get
(23) ‖ A ~ − 1 − D ~ n ‖ ≤ ‖ D ~ 0 ‖ ‖ F ~ 0 ‖ k n 1 − ‖ F ~ 0 ‖ , n = 0 , 1 , … (23) A ~ − 1 − D ~ n ≤ D ~ 0 F ~ 0 k n 1 − F ~ 0 , n = 0 , 1 , … {:(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*}(23)‖A~−1−D~n‖≤‖D~0‖‖F~0‖kn1−‖F~0‖,n=0,1,…
We are interested in conditions which ensure that A ~ A ~ widetilde(A)\widetilde{A}A~ is nonsingular. We consider the identity
I − A ~ − 1 A = A ~ − 1 ( A ~ − A ) I − A ~ − 1 A = A ~ − 1 ( A ~ − A ) I- widetilde(A)^(-1)A= widetilde(A)^(-1)( widetilde(A)-A)I-\widetilde{A}^{-1} A=\widetilde{A}^{-1}(\widetilde{A}-A)I−A~−1A=A~−1(A~−A)
which implies
‖ I − A ~ − 1 A ‖ ≤ ‖ A ~ − 1 ‖ ε I − A ~ − 1 A ≤ A ~ − 1 ε ||I- widetilde(A)^(-1)A|| <= || widetilde(A)^(-1)||epsi\left\|I-\widetilde{A}^{-1} A\right\| \leq\left\|\widetilde{A}^{-1}\right\| \varepsilon‖I−A~−1A‖≤‖A~−1‖ε
whence, by (17) we get
(24) ‖ I − A ~ − 1 A ‖ ≤ ε ‖ D ~ 0 ‖ 1 − ‖ F ~ 0 ‖ (24) I − A ~ − 1 A ≤ ε D ~ 0 1 − F ~ 0 {:(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*}(24)‖I−A~−1A‖≤ε‖D~0‖1−‖F~0‖
This relation shows that for the existence of the inverse for A ~ − 1 A A ~ − 1 A widetilde(A)^(-1)A\widetilde{A}^{-1} AA~−1A it suffices that
(25) r = ε ‖ D ~ 0 ‖ 1 − ‖ F ~ 0 ‖ < 1 (25) r = ε D ~ 0 1 − F ~ 0 < 1 {:(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*}(25)r=ε‖D~0‖1−‖F~0‖<1
whence for ε ε epsi\varepsilonε we get the condition
(26) ε < 1 − ‖ F 0 ‖ ‖ D ~ 0 ‖ (26) ε < 1 − F 0 D ~ 0 {:(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*}(26)ε<1−‖F0‖‖D~0‖
Further,
A − 1 = ( A ~ − 1 A ) − 1 A ~ − 1 A − 1 = A ~ − 1 A − 1 A ~ − 1 A^(-1)=( widetilde(A)^(-1)A)^(-1) widetilde(A)^(-1)A^{-1}=\left(\widetilde{A}^{-1} A\right)^{-1} \widetilde{A}^{-1}A−1=(A~−1A)−1A~−1
whence
‖ A − 1 ‖ ≤ ‖ A ~ − 1 ‖ ‖ A ~ − 1 A ‖ ≤ ‖ D ~ 0 ‖ 1 − ‖ F ~ 0 ‖ − ε ‖ D ~ 0 ‖ A − 1 ≤ A ~ − 1 A ~ − 1 A ≤ D ~ 0 1 − F ~ 0 − ε D ~ 0 ||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\|}‖A−1‖≤‖A~−1‖‖A~−1A‖≤‖D~0‖1−‖F~0‖−ε‖D~0‖
and (26) attracts 1 − ‖ F ~ 0 ‖ − ε ‖ D ~ 0 ‖ > 0 1 − F ~ 0 − ε D ~ 0 > 0 1-|| widetilde(F)_(0)||-epsi|| widetilde(D)_(0)|| > 01-\left\|\widetilde{F}_{0}\right\|-\varepsilon\left\|\widetilde{D}_{0}\right\|>01−‖F~0‖−ε‖D~0‖>0.
The following inequality can be easily proved
(27) ‖ A − 1 − A ~ − 1 ‖ ≤ ‖ D ~ 0 ‖ 2 ε ( 1 − ‖ F ~ 0 ‖ ) ( 1 − ‖ F ~ 0 ‖ − ε ‖ D ~ 0 ‖ ) (27) A − 1 − A ~ − 1 ≤ D ~ 0 2 ε 1 − F ~ 0 1 − F ~ 0 − ε D ~ 0 {:(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*}(27)‖A−1−A~−1‖≤‖D~0‖2ε(1−‖F~0‖)(1−‖F~0‖−ε‖D~0‖)
which, together with (23) leads to
(28) ‖ A − 1 − D ~ n ‖ ≤ ‖ D ~ 0 ‖ 1 − ‖ F ~ 0 ‖ [ ‖ D ~ 0 ‖ ε 1 − ‖ F ~ 0 ‖ − ε ‖ D ~ 0 ‖ + ‖ F 0 ‖ t n ] , n = 0 , 1 , … (28) A − 1 − D ~ n ≤ D ~ 0 1 − F ~ 0 D ~ 0 ε 1 − F ~ 0 − ε D ~ 0 + F 0 t n , n = 0 , 1 , … {:(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*}(28)‖A−1−D~n‖≤‖D~0‖1−‖F~0‖[‖D~0‖ε1−‖F~0‖−ε‖D~0‖+‖F0‖tn],n=0,1,…
This inequality provides a priori evaluations for the error. If we want to stop the iterations at a certain step n ¯ n ¯ bar(n)\bar{n}n¯ such that ‖ F ~ n ¯ ‖ ≤ ε 1 , ε 1 > 0 F ~ n ¯ ≤ ε 1 , ε 1 > 0 || widetilde(F)_( bar(n))|| <= epsi_(1),epsi_(1) > 0\left\|\widetilde{F}_{\bar{n}}\right\| \leq \varepsilon_{1}, \varepsilon_{1}>0‖F~n¯‖≤ε1,ε1>0 given, then by (7) and (17) it follows
‖ A ~ − 1 − D ~ n ¯ ‖ ≤ ‖ D ~ 0 ‖ 1 − ‖ F ~ 0 ‖ ε 1 A ~ − 1 − D ~ n ¯ ≤ D ~ 0 1 − F ~ 0 ε 1 || 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}‖A~−1−D~n¯‖≤‖D~0‖1−‖F~0‖ε1
which, together with (27) lead to
‖ A − 1 − D ~ n ¯ ‖ ≤ ‖ D ~ 0 ‖ 1 − ‖ F ~ 0 ‖ [ ε 1 + ε ‖ D ~ 0 ‖ 1 − ‖ F ~ 0 ‖ − ε ‖ D ~ 0 ‖ ] A − 1 − D ~ n ¯ ≤ D ~ 0 1 − F ~ 0 ε 1 + ε D ~ 0 1 − F ~ 0 − ε D ~ 0 ||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]‖A−1−D~n¯‖≤‖D~0‖1−‖F~0‖[ε1+ε‖D~0‖1−‖F~0‖−ε‖D~0‖]
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
  1. 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.
2003

Related Posts