Jacobi method (eigenvalues)

The Jacobi method (after Carl Gustav Jacob Jacobi (1846)) is an iterative method for the numerical calculation of all eigenvalues and vectors of (small) symmetrical matrices .

The process became practical with the advent of computers . The used rotation matrices are after Wallace Givens , also, the resulting mid-1950s dealt Givens rotation called.

description

Since the output matrix is ​​assumed to be symmetrical, it is orthogonal similar to a diagonal matrix ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ ${\displaystyle D\in \mathbb {R} ^{n\times n}.}$

${\displaystyle D=S^{T}\cdot A\cdot S,}$

where the diagonal of contains the eigenvalues of and the associated eigenvectors in columns. ${\displaystyle D}$ ${\displaystyle \lambda _{1},\ldots ,\lambda _{n}}$ ${\displaystyle A}$ ${\displaystyle S}$

${\displaystyle D={\text{diag}}(\lambda _{1},\ldots ,\lambda _{n}),\qquad S=\lbrace E(\lambda _{1}),\ldots ,E(\lambda _{n})\rbrace }$

The idea of ​​the Jacobi method is to bring the largest extra-diagonal element in each case to 0 with the help of a Givens rotation , and in this way to approximate more and more of a diagonal matrix . The result is the iteration rule

${\displaystyle {\begin{array}{lll}A^{(0)}&=&A\\A^{(k+1)}&=&R_{k}^{T}A^{(k)}R_{k}=\underbrace {R_{k}^{T}R_{k-1}^{T}\ldots R_{0}^{T}} _{S_{k}^{T}}A^{(0)}\underbrace {R_{0}\ldots R_{k-1}R_{k}} _{S_{k}}\end{array}}}$

With ${\displaystyle R_{k}={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &\cos \varphi &\cdots &\sin \varphi &\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &-\sin \varphi &\cdots &\cos \varphi &\cdots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}},}$

where and are in the -th and -th row and column and represent the largest off-diagonal element of . The components of now result from the following consideration: ${\displaystyle \cos \varphi }$ ${\displaystyle \sin \varphi }$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle (p<q)}$ ${\displaystyle |a_{pq}^{(k)}|\geq |a_{ij}^{(k)}|\quad \forall 1\leq i,j\leq n,i\not =j}$ ${\displaystyle A^{(k)}}$ ${\displaystyle R_{k}}$

The transformation causes the following changes, especially in the intersection elements: ${\displaystyle R_{k}^{T}A^{(k)}R_{k}}$

${\displaystyle {\begin{array}{lll}a_{pp}^{(k+1)}&=&a_{pp}^{(k)}\cos ^{2}\varphi -2a_{pq}^{(k)}\cos \varphi \sin \varphi +a_{qq}^{(k)}\sin ^{2}\varphi \\a_{qq}^{(k+1)}&=&a_{pp}^{(k)}\sin ^{2}\varphi +2a_{pq}^{(k)}\cos \varphi \sin \varphi +a_{qq}^{(k)}\cos ^{2}\varphi \\a_{pq}^{(k+1)}&=&a_{qp}^{(k+1)}=(a_{pp}^{(k)}-a_{qq}^{(k)})\cos \varphi \sin \varphi +a_{pq}^{(k)}(\cos ^{2}\varphi -\sin ^{2}\varphi )\qquad (\ast )\end{array}}}$

There should be, it follows from ${\displaystyle a_{pq}^{(k+1)}=0}$ ${\displaystyle (\ast ):\quad \Theta :={\frac {a_{qq}^{(k)}-a_{pp}^{(k)}}{2a_{pq}^{(k)}}}=\cot 2\varphi ={\frac {1-\tan ^{2}\varphi }{2\tan \varphi }}}$

${\displaystyle \Rightarrow \tan \varphi ={\begin{cases}{\frac {1}{\Theta +\operatorname {sgn} \Theta {\sqrt {1+\Theta ^{2}}}}}&\Theta \not =0\\1&\Theta =0\end{cases}}\Rightarrow \cos \varphi ={\frac {1}{\sqrt {1+\tan ^{2}\varphi }}},~\sin \varphi =\tan \varphi \cos \varphi }$

Since the rotation matrices are orthogonal and products of orthogonal matrices are again orthogonal, an orthogonal similarity transformation is described in this way . It can be shown that the sequence of matrices converges to a diagonal matrix. Due to the similarity, this must have the same eigenvalues. ${\displaystyle A^{(k)}}$

${\displaystyle A^{(k)}{\xrightarrow[{k\rightarrow \infty }]{}}\,{\text{diag}}(\lambda _{1},\ldots ,\lambda _{n})}$

Classic and cyclic Jacobi method

In the classic Jacobi method, the largest element in terms of amount is set to zero in each iteration step. Since the search for this is the main expense of the algorithm, the cyclic Jacobi method applies a Givens rotation to each element of the strict upper triangle in each iteration step.

literature

• Kaspar Nipp, Daniel Stoffer: Lineare Algebra: An introduction for engineers with special consideration of numerical aspects . VDF Hochschulverlag AG 2002, ISBN 978-3-7281-2818-8 . Section 10.2 (pp. 222–228) ( restricted online version (Google Books) )

Web links

• Fullerton University website on the Jacobi method (including a collection of links)

Individual evidence

1. ^ Jacobi, On an Easy Method for Numerically Solving the Equations Occurring in the Theory of Secular Disorders, Crelle's Journal, Volume 30, 1846, pp. 51-94