Sie sind hier: Numerik > Lösung linearer Gleichungssysteme

Lösung linearer Gleichungssysteme

Samstag 02. Dezember 2006 von
Simon Praetorius
Es gibt eine Reihe von Methoden, um ein lineares Gleichungssystem zu lösen. Angefangen von den in der Schule gelernten Verfahren mittels Auflösen nach einer Variable und Einsetzen in die Gleichungen. Ein sehr bekannter Algorithmus ist der Gaußsche Eliminationsalgorithmus, der heute in vielen Formen in der Informatik implementiert wird. Ich möchte hier einige der Verfahren vorstellen und eventuell Vor- und Nachteile aufzeigen.
Der Standard Gaußalgorithmus hat einige Nachteile, z.B. dass er bei einem ungünstig strukturierten Gleichungssystem (Gls) nicht zum Ziel führen kann (etwa, wenn in der Hauptdiagonalen Null-Elemente vorkommen). Ein erster Ansatz zur Lösung dieses Problems ist die Pivotisierung, d.h. der Algorithmen vertauscht die Zeilen (Spalten) so, dass ein Pivotelement (ein aus der Matrix ausgewähltes Element mit gewissen Eigenschaften) an der derzeit zu untersuchenden Hauptdiagonal-Stelle steht.

Das Gauß-Verfahren hat außerdem den Nachteil, dass es mit recht hohem Aufwand durchgeführt werden muss. Diesen kann man etwas reduzieren, etwa durch eine LU-Zerlegung (LR-Zerlegung) oder eine Cholesky-Zerlegung. Nähere Informationen dazu findet man auf der jeweiligen Unterseite.

Es gibt auch einige Verfahren, die nicht exakt arbeiten, sondern iterativ eine Näherung für die Lösung des Gleichungssystems finden. Da gibt es z.B. die Splittingverfahren. Damit habe ich mich in einem Seminar etwas näher beschäftigt und will euch da auch etwas teilhaben lassen.
Besucher: 18630 | Permalink | Kategorie: Numerik
Tags: , ,

Einfacher Gauß-Algorithmus

Um ein System linearer Gleichungen zu lösen, lernt man in der Schule meist als erstes die eine Gleichung nach einer Variablen aufzulösen und dann in die anderen Gleichungen einzusetzen. Somit eliminiert man eine Variable aus allen anderen Gleichungen. Wenn man das mit den anderen Variablen auch macht, ...
weiter lesen...

Gauß-Algorithmus mit Pivotisierung

Algorithmus wie beim einfachen Gauß-Algorithmus. Um numerische Fehler und Divisionen durch 0 möglichst zu vermeiden wird eine Pivotisierung angewandt (Wikipedia, Uni-Bielefeld). Im standard Gauß-Algorithmus wurde in jedem Schritt durch ein Element auf der Hauptdiagonalen der Matrix dividiert. Ist ...
weiter lesen...

LU-Faktorisierung

Man zerlege die Koeffizientenmatrix A in zwei Dreiecksmatrizen L und U, wobei L eine untere und U eine obere Dreiecksmatrix darstellt, so dass gilt: $A = L⋅U$ und L auf der Hauptdiagonalen nur Einsen stehen hat. Dann kann in zwei Schritten das Gleichungssystem $Ax=b$ gelöst werden. zuerst bestimmt ...
weiter lesen...

Splitting-Verfahren zur Lösung von LGS

Splitting-Verfahren zu Lösung linearer Gleichungssysteme sind eine Klasse iterativer Verfahren, die in den letzten Jahren stark an Bedeutung verloren haben, da z.B. die Konvergenzeigenschaften mit anderen Verfahren viel besser sind, trotzdem dienen sie noch als Vorkonditionierer oder z.B. in einem modifizierten Newtonverfahren zur Bestimmung der Lösung einer nichtlinearen Gleichung.
weiter lesen...

Kommentar hinzufügen

Dieses Feld bitten nicht ausfüllen: