„Numerikus módszerek” változatai közötti eltérés

Innen: TételWiki
55. sor: 55. sor:
  
 
===Gauss-Jordan elimináció===
 
===Gauss-Jordan elimináció===
 +
  
 
===LU dekompozíció===
 
===LU dekompozíció===
 +
Legyen '''A''' egy kvadratikus mátrix, erre az LU felbontás: A = LU. Az L és U mátrixok alsó illetve felső háromszög mátrixok (főátlóban is vannak elemek). [http://hu.wikipedia.org/wiki/LU_felbont%C3%A1s#Egyszer.C5.B1_p.C3.A9lda Példa]
 +
 +
====Alkalmazása====
 +
# Determináns számolás: det(A) = det(L)*det(U)
 +
:: A háromszög mátrixok determinánsa a főátlóban lévő elemek szorzata, ezért ez nagyon egyszerűen számolható
 +
# Mátrix inverz: <math>A^{-1} = U^{-1}L^{-1}</math>
 +
:: Háromszög mátrix inverze könnyen számolható, ezért jó ez a felbontás.
  
 
===Singular Value Decomposition - Szinguláris érték dekompozíció ===
 
===Singular Value Decomposition - Szinguláris érték dekompozíció ===

A lap 2011. június 9., 15:31-kori változata

Diffegyenlet-megoldó módszerek

Euler-módszer

A legegyszerűbb egylépéses módszer. Az y(x=0)=y0 kezdőfeltétellel megadott, y’=f(x,y) diffegyenlet megoldása esetén az Euler lépés alakja (Taylor-sorfejtés első két tagja): y_(n+1)=y_n+h*f(x_n,y_n)

Euler-módszer

Hibája: Taylor-sorfejtést tovább írjuk, a különbség O(h^2) lesz. Használata nem javasolt, mert a hibák hamar felösszegződnek, a megoldás „felrobban”. Ennek elkerülésére érdemes lehet használni az implicit Euler-módszert: y_(n+1)=y_n+h*f(x_{n+1},y_{n+1}). Ez nagy h értékekre is stabil marad.

Runge-Kutta módszer

Miért használjuk? Mert sokkal pontosabb, mint az Euler-módszer.

Másodrendű RK (vagy midpoint method - középponti módszer)

k_1=h\,f(x_n,y_n)\,
k_2=h\,f \left ( x_n+\frac{1}{2} h,y_n+\frac{1}{2} k_1 \right ) \,
y_{n+1}=y_n+k_2+O(h^3)\,

RK2.png

Ez a módszer tehát harmadrendig pontos. Általánosan az n-ed rendű RK-nak O(h^{n+1}) hibája van.

Negyedrendű RK

k_1=h\,f(x_n,y_n)\,
k_2=h\,f \left ( x_n+\frac{1}{2} h,y_n+\frac{1}{2} k_1 \right ) \,
k_3=h\,f \left ( x_n+\frac{1}{2} h,y_n+\frac{1}{2} k_2 \right ) \,
k_4=h\,f(x_n+h,y_n+k_3)\,
y_{n+1} = y_n + \frac{1}{6} k_1 + \frac{1}{3} k_2 + \frac{1}{3} k_3 + \frac{1}{6} k_4 + O(h^5)

Rk4 sajat.png

A negyedrendű módszerben négyszer kell kiértékelni az f függvényt, míg az Euler-módszernél egyszer kellett. Ezért ennek a használata akkor gazdaságos, ha ugyanakkora pontosság mellett legalább négyszer akkora lehet a lépésköz.

Adaptív RK

Egy differenciálegyenlet megoldása során lehetnek gyorsan és lassan változó szakaszok a függvényben. A lassan változó szakaszok integrálása során nagyobb lépéseket is tehetünk a hiba növekedése nélkül. Ennek a megoldására szolgál az adaptív Runge-Kutta módszer. Alapötlete, hogy egy lépést tegyünk meg egyszer teljesen (2h-val, y_1), egyszer pedig két fél lépésben (h-val, y_2). Mindegyik lépés 4 függvény kiértékelést igényel (3*4), de ebből kettő megegyezik, így 11 kiértékelés szükséges a 2*4 helyett, ami a két fél lépésből jönne össze.

y(x+2h) = y_1 + (2h)^5 \Phi + O(h^6)\,
y(x+2h) = y_1 + 2(h^5) \Phi + O(h^6)\,

A kettő közti különbség:

\Delta = y_2 - y_1\,

A különbség h^5-nel skálázik. Ha egy h_1 lépés eredménye \Delta_1, és mi \Delta_0 hibát akarunk elérni, akkor h_0 lépést kell tennünk, ami: h_0 = h_1 \left | \frac{\Delta_0}{\Delta_1} \right | ^{0.2}

Ha h_1>h_0, akkor meg kell ismételni a számolást egy kisebb lépéssel, ha pedig h_1<h_0, akkor a következő lépésben használhatjuk h_0-t lépésként.

Egyenletrendszerek megoldása

Gauss-Jordan elimináció

LU dekompozíció

Legyen A egy kvadratikus mátrix, erre az LU felbontás: A = LU. Az L és U mátrixok alsó illetve felső háromszög mátrixok (főátlóban is vannak elemek). Példa

Alkalmazása

  1. Determináns számolás: det(A) = det(L)*det(U)
A háromszög mátrixok determinánsa a főátlóban lévő elemek szorzata, ezért ez nagyon egyszerűen számolható
  1. Mátrix inverz: A^{-1} = U^{-1}L^{-1}
Háromszög mátrix inverze könnyen számolható, ezért jó ez a felbontás.

Singular Value Decomposition - Szinguláris érték dekompozíció

Sokszor előfordul, hogy a mátrix, amit invertálni akarunk, közel van a szingulárishoz (det A ≈ 0), és sem a Gauss-elimináció, se az LU felbontás nem jár sikerrel.

Adott egy A mátrixunk, ami MxN méretű. Ezt a mátrixot felírhatjuk UWVT formában, ahol:

  • U: MxN, oszlop-ortogonális mátrix
  • W: NxN, diagonális, a szinguláris értékeket tartalmazza
  • VT: NxN, ortogonális mátrix

A módszer segítségével nem-négyzetes mátrixokat is tudunk invertálni (pszeudoinverz) a következő módon:

A^{-1} = V\,[diag(1/w_j)]\,U^T

Ami problémát okozhat, az a szinguláris értékek reciproka, ha az nulla, vagy nagyon közel van nullához. A megoldás, hogy ebben az esetben az 1/wj-t nullának vesszük.

Optimalizációs módszerek - szélsőérték keresés

Konjugált gradiens módszer

Szimulált hőkezelés

A módszer elnevezése az anyagtudomány területéről ered, ahol hőkezelési eljárásokkal lehet változtatni egy anyag kristályosodási méretét. Számítógépes módszerként egy sokdimenziós függvény energiaminimumának megkeresésére lehet használni.

Működési struktúra:

  1. Válasszunk egy tetszőleges kezdőállapotot (i)
  2. Válasszuk ki az egyik szomszédot (j)
  3. Ha a szomszéd energiája kisebb, átlépünk rá
  4. Ha nagyobb a szomszéd energiája, az energiakülönbség, és egy globális T paraméter által meghatározott valószínűség szerint elfogadjuk a nagyobb energiájú helyet

Az elfogadási valószínűségek tehát:

  • ha f(j) ≤ f(i), akkor 1
  • ha f(j) > f(i), akkor e^{\frac{f(i)-f(j)}{T}}

A T hőmérsékletet kezdetben nagynak választva, majd folyamatosan csökkentve ezzel a módszerrel megtalálhatjuk a függvény globális minimumát.