Lineare Gleichungssysteme

Übersicht

Problemstellung

Gegeben sei eine invertierbare Matrix $ A\in\mathbb{R}^{n\times n}$ mit $ A=(a_{ij})$ , $ {1\leq i,j \leq n}$ und ein Vektor $ b\in\mathbb{R}^n$ . Dann ist ein lineares Gleichungssystem von der Form

$\displaystyle Ax=b$
bzw.

\begin{displaymath}\begin{array}{ccccccccc} a_{11}x_1&+&a_{12}x_2&+&...&+&a_{1n}... ... a_{n1}x_1&+&a_{n2}x_2&+&...&+&a_{nn}x_n&=&b_n\ \end{array}\end{displaymath}
Ziel ist es nun einen Vektor $ x=(x_1,\hdots,x_n)^T\in\mathbb{R}^n$ zu bestimmen, der diese Gleichungen erfüllt. Ein solcher Vektor heißt dann Lösung des Gleichungssystems.

Das Gauß'sche Eliminationsverfahren

Ein Verfahren zur Bestimmung der Lösung von linearen Gleichungssystemen ist das Gauß'sche Eliminationsverfahren. Die Idee ist, das gegebene Gleichungssystem durch bestimmte Umformungen in die folgende gestaffelte Form zu bringen:

\begin{displaymath}\begin{array}{ccccccccc} r_{11}x_1&+&r_{12}x_2&+&...&+&r_{1n}... ...&\ddots&&\vdots&&\vdots\ &&&&&&r_{nn}x_n&=&c_n\ \end{array}\end{displaymath}
Aus dieser Form lässt sich die Lösung des Systems sehr leicht durch Rückwärtsauflösen berechnen (falls $ r_{ii}\neq 0, i=1,\ldots ,n$ ):

$\displaystyle x_i=\left.\left(c_i - \sum_{k=i+1}^{n}r_{ik}x_k\right)\right/r_{ii}$   für$\displaystyle \quad i=n,n-1,\ldots ,1$
Natürlich dürfen zur Erzeugung der gestaffelten Form nur solche Umformungen am Gleichungssystem vorgenommen werden, die die Lösung des Systems nicht verändern. Im hier beschriebenen Verfahren werden folgende Transformationen benutzt:
  • Vertauschen von Zeilen/Spalten;
  • Multiplikation einer kompletten Zeile mit einer von null verschiedenen reellen Zahl;
  • Addition eines Vielfachen einer Zeile zu einer anderen.
Im Folgenden wird nun das Verfahren beschrieben.
Setze $ A^1:=A$ und $ b^1:=b$ . Seien nun schon $ k-1$ Schritte durchgeführt, dann hat das System die Form

$\displaystyle A^kx=b^k$
mit

\begin{displaymath}A^k=\left( \begin{array}{cccccc} a^k_{11}&\cdots&\cdots&\cdot... ...nk}&\cdots &a^k_{nn}\ \end{array}\right), \quad k=1,\ldots ,n\end{displaymath}
Der $ k$ -te Schritt geht dann wie folgt:
  1. Wähle ein $ r_k\in \{k,\ldots ,n\}$ mit $ a^k_{r_kk}\neq 0$ und vertausche die $ k$ -te und $ r_k$ -te Zeile von $ A^k$ (und $ b^k$ ), um $ D^k$ zu erhalten.
  2. Subtrahiere das $ \frac{d^k_{ik}}{d^k_{kk}}$ -fache der $ k$ -ten Zeile von der $ i$ -ten für $ i=k+1,\ldots ,n.$
  3. Bezeichne die so erhaltene Matrix mit $ A^{k+1}$ und den Vektor mit $ b^{k+1}$

Pivotisierungsstrategien

Das in Schritt 1 gewählte Element $ a^k_{r_kk}$ wird auch Pivotelement genannt. Durch geschickte Wahl des Pivotelements kann man gegebenenfalls numerisch bessere Ergebnisse bei der Durchführung des Verfahrens erzielen. Gängige Strategien zur Wahl des Pivotelements sind die Folgenden:
  • Bei der Diagonalstrategie wird immer $ r_k=k$ gewählt, allerdings kann dieses Verfahren selbst bei regulären Matrizen zusammenbrechen. Bestimmte Klassen von Matrizen wie z.B. strikt diagonaldominante oder positiv definite Matrizen, lassen sich damit allerdings behandeln.
  • Bei der absoluten Spaltenpivotisierung wählt man $ r_k\in \{k,\ldots ,n\}$ so, dass

    $\displaystyle \vert a^k_{r_k k}\vert=\max_{i\geq k}\vert a^k_{ik}\vert$
  • Bei der relativen Spaltenpivotisierung dagegen wählt man $ r_k\in \{k,\ldots ,n\}$ so, dass

    $\displaystyle \frac{\vert a^k_{r_k k}\vert}{s_{r_k}}=\max_{i\geq k}\frac{\vert a^k_{ik}\vert}{s_i},\quad s_i=\sum_{j\geq k}\vert a^k_{ij}\vert$
  • Man kann auch in der gesamten noch nicht "`gestaffelten"' Untermatrix $ \left(\begin{array}{ccc} a^k_{kk}&\cdots&a^k_{kn}\ \vdots&\vdots&\vdots\ a^k_{nk}&\cdots &a^k_{nn}\ \end{array}\right)$ das betragsmäßig maximale Element suchen. Dieses muss man dann durch Zeilen- und Spaltentausch an die Stelle $ (k,k)$ bringen. Das so erhaltene Verfahren nennt man totale Pivotisierung. Man kann diese Strategie ebenfalls absolut und relativ durchführen.

Fehlerabschätzungen

Während der Durchführung des Gauß-Algorithmus können sich Rundungsfehler anhäufen, und die berechnete Lösung $ \widetilde x$ muss nicht mehr viel mit der wahren Lösung $ x$ zu tun haben. Wie stark die Abweichung maximal sein kann, hängt unmittelbar von der Kondition der Matrix $ A$ ab. Die Kondition ist dabei definiert durch

$\displaystyle \textrm{cond}(A)=\textrm{cond}_{\vert\vert\cdot\vert\vert}(A):=\vert\vert A\vert\vert\,\vert\vert A^{-1}\vert\vert$
Man kann nun folgendes zeigen:
Sei $ \vert\vert\cdot\vert\vert$ eine Vektornorm und $ \vert\vert\cdot\vert\vert$ eine dazu verträgliche Matrixnorm. Ist die rechte Seite $ \widetilde b$ im Vergleich zur tatsächlichen rechten Seite $ b$ gestört, und löst dann $ \widetilde x$ das Gleichungssystem

$\displaystyle A\widetilde x=\widetilde b$
dann gilt für die relative Änderung der Lösung die (i.A. zu pessimistische) Abschätzung

$\displaystyle \frac{\vert\vert\widetilde x-x\vert\vert}{\vert\vert x\vert\vert}... ...extrm{cond}(A)\frac{\vert\vert\widetilde b-b\vert\vert}{\vert\vert b\vert\vert}$
Die Aussagen werden schwieriger falls auch Störungen in $ A$ berücksichtigt werden. Das analoge Ergebnis lautet dann:
Sei $ A$ invertierbar, und für die gestörte Matrix gelte $ \gamma=\vert\vert A^{-1}\vert\vert\,\vert\vert\widetilde A-A\vert\vert<1$ . Dann ist $ \widetilde A$ invertierbar, und mit $ \widetilde A\widetilde x=\widetilde b$ gilt

$\displaystyle \frac{\vert\vert\widetilde x-x\vert\vert}{\vert\vert x\vert\vert}... ...\vert}+\frac{\vert\vert\widetilde b-b\vert\vert}{\vert\vert b\vert\vert}\right)$



Das folgende Programm löst lineare Gleichungssysteme mit dem Gauß'schen Eliminationsverfahren. Wird nur eine Pivotisierungsstrategie für ein Gleichungssystem mit $ (n\leq 4)$ ausgewählt, zeigt das Programm die konkrete Durchführung des Verfahrens. Wählt man dagegen mehrere Strategien oder ein größeres Gleichungssystem, so werden die Ergebnisse genauer diskutiert. Es besteht außerdem die Möglichkeit, das Gauß-Verfahren mit verschiedenen Mantissenlängen durchzuführen, so dass Rundungsfehler besser deutlich werden.

 

 Top

 

 

 

 
Last Change: 22.09.2004