Direkt zum Inhalt

Lexikon der Mathematik: Deflation

Technik, eine Matrix A ∈ ℂn×n in zwei oder mehrere Matrizen kleinerer Dimension zu überführen, so daß das Spektrum von A gerade gleich der Vereinigung der Spektren dieser Matrizen kleinerer Dimension ist.

Überführt man eine Matrix A z. B. auf die Form \begin{eqnarray}\left(\begin{array}{A}_{11} & {A}_{12}\\ 0 & {A}_{22}\end{array}\right),{A}_{jj}\in {{\rm{{\mathbb{C}}}}}^{{k}_{j}\times {k}_{j}}\end{eqnarray} mit k1 + k2 = n, dann gilt für die Spektren dieser Matrizen die gewünschte Beziehung \begin{eqnarray}\sigma (A)=\sigma ({A}_{11})\cup \sigma ({A}_{22}).\end{eqnarray}

Anstelle des (n × n)-Eigenwertproblems Ax = λx kann man nun zwei kleinere Eigenwertprobleme \begin{eqnarray}{A}_{jj}y=\lambda y,\,\ \ \ j=1,2,\end{eqnarray}

lösen. Diese Technik wird insbesondere bei der Potenzmethode, der inversen Iteration und dem QR-Algorithmus angewendet.

Beim QR-Algorithmus berechnet man, ausgehend von einer unreduzierten oberen Hessenberg-Matrix H0, eine Folge von oberen Hessenberg-Matrizen Hj, bei denen bei geeigneter Shiftwahl-Strategie die Elemente der ersten unteren Nebendiagonale gegen Null konvergieren. Sobald eines der Nebendiagonalelemente \({h}_{i+1,i}^{(j)}\) von Hj hinreichend klein ist, spaltet man das Eigenwertproblem wie oben beschrieben in zwei kleinere auf, und arbeitet auf den beiden kleineren Problemen. Typischerweise hat man i = n − 1 oder i = n − 2, und man kann die Eigenwerte des rechten unteren Blocks in Hj explizit berechnen.

Bei der Potenzmethode und der inversen Iteration läßt sich für eine gegebene Matrix A nur ein einzelner Eigenwert λ1 mit zugehörigem Eigenvektor x1 berechnen. Um weitere Eigenpaare zu erhalten, überführt man die Matrix A mittels Ähnlichkeitstransformation mit einer nichtsingulären Matrix H auf die Form \begin{eqnarray}HA{H}^{-1}=\left(\begin{array}{cc}{\lambda }_{1} & {b}^{H}\\ 0 & B\end{array}\right),B\in {{\rm{{\mathbb{C}}}}}^{(n-1)\times (n-1)}\end{eqnarray} und wendet dann die Potenzmethode oder die inverse Iteration auf B an.

Für die Matrix H muß \begin{eqnarray}{\begin{array}\text H{x}_{1}={\lambda }_{1}{e}_{1}, & \text{wobei}\ {e}_{1}=(1,0,\ldots, 0)\end{array}}^{T}\end{eqnarray} gelten; man kann eine solche Matrix H z. B. als unitäre Householder-Matrix berechnen.

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

Partnervideos