Kurs:Numerik I/Lösung linearer Gleichungssysteme

Einleitung

Bearbeiten

Wiki2Reveal

Bearbeiten

Diese Seite kann als Wiki2Reveal Folien angezeigt werden. Einzelne Abschnitte werden als Folien betrachtet und Änderungen an den Folien wirken sich sofort auf den Inhalt der Folien aus.

Lösen von LGS mit Computeralgebrasystemen

Bearbeiten

Computeralgebrasystemen können symbolisch Berechnungen durchführen (siehe auch Maxima CAS/Lineare Gleichungssysteme). In der Numerik hat man in Regel mehr Gleichungen als Veränderliche gegeben (überbestimmtes Gleichungssystem, die sich aus einer Datenerhebung formulieren lassen). Algebraisch lässt sich diese LGS ggf. nicht lösen, Man kann aber numerische Verfahren verwenden, um einen Vektor   zu finden, bei dem der Fehler   bzgl. einer Norm möglichst klein wird.

Quadratische Matrizen

Bearbeiten

Im Falle von quadratische Matrizen   und   liefert die lineare Algebra Lösungsverfahren, um das   zu finden, welches das Gleichungssystem   löst. In einem solchen Fall gilt dann  .

Anwendungsbeispiel

Bearbeiten

In einem Habitat leben 3 verschiedene Arten - z.B.

  • von der 1. Art   Tiere,
  • von der 2. Art   Tiere und
  • von der 3. Art nur   Tiere.

Alle drei Arten bedienen sich einer Nahrungquelle, von der man weiß, welche Mengen alle 3 Arten zusammen verbrauchen z.B. als Volumeneinheiten  . Unbekannt ist aber der Anteil, den jede Art pro Tier zum Verbrauch der Nahrungsressourcen beiträgt.

Übertragung in Vektoren

Bearbeiten

Nun wurden in drei Habitaten   die Individuen gezählt und zu jedem Habitat gemessen, wie viele Volumeneinheiten der Nahrungsquelle insgesamt im Habitat verbraucht wurden (z.B.  ,  ,   Volumeneinheiten).

  •  
  •  
  •  

Beispieldarstelle

Bearbeiten

Das obige Problem wird nun als lineares Gleichungssystem darstellt, wobei gezählt Anzahlen der Arten in der Matrix   und die Volumeneinheiten der Nahrungsquelle als Vektor   dargestellt wird, z.B.

 

Nahrungsmittelverbrauch als Matrixmultiplikation

Bearbeiten

Angenommen, dass die Tiere der ersten Art 10% zum Verbrauch der Nahrungsquelle beitragen, die 2. ArtArt zu 20% und die 3. Art 70%. Mit dieser Aufteilung müsste in den 3 Habitaten folgenden Mengen der Nahrungsquelle verbraucht werden.

 

Abweichungen von gemessenen Werten

Bearbeiten

Für den abgenommenen Vektor   ist der Fehler zu den gemessenen Werten   sehr groß.

 

Exakte Lösung des Gleichungssystems

Bearbeiten

Die obige Matrix ist invertierbar/regulär, denn es gilt für die Determinante  . Damit ist die Lösung eindeutig bestimmt und es gilt mit:

 

Berechnungen in Maxima

Bearbeiten

In dem CAS Maxima kann die Matrizen wie folgt definieren

 A: matrix(
   [110,50,300], 
   [250,120,90], 
   [20,500,0]
 );

und den Spaltenvektor   durch:

 x: matrix(
  [0.5], 
  [0.2], 
  [0.3]
 );

Die Matrixmultiplikation kann man A.x berechnen.

Stellen Sie selbst ein Gleichungssystem   mit einer regulären Matrix   auf, geben einen Lösungsvektor   und berechnen Sie die Lösung  .

Nicht-quadratische Matrizen

Bearbeiten

In der Praxis sammelt man in der Regel aber nicht nur in 3 Habitaten die Daten über die Indivduen und den Futtermittelverbrauch, sondern in   Habitaten. Dadurch entstehen rechteckige Matrizen, bei denen die Anzahl der Zeilen der Anzahl der Habitate entspricht. Z.B. für   Habitate ergibt sich z.B. eine Matrix

 

Zielsetzung

Bearbeiten

Diese Lernressource in der Wikiversity hat das Ziel, "direkte" Verfahren zur numerischen Lösung linearer Gleichungssysteme   vorzustellen, wobei   eine gegebene Matrix und   ein gegebener Vektor ist. Dabei ist zu berücksichtigen, dass bei numerischen Lösungen der Berechnungsaufwand und die Fehler bei algebraischen Umformungen eine wesentliche Rolle spielen.

Dreieckssysteme

Bearbeiten

Dreiecksmatrizen entstehen z.B. durch die Anwendung des Gaußschen Eliminationsverfahrens auf die Matrix  , die in dem linearen Gleichungssysteme   verwendet wird. Dreieckssysteme werden nun untersucht.

Definition - Dreiecksmatrix

Bearbeiten

Matrizen   der Form:

 

heißen untere bzw. obere Dreiecksmatrizen.

Invertierbarkeit - Dreiecksmatrix

Bearbeiten

Die Matrizen   und   in der Definition sind offenbar genau dann regulär, wenn gilt:

 

(d.h. Produkt der Diagonalelemente liefert jeweils die Determinante)

Gestaffeltes Gleichungssystem

Bearbeiten

Für die obere Dreiecksmatrix   mit   für   ist das gestaffelte Gleichungssystem   für einen gegebenen Vektor   von der Form

 


Lösung eines gestaffelten Gleichungssystems

Bearbeiten

Dessen Lösung   kann für reguläres  , d. h. für    , zeilenweise von unten nach oben durch Auflösen nach der jeweiligen Unbekannten auf der Diagonalen berechnet werden und zwar nach der folgenden Vorschrift:

Für   berechne

 

Stufen der gestaffelten LGS

Bearbeiten

Dabei sind in den Stufen   je   Multiplikationen und eine Division, d. h.   wesentliche arithmetische Operationen, durchzuführen. Insgesamt sind dies also

 

Multiplikationen und Divisionen.

Untere Dreiecksmatrix - gestaffelten LGS

Bearbeiten

Für eine untere Dreiecksmatrix   mit   für   ist das entsprechende gestaffelte Gleichungssystem   für einen gegebenen Vektor   von der Form

 

Lösung untere Dreiecksmatrix - gestaffelten LGS

Bearbeiten

Seine Lösung   kann für reguläres  , d. h. für    , zeilenweise von oben nach unten durch Auflösen nach der Unbekannten in der Diagonalen berechnet werden und zwar nach folgender Vorschrift. Für   berechne

 

Rechenoperation untere bzw. obere Dreiecksmatrix

Bearbeiten

Dabei sind genauso viele wesentliche arithmetische Rechenoperationen durchzuführen wie im Fall eines oberen gestaffelten Gleichungssystems mit   Veränderlichen, nämlich

  (siehe Berechnungen in Dreiecksmatrix).

Die Anzahl der Zeilenumformungen hängt also quadratisch von der Anzahl   der Veränderlichen ab.

Der Gauß-Algorithmus

Bearbeiten

Im Folgenden beschreiben wir den sog. Gauß-Algorithmus. Dieser führt das lineare Gleichungssystem (kurz: LGS)   in ein äquivalentes oberes gestaffeltes LGS   über, dessen Lösung  , wie im vorangehenden Abschnitt gezeigt wurde, leicht berechnet werden kann.

Einführung - Gauß-Algorithmus

Bearbeiten

Seien nun   eine gegebene Matrix mit   und   ein gegebener Vektor. Erlaubte Operationen, die zu einer äquivalenten Umformung eines LGSs führen, sind offenbar

  • die Vertauschung der Reihenfolge von Gleichungen,
  • die skalare Multiplikation von Gleichungen,
  • die Addition des skalaren Vielfachen einer Gleichung zu einer anderen Gleichung,
  • die Vertauschung von Spalten der Koeffizientenmatrix.

Zeilen- Spaltenvertauschung im Gauß-Algorithmus

Bearbeiten

Dabei entspricht offenbar die Vertauschung von Spalten der Koeffizientenmatrix einer Vertauschung der Reihenfolge, in der die Variablen im LGS auftreten. Wir führen im Folgenden den Gauß-Algorithmus zunächst ohne Zeilen- und Spaltenvertauschungen ein, in welchem Fall er aber auch nur für spezielle Matrizen (wir geben einen solchen Typ an) durchführbar ist.

Ausgangssituation im Gauß-Algorithmus

Bearbeiten

Als Ausgangssituation im Gauß-Algorithmus wird das folgende gegebene LGS verwendet:

 

Berechnung der 1. Stufe im Gauß-Algorithmus 1

Bearbeiten

In der erste Stufe wird das gegegeben LGS in ein äquivalentes LGS der Form

 

überführt.

Bemerkung zur 1. Stufe im Gauß-Algorithmus 2

Bearbeiten

Wenn   ist, kann dies für die erste Zeile mit

 

erreicht werden und für die Zeilen   mit Zeilenoperationen der Form

 

für

 

Berechnung der 1. Stufe im Gauß-Algorithmus 3

Bearbeiten

Explizit kann man die Komponenten der Matrix durch

 

berechnen.

Eliminationsschritte im Gauß-Algorithmus - 1

Bearbeiten

Diesen Eliminationsschritt wiederholt man nun analog für das um die erste Zeile und Spalte reduzierte LGS für die   Unbekannten  . (Denn Addition eines Vielfachen einer Zeile mit Index   zu einer anderen Zeile mit Index   erzeugt wiederum eine Null in der ersten Spalte.)

Eliminationsschritte im Gauß-Algorithmus - 2

Bearbeiten

Führt man diesen Eliminationsprozess sukzessive für die jeweils entstehenden Teilsysteme durch, so erhält man also im Fall   zu   äquivalente Gleichungssysteme

 

Eliminationsschritte - spezielle Gestalt der Matrix - 3

Bearbeiten

mit Matrizen der speziellen Gestalt

 

Eliminationsschritte - Sequenz äquivalenter Matrizen - 4

Bearbeiten

Dabei hat man die folgenden Transformationen zu berechnen:

 
 

wobei   obere Dreiecksmatrix und   für   möglich ist. Wenn bereits mit weniger Iterationsschritten eine Dreiecksmatrix generiert werden konnte.

Eliminationsschritte - Bezeichnung Stufen - 5

Bearbeiten

Den Übergang von   nach   bezeichnen wir als  -te Stufe des Gauß-Algorithmus.

Eliminationsschritte - Anzahl der Rechenoperationen - 6

Bearbeiten

Im Zuge des Gauß-Algorithmus sind in der  -ten Stufe   Multiplikationen und   Divisionen, d. h.   wesentliche arithmetische Rechenoperationen durchzuführen, so dass insgesamt maximal

 

wesentliche Rechenoperationen anfallen.

Rechenaufwand - Landau-Symbol

Bearbeiten

Mit dem Landau-Symbol wird ein Rechenaufwand näherungsweise beschrieben.

  •   bedeutet, dass   beschränkt ist.
  •   bedeutet, dass   linear ist.
  •   bedeutet, dass   sich betragsmäßig mit einem quadratischen Polynom beschränken lässt.

Eliminationsschritte - Diagonalelement von 0 verschieden - 7

Bearbeiten

Es wurde hier vorausgesetzt, dass die in jeder Stufe auftretenden Diagonalelemente nicht verschwinden, d. h.     ist. Der folgende Satz gibt eine Klasse von Matrizen   an, für die dies der Fall und somit der Gauß-Algorithmus durchführbar ist.

Strikt diagonaldominante Matrizen

Bearbeiten

Wir betrachten nun strikt diagnaldominante Matrizen, bei denen in jeder Spalte, das Diagonalelement größer als alle anderen Komponenten der jeweiligen Spalte sind. Für diese diagonaldominanten Matrizen werden wir zeigen, dass diese mittels Gauß-Algorithmus lösbar sind.

Definition - strikt diagonaldominant

Bearbeiten

Eine Matrix   heißt strikt diagonaldominant, wenn gilt:

 

Satz - Lösbarkeit strikt diagonaldominanten Matrizen

Bearbeiten

Wenn   strikt diagonaldominant ist, so ist der Gauß-Algorithmus zur Lösung von   durchführbar.

Es wird mit vollständiger Induktion über   gezeigt, dass die Matrizen

 

strikt diagonaldominant sind und damit insbesondere     gilt.

Beweis 1 - Induktionsanfang

Bearbeiten

Für   ist dies nach Voraussetzung richtig.

Beweis 2 - Induktionsvoraussetzung

Bearbeiten

Wir nehmen nun an, dass   für ein beliebiges   strikt diagonaldominant ist. Dann gilt insbesondere  , so dass der Gauß-Eliminationsschritt auf   anwendbar ist.

Beweis 3 - Induktionsschritt

Bearbeiten

Der Eliminationsschritt liefert die Matrix   mit

 

und den Koeffizienten

 

Bemerkung 4 - Induktionsschritt

Bearbeiten

Man beachte, dass   nicht beim nächsten Schritt überschrieben wird und somit nicht mit einem Iterationszähler versehen werden muss.

Beweis 5 - Induktionsschritt

Bearbeiten

Für   ergibt sich unter Verwendung der Induktionsvoraussetzung

 


Gauß-Algorithmus mit Pivotsuche

Bearbeiten

Damit Matrix-Algorithmen bei der numerischen Berechnung möglichst kleine Fehler generieren, ist es oft nötig, dass Elemente ungleich null existieren und man auch nach dem (betragsmäßig) größten Element in der jeweiligen Zeile oder Spalte sucht. Die solchermaßen getroffene Auswahl des Elements nennt man dann Pivotisierung. Die Zeile, in der das Pivotelement steht, nennt man Pivotzeile, die Spalte des Pivotelements heißt Pivotspalte.

Bemerkung - Konditionszahl

Bearbeiten

Vor der Pivotisierung ist gegebenenfalls eine Äquilibrierung durchzuführen, um die Konditionszahl zu verbessern.

Beispiel 1

Bearbeiten

Wir betrachten nun zunächst das folgende Beispiel zur Vorbereitung für den Gauß-Algorithmus mit Pivotsuche.

Beispiel 1 - Vorbereitung zur Pivotsuche

Bearbeiten

Für

 

besitzt das Gleichungssystem   wegen   sogar für jedes   eine eindeutige Lösung. Jedoch ist der Gauß-Algorithmus in der angegebenen Form wegen   nicht für dessen Lösung durchführbar.

Beispiel 1 - Vertauschung der Zeilen - Pivotsuche

Bearbeiten

Vertauscht man jedoch die Zeilen in dem System und damit in  , so erhält man die Matrix

 

und kann der Gauß-Algorithmus für die Lösung des zugehörigen Systems erfolgreich angewendet werden.

Beispiel 2 - Zeilenumforung LGS - Pivotsuche

Bearbeiten

Die exakte Lösung des Gleichungssystems

 

Wir subtrahieren das 1000-fache der ersten Zeile von der 2.Zeile und erhalten.

 

Beispiel 2 - Exakte Lösung LGS - Pivotsuche

Bearbeiten

Man erhält dann als exakte Lösung des LGS

 

mit periodischer Dezimalbruchentwicklung.

Beispiel 2 - normalisierte Gleitkomma-Darstellung für LGS

Bearbeiten

Für die numerische Berechnung betrachten wir die normalisierte Gleitkomma-Darstellung mit der Basis   und   berechnen die Lösung von   in der Menge   reeller Zahlen, die auf dem Rechner für die näherungsweise Darstellung mit   Nachkommastellen für die Ergebnisse verwendet wird. Durch die Verwendung der sog. Maschinenzahlen entsteht ggf. ein Fehler, da nur eine endliche Teilmenge der reellen Zahlen exakt dargestellt werden kann.

Beispiel 2a - Näherungsweise Lösung LGS

Bearbeiten

Bei 3-stelliger Rechnung ergibt sich mit der normalisierten Gleitkommadarstellung die Matrix:

 


und die mit großen Fehlern behaftete "Lösung"  

Beispiel 2b - Näherungsweise Lösung LGS

Bearbeiten

Wir subtrahieren wieder das 1000-fache der ersten Zeile von der 2.Zeile und berechnen aber bis 3 Stellen hinter der Mantisse genau.

 

Beispiel 2c - Näherungsweise Lösung LGS

Bearbeiten

Da bei der obigen Berechnung im Gauß-Algorithmus mit dem Umrechnungsfaktor   nur 3 Nachkommastellen berücksichtigt werden, ergibt sich vereinfacht das folgende Tableau.

 

Beispiel 2d - Näherungsweise Lösung LGS

Bearbeiten

Bei der Lösung des obigen LGS ergibt sich eine mit großen Fehlern behaftete "Lösung"  , denn die exakte Lösung auf 3 Nachkommastellen gerunde genau wäre:

 

Beispiel 2e - Näherungsweise Lösung LGS

Bearbeiten

Vertauscht man aber die Zeilen in der Ausgangsgleichung, so gelangt man mit   zu dem Tableau

 

und man erhält damit zu der guten Näherungslösung  .

Bemerkung - Beispiel 2 - Bedeutung der Umrechnungsfaktoren

Bearbeiten

Insbesondere können also große Umrechnungsfaktoren zu numerischen Instabilitäten führen. Zur Vermeidung solcher etwaigen Instabilitäten bietet sich die folgende Modifikation des Gauß-Algorithmus mit einer Spaltenpivotsuche an. Dabei nimmt man, sofern dies erforderlich ist, im  -ten Schritt eine Zeilenvertauschung derart vor, dass man das auf bzw. unterhalb der Diagonale befindliche betragsmäßig größte Element der aktuellen  -ten Spalte an die Position des  -ten Diagonalelementes bringt.

Aufgabe - LGS-Lösung in Maxima

Bearbeiten

Lösen Sie das obige lineare Gleichungssystem mit Computer Algebra System Maxima über:

linsolve( [1/1000*x1+x2=1,x1+x2=2] , [x1,x2] )

Gauß-Algorithmus mit Spaltenpivotsuche - k-te Stufe

Bearbeiten

Der Gauß-Algorithmus mit Spaltenpivotsuche wird wie folgt definiert

Ausgangssituation 0 - Gauß-Algorithmus mit Spaltenpivotsuche

Bearbeiten

Gib die Matrix   der Gestalt.

Schritt 1 - Gauß-Algorithmus mit Spaltenpivotsuche

Bearbeiten

Bestimme ein   mit

 

Schritt 2 - Gauß-Algorithmus mit Spaltenpivotsuche

Bearbeiten

Erzeuge   aus   sowie   aus   durch Vertauschung der  -ten und der  -ten Zeile von   bzw.  ,


Schritt 2.1 - Gauß-Algorithmus mit Spaltenpivotsuche

Bearbeiten

d. h. man vertauscht die Zeilen komponentenweise bzgl aller Spalten und behält für   die Zeilen von   in   bei. Formal

 

Schritt 2.2 - Gauß-Algorithmus mit Spaltenpivotsuche

Bearbeiten

Analog vertauscht man die Komponenten in dem Spaltenvektor   zu   über:

 

Schritt 3 - Gauß-Algorithmus mit Spaltenpivotsuche

Bearbeiten

Führe den Eliminationsschritt   wie oben für   und   beschrieben aus.

Schritt 4 - Gauß-Algorithmus mit Spaltenpivotsuche

Bearbeiten

Setze   auf   und starte den Algorithmus erneut für die neue Matrix  .

Definition - Pivotement

Bearbeiten

Das Element   wird als Pivotelement der Spalte bezeichnet mit

 

Bemerkung 1 - Pivotement

Bearbeiten

Für   ist das Pivotelement   für jedes  , d. h. ist der Gauß-Algorithmus mit Spaltenpivotsuche durchführbar. Denn in der  -ten Stufe des Verfahrens muss   für mindestens ein   gelten, da man anderenfalls zur nächsten Stufe übergehen könnte und damit   eine Dreiecksmatrix wäre, für die mindestens ein Diagonalelement identisch Null und somit   wäre.

Bemerkung 2 - Pivotement

Bearbeiten

Letztere Bedingung   ist jedoch wegen   nicht möglich, da die beim Gauß-Algorithmus mit Pivotsuche in jeder Stufe durchgeführten Operationen (Zeilenvertauschung und Addition eines Vielfachen einer Zeile zu einer anderen Zeile) höchstens einen Vorzeichenwechsel der Determinante zur Folge haben.

Bemerkung 3 - Pivotement - Skalierung der Zeile

Bearbeiten

Es sei darauf hingewiesen, dass man offenbar durch Multiplikation der entsprechenden Gleichung mit einem geeigneten Skalar jedes Element   in der Pivotspalte zum Pivotelement machen kann und somit eine geeignete Skalierung des zugrunde liegenden linearen Gleichungssystems den Verlauf des Gauß-Algorithmus wesentlich beeinflussen kann.

Bemerkung 4 - Pivotement - Stabilität des Gauß-Algorithmus

Bearbeiten

Mehr dazu findet man z. B. bei Deuflhard/Hohmann. In dem Buch dieser Autoren findet man auch Aussagen zur Stabilität des Gauß-Algorithmus. So wird festgestellt, dass Gauß-Elimination mit Spaltenpivotsuche über der Menge aller invertierbaren Matrizen betrachtet nicht stabil, für wichtige Unterklassen, wie beispielsweise die der positiv definiten Matrizen und die der strikt diagonaldominanten Matrizen, aber stabil ist.


Siehe auch

Bearbeiten

Seiteninformation

Bearbeiten

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Bearbeiten

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.