Deflation (math)

Deflation describes a technique from numerical mathematics with which a matrix is ​​formed into a block triangular shape so that the spectrum of is just the union of the spectra of the diagonal blocks. ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle A}$

Deflation principle

Let be an endomorphism and the associated mapping matrix . By changing the base , this matrix can be converted into a matrix of the form ${\displaystyle F\in \operatorname {End} (V)}$ ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle B}$

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

to be transformed with for and . The following applies to the spectra ${\displaystyle B_{ii}\in \mathbb {C} ^{k_{i}\times k_{i}}}$ ${\displaystyle i\in \{1,2\}}$ ${\displaystyle k_{1}+k_{2}=n}$ ${\displaystyle \sigma (B_{ii})}$

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

Instead of the - eigenvalue problem , one can use the two smaller eigenvalue problems ${\displaystyle (n\times n)}$ ${\displaystyle Ax=\lambda x}$

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

to solve. This method can be continued iteratively.

Deflation through Similarity Transformation

Theoretical basis

Let be a square matrix and an eigenpair of consisting of the eigenvalue and an associated eigenvector . This own pair can be obtained, for example, using the power method . The matrix is now using the similarity transformation ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle (\lambda ,v)}$ ${\displaystyle A}$ ${\displaystyle \lambda \in \mathbb {C} }$ ${\displaystyle v\in \mathbb {C} ^{n}}$ ${\displaystyle A}$

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

transferred to a matrix . The transformation matrix is given by with where the identity matrix is and . This particular base transformation is a household transformation . Hence, and the matrix has the form ${\displaystyle B}$ ${\displaystyle T}$ ${\displaystyle T\colon {=}I-2{\tfrac {ww^{T}}{w^{T}w}}}$ ${\displaystyle w=v+\|v\|_{2}e_{1},}$ ${\displaystyle I}$ ${\displaystyle e_{1}\colon {=}{\begin{pmatrix}1&0&\ldots &0\end{pmatrix}}^{T}}$ ${\displaystyle T=T^{-1}}$ ${\displaystyle B}$

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

This matrix has the same eigenvalues ​​as the matrix . Now you can apply the power method to the matrix again and get all eigenvalues ​​iteratively. ${\displaystyle A}$ ${\displaystyle B_{1}}$

Numerical example

Be

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

With the power method one obtains as an own pair of . The transformation matrix is ​​now calculated . It is ${\displaystyle (\lambda _{1},v)=\left(10.22459,{\begin{pmatrix}0.2585012&0.3343480&0.9063049\end{pmatrix}}^{T}\right)}$ ${\displaystyle A}$ ${\displaystyle T}$

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

where is. ${\displaystyle w=v+\|v\|_{2}e_{1}}$

You get

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

and thus

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

The eigenvalues ​​of the matrix

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

are and thus is ${\displaystyle \lambda _{2}=-0.6122947+1.7737021i}$ ${\displaystyle \lambda _{3}=-0.6122947-1.7737021i}$

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

literature

• Martin Hanke-Bourgeois: Fundamentals of Numerical Mathematics and Scientific Computing. 1st edition, BG Teubner, Stuttgart 2002, ISBN 978-3-519-00356-4 .
• Robert Schaback, Helmut Werner: Numerical Mathematics. Fourth completely revised edition, Springer Verlag Berlin Heidelberg GmbH, Berlin Heidelberg 1992, ISBN 978-3-540-54738-9 .
• Willi Törnig: Numerical mathematics for engineers and physicists. Volume 1, Springer Verlag Berlin Heidelberg, Berlin Heidelberg 1979.

See also

• Inverse iteration

Web links

• Basics of Numerical Mathematics (accessed on September 8, 2016)
• Introduction to Numerical Mathematics (accessed on September 8, 2016)
• Non-periodic tilings with an integer inflation factor (accessed on September 8, 2016)