Felező módszer

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

A felező módszer folytonos, a valós számokat a valós számokra képező függvények gyökeinek meghatározására használatos numerikus módszer. A módszer felhasználhatóságának feltétele, hogy a kérdéses függvény felvegyen mind negatív, mind pozitív értéket.

Az általánosság megsértése nélkül feltételezhetjük hogy az előzőekben, a gyökök szétválasztása során sikerült olyan intervallumokra felosztanunk a számtengelyt, amelyek mindegyikében egyszer és csakis egyszer metszi az f(x) függvény az x tengelyt. Vegyünk egy ilyen intervallumot, és jelöljük annak két végpontját a0 illetve b0-val. A felező módszer abban áll, hogy kiindulva ebből a két értékből újabb (a1, b1), (a2, b2), ..., (an, bn), ... számpárokat kapunk úgy, hogy a gyök mindvégig a két érték által meghatározott intervallumon belül marad: azaz an < ξ < bn - ezáltal tetszőleges pontossággal "sarokba szorítván" a gyököt. Minden egyes lépésben felezzük az intervallum nagyságát: azaz bn - an = (bn-1 - an-1)/2. Szigorúan bizonyítható, hogy a közrezárási feltételt tiszteletben tartva és az intervallumot tetszőlegesen lecsökkentve, annak végpontjai tetszőlegesen közel kerülnek a ξ gyökhöz. Gyakorlatilag az eljárás a következő:
Legyen cn = (an + bn)/2 az intervallum közepe.
1. ha f(an)f (cn) < 0 akkor bn+1 = cn, azaz a jobb oldali végpontot az intervallum közepére mozgatjuk, mert ezzel nem csúszik ki kezünk közül a gyök;
2. ha f(an)f (cn) > 0 akkor an+1 = cn, azaz ha a jobb oldali végpont középre való mozgatásával a közrezárási feltétel nem teljesül, a bal oldali végponttal végezzük el a műveletet;
3. ha f(an)f (cn) = 0 leállunk, mert cn = ξ, azaz belebotlottunk a gyökbe. A harmadik lépésben figyelembe vett eshetőség valószínűsége gyakorlati alkalmazások esetén kicsi, de ettől függetlenül helyet kell kapnia az algoritmusban. Az n-edik lépésben a legjobb becslés cn. A hiba felső korlátja így
εn = (bn - an)/2

Gyökkeresés felező módszerrel

A fenti leírásnak pszeudokódban való megfelelője:
1: function Felező( in: f, a, b, E out: x ) *** f a tanulmányozott függvény, a, b az intervallum határai, E a megoldás megengedett hibája, x becsült megoldás
2: pre b > a, sign(f(a)) ≠ sign(f(b))
3: u → f(a)
4: ε → (b - a)/2
5: while ε > E do
6: c → a + ε
7: w → f(c)
8: if u · w < 0 then
9: b → c
10: else if w = 0 then
11: return c
12: else
13: a → c
14: u → w
15: end if
16: ε → ε/2
17: end while
18: return a + ε
19: end function

Példa[szerkesztés]

Legyen f(x) = x-ex, a = 0, b = 1.0 és a megengedett legnagyobb hiba 0.001. Használva a c = (a + b)/2 jelölést

a b c b - a|/2 f(a) f(b) f(c)
1 0.000000 1.000000 0.500000 0.500000 -1.000000 0.632121 -0.106531
2 0.500000 1.000000 0.750000 0.250000 -0.106531 0.632121 0.277633
3 0.500000 0.750000 0.625000 0.125000 -0.106531 0.277633 0.089739
4 0.500000 0.625000 0.562500 0.062500 -0.106531 0.089739 -0.007283
5 0.562500 0.625000 0.593750 0.031250 -0.007283 0.089739 0.041498
6 0.562500 0.593750 0.578125 0.015625 -0.007283 0.041498 0.017176
7 0.562500 0.578125 0.570312 0.007812 -0.007283 0.017176 0.004964
8 0.562500 0.570312 0.566406 0.003906 -0.007283 0.004964 -0.001155
9 0.566406 0.570312 0.568359 0.001953 -0.001155 0.004964 0.001905
10 0.566406 0.568359 0:567383 0:000977 -0.001155 0.001905 0.000375


A pontos érték öt helyes számjeggyel megadva 0.56714.
Az alábbi robusztusabb változatban a kilépési feltételt kiegészítjük, hogy kis |f(x)| értékekre, illetve nagy iterációszám esetén is térjen vissza az algoritmus:
1: function Robusztus-Felező( in: f, a, b, E,D,M out: x ) ***f a tanulmányozott függvény, a, b az intervallum határai, E a megoldás megengedett hibája, D az f(x) behelyettesítési értékben megengedett hiba, M az iterációk maximális száma, x a becsült megoldás
2: pre b > a, sign(f(a)) ≠ sign(f(b))
3: u → f(a)
4: ε → (b - a)/2 or
5: i → 0
6: w → f(a + ε)
7: while ε > E or |w| > D or i < M do
8: c → a + ε
9: w → f(c)
10: if u · w < 0 then
11: b → c
12: else if w = 0 then
13: return c
14: else
15: a → c
16: u → w
17: end if
18: ε → ε/2
19: i → i + 1
20: end while
21: return a + ε
22: end function

Hiba[szerkesztés]

Vizsgáljuk most meg a konvergencia sebességét. A hiba minden lépésben feleződik, azaz a rekurrencia-képlet
εn+1 = εn/2 ;
ami lineáris konvergenciát jelent.

Előnyei és hátrányai[szerkesztés]

A gyakorlatban szem előtt kell tartanunk a lebegőpontos számok tulajdonságai miatt bekövetkező esetleges hibákat.

1. Az f(a)*f(b) könnyen túlcsordulhat, és 0-t adhat, ha a és b nagyon kicsi számok. Ezt úgy kerülhetjük el, ha őket külön-külön vizsgáljuk, és nem a szorzatukat.
2. Ha epszilon túl kicsi, az (a - b) abszolút értéke lehet, hogy sosem lesz olyan kicsi mint 2*epszilon, így a és b szomszédos, nem egyenlő lebegőpontos számok értékeit veszik fel. Ezt elkerülhetjük úgy, hogy nem engedjük epszilont túl picinek lenni, vagy az algoritmusba épített ellenőrző lépésekkel.

A felező módszer nagy hátránya a Newton-módszerrel (érintő módszer) szemben, hogy több lépés után éri el a megkövetelt pontosságot, így hosszú művelet végzésekor lényegesen lassúbb. Előnyös viszont, mert nem szükséges az adott függvény deriváltjainak az ismerete, vagy egyáltalán a deriváltak létezése.

Forrás[szerkesztés]

Lázár Zsolt, Lázár József, Járai-Szabó Ferenc: Numerikus módszerek