in der Intervallrechnung der Nachweis der Existenz eines singulären Wertes σ* ∈ σ⁽⁰⁾ 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⁽⁰⁾, v⁽⁰⁾ 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 A^TA bzw. AA^T 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 A^TA bzw. AA^T 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, I_k 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 Fixpunkt (Δu*, Δ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(A^T, B^T) = n, p, q ≥ n gegeben, und orthogonale Matrizen U ∈ ℝ^p×p, V ∈ ℝ^q×q, Diagonalmatrizen C = diag(c₁,…, c_n), S = diag(s₁,…, s_n) 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 c_i ≥ 0, s_i ≥ 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.