---
Inhalt 4. Iterative Lösung linearer Gleichungssysteme

---
4.1 Gesamtschritt-, Einzelschritt-, und SOR-Verfahren


Vor.: Die Koeffizientenmatrix sei regulär und besitze Nicht-Nullelemente auf der Hauptdiagonalen, d. h.


Bem.: Die Eigenschaft kann auch durch geeignete Zeilenvertauschung erhalten werden.

Gleichungssystem:

(3.1)

Idee für die iterative Lösung von (3.1):

Umformung von (3.1) in eine Fixpunkt-Gleichung Erzeugung eines Iterationsverfahrens


Bestimmung der Fixpunkt-Gleichung:

Ansatz: mit : regulär und möglichst einfach invertierbar

Mit o.g. Ansatz folgt für (3.1)


Man erhält die Fixpunkt-Gleichung


(3.2)

Bem.: ist ,,Fixpunkt`` der Abbildung

Picard-Iteration:

Zur Lösung von (3.2) verwendet man die folgende Iteration


(3.3)

Konvergenzverhalten der iterierten Lösung:

Satz: Wenn die Folge konvergiert, dann ist der Grenzwert

gleich der gesuchten Lösung von (3.1).

Bem.: O.g. Satz beinhaltet eine Aussage über die gesuchte Lösung, nicht jedoch über das Konvergenzverhalten der Picard-Iteration

Satz: Die Picard-Iteration konvergiert global (beliebigem Startwert ) genau dann gegen die Lösung von (3.1), wenn für die Iterationsmatrix $\boldsymbol{M}$ gilt:


Eine hinreichende Bedingung für die Konvergenz ist außerdem gegeben durch


mit beliebiger, induzierter Matrixnorm .

Folgerung:

Ziel der Überlegungen soll ein Iterationsverfahren mit möglichst kleinem Spektralradius sein, d. h.
.

Begründung:

Mit dem Konvergenzmaß

und einer natürlichen Zahl gilt für folgende Abschätzung



Darin sind:  

je größer ist (kleiner ist), desto weniger Iterationen braucht man, um dieselbe Genauigkeit zu erzielen.

Konstruktion des Iterationsverfahrens:

Aufspaltung der Koeffizientenmatrix in eine Diagonalmatrix sowie eine (negative) linke Dreiecksmatrix und eine (negative) rechte Dreiecksmatrix :


Algorithmus 4.1 (Iteratives Verfahren):

Gesucht ist die Lösung des Gleichungssytems mit regulärer Matrix sowie . Die Aufspaltung mit regulärer Matrix liefert ein Iterationsverfahren ausgehend vom Startvektor :



Jacobi -Verfahren (Gesamtschrittverfahren)
 
 
Matrizen
 
Iteration
Konvergenz strikt oder irreduzibel diagonaldominant
 

Gauss - Seidel -Verfahren (Einzelschrittverfahren)
 
 
Matrizen
Iteration
Konvergenz strikt oder irreduzibel diagonaldominant oder
symmetrisch und positiv definit oder
M-Matrix
 

SOR-Verfahren (successive over relaxation)
 
 
Matrizen
Iteration
Konvergenz strikt oder irreduzibel diagonaldominant und oder
symmetrisch und positiv definit und oder
$ \boldsymbol{A}$ M-Matrix und
 

Konvergenzaussagen für spezielle Matrizen:

Definitionen: Eine Matrix heißt

  • reduzibel, wenn sie sich durch Umnummerierung von Zeilen ( ) und gleiche Umnummerierung von Spalten ( ) folgendermaßen transformieren läßt:


    mit , : quadratische Matrizen.
  • irreduzibel, sonst.
  • diagonaldominant, wenn > 
für <IMG
 WIDTH=, Betrag des Diagonalelements größer ist als die Summe der Beträge der restlichen Einträge .
  • irreduzibel diagonaldominant, wenn irreduzibel und diagonaldominant ist und für mindestens ein das ,,``-Zeichen gilt.
  • strikt diagonaldominant, wenn für alle das ,,``-Zeichen gilt.
  • L-Matrix, wenn für und .
  • M-Matrix, wenn nur nicht-negative Elemente besitzt und für und .
  • Stieltjes-Matrix, wenn eine symmetrische M-Matrix ist. ist dann positiv definit.


---
next 4.2 Das cg-Verfahren und seine Varianten 100 online
previous 3.4 GAUSSsche Ausgleichsrechnung


Inhalt 4. Iterative Lösung linearer Gleichungssysteme