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

666px|bélyegkép|Gyökkeresés felező módszerrel

A fenti leírásnak pszeudokódban való megfelelője: <tt>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</tt>

Példa 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 abcb - a|/2f(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.00190510 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

Kategória:Numerikus analízis