Deflation (Mathematik)

Deflation bezeichnet eine Technik aus der numerischen Mathematik, mit der eine Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ in Blockdreiecksform gebracht wird, so dass das Spektrum von ${\displaystyle A}$ gerade die Vereinigung der Spektren der Diagonalblöcke ist.

Deflationsprinzip

Sei ${\displaystyle F\in \operatorname {End} (V)}$ ein Endomorphismus und ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ die zugehörige Abbildungsmatrix. Durch Basiswechsel kann diese Matrix in eine Matrix ${\displaystyle B}$ der Form

${\displaystyle B\colon {=}{\begin{pmatrix}B_{11}&B_{12}\\0&B_{22}\end{pmatrix}}}$

mit ${\displaystyle B_{ii}\in \mathbb {C} ^{k_{i}\times k_{i}}}$ für ${\displaystyle i\in \{1,2\}}$ und ${\displaystyle k_{1}+k_{2}=n}$ transformiert werden. Für die Spektren ${\displaystyle \sigma (B_{ii})}$ gilt

${\displaystyle \sigma (A)=\sigma (B_{11})\cup \sigma (B_{22}).}$

Anstelle des ${\displaystyle (n\times n)}$ -Eigenwertproblems ${\displaystyle Ax=\lambda x}$ kann man also die zwei kleineren Eigenwertprobleme

${\displaystyle B_{ii}y=\lambda y,\quad i=1,2}$

lösen. Diese Methode k​ann man iterativ fortsetzen.

Deflation durch Ähnlichkeitstransformation

Theoretische Grundlage

Sei ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ eine quadratische Matrix und ${\displaystyle (\lambda ,v)}$ ein Eigenpaar von ${\displaystyle A}$ bestehend aus dem Eigenwert ${\displaystyle \lambda \in \mathbb {C} }$ und einem dazugehörigen Eigenvektor ${\displaystyle v\in \mathbb {C} ^{n}}$ . Dieses Eigenpaar kann man beispielsweise durch die Potenzmethode erhalten. Die Matrix ${\displaystyle A}$ wird nun mittels der Ähnlichkeitstransformation

${\displaystyle B\colon {=}T^{-1}AT}$

in eine Matrix ${\displaystyle B}$ überführt. Die Transformationsmatrix ${\displaystyle T}$ ist gegeben durch ${\displaystyle T\colon {=}I-2{\tfrac {ww^{T}}{w^{T}w}}}$ mit ${\displaystyle w=v+\|v\|_{2}e_{1},}$ wobei ${\displaystyle I}$ die Einheitsmatrix und ${\displaystyle e_{1}\colon {=}{\begin{pmatrix}1&0&\ldots &0\end{pmatrix}}^{T}}$ ist. Diese spezielle Basistransformation ist eine Householdertransformation. Daher gilt ${\displaystyle T=T^{-1}}$ und die Matrix ${\displaystyle B}$ hat die Gestalt

${\displaystyle B={\begin{pmatrix}\lambda &b^{t}\\0&B_{1}\end{pmatrix}}.}$

Diese Matrix hat dieselben Eigenwerte wie die Matrix ${\displaystyle A}$ . Nun kann man wieder die Potenzmethode auf die Matrix ${\displaystyle B_{1}}$ anwenden und erhält so iterativ alle Eigenwerte.

Zahlenbeispiel

Sei

${\displaystyle A={\begin{pmatrix}1&-1&3\\4&2&1\\3&1&9\end{pmatrix}}}$

Durch die Potenzmethode erhält man ${\displaystyle (\lambda _{1},v)=\left(10.22459,{\begin{pmatrix}0.2585012&0.3343480&0.9063049\end{pmatrix}}^{T}\right)}$ als Eigenpaar von ${\displaystyle A}$ . Nun berechnet man die Transformationsmatrix ${\displaystyle T}$ . Es ist

${\displaystyle T=I-2{\frac {ww^{T}}{w^{T}w}}}$ ,

wobei ${\displaystyle w=v+\|v\|_{2}e_{1}}$ ist.

Man erhält

${\displaystyle T={\begin{pmatrix}-0.258501&-0.3343480&-0.9063049\\-0.3343480&0.9111732&-0.2407795\\-0.9063049&-0.2407795&0.3473280\end{pmatrix}}}$

und somit

${\displaystyle TAT={\begin{pmatrix}10.22459&3.5492494&0.5352000\\0&-1.5051646&-2.3002829\\0&1.7142389&0.2805751\end{pmatrix}}}$

Die Eigenwerte d​er Matrix

${\displaystyle C={\begin{pmatrix}-1.5051646&-2.3002829\\1.7142389&0.2805751\end{pmatrix}}}$

sind ${\displaystyle \lambda _{2}=-0.6122947+1.7737021i}$ und ${\displaystyle \lambda _{3}=-0.6122947-1.7737021i}$ somit ist

${\displaystyle \sigma (A)=\{10.22459,-0.6122947+1.7737021i,-0.6122947-1.7737021i\}}$

Literatur

• Martin Hanke-Bourgeois: Grundlagen der Numerischen Mathematik und des Wissenschaftlichen Rechnens. 1. Auflage, B. G. Teubner, Stuttgart 2002, ISBN 978-3-519-00356-4.
• Robert Schaback, Helmut Werner: Numerische Mathematik. Vierte vollständig überarbeitete Auflage, Springer Verlag Berlin Heidelberg GmbH, Berlin Heidelberg 1992, ISBN 978-3-540-54738-9.
• Willi Törnig: Numerische Mathematik für Ingenieure und Physiker. Band 1, Springer Verlag Berlin Heidelberg, Berlin Heidelberg 1979.

Siehe auch

• Inverse Iteration

Weblinks

• Grundlagen der Numerischen Mathematik (abgerufen am 8. September 2016)
• Einführung in die Numerische Mathematik (abgerufen am 8. September 2016)
• Nichtperiodische Pflasterungen mit ganzzahligem Inflationsfaktor (abgerufen am 8. September 2016)