Gyökkeresés iterációval

Keressük az $f(x)=0$ egyenlet gyökeit. Vagyis azon $x$-eket, amelyek kielégítik az egyenlőséget. Erre a numerikus analízis többféle lehetőséget nyújt: felező módszer, Newton-módszer, szelőmódszer. Most egy ezekhez hasonló módszert mutatunk be.

Matematikai bevezetés

Az $f(x)=0$ egyenlet átírható a vele egyenértékű $g(x)=x$ egyenletté. Szükséges kezdetben egy $x_{0}$ becsült érték. Ezt behelyettesítjük az előbbi egyenlet bal oldalára, és kapunk egy $x_{1}$ értéket. Ha ez megegyezik az $x_{0}$ értékünkkel, akkor ezek ketten közösen a megoldást képezik. Ellenkező esetben megismételhető az előbb leírt lépés $x_{1}$ ből kiindulva és létrehozható az $x_{2},x_{3},...,x_{n},...$ sor, aminek azt a tulajdonságát szeretnénk elérni, hogy konvergáljon a gyökhöz. Legyen az iterációs képletünk a következő:

$x_{(}n+1)=g(x_{n})$, $g(x)=x-Q*f(x)$

Itt Q egy állandó paraméter, amely a konvergenciát biztosítja. Az alábbiakban a g(x) függvény néhány típusára grafikusan ábrázoljuk az iterációt, hogy jobban érthető legyen:

Amint az ábra c és d pontjában látható, a színezett területen áthaladó, azaz

túlzottan meredek g(x) függvény esetén divergens az iteráció. Tehát úgy kell megválasztanunk a Q értékét, hogy az ne legyen túl nagy és legyen az iterációnk konvergens.

Konkrét példa

Legyen az $f(x)=x-e^{x}$ függvény, aminek keressük a gyökeit. A kezdeti tippünk legyen $x_{0}=0.5$ és legyen először a $Q=0.6$. Ekkor az iteráció első 7 lépése a következőképpen néz ki:

	$x_{n}$	$g(x_{n})=x_{n}-Q*f(x_{n})$	$x_{(}n+1)$	$|x_{(}n+1)-x_{n}|$
1	0.5	0.563918396	0.563918396	0.063918396
2	0.563918396	0.566952490	0.566952490	0.003034095
3	0.566952490	0.567131903	0.567131903	0.000179413
4	0.567131903	0.567142610	0.567142610	1.07072889e-05
5	0.567142610	0.567143250	0.567143250	6.39353343e-07
6	0.567143250	0.567143288	0.567143288	3.81782835e-08
7	0.567143288	0.567143290	0.567143290	2.27977877e-09

Láthatóan nagyon gyorsan bekonvergált a keresett gyökhöz. Nézzük most meg, hogy mi történik, ha $Q=2$

	$x_{n}$	$g(x_{n})=x_{n}-Q*f(x_{n})$	$x_{(}n+1)$	$|x_{(}n+1)-x_{n}|$
1	0.5	0.71306132	0.71306132	0.21306132
2	0.71306132	0.26722152	0.26722152	0.44583980
3	0.26722152	1.26378544	1.26378544	0.99656392
4	1.26378544	-0.69862084	-0.69862084	1.96240628
5	-0.698620839	4.72057550	4.72057550	5.41919634
6	4.72057550	-4.70275541	-4.70275541	-9.42333091
7	-4.70275541	225.203833	225.203833	229.906589

Látható ez esetben, hogy az iteráció divergens és a hiba tart a végtelenbe.

Konvergencia

Nézzük most meg részletesebben a konvergencia kérdését. Az optimális paraméter a Q-ra a következő: $Q={\frac {1}{f^{'}(x_{0})}}$, ez belátható, hogyha megnézzük a Newton-módszer-nél az iterációs képletet: $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\,\!$. Ezek alapján belátható, hogy a Newton módszer egy sokkal gyorsabban konvergáló módszer, mivel minden egyes lépés után beállítja a Q értékét az optimális értékre. Az iterációs módszer viszont annyiban jobb, hogy nem mindig áll rendelkezésünkre a függvény deriváltja, vagy nagyon nehézkes deriválni, így ki tudjuk ezt küszöbölni.

Algoritmus

A kód python programozási nyelvben van írva, az epszilon paraméter pedig a kívánt pontosságot jelenti.

import math
def Fx(X):
	return X-e^X
def Iteracio(Fx, x0, Q, epszilon):
        x1=x0-Q*Fx(x0)
        while abs(x1-x0)>epszilon:
                x0=x1
                x1=x0-Q*Fx(x0)
        return x1
print Iteracio(Fx, 0.5, 0.6, 0.0001)

A program a 3. lépés után már kiírja a kívánt 0.5671 értéket.

Források

• Numerikus módszerek, 1st, Kolozsvári Egyetemi Kiadó (2008)