Ränderung

Als Ränderung (engl.: Bordering Method) bezeichnet m​an ein Verfahren z​ur Verbesserung d​er Lösungseigenschaften linearer Gleichungssysteme. Das Verfahren k​ommt in d​er linearen Algebra u​nd der Numerik z​ur Anwendung.

Einem linearen Gleichungssystem

${\displaystyle Ax=b}$

mit singulärer oder schlecht konditionierter Systemmatrix ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ kann man durch Hinzufügen von Zeilen und Spalten zu ${\displaystyle A}$ und entsprechendes Vergrößern von ${\displaystyle x}$ und ${\displaystyle b}$ ein erweitertes lineares Gleichungssystem zuordnen, bei dem die Systemmatrix gut konditioniert (also auch regulär) ist. Die einfachen Beispiele in den nächsten zwei Abschnitten sollen das verdeutlichen. Die durch Zeilen und Spalten ergänzte Systemmatrix bezeichnet man auch als geränderte Matrix.

Beispiel (Regularisierung)

Gegeben s​ei das Gleichungssystem

${\displaystyle (0)(x_{1})=(1)}$

mit der ${\displaystyle 1\times 1}$-Systemmatrix ${\displaystyle A=(0)}$, dem Einervektor ${\displaystyle x=(x_{1})}$ der Unbekannten und der rechten Seite ${\displaystyle b=(1)}$. Dieses kann durch Ränderung der Systemmatrix mit der Spalte ${\displaystyle \left({\begin{matrix}1\\0\end{matrix}}\right)}$ und der Zeile ${\displaystyle \left({\begin{matrix}1&0\end{matrix}}\right)}$ regularisiert werden:

${\displaystyle \left({\begin{matrix}0&{\overline {1}}\\{\overline {1}}&{\overline {0}}\end{matrix}}\right)\left({\begin{matrix}x_{1}\\{\overline {x}}_{2}\end{matrix}}\right)=\left({\begin{matrix}1\\{\overline {0}}\end{matrix}}\right).}$

Die zu dem ursprünglichen System hinzugekommenen Einträge sind überstrichen. Das geränderte System hat die eindeutige Lösung ${\displaystyle {\overline {x}}\in \mathbb {R} ^{2}}$ mit ${\displaystyle x_{1}=0,\;{\overline {x}}_{2}=1}$. Davon ist die durch die Ränderung dem ursprünglichen Problem zugeordnete Lösung ${\displaystyle x_{1}=0}$. Die Größe von ${\displaystyle {\overline {x}}_{2}}$ drückt aus, wie stark der regularisierende Einfluss der Ränderung ist.

Beispiel (Verbesserung der Kondition)

In diesem Beispiel sei ${\displaystyle b\in \mathbb {R} ^{2}}$ ein bzgl. der euklidischen Norm mit 10 % Fehler behafteter Messwertvektor aus dem mit Hilfe der Gleichung

${\displaystyle {\begin{matrix}\underbrace {\begin{pmatrix}1&10\\0&1\end{pmatrix}} &{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}&=&{\begin{pmatrix}b_{1}\\b_{2}\end{pmatrix}}&\\A\end{matrix}}}$

die Größen ${\displaystyle x_{1},x_{2}}$ ermittelt werden sollen. Für ${\displaystyle b={\begin{pmatrix}1\\0\end{pmatrix}}}$ ergibt sich die Lösung ${\displaystyle x={\begin{pmatrix}1\\0\end{pmatrix}}.}$ Für die um ca 10 % abweichende (also innerhalb der Fehlertoleranz liegende) rechte Seite ${\displaystyle b={\begin{pmatrix}1\\0.1\end{pmatrix}}}$ ermittelt man die vollkommen andere Lösung ${\displaystyle x={\begin{pmatrix}0\\0.1\end{pmatrix}}}$.

Ein Maß dafür, wie stark sich relative Fehler ${\displaystyle {\frac {|\Delta b|}{|b|}}}$ in der Messung auf den relativen Fehler ${\displaystyle {\frac {|\Delta x|}{|x|}}}$ des Rechenergebnisses auswirken, ist die Kondition der Systemmatrix ${\displaystyle A}$

${\displaystyle \operatorname {cond} (A)=\max \left\{\left.{\frac {\frac {|\Delta x|}{|x|}}{\frac {|\Delta b|}{|b|}}}\;\right|\;b,\Delta b\in \mathbb {R} ^{n}\setminus \{0\},\;Ax=b,\;A(x+\Delta x)=(b+\Delta b)\right\}.}$

Für die spezielle Wahl von ${\displaystyle A}$ aus diesem Beispiel ergibt sich ${\displaystyle \operatorname {cond} (A)\approx 102}$. Relative Fehler in den Messdaten ${\displaystyle b}$ können sich also durch die schlechte Kondition der Matrix ${\displaystyle A}$ ca. hundertfach im relativen Fehler der aus diesen Daten berechneten Größen ${\displaystyle x}$ niederschlagen.

Dieser Effekt ist im folgenden Bild für die oben vorgegebenen rechten Seiten grafisch veranschaulicht. Aus dem oberen Teil des Bildes erkennt man, dass die zwei Spaltenvektoren ${\displaystyle a^{(1)}:=\left({\begin{matrix}1\\0\end{matrix}}\right)}$ und ${\displaystyle a^{(2)}:={\begin{pmatrix}10\\1\end{pmatrix}}}$ von ${\displaystyle A}$ beinahe linear abhängig voneinander sind.

Dadurch fallen die im unteren Teil des Bildes rot dargestellten zwei rechten Seiten ${\displaystyle b^{(1)}}$ und ${\displaystyle b^{(2)}}$, die sehr nahe beieinander liegen, in die Bildräume unterschiedlicher Spalten von ${\displaystyle A}$ und die Koeffizienten ${\displaystyle x_{1},x_{2}}$ in

${\displaystyle a^{(1)}x_{1}+a^{(2)}x_{2}=Ax=b}$

unterscheiden sich beim Wechsel von ${\displaystyle b=b^{(1)}}$ zu ${\displaystyle b=b^{(2)}}$ stark voneinander.

Effekt einer Ränderung: Das Hinzufügen einer zusätzlichen Zeile zu ${\displaystyle A}$ entspricht der Erweiterung des Wertebereiches von ${\displaystyle A}$ um eine Dimension vom ${\displaystyle \mathbb {R} ^{2}}$ zum ${\displaystyle \mathbb {R} ^{3}}$ und mit dem Ergänzen einer Spalte kommt ein neuer Spaltenvektor ${\displaystyle {\overline {a}}^{(3)}}$ hinzu. Durch geschickte Wahl der zusätzlichen Komponenten ${\displaystyle {\overline {a}}_{3}^{(1)},\;{\overline {a}}_{3}^{(2)}}$ und des zusätzlichen Spaltenvektors ${\displaystyle {\overline {a}}^{(3)}}$ erreicht man, dass die Spaltenvektoren der geränderten Matrix ${\displaystyle {\overline {A}}:=\left({\overline {a}}^{(1)}\;{\overline {a}}^{(2)}\;{\overline {a}}^{(3)}\right)}$ wesentlich besser voneinander separiert werden. Genauer wählt man die neuen Freiheitsgrade möglichst so, dass die Spalten ${\displaystyle {\overline {a}}^{(1)},{\overline {a}}^{(2)},{\overline {a}}^{(3)}}$ der geränderten Matrix ${\displaystyle {\overline {A}}}$ senkrecht aufeinander stehen und die gleiche Länge haben.

Im Beispiel erreicht m​an das näherungsweise m​it der Ränderung

${\displaystyle {\underline {A}}:={\begin{pmatrix}1&10&{\underline {0}}\\0&1&{\underline {10}}\\{\underline {10}}&{\underline {0}}&{\underline {0}}\end{pmatrix}}.}$

Die Lage der Spaltenvektoren der geränderten Matrix ${\displaystyle {\underline {A}}}$ im ${\displaystyle \mathbb {R} ^{3}}$ ist im folgenden Bild veranschaulicht.

Für d​as geränderte System

${\displaystyle {\underline {A}}{\underline {x}}={\underline {b}}}$

ergeben sich mit den geränderten rechten Seiten ${\displaystyle {\underline {b}}^{(1)}=(1,0,0)}$ und ${\displaystyle {\underline {b}}^{(2)}=(1,0.1,0)}$ jeweils die Lösungen ${\displaystyle {\underline {x}}^{(1)}=(0,0.1,-0.01)}$ bzw. ${\displaystyle {\underline {x}}^{(2)}=(0,0.1,0)}$. Die für die Messaufgabe wesentlichen Komponenten ${\displaystyle x_{1}}$ und ${\displaystyle x_{2}}$ ändern sich also durch die 10 %ige Störung von ${\displaystyle b}$ überhaupt nicht.

Das i​st in d​en folgenden z​wei Bildern n​och einmal veranschaulicht.

Die Konditionszahl der geränderten Matrix hat sich auf ${\displaystyle \operatorname {cond} ({\underline {A}})\approx 1.15}$ verringert. Der relative Fehler wird sich durch die Berechnung von ${\displaystyle {\underline {x}}}$ aus den Messwerten ${\displaystyle {\underline {b}}}$ also nur noch höchstens um ca. 15 % verschlechtern.

In diesem motivierenden Beispiel wurde die Ränderung sehr einfach gehalten. Durch eine geschicktere Wahl der Ränderung ist erreichbar, dass sich der relative Fehler durch die Berechnung von ${\displaystyle x}$ aus ${\displaystyle b}$ überhaupt nicht mehr verschlechtert, dass also ${\displaystyle \operatorname {cond} ({\underline {A}})=1}$ gilt.

Regularisierung

Sei ${\displaystyle A}$ eine reelle ${\displaystyle m\times n}$-Matrix und ${\displaystyle b}$ ein dazu passender ${\displaystyle m}$-dimensionaler Spaltenvektor. Eine geränderte Matrix

${\displaystyle \left({\begin{matrix}A&A_{\rm {ro}}\\A_{\rm {lu}}&0\end{matrix}}\right)}$

mit passenden Matrizen ${\displaystyle A_{\rm {ro}}}$ und ${\displaystyle A_{\rm {lu}}}$ ist genau dann regulär, wenn die Zeilen von ${\displaystyle A_{\rm {lu}}}$ eine Basis des Kerns von ${\displaystyle A}$ bilden und die Spalten von ${\displaystyle A_{\rm {ro}}}$ ein minimales System von Spalten ist, das zusammen mit den Spalten von ${\displaystyle A}$ den ${\displaystyle \mathbb {R} ^{m}}$ aufspannt. In diesem Fall lässt sich das geränderte System

${\displaystyle \left({\begin{matrix}A&A_{\rm {ro}}\\A_{\rm {lu}}&0\end{matrix}}\right)\left({\begin{matrix}x\\x_{u}\end{matrix}}\right)=\left({\begin{matrix}b\\0\end{matrix}}\right)}$

eindeutig lösen und die Dimension der (quadratischen) geränderten Matrix ist ${\displaystyle m+\operatorname {def} (A)}$ (hierbei ist ${\displaystyle \operatorname {def} (A)}$ der Defekt von ${\displaystyle A}$).

Je nach Wahl der Matrizen ${\displaystyle A_{\rm {ro}}}$ und ${\displaystyle A_{\rm {lu}}}$ kann man verschiedene Aufgaben lösen. Spannen zum Beispiel die Zeilen von ${\displaystyle A_{\rm {lu}}}$ den Kern von ${\displaystyle A}$ auf und die Spalten von ${\displaystyle A_{\rm {ro}}}$ das orthogonale Komplement des Bildes von ${\displaystyle A}$, so ist ${\displaystyle x}$ aus der Lösung des geränderten Gleichungssystems gerade ${\displaystyle A^{+}b}$ mit der Pseudoinversen ${\displaystyle A^{+}}$ von ${\displaystyle A}$. Den Kern von ${\displaystyle A}$ kann man mit Hilfe des Gaußschen Eliminationsverfahrens berechnen und das orthogonale Komplement des Bildes von ${\displaystyle A}$ berechnet man günstigerweise als Kern von ${\displaystyle A^{T}}$.

Optimale Ränderung

Die Idee aus dem letzten Abschnitt wird hier aufgegriffen und eine beliebige Matrix ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ so gerändert, dass die Spalten der erweiterten Matrix ${\displaystyle {\overline {A}}}$ alle senkrecht aufeinander stehen und die gleiche euklidische Norm haben. Die erweiterte Matrix ${\displaystyle {\bar {A}}}$ ist dann das Produkt des größten Singulärwertes von ${\displaystyle A}$ mit einer orthogonalen Matrix und hat damit die minimal mögliche Konditionszahl eins. Die hier benutzte Darstellung orientiert sich an [1].

Singulärwertzerlegung als Hilfsmittel zur Ränderung

Die Struktur der Systemmatrix kann man mit Hilfe einer aus der Singulärwertzerlegung ${\displaystyle A=U\Sigma V^{T}}$ von ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ gewonnenen Koordinatentransformation ${\displaystyle b_{U}:=U^{T}b}$, ${\displaystyle x_{V}:=V^{T}x}$ vereinfachen. Die neue Systemmatrix ${\displaystyle \Sigma \in \mathbb {R} ^{m\times n}}$ hat dann sehr viele Nulleinträge. Nur die Elemente ${\displaystyle \Sigma _{1,1},\ldots ,\Sigma _{r,r}}$ sind mit Nichtnullelementen, nämlich den Singulärwerten ${\displaystyle \Sigma _{1,1}:=\sigma _{1}\geq \Sigma _{2,2}:=\sigma _{2}\ldots \geq \Sigma _{r,r}:=\sigma _{r}>0}$, belegt. Hierbei ist ${\displaystyle r}$ der Rang der Matrix ${\displaystyle A}$.

Die Transformationsmatrizen ${\displaystyle U\in \mathbb {R} ^{m\times m}}$ und ${\displaystyle V\in \mathbb {R} ^{n\times n}}$ sind orthogonal und damit normerhaltend ${\displaystyle |b_{U}|=|U^{T}b|}$, ${\displaystyle |x_{V}|=|V^{T}x|}$. Daraus folgt, dass die transformierte Systemmatrix ${\displaystyle \Sigma }$ die gleiche Kondition hat, wie die originale Systemmatrix ${\displaystyle A}$.

Eine Erweiterung

${\displaystyle {\bar {\Sigma }}:={\begin{pmatrix}\Sigma &{\bar {\Sigma }}_{\rm {ro}}\\{\bar {\Sigma }}_{\rm {lu}}&{\bar {\Sigma }}_{\rm {ru}}\end{pmatrix}}\in \mathbb {R} ^{{\bar {m}}\times {\bar {n}}}\qquad {\mbox{ mit }}{\bar {m}}\geq m{\mbox{ und }}{\bar {n}}\geq n}$

der Matrix ${\displaystyle \Sigma }$ um Matrixblöcke (zueinander passender Dimensionen) ${\displaystyle {\bar {\Sigma }}_{\rm {ro}}\in \mathbb {R} ^{{\bar {m}}\times ({\bar {n}}-n)},{\bar {\Sigma }}_{\rm {lu}}\in \mathbb {R} ^{({\bar {m}}-m)\times n},{\bar {\Sigma }}_{\rm {ru}}^{({\bar {m}}-m)\times ({\bar {n}}-n)}}$ entspricht eine Ränderung der Matrix ${\displaystyle A}$, wenn man die Transformationsmatrizen ${\displaystyle U}$ und ${\displaystyle V}$ passend durch Teile der Einheitsmatrix ergänzt:

${\displaystyle {\bar {A}}:={\begin{pmatrix}U&\mathbf {0} _{m\times ({\bar {m}}-m)}\\\mathbf {0} _{({\bar {m}}-m)\times m}&\mathbf {1} _{({\bar {m}}-m)\times ({\bar {m}}-m)}\end{pmatrix}}{\begin{pmatrix}\Sigma ^{(11)}&{\bar {\Sigma }}_{\mathrm {ro} }\\{\bar {\Sigma }}_{\mathrm {lu} }&{\bar {\Sigma }}_{\mathrm {ru} }\end{pmatrix}}{\begin{pmatrix}V^{T}&\mathbf {0} _{n\times ({\bar {n}}-n)}\\\mathbf {0} _{({\bar {n}}-n)\times n}&\mathbf {1} _{({\bar {n}}-n)\times ({\bar {n}}-n)}\end{pmatrix}}={\begin{pmatrix}U\Sigma V^{T}&U{\bar {\Sigma }}_{\mathrm {ro} }\\{\bar {\Sigma }}_{\mathrm {lu} }V^{T}&{\bar {\Sigma }}_{\mathrm {ru} }\end{pmatrix}}={\begin{pmatrix}A&U{\bar {\Sigma }}_{\mathrm {ro} }\\{\bar {\Sigma }}_{\mathrm {lu} }V^{T}&{\bar {\Sigma }}_{\mathrm {ru} }\end{pmatrix}}}$

Die erweiterten Transformationsmatrizen ${\displaystyle {\bar {V}}:={\begin{pmatrix}V&\mathbf {0} \\\mathbf {0} &\mathbf {1} \end{pmatrix}}}$ und ${\displaystyle {\bar {U}}:={\begin{pmatrix}U&\mathbf {0} \\\mathbf {0} &\mathbf {1} \end{pmatrix}}}$ sind wieder orthogonal, womit die Kondition der erweiterten Systemmatrix ${\displaystyle {\bar {A}}}$ mit der der Matrix ${\displaystyle {\bar {\Sigma }}}$ übereinstimmt.

Im Folgenden brauchen a​lso nur n​och Matrizen untersucht werden, d​ie eine Systemmatrix m​it der (von d​er Singulärwertzerlegung h​er bekannten) Struktur

${\displaystyle \Sigma _{i,j}=\left\{{\begin{matrix}\sigma _{i,i}&{\mbox{ wenn }}&i=j\leq r\\0&{\mbox{ sonst }}\end{matrix}}\right.}$

mit einer ganzen Zahl ${\displaystyle 0\leq r\leq \min(m,n)}$ haben.

Ergänzung einer rechteckigen Matrix zu einer quadratischen

Hier wird nur die Ränderung von Matrizen mit mehr Zeilen als Spalten beschrieben (${\displaystyle m>n}$). Durch Transposition kann man die Aussagen auf Matrizen mit mehr Spalten als Zeilen übertragen. Mit den Aussagen aus dem vorhergehenden Abschnitt ist klar, dass man sich auf die Untersuchung von Matrizen der Form

${\displaystyle \Sigma =\left({\begin{matrix}D\\\mathbf {0} \end{matrix}}\right)}$

beschränken kann, wobei ${\displaystyle D}$ eine positiv semidefinite Diagonalmatrix und ${\displaystyle \mathbf {0} }$ eine Nullmatrix mit der gleichen Anzahl an Spalten wie ${\displaystyle D}$ ist. Zunächst wird vorausgesetzt, dass ${\displaystyle D}$ keine Nullmatrix ist. Das maximale Diagonalelement ${\displaystyle d_{\max }}$ von ${\displaystyle D}$ ist also größer null. Dann ist es günstig, die fehlenden Spalten durch die an diese Spaltenpositionen gehörigen Spalten der mit ${\displaystyle d_{\max }}$ skalierten Einheitsmatrix zu ergänzen:

${\displaystyle {\bar {\Sigma }}=\left({\begin{matrix}D&\mathbf {0} \\\mathbf {0} &d_{\max }\mathbf {1} \end{matrix}}\right).}$

Falls ${\displaystyle D}$ regulär ist, trifft das auch für die geränderte Matrix ${\displaystyle {\bar {\Sigma }}}$ zu. Man hat also die Matrix in diesem Falle regularisiert.

Nachdem man die Rechteckmatrix so zu einer quadratischen ergänzt hat, kann man die im nächsten Abschnitt beschriebene Ränderung benutzen, um die Matrix besser zu konditionieren (oder, falls ${\displaystyle D}$ singulär ist, zu regularisieren). Dort wird sich herausstellen, dass die Wahl von ${\displaystyle d_{\max }}$ als Skalierungsfaktor günstig ist, da man die Norm dieser Spalten dann nicht mehr künstlich durch eine Ränderung vergrößern muss.

Optimale Ränderung einer quadratischen Matrix

Im vorhergehenden Abschnitt wurde beschrieben, wie man eine rechteckige Matrix durch Ränderung günstig zu einer quadratischen ergänzen kann. Hier wird nun darauf eingegangen, wie sich die Kondition einer quadratischen Matrix verbessern oder im singulären Fall die Matrix regularisieren lässt.

Der Unterabschnitt zur Singulärwertzerlegung zeigt, dass man sich dabei auf die Ränderung von Diagonalmatrizen ${\displaystyle \Sigma =\operatorname {diag} (\sigma _{1},\ldots ,\sigma _{r},0\ldots ,0)}$ beschränken kann.

Die Spaltenvektoren der Matrix ${\displaystyle \Sigma }$ stehen bereits senkrecht aufeinander. Man muss sie nur noch geeignet verlängern, damit sie normgleich werden. Dabei fängt man mit dem letzten Spaltenvektor an, dessen Komponente ${\displaystyle \Sigma _{n,n}}$ den kleinsten Wert der Diagonalelemente von ${\displaystyle \Sigma }$ hat. Zunächst ergänzt man ${\displaystyle \Sigma }$ durch eine Zeile ${\displaystyle z_{n+1,\bullet }:=(0\;\ldots \;0\;z_{n+1,n})\in \mathbb {R} ^{1\times n}}$, was einer Erweiterung des Spaltenvektorraumes um eine Dimension entspricht (der Punkt ${\displaystyle {}_{\bullet }}$ steht hier als Stellvertreter für den Spaltenindex). In dieser zusätzlichen Dimension verlängert man den letzten Spaltenvektor der erweiterten Matrix so weit, dass er die gleiche euklidische Länge wie der erste (längste) Spaltenvektor von ${\displaystyle \Sigma }$ bekommt (also die Länge ${\displaystyle \sigma _{1}}$):

${\displaystyle z_{n+1,n}:={\sqrt {\sigma _{1}^{2}-\Sigma _{n,n}^{2}}}.}$

Die Spaltenvektoren der erweiterten Matrix ${\displaystyle \left({\begin{matrix}\Sigma \\z_{n+1,\bullet }\end{matrix}}\right)}$ bleiben dadurch orthogonal zueinander. Um wieder eine quadratische Matrix zu erhalten, muss man noch eine Spalte ${\displaystyle s_{\bullet ,n+1}}$ ergänzen. Dazu wählt man günstigerweise eine Spalte mit

${\displaystyle s_{i,n}:=\left\{{\begin{matrix}z_{n+1,n}&{\mbox{ wenn }}&i=n\\-\Sigma _{n,n}&{\mbox{ wenn }}&i=n+1\\0&{\mbox{ sonst}}&\end{matrix}}\right.}$

Die Spalte ${\displaystyle s_{\bullet ,n+1}}$ hat die gewünschte Norm ${\displaystyle \sigma _{1}}$ und steht wiederum senkrecht auf allen anderen Spalten der erweiterten Matrix

${\displaystyle {\bar {\Sigma }}:=\left({\begin{matrix}\left.{\begin{matrix}\Sigma \\{\overline {z_{n+1,\bullet }}}\end{matrix}}\right|&s_{\bullet ,n+1}\end{matrix}}\right)}$.

Durch analoges Ergänzen weiterer Zeilen u​nd Spalten k​ann man sukzessive d​ie Norm a​ller Spaltenvektoren d​er erweiterten Matrix angleichen. Wie gewünscht, i​st das Ergebnis e​ine Systemmatrix, d​eren Spalten a​lle orthogonal aufeinander stehen u​nd die gleiche Norm haben.

Weblinks

• G.D. Kim: Bordering Method. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (englisch, online).

Einzelnachweise

1. Uwe Schnabel: Minimierung der Konditionszahl durch Ränderung von Matrizen. Preprint IOKOMO-05-2001, TU Dresden. 2001.