Kurs:Numerik I/Lösung linearer Gleichungssysteme

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.

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

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

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

• von der 1. Art ${\displaystyle a_{1,1}=110}$ Tiere,
• von der 2. Art ${\displaystyle a_{1,2}=50}$ Tiere und
• von der 3. Art nur ${\displaystyle 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 ${\displaystyle b_{1}=155}$. Unbekannt ist aber der Anteil, den jede Art pro Tier zum Verbrauch der Nahrungsressourcen beiträgt.

Nun wurden in drei Habitaten ${\displaystyle 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. ${\displaystyle b_{1}=155}$, ${\displaystyle b_{2}=176}$, ${\displaystyle b_{3}=110}$ Volumeneinheiten).

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

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

${\displaystyle 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}}}$

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.

${\displaystyle 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}}}$

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

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

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

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

In dem CAS Maxima kann die Matrizen wie folgt definieren

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

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

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

Die Matrixmultiplikation kann man A.x berechnen.

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

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

${\displaystyle 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}}}$

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

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

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

${\displaystyle 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.

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

${\displaystyle \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)

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

${\displaystyle {\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}}}$

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

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

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

${\displaystyle \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.

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

${\displaystyle {\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}}}$

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

${\displaystyle 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.}$

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

${\displaystyle {\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 ${\displaystyle n}$ der Veränderlichen ab.

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

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

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.

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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.

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

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

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

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

für

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

Explizit kann man die Komponenten der Matrix durch

${\displaystyle {\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.

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

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

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

mit Matrizen der speziellen Gestalt

${\displaystyle 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}.}$

Dabei hat man die folgenden Transformationen zu berechnen:

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

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

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

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

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

${\displaystyle {\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.

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

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

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

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.

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

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

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

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

${\displaystyle 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 ${\displaystyle |a_{kk}^{(k)}|>0}$ ${\displaystyle (k=1,...,n-1)}$ gilt.

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

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

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

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

und den Koeffizienten

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

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

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

${\displaystyle {\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}}}$

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.

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

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

Für

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

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

${\displaystyle {\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.

Die exakte Lösung des Gleichungssystems

${\displaystyle 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.

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

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

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

mit periodischer Dezimalbruchentwicklung.

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

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

${\displaystyle \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" ${\displaystyle x_{1}=0,x_{2}=1}$

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

${\displaystyle \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)}$

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

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

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

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

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

${\displaystyle \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 ${\displaystyle x_{1}=1,x_{2}=1}$.

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

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

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

Der Gauß-Algorithmus mit Spaltenpivotsuche wird wie folgt definiert

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

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

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

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

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

${\displaystyle \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}$

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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.

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

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

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.