Gyökkereső algoritmus

A Wikipédiából, a szabad enciklopédiából

Gyökkereső algoritmusnak nevezzük azokat a numerikus módszereket, vagy algoritmusokat, amelyeket valamely f függvény x gyökeinek (zérushelyeinek) meghatározására használunk, azaz olyan x-eket keresünk, melyekre teljesül, hogy f(x) = 0.

A feladat itt nem közvetlenül a zérushely, hanem az azt egy adott pontossággal megközelítő eredmény meghatározása. A gyökkereső algoritmusok akkor is használhatók, ha nem létezik megoldóképlet.

Ez a szócikk a valós és a komplex gyökök közelítésével foglalkozik, lebegőpontos számok használatával. Az egész gyökök vagy pontos megoldások megtalálása egy különböző probléma ami nem kapcsolódik a közelítő megoldásokhoz.

Az f(x) - g(x) = 0 egyenlet megoldása ugyanaz mint a f(x) = g(x) egyenlet megoldása. Vagyis bármely egyenlet megoldása visszavezethető egy f(x) = 0 egyenlet megoldására, vagyis egy függvény zérushelyeinek a megtalálására.

A numerikus gyökkereső módszerek iterációt alkalmaznak, vagyis egy sorozatot készítenek ami remélhetőleg konvergens és a határérték a gyök. A sorozat kezdő értéke a kezdeti érték vagy a kiindulópont (initial guess). A numerikus módszerek ezután a további elemeket a megelőzők és a függvény segítségével állítják elő.

A gyökkereső algoritmusokat és viselkedésüket a numerikus analízis tanulmányozza. Azok az algoritmusok nyilvánvalóan jobban teljesítenek amik kihasználják a függvény ismert tulajdonságait. A fontos kérdések egy adott módszerrel kapcsolatban: viselkedés közeli gyökök esetén, számítási/kerekítési hibák hatása, hibatűrés, a konvergencia sebessége.

Zárt módszerek[szerkesztés | forrásszöveg szerkesztése]

A zárt módszerek egy olyan intervallum határait szűkítik minden lépében ami biztosan tartalmaz egy gyököt. Ezek a módszerek alkalmasak a abszolút hibakorlát megadására. A módszerek alkalmazásához szükség van arra, hogy a függvény folytonos legyen. Két kezdeti érték szükséges, lásd lejjebb.

Felező módszer[szerkesztés | forrásszöveg szerkesztése]

A legegyszerűbb gyökkereső algoritmus az intervallumfelezés. A függvény folytonossága szükséges, és két olyan kezdeti pont amelyben a függvény előjelei különbözőek.

Falsz pozíció (regula falsi)[szerkesztés | forrásszöveg szerkesztése]

A falsz pozíció módszer a húrmódszerhez hasonló, azzal a kivétellel, hogy a 2 pont közül 1 mindenképp a gyök egyik oldalán legyen, a másik a másik oldalon.

Interpoláció[szerkesztés | forrásszöveg szerkesztése]

A falsz pozícó egy interpolációs módszer mivel a függvényt egy egyenessel közelíti két pont között. Magasabb fokú polinomok is használhatóak közelítésre, egyenes helyett. Ezek a módszerek gyorsan konvergálnak és abszolút hibakorláttal a legrosszabb esetben is.

Nyílt módszerek[szerkesztés | forrásszöveg szerkesztése]

Newton módszer (és hasonló derivált alapú módszerek)[szerkesztés | forrásszöveg szerkesztése]

A Newton módszerhez szükség van arra, hogy a függvénynek létezzen folytonos deriváltja. A módszer lehet, hogy egyáltalán nem konvergál, ha a kiindulási pont túl messze van a gyöktől. Amikor viszont konvergál akkor gyorsabb az intervallumfelező módszernél, gyakran kvadrikusan konvergál.

Húrmódszer[szerkesztés | forrásszöveg szerkesztése]

Ha lecseréljük a deriváltat a Newton módszerben véges differenciára akkor kapjuk a húrmódszert.

Interpoláció[szerkesztés | forrásszöveg szerkesztése]

Inverz interpoláció[szerkesztés | forrásszöveg szerkesztése]

Polinomok gyökeinek a keresése[szerkesztés | forrásszöveg szerkesztése]

Kiemelt figyelem illeti azt az esetet amikor a függvény polinomfüggvény és ezek gyökei keresendők.

Algoritmusok[szerkesztés | forrásszöveg szerkesztése]