Iterative Verfahren

Direkte Verfahren, iterative Verfahren

Im Unterschied zu den direkten Verfahren (Gauß, verketteter Algorithmus, Gauß-Jordan, Cholesky, ...), die die Lösung des linearen Gleichungssystems

mit einer festen Anzahl von Operationen erzeugen, arbeiten die iterativen Verfahren nach folgender Strategie: Beginnend mit einem Startvektor x₀, wird eine Folge von iterierten Vektoren x₁, x₂, x₃, ... mit dem Ziel erzeugt, dass diese sich immer mehr dem tatsächlichen Lösungsvektor des Gleichungssystems annähern. Der Iterationsprozess wird abgebrochen, wenn ein iterierter Vektor x_i das Gleichungssystem in einem zu definierenden Sinne ausreichend gut erfüllt. Man kann z. B. fordern, dass die Norm des Restvektors

ein vorzugebendes Limit nicht überschreitet.

Iterationsverfahren

Die Anzahl der Iterationsverfahren und ihrer zahlreichen Modifikationen ist kaum mehr zu überblicken (die Stichworte dazu lauten u. a. "Fixpunkt-Iteration", "Jacobi-Iteration", "Gauß-Seidel", "Splitting-Methoden", "Relaxationsverfahren", "Krylov-Unterraum-Verfahren", "Methode des steilsten Abstiegs", "Verfahren der konjugierten Richtungen", "Verfahren der konjugierten Gradienten", "Mehrgitterverfahren", ...):

• Eine umfangreiche Zusammenstellung findet man z. B. bei "Y. Saad: Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003" (die 1996 erschienene erste Auflage ist als PDF-Datei im Internet zu finden).
   
• Eine ausführliche deutschsprachige Darstellung findet man in dem Buch von "A. Meister: Numerik linearer Gleichungssysteme (2. Auflage, Vieweg-Verlag 2005)". Die im Anhang dieses Buchs angegebenen Matlab-Scripts zu einigen iterativen Verfahren stehen zum Download bereit.
   

Als typischer Vertreter dieser Klasse von Lösungsverfahren wird hier speziell die "Methode der konjugierten Gradienten" vorgestellt, deren Anwendbarkeit zwar auf symmetrische und positiv definite Koeffizientenmatrizen beschränkt ist, genau deshalb aber ist sie für Probleme der Technischen Mechanik von besonderer Bedeutung.

Wegweiser zum Thema "Iterative Verfahren"

• Testrechnungen mit Gleichungssystemen unterschiedlicher Größe mit insgesamt 10 verschiedenen Iterationsverfahren:



• Testrechnungen mit iterativen Verfahren (1)
• Testrechnungen mit iterativen Verfahren (2)
   
• Die Methode der konjugierten Gradienten:



• Minimalproblem und lineares Gleichungssystem
• Methode der konjugierten Gradienten
• Einfaches Beispiel für die Methode der konjugierten Gradienten
• Präkonditioniertes Konjugierte-Gradienten-Verfahren
• Matlab-Script PKG.m
• Testrechnungen mit präkonditioniertem Konjugierte-Gradienten-Verfahren
• Matlab: Probleme mit singulären Matrizen
   
• Präkonditionierung für iterative Verfahren



• Präkonditionierung (allgemein)
• Präkonditioniertes Konjugierte-Gradienten-Verfahren
• Testrechnungen mit präkonditioniertem Konjugierte-Gradienten-Verfahren
• Testrechnungen mit Präkonditionierung mit Matlab
• Test: Präkonditionierung mit "Incomplete Cholesky"
• Beispiel: System mit schlecht konditionierter Matrix
• Beispiel: Skalierung einer symmetrischen Matrix