Pivotstrategie

Beschreibung

Beim Numerischen Lösen von Gleichungssystemen mit LR-Methoden bekommt gelegentlich numerisch instabile Ergebnisse. Eine Möglichkeit, um die Konditionszahl zu verringern ist, Zeilentausche zwischen Eliminationsschritten durchzuführen. Das macht man, um bestimmte Elemente, sogenannte Pivotelemente an die richtige Stelle zu bringen.

Motiation

Wenn wir den Gaußscher Eliminationsalgorithmus ausführen wollen, wollen wir üblicherweise, dass besonders große Werte auf der Hauptdiagonalen einer Matrix liegen. Lägen die Werte links unten, z.B.bei der Matrix $\left(\begin{array}{cc}1& 1\\ 10000& 1\end{array}\right)$, so müsste man die erste Zeile mall $10000$ multiplizieren, um die Matrix in eine Dreiecksmatrix umzuwandeln. Das kann dazu führen, dass aus kleinen Abweichungen der Eingabewerte große Fehler resultieren, die sich im schlimmsten Fall gegenseitig verstärken.

Definition

Es gibt verschiedene Methoden um strukturiert Pivotelemente zu suchen. Nicht alle funktionieren so gut, wie man gerne hätte.

Spaltenmax-Strategie

Benutze die implizite Lösung aus der Motivation: Versuche vor jeder Elimination den Wert der Hauptdiagonale so große wie möglich zu machen. Dies bewerkstelligen wir, indem wir Zeilen vertauschen.

Relative Spaltenmax Strategie

Betrachte die Matrix $A=\left(\begin{array}{cc}2& 10000\\ 1& 1\end{array}\right)$ Welche Zeile sollte vor der ersten Elimination nach oben? Der Spaltenmax-Strategie zufolge die erste Zeile. Wenn wir den Wert $10000$ um $1\%$, d.h. um hundert $100$ verändern und uns dann den zweiten Eliminierungsschritt ansehen, dann merken wir, dass wir schon wieder mit großen Zahlen subtrahieren. Der reltaiv kleine Fehler wirkt sich dann stark auf andere Zeilen aus. Tatsächlich kann das eine Quelle von numerischer Instabilität sein. Um das zu verhindern, fordern wir, dass der Wert, den wir in die Hauptdiagonale tauschen relativ der größte ist. D.h. wenn wir den $k$-ten Wert der Haupdiagonale relativ maximieren wollen, muss: $|a_{i,k}|/{\sum }_{\beta =k}^{n+1}|a_{i,\beta }|$ maximal sein. Wobei $i\le k$ die möglichen Zeilen sind, die wir in die Hauptdiagonale schreiben können.

Die Summe oben geht bis $n+1$, da wir die Strategie üblicherweise nutzen, um ein Gleichungssystem aufzulösen.

Q: LR-Strategie Normale Spaltenmax-Pivot-Strategie. Nach was wird maximiert? A: $|a_{i,k}|$

Q: LR-Strategie Relative Spaltenmax-Pivot-Strategie. Nach was wird maximiert? A: $|a_{i,k}|/{\sum }_{\beta =k}^{n+1}|a_{i,\beta }|$