Gyökkereső algoritmus
 |
Ezt a szócikket be kellene dolgozni a Közelítő módszerek szócikkbe. A bedolgozás után ezt a cikket törölni kell, vagy – amennyiben a szócikk címe előfordulhat a keresésben – átirányítássá alakítani. A megbeszélésbe a vitalapon kapcsolódhatsz be. |
 |
Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. |
 |
Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye. |
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
[szerkesztés]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
[szerkesztés]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]
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]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
[szerkesztés]Newton-módszer (és hasonló derivált alapú módszerek)
[szerkesztés]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.
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]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.
Inverz interpoláció
[szerkesztés]Polinomok gyökeinek a keresése
[szerkesztés]Kiemelt figyelem illeti azt az esetet amikor a függvény polinomfüggvény és ezek gyökei keresendők.
Algoritmusok
[szerkesztés]- Felező módszer
- Érintő módszer (más néven Newton-módszer)
- Szelőmódszer
- Gyökkeresés iterációval
