| | |
| Title: | Das Gaußsche Eliminationsverfahren | |
| Home deutsch | ||
| ||
| |<< First < Previous Index Next > Last >>| | |  |
4. Gauß-Seidel-Verfahren
a11x1 + a12x2 +...+ a1nxn = b1
Dieses Verfahren weist keine Gemeinsamkeit mit den beiden vorherigen auf.
Dieses Verfahren enthält in seinem Namen den Namen Gauß deshalb, weil bereits Carl Friedrich Gauß dieses Verfahren anwendet. Allerdings veröffentlichte er dieses Verfahren nicht.
Viele Jahre stieß der Mathematiker Phillip L. von Seidel erneut auf diesen Algorithmus, deshalb Gauß-Seidel-Verfahren.
Das Gauß-Seidel-Verfahren ist ein iteratives Verfahren, d.h. die Lösung des Gleichungssystems wird durch Iterationen genähert.
Gegeben sei wieder folgendes Gleichungssystem:
a21x1 + a22x2 +...+ a2nxn = b2
..............................
an1x1 + an2x2 +...+ annxn = bn
Man löst nun nach xi für i=1..n auf:
x1 = (b1 - a12x2 -...- anxn):a11
x2 = ...
................................
xn = ...
Nun wählt man sich für xi mit i=1..n einen Startwert. Erstaunlicherweise ist dieser Startwert beliebig, da in den folgenden Iterationen die xis gegen die Lösung konvergieren. Einfachhalber wählt man für alle xi Null als Startwert:
x1 = 0
Im zweiten Durchgang berechnet man nun ein neues x1 mit den vorherigen anderen xis:
5. Probleme mit den Algorithmen
x2 = 0
......
xn = 0
Darauf werden die übrigen x'is jeweils mit den vorherigen Lösungen berechnet. Führt man diesen Prozeß weiter, so hat man nach genügend Durchläufen brauchbare Lösungen.
Es kann jedoch passieren, daß der Prozeß nicht konvergiert, sondern divergiert. Man kann dies manchmal umgehen, indem man wieder die oben besprochene partielle Pivotierung anwendet.
Meistens divergiert der Iterationsprozeß mit Pivotieren aber trotzdem. Eine Konvergenz tritt nämlich nur dann ein, wenn die Koeffizienten in der Hauptdiagolen (Pivotelemente) gegenüber den anderen Koeffizienten vom Betrag stark überwiegen. Die Zahl der Gleichungsysteme, die für das Gauß-Seidel-Verfahren geeignet sind, sinkt damit natürlich erheblich.
Man muß vor Anwendung dieses Verfahren nach dem Pivotieren also immer überprüfen, ob alle Pivotelemente aii mit i=1..n vom Betrag her größer als die Summe der aij j=1..n sind. Nur dann nämlich kann man eine schnelle Konvergenz garantieren. Eine Konvergenz könnte aber trotzdem eintreten, die dann aber so langsam wäre, daß ein anderes Verfahren die Lösung schneller finden würde.
Weiterhin hat es sich als günstig erwiesen, die Schrittweite zu halbieren, wenn sich das neue xi vom vorherigen x'i im Vorzeichen unterscheidet:
Ferner sollte man sich noch überlegen, wann die Iterierung abgebrochen werden soll. Dies hängt von der gewünschten Genauigkeit der Lösung ab. Man kann den Iterationsprozeß für beendet erklären, wenn sich xi vom vorherigen x'i nur noch um eine Toleranzgröße unterscheidet. Allerdings kann man den Rechenprozeß auch erst dann stoppen, wenn xi mit dem vorherigen x'i übereinstimmt, die Toleranz Null ist.
Das Gauß-Seidel-Verfahren eignet sich vor allem für sehr große Matrizen. Vorteilhaft ist zudem, daß die Näherung immer nur von der vorherigen abhängt, d.h. Rundungsfehler können sich nicht anhäufen.
Außerdem eignet sich das Gauß-Seidel-Verfahren auch zur Lösung nicht linearer Gleichungen.
Grundsätzlich arbeiten die oben beschriebenen Algorithmen nur mit nicht singulären Gleichungssystemen. Wendet man einen der Algorithmen auf ein singuläres Gleichungssystem an, so stößt man dann meist auf eine Nulldivision. Dies ist dann der Hinweis dafür, daß keine eindeutige Lösung existiert.
Probleme kann es mit Gleichungssystemen geben, deren Determinanten fast Null sind. Aufgrund von Rundungsfehlern stößt man dann vielleicht auf eine Division durch Null und schließt daraus, daß für dieses Gleichungssystem keine Lösung existiert. Tatsächlich existiert aber doch eine Lösung.
Ein weiteres Problem ist es, wenn in einem Gleichungssystem eine Gleichung eine komplizierte Linearkombination aus anderen Gleichungen dieses Gleichungssystems ist. Derartige Linearkombinationen sind schwer zu finden. Man könnte also eine Lösung erhalten, die aber nicht eindeutig ist.
Glücklicherweise stehen einem aber mehrere Lösungsverfahren zur Verfügung. Man sollte deshalb ein Gleichungssystem generell mehreren Verfahren unterziehen. Errechnen nun verschiedene Verfahren unterschiedliche Lösungen, so ist dies ein Hinweis darauf, daß keine eindeutige Lösung existiert.
Zusätzlich ist es ratsam, die lineare Unabhängigkeit von Gleichungen innerhalb eines Gleichungssystems mit Hilfe der Determinante zu überprüfen. Besonders bei großen Gleichungssystemen ist dies aber oft sehr aufwendig.
Speziell beim Gauß-Seidel-Verfahren hat man das Problem, daß dieser Algorithmus nur in sehr begrenztem Maße einsetzbar ist, da nur wenige Gleichungssysteme für dieses Verfahren geeignet sind.
|
|
|
Mathematik für Informatiker. Zahlen, Analysis, Elemente der Wahrscheinlichkeitstheorie, Lineare Algebra von Gerhard Berendt | |
| Sonstige Artikel: | |
| Jugend im Nationalsozialismus: Zwischen Faszination und Widerstand | |
| Severin WK 3361 Wasserkocher, blau / 1,0 Liter Inhalt / 1000 W von Severin | |
| KINDER PARTY KARNEVAL - 21 Kinderlieder für Fasching, Karneval und Verkleidungspartys | |
Back to the topic site:
StudyPaper.com/Startseite/Wissenschaft/Naturwissenschaften/Mathematik
External Links to this site are permitted without prior consent.
