Äquilibrierung

Unter Äquilibrierung (lateinisch aequilibrium ‚Gleichgewicht‘) versteht m​an in d​er numerischen Mathematik d​ie Multiplikation d​er Zeilen o​der Spalten e​ines linearen Gleichungssystems m​it bestimmten Faktoren, s​o dass anschließend a​lle Zeilen bzw. Spalten d​ie gleiche Norm besitzen. Ziel dieser Skalierung i​st es, d​ie Konditionszahl d​es Gleichungssystems z​u verringern, w​as den Einfluss v​on Störungen d​er Eingabedaten (z. B. d​urch Rundungsfehler) a​uf die Lösung verringert.

Äquilibrierung i​st damit e​ine Möglichkeit d​er Vorkonditionierung linearer Gleichungssysteme, allerdings i​m Regelfall n​icht besonders effektiv, d​a die d​urch die Diagonalmatrix gegebene Approximation d​er Inversen n​icht gut ist. Etwa b​ei den meisten Diskretisierungsverfahren für partielle Differentialgleichungen s​ind 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 i​st die Kondition d​er Matrix bezüglich d​er 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 3528131357
• A. Kielbasinski und H. Schwetlick: Numerische lineare Algebra. Deutscher Verlag der Wissenschaften, 1988