Deflation (Mathematik)

Deflation bezeichnet eine Technik aus der numerischen Mathematik, mit der eine Matrix $A \in \mathbb{C}^{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 \operatorname{End}(V)$ ein Endomorphismus und $A \in \C^{n \times n}$ die zugehörige Koordinatenmatrix. Durch Basiswechsel kann diese Matrix in eine Matrix B der Form

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

mit $B_{ii} \in \C^{k_i \times k_i}$ und k₁ + k₂ für $i \in \{1,2\}$ transformiert werden. Für die Spektren σ(B_ii) gilt

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

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

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

lösen. Diese Methode kann man iterativ fortsetzen.

Deflation durch Ähnlichkeitstransformation

Theoretische Grundlage

Sei $A \in \mathbb{C}^{n\times n}$ eine quadratische Matrix und (λ,v) ein Eigenpaar von A bestehend aus dem Eigenwert $\lambda \in \C$ und einem dazugehörigen Eigenvektor $v \in \C^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 \colon{=} I-2\tfrac{ww^T}{w^Tw}$ mit $w=v+\|v\|_2e_1,$ wobei I die Einheitsmatrix und $e_1 \colon{=} \begin{pmatrix}1 & 0 & \ldots & 0 \end{pmatrix}^T$ ist. Diese spezielle Basistransformation ist eine Householdertransformation. Daher gilt T = T ^{− 1} und die Matrix B hat die Gestalt

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

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

Zahlenbeispiel

Sei

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

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

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

wobei $w=v+\|v\|_2e_1$ ist.

Man erhält

$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

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

Die Eigenwerte der Matrix

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

sind λ₂ = − 0.6122947 + 1.7737021i und λ₃ = − 0.6122947 − 1.7737021i somit ist

σ(A) = {10.22459, − 0.6122947 + 1.7737021i, − 0.6122947 − 1.7737021i}

Siehe auch

• Inverse Iteration