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. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont!
Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

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

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)

Ez a szakasz egyelőre üres vagy erősen hiányos. Segíts te is a kibővítésében!

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ó

Ez a szakasz egyelőre üres vagy erősen hiányos. Segíts te is a kibővítésében!

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)

Ez a szakasz egyelőre üres vagy erősen hiányos. Segíts te is a kibővítésében!

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.