Felező módszer

A felező módszer (vagy az intervallumfelezés módszere) 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 a₀ illetve b₀-val. A felező módszer abban áll, hogy kiindulva ebből a két értékből újabb (a₁, b₁), (a₂, b₂), ..., (a_n, b_n), ... számpárokat kapunk úgy, hogy a gyök mindvégig a két érték által meghatározott intervallumon belül marad: azaz a_n < ξ < b_n - 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 b_n - a_n = (b_n-1 - a_n-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 c_n = (a_n + b_n)/2 az intervallum közepe.
1. ha f(a_n)f (c_n) < 0 akkor b_n+1 = c_n, 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(a_n)f (c_n) > 0 akkor a_n+1 = c_n, 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(a_n)f (c_n) = 0 leállunk, mert c_n = ξ, 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 c_n. A hiba felső korlátja így
ε_n = (b_n - a_n)/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

Legyen f(x) = x-e^x, 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

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

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ások

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