Gaußsches Eliminationsverfahren

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Dieser Artikel wurde auf den Seiten der Qualitätssicherung eingetragen. Hilf mit, ihn zu verbessern, und beteilige dich an der Diskussion!

Folgendes muss noch verbessert werden: Manche Formeln in diesem Artikel sind als Bilder eingebunden worden und funktionieren nicht mehr, da die Lizenzen nicht existieren oder falsch sind. Die Bilder sollten durch neue oder durch explizite Formeln ersetzt werden. -- Florian Feldhaus 19:54, 27. Mär. 2007 (CEST)

Das Gaußsche Eliminationsverfahren ist ein Algorithmus aus den mathematischen Teilgebieten der linearen Algebra und der Numerik. Es ist ein wichtiges Verfahren zum Lösen von linearen Gleichungssystemen. Die Anzahl der benötigten Operationen zur Lösung des Gleichungssystems ist von der Größenordnung $n 3$ bei einer $n\times n$ -Matrix. In seiner Grundform ist der Algorithmus anfällig für Rundungs- und Rechenfehler, mit kleinen Modifikationen (Pivotisierung) stellt er für allgemeine lineare Gleichungssysteme das Standardlösungsverfahren dar.

Das Verfahren wurde um 1850 von Carl Friedrich Gauß bei Arbeiten auf dem Gebiet der linearen Gleichungssysteme entwickelt, allerdings hatte der chinesische Mathematiker Liu Hui bereits im Jahr 263 eine Beschreibung des Lösungsschemas veröffentlicht.

Inhaltsverzeichnis

1 Erklärung
- 1.1 Kontrolle durch Zeilensumme
2 System mit unendlich vielen Lösungen
3 Pivotisierung
4 LR-Zerlegung
5 Siehe auch
6 Literatur
7 Weblinks

[Bearbeiten] Erklärung

Ein lineares Gleichungssystem mit drei Variablen bzw. Unbekannten (x,y,z) und den jeweiligen Koeffizienten a,b,c,e hat die Form:

a 1 x + a 2 y + a 3 z = e 1

;

b 1 x + b 2 y + b 3 z = e 2

;

c 1 x + c 2 y + c 3 z = e 3

Der Algorithmus zur Berechnung der Variablen x, y und z lässt sich in zwei Etappen einteilen:

Vorwärtselimination,
Rückwärtseinsetzen (Rücksubstitution).

Im ersten Schritt wird das Gleichungssystem durch Äquivalenzumformungen, bei denen die Informationen des Gleichungssystems nicht geändert werden, in die Stufenform gebracht. Stufenform heißt, dass pro Zeile mindestens eine Variable weniger auftritt, also mindestens eine Variable eliminert wird, indem die Zeile so umgeformt wird, dass der Koeffizient der Variablen Null ist. Im obigen Beispiel würde man $b 1, c 1$ und $c 2$ eliminieren, in der dritten Zeile ist dann nur noch die Variable $z$ . Zum Erreichen der Stufenform sind drei Umformungen zulässig: Es können (komplette) Zeilen vertauscht werden, eine Zeile kann mit einer von Null verschiedenen Zahl multipliziert werden oder es darf, wie beim Additionsverfahren, eine Zeile oder das Vielfache einer Zeile zu einer anderen Zeile addiert werden. Im zweiten Schritt werden ausgehend von der letzten Zeile, in der sich nur noch eine Variable befindet, die Variablen ausgerechnet und in die darüberliegende Zeile eingesetzt.

Ein lineares Gleichungssystem kann eine, mehrere oder keine Lösung haben. Diese Unterscheidung kann schon nach der Vorwärtselimination getroffen werden, indem die letzte Zeile betrachtet wird (siehe weiter unten).

Beispiel:

x + 2y + 3z = 2, hier: $a 1 = 1$ , $a 2 = 2$ , $a 3 = 3$ und $e 1 = 2$
x + y + z = 2
3x + 3y + z = 0

Es werden schematisch nur die Koeffizienten (a, b, c, e) geschrieben:

Jetzt wird so umgeformt, dass $b 1$ und $c 1$ Null werden, indem man geeignete Vielfache der ersten Gleichung zur zweiten und dritten Gleichung addiert. Den Multiplikator, mit dem man die Zeile multiplizieren muss, erhält man, indem man die erste Zahl der Zeile, aus der das Element elimiert werden soll, durch die Zahl teilt, die sich in der Zeile darüber an der gleichen Position befindet (hier: 1/1=1, 3/1=3). Da das Element verschwinden soll, muss die Zahl noch mit (–1) multipliziert werden, so dass sie negativ wird.

Zu Zeile 2 wird das (–1)-fache und zu Zeile 3 das (–3)-fache von Zeile 1 addiert. Damit $c 2$ Null wird, wird ein Vielfaches von Zeile 2 zu Zeile 3 addiert, in diesem Fall das (–3)-fache:

Falls die Zahl, durch die zur Berechnung des Multiplikators dividiert wird (hier für die ersten beiden Zeilen die Zahl 1, beim dritten Mal die Zahl (–1) ), Null ist, wird diese Zeile mit einer weiter unten liegenden vertauscht.

Am Ende kann durch Betrachten der letzten Zeile über die Lösbarkeit entschieden werden. Das Gleichungssystem ist:

eindeutig lösbar, wenn kein Element der Diagonalen (hier: $a 1, b 2, c 3$ ) Null ist,
nicht eindeutig oder unlösbar, wenn ein Element der Diagonalen Null ist

Befindet sich die einzige Null auf der Diagonalen in der letzten Zeile, ist das System unlösbar, wenn auf der rechten Seite ( $e x$ ) eine Zahl ungleich Null steht, da es sich dann um eine falsche (unerfüllbare) Aussage handelt (z. B. 0=1); hingegen hat das System unendlich viele Lösungen und ist nicht eindeutig lösbar, wenn dort eine Null steht, da es sich um eine wahre Aussage (0=0) handelt.

Weiter im Beispiel:

Die letzte Zeile bedeutet

- 2 z = - 6

Diese Gleichung ist einfach lösbar und $z = 3$ .

Damit ergibt sich für die zweite Zeile

- 1 y - 2 z = 0

, also

y = - 6

und weiter

x = 5

Damit sind alle "Variablen" (x, y, z) berechnet:

$x = 5 \quad y = -6 \quad z = 3$ .

Wird im ersten Schritt die Matrix weiter umgeformt, bis die Lösung direkt abgelesen werden kann, nennt man das Verfahren Gauß-Jordan-Algorithmus.

[Bearbeiten] Kontrolle durch Zeilensumme

Die Umformungen können durch das Berechnen der Zeilensumme kontrolliert werden.

Hier wurde in der letzten Spalte die Summe aller Elemente der jeweiligen Zeile addiert. Für die erste Zeile ist die Zeilensumme 1+2+3+2 = 8. Da an der ersten Zeile keine Umformungen durchgeführt werden ändert sich ihre Zeilensumme nicht. Bei der ersten Umformung dieses Gleichungssystems wird zur zweiten Zeile das (–1)-fache der ersten addiert. Macht man das auch für die Zeilensumme dann gilt 5 + (–1)*8 = –3. Dieses Ergebnis ist die Zeilensumme der umgeformten zweiten Zeile –1 – 2 + 0 = –3. Zur Überprüfung der Rechnungen kann man also die Umformungen an der Zeilensumme durchführen, sind alle Rechnungen korrekt, muss sich die Zeilensumme der umgeformten Zeile ergeben.

[Bearbeiten] System mit unendlich vielen Lösungen

(I) x + 4y = 8

(II) 3x + 12y = 24

Da die Gleichung (II) ein vielfaches der Gleichung (I) ist, hat das Gleichungssystem unendlich viele Lösungen. Bei der Elimination von x in Gleichung (II) verschwindet diese vollständig, übrig bleibt die Gleichung (I). Löst man diese nach x auf kann man die Lösungsmenge in Abhängigkeit von y angeben:

x = 8 - 4y

L={8 - 4y|y}

[Bearbeiten] Pivotisierung

Der gaußsche Algorithmus ist im Allgemeinen nicht ohne Zeilenvertauschungen durchführbar. Es ist zumindest notwendig, dass an der entsprechenden Stelle keine Null steht. Dieses zum Erzeugen der Nullen in diesem Schritt genutzte Element der Matrix wird Pivot genannt. Um das zu illustrieren, wurden die Pivots des obigen Beispiels markiert. Zeilenvertauschungen waren hier nicht nötig.

Für die Rechnung per Hand ist es sicher sinnvoll, eine 1 oder minus 1 als Pivot zu wählen. Um einen möglichst stabilen Algorithmus zu erhalten, wählt man das betragsgrößte Element als Pivot. Wählt man das Pivot in der aktuellen Spalte, spricht man von Spaltenpivotisierung (analog Zeilenpivotisierung).

[Bearbeiten] LR-Zerlegung

Will man das Lösen des Gleichungssystems Ax=b als Computerprogramm umsetzen bietet es sich an, den Gaußalgorithmus als LR-Zerlegung (auch LU-Zerlegung oder Dreieckszerlegung genannt) zu interpretieren. Dies ist eine Zerlegung der regulären Matrix A in das Produkt einer linken unteren Dreiecksmatrix $L$ (links, bzw. engl. "lower") und einer rechten oberen Dreiecksmatrix $R$ (rechts, auch mit $U$ bezeichnet, von engl. "upper"). Das folgende Beispiel zeigt dies:

$\begin{pmatrix} 1 & 2 & 3 \\ 1 & 1 & 1 \\ 3 & 3 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 3 & 3 & 1 \\ \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 & 3 \\ 0 & -1 & -2 \\ 0 & 0 & -2 \\ \end{pmatrix}$

Dabei hat R die oben erwähnte Stufenform und die Matrix L dient dem Speichern der benötigten Umformungsschritte. Um Eindeutigkeit zu Erreichen werden die Diagonalelemente der Matrix L als 1 festgelegt. Die Umformungsschritte zu speichern hat den Vorteil, dass für verschiedene "rechte Seiten" b das Gleichungssystem effizient durch Vorwärts- und Rückwärtseinsetzen gelöst werden kann.

Die im Allgemeinen aus Stabilitätsgründen benötigten Zeilenvertauschungen können durch eine Permutationsmatrix beschrieben werden:

P A = L R .

[Bearbeiten] Vorwärtseinsetzen

Beim Vorwärtseinsetzen berechnet man eine Lösung $y$ des linearen Gleichungssystem $L y = b$ . Diese steht über die Gleichung $y = R x$ mit der Lösung $x$ des ursprünglichen Gleichungssystems in Beziehung.

Ausgeschrieben hat das Gleichungssystem $L y = b$ folgende Gestalt:

$\begin{pmatrix} l_{11} & 0 & 0 & \ldots & 0\\ l_{21} & l_{22} & 0 & & \vdots\\ l_{31} & l_{32} & l_{33} & \ddots & \vdots\\ \vdots & \vdots & \vdots & \ddots & 0\\ l_{n1} & l_{n2} & l_{n3} & \ldots & l_{n,n} \end{pmatrix} \cdot \begin{pmatrix}y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_n\end{pmatrix} = \begin{pmatrix}b_1 \\ b_2 \\ b_3 \\ \vdots \\ b_n\end{pmatrix}$

Für die Komponenten $y i$ gilt dann die folgende Formel:

$y_i = \frac{1}{l_{ii}} \left( b_i - \sum_{k=1}^{i-1} l_{ik} \cdot y_k \right).$

Beginnend mit $y_1 = \frac{b_1}{l_{11}}$ können nacheinander $y_1, y_2, \ldots,y_n$ ausgerechnet werden, indem jeweils die schon bekannten $y i$ eingesetzt werden.

[Bearbeiten] Rückwärtseinsetzen

Beim Rückwärtseinsetzen berechnet man die Lösung $x$ des ursprünglichen Gleichungssystem, indem man $R x = y$ ähnlich wie beim Vorwärtseinsetzen löst. Der Unterschied besteht darin, dass man bei $x_n = \frac{y_n}{r_{nn}}$ beginnt und dann nacheinander die Werte von $x_{n-1},x_{n-2},\ldots,x_1$ berechnet. Die entsprechende Formel lautet

$x_i = \frac{1}{r_{ii}} \left( y_i - \sum_{k=i+1}^{n} r_{ik} \cdot x_k \right)$

[Bearbeiten] Algorithmus in Pseudocode

Der folgenden Algorithmus führt eine LR-Zerlegung ohne Pivotisierung aus.

   Eingabe: Matrix A
   
   For i = 1 To n
       For j = i To n
           For k = 1 TO i-1               
               A(i,j)-=A(i,k)*A(k,j) 
           end
       end    
       For j=i+1 To n
           For k = 1 TO i-1
               A(j,i)-=A(j,k)*A(k,i)
           end
           A(j,i)/=A(i,i)
       end
    end
   
   Ausgabe: Die mit den Dreiecksmatrizen L und R überschriebene Matrix A, 
   wobei die Einsen auf der Diagonalen von L nicht gespeichert werden.

[Bearbeiten] Komplexität

Die Anzahl arithmetischer Operationen für die LR-Zerlegung ist bei einer $n \times n$ -Matrix ca. $\frac{2}{3}n^3$ . Der Aufwand für das Vorwärts- und Rückwärtseinsetzen ist quadratisch ( $O (n 2)$ ). Für Bandmatrizen mit fester Bandbreite(unabhängig von n) reduziert sich der Aufwand auf $O (n)$ .

Konkret benötigt man bei einem 3×3 System maximal 11 Multiplikationen (oder Divisionen) und 8 Additionen für die Elimination. Dazu kommen 6 Divisionen (oder Multiplikationen) sowie 3 Subtraktionen beim Rückwärtseinsetzen. Bei einem 4×4 System benötigt man insgesamt bis zu 42 Multiplikationen oder Divisionen und 32 Additionen oder Subtraktionen. Der Algorithmus sollte auf einem Rechner nur für Gleichungssysteme kleiner bis mittlerer Dimension verwendet werden (bis etwa n=1000). Für Matrizen höherer Dimension sollten iterative Verfahren verwendet werden.

[Bearbeiten] Stabilität

Ohne Pivotisierung ist das Verfahren im Allgemeinen instabil. Stabilität ergibt sich, falls Spaltenpivotisierung zur Lösung verwendet wird. Bei diagonaldominanten oder positiv definiten Matrizen (siehe auch Cholesky-Zerlegung) ist das Verfahren auch ohne Pivotisierung durchführbar und stabil. Die Stabilitätskonstante kann für das Verfahren allerdings vergleichsweise groß sein. Dies ist der Fall wenn die Matrizen L und R eine wesentlich schlechtere Kondition haben als die Matrix A selbst. Generell bessere Stabilität haben QR-Zerlegungen.

Ein praktischer Ansatz zum Ausgleich dieser Rechenungenauigkeiten besteht aus einer Nachiteration mittels Splitting-Verfahren, da über die LR-Zerlegung eine gute Näherung der Matrix A zur Verfügung steht, die leicht invertierbar ist. Da es meistens nur um kleine Korrekturen geht, reicht oft ein einziger solcher Iterationsschritt. Im Allgemeinen ist für diese Rechnung allerdings eine höhere Genauigkeit notwendig.

[Bearbeiten] Speicherplatzbedarf

Die Rechnung kann auf dem Speicher der Matrix A durchgeführt werden, so dass außer der Speicherung von A selbst kein zusätzlicher Speicherbedarf entsteht. Bei iterativen Verfahren, die mit Matrix-Vektor-Multiplikationen arbeiten, kann allerdings eine explizite Speicherung von A selbst nicht nötig sein, so dass diese Verfahren ggf. vorzuziehen sind. Die Besetztheitsstruktur der Matrix lässt sich zum Beispiel im Falle von Bandmatrizen ausnutzen.

[Bearbeiten] Siehe auch

Liste numerischer Verfahren

[Bearbeiten] Literatur

Andrzej Kielbasiński, Hubert Schwetlick: Numerische lineare Algebra. Eine computerorientierte Einführung. Deutscher Verlag der Wissenschaften, Berlin 1988, ISBN 3-326-00194-0.
Andreas Meister: Numerik linearer Gleichungssysteme. Eine Einführung in moderne Verfahren. 2. Auflage, Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7.

[Bearbeiten] Weblinks

Von „http://de.wikipedia.org../../../g/a/u/Gau%C3%9Fsches_Eliminationsverfahren_59ca.html“

Kategorien: Wikipedia:Qualitätssicherung | Algorithmus | Numerische lineare Algebra