H. KRAVER, Eine Vcreinfachung des Verfalirrns von LE VERRIER- HORST 297 - __ - - ~-

ZAMM 46 (1066) Heft 1, Soito 297-304

Eine Vereinfachung des Verfahrens von L e V er r i e r - H o r s t zur Aufstellung des charakteristischen Polynoms einer Matrix *)

Von H. KRAMER

lh wirtl e ine M ~ l l i o d c angrgrbcn. dic cs Prlaubt. doit Rmhpnaufwnnd h i i i i Vei fuhrrn iron Lc V r i -

It as shown that, by a certain method described here in , the calculation expfnditurc TeqzLired in the L P

t i e r [l] - H o r s t [2] f u i n > 1 von n4nuf n7I2zu sPnI:an.

T/c.rricr [l] - H o r s t [2]proc~dure for n > 1 may br reduces from n4 to n7P.

. I e ~ c p p r ~ e [l] - XopcTa 121 mu^ n > 1 cn4 20 72713, B pa6OTe HaH MeTOX, KOTOphIfi IIO3BOJIHeT >‘nfeHI~III~Th B 1 ~ I ~ I ~ C ~ I L I T C ; l I ~ H y I O pa6OTy IIpm C I I O C O 6 ?

1. Kurze Beschreibung des Verfahrens Das im Titel genannte Verfahren gehort zu den direkten Verfahren zur Herechnnng der

Eigenwerte yon Matrizen. Das Verfahren dient dazu, zu gegebener (n, n)-Matrix A = ( a t j ) mit komplexen Elemeliten aLJ die Koeffizienten a, des zur Matrix A gehiirenden cliarakteristischen Polynoms Pn(;l) zu berechnen.

det (A -1 E ) = PR(;l) = 2 an-% 2 . 11

k = o (1 )

Dahei wird die Tatsache benutzt, da13 die Spuren der Matrizen A” = (a!?) gleich den Potenzsummen s, der Wurzeln At des charakteristischen Polynoms sind.

n

Die Koeffizienten ai des charakte,ristischen Polynoms erhalt man nach den NEwTomchen Formeln

(3)

2. Betrachtung uber den Rechenaufwand Als Rechenaufwand r bezeichnen wir die Anzahl der Additionen a, der Subtraktionen s,

der Multiplikationen ni und der Divisionen d. Wir schreiben r als Vektor und spalten ihn in drei Restandteile auf:

llabei ist r, der liechenaufwand zur Berechnung der At’ bzw. der a!;), r, der Rechenaufwand zur Berechnung der s, aus den aj;), r8 der Kechenaufwand zur Berechnung der a, aus den s,.

Es ist, wie man aus den Formeln (2) bzw. (3) erkennt,

(5)

n ( R - 1) 0

r2 =( I bzw. r3 = (i Die Komponenten von r, hangen d a w n ab, auf welche Art und Weise man die a:;) berechnet. Man kann nacheinander die Potenzen A” nach der Vorschrift (6) bilden und hat damit auch die gesuchten a!$) :

= A A ” f ~ r v = l , 2 ,..., n - 1 . APfl (6)

~ ~

*) Teil einer Diplomarbeit an der Technischen Hochschule Karlsruhe, Institut fur angewandte Mathc- niatik und GroWrechenanlagen (Direktor : Prof. Dr. KARL NICKEL), unter dem Titel: Numerische Berechnung der Eigenu erte von beliebigen Matrizen mit koniplexen Elenienten beiin Einsatz von (elektronisrhen) Rechen- automaten.

H. KRAMER, Eine Vereinfachung des Verfalirens von LE VERRIER -HORST __-___ - ~ - ~ _ _ ~~-

29s

Den damit verbundenen Rechenaufwand bezeichnen wir mit r',". Es ist

_ _ _ ~ -

Beachtet man, da13 die aufierdiagonalen Elemente der Matrix AY nur dazu dienen, die nachstfolgende Matrix zu berechnen, so erkennt nian, da13 sich ihre Berechnung in der Matrix LA*t eriibrigt. Auf nn folgt keine weitere Matrix mehr. Der Rechenaufwand r, ist in diesem Falle also kleiner als r(1l). Er sei mit rC2) bezeichnet. Es ist

(n - 1)2 n

(n - 1) n2 rc2) = r(1) - (: ) = ri1) - R = (n - 1) R . (8)

BODEWIG [3] bzw. DURAND [4] zeigen, da13 sich der Kechenaufwand r, weiter verkleinern laflt. Es ist namlich gar nicht notig, n - 1 volle Rfatrizenpotenzen zu kennen. Es geniigen die ers-ten [!!-:-!I I'otenzenl). Aus ihnen lassen sich die a,!;) (v > [f- 11) der fehlenden Potenzen nacli der

gleiclien Uberlegung, die zu (8) gefiihrt haben, nach der Vorschrift (9) berechnen. Es eriibrigt

sich dabei, die auBerdiagonalen Elemente von AY ( v > [n-:J]) zu berechnen.

Der damit verbundene Kechenaufwand r1 werde mit $1 bezeichnet. Es ist

ri') ist zwar immer noch proportional zu n4, aber nur uiigefalir halb so grolj wie rp). Eine wesent- liche Verringerung des Arbeitsaufwaiides ist bereits erzielt.

3. Eine weitcre Vcrkleinerung des Rechenaufwandes Bezeichnel man die Anzahl der vollstandigen zu berechnenden Potenzen von A mit p ,

so lassen sich die I'ormeln (7), (8) und (10) auf die ubersichtliche Formel (11) hririgen: (11) $1 = p(1) Ii ( i = 1, 2, 3) .

E s is1 also p ( l ) = n, $ 2 ) = n - 1, p(.') = [ I 1 '1. I k r Rechenaufwand r, wachst linear mit p . Es erhebt sicli nun die Frage, wie und ob nian

mit riocli weniger als der von BODEWIG bzw. DURAND angegebeneri Anzahl vollstandiger Matrizen- potenzen auskommen kann. Das ist moglich, wie ein weiter unten angefuhrtes Beispiel und die darauf folgende Uberlegung zeigt. Zunachst aber stellen wir folgende Betrachtung an :

IVir herrchnen die Potenzen von d nach deni Schema (12): A, '42, A3, . . . , A q , A", A 3 * , . . ., A(k--l)Y . (12)

Dabei ist zunachst q < n beliehig. k wird so groB gewahlt, da13

(13a) ist. 15s gclte auflerdem (13b)

Icy zn ( k - l ) g < n .

Es ist leicht einzusehen, da13 auch mit dieser Anordnung der vollstandigeii Potenzen von A die Spurenelemente a',",) (v 5 n) der restlichen Potenzen von A berechnet werden konnen, ohne da13 dabei die Nichtdiagonalglieder mitberechnet werden miissen. Unter der Voraussetzung (13) hat man also insgesamt

('4) p = g + k - - 2

H. KRADIER, Eine Vereinfachung des Verfahrens von LE VERRIER- H O R ~ T 299

vollstandige Potenzen yon A zu berechnen. Dan das aus (14) erhaltene p kleiner sein kann als das p nach Formel (lo), zeigt das folgende Beispiel: n = 100, q sei 10; aus (13) folgt, da13 k = 10 sein mu8. Uemnach wird p = 18, gegenuber p = 50 nach Formel (10). q war in diesem Reispiel beliebig gewahlt. Es ist vorteilhaft zu wissen, fur welches q die Zahl p am kleinsten wird. Vm dies zu erfahren, losen wir folgende

R u f g a b e : Zu gegebenem I I > 1 mache man p = q + k - 2 zum Minimum unter der Nebenbedingung (13): (k - 1) q < R 5 k q.

Von der fraglichen Losung p , die wir mit pc4) bezeichnen werden, behaupte ich:

1. 1% rxistiert mindestens ein Losungspaar ( k , q) so, da13 p(') ein Minimum wird.

~~~ ~ ____ __ ____ ~~- - _ _ ~

3. p(4) 5 p ( : j ) . Das Gleichheitszeichen gilt nur fiir 2 5 n 5 8 und fur I I = 10.

llilrl 1 . Skizzc ZII Tcil 1. unrl 3. dcr Aufynlie fiir 11-5

Beweis zu 1. und 2 . : Die Nebenbedingung (13) besagt, dalJ nur solche Punkte der k-q- Ebene in Betracht kommen, die in dem Bereich B zwischen den beiden Hyperbelasten q = nlk und q = n / (k - 1) liegen (s. Bild 1). Dieser Bereich heil3e zulassiger Bereich B. Die Gleichung (14) stellt eine Geradenschar dar mit p als Scharparameter. Die Steigung der Geraden ist - I. Losung des Problems ware, miifiten nicht k und q, und damit auch p , ganze Zahlen sein, offensichtlich der Beriihrnngspunkt P der zn den Geraden parallelen Tangente an den Hyperbelast q = n /k . I' hat die Koordinaten ( k , q) = ( in, I/;). Der zugehorige Parameterwert ist p = k + q - 2 =

2 I/. - 2. Fur ein p < gibt es sicher keine Losung des Problems. 1st n eine Quadratzahl, so ist I/. ganzzahlig und (i, i) bzw. p ̂ Losung der Aufgabe. Fur n = ni2 ist damit 1. und 2. be- wiesen. Im folgenden betrachten wir nur den Fall n + m2. Fur n + m2 ist die kleinste in Be- tracht kommende Losung die nachste auf p̂ folgende ganze Zahl, d. h. p = [^p + 11 = [2 1; - 11 ; das ist das in der Behauptung 2. angegebene p . \.Venn wir gezeigt haben werden, da13 die Gerade 9 mit dem Scharparameter p ganzzahlige Punkte ( k , q) im zulassigen Bereich hat, so ist der Beweis von 1. und 2. vollstandig.

A / . A h A

H. KRAMER, Eine Vereinfachung des Verfithrens von Ls VERRIER - HORST _ _ - ~ _ ~ _ _ __ -____ 300 _ _

Ich will nun einen Punkt ( k , q) angeben und zeigen, daB er zu B gehort und auf I/ liegt. Die Koordinatm des Punktes sind:

(15a) q = [Jn + 11 f i r [in] [I/; + 11 < n , (15 b) = [I/; + 11 , = [ii] filr [fn] + 11 2 1 7 .

Der Punkt ( k , q) liegt in R, denn es ist filr

(15a)

k = [JG + I ] ,

( k - 1) q = [in] [h + I] < n nach Voraussetzung und k q = [l/k + 11 [(. + 11 2 n da [ i n + 11 2 I/; ist;

( k - 1) = [I/;] [In ’-1 < n, da [r/n] < i n ist fdr 17 + n72 und k q = [I/’. + 11 [in] 2 n nach Voraussetzung.

(15b)

Der Punkt (k , q) liegt auf g , denn es ist nach Voraussetzung im

Fall (l.5a) [in] [q. + 11 < n. Damit ist auch, da [h], [h + 11, n ganze Zahlen sind, [ i n ] [l’n 4- 11 + 1/4 < n. Die linke Seite der Ungleichung 1aBt sich umformen:

‘“l + 2

< j/n und damit 2 [ in] + 1 < 2 ti. Da aber 2 1/. < 2 [r/. -t 11 isl, Es ist also

so liegt 2 f n zwischen zaei aufeinanderfolgenden ganzen Zahlen und es ist [2 l’n] = 2 [1/n] + 1. Dar heint, es ist k + q - 2 = [I/< + 11 + [in + 11 - 2 = 2 [h] nach dem ebeu Gezelgten gle1ch [a I/.] - 1 = [ 2 1/i - 11 = p(4).

L\hnlich schlie13t man im Fall (15b): EsistnachVoraussetzung [(GI [I/. + 11 2 n. Damit wird [in] [n + 11 + 1/4>n

zwischen den ganzen Zahlen und 2 rf.1 + 1 > 2 1.. Da aber 2 I/. > 2 [I//<] ist, so liegt 2 2 rl’n1 uud 2 [I/.] + 1, d. h., es ist [ 2 I/.] = 2 [iii]. Damit ist

-

k + - 2 = [JE 11 + rC/;] - 2 = 2 [in] - 1 = r2 in] - 1 = [ 2 in - 11 = p). .JeLzt 1st 1. und 2. vollstandig bewiesen.

Zum Heneis von 3. rechnen wir uns die GroBen p(’) und p(4) fur n (= 13 a m :

~ ~ ~ --

p ( 4 ) - 2 [1 /n - 1 - ‘ 7Yn [Vn,] 1 2 . 2 3 8 4 4 4 5 5 3 li

Fur n > 13 gilt: n2 -- 14 11 + 49 = (n - 7)z > 48. Dieser Ausdruck laI3t sich auch schreiben als (n + 1)2 > 16 n. Zieht man beiderseits die Wurzel und dividiert durch 2, so erhalt man die Beziehung + > 2 ti. naraus folgl [ n 4- 2~ 1 1 2 [ 2 y.1 und (iaraus wiederum folgt

[I’ ‘1 > [ 2 fri] - 1 = [2 I n - 11 2 [2 I n - 1 - hVn, r,/z,], w. z. b. w.

Damit haben wir gezeigt, daB sich durch geschickte Anordnung der vollstantligen Potenzeii von -2 filr n = 9 und n > 10 eine weitere Kechenersparnis ergibt. Beachtet man, da13 r, und r3 - deren Komponenten im wesentlichen proportional zu n2 sind - gegenuber dem Aufwand r1 vernachlassigbar sind und damit I’ m r1 ist, so sieht man, da13 auch r bei konstantem n linear vou p abhangt. Das Verhaltnis der einzelnen p(‘ ) zueinander gibt also im wesentlichen auch das Verhaltnis des Kechenaufwandes mit den einzelnen p”) an. Zur Veranschaulichung sind die einzelnen p(’) uber n in Bild 2 aufgetragen.

4. Das Verfahren von Le Verrier -Horst beim Einsatz von automatischen Rcchenmaschirlell Hatte man eine unbegrenzte Anzahl von Speicherzellen zur Verfugung, so wiirde sich die

folgende Betrachtung erubrigen. Doch ist diese Anzahl, sie sei mit c bezeichnet, begrenzt. Es fragt sich, wie grol3 n bei den vorhes beschriebenen Methoden ( i ) z, (i = 1, 2, 3, 4) maximal sein kann,

2 /-

Hier hedeiitet die Methode (i) die zi1m Rechenaufwand r(i) gehorencle Methodr.

H. KRAN IZR, Eine Vereinfachung des Verfahrens von LE _ _ _ _ ~ - ~'KRRIER - HORST 301

I 20

10 20 30 40 n

Hild 2. Syczifischcr Rechcnaiifwand p ( i ) fiir die vier betrachteten VcrftIhrell

damit rnit eirier Illaschine der Kapazitat c die Koeffizienten ai von P, aus A berechnet werden konnen.

Zunachst mochte ich den Begriff ,,Block" einfuhren. Unter einem k-Block will ich k fur einen bestimmten Zweck reservierte Speicherzellen verstehen; z. B. ist der Speicherplatz fur die n2 Elemente von A ein n2-Block.

Fur die Verfahren (1) bzw. (2) brauchen wir jeweils nur n2 + 3 n Speicherplatze, wenn man folgenden Kunstgriff zur Berechnung der s, anwendet. Wir schreiben A als (Al, A,, A,, ..., A,), wobei die Ad Spaltenvektoren sind. Dann ist mit AY+-l = A Av auch A$'-:-1) = A A:*,), wobei AY = A?), . . .) A t ) ) ist. A speichern wir in den n2-Block X. Fur die s, reservieren wir einen 11-Block S. AuBerdem reservieren wir zwei weitere n-Blocke Y und Z. Hat man s1 be,rech- net, so verlauft die weitere l<echnung fiir i = 1, 2, 3, . . ., IZ wie folgt: Nach Y speichern wir A(:) = Ai. AnschlieBend berechnen wir A?) (v = 2, 3, . . ., n) und speichern diese Vektoren abwechselnd nach Z oder Y zur Berechnung des Vektors A$'+1). Das kann man tun, da der Inhalt dcs n-Blocks Z oder Y , in den gerade gespeichert werden soll, zur eben durchzufuhrenden und auch zur weiteren Rechnung nicht mehr benotigt wird. Jedesmal, wenn man ein A?) berech- net hat, addiert man zur GroBe s, das i-te Element von Man uberzeugt sich leicht, daB nach dieser Vorschrift die Anzahl der arithmetischen Operationen erhalten bleibt, vie1 mehr noch, daB die Zahlen, mit denen sie ausgefuhrt werden, dieselben sind wie bei der urspriinglichen Methode. Die noch aus den s, zu berechnenden a, kann man z. B. auf den n-Block Y speichern.

(16) n 2 + 3 n 5 c . Daraus folgt: rzgiLx = [fc +- 2,25 - 1,5] (i = 1, 2).

Me thode (3): Nach DURAND [4] hat man hier p(3) = In$] ganze Potenzen von A

d. h.

Man erhiilt somit das maximale n = nlllas aus der IJngleichung (16):

L L J n + 1 zu speichern. Das heifit, daB man 1- ~ 1 n2-Blocke zur Verfugung haben mu13. Man kommt L J

aber mil nur drei n2-Blocken aus, wenn man die Spurenelemente der Potenzen fly (v > P ( ' ~ ) ) nicht nach der Vorschrift (9), sondern nach der Vorschrift (17) bildet.

(1 7) llas heiBt : Man braucht nicht erst A"'3' Z U kennen, urn die Spureneleinente von A" (v > p@))

zu bereclinen. Es geniigt die Kenntnis der Potenzen bis einschlieBlich 1, und von diesen L A J

V fur geradzahliges v und die Potenzen r-; '1 und 2

wiederum nur die Potenz

%) Dabei ist zu beachton, d t d i wir vor Beginn der ganzen Rcclinung s, = 0 gesetxt h n h m .

302 H. KRAMER, Eine Vereinfaclzuiig des Verfahrens von LE VERRIER- HORST

[Y-i~L] fiir ungeradzahliges v, also hochstens zwei Potenzen. Insgesamt benotigt man drei

ii2-Blockc nnd einen n-Block, wenn man nach der Vorsclirift (17) arbeitet. Nan berechnet die

PotenZen bis einschliel3lich t = ~~ __- mit den zugehorigen Spuren, indem man die PotenZen

abwechselnd in zwei nZ-Blocke speichert, SO daI3 immer nur die Potenzen 1, v und v + 1 ge- speichert sind. Ab v = t berechnet man noch die Spurenelemente von A' A I , ~ + l bzw. A ~ Y , bevor

man eine weitere volle Potenz A y ? ~ 3 bereclinet. Man fahrt so fort, bis man alle pc") =

PotenZen berechnet hat und damit auch alle Spuren der atatrizen Rv ( v > p ) kennt. Die ai speichert man in eiiien der nicht mehr benotigten n2-B10cke. Man erhalt dann r ~ ' & , ~ aus der Ungleichung (18).

I ":$)2+ I [,,,I]

3 n 2 + 1 7 sc

Metl iode (4): Die Losung der Aufgabe war nur beziiglich p eindeutig gewesen. k und q liatte ich zunachst heliebig gewahlt. Wie aus Bild 1 zu ersehen ist, kann es vorkonimen, dafi mehrere Punkte ( k , q) Losung der Aufgabe sind. - Hei der Methode (4) mu0 man die ersten (I Potenzen von A speichern, wahrend es fiir die restlichen Potenzen AvY genugt - wie bei den Meihoden (1) und (2 ) -, jeweils nur zwei Spaltenvektoren A(iy'J) bzw. AP+l)Y zii kennen. Man braucht also insgesamt q n2 + 3 n Speicherplatze. - Da q nach der ersten Bemerkung zur Me- lhode (4) nicht eindeutig ist und nach der zweiten Bemerkung der Speicherplatz rnit wachsen- dem q auch grol3er wird, so ist es vorteilhaft, das kleinste q = qiirill zu gegebenem n und p zu kennen. Dazn schneidet man (s. Bild 1) die Gerade p( ' ) = k + q -. 2 rnit der Hyberbel = n/k, Das fiihrt anf eine quadratische Gleichung fur k (bzw. q) mit der Losung

-- [ p + 21 & \/mqm _ _ ~ 2 (19) k =

Wahlt man das k maximal, d. h. die Wurzel mit dem +-Zeichen, SO wird q minimal. Da aber k uiid q ganzzahlig sein sollen, so erhalt man als Losungspunkt de,n Punkt (k, u=> mit

Ilahri ist p = [ 2 I/n - 1 - d),<, [ y i I 1 .

Diese Ungleichung nach n aufzulosen, ist mir auf einfache Art und Weise, d. h. ohne viele Fallunterscheidungen, nicht gelnngen. Man konnte, um die Ungleichung (21 a) auszuwerten, die Funktion f(n) tabellieren Is. Tabelle (22)] oder graphisch darstellen (s. Bild 3).

(22)

3 1 4 '

: 1 7 ' 8 1 !I I

10 11 I

10 ~1 12

90 1 16

27 1 13 44 1 14 65 15

119 '~ 17 152 18 270 , I 19 230 20 396 1 1 21

__ -

468 22 546 I 23 630 i 24 720 25

1072 ~ 26

1026 28 1501 29 1660 1 30 1386 1 31

918 I 27

2002 2185 2376 3200 2782 2997 3220 4292 4590 3937

H. K s a n i ~ ~ , Einc Vercinfachung des Verfahrens 1-011 LE VERRIER - HORST 303 ~ _ _ _ _ _ _ _ ~ ~ -~ - ~-~~ ~-

f (RJ

5000

4006

3000

2000

1000

0

d

d

p:

4' ? 1

I

P P

d 0

P

Docli ist das gar nicht notwendig, wenn man noch die folgende Betrachtung anstellt. \Venn die durch die Methode (4) benotigte Anzahl der Speicherplatze, gegeben durch f(n),

grol3er ist als c, so kann man sich die Frage stellen, ob man nun mit dem Verfahren (3) rechnen mu13 (falls die Maschine uber 3 n 2 + n Speicher verfugt), oder ob es moglich ist, eine andere Methode zu ersinnen, deren Rechenaufwand nicht mehr minfmal ist wie mit der Methode (4), aber doch kleiner als der mit der Methode (3). - Das ist moglich, wenn man mehr als 2 n2 + 3 n Speicherzellen zu r Verfiigung hat. Man uberlegt sich, da13 nach Schema (12) der Rechenaufwand

fiir p = 2 genaii so groB ist wie bei der Methode (3), p ist ebcnfalls [" P~~~ '1. Ferner iiberlegt

man sich, daB, da k w n/q ist, p w n/q + q - 2 wird ( p ist hier nicht mehr wie bei der Methode (4) festgelegt, sondern eine Funktion von q) . Da aber n/q + q - 2 in 1 5 q < I/. mit wachsendem q eine monoton fallende Funktion ist, so wird auch p und damit der Rechenaufwand mit wachsen- dem q kleiner. Man wird versuchen, q moglichst grol3 zu wahlen, d. h. alle Speicherplatze auszu- nutzen. Ilieses maximale q = q,,,, hestimmt sich damit aus der Ungleichnng

(23) q n 2 - + 3 n g r .

c - 3 n Daraus folgt: (I,,,~,, =

Berechnet man jetzt qllli,, aus (20) und qnlnx aus (23), so kann man, ohne erst f(n) berechnen zu mussen, entscheiden: l., ob man mil: der optimalen Methode (4) rechnen kann (dann ist qmir, 5 q,,,,,) urid 2., wie man Q zu wahlen hat (namlich q = qmi,,, falls ql,,in 5 qlllRX, und q = qlllil,, falls qiii in > qmax).

H. KRAMES, Eine Vereinfachung des Verfahrens von LE VERRIER- HORST -~ __ -___ 304

. ~~ - - _ ~ _ _ _ _ _ ~ _ _ ~ _ _ _ _

Ich mochte noch anfiigen, daI3 die Methode (4) auch im Falle q = 2, d. h., wenn &Lht opt,nral =

4- * = [P) ist, der Methode (3) vorzuziehen ist, da mit der Methode (3) insgesamt 3 n2 + n [---I Speicher, mit der Methode (4) aber nur 2 n2 + 3 n Speicher benotigt werden.

Literatnr 1 U. J. J. LE VERRIER, Journal de Math., serie 1, vol. 5, S. 230 (1840). 2 HORST, Annals Math. Statistics 6, R. 83 (1935). 3 K. RODEWIG, Matrix calculus, Bmsterdani 1956, S. 315-317. 4 E. DURAND, Solutions num6riques des Bquations algBbriques, tome TI, Paris 1961, R . 195-196.

Manuskripteingang : 4. 8. 1964

Avsehrift: H. K R ~ M E R , 673 Haardt, Hauptstr. 64