Kurs:Numerik I/Lösung linearer Gleichungssysteme

Aus Wikiversity

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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikiversity.org/v1/“:): {\displaystyle a_{1,2} = 50 } 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.

Aufgabe[Bearbeiten]

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.

Beweis[Bearbeiten]

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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikiversity.org/v1/“:): {\displaystyle \det(\hat A^{(n)}) = 0} 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.