Deflation (Mathematik)

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

Deflationsprinzip

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

$B:=\left(\begin{array}{cc}{B}_{11}& B_{12}\\ 0& B_{22}\end{array}\right)$

mit $B_{ii}\in {ℂ}^{k_i\times k_i}$ für $i\in \{1,2\}$ und $k_1+k_2=n$ transformiert werden. Für die Spektren $\sigma (B_{ii})$ gilt

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

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

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

lösen. Diese Methode kann man iterativ fortsetzen.

Deflation durch Ähnlichkeitstransformation

Theoretische Grundlage

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

$B:=T^{-1}AT$

in eine Matrix $B$ überführt. Die Transformationsmatrix $T$ ist gegeben durch $T:=I-2\frac{w{w}^T}{w^{T}w}$ mit $w=v+\Vert v{\Vert }_2{e}_1$, wobei $I$ die Einheitsmatrix und $e_1:={\left(\begin{array}{cccc}1& 0& \dots & 0\end{array}\right)}^T$ ist. Diese spezielle Basistransformation ist eine Householdertransformation. Daher gilt $T=T^{-1}$ und die Matrix $B$ hat die Gestalt

$B=\left(\begin{array}{cc}\lambda & b^t\\ 0& B_1\end{array}\right)$.

Diese Matrix hat dieselben Eigenwerte wie die Matrix $A$. Nun kann man wieder die Potenzmethode auf die Matrix $B_1$ anwenden und erhält so iterativ alle Eigenwerte.

Zahlenbeispiel

Sei

$A=\left(\begin{array}{ccc}1& -1& 3\\ 4& 2& 1\\ 3& 1& 9\end{array}\right)$

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

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

wobei $w=v+\Vert v{\Vert }_2{e}_1$ ist.

Man erhält

$T=\left(\begin{array}{ccc}-0.258501& -0.3343480& -0.9063049\\ -0.3343480& 0.9111732& -0.2407795\\ -0.9063049& -0.2407795& 0.3473280\end{array}\right)$

und somit

$TAT=\left(\begin{array}{ccc}10.22459& 3.5492494& 0.5352000\\ 0& -1.5051646& -2.3002829\\ 0& 1.7142389& 0.2805751\end{array}\right)$

Die Eigenwerte der Matrix

$C=\left(\begin{array}{cc}-1.5051646& -2.3002829\\ 1.7142389& 0.2805751\end{array}\right)$

sind ${\lambda }_2=-0.6122947+1.7737021i$ und ${\lambda }_3=-0.6122947-1.7737021i$ somit ist

$\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)