Kurs:Numerik I/Lösung linearer Gleichungssysteme

Einleitung

Wiki2Reveal

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

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 $x\in \mathbb {R} ^{n}$ zu finden, bei dem der Fehler $\|Ax-b\|$ bzgl. einer Norm möglichst klein wird.

Quadratische Matrizen

Im Falle von quadratische Matrizen $A\in \mathbb {R} ^{n\times n}$ und $x,b\in \mathbb {R} ^{n}$ liefert die lineare Algebra Lösungsverfahren, um das $x\in \mathbb {R} ^{n}$ zu finden, welches das Gleichungssystem $Ax=b$ löst. In einem solchen Fall gilt dann $\|Ax-b\|=0$.

Anwendungsbeispiel

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

• von der 1. Art $a_{1,1}=110$ Tiere,
• von der 2. Art $a_{1,2}=50$ Tiere und
• von der 3. Art nur $a_{1,3}=300$ Tiere.

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

Übertragung in Vektoren

Nun wurden in drei Habitaten $a_{1},a_{2},a_{3}$ die Individuen gezählt und zu jedem Habitat gemessen, wie viele Volumeneinheiten der Nahrungsquelle insgesamt im Habitat verbraucht wurden (z.B. $b_{1}=155$, $b_{2}=176$, $b_{3}=110$ Volumeneinheiten).

• $a_{1}:=(110,50,300)\in \mathbb {R} ^{3}$
• $a_{2}:=(250,120,90)\in \mathbb {R} ^{3}$
• $a_{3}:=(20,500,0)\in \mathbb {R} ^{3}$

Beispieldarstelle

Das obige Problem wird nun als lineares Gleichungssystem darstellt, wobei gezählt Anzahlen der Arten in der Matrix $A\in \mathbb {R} ^{3\times 3}$ und die Volumeneinheiten der Nahrungsquelle als Vektor $b\in \mathbb {R} ^{3}$ dargestellt wird, z.B.

$A:={\begin{pmatrix}110&50&300\\250&120&90\\20&500&0\end{pmatrix}}\qquad b={\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\end{pmatrix}}={\begin{pmatrix}155\\176\\110\end{pmatrix}}$

Nahrungsmittelverbrauch als Matrixmultiplikation

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.

$A\cdot {\tilde {x}}:=A\cdot {\begin{pmatrix}0.1\\0.2\\0.7\end{pmatrix}}={\tilde {b}}={\begin{pmatrix}231\\113\\102\end{pmatrix}}$

Abweichungen von gemessenen Werten

Für den abgenommenen Vektor ${\tilde {x}}:={\begin{pmatrix}0.1\\0.2\\0.7\end{pmatrix}}$ ist der Fehler zu den gemessenen Werten $b$ sehr groß.

$\|A\cdot {\tilde {x}}-b\|=\left\|{\begin{pmatrix}-75\\64\\8\end{pmatrix}}\right\|={\sqrt {(-76)^{2}+64^{2}+8^{2}}}\approx 99,7$

Exakte Lösung des Gleichungssystems

Die obige Matrix ist invertierbar/regulär, denn es gilt für die Determinante $det(A)=31920000\not =0$. Damit ist die Lösung eindeutig bestimmt und es gilt mit:

$x={\begin{pmatrix}0.5\\0.2\\0.3\end{pmatrix}}\qquad A\cdot x={\begin{pmatrix}155\\176\\110\end{pmatrix}}$

Berechnungen in Maxima

In dem CAS Maxima kann die Matrizen wie folgt definieren

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

und den Spaltenvektor $x\in \mathbb {R}$ durch:

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

Die Matrixmultiplikation kann man A.x berechnen.

Aufgabe

Stellen Sie selbst ein Gleichungssystem $A\cdot x=b$ mit einer regulären Matrix $A$ auf, geben einen Lösungsvektor $b$ und berechnen Sie die Lösung $x$.

Nicht-quadratische Matrizen

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

$A:={\begin{pmatrix}110&50&300\\250&120&90\\20&500&0\\90&100&120\\30&40&50\end{pmatrix}}\qquad b={\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\end{pmatrix}}={\begin{pmatrix}155\\176\\110\\101\\38\end{pmatrix}}$

Zielsetzung

Diese Lernressource in der Wikiversity hat das Ziel, "direkte" Verfahren zur numerischen Lösung linearer Gleichungssysteme $Ax=b$ vorzustellen, wobei $A\in \mathbb {R} ^{n\times n}$ eine gegebene Matrix und $b\in \mathbb {R} ^{n}$ 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

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

Definition - Dreiecksmatrix

Matrizen $L,R\in \mathbb {R} ^{n\times n}$ der Form:

$L:={\begin{pmatrix}l_{11}&0&...&0\\l_{21}&l_{22}&\ddots &\vdots \\\vdots &&\ddots &0\\l_{n1}&...&...&l_{nn}\end{pmatrix}},\quad R:={\begin{pmatrix}r_{11}&r_{12}&...&r_{1n}\\0&r_{22}&&\vdots \\\vdots &\ddots &\ddots &\vdots \\0&...&0&r_{nn}\end{pmatrix}}$

heißen untere bzw. obere Dreiecksmatrizen.

Invertierbarkeit - Dreiecksmatrix

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

$\det(L)=\prod _{k=1}^{n}l_{kk}\neq 0,\quad \det(R)=\prod _{k=1}^{n}r_{kk}\neq 0.$

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

Gestaffeltes Gleichungssystem

Für die obere Dreiecksmatrix $R:=(r_{kj})\in \mathbb {R} ^{n\times n}$ mit $r_{kj}=0$ für $k>j$ ist das gestaffelte Gleichungssystem $Rx=z$ für einen gegebenen Vektor $z\in \mathbb {R} ^{n}$ von der Form

${\begin{array}{ccccccccc}r_{11}x_{1}&+&r_{12}x_{2}&+&...&+&r_{1n}x_{n}&=&z_{1},\\&&r_{22}x_{2}&+&...&+&r_{2n}x_{n}&=&z_{2},\\&&&&\ddots &&\vdots &\vdots &\vdots \\&&&&&&r_{nn}x_{n}&=&z_{n}.\end{array}}$

Lösung eines gestaffelten Gleichungssystems

Dessen Lösung $x\in \mathbb {R} ^{n}$ kann für reguläres $R$, d. h. für $r_{ii}\neq 0$ $(i=1,...,n)$, 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 $i=n,n-1,n-2,...,1$ berechne

$x_{i}=\left(z_{i}-\sum _{j=i+1}^{n}r_{ij}x_{j}\right)/r_{ii}.$

Stufen der gestaffelten LGS

Dabei sind in den Stufen $i=n,n-1,n-2,...,1$ je $n-i$ Multiplikationen und eine Division, d. h. $n-i+1$ wesentliche arithmetische Operationen, durchzuführen. Insgesamt sind dies also

$\sum _{i=1}^{n}(n-i+1)=\sum _{m=1}^{n}m={\frac {n(n+1)}{2}}={\frac {n^{2}}{2}}\left(1+{\mathcal {O}}\left({\frac {1}{n}}\right)\right)$

Multiplikationen und Divisionen.

Untere Dreiecksmatrix - gestaffelten LGS

Für eine untere Dreiecksmatrix $L:=(l_{ij})\in \mathbb {R} ^{n\times n}$ mit $l_{ij}=0$ für $i<j$ ist das entsprechende gestaffelte Gleichungssystem $Lx=b$ für einen gegebenen Vektor $b\in \mathbb {R} ^{n}$ von der Form

${\begin{array}{ccccccccc}l_{11}x_{1}&&&&&&&=&b_{1},\\l_{21}x_{1}&+&l_{22}x_{2}&&&&&=&b_{2},\\\vdots &&\vdots &&\ddots &&&\vdots &\vdots \\l_{n1}x_{1}&+&l_{n2}x_{2}&+&...&+&_{nn}x_{n}&=&b_{n}.\end{array}}$

Lösung untere Dreiecksmatrix - gestaffelten LGS

Seine Lösung $x\in \mathbb {R} ^{n}$ kann für reguläres $L$, d. h. für $l_{ii}\neq 0$ $(i=1,...,n)$, zeilenweise von oben nach unten durch Auflösen nach der Unbekannten in der Diagonalen berechnet werden und zwar nach folgender Vorschrift. Für $i=1,2,3,...,n$ berechne

$x_{1}={\frac {b_{1}}{l_{1,1}}}\qquad x_{i}=\left(b_{i}-\displaystyle \sum _{j=1}^{i-1}l_{ij}x_{j}\right)\cdot {\frac {1}{l_{ii}}}{\mbox{ mit }}i\geq 2.$

Rechenoperation untere bzw. obere Dreiecksmatrix

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

${\frac {n\cdot (n+1)}{2}}={\frac {n^{2}}{2}}+{\frac {n}{2}}=1+\ldots +n$ (siehe Berechnungen in Dreiecksmatrix).

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

Der Gauß-Algorithmus

Im Folgenden beschreiben wir den sog. Gauß-Algorithmus. Dieser führt das lineare Gleichungssystem (kurz: LGS) $Ax=b$ in ein äquivalentes oberes gestaffeltes LGS $Rx=z$ über, dessen Lösung $x\in \mathbb {R} ^{n}$, wie im vorangehenden Abschnitt gezeigt wurde, leicht berechnet werden kann.

Einführung - Gauß-Algorithmus

Seien nun $A:=(a_{ij})\in \mathbb {R} ^{n\times n}$ eine gegebene Matrix mit $\det(A)\neq 0$ und $b\in \mathbb {R} ^{n}$ 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

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

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

${\begin{array}{ccccccccc}a_{11}x_{1}&+&a_{12}x_{2}&+&...&+&a_{1n}x_{n}&=&b_{1},\\a_{21}x_{1}&+&a_{22}x_{2}&+&...&+&a_{2n}x_{n}&=&b_{2},\\\vdots &&\vdots &&&&\vdots &&\vdots \\a_{n1}x_{1}&+&a_{n2}x_{2}&+&...&+&a_{nn}x_{n}&=&b_{n}\end{array}}$

Berechnung der 1. Stufe im Gauß-Algorithmus 1

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

${\begin{array}{ccccccccc}a_{11}^{(2)}x_{1}&+&a_{12}^{(2)}x_{2}&+&...&+&a_{1n}^{(2)}x_{n}&=&b_{1}^{(2)},\\&&a_{22}^{(2)}x_{2}&+&...&+&a_{2n}^{(2)}x_{n}&=&b_{2}^{(2)},\\&&\vdots &&&&\vdots &&\vdots \\&&a_{n2}^{(2)}x_{2}&+&...&+&a_{nn}^{(2)}x_{n}&=&b_{n}^{(2)}\end{array}}$

überführt.

Bemerkung zur 1. Stufe im Gauß-Algorithmus 2

Wenn $a_{11}\neq 0$ ist, kann dies für die erste Zeile mit

$a_{1j}^{(2)}:=a_{1j}\quad (j=1,...,n),\quad b_{1}^{(2)}:=b_{1}$

erreicht werden und für die Zeilen $i=2,3,...,n$ mit Zeilenoperationen der Form

${\text{neue Zeile }}i:={\text{alte Zeile }}i-l_{i1}\cdot ({\text{alte Zeile }}1)$

für

$l_{i1}:={\frac {a_{i1}}{a_{11}}},\quad i=2,3,...,n$

Berechnung der 1. Stufe im Gauß-Algorithmus 3

Explizit kann man die Komponenten der Matrix durch

${\begin{array}{rcl}\underbrace {(a_{i1}-l_{i1}a_{11})} _{=0}x_{1}+\underbrace {(a_{i2}-l_{i1}a_{12})} _{=:a_{i2}^{(2)}}x_{2}+&...&+\underbrace {(a_{in}-l_{i1}a_{1n})} _{=:a_{in}^{(2)}}x_{n}\\&=&\underbrace {b_{i}-l_{i1}b_{1}} _{=:b_{i}^{(2)}}.\\\end{array}}$

berechnen.

Eliminationsschritte im Gauß-Algorithmus - 1

Diesen Eliminationsschritt wiederholt man nun analog für das um die erste Zeile und Spalte reduzierte LGS für die $(n-1)$ Unbekannten $x_{2},...,x_{n}$. (Denn Addition eines Vielfachen einer Zeile mit Index $\geq 2$ zu einer anderen Zeile mit Index $\geq 2$ erzeugt wiederum eine Null in der ersten Spalte.)

Eliminationsschritte im Gauß-Algorithmus - 2

Führt man diesen Eliminationsprozess sukzessive für die jeweils entstehenden Teilsysteme durch, so erhält man also im Fall $a_{kk}^{(k)}\neq 0$ zu $Ax=b$ äquivalente Gleichungssysteme

$A^{(k)}x=b^{(k)},\quad k=1,...,n$

Eliminationsschritte - spezielle Gestalt der Matrix - 3

mit Matrizen der speziellen Gestalt

$A^{(k)}:={\begin{pmatrix}a_{11}^{(k)}&a_{12}^{(k)}&...&...&...&a_{1n}^{(k)}\\0&a_{22}^{(k)}&...&...&...&a_{2n}^{(k)}\\\vdots &&\ddots &&&\vdots \\0&\ldots &0&a_{kk}^{(k)}&...&a_{kn}^{(k)}\\\vdots &&&\vdots &&\vdots \\0&\ldots &0&a_{nk}^{(k)}&...&a_{nn}^{(k)}\end{pmatrix}}\in \mathbb {R} ^{n\times n}.$

Eliminationsschritte - Sequenz äquivalenter Matrizen - 4

Dabei hat man die folgenden Transformationen zu berechnen:

$A:=A^{(1)}\to A^{(2)}\to ...\to A^{(n)}=:R,$

$b:=b^{(1)}\to b^{(2)}\to ...\to b^{(n)}=:z,$

wobei $R$ obere Dreiecksmatrix und $A^{(s)}=A^{(s+1)}=...=A^{(n)}=R$ für $s\leq n$ möglich ist. Wenn bereits mit weniger Iterationsschritten eine Dreiecksmatrix generiert werden konnte.

Eliminationsschritte - Bezeichnung Stufen - 5

Den Übergang von $A^{(i)}$ nach $A^{(i+1)}$ bezeichnen wir als $i$-te Stufe des Gauß-Algorithmus.

Eliminationsschritte - Anzahl der Rechenoperationen - 6

Im Zuge des Gauß-Algorithmus sind in der $r$-ten Stufe $(n-r)(n-r+1)$ Multiplikationen und $n-r$ Divisionen, d. h. $(n-r)^{2}+2(n-r)$ wesentliche arithmetische Rechenoperationen durchzuführen, so dass insgesamt maximal

${\begin{array}{rcl}\displaystyle \sum _{i=1}^{n-1}i^{2}+2\sum _{i=1}^{n-1}i&=&\displaystyle {\frac {n(n+1)(2n+1)}{6}}+n(n-1)\\&=&\displaystyle {\frac {n^{3}}{3}}\left(1+{\mathcal {O}}\left({\frac {1}{n}}\right)\right)\\\end{array}}$

wesentliche Rechenoperationen anfallen.

Rechenaufwand - Landau-Symbol

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

• $f\in {\mathcal {O}}(1)$ bedeutet, dass $f$ beschränkt ist.
• $f\in {\mathcal {O}}(n)$ bedeutet, dass $f$ linear ist.
• $f\in {\mathcal {O}}(n^{2})$ bedeutet, dass $f$ sich betragsmäßig mit einem quadratischen Polynom beschränken lässt.

Eliminationsschritte - Diagonalelement von 0 verschieden - 7

Es wurde hier vorausgesetzt, dass die in jeder Stufe auftretenden Diagonalelemente nicht verschwinden, d. h. $a_{kk}^{(k)}\neq 0$ $(k=1,...,n-1)$ ist. Der folgende Satz gibt eine Klasse von Matrizen $A\in \mathbb {R} ^{n\times n}$ an, für die dies der Fall und somit der Gauß-Algorithmus durchführbar ist.

Strikt diagonaldominante Matrizen

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

Eine Matrix $A=(a_{ij})\in \mathbb {R} ^{n\times n}$ heißt strikt diagonaldominant, wenn gilt:

$\sum _{j=1 \atop j\neq i}^{n}|a_{ij}|<|a_{ii}|,\quad i=1,...,n.$

Satz - Lösbarkeit strikt diagonaldominanten Matrizen

Wenn $A=(a_{ij})\in \mathbb {R} ^{n\times n}$ strikt diagonaldominant ist, so ist der Gauß-Algorithmus zur Lösung von $Ax=b$ durchführbar.

Beweis

Es wird mit vollständiger Induktion über $k=1,...,n-1$ gezeigt, dass die Matrizen

$B^{(k)}:={\begin{pmatrix}a_{kk}^{(k)}&...&a_{kn}^{(k)}\\\vdots &\ddots &\vdots \\a_{nk}^{(k)}&...&a_{nn}^{(k)}\end{pmatrix}}\in \mathbb {R} ^{(n-k+1)\times (n-k+1)}$

strikt diagonaldominant sind und damit insbesondere $|a_{kk}^{(k)}|>0$ $(k=1,...,n-1)$ gilt.

Beweis 1 - Induktionsanfang

Für $B^{(1)}:=A$ ist dies nach Voraussetzung richtig.

Beweis 2 - Induktionsvoraussetzung

Wir nehmen nun an, dass $B^{(k)}$ für ein beliebiges $k$ strikt diagonaldominant ist. Dann gilt insbesondere $a_{kk}^{(k)}\neq 0$, so dass der Gauß-Eliminationsschritt auf $B^{(k)}$ anwendbar ist.

Beweis 3 - Induktionsschritt

Der Eliminationsschritt liefert die Matrix $B^{(k+1)}=(a_{ij}^{(k+1)})\in \mathbb {R} ^{(n-k)\times (n-k)}$ mit

$a_{ij}^{(k+1)}:=a_{ij}^{(k)}-l_{ik}a_{kj}^{(k)},\quad i,j=k+1,...,n$

und den Koeffizienten

$l_{ik}=a_{ik}^{(k)}/a_{kk}^{(k)},\quad i=k+1,...,n.$

Bemerkung 4 - Induktionsschritt

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

Beweis 5 - Induktionsschritt

Für $i=k+1,...,n$ ergibt sich unter Verwendung der Induktionsvoraussetzung

${\begin{array}{rcl}\sum _{j=k+1 \atop j\neq i}^{n}\left|a_{ij}^{(k+1)}\right|&\leq &\sum _{j=k+1 \atop j\neq i}^{n}\left|a_{ij}^{(k)}\right|+|l_{ik}|\sum _{j=k+1 \atop j\neq i}^{n}\left|a_{kj}^{(k)}\right|\\&=&\sum _{j=k \atop j\neq i}^{n}\left|a_{ij}^{(k)}\right|-\left|a_{ik}^{(k)}\right|+|l_{ik}|\left(\sum _{j=k+1}^{n}\left|a_{kj}^{(k)}\right|-\left|a_{ki}^{(k)}\right|\right)\\&<&\left|a_{ii}^{(k)}\right|-\left|a_{ik}^{(k)}\right|+{\frac {\left|a_{ik}^{(k)}\right|}{\left|a_{kk}^{(k)}\right|}}\left(\left|a_{kk}^{(k)}\right|-\left|a_{ki}^{(k)}\right|\right)\\&=&\left|a_{ii}^{(k)}\right|-|l_{ik}|\left|a_{ki}^{(k)}\right|\leq \left|a_{ii}^{(k+1)}\right|.\end{array}}$

Gauß-Algorithmus mit Pivotsuche

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

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

Beispiel 1

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

Beispiel 1 - Vorbereitung zur Pivotsuche

Für

$A:={\begin{pmatrix}0&1\\1&0\end{pmatrix}}\quad x:={\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}\quad b:={\begin{pmatrix}b_{1}\\b_{2}\end{pmatrix}}$

besitzt das Gleichungssystem $Ax=b$ wegen $\det(A)=-1$ sogar für jedes $b\in \mathbb {R} ^{2}$ eine eindeutige Lösung. Jedoch ist der Gauß-Algorithmus in der angegebenen Form wegen $a_{11}=0$ nicht für dessen Lösung durchführbar.

Beispiel 1 - Vertauschung der Zeilen - Pivotsuche

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

${\bar {A}}:={\begin{pmatrix}1&0\\0&1\end{pmatrix}}\quad {\bar {x}}:={\begin{pmatrix}x_{2}\\x_{1}\end{pmatrix}}\quad {\bar {b}}:={\begin{pmatrix}b_{2}\\b_{1}\end{pmatrix}}$

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

Beispiel 2 - Zeilenumforung LGS - Pivotsuche

Die exakte Lösung des Gleichungssystems

$A\cdot x:={\begin{pmatrix}10^{-4}&1\\1&1\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}={\begin{pmatrix}1\\2\end{pmatrix}}=b$

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

${\begin{pmatrix}10^{-4}&1\\0&-999\end{pmatrix}}\cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}={\begin{pmatrix}1\\-998\end{pmatrix}}$

Beispiel 2 - Exakte Lösung LGS - Pivotsuche

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

$x_{1}={\frac {1000}{999}}=1,{\overline {001}}\quad x_{2}={\frac {998}{999}}=0,{\overline {998}}$

mit periodischer Dezimalbruchentwicklung.

Beispiel 2 - normalisierte Gleitkomma-Darstellung für LGS

Für die numerische Berechnung betrachten wir die normalisierte Gleitkomma-Darstellung mit der Basis $b:=10$ und $r:=3$ berechnen die Lösung von $A\cdot x=b$ in der Menge ${\mathcal {A}}(b;r;s):={\mathcal {A}}(10;r;3)$ reeller Zahlen, die auf dem Rechner für die näherungsweise Darstellung mit $s=3$ 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

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

$\left({\begin{array}{cc|c}0.1\cdot 10^{-3}&0.1\cdot 10^{1}&0.1\cdot 10^{1}\\0.1\cdot 10^{1}&0.1\cdot 10^{1}&0.2\cdot 10^{1}\end{array}}\right)$

und die mit großen Fehlern behaftete "Lösung" $x_{1}=0,x_{2}=1$

Beispiel 2b - Näherungsweise Lösung LGS

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

$\left({\begin{array}{ll|l}0.1\cdot 10^{-3}&0.1\cdot 10^{1}&0.1\cdot 10^{1}\\0.1\cdot 10^{1}-0.1\cdot 10^{1}&0.1\cdot 10^{1}-0.1\cdot 10^{5}&0.2\cdot 10^{1}-0.1\cdot 10^{5}\end{array}}\right)$

Beispiel 2c - Näherungsweise Lösung LGS

Da bei der obigen Berechnung im Gauß-Algorithmus mit dem Umrechnungsfaktor $l_{21}=10^{4}$ nur 3 Nachkommastellen berücksichtigt werden, ergibt sich vereinfacht das folgende Tableau.

$\left({\begin{array}{cc|c}10^{-4}&1&1\\0&-10^{4}&-10^{4}\end{array}}\right)$

Beispiel 2d - Näherungsweise Lösung LGS

Bei der Lösung des obigen LGS ergibt sich eine mit großen Fehlern behaftete "Lösung" ${\widetilde {x_{1}}}=0,{\widetilde {x_{2}}}=1$, denn die exakte Lösung auf 3 Nachkommastellen gerunde genau wäre:

$x_{1}={\frac {1000}{999}}\approx 1\quad x_{2}={\frac {998}{999}}\approx 1$

Beispiel 2e - Näherungsweise Lösung LGS

Vertauscht man aber die Zeilen in der Ausgangsgleichung, so gelangt man mit ${\tilde {l}}_{21}=10^{-4}$ zu dem Tableau

$\left({\begin{array}{cc|c}1&1&2\\0&1&1\end{array}}\right)$

und man erhält damit zu der guten Näherungslösung $x_{1}=1,x_{2}=1$.

Bemerkung - Beispiel 2 - Bedeutung der Umrechnungsfaktoren

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 $k$-ten Schritt eine Zeilenvertauschung derart vor, dass man das auf bzw. unterhalb der Diagonale befindliche betragsmäßig größte Element der aktuellen $k$-ten Spalte an die Position des $k$-ten Diagonalelementes bringt.

Aufgabe - LGS-Lösung in Maxima

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

Der Gauß-Algorithmus mit Spaltenpivotsuche wird wie folgt definiert

Ausgangssituation 0 - Gauß-Algorithmus mit Spaltenpivotsuche

Gib die Matrix $A^{(k)}$ der Gestalt.

Schritt 1 - Gauß-Algorithmus mit Spaltenpivotsuche

Bestimme ein $p\in \{k,...,n\}$ mit

$\left|a_{pk}^{(k)}\right|\geq \left|a_{ik}^{(k)}\right|,\quad i=k,...,n.$

Schritt 2 - Gauß-Algorithmus mit Spaltenpivotsuche

Erzeuge ${\hat {A}}^{(k)}:=({\hat {a}}_{ij}^{(k)})\in \mathbb {R} ^{n\times n}$ aus $A^{(k)}$ sowie ${\hat {b}}^{(k)}:=({\hat {b}}_{i}^{(k)})\in \mathbb {R} ^{n}$ aus $b^{(k)}$ durch Vertauschung der $p$-ten und der $k$-ten Zeile von $A^{(k)}$ bzw. $b^{(k)}$,

Schritt 2.1 - Gauß-Algorithmus mit Spaltenpivotsuche

d. h. man vertauscht die Zeilen komponentenweise bzgl aller Spalten und behält für $i\notin \{p,k\}$ die Zeilen von $A^{(k)}$ in ${\hat {A}}^{(k)}$ bei. Formal

$\left.{\begin{matrix}{\hat {a}}_{pj}^{(k)}:=a_{kj}^{(k)},\quad {\hat {a}}_{kj}^{(k)}:=a_{pj}^{(k)},\\{\hat {a}}_{ij}^{(k)}:=a_{ij}^{(k)}{\mbox{ für }}i\notin \{p,k\}\end{matrix}}\right\}j=1,...,n$

Schritt 2.2 - Gauß-Algorithmus mit Spaltenpivotsuche

Analog vertauscht man die Komponenten in dem Spaltenvektor $b^{(k)}$ zu ${\hat {b}}^{(k)}$ über:

${\begin{matrix}{\hat {b}}_{k}^{(k)}:=b_{p}^{(k)},\quad {\hat {b}}_{p}^{(k)}:=b_{k}^{(k)},\\{\hat {b}}_{i}^{(k)}:=b_{i}^{(k)}{\mbox{ für }}i\notin \{p,k\}.\end{matrix}}$

Schritt 3 - Gauß-Algorithmus mit Spaltenpivotsuche

Führe den Eliminationsschritt ${\hat {A}}^{(k)}\to A^{(k+1)},{\hat {b}}^{(k)}\to b^{(k+1)}$ wie oben für $A^{(k)}\to A^{(k+1)}$ und $b^{(k)}\to b^{(k+1)}$ beschrieben aus.

Schritt 4 - Gauß-Algorithmus mit Spaltenpivotsuche

Setze $k$ auf $k+1$ und starte den Algorithmus erneut für die neue Matrix $A^{(k+1)}$.

Definition - Pivotement

Das Element $a_{pk}^{(k)}$ wird als Pivotelement der Spalte bezeichnet mit

$\left|a_{pk}^{(k)}\right|\geq \left|a_{ik}^{(k)}\right|,\quad i=k,...,n.$

Bemerkung 1 - Pivotement

Für $\det(A)\neq 0$ ist das Pivotelement $a_{pk}^{(k)}\neq 0$ für jedes $k$, d. h. ist der Gauß-Algorithmus mit Spaltenpivotsuche durchführbar. Denn in der $k$-ten Stufe des Verfahrens muss $a_{ik}^{(k)}\neq 0$ für mindestens ein $i\in \{k,k+1,...,n\}$ gelten, da man anderenfalls zur nächsten Stufe übergehen könnte und damit ${\hat {A}}^{(n)}$ eine Dreiecksmatrix wäre, für die mindestens ein Diagonalelement identisch Null und somit $\det({\hat {A}}^{(n)})=0$ wäre.

Bemerkung 2 - Pivotement

Letztere Bedingung $\det({\hat {A}}^{(n)})=0$ ist jedoch wegen $\left|\det({\hat {A}}^{(n)})\right|=|\det(A)|$ 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

Es sei darauf hingewiesen, dass man offenbar durch Multiplikation der entsprechenden Gleichung mit einem geeigneten Skalar jedes Element $\neq 0$ 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

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

• absoluter Fehler
• relativer Fehler
• normalisierte Gleitkomma-Darstellung
• Zerlegung PA = LR - (Foliensatz)
• Orthonormalisierungsverfahren - (Foliensatz)
• Landau-Symbol - Abschätzung des Rechenaufwandes

Seiteninformation

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

Wiki2Reveal

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.

• 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.