Pivotisierung (Zeilen-, Spalten- & totale)

09.11.2007, 15:57

Verzweiflung

Pivotisierung (Zeilen-, Spalten- & totale)

Hallo,
ich müsste bis mo in Matlab ein Programm schreiben, in dem ich den (vorgegeben Gauß-Algorithmus habe (http://www.mathematik.uni-kl.de/~damm/PR...ss_ohne_pivot.m)
mit http://www.mathematik.uni-kl.de/~damm/PR...ss_ohne_pivot.m

ich verstehe so die zeilenpivotisierung:

Wenn man eine reguläre, quadr. Matrix hat dann läßt man eine Schleife über die Spalten laufen s.d. in der k. Spalte:
Schleife nach i d.h.Zeilen um max(abs(aik)) zu suchen, wobei abs der Betrag ist
Dann diese Zeile auf k. Zeile verschieben (so steht sie auf der Diagonale)
dann die k-1 restlichen Einträge aus den unteren Zeilen dieser Spalte durch
Gauß-Algorithmus eliminiern
und das ganze bis zur n-1.Spalte durchführen

Das Problem ist jetzt bei der Spaltenpivotisierung:
-also auch erstmal das betragmäßig größte Element in der Zeile,
aber ich glaube nicht, dass man jetzt diese Spalte mit der ersten vertauschen sollte und
dann mit Gauß eliminieren. Das würde die Matrix ja nur zu sehr verändern

Die Totale ist ja, wenn man die beiden kombiniert, aber irgendwie kann ich mir darunter überhaupt nichts vorstellen und was ich gefunden habe, hilft mir auch nicht sehr weiter.

Bitte kann mir jemand helfen und mir helfen.

Ich danke euch schon mal im voraus

09.11.2007, 23:21

tigerbine

Auf diesen Beitrag antworten »

Aus dem [WS] Lineare Gleichungssysteme (preview)
Am Ende ist ein kleines Rechenbeispiel. Vielleicht formuliert einmal deutlicher, was Du mit "Matrix zu sehr verändern" meinst.

LG,
tigerbine Wink

Zitat:

In den Überlegungen von (4b) wurde bislang nur festgestellt, dass man bei einer regulären Matrix A immer einen "Tauschpartner" für den Fall einer Null auf der Diagonale findet.

Steht einem nicht nur ein "Tauschpartner" zur Verfügung, so stellt sich die Frage nach der "besten" Wahl. Den geringsten Aufwand wird wohl eine Suche nach dem ersten von 0 verschiedenen Eintrag in der betreffenden Spalte unterhalb der Diagonale machen. Ist diese "blinde" Wahl jedoch numerisch sinnvoll?

Durch die Implementierung erhält man eine Zerlegung $\begin{eqnarray*} \hat L \hat R \end{eqnarray*}$ und löst das LGS der Form:

$\begin{eqnarray*} (A+E)\hat x = b \end{eqnarray*}$

mit einer unbekannten Matrix E, für die folgende Abschätzung gilt (Golub & VanLoan[1996, S. 106]):

$\begin{eqnarray*} \fbox{$ \displaystyle |E| \leq n\cdot m (3|A| + 5|\hat L| |\hat R|) + \mathcal O(m^2) $} \end{eqnarray*}$

m: Maschinengenauigkeit

n: Ordnung von A, also ist A eine (n x n) Matrix

|.|: Matrix der betragsmäßigen Einträgen

Somit ist es erstrebenswert die Einträge von $\begin{eqnarray*} \hat L \hat R \end{eqnarray*}$ möglichst klein zu halten.

2 LR-Zerlegungen:

$\begin{eqnarray*} A:=\begin{pmatrix} \varepsilon & 1 \\1&1\end{pmatrix}=\begin{pmatrix}1 & 0\\\frac{1}{\varepsilon}&1 \end{pmatrix} \begin{pmatrix} \varepsilon&1\\ 0 & 1-\frac{1}{\varepsilon} \end{pmatrix}=LR \end{eqnarray*}$

$\begin{eqnarray*} A:=\begin{pmatrix} 1 & 1 \\\varepsilon&1\end{pmatrix}=\begin{pmatrix}1 & 0\\\varepsilon &1 \end{pmatrix} \begin{pmatrix} 1&1\\ 0 & 1-\varepsilon\end{pmatrix}=LR \end{eqnarray*}$

$\begin{eqnarray*} \text{mit }0<\varepsilon <<1 \end{eqnarray*}$

Im ersten Fall treten also, im Gegensatz zum Zweiten, sehr große Werte auf. Man kann nun zeigen, dass allgemein für sehr kleine Diagonalelemente in der Matrix die Einträge in den Matrizen L und R sehr groß werden. Somit sollte man Kehrschluss die Diagonalelemente durch vertauschen möglichst groß wählen. Somit ergeben sich:

weitere Pivotsuchstrategien:

Spaltenpivotsuche
Unter den Elementen $\begin{eqnarray*} a_{j,i+1}^{(i)},~j=i+1,...,n \end{eqnarray*}$ der j-ten Spalte wähle man ein dem Betrage nach größtes als neues Diagonalelement.
Suchaufwand: $\begin{eqnarray*} \mathcal O(n^2) \end{eqnarray*}$

Totale Pivotsuche
Unter den Elementen $\begin{eqnarray*} a_{j,k}^{(i)},~j,k \leq i+1 \end{eqnarray*}$ wähle man ein dem Betrag nach größtes als neues Diagonalelement aus. Hier müssen dann ggf. Zeilen und Spalten getauscht werden.
Suchaufwand: $\begin{eqnarray*} \mathcal O(n^3) \end{eqnarray*}$

Bei größeren Matrizen kann es sinnvoll sein, nur so lange zu suchen, bis ein Schwellenwert s überschritten wird.

Mit diesem Wissen kann man nun festhalten, dass auch im Falle der Existenz einer LR-Zerlegung ohne Pivotisierung es sinnvoll seien kann, selbige durchzuführen.

Hierzu ein Beispiel:

$\begin{eqnarray*} A=\begin{pmatrix} 11 & 44 & 1 \\ 0.1 & 0.4 & 3 \\ 0 & 1 & -1 \end{pmatrix},~b = \begin{pmatrix} 1\\ 1 \\ 1\end{pmatrix} \end{eqnarray*}$

Exakte Lösung

$\begin{eqnarray*} x^T=\frac{1}{329}(-1732,~438,~109) \approx (-5.26444,~1.33131,~0.331307) \end{eqnarray*}$

Ohne Pivotisierung

$\begin{eqnarray*} A^{(1)} = \begin{pmatrix} 11 & 44 & 1 \\ 0 & -4.00000E-08 & 2.99091 \\ 0 & 1 & -1 \end{pmatrix},~b^{(1)} = \begin{pmatrix} 1\\ 0.990909 \\ 1\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} A^{(2)} = \begin{pmatrix} 11 & 44 & 1 \\ 0 & -4.00000E-08 & 2.99091 \\ 0 & 0 & 7.47727E+07 \end{pmatrix},~b^{(1)} = \begin{pmatrix} 1\\ 0.990909 \\ 2.47727E+07\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow x^T=(-41.8765,~10.4843,~0.331307) \end{eqnarray*}$

Mit Spalten-Pivotisierung

$\begin{eqnarray*} A^{(1)} = \begin{pmatrix} 11 & 44 & 1 \\ 0 & -4.00000E-08 & 2.99091 \\ 0 & 1 & -1 \end{pmatrix},~b^{(1)} = \begin{pmatrix} 1\\ 0.990909 \\ 1\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} A^{(2)} = \begin{pmatrix} 11 & 44 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 2.99091 \end{pmatrix},~b^{(1)} = \begin{pmatrix} 1\\ 1\\ 0.990909 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow x^T=(-5.26445,~1.331331,~0.331307) \end{eqnarray*}$

Neue Frage »

Antworten »

Pivotisierung (Zeilen-, Spalten- & totale)

Verwandte Themen