Direkt zum Inhalt

Lexikon der Mathematik: Lösungsverifikation beim algebraischen Eigenwertproblem

in der Intervallrechnung Nachweis der Existenz eines Eigenwerts λ*λ(0) und eines (meist normierten) zugehörigen Eigenvektors \(x* =({x}_{i}^{* })\in {\bf x}^{(0)}\) zu einer reellen (n × n)-Matrix A. Dabei ist λ(0) ein gegebenes reelles kompaktes Intervall und x(0) ein n-komponentiger Intervallvektor.

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

Für das skizzierte Problem kann man jedes Verfahren zur Lösungsverifikation bei nichtlinearen Gleichungssystemen mit \begin{eqnarray}f(x,\lambda)=\left(\begin{array}{c}Ax-\lambda x\\ {x}_{{i}_{0}}-\alpha \end{array}\right)\end{eqnarray} verwenden. Als Alternative bietet sich die Funktion \begin{eqnarray}g({\rm{\Delta }}x,{\rm{\Delta }}y)=-Cf(\tilde{x},\tilde{y})+\left\{{I}_{n+1}\\ -C\left(\begin{array}{cc}A-\tilde{\lambda }{I}_{n} & -\tilde{x}-{\rm{\Delta }}x\\ {({e}^{({i}_{0})})}^{T} & 0\end{array}\right)\right\}\left(\begin{array}{c}{\rm{\Delta }}x\\ {\rm{\Delta }}y\end{array}\right)\end{eqnarray} an, in der \((\tilde{x},\tilde{\lambda })\) eine mit herkömmlichen Verfahren berechnete Näherung von (x*, λ*), C eine präkonditionierende ((n + 1) × (n + 1))-Matrix, Ik die (k × k)-Einheitsmatrix, \({e}^{({i}_{0})}\) die i0-te Spalte von In, und \begin{eqnarray}({\rm{\Delta }}x,{\rm{\Delta }}\lambda )=(x-\tilde{x},\lambda -\tilde{\lambda })\end{eqnarray} den Fehler bezeichnen.

Für jedes Eigenpaar (x*, λ*) mit \({x}_{{i}_{0}}^{* }=\alpha \ne 0\) ist \begin{eqnarray}({\rm{\Delta }}{x}^{* },{\rm{\Delta }}{\lambda }^{* })=({x}^{* }-\tilde{x},{\lambda }^{* }-\tilde{\lambda })\end{eqnarray}

Fixpunkt von g. Mit den erwähnten Bezeichnungen und dem Intervallvektor \(({\rm{\Delta }}x,\,{\rm{\Delta }}\lambda )=({\bf x}-\tilde{x},\,\lambda -\tilde{\lambda })\) erhält man den folgenden Satz:

Aus \begin{eqnarray}\begin{array}{cc}{\bf{\text{g}}}({\bf{\Delta }}{\bf{\boldsymbol x}},{\boldsymbol{\Delta }}{\boldsymbol{\lambda }})\subseteq \text{Inneres von}\ \left(\begin{array}{c}{\boldsymbol{\Delta }}{\boldsymbol {x}}\\ {\boldsymbol{\Delta }}{\boldsymbol{\lambda }}\end{array}\right)\end{array}\end{eqnarray}für die Intervallauswertung g von g folgt:

  1. C ist nichtsingulär.
  2. Es gibt genau einen Eigenvektor \({x}^{* }\in \tilde{x}+{\bf{\Delta }}\boldsymbol x\) mit \({x}_{{i}_{0}}^{* }=\alpha \)und genau einen Eigenwert \({\lambda }^{* }\in \tilde{\lambda }+{\bf{\Delta }}\boldsymbol \lambda \). λ* ist geometrisch einfach, und es gilt Ax* = λ*x*. Bei hinreichend guter Näherung \((\tilde{x},\tilde{\lambda })\)ist λ* auch algebraisch einfach.
  3. Startet man die Iteration \begin{eqnarray}\begin{array}{cc}\left(\begin{array}{c}{\bf{\Delta }}{{\boldsymbol{x}}}^{(k+1)}\\ {\bf{\Delta }}{{\boldsymbol{\lambda }}}^{(k+1)}\end{array}\right)={\bf{\text{g}}}({\bf{\Delta }}{{\boldsymbol{x}}}^{k},{\boldsymbol{\Delta }}{{\boldsymbol{\lambda }}}^{k}),\,\,\,k=0,1,\ldots\end{array}\end{eqnarray}mit den Größen aus (1), dann konvergieren die Iterierten und enthalten \({({({x}^{* }-\tilde{x})}^{T},{\lambda }^{* }-\tilde{\lambda })}^{T}\).

Um (1) zu erfüllen, kann man beispielsweise mit ϵ-Inflation iterieren. Eine andere Möglichkeit bietet der folgende Satz:

Mit den Bezeichnungen von oben, der Maximumsnorm ║·║, und \begin{eqnarray}\varrho ={\Vert C\left(\begin{array}{c}A\tilde{x}-\tilde{\lambda }\tilde{x}\\ 0\end{array}\right)\Vert }_{\infty },\,\,\tau ={\Vert C\Vert }_{\infty }\\ \sigma ={\Vert {I}_{n+1}-C\left(\begin{array}{cc}A-\tilde{\lambda }{I}_{n} & -\tilde{x}\\ {({e}^{({i}_{0})})}^{T} & 0\end{array}\right)\Vert }_{\infty }\end{eqnarray}gelte σ < 1 und Δ = (1 − σ)2 − 4ϱτ ≥ 0.

Dann sind die Zahlen \({\beta }^{-}=(1-\sigma -\sqrt{{\rm{\Delta }}})/(2\tau )\)und \({\beta }^{+}=(1-\sigma -\sqrt{{\rm{\Delta }}})/(2\tau )\)nicht negativ und (1) ist für \begin{eqnarray}{({\boldsymbol{\Delta }}{{\boldsymbol{x}}}^{T},{\boldsymbol{\Delta }}{\boldsymbol{\lambda }})}^{T}={([-\beta,\beta ],\ldots,[-\beta,\beta ])}^{T}\end{eqnarray}mit beliebigem β ∈ (β, β+) erfüllt. Für \begin{eqnarray}\beta \in [{\beta }^{-},({\beta }^{-},({\beta }^{-}+{\beta }^{+})/2)\end{eqnarray}konvergieren die Iterierten (2) im Sinn des Hausdorff-Abstands gegen \begin{eqnarray}{({({x}^{* }-\tilde{x})}^{T},{\lambda }^{* }-\tilde{\lambda })}^{T}.\end{eqnarray}

Die Problemstellung und die Sätze können auf eine Intervallmatrix A übertragen werden, bei der man zu jeder Matrix AA in (x(0), λ(0)) ein Eigenpaar garantieren möchte.

Komplexe Matrizen können auf analoge Weise behandelt werden, ebenso das verallgemeinerte Eigenwertproblem Ax = λBx. Für symmetrische bzw. Hermitesche Matrizen gibt es spezielle Verifikationsverfahren.

[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