Newton–Raphson-módszer: definíció, elv és lépések gyökkereséshez
Newton–Raphson-módszer — egyszerű definíció, elv és gyakorlati lépések a gyors, iteratív gyökkereséshez (képlet, érintőelv, példák).
A Newton-módszer egy függvény valós nullpontjainak megtalálására ad módot. Ezt az algoritmust néha Newton-Raphson-módszernek is nevezik, Sir Isaac Newton és Joseph Raphson után elnevezve.
A módszer a függvény deriváltját használja a gyökerek megtalálásához. A nullpont helyére vonatkozóan egy kezdeti "becsült értéket" kell megadni. Ebből az értékből egy új becsült értéket számolunk ki ezzel a képlettel:
x n + 1 = x n - f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}} 
Itt xn a kezdeti tipp, xn+1 pedig a következő tipp. Az f függvénynek (amelynek nullpontját megoldjuk) f' deriváltja van.
Ha ezt a képletet ismételten alkalmazzuk a generált találgatásokra (azaz az xn értékét a képlet kimenetére állítjuk és újraszámoljuk), a találgatások értéke a függvény nullájához fog közelíteni.
Alapfeltételek és konvergencia
A Newton-módszer jól működik, ha az alábbi feltételek teljesülnek:
- f folytonosan differenciálható az érdeklődés tartományában (általában legalább egyszer),
- a gyök egyszeres (azaz f(r) = 0, de f'(r) ≠ 0),
- a kezdőbecslés x0 elég közel van a valódi gyökhöz.
Ha ezek teljesülnek és a kezdőérték megfelelően közel van, a Newton-módszer kvadratikus konvergenciát mutat a egyszeres gyökök körül: a hiba nagysága közelítőleg négyzetére csökken iterációnként. Többszörös gyök esetén a konvergencia általában lassabb (lineáris vagy egyéb). A módszer viszont lokálisan konvergens — nem garantált a globális konvergencia rosszul megválasztott kezdőértéknél.
Lépések (algoritmus lépésről lépésre)
- Válassz egy kezdőértéket x0 (becslés a gyökre).
- Számítsd ki f(xn) és f'(xn).
- Ha f'(xn)=0 vagy nagyon kicsi, más módszer vagy módosítás szükséges (lásd tovább).
- Frissítsd xn+1 = xn − f(xn)/f'(xn).
- Ellenőrizd a megszakítási feltételeket: például |f(xn+1)| < tol, |xn+1 − xn| < tol vagy elértük a maximális iterációszámot.
- Ha a feltétel nincs teljesülve, állítsd xn := xn+1 és ismételd.
Példa
Vegyük f(x) = x² − 2 (gyök: √2 ≈ 1,41421356). Kezdőérték legyen x0 = 1.
- x1 = 1 − (1² − 2)/(2·1) = 1.5
- x2 = 1.5 − (1.5² − 2)/(2·1.5) = 1.4166666667
- x3 ≈ 1.4142156863 — rövid iteráció után nagyon közel kerülünk a valódi gyökhöz.
Ez a példa szemlélteti a módszer gyors (kvadratikus) konvergenciáját egyszeres gyök esetén.
Gyakori problémák és megoldások
- Derivált zérus vagy kicsi értéke: ha f'(xn)=0, a képlet nem használható. Ilyenkor érdemes másik kezdőértéket választani, vagy használni módosított Newton-módszert (pl. csillapított lépések) vagy szekáns módszert.
- Eltávolodás vagy oszcilláció: rossz kezdőértékeknél az iteráció eltávolodhat a gyöktől vagy oszcillálhat. Megoldás: hibakeresés vizualizációval, több kezdőpont próbája, vagy hibrid módszer (bisection + Newton) alkalmazása.
- Többszörös gyökök: ha a gyök többszörös (f'(r)=0), a konvergencia lassabb lehet. Ilyenkor speciális formulák vagy gyökdefláció alkalmazása segíthet.
- Komplex gyökök: ha valós kezdőértékről indulsz, lehet, hogy a módszer komplex sík felé tereli az iterációt — ilyenkor komplex kezdőértékekre is szükség lehet.
Módosítások és alternatívák
- Csillapított (damped) Newton: xn+1 = xn − λ·f(xn)/f'(xn) ahol 0<λ≤1 választásával elkerülhetők nagy ugrások.
- Szekáns módszer: ha f' nehezen számítható, a szekáns módszer numerikus derivált helyett két korábbi xi-t használ.
- Hibrid módszerek: például bisection + Newton: a bisection garantálja a globális konvergenciát, a Newton pedig gyors helyi konvergenciát.
Megjegyzések
A Newton-módszer egy iteratív, gyorsan konvergáló eljárás egyszeres gyökök megtalálására, de feltételezi a derivált ismeretét és nem garantálja a globális konvergenciát. Széles körben használják gyökkeresésre és optimalizációs feladatokban is (például másodrendű Taylor-közelítések alkalmazásával). Fontos a megfelelő kezdőérték kiválasztása és a megszakítási feltételek megadása a numerikus megvalósításokban.
A függvényt (kék) az xn pontban lévő érintővonal (piros) meredekségének kiszámítására használjuk.
Problémák a Newton-módszerrel
A Newton-módszer gyorsan talál megoldást, ha a becsült érték elég közel kezdődik a kívánt gyökhöz. Ha azonban a kezdeti becsült érték nem közel van, és a függvénytől függően a Newton-módszer lassan vagy egyáltalán nem találja meg a választ.
További olvasmányok
- Fernández, J. A. E., & Verón, M. Á. H. (2017). Newton-módszer: Kantorovics elméletének aktualizált megközelítése. Birkhäuser.
- Peter Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms, Második nyomtatott kiadás. Series Computational Mathematics 35, Springer (2006)
- Yamamoto, T. (2001). "Történelmi fejlemények a Newton- és Newton-szerű módszerek konvergenciaelemzésében". In Brezinski, C.; Wuytack, L. (szerk.). Numerical Analysis : Historical Developments in the 20th Century. North-Holland. pp. 241-263.
Lásd még
- Kantorovics-tétel (Leonyid Kantorovics által talált állítás a Newton-módszer konvergenciájáról)
| Hatósági ellenőrzés |
|
Kérdések és válaszok
K: Mi az a Newton-módszer?
V: A Newton-módszer egy algoritmus egy függvény valós nullpontjainak megtalálására. A függvény deriváltját használja a gyökök kiszámításához, és egy kezdeti becsült értéket igényel a nulla helyére vonatkozóan.
K: Ki fejlesztette ki ezt a módszert?
V: A módszert Sir Isaac Newton és Joseph Raphson fejlesztette ki, ezért néha Newton-Raphson-módszernek is nevezik.
K: Hogyan működik ez az algoritmus?
V: Ez az algoritmus egy olyan képlet ismételt alkalmazásával működik, amely egy kezdeti becsült értéket (xn) vesz fel, és egy új becsült értéket (xn+1) számol ki. Ezt a folyamatot megismételve a kitalált értékek a függvény nulla értékéhez közelítenek.
K: Mi szükséges ennek az algoritmusnak a használatához?
V: Ennek az algoritmusnak a használatához rendelkeznie kell egy kezdeti "tippértékkel" a nulla helyére vonatkozóan, valamint az adott függvény deriváltjának ismeretével.
K: Hogyan lehet grafikusan elmagyarázni a Newton-módszert?
V: A Newton-módszert grafikusan úgy tudjuk elmagyarázni, hogy megnézzük az érintővonalak és az x-tengely metszéspontjait. Először kiszámítjuk az f-hez xn pontban érintő egyenest. Ezután megkeressük ennek az érintővonalnak a metszéspontját az x-tengellyel, és feljegyezzük annak x-pozícióját, mint a következő tippünket - xn+1.
K: Van-e valamilyen korlátozás a Newton-módszer használatakor?
V: Igen, ha a kezdeti becsült érték túl messze van a tényleges gyökértől, akkor hosszabb időbe telhet, vagy akár nem is konvergálhat a gyökér felé a gyökér körüli oszcilláció vagy a gyökértől való eltérés miatt.
Keres