Wikipédia

„Jacobi-módszer” változatai közötti eltérés

Laptörténet interaktív böngészése
[ellenőrzött változat][ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
a összedolgozandó
a Articles with example pseudocode kategória eltávolítva (a HotCattel)
1. sor:
{{összedolgoz|Jacobi-féle sajátértékfeladat-megoldási módszer}}
A [[numerikus analízis]]ben, a '''Jacobi-féle módszer''' egy [[iteráció]]s módszer valamely valós szimmetrikus mátrix [[sajátvektor és sajátérték|sajátérték és sajátvektorának]] kiszámítására. (ez a folyamat mátrix diagonalizálás néven ismert). Nevét [[Carl Gustav Jacob Jacobi]], útán kapta aki a módszszert először 1846-ban publikálta,<ref>{{cite journal
A '''Jacobi-módszer''' (vagy '''Jacobi-féle sajátértékmódszer''') néven ismert eljárás egy [[iteráció|iteratív]] módszer, amely kis méretű (n<10) szimmetrikus valós [[mátrix (matematika)|mátrixok]] [[Sajátvektor és sajátérték|sajátértékeinek]] és [[Sajátvektor és sajátérték|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.
|last=Jacobi |first=C.G.J. |authorlink=Carl Gustav Jacob Jacobi
A Jacobi-módszer esetében az iterációs képlet a következő lesz:
|url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002144522
|title=Über ein leichtes Verfahren, die in der Theorie der Säkularstörungen vorkommenden Gleichungen numerisch aufzulösen
|journal=[[Crelle's Journal]]
|volume=30 |year=1846 |pages=51–94
|language=German
}}</ref> de csak az 1950-es években vált elterjedtté a számítógépek fejlődése miatt.<ref>{{cite journal
|first=G.H. |last=Golub
|first2=H.A. |last2=van der Vorst
|title=Eigenvalue computation in the 20th century
|journal=Journal of Computational and Applied Mathematics
|volume=123 |issue=1-2 |year=2000 |pages=35&ndash;65
|doi=10.1016/S0377-0427(00)00413-1
}}</ref>
 
== Leírás ==
<math>x_i^{(k)}={b_i\over a_{ii}}-\sum_{j=1,j\ne i}^n a_{ij} x_j^{(k-1)}</math>
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 <math>\mathbf{R^{-1} = R^T}</math>
, 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 <math>\mathbf{A}</math> szimmetrikus mátrix
diagonalizálása megoldható az <math>\mathbf{R}</math> ortogonális hasonlósági transzformáció segítségével,
azaz
:<math>
\begin{align}
\mathbf{R^T\cdot A\cdot R = \Lambda}.
\end{align}
</math>
 
Vegyük példaként a <math>2\times 2</math> típusú mátrix esetét. Ekkor a transzformációhoz használjuk a
Ahhoz, hogy könnyebben megérthessük a módszer elvét, tekintsünk egy példát:
:<math>
\mathbf{R} =
\begin{pmatrix}
\cos\varphi & -\sin\varphi \\
\sin\varphi & \cos\varphi
\end{pmatrix}
</math>
 
síkforgatást leíró mátrixot, ahol <math>\varphi</math> a forgatás szöge. Ha felírjuk ezzel az <math>\mathbf{A' = R^T\cdot A\cdot R}</math>
<math>\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} {x_1 \choose x_2}={b_1 \choose b_2}</math>
szimmetria transzformációt, a transzformálás után az <math>\mathbf{A'}</math> mátrix elemei
:<math>
\begin{align}
a^'_{11} &= a_{11}\cos^2\varphi+2a_{21}\sin\varphi\cos\varphi+a_{22}\sin^2\varphi \\
a^'_{22} &= a_{11}\sin^2\varphi-2a_{21}\sin\varphi\cos\varphi+a_{22}\cos^2\varphi \\
a^'_{21} &= a_{21}(\cos^2\varphi-\sin^2\varphi)+(a_{22}-a_{11})\sin\varphi\cos\varphi = a^'_{12}
\end{align}
</math>
lesznek. Ha a nem átlós <math>a^'_{12}</math> és <math>a^'_{21}</math> elemeket 0-vá alakítjuk, az elforgatási szögre a következő egyenletet kapjuk:
 
:<math>
Hogy jobban áttekinthető legyen, átírhatjuk egyenletek formájába, amely így nézhet ki:
\begin{align}
\cot^2\varphi+\frac{a_{22}-a_{11}}{a_{21}}\cot\varphi-1 &= 0,
\end{align}
</math>
 
melynek alapján
<math>\begin{cases} a_{11}x_1+a_{12}x_2=b_1 \\ a_{21}x_1+a_{22}x_2=b_2 \end{cases}</math>
 
:<math>
Innen kifejezhető az x<sub>1</sub> és x<sub>2</sub> ismeretlen, így a következő egyenleteket kapjuk:
\begin{align}
\tan\varphi &= \Biggl[ \frac{a_{11}-a_{22}}{2a_{12}}\pm \sqrt{\Bigl(\frac{a_{11}-a_{22}}{2a_{12}}\Bigl)^2+1} \Biggl]^{-1}.
\end{align}
</math>
 
Innen megkaphatjuk a <math>
<math>x_1=-{a_{12}\over a_{11}}x_2+{b_1\over a_{11}}</math>,
\cos\varphi=(1+\tan\varphi)^{-1/2}
</math>
és <math>\sin\varphi = \tan\varphi\cos\varphi</math> függvényeket, melyekkel
felépítjük a forgatásmátrixot.
Az így kapott <math>\mathbf{A'}</math> mátrix diagonális, tehát az átlóban található együtthatók a sajátértékek,
míg az <math>\mathbf{R}</math> forgatásmátrix két oszlopa a sajátértékeknek megfelelő két sajátvektor:
:<math>
\begin{align}
\lambda_1&=a^'_{11}, & \mathbf{x}^{(1)} &=
\begin{bmatrix}
\cos\varphi \\
\sin\varphi
\end{bmatrix}
; \\
\lambda_2 &= a^'_{22}, & \mathbf{x}^{(2)} &= \begin{bmatrix}
-\sin\varphi \\
\cos\varphi
\end{bmatrix}.
\end{align}
</math>
 
== Általános eset ==
<math>x_2=-{a_{21}\over a_{22}}x_1+{b_2\over a_{22}}</math>
 
A következőkben nézzük meg, hogy miként működik ez a módszer általános esetben
Az így kapott egyenletrendszert úgy oldhatjuk meg, hogy kezdetben kiindulunk az <math>x_1^{(0)}</math>, illetve az <math>x_2^{(0)}</math> legjobb becslésünkből, vagy az egyszerűség kedvéért indulhatunk 0-ból is. Ezután felhasználva az
<math>n\times n</math> méretű mátrixok esetén. A sík-forgatás mátrixunk az egységmátrixtól csak az <math>r_{ii},
r_{ij} , r_{ji}, r_{jj}</math> elemekben tér el, vagyis
:<math>
\mathbf{R}_{ij} = \begin{pmatrix}
1 & \vdots & & \vdots & 0 \\
\cdots & \cos\varphi &\cdots & -\sin\varphi & \cdots \\
& \vdots & \ddots&\vdots& & \\
\cdots & \sin\varphi &\cdots & \cos\varphi & \cdots \\
0 & \vdots & & \vdots & 1
\end{pmatrix}
</math>
 
Ezt felhasználva az
<math>x_1^{(k)}=-{a_{12}\over a_{11}}x_2^{(k-1)}+{b_1\over a_{11}}</math>,
:<math>
\mathbf{A'= R^T_{ij}\cdot A\cdot R_{ij}}
</math>
ortogonális hasonlósági transzformációval nullákat viszünk be az <math>a^'_{ij}</math>és <math>a^'_{ji}</math> elemek helyére.
A szorzás elvégzése után az
:<math>
\begin{align}
a^'_{ik} &= a^'_{ki}=a_{ik}\cos\varphi+a_{jk}\sin\varphi, k=\overline{1,n} \\
a^'_{jk} &= a^'_{kj}=a_{ik}\sin\varphi+a_{jk}\cos\varphi, k\neq i,j \\
a^'_{ii} &= a_{ii}\cos^2\varphi+2a_{ji}\sin\varphi\cos\varphi+a_{jj}\sin^2\varphi \\
a^'_{jj} &= a_{ii}\sin^2\varphi-2a_{ji}\sin\varphi\cos\varphi+a_{jj}\cos^2\varphi \\
a^'_{ji} &= a_{ji}(\cos^2\varphi-\sin^2\varphi)+(a_{jj}-a_{ii})\sin\varphi\cos\varphi=a^'_{ij}
\end{align}
</math>
 
mátrixelemeket kapjuk eredményül. Ezek közül megköveteljük, hogy az <math>a^'_{ij}</math> , illetve az <math>a^'_{ji}</math>
<math>x_2^{(k)}=-{a_{21}\over a_{22}}x_1^{(k-1)}+{b_2\over a_{22}}</math>
elemek 0-ák legyenek. Ekkor a
:<math>
\cot^2\varphi+\frac{a_{jj}-a_{ii}}{a_{ji}}\cot\varphi -1=0
</math>
egyenlethez jutunk, melyet megoldva a forgatás szöge
:<math>
\tan\varphi = \Bigg[\frac{a_{ii}-a_{jj}}{2a_{ij}}\pm\sqrt{\Big( \frac{a_{ii}-a_{jj}}{2a_{ji}}
\Big)^2+1} \Bigg]^{-1}
</math>
lesz.
 
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.
 
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
== Források ==
feltételek mellett az átlón kívüli elemek négyzetösszege egy lépésben <math>2\mid a_{ij}\mid^2</math>-tel csökken,
* Lázár Zsolt, Lázár József, Járai-Szabó Ferenc: Numerikus módszerek, egyetemi jegyzet, 2008
vagyis monoton módon tart 0-hoz.
* Digitális tankönyvtár/Természettudományok/Matematika/Numerikus módszerek 1./Jacobi-módszer
 
<math>A_l</math>-lel jelölve az <math>l</math>. transzformáció utáni mátrixot, a transzformáció-sorozatot a következőképpen írhatjuk:
[[Kategória:Lineáris algebra]]
:<math>
\mathbf{A_0=A, A_1=R^T_1\cdot A_0\cdot R_1, A_2=R^T_2\cdot A_1\cdot R_2,\dots ,A_l=R^T_l\cdot A_{l-1}\cdot R_l,\dots,}
</math>
 
ahol <math>\mathbf{R_l}</math>-el valamely nem-átlós elemre alkalmazott transzformációt jelöltük. Képezzük a
transzformációs mátrixok
:<math>
\begin{align}
\mathbf{X_l=R_0\cdot R_1\cdots R_l},& & l=0,1,2,\dots,
\end{align}
</math>
szorzatát. Ha végtelen sok transzformációt végzünk, akkor
:<math>
\begin{align}
\lim_{l\to\infty}\mathbf{A_l = \Lambda}, && \lim_{l\to\infty}\mathbf{X_l = X}
\end{align}
</math>
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.
 
 
Beszéljünk még egy keveset a módszer konvergenciájáról, melyet a <math>\tan\varphi\leq 1</math> feltétel
tiszteletbentartása biztosít, ami egy <math>\varphi\leq\pi/4</math> forgatásnak felel meg. Ezt úgy tudjuk
biztosítani, hogy a két gyök közül a "+" előjelest válasszuk, amennyiben <math>(a_{ii}-a_{jj})/a_{ji}>0</math>
é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:
:<math>
\tan\varphi = sign \Big( \frac{a_{ii}-a_{jj}}{2a_{ji}} \Big) \Bigg[ \left | \frac{a_{ii}-a_{jj}}{2a_{ji}} \right | +\sqrt{\Big( \frac{a_{ii}-a_{jj}}{2a_{ji}} \Big)^2+1} \Bigg]^{-1}.
</math>
 
 
 
 
== Algoritmus ==
 
A leírt módszer a következő algoritmus segítségével alkalmazható számítógépre:
 
<source lang=python>
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
 
</source>
 
 
 
=== Példa ===
 
Legyen
<math>
A = \begin{pmatrix} 3 & 0 & 2 & 1 \\ 0 & 1 & 3 & 4 \\ 2 & 3 & 2 & 1 \\ 1 & 4 & 1 & 5 \end{pmatrix}
</math>
 
A ''jacobi'' a következő sajátértékeket és sajátvektorokat adja:
 
<math>
\lambda_1 = 3.8614176875601696
</math>
 
<math>
\eta^{(1)} = \begin{bmatrix}0.20847934594025172\\ -0.9248091113211869\\ -0.30940655891140356\\ 0.07437776036050801\end{bmatrix}
</math>
 
<math>
\lambda_2 = 1.0818507981865024
</math>
 
<math>
\eta^{(2)} = \begin{bmatrix}0.04702320745376396\\ 0.334174641833777\\ -0.9043336166358197\\ 0.2613366345126636\end{bmatrix}
</math>
 
<math>
\lambda_3 = -2.741255286528889
</math>
 
<math>
\eta^{(3)} = \begin{bmatrix}0.5641570498877014\\ 0.09332500337954595\\ 0.2860200054465712\\ 0.7689016993677129\end{bmatrix}
</math>
 
<math>
\lambda_4 = 8.797986800782214
</math>
 
<math>
\eta^{(4)} = \begin{bmatrix}-0.7975286849631742\\ -0.156031599737972\\ 0.06812376684627766\\ 0.5787584029064224\end{bmatrix}
</math>
 
 
== Referenciák ==
* {{cite book | last1=Zsolt | first1=Lázár| last2=József | first2=Lázár | last3=Ferenc | first3=Járai-Szabó |year=2008 | title=Numerikus módszerek | edition=1st | publisher=[[Kolozsvári Egyetemi Kiadó]]}}
{{reflist}}
 
 
 
== További olvasnivaló ==
{{refbegin}}
*{{Citation | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | publication-place=New York | isbn=978-0-521-88068-8 | chapter=Section 11.1. Jacobi Transformations of a Symmetric Matrix | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=570}}
* {{cite journal
|last=Rutishauser |first=H.
|title=Handbook Series Linear Algebra: The Jacobi method for real symmetric matrices.
|journal=Numerische Mathematik
|volume=9 |issue=1 |year=1966 |pages=1–10
|doi=10.1007/BF02165223 |mr=1553948
}}
* {{cite journal
|last=Sameh |first=A.H.
|title=On Jacobi and Jacobi-like algorithms for a parallel computer
|journal=[[Mathematics of Computation]]
|volume=25 |issue=115 |year=1971 |pages=579–590
|mr=297131 | jstor = 2005221 | doi = 10.1090/s0025-5718-1971-0297131-6
}}
* {{cite journal
|last=Shroff |first=Gautam M.
|title=A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix
|journal=Numerische Mathematik
|volume=58 |issue=1 |year=1991 |pages=779–805
|doi=10.1007/BF01385654 |mr=1098865
}}
* {{cite journal
|last=Veselić |first=K.
|title=On a class of Jacobi-like procedures for diagonalising arbitrary real matrices
|journal=Numerische Mathematik
|volume=33 |issue=2 |year=1979 |pages=157–172
|doi=10.1007/BF01399551 |mr=549446
}}
* {{cite journal
|last=Veselić |first=K.
|last2=Wenzel |first2=H. J.
|title=A quadratically convergent Jacobi-like method for real matrices with complex eigenvalues
|journal=Numerische Mathematik
|volume=33 |issue=4 |year=1979 |pages=425–435
|doi=10.1007/BF01399324 |mr=553351
}}
 
{{refend}}
 
 
[[Category:Numerikus analízis]]
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Jacobi-módszer”