Gyökkeresés iterációval

A gyökkeresés iterációval egy módszer egyenletek megoldására. Az eljárás nem a pontos gyököt adja meg, hanem egy közelítő értéket, ez a közelítő módszerek sajátossága.

Az iteráció során minden lépés bemenő adata az előző lépés kimenete lesz. Amikor ezt gyökkeresésre alkalmazzuk, akkor elsősorban a konvergencia érdekes, azaz az eljárás fokozatosan közelítse az etgyenlet gyökét. Ekkor ugyanis meg tudunk határozni egy határt, aminél pontosabb értéket már elfogadunk megoldásnak.

Minden ilyen eljárás során érdekes a kezdő lépés, ettől ugyanis nagy mértékben függ a konvergencia gyorsasága, egyáltalán a léte. Ez egy külön problémakör a numerikus matematikai módszerek témájában.

Jelen eljárás egy lieáris közelítése a gyököknek, azaz a bemenő adat és ez egyenlet helyettesítési értékének lineáris kombinációja lesz a kimenő (elvileg pontosabb) adat, amit a következő lépésben bemenő adatnak felhasználunk.

Matematikai bevezetés

Konvergencia és divergencia az iteráció során

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_{\left(n+1\right)}=g(x_{n})$, $g(x)=x-Q*f(x)$

Itt Q egy állandó paraméter, amely a konvergenciát biztosítja. A jobbra látható ábrán 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_{\left(n+1\right)}$	$|x_{\left(n+1\right)}-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.07072889·10-05
5	0.567142610	0.567143250	0.567143250	6.39353343·10-07
6	0.567143250	0.567143288	0.567143288	3.81782835·10-08
7	0.567143288	0.567143290	0.567143290	2.27977877·10-09

Láthatóan nagyon gyorsan konvergá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_{\left(n+1\right)}$	$|x_{\left(n+1\right)}-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)