NASA Technical Memorandum 10236_1 ....

ICOMP-89-25

t =

Quotient-Difference Type Generalizations of the Power Method and

Their Analysis

(NASA-TM-IL02361 ) _UOT IFNT-D I_FERCNCE TYPE N90-iO6B5

GFN_,_ALIZAT!GNS Or- THF POWER METHOD AND

THEIR ANALYSIS (NASA) 18 p C_CL 12A

Uncl as

_3/o4 023393?

Avram Sidi

Institute for Computational Mechanics in Propulsion

Lewis Research Center _ _

Cleveland, Ohio

and Technion--lsrael Institute of Technology

Haifa, Israel

and

William F. Ford

Lewis Research Center

Cleveland, Ohio

September 1989

QUOTIENT-DIFFERENCE TYPE GENERALIZATIONS OF THE

POWER METHOD AND THEIR ANALYSIS

Avram Sidi

Institute for Computational Mechanics in Propulsion*

Lewis Research Center

Cleveland, Ohio 44135 U.S.A.

and Technion--Israel Institute of Technology

Computer Science Department

Haifa 32000, Israel

and

William F. Ford

National Aeronautics and Space Administration

Lewis Research Center

Cleveland, Ohio 44135 U.S.A.

ABSTRACT

The recursion relations that were proposed in [2] for implementing vector extrapolation

methods are used for devising generalizations of the power method for linear operators.

These generalizations are shown to produce approximations to largest eigenvalues of a linear

operator under certain conditions. They are similar in form to the quotient-difference algorithrn and share similar convergence properties with the latter. These convergence properties

resemble also those obtained for the basic LR and QR algorithms. Finally, it is shown that the

convergence rate produced by one of these generalizations is twice as fast for normal operators as it is for non-normal operators.

*Work funded under Space Act Agreement C99066G.
-2-

1. INTRODUCTION

Let B be a normed linear space over the field of complex numbers, and denote the norm associated with B by II • II . In case B is also an inner product space, we adopt the following convention for

the homogeniety property of the inner product: for y ,z _ B and o_,[5complex numbers, the inner product (.,-) satisfies (cry ,13z)= _13(y ,z). The norm in this case is the one induced by the inner product,

i.e.,ifx e B, II x 11 ='/(x,x).

Let xi, i = 0,1 ..... be a sequence in B. We shall assume that

eo /'/1.

X m -- __._Vi_. i as m _ ,,0. (1.1)

i=1

Here v 1,v2..... are linearly independent vectors in B. Xi are distinct scalars ordered such that

I_ql >_ I_1 _ I_l >---, (1.2)

and satisfy

_.i # 0, i = 1,2,...; 3.i # 7tj if i # j. (1.3)

Also there can be only a finite number of Xi's having the same modulus. The meaning of (1.1) is that

for any positive integer N there exist a positive constant K and a positive integer mo that depend only

on N, such that for every m > too,

N-I

II x,.,, - _vi3ff II _<KI_.NI _ . (1.4)

i=1

Sequences of the form described above arise naturally, for example, in the matrix iterative proceSS

xj+l = Axj, j = 0,1 ..... (1.5)

in which Xo is an arbitrary column vector, and A is a square matrix whose nonzero eigenvalues have

only associated eigenvectors and no principal vectors. In this case X1,7_..... are some or all of the

nonzero eigenvalues of A, depending on the spectral decomposition of Xo, and v l,v 2..... are proportional to its corresponding eigenvectors. Also the infinite sum iviX_' in (1.1) is now finite, and the

i=I

asymptotic relation there becomes an equality.
-3-

In thenextsectionwepresenthreerecursivetechniques,whichwedesignatetheqd-MMPE,

qd-TEA,andqd-MPEalgorithms,thatarebasedsolelyonthevectorsequenceXo,Xl,X2 ..... and that

can be used for obtaining approximations to _.l,L2,Tq ..... in this order. These techniques generalize

the well known power method and resemble the quotient-difference (qd) algorithm. In Section 3 we

analyze the convergence properties of these techniques and show that they indeed behave like the qd

algorithm. We recall that the qd algorithm is used in approximating the poles of meromorphic functions in general, and the zeros of polynomials in particular. For detailed descriptions of the qd algorithm, see, for example, Hertrici [3, Chap. 7] and Householder [4, Chap. 3]. The convergence rates

derived for the methods of the present work are also very similar to those derived for the basic LR

and QR algorithms, see, for example, Parlett [5].

In Section 4 we will analyze one of the recursive techniques of Section 2, namely the qd-MPE

algorithm, in conjunction with vector sequences xm, m = 0,1 ..... that are generated by iterating with a

normal operator, and we will show that the rate of convergence for this case is twice that obtained for

an arbitrary non-normal operator that has the same spectrum.

Finally, we mention that the recursive techniques developed in this work are based on the recursive algorithms that were developed by Ford and Sidi [2] for implementing some vector extrapolation

method, such as the modified minimal polynomial extrapolation (MMPE), the topological epsilon

algorithm (TEA), and the minimal polynomial extrapolation (MPE), from which their names are

derived. The methods of proof relating to the convergence of these techniques are similar to those that

were used in Sidi, Ford, and Smith [8] and in Sidi [6] in the analysis of the above mentioned vector

extrapolation methods, and in Sidi [7] in the analysis of some other recent extensions of the power

method as they are applied to normal operators. We also mention that the scalar and vector epsilon

algorithms of Wynn [9,10] can also be used as generalizations of the power method and produce

results similar to the ones given in Section 3 of the present work. This has been shown by Brezinski

[1].
-4-

2. DEVELOPMENT OF THE ALGORITHMS

In this section we follow very closely the developments and notation of [2].

In all three methods that we develop in this section we assume that the vector sequence

Xo,Xl,x2 ..... is given. We also assume that a sequence of scalar quantifies g_, m,n >_0, is given.

These quantities are determined in different forms from the vectors xi. Their exact definition will be

given later in this section. In addition, we denote by b an arbitrary sequence bo,b l,b2 ..... Thus I.tj

stands for the sequence P-d,l.t[,g_.....

We def'me Gff m to be the determinant

G_.'_ =

l.t£ 0-,,%1 "" _t_÷k-1

_t£+t tt£._t • " " ,,,.+I _n+k-I

• "" P'n+k-I

(2.1)

and f; re(b) to be the determinant

We also define

Finally, we let

Note that by (2.3) and (2.4)

fff_(b) =

bn b,,+l " "" bn+k

tt_+k-t tt_+_k-x ; ,,,+k-I • " " l'_n +k I

(2.2)

G_)"_= 1 and f_)"(b)= b,,. (2.3)

T_"(b )= ff"(b )/G; +I¢'. (2.4)

T_"(b )=b,,. (2.5)
-5-

2.1 The qd-MMPE Algorithm

Let Q 1,Q2 ..... be a sequence of linearly independent bounded linear functionals on B, and let

ixnm = Qm+l(x.), m,n >-O. (2.6)

We recall that in case B is a complete inner product space each Qj has a unique representer q) in B in

the sense that Q) (z) = (qj,z) for all z in B.

As is shown in [2, Theorem 2.1], the quantities T_,(b) =-T:,'°(b) satisfy the 3-term recursion relation

where

n .4n'T'n+l r_(b ) = T__ 1(b ) - _'k" k-1 (b ), (2.7)

dff = T__ 1 (l_k-1)/r;._+: (_k-1) , (2.8)

Note that d_ = I.t,/l_,+l o o from (2.5) and (2.8). Note also that T_(_/) = 0 for 0 <j < k-1.

As will be shown in Section 3, for the vector sequences Xo,Xl,X 2..... described in the beginning of Section 1, 1/d_ --) 7_k as n --) 0. under certain conditions. Thus the developments above provide us with a technique that can produce approximations to _._,_ ..... in this order. This technique

is summarized below:

qd-MMPE Algorithm (2.9)

Given the sequence xo,xl,x2 ..... compute I.t_m, m,n >-0, by (2.6), and set T_(I z)) =lx_/. For

k = 1,2 ..... use (2.8) to compute rift, and then use (2.7) to compute Tff(lff), j >-k.

We note that dff is constructed from the k+l vectors x, ,Xn+l.... ,xn+k.

Finally, we observe that 1/d_ = i.tn+l/i.t,, o o = Q l(x,,+l)/Ql(x,,), which is exactly the approximation

provided by the power method for _1, the largest eigenvalue in modulus of a linear operator, provided

this eigenvalue is simple, and satisfies 17Vl I > I_ I. In this sense the qd-MMPE algorithm generalizes the power method.
-6-

2.2 The qd-TEA Algorithm

Let Q be a bounded linear functional on B, and let

g_=Q(xm+,), m,n >-0. (2.10)

Again, in case B is a complete inner product space Q has a unique representer q in B in the sense that

Q (z) = (q ,z) for all z in B. The rest is exactly as in the qd-MMPE algorithm. We only have to observe

that d_ now is determined by the 2k vectors x n ,x,,+ l.... ,x,,+2k-l. We also observe that for k = 1 the qdTEA and qd-MMPE algorithms are the same when Q = Q 1- Consequendy, as with the qd-MMPE

algorithm, also with the qd-TEA algorithm the power method is obtained for k=l. Hence the qd-TEA

algorithm also generalizes the power method.

2.3 The qd-MPE Algorithm

The scalar quantities IX_ are now defined by

g_m=(xm,xn), m,n >_0. (2.11)

As is shown in [2, Theorem 3.1], the quantities T_(b)=-T_'_(b) and 7_(b)- T_V'-X(b) satisfy

the coupled recursion relations

T;(b ) = r;_l (b ) -d;ff_+ll (b ), n >_0,

where

f;(b)=rL_O)-d;7:L+?(b), n > 1,

a_ = rL1 (l_"+k-b/fL+: (l:+k-b,n >_O,

(2.12)

(2.13)

d,_ = Tff_l(I.t"-I)/7:_+_ (IX"-1), n >- 1.

In fact, there exists a very interesting 4-term (lozange) recursion relation among T_+I (b), T_(b),

T_+l(b), and T_._*:(b), see [2]. Note that d_ = i_/Ix_'+l, n >_0, and d'_ = g,_-l/g2+:, n > 1, from (2.5)

and (2.13). Note also that T_(gJ) = 0 for n < j <-n+k-1, and 7_(lx j) = 0 for n-1 -<j -<n +k-2.

As will be shown in Section 3, for the vector sequences x0,xvx2 ..... described in the beginrting of Section I, 1/dF, ---) Xk and 1/d_' _ Xk as n ---)** under certain conditions. Thus, the developments above provide us with yet another technique that can produce approximations to Xl,_ ..... in
-7-

thisorder.Thistechniqueissummarizedbelow:

qd-MPE Algorithm (2.14)

Given the sequence x0,xl,x z..... compute _', m,n>O, by (2.11), and set

T_(_t/) = _t/ = ¢_(I.t/). For k = 1,2 ..... use (2.13) to compute d; and d_, and then use (2.12)

to compute T_,(lxJ), j < n-l, j >_n+k, and 7:_(_t/), j < n-2, j >-n+k-1.

Observe that d_ and d_' are constructed from the k+2 vectors xn_l,xn ,xn+ I.... ,Xn+k only.

Finally, we observe that 1/d_ = _t_+l/kt_ _ = (xn ,xn+l)/(x_ ,xn), which is exactly the Rayleigh quotient that provides an approximation to _.l, the largest eigenvalue in modulus of a linear operator, provided this eigenvalue is simple, and satisfies I_.11 > IL21 . In this sense the qd-MPE algorithm generalizes the power method (the Rayleigh quotient). It is known that in case the vector sequence

x0,xl,x2 ..... is generated by a normal operator, the Rayleigh quotient converges to _-t twice as

quickly as it does for a non-normal operator.

So far we have shown that the three algorithms above generalize the power method for a linear

operator. We would now like to explain why they are of the quotient-difference type. First, the algorithms are somewhat similar in form to the quotient-difference method. Second, as is shown in the

next section (see (3.20) and (3.24)), the d_ are all expressed in terms of four determinants the way the

quantities in the quotient-difference method are. Furthermore, again as will be shown in the next section, these determinants have asymptotic expansions very similar in form to those obtained for the

determinants involved in the quotient-difference method. We note in passing that the determinants that

appear in the quotient-difference algorithm are Hankel determinants. The same holds true for the qdTEA algorithm as wiU be clear in the next section, although the indices of these determinants are different in the two methods.
-8-

3. CONVERGENCE ANALYSIS OF THE ALGORITHMS

We now state the main convergence results for the qd-type algorithms that were devised in the

previous section.

The following assumption is common to all three methods:

I_.k-t I > I_.k I > I_.k+l I for some integer k >_.1; 7_o - **. (3.1)

Let us also define

_k = max ' _.k , k _ 1. (3.2)

Thus, ek < 1.

Theorem 3.1: In the qd-MMPE algorithm denote

Sj

Ql(Vl) ... Ql(Vj)

Qj(v ) ... Qj(v:)

, y = 1,2 ..... (3.3)

Provided (3.1) holds, and

we have

Theorem 3.2:

Sk-x*O and St,_:O, (3.4)

I/dff = _k + 0 (eft) as n --_ "*. (3.5)

In the qd-TEA algorithm provided (3.1) holds and

(3.5) is satisfied.

k

I'Ia(vi)_O, (3.6)

i=l

Theorem 3.3: In the qd-MPE algorithm provided (3.1) holds, (3.5) is satisfied. (3.5) is satisfied also

when dff is replaced by rift.

Note: In relation to Theorem 3.3 we realize that if the sequence x0,xx,x2 ..... is generated by the

matrix A in the way xj+ 1 = Axj, j = 0,1 ..... x o being arbitrary, then the qd'MPE algorithm performs
-9-

asymptoticallylike theqd-MMPEandqd-TEAalgorithms,althoughit doesnot requireadditional

conditionslike (3.4)and(3.6).

In theproofsof Theorems3.1-3.3weshallmakeuseof thefollowingresults,which areof

interestinthemselves.

Lemma3.4: Let ol,o2..... and_1,42..... betwosequencesof nonzeroscalars,suchthattheoi

aredistinct,and

1411 > 1421 > .-. (3.7)

Assume, furthermore, that there can be only a finite number of 4i's having the same modulus. Consider the determinant

in which

•

zj_ being some scalars. Define

(3.8)

u_.q)- _zja, oq;; as n _**, (3.9)

j--I

Zj,d,....d, =

z.i..t zj,a • o . _jrtT

Then _, for n .-o _, has the asymptotic expansion

v;- E z_,j,....j,v(oj,,oj, ..... %;) -"

l<jt<j2<'"<j,

where V(al ..... a,.) is the Vandermonde determinant defined by

(3.1o)

(3.11)
- 10-

V(a,.....a,) =

1 a r "-- arr-1

(When - is replaced by = in (3.9), - is replaced by = in (3.11) too.) If, in addition,

I_, I> I_r+ll and Zl_,...,r _0,

then

(3.12)

(3.13)

_/rn ----Zl,2,...,rV(ffI,G2 ..... fir) _ I + 0 asn--_**. (3.14)

Lemma 3.4can be obtainedfrom [7,Lemmas 2.2 and 2.3],whose techniqueisa generalization

of that employed in [8, Theorem 3.2].

Lemma 3.5: Let _1,_2 ..... be a sequence of nonzero scalars exactly as described in Lemma 3.4.

Consider the determinant V_ as given in (3.8), but with

2., zij t,i _j as n --->*%

i--1 j=l

(3.15)

zij being some scalars. Define

7"i, jt 7"i,ja "'"

Then V_, for n --->*%has the asymptotic expansion

zi,j,

(3.16)

eD

7.6.--._. v:- E E -j,,.._,

l_'t <i2<'"</_ l<jl<j2<'"<j,

..... ..... ;j,) " .

(3.17)

(When - is replaced by = in (3.15), - is replaced by = in (3.17) too.) If, in addition,
- I1-

then

• n zl,...,r[V(_l, ,_r)[2 _r ---- 1,...,r "" "

as/I _.) oo.

Lemma 3.5 can be proved exactly as in [6, Lemma 3.2 and Theorem 3.1].

Proof of Theorem 3.1:

T_(b ) -- T;'°(b ), we obtain

Combining (2.8) with (2.4), (2.2), and (2.1),

_ ; ,oG;_+?,o

d;= G; +I'°"-'k:-"+l'O-I "

(3.18)

(3.19)

and recalling that

(3.20)

Now by (2.6) and (1.1) we have

n

IxT- ZQm+l(vj)Lj as n --->**. (3.21)

j=l

Substituting (3.21) in the determinant expression for G;'°, we see that Gff '° is simply V;' of Lemma

3.4 with u(_) = _t,,+q, p-l thus zj#, =Qp(vj), _j =Lj, and aj =_j. Furthermore, S i in (3.3) is Zl_,...d in

Lemma 3.4. Therefore, Lemma 3.4 applies, and we have

G_'o=sk V(_.l ..... _.D _.] 1+0 _ ash _.

Treating m,,+l '-,k 'o,'-,k-i _n+l,O , and _n+2,o ,-,k-i similarly, and combining the results in (3.20), we obtain (3.5).

(3.22)

[]

Proof of Theorem 3.2: We observe that by (2.10) and (2.1)

I.t_"- Z[Q(vi)_.j"]_,7 as n _ **. (3.23)

j--I

The rest of the proof is exactly the same as that of Theorem 3.1, with Q_+l(vi) in the latter being

replaced by Q(vi)_.], now. On account of this, Zl,...,i now becomes [ f'[=lQ(vi)] V (L 1..... _./). We

leave out the rest of the details. []

Here we note that Gff '° for the qd-TEA algorithm is a Hankel determinant. Thus the qd-TEA

algorithm resembles very strongly the qd algorithm. Furthermore, when the sequence Xo,XpX2 .....
- 12-

is oneof scalars,thentheqd-TEAalgorithmcan still be employed by picking the functional Q to be

the identity operator, in which case Ix_ = x,,,+,,. Thus for scalar sequences satisfying all the conditions

mentioned in Section 1 of this work the qd-TEA algorithm provides another form of the qd algorithm.

Proof of Theorem 3.3: Combining (2.13) with (2.4), (2.2), and (2.1), and recalling that

T_(b ) =__T_ :(b ) and 7?_(b ) =_T_ "_-1(b ), we obtain

,,-,n ,n ,,-, n+201

l,,.,Irk t-.rk_ 1

Gff+l.n Vk-lr2-n+lgt '

Gff,n-I _Uk_ln+2,_

Gff +lm-I _-_kt'2- nl,n_l + "

(3.24)

Substituting (2.11) in (2.1), and comparing with (3.8), we see that G_,"'s=_ with

u_.,,q)=. O.,,+q ,+_+,-1 = (xn+_+p_l,x,,+q). Invoking now (1.1), we see that U_"q) is of the form (3.15), with

zl/ = (vi,vj)[: and _i = _i. Also Z _:.':'_ in Lemma 3.5 now becomes

.... li=l J

(V 1,V 1)

(V k ,111)

• -- (vl,vk)

•"" (vk,vD

(3.25)

Since the vectors v 1,v2 ..... in (1.1) are assumed to be linearly independent, the Gram determinant

UL...j, of the vectors v 1..... vk is positive. Thus Zt, S.'_ 0. Consequently, Lemma 3.5 applies, and we

obtain

G?,,"+'= Z._ UI,...._ IV(Z._ ..... _.k)l 2 ._-_q

Invoking (3.26) in (3.24), we obtain the required result.

2n

[]

as n --->**. (3.26)
- 13-

4. THE qd-MPE ALGORITHM FOR NORMAL OPERATORS

As we have shown in Theorem 3.3, the convergence rate of the qd-MPE algorithm is the same as

those of the qd-MMPE and qd-TEA algorithms, in general. When the vectors v l,v2 ..... in the expansion (1.1) are orthogonal with respect to the inner product (','), however, the convergence rate of the

qd-MPE method becomes twice that given in Theorem 3.3, as will be shown shortly in Theorem 4.1.

When the vector sequence Xo,Xl ..... is generated by the matrix iterative process xj÷ t =Axj,

j = 0,1 ..... with Xo arbitrary, then, as we mentioned in the introduction to this work, x_ satisfies (1.1),

with Xi there being nonzero eigenvalues of A that possess only eigenvectors and no principal vectors,

and vi there being proportional to the corresponding eigenvectors. Now when A is a normal operator

it has only eigenvectors, and these form an orthogonal set with respect to the inner product. We recall

that hermitian and antiherrnitian operators are normal. Thus Theorem 4.1 below applies to vector

sequences generated by matrix iterative processes with normal matrices.

Theorem 4.1:

satisfy

we have

In the qd-MPE algorithm, provided (3.1) holds and the vectors vl,v2 ..... in (1.1)

(vz,vj) = zj 5_/, (thus zj > 0), (4.1)

lld_ = _k + O (gk2n) as n --_ **. (4.2)

When _,j > O, j = 1,2 ..... (4.2) can be refined considerably. (In this case the condition in (3.1) is

automatically satisfied.) If _,k+l/Z.k > _,_/_k-l, then

lld_ - _,k--_k as n ---) 00,some 13k> 0, (4.3)

i.e., the sequence {1/d_}_=o converges to _,k monotonically from below, and if Xk+t/_,k < Xk/%k-1, then

1/d_ - _,k+ Yk as n --->**,some Yk> 0, (4.4)

i.e., the sequence {1/dff}_'=o converges to 7_k monotonically from above. _k and )'k are given in the

proof below.
- 14-

All theresultsaboveholdwhend,_ is replaced by d;, though with different _k and )'k.

Proof: We saw in the proof of Theorem 3.3 that Gff'_+s= _ with ue(_) --(x_, ÷s÷p-l ,x,,+e). Invoking

now (1.1) and (4.1), we see that up(,"q) is of the form (3.9), zj,p = :_hj , ¢_j -- and = I'.

Also Zy,....j, in Lemma 3.4 becomes

zj,....j,= zj, v:j, .....

Substituting all this in (3.11), we obtain for n --) ,,_

(4.5)

Consequently, all the conditions of Lemma 3.4 are satisfied, and

Invoking (4.7) in (3.24), (4.2) follows.

k

ash --->,,,. (4.7)

Now when the _/'s are all real, from (4.6) and (4.1), we see that Gff a'÷s,s = 0,+%:1:4..... are all

real and positive. When the _.j's are all positive Gff "_are positive for all s. In case all _../'s are posifive, (i.2) and (3.1) become

_.I> _ >'">_-k-I> _.k> Z.k+1>'", (4.8)

so that (3.1) is automatically satisfied now. The two most dominant terms in the summation in (4.6)

are those with the indices Jl ..... Jk = 1,2 ..... k and Jl .....Jtc = 1,2 ..... k-l,k+l. Thus

Gff:+s= zj IV(_. 1..... _k)l 2 1 +co k

where

_'t +$

as n --->**, (4.9)

gk+l

(_k ----

_k

v(_.1.....X_,-1,XJ,+O"

V(_l ..... _.___,_._,)

2

>0. (4.10)

Consequently, for n --->_*,
- 15-

1 - L_'_-,J

- L_-,J

1---C-, j L x,,:j

restof,,,e p,-oofcooow omp, ete , eas"y. Weo y n, ,',at ok[a-

= -- in (4.4). []

(4.11)

in (4.3), and
- 16-

REFERENCES

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

C. Brezinski, Computation of the eigenelements of a matrix by the e-algorithm, Lin. Alg.

Appl., 11 (1975), pp. 7-20.

W.F. Ford and A. Sidi, Recursive algorithms for vector extrapolation methods, Appl. Numer.

Math., 4 (1988), pp. 477-489.

P. Henrici, Applied and Computational Complex Analysis, Vol. 1, John Wiley & Sons, New

York, 1974.

A.S. Householder, The Numerical Treatment of a Single Nonlinear Equation, McGraw-Hill,

New York, 1970.

B.N. Parlett, The LU and QR algorithms, in Mathematical Methods for Digital Computers,

(A. Ralston and H.S. Wilf, eds.), Vol. II, John Wiley & Sons, New York, 1967, pp. 116-130.

A. Sidi, Convergence and stability properties of minimal polynomial and reduced rank extrapolation algorithms, SIAMJ. Numer. Anal., 23 (1986), pp. 197-209.

A. Sidi, On extensions of the power method for normal operators, Lin. Alg. Appl.,

120 (1989), pp. 207-224.

A. Sidi, W.F. Ford, and D.A. Smith, Acceleration of convergence of vector sequences, SIAM

J. Numer. Anal., 23 (1986), pp. 178-196.

P. Wynn, On a device for computing the em(S,) transformation, MTAC, 10 (1956), pp. 91-96.

P. Wynn, Acceleration techniques for iterated vector and matrix problems, Math. Comp., 16

(1962), pp. 301-322.
NationarAeronautics and

SpaceAdministration

1+ Report No. NASA TM-102361

ICOMP-89-25

Report Documentation Page

2. Government Accession No. 3. Recipient's Catalog No.

4. Title and Subtitle

Quotient-Difference Type Generalizations of the

Power Method and Their Analysis

7. Author(s)

Avram Sidi and William F. Ford

9. Performing Organization Name and Address

National Aeronautics and Space Administration

Lewis Research Center

Cleveland, Ohio 44135-3191

12. Sponsoring Agency Name and Address

National Aeronautics and Space Administration

Washington, D.C. 20546-0001

5. Report Date

September 1989

6. Performing Organization Code

8. Performing Organization Report No.

E-5077

10. Work Unit No.

505-62-21

11. Contract or Grant No.

13. Type of Report and Period Covered

Technical Memorandum

14. Sponsoring Agency Code

15. Supplementary Notes

Avram Sidi, Institute for Computational Mechanics in Propulsion, Lewis Research Center (work funded under

Space Act Agreement C99066G) and Technion--Israel Institute of Technology, Computer Science Department,

Haifa 32000, Israel; William F. Ford, NASA Lewis Research Center. Space Act Monitor: Louis A. Povinelli.

16. Abstract

The recursion relations that were proposed in "Recursive Algorithms for Vector Extrapolation Methods" by

W.F. Ford and A. Sidi (Appl. Numer. Math, 4 (1988), pp. 477-489) for implementing vector extrapolation

methods are used for devising generalizations of the power method for linear operators. These generalizations are

shown to produce approximations to largest eigenvalues of a linear operator under certain conditions. They are

similar in form to the quotient-difference algorithm and share similar convergence properties with the latter. These

convergence properties resemble also those obtained for the basic LR and QR algorithms. Finally, it is shown

that the convergence rate produced by one of these generalizations is twice as fast for normal operators as it is for

nonnormal operators.

17. Key Words (Suggested by Author(s))

Eigenvalue problem

Power method

Extrapolation methods

Quotient-difference algorithm

19. Security Classif. (of this report)

Unclassified

18. Distribution Statement

Unclassified- Unlimited

Subject Category 64

20. Security Classif. (of this page)

Unclassified

21. No of pages

18

NASAFORM1626OCT86 *For sale by the National Technical Information Service, Springfield, Virginia 22161

22. Price"

A03