Äquilibrierung

Unter Äquilibrierung (lateinisch aequilibrium ‚Gleichgewicht‘) versteht man in der numerischen Mathematik die Multiplikation der Zeilen oder Spalten eines linearen Gleichungssystems mit bestimmten Faktoren, so dass anschließend alle Zeilen bzw. Spalten die gleiche Norm besitzen. Ziel dieser Skalierung ist es, die Konditionszahl des Gleichungssystems zu verringern, was den Einfluss von Störungen der Eingabedaten (z. B. durch Rundungsfehler) auf die Lösung verringert.

Äquilibrierung ist damit eine Möglichkeit der Vorkonditionierung linearer Gleichungssysteme, allerdings im Regelfall nicht besonders effektiv, da die durch die Diagonalmatrix gegebene Approximation der Inversen nicht gut ist. Etwa bei den meisten Diskretisierungsverfahren für partielle Differentialgleichungen sind andere Vorkonditionierer vorzuziehen.

Mathematische Beschreibung

Ziel der Äquilibrierung ist das Ersetzen des Gleichungssystems ${\displaystyle Ax=b}$ durch ein äquivalentes Gleichungssystem mit Systemmatrix ${\displaystyle A^{*}}$ mit möglichst kleiner Konditionszahl. Dabei hängt die Konditionszahl von der Matrixnorm ab und diese Verkleinerung gelingt nicht zwingend bezüglich jeder Matrixnorm. Man kann allerdings für die Zeilensummennorm und die Spaltensummennorm optimale Skalierungen angeben.

Zeilenäquilibrierung

Eine Zeilenäquilibrierung entspricht der Multiplikation der Matrix A von links mit einer Diagonalmatrix D. Durch Skalierung der Zeilen mit der Betragssummennorm wird die Kondition ${\displaystyle \kappa _{\infty }(A^{*})=\Vert A^{*}\Vert _{\infty }\cdot \Vert A^{*-1}\Vert _{\infty }}$ des skalierten Gleichungssystems bezüglich der Zeilensummennorm

${\displaystyle \Vert A^{*}\Vert _{\infty }=\max _{i=1}^{n}\sum _{j=1}^{n}{|a_{ij}^{*}|}}$

optimiert. Es gibt also keine reguläre Diagonalmatrix ${\displaystyle {\hat {D}}}$ derart, dass ${\displaystyle \kappa _{\infty }(A^{*})>\kappa _{\infty }({\hat {D}}A^{*})}$. Dabei wird jede Zeile ${\displaystyle i}$ der Matrix ${\displaystyle A}$ durch ihre Zeilensumme ${\displaystyle \textstyle \sum _{j=1}^{n}\vert a_{ij}\vert }$ geteilt (diese Summe ist größer als 0, da die Matrix als regulär vorausgesetzt wurde).

Spaltenäquilibrierung

Eine Äquilibrierung der Spalten entspricht der Multiplikation der Matrix A von rechts mit einer Diagonalmatrix. Skalierung der Spalten über die Betragssummennorm, indem man durch die Spaltensummen ${\displaystyle \textstyle \sum _{i=1}^{n}\vert a_{ij}\vert }$ teilt, liefert eine optimale Skalierung bezüglich der Spaltensummennorm in dem Sinne, dass keine Diagonalmatrix ${\displaystyle {\hat {D}}}$ existiert derart, dass ${\displaystyle \kappa _{1}(A^{*})>\kappa _{1}(A^{*}{\hat {D}})}$.

Beispiel

Anhand eines kurzen Beispiels soll die Zeilenäquilibrierung demonstriert werden. Gegeben sei die Matrix A zum linearen Gleichungssystem ${\displaystyle Ax=b}$.

${\displaystyle A={\begin{pmatrix}1&2\\3&4\end{pmatrix}}}$ mit der Inversen ${\displaystyle A^{-1}={\begin{pmatrix}-2&1\\{\frac {3}{2}}&-{\frac {1}{2}}\end{pmatrix}}}$

Damit ist die Kondition der Matrix bezüglich der Zeilensummennorm

${\displaystyle \kappa _{\infty }(A)=\Vert A\Vert _{\infty }\cdot \Vert A^{-1}\Vert _{\infty }=7\cdot 3=21.}$

Bei der Zeilenäquilibrierung wird nun die folgende Diagonalmatrix ${\displaystyle D={\begin{pmatrix}{\frac {1}{3}}&0\\0&{\frac {1}{7}}\end{pmatrix}}}$ (aufgestellt wie oben beschrieben) von links heranmultipliziert. Damit ergibt sich

${\displaystyle A^{*}=DA={\begin{pmatrix}{\frac {1}{3}}&{\frac {2}{3}}\\{\frac {3}{7}}&{\frac {4}{7}}\end{pmatrix}}}$ mit der Inversen ${\displaystyle A^{*-1}={\begin{pmatrix}-6&7\\{\frac {9}{2}}&-{\frac {7}{2}}\\\end{pmatrix}}}$

Die Kondition der Matrix ${\displaystyle A^{*}}$ berechnet sich zu

${\displaystyle \kappa _{\infty }(A^{*})=\Vert A^{*}\Vert _{\infty }\cdot \Vert A^{*-1}\Vert _{\infty }=1\cdot 13=13,}$

was kleiner ist als die Kondition der Matrix ${\displaystyle A}$. Der Wert ${\displaystyle \Vert A^{*}\Vert _{\infty }}$ ist hierbei aufgrund der Definition von ${\displaystyle A^{*}}$ immer 1.

Literatur

• A. Meister: Numerik linearer Gleichungssysteme. 2. Auflage. Vieweg, 2005, ISBN 3-528-13135-7
• A. Kielbasinski und H. Schwetlick: Numerische lineare Algebra. Deutscher Verlag der Wissenschaften, 1988