Direkt zum Inhalt

Lexikon der Mathematik: Singulärwertzerlegung

die Zerlegung einer Matrix A ∈ ℝm×n in das Produkt A = UVT, wobei U ∈ ℝm×m und V ∈ ℝn×m orthogonale Matrizen sind, und

Abbildung 1 zum Lexikonartikel Singulärwertzerlegung
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

die aus den von Null verschiedenen singulären Werten σ1,…,σr von A gebildete Matrix. r ist der Rang von A.

Weiter gelten mit der Bezeichnung U = [u1, u2,…,um] und V = [v1, v2,…,vn] folgende Beziehungen: \begin{eqnarray}\begin{array}{rcl}\ker (A) & = & \text {Span}\{{v}_{r+1},\mathrm{\ldots},{v}_{n}\},\\\text {im}(A) & = & \text {Span}\{{u}_{1},\mathrm{\ldots},{u}_{r}\},\\ A & = & \displaystyle \sum _{i-i}^{r}{\sigma}_{i}{u}_{i}{v}_{i}^{T},\\ ||A|{|}_{2} & = & {\sigma}_{1},\\ ||A|{|}_{F}^{2} & = & {\sigma}_{1}^{2}+{\sigma}_{2}^{2}+\mathrm{\ldots}+{\sigma}_{p}^{2},p=\min \{n,m\}.\end{array}\end{eqnarray} Die Spalten von U geben m orthonormale Eigenvektoren der symmetrischen (m × m)-Matrix AAT an, die Spalten von V n orthonormale Eigenvektoren der symmetrischen (n × n) -Matrix ATA. Die Singulärwertzerlegung kann zur Rangbestimmung einer Matrix und zur Lösung eines überbestimmten linearen Gleichungssystems mittels der Methode der kleinsten Quadrate eingesetzt werden.

Ein gebräuchlicher Algorithmus zur Berechnung der Singulärwertzerlegung besteht aus zwei Schritten. (Zur Vereinfachung sei mn angenommen, andernfalls betrachte man AT statt A). Im ersten Schritt wird die Matrix A durch Transformation mit Householder-Matrizen (oder Givens- Matrizen) in eine Bidiagonalgestalt überführt, d. h. in eine Matrix B, bei welcher lediglich die Dia-gonalelememte bii und die oberen Nebendiago-nalelemente bi,i+1 ungleich 0 sind. Dazu führt man abwechselnd Spalten- und Zeileneliminationen mit Householder-Matrizen (oder Givens- Rotationen) durch: Zunächst bestimmt man eine (m × m)-Householder-Matrix P1, welche die Elemente der ersten Spalte von A unterhalb des Matrixelements a11 annulliert: \begin{eqnarray}\begin{array}{cccc}{P}_{1}A & = & {P}_{1} & \left(\begin{array}{cccc}x & x & x & x\\ x & x & x & x\\ x & x & x & x\\ x & x & x & x\\ x & x & x & x\end{array}\right)\\ & = & {A}^{(1)} & =\left(\begin{array}{cccc}{b}_{11} & x & x & x\\ 0 & x & x & x\\ 0 & x & x & x\\ 0 & x & x & x\\ 0 & x & x & x\end{array}\right).\end{array}\end{eqnarray} Anschließend bestimmt man eine (n × n)-Householder-Matrix Q1 so, daß die Elemente auf den Positionen (1, 3), (1, 4),…,(1, n) der ersten Zeile von A(2) = A(1)Q1 verschwinden: \begin{eqnarray}{A}^{(2)}=\left(\begin{array}{cccc}{b}_{11} & {b}_{12} & 0 & 0\\ 0 & x & x & x\\ 0 & x & x & x\\ 0 & x & x & x\\ 0 & x & x & x\end{array}\right).\end{eqnarray} Allgemein erhält man im ersten Schritt eine Matrix A(2) der Form

Abbildung 2 zum Lexikonartikel Singulärwertzerlegung
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

mit einer (m − 1) × (n − 1)-Matrix Ã. Man behandelt nun die Matrix A auf die gleiche Weise wie à und erhält so nach n Reduktionsschritten eine (m × n)-Bidiagonalmatrix B \begin{eqnarray}B=\left(\begin{array}{c}\tilde{B}\\ 0\end{array}\right),\quad \tilde{B}=\left(\begin{array}{cccc}{b}_{11} & {b}_{12} & & \\ & {b}_{22} & \ddots & \\ & & \ddots & \mathop{{b}_{n-1,n}}\limits_{bnn}\end{array}\right),\end{eqnarray} wobei B = PnPn-1 · · ·P1AQ1Q2 · · · Qn-2. Da nur Orthogonaltransformationen verwendet wurden, besitzen B und A dieselben singulären Werte. Im zweiten Schritt wird nun die Singulärwertzerlegung von B = UVT berechnet. Dann ist \begin{eqnarray}A={p}^{T}U\sum {V}^{T}{Q}^{T}\end{eqnarray} mit P = PnPn-1 · · · P und Q = Q1Q2 · · · Qn-2 eine Singulärwertzerlegung von A. Die Singulärwertzerlegung von B kann durch Anwendung des QR-Algorithmus auf die Matrix BTB bestimmt werden. Die explizite Berechnung von BTB kann dabei vermieden werden, sodaß man in der Praxis iterativ mittels Orthogonaltransformationen eine Folge von Bidiagonalmatrizen berechnet, welche gegen eine Diagonalmatrix konvergieren.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.