Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] [Suche] Englische Flagge
Mathematik-Online-Kurs: Lineare Algebra - Normalformen - Singulärwertzerlegung

Pseudo-Inverse

[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]
Mit der Singulärwert-Zerlegung $ USV^*$ einer komplexen $ (m\times n)$-Matrix $ A$ lässt sich die Lösung des Ausgleichsproblems $ \vert Ax-b\vert\to\min$ mit minimaler Norm in der Form

$\displaystyle x = A^+b,\quad A^+ = VS^+U^*, $

schreiben, wobei $ A^+$ als Pseudo-Inverse von $ A$ bezeichnet wird, und

$\displaystyle S^+ = \operatorname{diag}(1/s_1,\ldots,1/s_k,0,\ldots,0), \quad k = \operatorname{Rang} A \,, $

die $ (n \times m)$-Diagonalmatrix mit den Kehrwerten der positiven singulären Werte ist.

Bezeichnen $ \{u_1,\ldots,u_m\}$ und $ \{v_1,\ldots,v_n\}$ die orthonormalen Basen aus den Spalten von $ U$ bzw. $ V$, so lässt sich die lineare Abbildung $ b\mapsto x= A^+b$ in der faktorisierten Form

$\displaystyle x = \sum_{\ell=1}^k \frac{1}{s_\ell}\,(u^*_\ell b)v_\ell $

darstellen. Daraus folgt insbesondere, dass

$\displaystyle \operatorname{Kern}A^+ = \operatorname{span} \{u_{k+1},\ldots,u_m\},\quad \operatorname{Bild}A^+ = \operatorname{span} \{v_1,\ldots,v_k\} $

und $ \Vert A^+\Vert _2 = 1/s_k$.
(Autoren: App/Höllig)

Wegen der Invarianz der $ 2$-Norm unter unitären Transformationen kann man $ Ax-b$ von links mit $ U^*$ multiplizieren. Mit

$\displaystyle c=U^* b,\quad y=V^* x $

ergibt sich das äquivalente Minimierungsproblem

$\displaystyle \vert Sy-c\vert = \left\vert \left( \begin{array}{c} s_1y_1-c_1 \... ...y_k-c_k \\ -c_{k+1} \\ \vdots \\ -c_m \end{array} \right) \right\vert \to\min. $

Das Minimum erhält man durch Lösung der ersten $ k$ Gleichungen:

$\displaystyle y_i=c_i/s_i,\ i=1,\ldots\,k\, . $

Wegen der Normtreue der unitären Matrix $ V$ $ (\vert x\vert = \vert y\vert)$ ist für die Lösung minimaler Norm

$\displaystyle y_{k+1}=\cdots=y_n=0\, . $

Insgesamt folgt

\begin{displaymath} y = S^+c,\quad s^+_{i,j} = \begin{cases} 1/s_i & \text{f\uml ur}\ i=j\le k \\ 0& \text{sonst .} \end{cases}\end{displaymath}

(Autoren: App/Höllig)
Es soll das Ausgleichproblem für

$\displaystyle A = \left(\begin{array}{rrr} 2 & -4 & 5 \\ 6 & 0 & 3 \\ 2 & -4 &... ...right),\quad b = \left(\begin{array}{r} 1 \\ 3 \\ -1 \\ 3 \end{array}\right)\, $

gelöst werden.

Zur Berechnung der Singulärwert-Zerlegung bestimmt man zunächst die Eigenwerte und Eigenvektoren von

$\displaystyle A^{\operatorname t}A = \left(\begin{array}{rrr} 80 & -16 & 56 \\ -16 & 32 & -40 \\ 56 & -40 & 68 \end{array}\right) $

und erhält

$\displaystyle s_1^2 = 144,\, s_2^2 = 36,\, s_3^2=0,\quad V = \frac{1}{3} \left(\begin{array}{rrr} 2 & 2 & -1 \\ -1 & 2 & 2 \\ 2 & -1 & 2 \end{array}\right)\, . $

Daraus folgt

$\displaystyle S = \left(\begin{array}{rrr} 12 & 0 & 0 \\ 0 & 6 & 0 \\ 0 & 0 & ... ... & -3 & 0 \\ 6 & 3 & 0 \\ 6 & -3 & 0 \\ 6 & 3 & 0 \end{array}\right) = US\, . $

Die ersten zwei Spalten von $ U$ erhält man durch Division der entsprechenden Spalten von $ AV$ durch die singulären Werte (dabei müssen Einheitsvektoren entstehen), die restlichen Spalten (nicht eindeutig bestimmt) durch Ergänzen zu einer orthonormalen Basis:

$\displaystyle U = \frac{1}{2} \left(\begin{array}{rrrr} 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & 1 & 1 \end{array}\right). $

Damit ist die Pseudo-Inverse

$\displaystyle A^+ = V \left(\begin{array}{cccc} \frac{1}{12} & 0 & 0 & 0 \\ 0 ... ...{rrrr} -2 & 6 & -2 & 6 \\ -5 & 3 & -5 & 3 \\ 4 & 0 & 4 & 0 \end{array}\right) $

und

$\displaystyle x = A^+b = \frac{1}{4}\left(\begin{array}{c} 2 \\ 1 \\ 0\end{array}\right) $

die Lösung minimaler Norm.
(Autoren: App/Höllig)
Zur Kontrolle topographischer Höhendaten $ h_i$ werden Höhendifferenzen $ d_{i,j}$ gemessen. Aufgrund von Messfehlern gilt in der Regel $ d_{i,j}\neq h_i-h_j$. Geeignete Höhenkorrekturen $ x_i$ lassen sich durch Lösen des Ausgleichsproblems

$\displaystyle \sum_{(i,j)}\Big(d_{i,j}-\big( (h_i+x_i)-(h_j+x_j) \big) \Big)^2 \longrightarrow \min \; . $

Zur Illustration der Vorgehensweise wird ein Modellproblem mit wenigen Daten gelöst.

\includegraphics[width=.7\linewidth]{topo.eps}
Für die Höhen und Differenzwerte

$\displaystyle h=(834, 561, 207, 9)^{\operatorname t}, \quad d=(276, 631, 822, 356, 549)^{\operatorname t} $

mit $ d=(d_{1,2}, d_{1,3}, d_{1,4}, d_{2,3}, d_{2,4})^{\operatorname t}$, erhält man das überbestimmte System

$\displaystyle A(h+x)=d, \quad A= \left(\begin{array}{rrrr} 1 & -1 & 0 & 0 \\ 1... ... 0 \\ 1 & 0 & 0 & -1 \\ 0 & 1 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{array} \right). $

Die gesuchte Lösung minimaler Norm ist dann

$\displaystyle x = A^+ (d - Ah) = \left( \begin{array}{c} 1 \\ -1 \\ -3 \\ 3 \end{array} \right). $

Die Berechnung der Minimum-Norm-Lösung ist für die betrachtete Anwendung sinnvoll, denn es soll eine möglichst kleine Korrektur bestimmt werden.
(Autor: Wipper)
[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]
  automatisch erstellt am 23.5.2011