|
1. Einführung
Diese Facharbeit behandelt drei Verfahren zur Lösung linearer Gleichungssysteme. Im ersten werden zunächst die theoretischen Grundlagen der Verfahren dargelegt, im zweiten Teil folgt dann die Umsetzung der Verfahren in Computerprogramme.
Zunächst soll allerdings zuerst einmal der Aufbau der linearen Gleichungssysteme erklärt werden.
1.1 Aufbau einer linearen Gleichung
Lineare Gleichungssysteme sind ihrerseits aus linearen Gleichungen aufgebaut.
Lineare Gleichungen bestehen aus Summen von Termen wie:
ax + by + cz = d
a,b,c und d sind Konstanten, x, y und z dagegen Variablen in dieser Gleichung. Der auf der rechten Seite stehende Teil der Gleichung wird als Freiglied bezeichnet.
Ein Term ist eine Multiplikation von einer Konstanten einer Variable, wobei diese nur in der ersten Potenz auftreten darf.
1.2 Lineare Gleichungssysteme
Faßt man mehrere lineare Gleichungen zusammen, so erhält man ein lineares Gleichungssystem:
a11x1 + a12x2 +...+ a1nxn = b1
a21x1 + a22x2 +...+ a2nxn = b2
..............................
an1x1 + an2x2 +...+ annxn = bn
Die aij mit i,j=1..n sind Konstanten und xi mit i=1..n Variablen. bi mit i=1..n stellen die Freiglieder dar.
Obiges Gleichungssystem ist außerdem noch ein Spezialfall, da die Anzahl der Unbekannten der Anzahl der Gleichungen entspricht. Für diesen Spezialfall sind eindeutige Lösungen möglich. Um diese Lösungen zu finden, bedient man sich verschiedener Lösungsverfahren, z.B. Cramer\'sche Regel, Gaußsches Eliminationsverfahren.
Letzteres soll später genauer untersucht werden.
1.3 Lineare Gleichungssysteme als Matrizen
Man kann das gerade vorgestellte Gleichungssystem auch noch auf eine andere Weise darstellen:
|¯a11 a12 ... a1n¯| |¯x1¯| |¯b1¯|
| a21 a22 ... a2n | | x2 | | b2 |
| a31 a32 ... a3n | | x3 | = | b3 |
| ............... | | .. | | .. |
|_an1 an2 ... ann_| |_xn_| |_bn_|
noch kürzer:
Ax = b
A repräsentiert die Koeffizientenmatrix, x die Unbekannten und b die Freiglieder des Gleichungssystems.
Bei Matrizen sind drei Umformungen erlaubt, ohne daß sich das Ergebnis der Matrix ändert:
1. Vertauschen von Zeilen
2. Ersetzen von einer Zeile durch eine Linearkombination aus dieser Zeile und einer anderen.
3. Vertauschen von Spalten
2. Gaußsches Eliminationsverfahren
Carl Friedrich Gauß war einer der größten Mathematiker überhaupt. Neben seinen großen Entdeckungen, wie z.B. der Gauß\'schen Normalverteilung, der Gauß\'schen Fehlerfunktion oder der Gauß\'schen Zahlenebene, wird das Gauß\'sche Eliminationsverfahren oft übersehen.
Der Gaußsche Eliminationsalgorithmus gehört zu den wichtigsten numerischen Verfahren der Mathematik. Er ist bereits 150 Jahre alt und hat sich in dieser Zeit kaum verändert. Dieses Verfahren wurde in den letzten zwanzig Jahren ausgiebig erforscht, was für die Effizienz dieses Algorithmuses spricht.
Zu dem ist das Gaußsche Eliminationsverfahren relativ einfach.
Der Algorithmus besteht aus zwei Etappen, aus der Vorwärtselimination und dem Rückwärtseinsetzen.
2.1 Vorwärtselimination
Ziel dieser ersten Etappe ist es, das Gleichungssystem auf eine Dreiecksform zu bringen, wobei unterhalb der Hauptdiagonalen Nullen stehen und oberhalb neue Koeffizienten stehen sollen.
Das Gleichungssystem soll nach dieser Etappe also wie folgt aussehen:
a\'11x1 + a\'12x2 +...+ a\'1nxn = b\'1
0 + a\'22x2 +...+ a\'2nxn = b\'2
..................................
0 + 0 + 0 + a\'nnxn = b\'n
Ein Gleichungssystem, das auf diese Form gebracht wurde, wird auch als gestaffeltes Gleichungssystem bezeichnet.
Die erste Zeile im Gleichungssystem enspricht bereits der Zeile im gestaffelten Gleichungssystem. In allen weiteren Zeilen muß man nun mit geeigneten Operationen in der ersten Spalte Nullen erzeugen. Dazu benutzt man die zweite Elementaroperation bei Matrizen. Man multipliziert dazu die erste Zeile mit einem geeigneten Faktor c und subtrahiert dieses Produkt dann von der zweiten Zeile.
Der Faktor c wird so berechnet:
c=a21:a11
Nach diesem Schritt hat man die erste Null erzeugt:
a11x1 + a12x2 +...+ a1nxn = b1
0 + a\'22x2 +...+ a\'2nxn = b\'2
...............................
an1x1 + an2x2 +...+ annxn = bn
Im zweiten Schritt multipliziert man wieder die erste Zeile mit einem Faktor c, allerdings dieses Mal mit c=a31:a11 und subtrahiert diese von der dritten Zeile. Dann wird das Produkt aus c=a41:a11 und erster Zeile von der vierten Zeile subtrahiert. So verfährt man weiter bis zur letzten Zeile. Nach diesem Vorgang sind alle ai1 mit i=2..n eliminiert:
a11x1 + a12x2 +...+ a1nxn = b1
0 + a\'22x2 +...+ a\'2nxn = b\'2
.................................
0 + a\'n2x2 +...+ a\'nnxn = b\'n
Jetzt stimmt auch schon die zweite Zeile mit der der gewünschten Endform überein. Man muß nun die zweite Spalte ab der dritten Zeile eliminieren. Dazu schreibt man beim Faktor c jeweils a\'22 in den Nenner. Im Zähler steht dann wieder der jeweilige Koeffizient, der Null werden soll. Außerdem multipliziert man nun nicht mehr die erste Zeile mit diesem Faktor, sondern die zweite Zeile. Wir befinden uns also in der zweiten Eliminationsstufe. Sonst verfährt man wie bei der ersten Eliminationsstufe. Bei der Eliminationsstufe k wird der Faktor c also immer aus einem Quotienten mit dem ersten Koeffizient der k-ten Zeile im Nenner und dem zu eliminierenden Koeffizienten im Zähler gebildet. Mit diesem Faktor wird nun die k-te Zeile multipliziert und von der Zeile mit dem zu eliminierendem Koeffizient subtrahiert.
Der Faktor c allgemein:
cik = aik:akk
mit
n = Anzahl der Gleichungen und Unbekannten
k = 1..n-1; Eliminationsstufe
i = 1..n-1; Zeile
Nachdem man n-1 Eliminationen durchgeführt hat, ist die Dreiecksform erreicht:
w11x1 + w12x2 +...+ w1nxn = v1
w22x2 +...+ w2nxn = v2
..............................
wnnxn = vn
Die neuen Koeffizienten heißen jetzt wij mit i,j=1..n, da die Koeffizienten aij mit i=j=1..n durch die bisherigen Umformungen andere Werte wij mit i=j=1..n angenommen haben. Dasselbe gilt für die Freigelieder bi mit i=1..n und vi mit i=1..n.
Aus dieser Dreiecksform lassen sich nun die Unbekannten xi mit i=1..n durch Rückwärtseinsetzen leicht errechnen.
2.2 Rückwärtseinsetzen oder Rücksubstitution
Die Lösung der letzten Gleichung steht nun schon fast da. Man muß nur noch nach xn auflösen:
xn = vn:wnn
Betrachtet man die vorletzte Gleichung, so erkennt man, daß xn-1 wieder durch Auflösen nach xn-1 und mit bekanntem xn berechnet werden kann:
xn-1 = (vn-1 - wnnxn):wn-1n
Auf diese Weise kann man sich im ganzen gestaffelte Gleichungssystem hocharbeiten, indem man immer wieder mit bisher bekannten Lösungen eine neue ausrechnet.
Damit sind nun alle xi mit i=1..n bestimmt.
2.3 Verbesserung durch Pivotierung
Durch das nachfolgend erklärte Verfahren kann die Effektivität der Vorwärtselimination verbessert werden.
Als Spitzen- oder Pivotelement bezeichnet man den Koeffizienten, der bei der Berechnung des Faktors c im Nenner steht.
Man kann nun durch Zeilenvertauschen erreichen, daß das Pivotelement das betragsgrößte in der jeweiligen Spalte ist, z.B. bei Eliminationsstufe k=1 und |a11| < |a51|:
nach Zeilvertauschen:
a51x1 + a52x2 +...+ a5nxn = b5
a21x1 + a22x2 +...+ a2nxn = b2
a31x1 + a32x2 +...+ a3nxn = b3
a41x1 + a42x2 +...+ a4nxn = b4
a11x1 + a12x2 +...+ a1nxn = b1
a61x1 + a62x2 +...+ a6nxn = b6
..............................
an1x1 + an2x2 +...+ annxn = bn
Für den Faktor c bedeutet dies, daß er nun höchstens den Wert 1 annehmen kann, da das Pivotelement bei der Berechnung von c im Nenner steht und ist durch die Pivotierung der Nenner stets größer als der Zähler.
Durch dieses Verfahren kann man die Koeffizienten klein halten. Andernfalls könnten einige Koeffizienten sehr groß werden und andere sehr klein, denn wenn der Pivotwert aii mit i=1..n sehr klein wäre, würde der Faktor c sehr groß.
Darauffolgend würde aii nun mit dem Faktor c multipliziert werden. Rechenmaschinen haben nun einmal große Probleme damit, aus Produkten mit sehr großen und sehr kleinen Faktoren vernünftige Ergebnisse zu berechnen. Ein Gleichungsystem könnte nun derart schlecht konditioniert sein, daß sich solche Rechenfehler häufen und die Lösungen verzerrt würden. Dies wird mit der Pivotierung umgangen.
Werden nur Zeilenausgetauscht, so bezeichnet man dieses Vorgehen als partielle Pivotierung. Vollständige Pivotierung wäre, wenn man zusätzlich noch Spalten vertauschen würde. In der Praxis hat sich jedoch gezeigt, daß das weitaus aufwendigere vollständige Pivotieren gegenüber dem partiellen Pivotieren keinen Vorteil hat. Die Genauigkeit der Lösung wird nicht verbessert.
Die partielle Pivotierung darf bei der Anwendung des Gauß\'schen Eliminationsverfahren noch aus einem anderen Grund keineswegs fehlen. Es könnte nämlich sein, daß das aktuelle Pivotelement den Wert 0 hat. In diesem Fall würde man bei der Berechnung des Faktors c auf eine Division durch Null stoßen.
Mit der Pivotierung wird das umgangen, sie darf also auf keinen Fall fehlen.
3. Gauß-Jordan Algorithmus
Der Gauß-Jordan Algorithmus unterscheidet sich vom Gauß\'schen-Eliminationsverfahren nur in der zweiten Etappe. Die erste Etappe ist bei beiden Verfahren die Vorwärtselimination. Nachdem nun das Gleichungssystem in ein gestaffeltes System doch Vorwärtseliminieren überführt worden ist, wird nun nicht rücksubstitutiert, sondern man versucht oberhalb der Hauptdiagonale ebenfalls Nullen zu erzeugen. Zum Schluß bleibt also nur noch die Hauptdiagonale stehen, und die Werte für die xi mit i=1..n sind damit gegeben:
s11x1 = t1
s22x2 = t2
................................
. snnxn = tn
Das angestrebte Ziel erreicht man durch das sogenannte Gauß-Jordan\'sche Reduktionsverfahren. Man geht von einem gestaffelten Gleichungsystem, das durch Vorwärtselemination erstellt wurde:
w11x1 + w12x2 +..............+ w1nxn = v1
w22x2 +..............+ w2nxn = v2
.............................................
wn-1,n-1xn-1 + wn-1,nxn = vn
wnnxn = vn
Die eben durchgeführte Vorwärtselimination muß nun genau in anderer Richtung durchgeführt werden, d.h. es gilt nun in der ersten Reduktionsstufe die letzte Spalte ab der vorletzten Zeile zu eliminieren, denn die letzte Zeile entspricht bereits der gewünschten Endform. Die letze Zeile wird also wieder mit einem Faktor c=wn-1,n:wnn multipliziert und dann von der vorletzen Zeile subtrahiert werden. Die vorletzte Zeile lautet dann:
w\'n-1,n-1x\'n-1 = v\'n-1
Ähnlich behandelt man die (n-2)-te Zeile. Das Produkt aus c=wn-2,n:wnn und wnn wird von der (n-2)-ten Zeile abgezogen, zurück bleibt:
w\'n-2,n-2xn-2 + w\'n-2,n-1xn-1 = v\'n-2
Ist man schließlich in der ersten Zeile angelangt, so geht man über zur zweiten Reduktionsstufe. Bei der Berechnung des Faktors c steht nun w\'n-1,n-1 im Nenner und der Subtrahend ist nun das Produkt aus c und der vorletzten Zeile. Dies führt man ebenfalls wieder solange durch, bis man die erste Zeile erreicht hat. Dann geht man über zur dritten Reduktionsstufe.
Letztendlich erreicht man die (n-1)-te Reduktionsstufe und die Hauptdiagonalen-Form des Gleichungssystems ist erreicht.
Der Faktor c bei dem Reduktionsverfahren wird allgemein wie folgt berechnet:
cik = an-i,n-k+1:an-k-1,n-k+1
mit
n = Anzahl der Gleichungen und Unbekannten
k = 1..n-1; Reduktionsstufe
i = 1..n-1; Zeile
Um die Lösungen für die xis mit i=1..n zu bekommen, muß man lediglich die einzelnen Gleichungen nach x auflösen:
x1 = t1:s11
x2 = t2:s22
....................
xn-1 = tn-1:sn-1,n-1
xn = tn:snn
Hiermit ist die Lösung für das Gleichungssystem mit Hilfe des Gauß-Jordan-Verfahrens gefunden worden.
4. Gauß-Seidel-Verfahren
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:
a11x1 + a12x2 +...+ a1nxn = b1
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
x2 = 0
......
xn = 0
Im zweiten Durchgang berechnet man nun ein neues x1 mit den vorherigen anderen xis:
x\'1 = (b1 - a120 -...- an0):a11
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:
xi = (xi + x\'i):2
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.
5. Probleme mit den Algorithmen
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.
|
