Nemline´aris egyenletrendszerek megold´asa
2014. ´aprilis 15.
Nemline´aris egyenletrendszerek Az egyenletrendszer a k¨ ovetkez˝ o form´aban adott: fi (x1 , x2 , ..., xM ) = 0
i = 1...N
I
az fi f¨ uggv´enyek az xj v´altoz´ okban nem line´arisak
I
egyenletrendszer eset´en t¨ obb f¨ uggv´eny gy¨ ok´et keress¨ uk szimult´an m´odon
Sokkal nehezebb probl´ema, mint a line´aris eset. I
ott az egyenletek line´aris kombin´algat´as´aval lehetett elimin´alni
I
line´arisan kombin´alni itt is lehet, de nem vezet megold´asra
A megold´as l´ete A megold´as l´ete I
N > M esetben ´altal´aban nincsen megold´as
I
N ≤ M esetben sem garant´alt
I
ha van megold´as, akkor nem garant´alt, hogy egy´ertelm˝ u
I
gyakori, hogy a gy¨ ok¨ ok nem diszkr´etek, eg´esz intervallum gy¨ok
I
lehetnek nem val´os gy¨ ok¨ ok is
Inverzf¨ uggv´eny-t´etel I
ha egy f f¨ uggv´eny egy x pontban folytonos, ´es a deriv´altja nem nulla, akkor az x pont egy k¨ ornyezet´eben invert´alhat´o
I
ez ´altal´anos´ıthat´o t¨ obbdimenzi´ os esetre is
I
N ≤ M esetben tudunk mondani valamit a megold´as l´et´ere
Mit˝ol jobb egyik vagy m´asik m´odszer?
F¨ uggv´enyki´ert´ekel´esek sz´ama I
min´el kevesebb f¨ uggv´enyki´ert´ekel´es mellett
I
min´el pontosabban meg akarjuk hat´arozni a gy¨ok¨ot
I
kovergencia sebess´ege
Stabilit´as I
´altal´aban k´ezzel” kell a gy¨ ok k¨ ozel´eb˝ ol ind´ıtani ” garant´alja-e valami, hogy ott is marad a k¨ ozelben
I
nem diverg´al-e el a v´egtelenbe
I
A m´odszerek ´altal´anos tulajdons´agai
Sokat seg´ıt, ha nem csak f -et, de a deriv´altj´at is ismerj¨ uk I
j´oval gyorsabb algoritmusok
Egy v´altoz´os esetben vannak hat´ekony m´ odszerek I
megfelel˝oen j´ol viselked˝ o f¨ uggv´enyekre
I
a gy¨ok¨oket be lehet keretezni
Iterat´ıv m´odszerek A nem line´aris m´odszerek mindig iterat´ıvak I
kiindulunk valamilyen ´ert´ekekb˝ ol
I
ez lehet egy intervallum, amin bel¨ ul a gy¨ ok¨ ot sejtj¨ uk
I
a gy¨ok¨ot l´ep´esr˝ol l´ep´esre k¨ ozel´ıtj¨ uk meg
A k¨ozel´ıt˝o m´odszer k¨ovetkezm´enye I
a gy¨ok¨ot ´altal´aban csak k¨ ozel´ıt˝ oleg kapjuk meg
I
viszont tetsz˝olegesen kis hib´aval meghat´arozhatjuk
Nem mindig konverg´al I
el kell tudni d¨onteni, hogy konverg´al-e
I
megfelel˝o helyr˝ol kell kiindulni
I
j´o helyre konverg´alt-e?
Gy¨ok bekeretez´ese egy dimenzi´oban P´elda gy¨ok bekeretezhet˝ os´eg´ere I
tudjuk, hogy a f¨ uggv´eny folytonos a < x < b intervallumon
I
f (a) < 0 ´es f (b) > 0
⇒
l´etezik gy¨ ok az intervallumon
Rosszul viselked˝o f¨uggv´enyek A bekeretez˝os m´odszer nem mindig egyszer˝ u A f˝o probl´em´at a szingul´aris viselked´es okozza I
a f¨ uggv´eny nem folytonos
I
valahol diverg´al
I
valamelyik deriv´altja diverg´al
A gy¨ok l´ete nem f´eltetlen¨ ul jelent el˝ ojelv´alt´ast I
lehet, hogy a gy¨ok minimumhelyen van
I
de a minimumhely nem felt´etlen gy¨ ok
Egy intervallumon bel¨ ul sok gy¨ ok is lehet
Szakaszonk´ent folytonos, divergens f¨uggv´eny
F¨uggv´eny rosszul viselked˝o deriv´alttal
Gy¨ok¨ok ´es minimumok konfigur´aci´oi
A nem line´aris gy¨okkeres´es a f¨uggv´eny anal´ızis´evel kezd˝odik A nem line´aris algoritmusok nem garant´altan j´ ok I
nincsen glob´alis megold´as
I
mindig valami j´o becsl´es kell a gy¨ ok¨ ok hely´ere
Iterat´ıv m´odszerek gyakori probl´em´aja I
ha rossz helyr˝ol eldiverg´al
I
j´o kiindul´asi pontokat kell tal´alni
I
a j´o kiindul´asi pontok megtal´al´as´ara nincsen algoritmus
I
analitikusan kell kezelni a f¨ uggv´enyt
´ Erdemes mindig ´abr´azolni I
ha k¨onnyen deriv´alhat´ o, akkor a deriv´altakat is vizsg´alni
Felez˝os m´odszer
Kiindul´as I
valamilyen m´odon siker¨ ult bekeretezni a gy¨ ok¨ot
I
adott teh´at egy [a, b] intervallum
I
f (a)f (b) < 0, azaz a f¨ uggv´eny el˝ ojelet v´alt
Iterat´ıv l´ep´es I
megfelezz¨ uk az intervallumot
I
a felez˝opont el˝ojele megegyezik valamelyik v´egpont el˝ojel´evel
I
az el˝ojelv´alt´o f´el intervallumot tartjuk meg
A felez˝os m´odszer le´all´asi felt´etele
A konvergenci´ahoz sz¨ uks´eges l´ep´esek sz´ama I
a kiindul´asi intervallum hossza: 0
I
a gy¨ok ´ert´ek´ere el˝ o´ırt pontoss´ag:
I
a m´odszer az intervallumot felezi, ´ıgy a l´ep´esek sz´ama n = log2
0
Le´all´asi felt´etel I
ha az intervallum hossza el´eri -t, meg´allunk
I
gy¨oknek az intervallum felez˝ opontj´at tekintj¨ uk
A felez˝os m´odszer tulajdons´agai
F˝o el˝ony: I
a m´odszer mindig konverg´al
F˝o gondok: I
csak el˝ojelv´alt´o esetben m˝ uk¨ odik
I
csak egy gy¨ok¨ot tal´al meg
I
ha a f¨ uggv´enynek szakad´asa van, ´es ez´ert v´alt el˝ojelet, akkor a m´odszer nem a gy¨ ok¨ ot, hanem a szakad´asi pontot tal´alja meg
A szek´ans m´odszer
Kiindul´as I
valamilyen m´odon megk¨ ozel´ıtett¨ uk a gy¨ ok¨ ot
I
nem is kell felt´etlen bekeretezni
I
egy x0 ´es x1 pontb´ ol indulunk
Iterat´ıv l´ep´es I
tekintj¨ uk az f (xi−1 ) ´es f (xi ) ´ert´ekeket
I
xi−1 ´es xi k¨oz¨ott line´arisan interpol´aljuk a f¨ uggv´eny
I
az xi+1 ´ert´eke a line´aris interpol´aci´ o gy¨ oke lesz
A szek´ans m´odszer
A szek´ans m´odszer tulajdons´agai Gyorsabban konverg´al, mint a felez˝ os m´ odszer I
ott az intervallum mindig a fel´ere cs¨ okkent
I
itt a konvergencia sebess´ege gyenge hatv´any´aval megy lim |i+1 | = c · |i |1,618
i→∞
A m´odszer nem tartja bekeretezve a gy¨ ok¨ ot I
nem csak ott m˝ uk¨ odik, ahol a f¨ uggv´eny el˝ ojelet v´alt
I
de ha a gy¨ok lok´alis minimum k¨ orny´ek´en van, akkor elt´eved
I
ak´ar a v´egtelenbe is elmehet
Akkor m˝ uk¨odik j´ol, ha a f¨ uggv´eny j´ ol k¨ ozel´ıthet˝ o egyenessel.
A szek´ans m´odszer egy probl´em´aja
Regula falsi m´odszer
A m´odszer az el˝oz˝o kett˝ o kombin´aci´ oja I
bekeretezve tartja a gy¨ ok¨ ot
I
de nem az intervallumot felezgeti, hanem egyenessel metszi az abszcissz´at
A szek´ans m´odszert ´ıgy m´ odos´ıtjuk I
nem a legr´egebbi pontot dobjuk el
I
(hiszen ´ıgy kifuthatn´ank az intervallumb´ ol)
I
hanem a metsz´espont megtal´al´asa ut´ana azt a kett˝ot tartja meg, amelyekn´el a f¨ uggv´eny el˝ ojele k¨ ul¨ onb¨ oz˝ o
Regula falsi m´odszer
A regula falsi m´odszer algoritmusa Kiindul´as I
valamilyen m´odon siker¨ ult bekeretezni a gy¨ ok¨ot
I
adott teh´at egy [a, b] intervallum
I
f (a)f (b) < 0, azaz a f¨ uggv´eny el˝ ojelet v´alt
Iterat´ıv l´ep´es I
[a, b]-n line´arisan interpol´alunk
I
megkeress¨ uk az egyenes ´es az x-tengely metsz´espontj´at
I
azt az u ´j intervallumot tartjuk meg, ahol f el˝ojelet v´alt
N´emileg gyorsabb, mint a felez˝ os m´ odszer
Magasabb rend˝u m´odszerek A szek´ans m´odszern´el egyenessel interpol´altunk I
csak kell˝oen sima f¨ uggv´enyekre hat´ekony
I
interpol´alhatn´ank magasabb rend˝ u f¨ uggv´ennyel is
I
ehhez nem el´eg az intervallum k´et v´egpontja
P´eld´aul: inverz kvadratikus m´ odszer I
nem kett˝o, hanem h´arom ponttal dolgozunk
I
ezekre parabol´at illeszt¨ unk y = ax 2 + bx + c alakban
I
a gy¨ok¨oket a megold´ ok´eplettel hat´arozzuk meg
Magasabb rendre nehezen ´altal´anos´ıthat´ o I
nem l´eteznek megold´ ok´epletek
A belassul´ast elker¨ul˝o m´odszerek Vannak f¨ uggv´enyek, ahol az elvileg gyorsabb m´ odszerek lemaradnak I
pl. a regula falsi lehet lassabb a felez˝ od m´ odszern´el is
I
ilyenkor ´erdemes a m´ odszereket kombin´alni
I
figyelj¨ uk a konvergencia sebess´eg´et
I
ha lass´ u, akkor m´as m´ odszerre v´altunk
Wijngaarden–Dekker–Brent-m´ odszer (r¨ oviden Brent) I
alapesetben az inverz kvadratikus m´ odszert haszn´alja
I
ha az u ´j pont a kereten k´ıv¨ ul esik, vagy
I
a konvergencia t´ ul lass´ u
I
akkor ink´abb felezi az intervallumot
A f¨uggv´eny deriv´altj´anak felhaszn´al´asa
Az eddigit m´odszerek nem haszn´alt´ak a f¨ uggv´eny deriv´altj´at I
viszont lehet, hogy az is expliciten adott
I
ekkor gyorsabb m´ odszer lehets´eges
A Newton–Ralphson-m´ odszer I
egyetlen pontb´ol indulunk
I
megh´ uzzuk a f¨ uggv´eny ´erint˝ oj´et
I
az x tengellyel vett metszet lesz az u ´j pont
A Newton–Ralphson-m´odszer
A Newton–Ralphson-m´odszer tulajdons´agai Kell˝oen sima f¨ uggv´eny eset´en j´ ol m˝ uk¨ odik, ugyanis I
a gy¨ok k¨or¨ uli Taylor-sorb´ ol el´eg csak az els˝ o tagot megtartani 1 f (x + δ) ≈ f (x) + f 0 (x)δ + f 00 (x)δ 2 + ... 2
I
ezzel a gy¨okt˝ol val´ o elt´er´es egy j´ o k¨ ozel´ıt´ese δ≈−
f (x) f 0 (x)
Bel´athat´o, hogy a konvergencia sebess´ege n´egyzetes: i+1 = c · 2i
Newton–Ralphson-m´odszer: t´ul lapos f¨uggv´eny
Newton–Ralphson-m´odszer: p´aratlan” f¨uggv´eny ”
A Newton–Ralphson-m´odszer jav´ıt´asa A Newton–Ralphson-m´ odszer gyakran nem konverg´al I
ilyenkor ´erdemes hibrid m´ odszert v´alasztani
I
a Wijngaarden–Dekker–Brent-m´ odszerhez hasonl´oan
Egy dimenzi´oban nem szabad numerikus deriv´altat haszn´alni I
t¨obb f¨ uggv´enyki´ert´ekel´est ig´enyel
I
nem el´eg pontos, ´ıgy lass´ıtja a konvergenci´at
I
a szek´ans m´odszer gyorsabb
A Newton–Ralphson-m´ odszer lok´alisan gyors, de glob´alisan instabil I
´erdemes ez´ert m´as m´ odszerrel bekeretezni a gy¨ok¨ot
I
ha m´ar k¨ozel j´arunk, akkor N–R-m´ odszerrel pontos´ıtjuk
Polinomok gy¨okei Az n-ed rend˝ u polinomnak n gy¨ oke van I I
lehetnek val´osak vagy komplexek ha az egy¨ utthat´ok val´ osak, akkor I I
a gy¨ ok¨ ok val´ osak, vagy komplex konjug´alt p´arok
A gy¨ok¨oket egyes´evel keress¨ uk I
valamilyen m´odszerrel egy gy¨ ok¨ ot megtal´alunk: r
I
leosztjuk a polinomot (x − r )-rel Pi (x) = (x − r )Pi+1 (x)
I
Pi+1 meghat´aroz´as´ara l´etezik egyszer˝ u algoritmus
I
az eggyel alacsonyabb fok´ u polinom egy gy¨ ok´et ism´et valami elemi algoritmussal keress¨ uk
Polinomok gy¨okeinek megtal´al´asa Probl´em´ak: I
a gy¨okkeres´es nagyon sok l´ep´est ig´enyel
I
felhalmoz´odnak a numerikus hib´ak
I
a megtal´alt gy¨ok, amivel osztunk, sem teljesen pontos
Jav´ıt´asi lehet˝os´eg I
megkeress¨ uk a gy¨ ok¨ oket
I
egyenk´ent pontos´ıtjuk ˝ oket a Newton–Ralphson-m´odszerrel
I
gy¨ok¨ok pol´ıroz´asa” ”
M´odszerek komplex gy¨ ok¨ ok megtal´al´as´ara I
ld. Numerical Recipes
I
pl. Laguerre-m´odszer
Gy¨ok¨ok keres´ese t¨obb dimenzi´oban T¨obb dimenzi´oban nincsen ´altal´anosan j´ o gy¨ okkeres˝o m´odszer. I
a probl´ema m´ar k´et f¨ uggv´eny eset´en is nagyon bonyolult
A t¨obbdimenzi´os m´odszer v´azlata Meg kell hat´arozni valahogyan az fi f¨ uggv´enyek z´er´o-kont´ urjait I
a gy¨ok¨ok a kont´ urok metsz´espontjaiban lesznek
I
de eleve a kont´ urok meghat´aroz´asa is k¨ ozel lehetetlen
Mindenk´eppen tudnunk kell r´eszleteket is a probl´em´ar´ol I
h´any gy¨ok¨ot v´arunk
I
ezeket kb. hol v´arjuk
Jobb h´ıj´an I
olyan m´odszert keres¨ unk, ami egy gy¨ ok¨ ot meg tud tal´alni
I
abban az esetben, ha a gy¨ okt˝ ol el´eg k¨ ozelr˝ ol indulunk
Newton–Ralphson-m´odszer t¨obb dimenzi´oban A deriv´altat most a teljes Jacobi-m´atrix helyettes´ıti: Jik =
∂fi ∂xk
Ezzel a f¨ uggv´eny Taylor-sora f(x + δx) = f(x) + Jδx + ... Hasonl´oan, mint egy dimenzi´ oban I
keress¨ uk azt a δx vektort,
I
ami a gy¨ok ir´any´aba l´epteti az aktu´alis legjobb becsl´est
Ehhez a Jδx = −f line´aris egyenletrendszert kell megoldani, majd xi+1 = xi + δx
