4.5 Gradientenverfahren



next up previous contents
Next: 4.5.1 Die Methode des Up: 4 Lösung des Gleichungssystems Previous: 4.4.3 Rechenaufwand

4.5 Gradientenverfahren

Die Methode der konjugierten Gradienten ist die populärste iterative Methode, um Systeme von linearen Gleichungen zu lösen. Das Verfahren benötigt als Ausgangspunkt eine Matrix , die positiv definit und symmetrisch ist. Ist die Matrix stark besetzt, so sollte man besser auf eine Faktorisierung der Matrix ausweichen.

Der Hauptvorteil der meisten iterativen Methoden liegt in der effizienten Nutzung des Hauptspeichers. Die Koeffizientenmatrix bleibt während der Iteration unverändert. Dadurch muß auch kein zusätzlicher Speicherplatzgif alloziert werden.

Grundidee der Gradientenverfahren ist, die quadratische Form

 

zu minimieren. Diese Form besitzt unter der Voraussetzung, daß positiv definit ist, ein Minimum. Die Werte des Lösungsvektors für ein minimales kann man durch

berechnen. Die partiellen Ableitungen der quadratischen Form können in Komponentenschreibweise

mit

berechnet werden.

Kehrt man zu der Matrixschreibweise

zurück und berücksichtigt die gegebene Symmetrie des Gleichungssystems, so reduziert sich die Lösung des Minimierungsproblems auf

Das Ergebnis

ist also gleich dem zu lösenden Gleichungssystem.





Martin Stiftinger
Fri Nov 25 16:50:24 MET 1994