Jacobi-módszer

A Jacobi-módszer (vagy Jacobi-féle sajátértékmódszer) néven ismert eljárás olyan iteratív módszer, amely kis méretű (n<10) szimmetrikus valós mátrixok sajátértékeinek és sajátvektorainak a meghatározására használható. Ezen módszer célja a mátrix főátlón kívüli elemeinek iteratív eljárással történő kinullázása. A Jacobi-módszer esetén az iterációs lépéseket addig ismételjük, míg egy általunk meghatározott pontosságig az ismeretleneket meg nem határozzuk. Ez azt fogja jelenteni, hogy akkor állunk meg a lépesekkel, mikor már két egymás utáni lépésben kapott ismeretlen értékek különbsége kisebb egy általunk meghatározott értéknél. Nevét Carl Gustav Jacob Jacobiról kapta, aki először 1846-ban publikálta, de csak az 1950-es években vált elterjedtté a számítógépek fejlődése miatt. A Jacobi-módszer esetében az iterációs képlet a következő lesz: $x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j=1,j\ne i}^n{a}_{ij}{x}_j^{(k)}),i=1,2,\dots ,n$ Ahhoz, hogy könnyebben megérthessük a módszer elvét, tekintsünk egy példát: $\left(\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right)(\genfrac{}{}{0ex}{}{x_1}{x_2})=(\genfrac{}{}{0ex}{}{b_1}{b_2})$ Hogy jobban áttekinthető legyen, átírhatjuk egyenletek formájába, amely így nézhet ki: $\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2=b_1\\ a_{21}{x}_1+a_{22}{x}_2=b_2\end{array}$ Innen kifejezhető az x₁ és x₂ ismeretlen, így a következő egyenleteket kapjuk: $x_1=-\frac{a_{12}}{a_{11}}{x}_2+\frac{b_1}{a_{11}}$, $x_2=-\frac{a_{21}}{a_{22}}{x}_1+\frac{b_2}{a_{22}}$ Az így kapott egyenletrendszert úgy oldhatjuk meg, hogy kezdetben kiindulunk az $x_1^{(0)}$, illetve az $x_2^{(0)}$ legjobb becslésünkből, vagy az egyszerűség kedvéért indulhatunk 0-ból is. Ezután felhasználva az $x_1^{(k)}=-\frac{a_{12}}{a_{11}}{x}_2^{(k-1)}+\frac{b_1}{a_{11}}$, $x_2^{(k)}=-\frac{a_{21}}{a_{22}}{x}_1^{(k-1)}+\frac{b_2}{a_{22}}$ lépéseket, eljuthatunk egy jobb közelítő értékig. Ezt addig alkalmazzuk, amíg az ismeretleneket tetszőleges pontossággal meg nem határozzuk.

Leírás

Az olyan transzformációt, ahol egy mátrixszal jobbról és az inverzével balról szorzunk egy mátrixot, hasonlósági transzformációnak nevezzük. A karakterisztikus egyenletet felírva belátható, hogy a hasonlósági transzformáció nem változtatja meg a sajátértékeket. Valós és szimmetrikus mátrixok esetén ${\mathbf{R}}^{\mathbf{-}\mathbf{1}}\mathbf{=}{\mathbf{R}}^{\mathbf{T}}$, vagyis a hasonlósági transzformáció ortogonális transzformáció is egyben. Ezen az összefüggésen alapul a következőkben ismertetett módszer is. Vagyis a megfelelően megválasztott transzformációval a mátrixot diagonalizáljuk. Mivel a sajátvektorok maguk is valósak és ortogonálisak, az $\mathbf{A}$ szimmetrikus mátrix diagonalizálása megoldható az $\mathbf{R}$ ortogonális hasonlósági transzformáció segítségével, azaz

$\begin{array}{r}{\mathbf{R}}^{\mathbf{T}}\mathbf{\cdot }\mathbf{A}\mathbf{\cdot }\mathbf{R}\mathbf{=}\mathrm{\Lambda }.\end{array}$

Vegyük példaként a $2\times 2$ típusú mátrix esetét. Ekkor a transzformációhoz használjuk a

$\mathbf{R}=\left(\begin{array}{cc}\cos \phi & -\sin \phi \\ \sin \phi & \cos \phi \end{array}\right)$

síkforgatást leíró mátrixot, ahol $\phi$ a forgatás szöge. Ha felírjuk ezzel az ${\mathbf{A}}^{\prime }\mathbf{=}{\mathbf{R}}^{\mathbf{T}}\mathbf{\cdot }\mathbf{A}\mathbf{\cdot }\mathbf{R}$ szimmetria transzformációt, a transzformálás után az ${\mathbf{A}}^{\prime }$ mátrix elemei

$\begin{array}{rl}{a}_{11}^{\text{'}}& =a_{11}{\cos }^2\phi +2a_{21}\sin \phi \cos \phi +a_{22}{\sin }^{}\phi \\ a_{22}^{\text{'}}& =a_{11}{\sin }^2\phi -2a_{21}\sin \phi \cos \phi +a_{22}{\cos }^{}\phi \\ a_{21}^{\text{'}}& =a_{21}({\cos }^2\phi -{\sin }^2\phi )+(a_{22}-a_{11})\sin \phi \cos \phi =a_{12}^{\text{'}}\end{array}$

lesznek. Ha a nem átlós $a_{12}^{\text{'}}$ és $a_{21}^{\text{'}}$ elemeket 0-vá alakítjuk, az elforgatási szögre a következő egyenletet kapjuk:

$\begin{array}{rl}{\cot }^2\phi +\frac{a_{22}-a_{11}}{a_{21}}\cot \phi -1& =0,\end{array}$

melynek alapján

$\begin{array}{rl}\tan \phi & =[\frac{a_{11}-a_{22}}{2a_{12}}\pm \sqrt{(\frac{a_{11}-a_{22}}{2a_{12}}{)}^2+1}{]}^{-1}.\end{array}$

Innen megkaphatjuk a $\cos \phi =(1+\tan \phi {)}^{-1/2}$ és $\sin \phi =\tan \phi \cos \phi$ függvényeket, melyekkel felépítjük a forgatásmátrixot. Az így kapott ${\mathbf{A}}^{\prime }$ mátrix diagonális, tehát az átlóban található együtthatók a sajátértékek, míg az $\mathbf{R}$ forgatásmátrix két oszlopa a sajátértékeknek megfelelő két sajátvektor:

$\begin{array}{rlrl}{\lambda }_1& =a_{11}^{\text{'}},& {\mathbf{x}}^{(1)}& =\left[\begin{array}{c}\cos \phi \\ \sin \phi \end{array}\right];\\ {\lambda }_2& =a_{22}^{\text{'}},& {\mathbf{x}}^{(2)}& =\left[\begin{array}{c}-\sin \phi \\ \cos \phi \end{array}\right].\end{array}$

Általános eset

A következőkben nézzük meg, hogy miként működik ez a módszer általános esetben $n\times n$ méretű mátrixok esetén. A sík-forgatás mátrixunk az egységmátrixtól csak az $r_{ii},r_{ij},r_{ji},r_{jj}$ elemekben tér el, vagyis

${\mathbf{R}}_{ij}=\left(\begin{array}{ccccc}1& ⋮& & ⋮& 0\\ \cdots & \cos \phi & \cdots & -\sin \phi & \cdots \\ & ⋮& \ddots & ⋮& & \\ \cdots & \sin \phi & \cdots & \cos \phi & \cdots \\ 0& ⋮& & ⋮& 1\end{array}\right)$

Ezt felhasználva az

${\mathbf{A}}^{\prime }\mathbf{=}{R}_{\mathbf{i}\mathbf{j}}^{\mathbf{T}}\mathbf{\cdot }\mathbf{A}\mathbf{\cdot }{\mathbf{R}}_{\mathbf{i}\mathbf{j}}$

ortogonális hasonlósági transzformációval nullákat viszünk be az $a_{ij}^{\text{'}}$és $a_{ji}^{\text{'}}$ elemek helyére. A szorzás elvégzése után az

$\begin{array}{rl}{a}_{ik}^{\text{'}}& =a_{ki}^{\text{'}}=a_{ik}\cos \phi +a_{jk}\sin \phi ,k=\overline{1,n}\\ a_{jk}^{\text{'}}& =a_{kj}^{\text{'}}=a_{ik}\sin \phi +a_{jk}\cos \phi ,k\ne i,j\\ a_{ii}^{\text{'}}& =a_{ii}{\cos }^2\phi +2a_{ji}\sin \phi \cos \phi +a_{jj}{\sin }^{}\phi \\ a_{jj}^{\text{'}}& =a_{ii}{\sin }^2\phi -2a_{ji}\sin \phi \cos \phi +a_{jj}{\cos }^{}\phi \\ a_{ji}^{\text{'}}& =a_{ji}({\cos }^2\phi -{\sin }^2\phi )+(a_{jj}-a_{ii})\sin \phi \cos \phi =a_{ij}^{\text{'}}\end{array}$

mátrixelemeket kapjuk eredményül. Ezek közül megköveteljük, hogy az $a_{ij}^{\text{'}}$ , illetve az $a_{ji}^{\text{'}}$ elemek 0-ák legyenek. Ekkor a

${\cot }^2\phi +\frac{a_{jj}-a_{ii}}{a_{ji}}\cot \phi -1=0$

egyenlethez jutunk, melyet megoldva a forgatás szöge

$\tan \phi =[\frac{a_{ii}-a_{jj}}{2a_{ij}}\pm \sqrt{(\frac{a_{ii}-a_{jj}}{2a_{ji}}{)}^2+1}{]}^{-1}$

lesz. Meg kell jegyeznünk, hogy amikor egy másik elemet nullázunk ki a következő lépésben, akkor az előzőekben kinullázott elem elromlik. Viszont belátható, hogy bizonyos feltételek mellett az átlón kívüli elemek négyzetösszege egy lépésben $2\mid a_{ij}{\mid }^2$-tel csökken, vagyis monoton módon tart 0-hoz. $A_l$-lel jelölve az $l$. transzformáció utáni mátrixot, a transzformáció-sorozatot a következőképpen írhatjuk:

${\mathbf{A}}_{\mathbf{0}}\mathbf{=}\mathbf{A},{\mathbf{A}}_{\mathbf{1}}\mathbf{=}{R}_{\mathbf{1}}^{\mathbf{T}}\mathbf{\cdot }{\mathbf{A}}_{\mathbf{0}}\mathbf{\cdot }{\mathbf{R}}_{\mathbf{1}},{\mathbf{A}}_{\mathbf{2}}\mathbf{=}{R}_{\mathbf{2}}^{\mathbf{T}}\mathbf{\cdot }{\mathbf{A}}_{\mathbf{1}}\mathbf{\cdot }{\mathbf{R}}_{\mathbf{2}},\mathbf{\dots },{\mathbf{A}}_{\mathbf{l}}\mathbf{=}{R}_{\mathbf{l}}^{\mathbf{T}}\mathbf{\cdot }{\mathbf{A}}_{\mathbf{l}\mathbf{-}\mathbf{1}}\mathbf{\cdot }{\mathbf{R}}_{\mathbf{l}},\mathbf{\dots },$

ahol ${\mathbf{R}}_{\mathbf{l}}$-el valamely nem-átlós elemre alkalmazott transzformációt jelöltük. Képezzük a transzformációs mátrixok

$\begin{array}{rlr}{\mathbf{X}}_{\mathbf{l}}\mathbf{=}{\mathbf{R}}_{\mathbf{0}}\mathbf{\cdot }{\mathbf{R}}_{\mathbf{1}}\mathbf{\cdots }{\mathbf{R}}_{\mathbf{l}},& & l=0,1,2,\dots ,\end{array}$

szorzatát. Ha végtelen sok transzformációt végzünk, akkor

$\begin{array}{rlr}\underset{l\to \mathrm{\infty }}{\lim }{\mathbf{A}}_{\mathbf{l}}\mathbf{=}\mathrm{\Lambda },& & \underset{l\to \mathrm{\infty }}{\lim }{\mathbf{X}}_{\mathbf{l}}\mathbf{=}\mathbf{X}\end{array}$

lesz. Ez azt jelenti, hogy ha ezeket a transzformációkat egymás után alkalmazzuk, akkor a mátrix diagonalizálódik, és az átlóban a sajátértékeket kapjuk. A sajátvektorok pedig a transzformációk szorzatmátrixának oszlopaiban lesznek. A módszer konvergenciáját a $\tan \phi \le 1$ feltétel tiszteletben tartása biztosítja, ami egy $\phi \le \pi /4$ forgatásnak felel meg. Ezt úgy tudjuk biztosítani, hogy a két gyök közül a "+" előjelest választjuk, amennyiben $(a_{ii}-a_{jj})/a_{ji}>0$ és a "−" előjelest az ellenkező esetben. Ezt úgy tudjuk legkönnyebben megvalósítani, hogy a szöget a következőképpen számoljuk:

$\tan \phi =sign\left(\frac{a_{ii}-a_{jj}}{2a_{ji}}\right)[\left|\frac{a_{ii}-a_{jj}}{2a_{ji}}\right|+\sqrt{(\frac{a_{ii}-a_{jj}}{2a_{ji}}{)}^2+1}{]}^{-1}.$

Algoritmus

A leírt módszer a következő algoritmus segítségével alkalmazható számítógépre:

from __future__ import division
import math
dim=4
def Jacobi(a,imax,epsilon,x,l):
	for i in range(dim):
		for j in range(dim):
			x[i][j]=0
		x[i][i]=1
		l[i]=a[i][i]
	for it in range (imax):
		amax=0
		for j in range(1,dim,1):
			for i in range (j):
				a[i][i]=l[i]
				a[j][j]=l[j]
				a[j][i]=math.fabs(a[j][i])
				if amax<a[j][i]:
					amax=a[j][i]
				if a[j][i]>epsilon:
					tmp=(a[i][i]-a[j][j])/(2*a[j][i])
					t=1/(math.fabs(tmp)+math.sqrt(1+tmp*tmp))
					if tmp<0:
						t=-t
					c=1.0/(math.sqrt(1+t*t))
					s=c*t
					for k in range(i):
						temp=a[i][k]*c+a[j][k]*s
						a[j][k]=a[j][k]*c-a[i][k]*s
						a[i][k]=temp
					for k in range(i+1,j,1):
						temp=a[k][i]*c+a[j][k]*s
						a[j][k]=a[j][k]*c-a[k][i]*s
						a[k][i]=temp
					for k in range(j+1,dim,1):
						temp=a[k][i]*c+a[k][j]*s
						a[k][j]=a[k][j]*c-a[k][i]*s
						a[k][i]=temp
					for k in range (dim):
						temp=x[k][i]*c+x[k][j]*s
						x[k][j]=x[k][j]*c-x[k][i]*s
						x[k][i]=temp
					tmp=2*s*c*a[j][i]
					l[i]=a[i][i]*c*c+a[j][j]*s*s+tmp
					l[j]=a[i][i]*s*s+a[j][j]*c*c-tmp
					a[j][i]=0
		if amax<=epsilon:
			return 0
	return 666
a=[
	[3,0,2,1],
	[0,1,3,4],
	[2,3,2,1],
	[1,4,1,5]
	]
x=[
	[0,0,0,0],
	[0,0,0,0],
	[0,0,0,0],
	[0,0,0,0]
	]
l=[0,0,0,0]
epsilon=1e-16
imax=1e6
print a
b=Jacobi(a,imax,epsilon,x,l)
print b
print x
print l

Példa

Legyen $A=\left(\begin{array}{cccc}3& 0& 2& 1\\ 0& 1& 3& 4\\ 2& 3& 2& 1\\ 1& 4& 1& 5\end{array}\right)$ A jacobi a következő sajátértékeket és sajátvektorokat adja: ${\lambda }_1=3.8614176875601696$ ${\eta }^{(1)}=\left[\begin{array}{c}0.20847934594025172\\ -0.9248091113211869\\ -0.30940655891140356\\ 0.07437776036050801\end{array}\right]$ ${\lambda }_2=1.0818507981865024$ ${\eta }^{(2)}=\left[\begin{array}{c}0.04702320745376396\\ 0.334174641833777\\ -0.9043336166358197\\ 0.2613366345126636\end{array}\right]$ ${\lambda }_3=-2.741255286528889$ ${\eta }^{(3)}=\left[\begin{array}{c}0.5641570498877014\\ 0.09332500337954595\\ 0.2860200054465712\\ 0.7689016993677129\end{array}\right]$ ${\lambda }_4=8.797986800782214$ ${\eta }^{(4)}=\left[\begin{array}{c}-0.7975286849631742\\ -0.156031599737972\\ 0.06812376684627766\\ 0.5787584029064224\end{array}\right]$

Források

• Numerikus módszerek, 1st, Kolozsvári Egyetemi Kiadó (2008) 
• Digitális tankönyvtár/Természettudományok/Matematika/Numerikus módszerek 1./Jacobi-módszer

További információk

• Press, WH; Teukolsky, SA & Vetterling, WT et al. (2007), "Section 11.1. Jacobi Transformations of a Symmetric Matrix", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
• Rutishauser, H. (1966). „Handbook Series Linear Algebra: The Jacobi method for real symmetric matrices.”. Numerische Mathematik 9 (1), 1–10. o. DOI:10.1007/BF02165223. 
• Sameh, A.H. (1971). „On Jacobi and Jacobi-like algorithms for a parallel computer”. Mathematics of Computation 25 (115), 579–590. o. DOI:10.1090/s0025-5718-1971-0297131-6. JSTOR 2005221. 
• Shroff, Gautam M. (1991). „A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix”. Numerische Mathematik 58 (1), 779–805. o. DOI:10.1007/BF01385654. 
• Veselić, K. (1979). „On a class of Jacobi-like procedures for diagonalising arbitrary real matrices”. Numerische Mathematik 33 (2), 157–172. o. DOI:10.1007/BF01399551. 
• Veselić, K. (1979). „A quadratically convergent Jacobi-like method for real matrices with complex eigenvalues”. Numerische Mathematik 33 (4), 425–435. o. DOI:10.1007/BF01399324.