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 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 : = (\begin{matrix} B_{11} & B_{12} \\ 0 & B_{22} \end{matrix})

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

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

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

B_{i i} y = λ 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 $(λ, v)$ ein Eigenpaar von $A$ bestehend aus dem Eigenwert $λ \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} A T

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 + ‖ v ‖_{2} e_{1}$ , wobei $I$ die Einheitsmatrix und $e_{1} : = {(\begin{matrix} 1 & 0 & \dots & 0 \end{matrix})}^{T}$ ist. Diese spezielle Basistransformation ist eine Householdertransformation. Daher gilt $T = T^{- 1}$ und die Matrix $B$ hat die Gestalt

B = (\begin{matrix} λ & b^{t} \\ 0 & B_{1} \end{matrix})

.

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 = (\begin{matrix} 1 & - 1 & 3 \\ 4 & 2 & 1 \\ 3 & 1 & 9 \end{matrix})

Durch die Potenzmethode erhält man $(λ_{1}, v) = (10.22459, {(\begin{matrix} 0.2585012 & 0.3343480 & 0.9063049 \end{matrix})}^{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 + ‖ v ‖_{2} e_{1}$ ist.

Man erhält

T = (\begin{matrix} - 0.258501 & - 0.3343480 & - 0.9063049 \\ - 0.3343480 & 0.9111732 & - 0.2407795 \\ - 0.9063049 & - 0.2407795 & 0.3473280 \end{matrix})

und somit

T A T = (\begin{matrix} 10.22459 & 3.5492494 & 0.5352000 \\ 0 & - 1.5051646 & - 2.3002829 \\ 0 & 1.7142389 & 0.2805751 \end{matrix})

Die Eigenwerte der Matrix

C = (\begin{matrix} - 1.5051646 & - 2.3002829 \\ 1.7142389 & 0.2805751 \end{matrix})

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

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

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)