Analytische Betrachtung der systematischen Iterationsmethoden

 

Die numerische Lösung partieller Differentialgleichungen durch finite Approximationen führt auf das mathematische Gebiet der linearen Algebra. In den vorausgegangenen Abschnitten dieses Kapitels haben wir einige Möglichkeiten zur Lösung der anfallenden linearen Gleichungssysteme skizziert. Zur Beurteilung der Verfahren genügen manchmal bereits geringe, grundlegende Kenntnisse der linearen Algebra. Wir werden uns in diesem Abschnitt eingehender mit den Konvergenzeigenschaften der iterativen Lösungsverfahren beschäftigen, ohne den dazugehörigen mathematischen Aufwand allzu groß werden zu lassen.

Man betrachte $n$ lineare algebraische Gleichungen

bzw.

(5.36)

die alle mit den Koeffizienten der Hauptdiagonalen normiert wurden. Wir wollen annehmen, daß der Wert der Koeffizientendeterminante von verschieden von Null sei, daß also ^-1 existiert. Nach der Normierung verfügt die Matrix auf der Hauptdiagonalen nur noch über Elemente vom Wert eins. Daher kann man anstelle von (5.36) auch

(5.37)

schreiben, wobei

und die Einheitsmatrix der Ordnung $n$ ist. Eine Auflösung von (5.37) nach dem unbekannten Vektor $$u ist durch die Zerlegung besonders einfach

Die Jacobische Iterationsmethode ist somit durch

(5.38)

definiert. Für das Punkt-Gauß-Seidel-Verfahren notiert man

(5.39)

wofür auch

bzw.

(5.40)

geschrieben werden kann.

Die Matrizen nennt man die der Abbildungsvorschrift zugeordneten Iterationsmatrizen `' von Jacobi bzw. Gauß-Seidel. Wenn $$u die gesuchte Lösung der Beziehung (5.38) bzw. (5.39)

(5.41)

ist (man sagt auch $$u ist Fixpunkt der Gleichung (5.41)), und $$e^(k) der Fehler der Näherungslösung des $k$-ten Iterationsschrittes

so schreibt man anstelle von (5.41)

bzw.

Man kann somit die Auswirkungen eines zu Iterationsbeginn induzierten Fehlers

(5.42)

a priori angeben.

Für die sukzessiven Relaxationsverfahren lautet die Iterationsvorschrift

woraus man

(5.43)

also

(5.44)

gewinnt.

Analog zum Abschnit 3.2.2 versuchen wir den Fehlervektor $$e als Linearkombination von Eigenvektoren der Iterationsmatrix auszudrücken. Vorausgesetzt habe $n$ linear unabhängige Eigenvektoren $$v_s zu den $n$-ten verschiedenen Eigenwerten $$_s, so kann man die $n$ Komponenten des Anfangsfehlers e⁽⁰⁾ als Linearkombination der Eigenvektoren in der Form

auszudrücken. Wir zitieren nun noch Gleichung (3.19) und erhalten den bekannten Zusammenhang

(5.45)

Für die Konvergenz des Iterationsverfahrens ist es notwendig und hinreichend, daß sämtliche Eigenwerte $$_s betragsmäßig kleiner Eins sind, woraus folgt, daß $$e^(k) mit wachsendem $k$ gegen Null strebt. Im Konvergenzfall bestimmt der betragsmäßig größte Eigenwert, den man als Spektralradius `rho' von bezeichnet, die asymptotische Abnahme des Fehlervektors $$e.

Wir wollen nun versuchen den größten Eigenwert der Matrix (5.44)

zu bestimmen, um diesen dann durch geschickte Wahl von $$ zu minimieren. Hierfür notieren wir das Eigenwertproblem

und schließlich für 2 zyklische Matrizen von konsistenter Ordnung

(5.46)

Vergleicht man die Eigenwertaufgabe (5.46) mit derjenigen des Jacobischen Gesamtschrittverfahrens

so läßt sich jedem Eigenwert $$ der sukzessiven Relaxationsmethode ein entsprechender Eigenwert $$ des Gesamtschrittverfahrens zuordnen:

(5.47)

In einer veränderten Fassung läßt sich (5.47) als Schnittpunkt zweier Graphen $f$ und $g$ darstellen

 

Abbildung 45: Geometrische Interpretation der Beziehung (5.47

Im Spezialfall des Gauß-Seidelschen Verfahrens mit $$= 1 reduziert sich die Relation (5.47) auf

Die Steigung der Geraden $f$ wird durch den reziproken Wert des Relaxationsfaktors bestimmt. Die Schnittpunkte sind definiert durch die Nullstellen der quadratischen Gleichung

also durch

(5.48)

Mit wachsendem Relaxationsfaktor wandern $A$ und $B$ wegen ihres stetig kleiner werdenden Abszissenunterschiedes aufeinander zu. Die beiden Schnittpunkte vereinigen sich im Berührungspunkt, wenn die Diskriminante

verschwindet, so daß wir für den Punkt C

(5.49)

(5.50)

erhalten.

Unser Ziel war es, den größten Eigenwert der Iterationsmatrix (5.43) in Abhängigkeit von $$ zu minimieren. Bereits aus Abbildung 45 wird ersichtlich, daß der Fall zweier verschiedener reeller Wurzeln $$ (5.48) hierfür nicht von Interesse sein kann, da eine der beiden stets größer als $($- 1) ist. Gleiches gilt auch für die konjugiert komplexen Wurzeln

(5.51)

welche in die (5.50) ähnliche Beziehung

$|$| = - 1

münden. Im Unterschied zu (5.50) sind für das Zustandekommen komplexer Wurzeln jedoch größere Relaxationsfaktoren $$ notwendig, so daß wir uns auf die Untersuchung von (5.49) beschränken können.

(5.52)

Da der Spektralradius für konvergente Iterationsabläufe stets kleiner als eins sein muß, fordern wir

$0$< || < 1 .

Deutlich erkennt man, daß die Verwendung des Minuszeichens in (5.49) auf Relaxationsfaktoren $2$ führt, wohingegen die von uns gesuchte Lösung

lautet, welche auf reele Eigenwerte

= - 1 < 1

führt.

Von entscheidener Bedeutung zur Bestimmung eines optimalen Relaxationsfaktors ist also die Kenntnis des Spektralradius der Jacobischen Iterationsmatrix $$. Zur Abschätzung des Spektralradius, einer quadratischen Matrix benutzt man häufig den Satz von Gerschgorin. Hiernach kann der Betrag des größten Eigenwertes der quadratischen Matrix die größte Summe der Beträge der Elemente einer Zeile oder Spalte nicht überschreiten.

Beweis: Aus dem Eigenwertproblem

$$ v = v

folgt nach Division aller Gleichungen durch die größte Komponente $v$_s des Eigenvektors für die $i$-te Zeile

und da immer < $1$ ist, gilt deshalb

(5.53)

Da die Eigenwerte von ^T immer die selben wie die von sind, ist der Satz auch für Spalten richtig.

Ein anderer gangbarer Weg zur Bestimmung von $$ ist die Durchführung von Anfangsiterationen mit einem Startwert $$= 1, woraus sich anschließend eine Näherung des Jacobischen Spektralradius $$ ermitteln läßt. Diese Näherung setzt man in die Beziehung (5.52)

ein, und führt die Iteration mit dem so gewonnenen neuen Relaxationsfaktor fort. Die oben angesprochene Näherung von $$ ergibt sich ganz einfach aus der relativen Änderung der Iterationsdifferenzen

(5.54)

wobei man als Vektornorm für gewöhnlich die euklidische Norm verwendet.

Beweis: Entwickelt man den Anfangsfehler $$d⁽⁰⁾ aus den Eigenvektoren der Iterationsmatrix des Gauß-Seidel- Verfahrens,

und weiter

wobei $|$_i| der Spektralradius der Iterationsmatrix sei, dann geht $d(m)$ für große Werte von $m$ gegen . Deshalb geht