Direkt zum Inhalt

Lexikon der Mathematik: Lösungsverifikation beim Singulärwertproblem

in der Intervallrechnung der Nachweis der Existenz eines singulären Wertes σ*σ(0) und eines zugehörigen rechten bzw. linken singulären Vektors \(u* =({u}_{i}^{* })\in {\bf u}^{(0)}\) bzw. \(v* =({v}_{i}^{* })\in {\bf v}^{(0)}\) zu einer reellen (m × n)-Matrix A. Dabei ist σ(0) ein gegebenes reelles kompaktes Intervall und u(0), v(0) sind entsprechende Intervallvektoren.

Die Aufgabenstellung wird meist ergänzt durch eine Eindeutigkeitsuntersuchung und durch eine Schrankenverbesserung bis hin zu einer Einschließung von σ*. und \({u}_{i}^{* }\), \({v}_{i}^{* }\) in enge Intervalle, bei denen möglichst viele führende Ziffern der Intervalluntergrenze mit den entsprechenden der Intervallobergrenze übereinstimmen (Zifferngarantie für σ*. und u*, v*!).

Für das skizzierte Problem kann man jedes Verfahren zur Lösungsverifikation bei nichtlinearer Gleichungssysteme mit \begin{eqnarray}f(u,v,\sigma )=\left(\begin{array}{c}Au-\sigma v\\ {A}^{T}v-\sigma u\\ {u}^{T}u-1\end{array}\right)\end{eqnarray} oder jedes Verfahren zur Lösungsverifikation beim algebraischen Eigenwertproblem für die Matrizen ATA bzw. AAT verwenden: Im ersten Fall nutzt man aus, daß (u*, v*, σ*) eine Nullstelle von f ist, und im zweiten, daß u*, \({({\sigma }^{* })}^{2}\) bzw. v*, \({({\sigma }^{* })}^{2}\) Eigenpaare von ATA bzw. AAT sind.

Als Alternative bietet sich die Funktion \begin{eqnarray}g({\rm{\Delta }}u,{\rm{\Delta }}v,{\rm{\Delta }}\sigma )=-Cf(\tilde{u},\tilde{v},\tilde{\sigma })\\ +(I-CB)\left(\begin{array}{c}{\rm{\Delta }}u\\ {\rm{\Delta }}v\\ {\rm{\Delta }}\sigma \end{array}\right)+\tilde{T}\left(\begin{array}{c}{\rm{\Delta }}u\\ {\rm{\Delta }}v\\ {\rm{\Delta }}\sigma \end{array}\right)\end{eqnarray} an, in der \((\tilde{u},\tilde{v},\tilde{\sigma })\) eine mit herkömmlichen Verfahren berechnete Näherung von (u*, v*, σ*), C eine präkonditionierende Matrix, Ik die (k × k)-Einheitsmatrix, \begin{eqnarray}\begin{array}{lll}B & = & \left(\begin{array}{ccc}A & -\tilde{\sigma }{I}_{m} & -\tilde{v}\\ -\tilde{\sigma }{I}_{n} & {A}^{T} & -\tilde{u}\\ 2{\tilde{u}}^{T} & 0 & 0\end{array}\right),\\ \tilde{T} & = & \left(\begin{array}{ccc}0 & 0 & {\rm{\Delta }}v\\ 0 & 0 & {\rm{\Delta }}u\\ {({\rm{\Delta }}u)}^{T} & 0 & 0\end{array}\right),\end{array}\end{eqnarray} und \begin{eqnarray}{({({\rm{\Delta }}x)}^{T},{\rm{\Delta }}\lambda )}^{T}={({(x-\tilde{x})}^{T},\lambda -\tilde{\lambda })}^{T}\end{eqnarray} den Fehler bezeichnen.

Für jedes Tripel (u*, v*, σ*) ist \begin{eqnarray}({\rm{\Delta }}{u}^{* },{\rm{\Delta }}{v}^{* },{\rm{\Delta }}{\sigma }^{* })=({u}^{* }-\tilde{u},{v}^{* }-\tilde{v},{\sigma }^{* }-\tilde{\sigma })\end{eqnarray}

Fixpunkt von g. Mit dem Intervallvektor \(({\bf \Delta \boldsymbol u},\,{\bf\Delta \boldsymbol v},\,{\bf\Delta \sigma} )=({\bf u}-\tilde{u},\,{\bf v}-\tilde{v},\,{\boldsymbol \sigma} -\tilde{\sigma })\) erhält man den folgenden Satz:

Mit den Bezeichnungen von oben, der Maximumsnorm ‖ · ‖und \(\varrho =||Cf(\tilde{u},\,\tilde{v},\,\tilde{\sigma })\,|{|}_{\infty }\), \(\hat{\sigma }=||I-CB\,|{|}_{\infty }\), \(\tau =\,||\,|C|\,\cdot \,{(1,\ldots,1,n)}^{T}|{|}_{\infty }\)gelte \(\hat{\sigma }\lt 1\)und \({\rm{\Delta }}={(1-\hat{\sigma })}^{2}-4\varrho \tau \ge 0\).

Dann sind die Zahlen \({\beta }^{-}=(1-\hat{\sigma }-\sqrt{{\rm{\Delta }}})/(2\tau )\)und \({\beta }^{+}=(1-\hat{\sigma }+\sqrt{{\rm{\Delta }}})/(2\tau )\)nicht negativ, g besitzt für jedes β ∈ [β, β+] in \begin{eqnarray}({\boldsymbol{\Delta }}{{\boldsymbol{u}}}^{(0)},{\boldsymbol{\Delta }}{{\boldsymbol{v}}}^{(0)},{\boldsymbol{\Delta }}{{\boldsymbol{\sigma }}}^{(0)})=([-\beta,\beta ],\ldots,[-\beta,\beta ])\end{eqnarray}mindestens einen Fixpunktu*, Δv*, Δσ*), und \((\tilde{u}+{\rm{\Delta }}u*,\,\tilde{v}+{\rm{\Delta }}v*,\,\tilde{\sigma }+{\rm{\Delta }}\sigma * )\)bildet ein Tripel aus einem singulären Wert und zugehörigen singulären Vektoren.

Startet man die Iteration \begin{eqnarray}\left(\begin{array}{c}{\boldsymbol{\Delta }}{{\boldsymbol{u}}}^{(k+1)}\\ {\boldsymbol{\Delta }}{{\boldsymbol{v}}}^{(k+1)}\\ {\boldsymbol{\Delta }}{{\boldsymbol{\sigma }}}^{(k+1)}\end{array}\right)=\text{g}\left({\boldsymbol{\Delta }}{{\boldsymbol{u}}}^{(k)},{\boldsymbol{\Delta }}{{\boldsymbol{v}}}^{(k)},{\boldsymbol{\Delta }}{{\boldsymbol{\sigma }}}^{(k)}\right),\,\,k=0,1,\ldots \,\,,\end{eqnarray}mit dem oben konstruierten Vektor, dann konvergieren die Iterierten gegen einen Intervallvektor \({({({\boldsymbol{\Delta }}\boldsymbol u^* )}^{T},\,{({\boldsymbol{\Delta }}\boldsymbol v^* )}^{T},\,{\boldsymbol{\Delta }}\boldsymbol \sigma^* )}^{T}\)und enthalten \({({({\rm{\Delta }}u* )}^{T},\,{({\rm{\Delta }}v* )}^{T},\,{\rm{\Delta }}\sigma * )}^{T}\).

Für β ∈ [β, (β + β+)/2) ist der Fixpunkt im erwähnten Startvektor eindeutig, und die Iterierten konvergieren im Sinn des Hausdorff-Abstands gegen ihn.

Komplexe Matrizen können auf analoge Weise behandelt werden, ebenso das verallgemeinerte Singulärwertproblem, bei dem A ∈ ℝp×n, B ∈ ℝq×n mit Rang(AT, BT) = n, p, qn gegeben, und orthogonale Matrizen U ∈ ℝp×p, V ∈ ℝq×q, Diagonalmatrizen C = diag(c1,…, cn), S = diag(s1,…, sn) und eine nichtsinguläre Matrix X ∈ ℝn×n gesucht sind, für die \begin{eqnarray}{U}^{T}AX=\left(\begin{array}{c}C\\ O\end{array}\right),\,\,\,\,{V}^{T}BX=\left(\begin{array}{c}S\\ O\end{array}\right)\end{eqnarray} und ci ≥ 0, si ≥ 0, \({c}_{i}^{2}+{s}_{i}^{2}=1\) für i = 1,…, n gilt.

[1] Herzberger, J. (ed.): Topics in Validated Computations. North-Holland Amsterdam, 1994.

Lesermeinung

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