Einfaches Beispiel für die Methode der konjugierten Gradienten

KGTest1MatlabDer hier beschriebene Algorithmus der Methode der konjugierten Gradienten ist genau in dieser Form im Matlab-Script KonjugGrad.m realisiert, das im Anhang des Buchs "A. Meister: Numerik linearer Gleichungssysteme" gelistet und über den Link http://www.mathematik.uni-kassel.de/~meister/buch_online zum Download verfügbar ist. Das nebenstehend zu sehende kleine Testprogramm KGTest1.m löst das Gleichungssystem

Bsp1KG

mit  n = 6 Gleichungen mit diesem Script. Das nachfolgend zu sehende Command Window zeigt die Ausgabe bei Rechnung mit einem leicht modifizierten Script KonjugGrad.m, so dass für dieses einfache Beispiel alle iterierten Vektoren zu sehen sind. Die Iteration startet mit dem Nullvektor, und nach n = 6 Iterationen ist - wie es die Theorie verlangt - die Lösung des Gleichungssystem entstanden:

BspKG1CW

MatlabItVerfsMatlab bietet insgesamt 9 iterative Lösungsverfahren an. Das nebenstehend zu sehende Matlab-Script ItVerfTest1.m zeigt sie mit den Namen, die aus Matlab-Help entnommen wurden. Für die kleine Beispielrechnung liefern sie alle das bereits oben zu sehende Ergebnis.

Solche kleinen Probleme sind allerdings nicht die typischen Anwendungsfälle für die iterativen Verfahren (und sollten auch besser mit direkten Verfahren gelöst werden). Die iterativen Verfahren sind gedacht für sehr große Gleichungssysteme mit Koeffizientenmatrizen, die als "Sparse matrices" gespeichert sind.

Deshalb werden nachfolgend und auf der Seite "Testrechnungen für iterative Verfahren (2)" einige Rechnungen mit größeren Gleichungssystemen beschrieben.

Verfahrensvergleich am einfachen praktischen Beispiel

Für die Testrechnungen werden neben den 9 Matlab-Verfahren auch das weiter oben bereits verwendete Matlab-Script KonjugGrad.m verwendet. Es werden dafür FEM-Gleichungssysteme mit Matlab-Femset erzeugt (Zeilen 4 bis 6 in nachfolgendem Script ItVerfTest2.m), deren Koeffizientenmatrizen symmetrisch und positiv definit und dünn besetzt sind. Die Matrizen werden vor der Übergabe an die Lösungsalgorithmen zu "Sparse matrices" umgeformt (Zeile 8).

Die Gleichungssysteme werden zusätzlich mit dem Matlab-Standard-Solver (verwendet direkte Lösungsverfahren, Zeile 11) gelöst, um einen Vergleich mit der "exakten Lösung" zu ermöglichen.

ItVerf203

Zunächst wird ein ganz kleines Problem gelöst. Nachfolgend ist links der ebene biege- und dehnsteife Rahmen dargestellt (entnommen aus dem Kapitel "Verifizieren von Computerrechnungen"), dessen FEM-Modell in der Datei Rahm17.dat gespeichert ist. Diese wird im oben zu sehenden Script in Zeile 4 geladen, das daraus erzeugte Gleichungssystem mit 33 Gleichungen hat eine Koeffizientenmatrix mit nur 177 von Null verschiedenen Elementen (siehe nachfolgend rechts zu sehendes Muster, Ausgabe der spy-Function in Zeile 9).

EbRahm17EbRahm17SpyEs ist ein sehr kleines System, dessen Lösung mit beliebigen Verfahren unproblematisch sein sollte. Deshalb wurden im Matlab-Script auch alle Solver mit den Default-Werten für die Parameter aufgerufen.

Das Ergebnis ist eher enttäuschend: Kein iteratives Lösungsprogramm liefert eine brauchbare Lösung für dieses Mini-System ab. Der Grund dafür ist die viel zu optimistische Voreinstellung des Parameters "Maximale Anzahl auszuführender Iterationen". In KonjugGrad.m ist dieser Wert auf 30 eingestellt, in den von Matlab angebotenen Verfahren auf 20, in einigen sogar auf 10. Die Annahme, dass damit schon eine akzeptable Näherung der Lösung zu erreichen ist, wird durch dieses kleine Beispiel widerlegt, siehe folgenden Ausschnitt des Command Windows mit der Ergebnisausgabe:

EbRahm17CW103

Es wurden jeweils nur die letzten 12 Werte der insgesamt 33 Elemente umfassenden Lösungsvektoren ausgegeben. Die linke Spalte ist das (korrekte) Ergebnis, das der Matlab-Standard-Solver lieferte. Keines der 10 iterativen Verfahren, deren Ergebnisse in den Spalten 2 bis 11 stehen (darunter jeweils der Name der Function) kam auch nur in die Nähe dieser Werte.

Deshalb wird die Rechnung mit einem modifizierten Matlab-Script ItverfTest3.m wiederholt, in dem den Functions für die iterativen Verfahren jeweils 2 zusätzliche Parameter übergeben werden: Auf Position 3 steht der Toleranzwert (Norm des Restvektors bezogen auf die Norm des Vektors der rechten Seite), der als Maß für die Konvergenz gilt, 10-6 ist der Standardwert, mit dem die Functions auch dann arbeiten, wenn kein Wert übergeben wird. Der 4. Parameter gibt die Anzahl der maximal auszuführenden Iterationsschritte an. Der hier gewählte Wert 2·m (m ist die Anzahl der Gleichungen) sollte eigentlich mehr als ausreichend sein, man bedenke, dass z. B. die Methode der konjugierten Gradienten theoretisch schon nach m Schritten konvergiert:

ItVerf302

Nun sieht das Ergebnis (allerdings nur teilweise) besser aus. Deshalb wird nachfolgend die komplette Ausgabe aller Functions in das Command Window gezeigt:

EbRahm17CW205

Fazit dieser Rechnungen:

Warnung:

Bei Verwendung iterativer Verfahren zur Lösung linearer Gleichungssysteme ist Vorsicht geboten. Schon bei recht kleinen Systemen können falsche Ergebnisse abgeliefert werden. Man lese deshalb sehr sorgfältig die Hinweise (zur Konvergenz der Rechnung), die von den Lösungsverfahren ausgegeben werden. Da die iterativen Verfahren für sehr große Gleichungssysteme gedacht sind, besteht die Gefahr, dass diese Hinweise zum Beispiel bei der Berechnung mit Matlab im Command Window bereits veschwunden sind, wenn man sich nach der Berechnung den Ergebnisvektor ausgeben lässt!

Download

Die Matlab-Scripts auf dieser Seite und die von ihnen aufgerufenen Functions, DLLs und Dateien sind zum Download verfügbar: