381 ~~ .--

L. ELSNER: Uber EigenwerteinschlieDungen rnit Hilfe von Gersc hgorin-Kreisen - _____ -~

Uber Eigenwerteinschliehngen rnit Hilfe von G e r s c h g or i n-Kreisen

Von L. ELSNER

Meinem verehrten Lehrer Professor I)r. Or. 11. c. L. COLLATZ Zuni 60. Gebuststag gewidnict

Die Vereinigung gewisser Gerschgorin-Kreise einer Matrix A sei durch einen Kreis vom Radius r und Nittel- punkt y von den Cbrigen Gerschgorin-Kreisen getrennt. M e d l e y und V a r g a haben das minimale r, das bei festem y durch Diagonaltransfornaationen von A erreicht werden kann, churakterisiert. Es wird gezeigt, da# dieses Ergebnis mit den in einer fruheren Arbeit des Autors benutzten Methoden leicht bewiesen werden kann. AuJerdem wird der maximale Radius charakterisiert, pruktisch verwendbare Abschatzungen angegeben und gezeigt, daJ A und die transponierte Matrix A T die gleichen optimalen Radien haben.

Let the union of some Gerschgorin-disks of a matrix A be separated from the other disks by a circle of radius r and center y . M e d l e y and V a r g a have characterized the minimal r, which can be achieved by diagonal transfor- mations of A and fixed y . I t i s shown that this result can easily be proved with methods used in an earlier puper of the author. I n addition, the maximal radius is characterized, easily computable bounds are given and it is shown, that A and tLe transposed matrix A T have the same optimal radii.

IIpmumaeTcB YTO o6'6emmeHrne HeKoTopMx oKpyfitiocTeii e p IU r o p B n a MaTpmbi A omeneHo OIEPYX- HOCTHO c panaycoMr II uempoM y OT OCTaJIbHbIX oIipyxwocTelti repmropma. Manneh B B a p r a oxa- y a ~ ~ e p ~ 3 o s a n n ManaMamnoe 3na~enae r , AocTmraeMoe n p ~ nocTonHHoM y ~ Y T ~ M maroHanbHoro r1peo6paaonann~. lTo~a3ano YTO TOT pe3ynbTaT MomeT 6 ~ ~ b nerKo HoKo3an MeTozoM, KoTopbm I I O J I ~ ~ O B ~ J I C R amop B OHHOB 113 rrpenmyrrlHx pa6o~. ICpoMe 3 ~ o r o o x a p a ~ ~ e p ~ 3 o s a a MaKcmtanm&i pamyc, npmeqenLI npawmuecwi npaMenMMbIe oueIiirn EI I I O I F ~ ~ ~ H O , ~ I T O A M TpaHcnoIInpoearriiari~ MaTpHlKa AT 06JIaRaIOT OlIHHaKOBbIMW OIITHMa:lLIIbIMI4 paAByCaMM.

1.

Es sei A eine komplexe n x n-Matrix, 2: 2 0 ein Vektor mit positiven Komponenten, X = diag (xi) = (xi dik) und

J l ( X ) = ( z E c: / z - azzl 2 A4t(4} (2) (i = 1, 2, . . . , m) die ~BRscHGoRIN-Radien bzw. GERscHcoRIN-Kreise von X - l A x. sei N = (1 , 2, . . . , n}. Dann gilt bekanntlich fur alle Teilmengen cr, z< N mit cr uz = N , crn t = 0 : 1st p = die Amzuhl der Elernemte von (T (0 5 p 5 n) urtd ist

/asz - a,,/ - A&) - A,(x) 2 0 v i E 0, v j E z (3) so enthalt IJ r , (x) smhdestens p und U r f ( x ) mindestens m - p Eigenwerte vom A (wenn man die Eigenwerte

gemaS ihrer algebraischen Vielfachheit ziihlt). Siehe etwa [4]. GERscHcoRIN-Kreise bestimmen EinschlieSungsmengen bzw. AusschlieSungsmengen fur die Eigenwerte

von A , die man durch passende Wahl von X zu optimieren sucht. Wahlt man etwa als EinschlieSungsmenge den kleinsten Kreis um 0, der alle I',(x) enthalt, so ergibt

sioli die Aufgabc, dcssen Radius

i € U jcz

r ( ~ ) =; Max ( / a r z / + A&)) -= Max ( ]A/ .d / .cs i i

zu minimieren. Dabei ist lA/ = ( / a t r ] ) . Der Quotienten-Satz von COLLATZ ([l], [7]) zeigt, daD inf r(x) gleich dem Spektralradins @ ( / A / ) von /A1 ist.

Gibt es ein x > 0, so da13 0 B U ITz(x) ist, so kann man als AussclilieWungsrncngc dcn groSten Krcis

um 0 betrachten, der beine inneren l'unkte von U l 'z( .c) erithalt. Hier suchen wir also i € N

i € N

r(.c) = riiiii ( / a z s / - A,(c)) i

zu maximieren. Es ergibt sich unter Benutzung der Theorie der M-Matrizen

sup T ( X ) = (&i-1))-1 , wobei 2 - ( ( 2 d s k - - l ) / u t k / ) ib t .

Analog lassen sich die Real- und Imaginarteile der Eigenwerte abschatzen. Der Fall, daS als Einschliehngsmenge ein isolierter bzw. die Vereinigung mehrerer isolierter GBRSCH-

uoRIN-Kreise rnit gleichem Mittelpunkt gewiihlt wird, wurde von VARGA [6] und TODD [5] bzw. dem Autor [ Z ] behandelt.

L. ELYNER: uber Eigenwerteinschliehngen mit Hilfe von Gerschgorin-Kreisen ______

382 _______--__

Eine allgemeinere Situation wurde in einer wenig spiiter erschienenen Arbeit 131 von MEDLEY und VAXGA betrachtet: Es gebe ein x > 0 und einen Kreis Ky,r mit Mittelpunkt 7 und Radius r , so daS

ist. Das ist eine starkere Forderung als (3). K,,r wird als Einschliehngsmenge angesehen. Bei festem y wird r uber alle x mit der Nebenbedingung (4) minimiert. Es stellt sich heraus, daR die dortigen Ergebnisse auch mit den in [ 2 ] benutzten SchluRweisen zu gewinnen sind. Es gelingt gleichzeitig, auch das maximale r zu charakterisieren, also den eigenwertfreien Kreisring moglichst groR zu machen. AuRerdem wird angedeutet, wie diese Charakterisierung rnit den Hilfsmitteln in [3] zu gewinnen ist. Gewisse hinreichende Trennbarkeits- bedingungen in [ 2 ] , die auch numerisch brauchbar sind, lassen sich auf diesen Fall ubertragen.

SchlielJlich zeigen wir, daR die optimalen Schranken fur A und AT ubereinstimmen.

2.

Wir stellen zunachst kurz einige Hilfsmittel zusammen. 1st x = ( x t ) ein Vektor, so bedeutet x > 0 (ZO), dalJ alle xt > 0 (2 0) sind. Eine analoge Schreibweise wird fur Matrizen verwendet.

S a t z 1 : Ist C 2 0, D = diag (d,) eine Diagonalmatrix und B = D - C, so sirul, aqiuvalent B ist M-Matrix, d. h. B-1 existiert und B-l 2 0.

d, > 0 f u r alle i E N , e(D-l C) < 1. 3 v > 0 nait B v > 0.

3 v 2 0 init B v 2 0, B v =b 0.

(1) (11)

(111) Ist C irreduzibel, so gilt die xusatxliche Aquivalenz (IV) Beweis siehe [7] und 121.

Fur H = (hzk) rnit hLk 2 0 fur i + k sei

M ( H ) = { d E Rn: D - H ist M-Matrix, D = diag (d,)} --

M ( H ) ist offen. Sei a M ( H ) der Rand und M ( H ) = N ( H ) u a M ( H ) die AbschlieRung von J ! ( H ) .

S a t z 2 : (121) H aei irreduxibel. Uann ist aquivalent a E aM(I1 ) . 3 v > 0 rnit ( H u ) ~ = cli vi fur alle i E N .

(1) (11) v ist bis auf einen positiven B'aktor eindeutig.

__ ~ _ _ ~- S a t z 3 : M ( H ) und M ( H ) sind konvex. Piir irreduzibles H ist M ( H ) strikt konvex. Beweis: Fur 0 < a < 1 und E , 7 > 0 gilt Ea +-a 5 a E + (1 - a) 11. Dabei liegt Gleichheit genan fur 6 = 7 vor.

Seien D = diag ( d , ) und fi = diag (2,) in M(H). Nach Satz 1, I11 und Satz 2, I1 existieren x, y > 0 mit H x 5 6 x , H y 5 D y. Mit u = (ud) und ui = xt yt-" ist dann

d. h. JI u 5 (a 5 + (1 - a) D) u oder a b + (1 - a) D E M m ) . Ebenso folgt die Konvexitat von M ( H ) . Nun zeigen wir, daD M(H) fur irreduzibles H strikt konvex ist, d. h. daD fur D, 5 E M(H), D * b und 0 < a < 1 stets a b + (1 - a ) D E M ( H ) ist. Wir nehmen das Gegenteil an: a b + (1 - a ) D E a;ZI(H). Dann steht wegen Satz 1, TV in ( 5 ) stets das Gleichheitszeichen. Daher ist 6 x = H x, D y = H y und wegen D =k 8 sind x und y linear nnabhangig. Nithin ist ?G = { i : 26 = yi} + A'. 0. H. d . A. kijnneii wir aiich x1 = yl, also n =k 0 annehmen. Dann ist fur i E n, k a n sicher xk/xj * yk/yi , also U J U , < a x k / x , -+- (1 -a)yk/y,. Bus der Gleichung in ( 5 ) folgt h L k = 0 fur i E n, k 6 n. Das ist ein Widerspruch zur Irreduzibilitat von 11.

Es sei 1 5 p = Ig1 5 n - 1 und P die Menge der Vektoren x > 0, fur die bei festem y und passendem r = r ( x ) die Aussage (4) erfullt ist, fur die es also ein r > 0 gibt mit

ladi - y / 1- A,(x) r laf, - yI - A,(x) V i E c , V j E z . (6)

Fur x E P gilt offenbar

U'ir versuchen

A, = inf { ~ ( x ) : x E P} iM, = sup {F(x): x E P }

zu bestimmen.

(7)

L. ELSNER: fjber Eigenwerteinschliehngen mit Hilfe von Gerschgorin-Kreisen 383 _ _ _ ~ - ..

0. B. d. A. sei y = 0 und u = (1 , . . . , p}. Es sei ferner

e , = (1 , . . . , 1 , - 1 , . . . , -l), E , = diag ( I , . . . , 1, - 1 , . . . , --1) - - $1- mnl p-ma1

Dann folgt sofort

z E P , r(x) 5 A 5 T(z) ( A E , - H ) x 2 0 .

Lemma 1 : Fur einem Vektor x > 0 sind aquivalent

(1) (11)

Be wcis: Man beachte nur die Aquivalenx der Ungleichungen

laiil + A+(%) 5 I 5 la,jJ - A,(%) i S P < j init

Aus Xatz 1 und Lemma 1 folgt nun

Lemma 2 : Flir irreduxibles H und eine gegebene Zahl A simd folgende Aussagen aquivalent : _- 1 e, E M ( H ) . 3 x > 0 init (A E, - If) x 2 0 . 3 L E P , so daJ ~ ( x ) 5 A 5 F(z) is t .

Es sci iin folgendcn A und darnit H irrcduzibel,

(1) (11)

(111)

_. _- A, = inf {A: 1 e , E M ( H ) }

Da die Diagonalelemente von &I-Matrizen positiv sind, ist A, > - co. Offenbar ist A, e p E a M ( H ) . Sach Satz 2 existiert genau ein x, > 0 mit A, E , x, = H x,. Lemma 1 zeigt, daB x, E P ist, daB also A, 5 A, ist. 1st A, < A , , so gibt es ein x E f’ mit A, ~ ( z ) < A,. Nach Lemma 2 ist ~ ( x ) e p E M(H), also A, 5 r ( x ) . Es folgt A, = A,. Ebenso lionncn wir zeigen, daW

___ M , = M , = sup (1: 1 e , E M ( H ) }

ist und daW es ein z, E P mit Mu E , zo = H z, gibt. Es sei Q = Epl H . Dann ist Q xu = A, xu und Q x, = M u 2,. Aus der strikten lionvexitat von M ( H ) folgt, dalJ A, und M, die cinzigen Eigenwertc von Q rnit positivcin Eigenvektor sind. Wir fassen zusammeri :

S a t z 4 : Es sei A irreduxibel. Fur 7’ = 0 und u = { 1, . . . , p } sei P nichtleer und A,, M , wie in (7) definiert. Damn sind A, umd M , der kleimste bxw. der groJte Eigenwert von Q = E;l H , der einen positiven Eigenvektor besitzt. Es existieren inindestems p Eigenwerte vom A , die einem Betrag kleimer als oder gleich A,, und naindestens 71. - p Eigeiwerte, die rinen Betrag groper als oder gleich M , besitzem.

4.

Man kann dieses Ergebnis auch mit den von MEDLEY und VARGA benutzten Mitteln erhalten. Wir nehmen in H die folgende Einteilung vor:

- - P n - P

Dabei sei E die ( m - p)-dimensionale Einheitsmatrix. Wahlen wir k 2 max latzl fest, so sind alle H , (i = 1 . . . . ,4) nichtnegativ. I r P

In [3] und [6J wird die Iteration

&+I = Q (HI + Hz (k - hi - Hq1-l H3)

betrachtet und gezeigt, daB fur A, E [A,, M,] gilt

ili I 1 5 A, ( i = 0, 1 , . . .) , litriAi = A, . Analog lafit sich beweisen : 1st

so gilt E [A,, M01 u n d ~ i + l

pt 1 2 pz lim pa = J f o .

k - Q (H* + H3 (puz - Hi)-’ H , ) ( i = 0 , 1 , . . . ) ,

384 L. ELSNER: uber EigenwerteinschlieBungen mit Hilfe von Gerschgorin-Kreisen

J.

I n diesem Abschnitt werden hinreichende Bedingungen dafur angegeben, daB bei y = 0 und 0 = { 1, . . . , p } Y nichtleer ist, daB also die Bedingung (4) fur passendes x erfullbar ist.

Es sei wie in [2 ] 8 die Menge aller Matrizen mit der Eigenschaft, daB die Koeffizienten jeder Zeile auBer- halb der Diagonalen gleiche Betrage haben. Sei A E 8, mi = lutkl, i + k. Fur H = H ( A ) gilt dann

rnit l a T = (q, . . . , mn), eT = (1 , . . . , l), D = diag (d,) und

- H + l E p = - m e T + D

1 . nz, + I - la,,\ i 5 p i > p { IaEZl + m, - A

di =

- Kach Lemma 2 ist P + 0 genau dann, wenn fur einA der VektorA ep E M ( H ) ist, d. h. wenn (siehe Satz 1,

11) p(D-1 eT) 5 1 , dt > 0 ( i = 1, . . ., n)

ist. Wegen e (D-I m eT) = eTr D-I m folgt S a t z 5 : Ist A E 8, m > 0, so ist P $1 0 g e m u d a m , wemm es eim 1 gibt mit

- 4 = max lazi] 5 A d = min luitl ,

i 5 p i > p so daJ

m* mi C mi - lalil + 3- + C ~ + l ~ l j z 5 f (A) = eT D-1 m = i s p i>p

i s t . A, m d ill, sind die kleinste bzw. groJte Nullstelle von f(A) - 1 in ( d , 2). \Via in L2] ergibt sicli daraus ein hinreichendes Kriteriurn fiir P $r 0 :

S a t z 6 : 1st mt = max luikl + 0 und fiir e inA in (8, 2) f(1) 5 1, so ist P =/= 0.

Ebenso ubertriigt sich Satz 5 von [2]. Genauer gilt:

S a t z 7: Xei /aixl 5 E (i $1 k ) , w = d - d_ - (n - 2 p ) E ,

ifk

-

1 2

LXl$ - 4 - 1 -- (20 7 (WZ - 4 (12. - 1) 6 2 - 4 (1 - 4) ( p - 1) E ) q

Und a - 6

n - 2 + 2 i P (n - 2.)) 6 _ _ _ _ _ _ _ ~ ~ .

Dan% ist Y + 0 und, A, 5 a1 Es gibt also mindestens p Eigenwerte von A in 1x1 5 a, und mindestens n - p Eigenwerte von A in /zI 2 a2.

Es sollte abschliefiend noch einmal daran erinnert werden, daB diese Aussagen nur fur y = 0 und cr = { 1, . . . , p } gelten. Im konkreten Fall wird daher im allgemeinen noch eine Verschiebung und eine Permu- tation der Zeilen und Spalten erforderlich sein.

a2 5 M,.

6.

L)a (1 uiid ihre Transponierte AT gleiche Eigenwerte bcsitzcn, lie@ es nahc, auch die GERsoHGoRIN-Kreise von A'' zu betrachtcn. Sie siricl zwar bei gleichem x i. a. von don IIt(z) veruchieden, cs zeigt sich jedoch, daW fur A, und M , dieselben Werte herauskommen, daR also die Minimalkonfigurationen, die ja nur durch die ati sowie A, und M , festgelegt sind, iibereinstimmen.

Es gilt zunachst H(AT) = HT(A). Weil eine Matrix B wegen (B-l)T = (BT)-l genau dann M-Matrix ist, wenn BT es ist, gilt M ( H ( A ) ) = iW(H(AT)) . Aus A, = inf {A: A e p E M ( H ) } und No = sup { A : 1 e p E M ( H ) } folgt nun die Uehauptung.

__ __

Li teratur 1 L. COLLATZ, EinschlieBungssatx fur die charakteristisohen Zahlen von Matrizen, Math. Z. 48, 221 -226 (1942). 2 L. ELSNER, Ninimale Gerschgorin-Kreise, ZAMM 48 (1968), 51 -56. 3 H. I. MEDLEY, R. S. VARQA, On Smallest Isolated Gerschgorin-Disks for Eigenvalues 111, Num. Math. 11, 361-369 (1968). 4 0. TAUSSKY, Eigenvalues of finite Matrices, in: A Survey of Numerical Analysis (ed. Todd), 1962. 5 J. TODD, On Smallest Isolated Gerschgorin-Disks for Eigenvalues, Num. Math. 7, 171-175 (1965). 6 R. S. VARGA, On Smallest Tsolated Gerschgorin-Disks for Eigenvalues, Num. Math. 6, 366-376 (1964). 7 R. S. VARGA, Matrix lterat,ivo Analysis, Englewood Cliffs, New Yersey, Prentice Hall Inc., 1962.

Mariuskripteingang: 16. 10. 1969

Aizschrift: Dr. LUUWIG ELSNER, 2000 Hamburg 13, Rothenbaumchaussee 67/69, Institut fur Angewandte Mathematik