| dbo:abstract
|
- 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 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ás2: pre b > a, sign(f(a)) ≠ sign(f(b))3: u → f(a)4: ε → (b - a)/25: while ε > E do6: c → a + ε7: w → f(c)8: if u · w < 0 then9: b → c10: else if w = 0 then11: return c12: else13: a → c14: u → w15: end if16: ε → ε/217: end while18: return a + ε19: end function (hu)
- 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 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ás2: pre b > a, sign(f(a)) ≠ sign(f(b))3: u → f(a)4: ε → (b - a)/25: while ε > E do6: c → a + ε7: w → f(c)8: if u · w < 0 then9: b → c10: else if w = 0 then11: return c12: else13: a → c14: u → w15: end if16: ε → ε/217: end while18: return a + ε19: end function (hu)
|
