Cím: Húrmódszer, szelőmódszer, Newton-módszer, iterációs módszerek

Felhasznált irodalom: Dringó László Numerikus Analízis I.

A numerikus problémamegoldás néhány elve nemlineáris egyenletek megoldásához:

I. Az iteráció elve

Az iteráció vagy más néven fokozatos közelítések elve lényegében egy számítási eljárás véges sokszori ismét­lését jelenti. Elsősorban egyenletek, egyenletrendszerek, differenciálegyenletek megoldására használjuk, ahol az adott számítási eljárás egyszeri alkalmazásával az egyenlet gyökéhez konvergáló valamely sorozat egy ele­mét határozzuk meg. Most lássuk ezt a gyakorlatban!

Feladat: Határozzuk meg az F(x)=0 nemlineáris egyenlet valós gyökét!

Első lépésként alakítsuk át egy vele ekvivalens egyenletté:

Az így nyert, az eredetivel ekvivalens egyenlet valós gyökét fogjuk meghatározni.

Válasszunk egy x0 alkalmasan megválasztott kezdőértéket és képezzük a következő sorozatot:

Ha az xn sorozat konvergál egy x* határértékhez, és f(x) folytonos, akkor

vagyis x* gyöke az egyenletnek és így az eredeti F(x)=0 egyenletnek is.

Geometriailag:

Megjegyzés: Az (xn+1) sorozat sajnos nem minden esetben konvergál az x* megoldáshoz (2. ábra), ezért fontos a megfelelő kezdőérték megválasztása, ebben – ha más előismerettel nem rendelkezünk a függvényünkről – segítségünkre lehet az y=x és az y=f(x) függvények grafikus ábrázolása.

Algoritmus: Az algoritmus elkészítésekor két dologra kell ügyelnünk, egyrészt arra, hogy nem érdemes in­dexelni, mert ez fölöslegesen növeli a tárigényt, hi­szen nekünk csak az utolsó, x* értékre van szükségünk, másrészt hogy beépítsünk valamiféle lépésszámlálót, és maximális lépésszámot, hátha nem konvergál az iterációnk.

II. A linearizálás elve

A numerikus algoritmusok megkonstruálásának egy igen gyakran használt elve, hogy a modellben szereplő függvényt valamely eléggé kis intervallumban egy egyszerűbb, pél­dául lineáris függvénnyel helyettesítjük. Ezt az elvet az iteráció elvével kombinálva kapjuk a következő három egyenletmegoldó módszert.

Feladat: Most (is) az f(x)=0 nemlineáris egyenlet (egy) valós gyökét kell meghatározni.

a) szelőmódszer

Tegyük fel, hogy f(x) folytonos az [x1, x2] intervallumban és f(x1)f(x2)<0. Ebből kö­vetkezik (Bolzano), hogy f(x)-nek van gyöke az intervallumban. Tegyük fel továbbá, hogy csak egy gyöke van itt. (Ehhez csak az kell, hogy f(x) szigorúan monoton is le­gyen az intervallumban.)

Az (x1, f(x1)) és az (x2, f(x2)) pontokat összekötő húr messe az x tengelyt az x3 pontban. Számítsuk ki f(x3) értékét. Ha ez 0, akkor megkaptuk az egyenlet gyökét, különben folytassuk az eljárást, azaz x4 legyen az

(x2, f(x2)) és az (x3, f(x3)) pontokat össze­kötő húr és az x tengely metszéspontja és így tovább. Így jobb eset­ben előbb-utóbb megkapjuk az egyenlet gyökét, vagy egy ehhez konvergáló végtelen sorozatot. De itt is kap­hatunk divergens sorozatot.

Geometriailag:

b) húrmódszer

A módszer lényege ugyanaz, mint a szelőmódszernél, csak most az x1, x2 pontok közül azt tartsuk meg, amelyre f(x3)*f(xi) < 0 (i=1,2), azaz amelyikkel nem egyezik az elő­jele x3-nak. Ezt folytatva biztosan meg­kapjuk az egyenlet gyökét, vagy egy ehhez kon­vergáló sorozatot. (Tehát ez a módszer biztosabb, csak körül­ményesebb.)

Matematikailag: Felhasználva koordinátageometriai ismereteinket, és az

y-y1=m(x-x1)

képletbe helyettesítve kapjuk a következőt (y=0):

ezt átrendezve nyerjük az iteráció következő tagját:

.

c) Newton-módszer

Válasszunk valamilyen x0 kezdőértéket és helyettesítsük az f(x) függvényt az (x0,f(x0)) pontján áthaladó érintővel (linearizálás), és legyen az érintő x tengellyel vett metszéspontja x1. Ezután helyettesítsük az f(x) függvényt az (x1,f(x1)) pontján átha­ladó érintővel, és legyen ennek az x tengellyel vett metszéspontja az x2, és így tovább (iteráció).

Tétel: Legyen f folytonos és kétszer differenciálható az [a,b] intervallumon, valamint x0 eleme az intervallum­nak. Ha ekkor bármely intervallumbeli x-re teljesülnek a követke­zők:

1) f(a)f(b)<0

2) f’(x)0

3) f”(x)0

4) f(x0)f”( x0)>0

akkor az x0 pontból indított Newton-iteráció konvergens.

Geometriailag:

Matematikailag: Az iteráció következő tagját az előző módszernél látottakhoz hasonlóan kaphatjuk (csak a meredekség most f’(xn)), így az

y-y1=m(x-x1)

képletbe helyettesítve kapjuk a következőt:

ezt átrendezve nyerjük az iteráció következő tagját:

.

Megjegyzés: A Newton-módszerből visszakaphatjuk a húrmódszert, ha az f(x) függvény deriváltját a diffe­renciahányadossal közelítjük.

15. tétel: Nemlineáris egyenletek megoldása

4

NUMERIKUS ANALÍZIS

Frena András

2002-06-29T23:47:00

Peter Szamoskozi