Gyökkereső algoritmus

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, amely nem kapcsolódik a közelítő megoldásokhoz.

Az f(x) - g(x) = 0 egyenlet megoldása ugyanaz, mint az 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, amely 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, amelyek 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

A zárt módszerek egy olyan intervallum határait szűkítik minden lépésben, 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

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)

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ó

A falsz pozíció 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

Newton-módszer (és hasonló derivált alapú módszerek)

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

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

Interpoláció

Az interpoláció matematikai közelítő módszer, amely egy függvény nem ismert értékeire az ismert értékek alapján ad közelítést.

Polinomok gyökeinek a keresése

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

Algoritmusok

• Felező módszer
• Érintő módszer (más néven Newton-módszer)
• Szelőmódszer
• Gyökkeresés iterációval