367 Z. angew. Math. Mech. Bd. 22 Nr. G Dez. 1911 C o 1 1 a t z , Fehlerabwhatzung fiir das Iterationsverfahren

Fehlerabschatzung fur das Iterationsverfahren zur Auflosung linearer Gleichungssysteme.

Von L. CoZZatz in Karlsruhe. Vorgetragen auf der GAMM-Tagung 1942 in Miinchen.

Fur das ItePationsverfahren xur nitmerischen Auflosung linearer Gleichungs- systeme w i r d eine Fehlerabschatzung durchgefiihrt unter der Voraussetzung, dup die Hu.ztZ-'tdia~onnlelemente genugend stark iiberruiegen. Die G auFsehe Transformiition ist nicht immer geeignet, um a w einem beliebigen Gleichzcngs- system ein solches mit iiherwiegenden Hauptdiagonalgliedern xu erze4tge.n.

*$

1. Fragestellung.

Vorgelegt sei ein lincares Gleichungssystem 11

. . . . . . . . . . x C t i k X k = r l ( i = 1 , 2 , . . , n ) . * (1) k = l

oder in Matrizenscllreibweisc . . . . . . . . . . . . . ' U g = r . * f (21,

die Deterininante 1 a i k / eei $=o. Rei dern ,,Iterationsverfahren in Gesamtschritten" ') verbessert man Nglierungswerte fur

die xi schrittweise und berechnet aus der v - ten Naherung xi"" eine (v + 1) - te Nllierung xi" + I)

nach der Vorschrift

k = l k 11: i

und heim ,,Iterationsverfaliren in Einzelschritten nacli der Vorschrift i - 1

*P x ; ( Y + I ) .- - __ (I.i - ) :a iKxklv+l ' - 2.i. xgfyl) . I . . . (4).

ai i k = l k = i + l

Diese beiden Iterationsverfahren konvergieren nicht immer, und wenn sie konvergieren, nur dann fur die numerische Reclinunq rasch genug, wenn die Hauptdiagonalelemente aii die iibrigen Elemente ailc genugend stark uberwiegen.

Im folgenden wird auf die beiden Fragen eingegangen : 1. Wie stellt man zu einem beliebigen vorgegebenen Gleichungssystem (I), bei dem die

ai i nicht genugend uberwiegen, ein neues Gleichungssystem rnit gdnugend iiber- wiegenden Hauptdiagonalelementen her?

2. Wie kann man a m den nacli den Iterationsverfahren berechneten Naherungswerten ihren Fehler abschatzen?

2. Hilfsbetrachtung: 2 Unbekannte. Bei 2 Gleicliungen mit 2 Unbekannten

} a,,%, +"iZ%=r,,

Q,, *i + a 2 9 5, = r2 . . . . . . . . . . (5)

lassen sich die Verhaltnisse vollstandig uberblicken. Fiir die Fehler &i(") der v - ten Naherung f y) = Xi (" ) - xi (i = 1, 2)

erhalt man beiiii Iterationsverfahren in Gesamtschritten

wobei zur Ahkiirzung IY + 11 - - a F i l Y - 1) Fi Y

3) R. v. h I i s e s - H . P o l l a c i e k - C ; e i r i i i g e r : Z. angew. Math. Meoh. Bd. 9 (1929), S. 58 bis 7 i . e ,

Z. angew. Math. Mech. Bd.2% Nr.6 Dez.1942 C o 11 a t z , Fohlernbschatzung fiir das Iterationsverfahren 358

gesetzt ist, wallrend beim Verfaliren in Einzelscliritten

wird. Man sieht also: Beide Iterationsverfahren konvergieren genau dann, wenn (a1 < 1 ist; man kann a als Gutezahl fur die Konvergenz auffassen, der Fehler gelit auf den Bruchteil a herunter, und zwar beim Gesamtschrittverfahren in 2 Schritten, beim Einzelschrittverfaliren in 1 Schritt. Das Gesnmtsciirittverfahren benotigt zur gleichen Genauigkeit im vorliegcnden Fall genau doppelt so viele Schritte als das Einzelschrittverfahren.

Bei drei Gleicliungen mit drei Uubekannten liegen die Verhaltnisse iiictit mclir so ein-

bell. Bei einem Gleichungssystem ( 2 ) iiiit der Matrix % = (-: konvergiert (hei be-

liebigem Vektor r) das Einzelschrittverfahren, aber niclit das Gesamtschrittverfaliren iind bei

F i ( l J + 1) = a Fit"')

2 --1 1

/1 2 - 2\ einem Gleichungssystem (2) mit der Matrix 8 = 1 1 1 konvergiert das Gesamtscliritt- L 3 1) verfahren, aber nicht das Einzelschrittverfahrcn.

3. Die Gaui3 sche Transformation. Bei der Gaukiscllen Transformation rnultipliziert man G1. (2) von links niit der aus ‘u

durch Spiegelung an der Hauptdiagonalen hervorgelienden Matrix el’ und erlialt als neues Gleichungssystem

% ~ = 5 niit %=a‘%; 9=W’r . . . . . . , . . . (6).

Die Matrix d‘ ist symmetriscl~. Die zu ihr gelidrende quadratisclie Form ist positiv definit und daher I ) konvergiert das Einz~:lscl~rittverfaliren bei den1 neuen Gleicliungssystem (6). Die Theorie hat dadurch eine grofic Abr undung erfahren, fur die praktische Rechnung hat jedoch die G a u D sclie Transformation einige unangenehme Eigenscliaften. Das neue Gleicliungs- system (6) gehdrt zwar zu einer positiv definiten quadratischen Form, aber die Hauptdiagonal- elemente tiberwiegen oft nur in so sch wacliem Mafie, dafi das Iterationsverfahren sehr langsani konvergiert und fur praktisclie Zwecke vdllig unbrauchbar sein kann. Ferner kann die G a u fi sclie Transformation die Konvergenzgute verschlechtern.

Zur Erlauterung mird ein Gleicliungssqstem mit 2 Unbckannten betrachtc t, GI. (5).

a 1 2 f l L l

a,, %2

Hier hat das Gleichungssystem nach Nr. 2 als Gutezahl v

a = 7

t wahrend die Gutezahl des nach G1 (6) hereclineten transformierten Gleicliungssystenies

lautet. Wie es sein niufi, ist < 1. Fuhrt man die Quotienten

Bild 1. Durch die GauQsohe Transforniation wird die Konvergenz des Iterationsverfahrens

0 herbeyefihrt verbuseft verschiehteri

ein, so kann man in einer x-y-Ebene die Bereiche aufsuclien, fur deren Punkte die G a u fische Trans- formation die Konvergenz des Iterationsverfahrens her- beiftihrt (la I > l), verbessert (1 > la] > [ 11) oder ver- schlechtert (1 > I/?\ > l a [ ) .

Bei positivem .c, 3 sieht man, dah nur die beiden Falle la1 > 1 und 1 > IpI > la1 auftreten. Reschrankt

a man sich auf positive Werte der Quotienten -“ 5‘.

a 1 1 , a 2 2

so sind also nur die folgenden 2 Falle moglicl~ (ab- gesehen vom Grenzfall a = 1) : Entweder ist beim Aus- gangssystem a > 1, d a m fuln-t die Gaufische Trans- formation die Konvergenz herbei, oder es ist 0 < a < 1, clann vcrsclilechtert die Transfornlation die Konvergenz. Wendet man also die G a u fi sche Transformation mehr- mals hintereinander an, so kann sie mbglicherweise das erste Ma1 Konvergenz herbeifuhren, bei jedeni weiteren Male jedoch verschlechtert sie die Konvergenz des Iterationsverfahrens.

C o 1 1 a t z , Fehlerabschatzung fiir das Iterationsverfahren 369 2. angew. Math. Meeh. Bd. 2'2 Nr. 6 Dez. 1941

Als einfaches Beispiel betrachten wir das Gleichungssystem

x , - 2 x 2 = 0 ,

ax,- x , = 3

mit der Ldsung xi = 2 , x , = 1 und der Gutezahl. a = 4. Bei der G a u k sclien Transformation entsteht das neue Gleichungssystem

5 X, - 4 $2 = 6,

- 4 x, + 5 2 , = - 3 16 20 mit der Gutezahl -= = 0,64 und bei nochmaliger G a u k scher Transformation das Gleichungs.

system 41 2, - 40 X, =42,

.40 x,+41x2 = -39

1600 init der Gutezahl = 0,95181. Bei dem letzten Gleichungssystem gelit beiin Iterations- 1681 verfahren der Fehler bei jcdem Schritt also nur urn 5 ' /0 herunter, d. h. das Verfahren ist praktiscli unbrauclibar.

4. Das Umformungsverfahren von C. Runge. Nacli dem Vorangelienrlen erscheint die G a u k sche Transformation trotz der theoretischen

Abgerundetheit fur die numerische Rechnung noch nicht als das> ideale Mittel zur Erzeugung ubcrwiegender Hnuptdiagonalglieder. Es sei hier vielmelir auf ein bereits von C. R u n g e angegebenes Verfaliren z, liingewiesen ; man stellt durch Linearkombination der gegebenen Gleichungen neue her, bei denen aukerhalb der Hauptdiagonale nur ' noch kleine Zahlen stehen. Dafi das stets nioglich ist, beweist das G a u ti sche Eliminationsverfaliren, bei dem nian ja durch Linearkombination erreichen kann, daP aukerhalb der Hauptdiagonale uberall Nullen stehen (damit ist dann das Gleichungssystem aufgelost). Beim R u n g e schen Ver. fahren verzichtet man auf die Forderung, aufierhalb der Hauptdiagonale streng Nullen zu er- zeugen, sondern begnugt sicli damit, dak aukerhalb kleine Zahlen stehen, so dak das Iterations- verfahren gut konvergiert. Gegenuber dem G a u P sclien Eliminationsverfaliren hat das R u n g e - sclie Verfahren die Vorteile :

1. Die Erzeugung kleiner Zalilen aukerhalb der Hauptdiagonale ist sehr vie1 leichter als die Erzeugung von Nullen, oft kann man einem Gleichungssystem unmittelbar an- selien, welclie Zeilenkombinationen schncll zum Ziel ftihren.

2. Dadurch, dak man beim R u n g e schen Verfahren die Zeilenkombinationen so vor. nehmen kaiin, dab man nur mit ganzen oder zumindest genauen Zahlen multipliziert, addiert und subtraliiert, hat man keinen Genauigkeitsverlust und kann z. B. ein Gleichungssystem mit dem Rechenschieber aufltisen, wiihrend man beim G a u fi - schen Verfahren zur Erzeugung von Nullen mit im allgenieinen ungenauen Zahlen multiplizieren mu8 und bei grbkerer Anzahl von Unbekannten nicht mehr mit dem Rechenschieber reclinen kann.

Das R u n g e sche Verfahren wird so lange fortgesetzt, bis die Hauptdiagonalelemente ,,genugend" fiherwiegen, d. 11. bis das ,,Zeilensummenkriterium"

t1

1aiil > bi niit b i - - X \ a i k ~ . . . . . . . . . . . (7) k = l k =I= i

fur alle i erfullt ist. Es werde noch

und

gesefzt. Dann ist e ein Mak fiir das Oberwiegen der Hauptdiagonalelemente. J e kleiner e,. desto besser konvergiert das Iterationsrerfahren. Als grober Anhaltspunkt fur numerische Rechnungen sei die Forderung e < 2 genannt. Wie beim Eliminationsverfahren hat man auch beim R u n g e schen Verfahren die bequeme Kontrolle fiir die Summen aller Koeffizienten und rechten Seiten einer Zeile.

2) 0. R u n g e H. K i j u i g : Numerisohes Rechnen, Berlin 1924, S. 18i.

Z. angew. Math. Mech. 3 60 C o 11 a t z . Fehlerabschatzung fiir das Iterationsverfahren Bd. 32 &re I; Drz. 1!)4’?

5. Fehlerabschatzung 3) . Es gilt dcr

S a t z: 1st bei einem linearen Gle i~ l iongssys t~~i~~

2 Q j k x k ;= rl (i = 1, 2, . . . , n )

k = l die Bedingung

I1

6,=:A1’laiki< J Q i i l k = l k = - i

fur alle i erfullt, so gilt fur die nach der Vorsclirift (4) des lter a t. ions- verfahrens in Einzelschritten 4, berechneten Naherungen die Fehler- ahschatzung

I X i ( Y t 1) - X i [ 5 @ . 8”’ , . . . . . . * . . (9). h .

Dabei ist e = Max -p2_-- uncl 8”) der Betrag der maximalen Anclerung

beim letzten Iterationsschritt B‘” = Max 1 xi(’ + I) - x,‘”’ 1 . i I a i i l - b i

i

B e w e i s : Es sei Z”’ der grohte Betrag der n Fehler

-XI, t f ‘ V ) = q ( V ’

also P” =Max I F ~ ” ) 1 .

Fur den Feliler gilt nacli (4) i - - 1

‘ I + @

ein, so ist nacii Voraussetzung Fiihrt man nun die Bbkurzung p =

bi I l c l c i l mit ,u < 1 und es gilt weiterhin

denn fur i = 1 liest nian 1 ElrV+ ,u Z‘” unniittelbar nus (10) ab, da dann die erste Summe leer ist, und fur die weiteren i kann man rechts bei der ersten Sumine / e ~ c ( ~ f ~ ) ( 5 ,u ZCY’ < ZCv’ einsetzen und erkennt so (11) fur alle i als gultig. Nun sollte Z ‘ v + l ) das Maximum der n Zahlen I & i ‘ Y + i ’ ( scin, mufi also unter diesen Zahlen vorkommen, d. 11. es gilt

1 &[‘Y 1 1 ’ I 5 / A . Z‘”’ . . * . . . . . . , . . . (11),

und daniit

Das ist di? bekannte Konvergenzaussage P” + O fur Y + a. der beim Ihcrgang von der 1’- ten zur (v + 1). ten Naherung aufgetretenen Anglerungen

Nun sei d‘v’ der grfihte Betruq

S ‘ Y ’ = Max I s i ( Y C 1) .- xi(”) 1 = Max j p i t y 4- 1 ) - F i ( ” ) 1 , i i

und es sei xo diejenige Unbekannte, fur die I ~ i ‘ ” ) 1 den Maximalwert P’) annimmt: IF^(^)^ = ZCv’. Fur dieses ts gilt:

f i (VI > = I ( V t - F6‘’ + 1 2 \&,‘” 1 - 1 pG(’ + I’ 1 2 Ziv’ - Z‘’ + ”

Damit ist

bewiesen. 3) Bei R. v. M i s c s - H . P o l l a c z e k - U e i r i a g ~ r : Z. augew. Math. Mech. Ud. !I (ILJZY), S . 0% findet sich eine

Fehlerahschatznng, allerdiugs nur Piir das Iterationsverfahren i n Gesaultschrilten und zudetn bei Erfiilltscin dcs Spalteti- summenkriteriums. Dieses hat gegeniiber dem hier zugrundegelegten Zeilensu~i~riienkritoriiini die Nachteile. daW man ziir nnmerischen Anwendung erst die Zeilen durch die Hauptdiagonalelemente durchdividieren mill3 und daW man einc Aussage iiber die Summe der Fehlerbetrage und nieht direkt iiher den Maxirnallehler erhalt (hochstens durch die grohc Abschatzung: Maxirnallehler s Summe der FehlerbetrPge).

4, Wie man Ieicht heweist, bleibt der Bats richtig, wexin man ,,Vorschrift (4)“ iind ,,Einzelsi.hritte“ durch , ,V(IY. schrift (3)” urid ,,Gesamtschritte“ ersetat.

Kleine Mitteilungen 36 1

Zur Untersuchung der Gute der Fehlerabschatzung werde folgendes einfaclie Beispiel betrachtet, bei dem sich zeigt, dab die Fehlerscliranke (9) und der tatsachliche Maximalfehler sich beliebig nahe kommen konnen.

Z. aagew. Math. Mech. Bd. 23 Nr. 6 Dez. 194'2

Geht man bei dem Gleichungssystem

(1 + e> xi + .o 2, =0 x , = - I

aus yon xl'O'=O, x,(O)=O, so erhalt man bei einem Iterationschritt

Die exakte Losung lautet

. , xl(l) -- 0 , x,"' = - 1.

B der Maximalfehler betragt mithin _- . I+@

Der Parameter p stimmt mit dem in (8) eingefuhrten Q uberein, man erhalt daher mit 6 = 1 die Fehlerschranke e 6 = Q, die sich fur e + 0 prozentual uin beliebig wenig von dem Maximalfeliler unterscheidet. 417

KLEINE MITTEILUNGEN Zur Konrergenr der Newtonrchen Ver-

fshrenr fUr aleichungssysteme. (Ans dem Institut fur angewandte Mathematik und Darstel- lende Geometric der Technischen Hochschulc Hraunschweig.) In einer Dissertation l), die Wvegen des Krieges nicht gedruckt werden konnte, hat Herr K a r l €3 u s s m a n n eine Reihe von Satzen und Fehlerabschatzungen gezeigt, durch die einigc Satze von A. O s t r o w s k i 2 ) und F i . A. W i l - l r! r s 3, wcsentlich verallgemeinert werden. Von ihnen seien die wichtigsten in c,twas andcrcr For- inulirrung ohne Beweis hier mitgeteilt.

%ti losen sei das Gleichungssystem

gx (Xi, 22, . . . ,2?J = 0 , x = 1,2, . . ., 7 1 ,

Die gx seien Funktionen des Vektors g = (xl, . . e 7 xtt) und sollen stetige partielle Ableitungen bis zur 2. Ordnung besitzen. Es sei g der Vektor rnit den Koordinaten g, , y,, . . . g)L. Zur Abkiirzung werde gesetzt :

Adjunkten von a: G x l , Determinante von 8 - G , g, , 8 T g t , = 8; '7 G (xy)

Das N e w t o n sche Verfahren besteht in der folgenden Iteration: Man geht von einer Naherung g y (v = 0,1,2,. . .) der gesuchten Stelle g aus, rechnet sich den Vektor 0. mit den Koordinaten gx (gy) aus unrl gewinnt durch lineare Transformation dieses Vektors einen neuen Vektor gy + *, namlich

g (g,,) Gv.

x v + i = &Y + Kv g v .

Dabei ist gy die a n der Stelle gy genonimene Matrix - = - @;', also

I gY+l=gy-@; lgY I. 1) Eingereicht bei der Technischen Hochschule Braun-

schweig 1940. 2) A. O s t r o w s k i : Konvergenzdiskussion und Fehler-

ahschatzung fur die Newtonsohe Methode hei Gleiohungs- systemen. Commeiitnrii Mathematici, Helvetioi, Bd. 9 (1937J%3), S. 'i9 bis 103.

3, Fr. A. W i l l e r s : Zur Bonvergenz des Newtonschen Naherung3verPahrens. Z. angow. Math. Meoh., Bd. 18 (19%). S. 1 9 i bis 300.

B e z e i e h n u n g e n : 1. a sei eine Liisungsstelle des Gleichungssystems g (g) = D.

2. Die Koordinatenbetrlge des Vektors g. - a , also die Zahlen 1 T U X - a x 1 , heil3en d i e n A b - w e i c h u n g e n d e r N a h e r u n g gY.

3. Die gr6Bte dieser n Abweichungen nennen wir den M a x i m a l f e h l e r BY d e r N a l i e r u n g gV.

4. Die Koordinatenbetrage des Vektors gy+ , - g v , alsodieZal i lenI~,+, ,x--r , . l , 1ieiBen d i e n K o r - r e k t u r e n d e r N l h e r u n g gW.

5. Die gro5te dieser n Korrekturen nennen wir die M a x i m a l k o r r e k t u r d~ d e r N l h e r u n g g , , .

6. Einen abgeschlossenen achsenparallelen Wiirfel mit dem Mittelpunkt g,, [v=0, 1,2, , . .] und der Spannweite (d. h. KantenlBnge) s bezeiclinen wir durch clas Symbol W [gY, s].

7. In einem vorgegebenen abgeschlossenen Ge- biet bezeichnen wir eine obere Schranke fur eine Funktion I g(g) j mit ?, eine untere mit IS; eine obere Schranke fur die Werte d e r n Funktionen IgJ, . . ., 1 g, 1 b e z a h n e n wir mit gxl usw.

S a t z 1 (Ein KonvergenFkriterium). Es sei schon bekannt, dab im Wurfel W [go, s]

wenigstens eine Losung a liege. Im Wurfel W [x,, 2 s \ schatzen wir 1 GI und samtliche 1 g w , x l , /g i , ,np I , a b und berechnen aus den auftretenden Schrariken eine dem Wiirfel W [go, s] zuzuordnende K e n n - z a h l a.

Zeigt sich nun, daB die Spannweite

s < a , . so gilt zweierlei:

I. a ist die e i n z i g e Losung in W [go, s]. 11. Die zu go gehorende N e w t o n sche Folge kon.

Zur Ermittlung von a werden in W [go, 2s] be- vergiert gegen a.

stimmt e, gl,n', g z k ' . Dann wird

n z n ! g,,nln-l Sx,p ' 4.e '

a = -

S a t z 2 (Konvergenz bei genugender Approxi- mation).

Wir betrachten eine Wurfelfolge Wv '= W [gY,s,J v=O,1,2,. . ., fur die 1. so >s, >s, > ..., 2. s,+0, 3. W18+, ganz in Wv, 4. a in jedem Wv. Dann