Kurs:Numerik I/Lösung linearer Gleichungssysteme
Einleitung
BearbeitenWiki2Reveal
BearbeitenDiese 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
BearbeitenComputeralgebrasystemen 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
BearbeitenIm 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
BearbeitenIn 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
BearbeitenNun 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
BearbeitenDas 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
BearbeitenAngenommen, 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
BearbeitenFür den abgenommenen Vektor ist der Fehler zu den gemessenen Werten sehr groß.
Exakte Lösung des Gleichungssystems
BearbeitenDie 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
BearbeitenIn 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
BearbeitenStellen Sie selbst ein Gleichungssystem mit einer regulären Matrix auf, geben einen Lösungsvektor und berechnen Sie die Lösung .
Nicht-quadratische Matrizen
BearbeitenIn 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
BearbeitenDiese 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
BearbeitenDreiecksmatrizen 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
BearbeitenMatrizen der Form:
heißen untere bzw. obere Dreiecksmatrizen.
Invertierbarkeit - Dreiecksmatrix
BearbeitenDie Matrizen und in der Definition sind offenbar genau dann regulär, wenn gilt:
(d.h. Produkt der Diagonalelemente liefert jeweils die Determinante)
Gestaffeltes Gleichungssystem
BearbeitenFür die obere Dreiecksmatrix mit für ist das gestaffelte Gleichungssystem für einen gegebenen Vektor von der Form
Lösung eines gestaffelten Gleichungssystems
BearbeitenDessen 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
BearbeitenDabei 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
BearbeitenFü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
BearbeitenSeine 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
BearbeitenDabei 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
BearbeitenIm 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
BearbeitenSeien 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
BearbeitenDabei 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
BearbeitenAls Ausgangssituation im Gauß-Algorithmus wird das folgende gegebene LGS verwendet:
Berechnung der 1. Stufe im Gauß-Algorithmus 1
BearbeitenIn der erste Stufe wird das gegegeben LGS in ein äquivalentes LGS der Form
überführt.
Bemerkung zur 1. Stufe im Gauß-Algorithmus 2
BearbeitenWenn 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
BearbeitenExplizit kann man die Komponenten der Matrix durch
berechnen.
Eliminationsschritte im Gauß-Algorithmus - 1
BearbeitenDiesen 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
BearbeitenFü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
Bearbeitenmit Matrizen der speziellen Gestalt
Eliminationsschritte - Sequenz äquivalenter Matrizen - 4
BearbeitenDabei 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
BearbeitenDen Übergang von nach bezeichnen wir als -te Stufe des Gauß-Algorithmus.
Eliminationsschritte - Anzahl der Rechenoperationen - 6
BearbeitenIm 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
BearbeitenMit 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
BearbeitenEs 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
BearbeitenWir 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
BearbeitenEine Matrix heißt strikt diagonaldominant, wenn gilt:
Satz - Lösbarkeit strikt diagonaldominanten Matrizen
BearbeitenWenn strikt diagonaldominant ist, so ist der Gauß-Algorithmus zur Lösung von durchführbar.
Beweis
BearbeitenEs wird mit vollständiger Induktion über gezeigt, dass die Matrizen
strikt diagonaldominant sind und damit insbesondere gilt.
Beweis 1 - Induktionsanfang
BearbeitenFür ist dies nach Voraussetzung richtig.
Beweis 2 - Induktionsvoraussetzung
BearbeitenWir 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
BearbeitenDer Eliminationsschritt liefert die Matrix mit
und den Koeffizienten
Bemerkung 4 - Induktionsschritt
BearbeitenMan beachte, dass nicht beim nächsten Schritt überschrieben wird und somit nicht mit einem Iterationszähler versehen werden muss.
Beweis 5 - Induktionsschritt
BearbeitenFür ergibt sich unter Verwendung der Induktionsvoraussetzung
Gauß-Algorithmus mit Pivotsuche
BearbeitenDamit 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
BearbeitenVor der Pivotisierung ist gegebenenfalls eine Äquilibrierung durchzuführen, um die Konditionszahl zu verbessern.
Beispiel 1
BearbeitenWir betrachten nun zunächst das folgende Beispiel zur Vorbereitung für den Gauß-Algorithmus mit Pivotsuche.
Beispiel 1 - Vorbereitung zur Pivotsuche
BearbeitenFü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
BearbeitenVertauscht 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
BearbeitenDie 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
BearbeitenMan erhält dann als exakte Lösung des LGS
mit periodischer Dezimalbruchentwicklung.
Beispiel 2 - normalisierte Gleitkomma-Darstellung für LGS
BearbeitenFü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
BearbeitenBei 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
BearbeitenWir 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
BearbeitenDa 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
BearbeitenBei 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
BearbeitenVertauscht 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
BearbeitenInsbesondere 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
BearbeitenLö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
BearbeitenDer Gauß-Algorithmus mit Spaltenpivotsuche wird wie folgt definiert
Ausgangssituation 0 - Gauß-Algorithmus mit Spaltenpivotsuche
BearbeitenGib die Matrix der Gestalt.
Schritt 1 - Gauß-Algorithmus mit Spaltenpivotsuche
BearbeitenBestimme ein mit
Schritt 2 - Gauß-Algorithmus mit Spaltenpivotsuche
BearbeitenErzeuge aus sowie aus durch Vertauschung der -ten und der -ten Zeile von bzw. ,
Schritt 2.1 - Gauß-Algorithmus mit Spaltenpivotsuche
Bearbeitend. 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
BearbeitenAnalog vertauscht man die Komponenten in dem Spaltenvektor zu über:
Schritt 3 - Gauß-Algorithmus mit Spaltenpivotsuche
BearbeitenFühre den Eliminationsschritt wie oben für und beschrieben aus.
Schritt 4 - Gauß-Algorithmus mit Spaltenpivotsuche
BearbeitenSetze auf und starte den Algorithmus erneut für die neue Matrix .
Definition - Pivotement
BearbeitenDas Element wird als Pivotelement der Spalte bezeichnet mit
Bemerkung 1 - Pivotement
BearbeitenFü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
BearbeitenLetztere 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
BearbeitenEs 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
BearbeitenMehr 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
BearbeitenSeiteninformation
BearbeitenDiese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.
Wiki2Reveal
BearbeitenDieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.
- Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
- Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/L%C3%B6sung%20linearer%20Gleichungssysteme
- siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.