Newton-módszer

A numerikus analízisben a Newton-módszer (más néven Newton–Raphson-módszer, Newton–Fourier-módszer vagy érintőmódszer) az egyik legjobb módszer, amellyel valós függvények esetén megközelíthetjük a gyököket (zérushelyeket). A Newton-módszer gyakran nagyon gyorsan konvergál, de csak akkor, ha az iteráció a kívánt gyökhöz elég közelről indul. Ez a közelség és a konvergenciasebesség a függvénytől függ. A Newton-módszer minden figyelmeztetés nélkül nagyon könnyen félrevezethet egy tapasztalatlan használót, ha túl távolról próbálkozik indítani a módszert. A legjobb megoldás tehát az, hogy egy másik eljárással vizsgáljuk a konvergenciát, ami felismeri és lehetőleg kiküszöböli a lehetséges konvergenciahibákat.

Nemcsak gyököt tudunk keresni ezen a módon, hanem minimumot vagy maximumot is találhatunk, feltéve, hogy a függvény differenciálható; ugyanis a függvénynek ott lehet szélsőértéke, ahol deriváltjának gyöke van. Az algoritmus az első a Householder-algoritmusok osztályában, de ezeket meghaladja a Halley-módszer.

A módszer leírása

A módszer ötlete a következő: kiindulunk egy pontból, amely az igazi gyökhöz elég közel található. A függvényérték ebben a pontban megközelítőleg az ehhez a ponthoz húzott érintőn található (amelyet meghatározhatunk egyszerű számításokkal), majd kiszámoljuk ennek az érintőnek az x tengellyel való metszéspontját (melyet egyszerűen megtehetünk algebrai ismereteinket felhasználva). Ez az OX tengellyel való metszéspont valószínűleg egy jobb közelítése a függvény gyökének, mint az eredeti pontunk, a módszer iterálható.

Feltételezzük, hogy f : [a, b] → ${\displaystyle \mathbb {R} }$ differenciálható függvény, amely leképezi az [a, b] zárt intervallumot a valós számok ${\displaystyle \mathbb {R} }$ halmazába. Könnyen kifejezhető a képlet, ami szerint a gyök felé konvergálunk. Tegyük fel, hogy ismerjük a x_n közelítést. Tovább módosíthatjuk az összefüggést egy még jobb x_n+1 közelítés irányába, figyelembe véve a bal oldali diagramot. Tudjuk a derivált definíciójából, hogy egy bizonyos pontban a ponthoz húzott érintővel azonos. Vagyis:

${\displaystyle f'(x_{n})={\frac {\mathrm {rise} }{\mathrm {run} }}={\frac {\mathrm {\Delta y} }{\mathrm {\Delta x} }}={\frac {f(x_{n})-0}{x_{n}-x_{n+1}}}={\frac {0-f(x_{n})}{(x_{n+1}-x_{n})}}\,\!}$.

Ahol f ' az f függvény deriváltját jelenti. Innen egy kis algebrai átalakítás után a végső alak:

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\,\!}$.

A folyamatot az x₀ pontból indítjuk (Minél közelebb van a gyökhöz, annál jobb. De mivel nem ismerjük a gyök pozícióját, találgatással és ellenőrzéssel leszűkíthetjük az intervallumot kisebb intervallumokra a felezőpont meghatározásának módszerét felhasználva). A módszer általában konvergál, ha a megadott érték elég közel található az ismeretlen helyzetű gyökhöz, és ${\displaystyle f'(x_{0})\neq 0}$. Továbbá ahhoz, hogy a gyök legalább egyszeres gyök legyen, szükséges, hogy a konvergenciája kvadratikus legyen a gyök szomszédságában, amely azt jelenti, hogy a szám megközelítőleg megduplázódik minden lépésben. Több részlet az analízis részben található.

Algoritmus

Az alábbi kód Python programozási nyelvben van írva, az epszilon paraméter pedig a kívánt pontosságot jelenti. Például ha az ${\displaystyle f(x)=x-e^{x}}$ függvény gyökét keressük:

import math
def Fx(X):
	return X-e**X
def Erinto(Fx, dFx, x0, epszilon):
	x1=x0-Fx(x0)/dFx(x0)
	while abs(x1-x0)>epszilon:
		x0=x1
		x1=x0-Fx(x0)/dFx(x0)
	return x1
print Erinto(Fx, dFx, 0.5, 0.0001)

Példa

Adott a cos(x) = x³ függvény, ahol x pozitív szám. Ebből kiindulva a feladat a következő: keressük az f(x) = cos(x) − x³ függvény gyökét. Annak tudatában, hogy f '(x) = −sin(x) − 3x², és cos(x) ≤ 1, illetve x³ > 1 minden x-re (ha x>1), azt is tudjuk, hogy a gyök valahol 0 és 1 között található. Ezért egy x₀ = 0,5 kezdeti értékkel próbálkozunk:

${\displaystyle {\begin{matrix}x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}&=&0.5-{\frac {\cos(0.5)-0.5^{3}}{-\sin(0.5)-3\times 0.5^{2}}}&=&1.112141637097\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&&\vdots &=&{\underline {0.}}909672693736\\x_{3}&&\vdots &&\vdots &=&{\underline {0.86}}7263818209\\x_{4}&&\vdots &&\vdots &=&{\underline {0.86547}}7135298\\x_{5}&&\vdots &&\vdots &=&{\underline {0.8654740331}}11\\x_{6}&&\vdots &&\vdots &=&{\underline {0.865474033102}}\end{matrix}}}$

A helyes számjegyek alá vannak húzva a fenti példában. Kivételesen x₆ egyezik a legjobban a megadott decimális helyekhez viszonyítva. Láthatjuk a helyes számjegyű számot, miután a tizedesvessző 2-ről (x₃-re), 5-re és 10-re növekszik, illusztrálva a kvadratikus konvergenciát.

Egy szám négyzetgyöke

Egy szám négyzetgyökét számos módon megkereshetjük, a Newton-módszer többek között erre is remekül használható.

Például, ha a 612 négyzetgyökére vagyunk kíváncsiak, akkor az alábbi módon járhatunk el.

${\displaystyle \,x^{2}=612}$

Írjuk fel függvényként a felső kifejezést!

${\displaystyle \,f(x)=x^{2}-612}$

ezt deriválva a következőt kapjuk,

${\displaystyle f'(x)=2x.\,}$

Kezdeti becslésünk a 10, a folytatás Newton-módszerrel megadva,

${\displaystyle {\begin{matrix}x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}&=&10-{\frac {10^{2}-612}{2\cdot 10}}&=&35.6\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&=&35.6-{\frac {35.6^{2}-612}{2\cdot 35.6}}&=&{\underline {2}}6.3955056\\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}906355\\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.7386}}883\\x_{5}&=&\vdots &=&\vdots &=&{\underline {24.7386338}}\end{matrix}}}$

A helyes számjegyek alá vannak húzva. Csupán pár iterációval bárki elnyerheti a megfelelő számú tizedes jegyet.

Történelmi háttér

A Newton-módszert először Isaac Newton írta le a De analysi per aequationes numero terminorum infinitas-ban (amelyet 1669-ben írt és 1711-ben William Jones adott ki) és a De metodis fluxionum et serierum infinitarum-ban (amelyet 1671-ben írt, fordította és kiadta Method of Fluxions címmel John Colson 1763-ban). Ez a leírás nagymértékben különbözik a fentiekben megadott modern leírástól, meghatározástól. Newton csak polinomok esetében használta a módszert. Ő nem számolta ki a ${\displaystyle x_{n}}$- rákövetkező közelítést, hanem kiszámolt egy polinomsorozatot, és majd csak a végen ért el az x gyök közelítéséhez. Végül Newton a módszert kizárólag algebrainak tekintette, és nem vette észre a kapcsolatot a számításokkal. Valószínűleg François Viète egyik nem annyira pontos, de hasonló módszeréből vezette le. Viète módszerének lényege megtalálható a perzsa matematikus Sharaf al-Din al-Tusi (Ypma 1995) munkái közt. Egy speciális esete a Newton-módszernek, amikor négyzetgyököket számolunk, sokkal korábban előfordult, és úgy nevezték, hogy babilóniai módszer.

A Newton-módszer először 1685-ben John Wallis A Treatise of Algebra both Historical and Practical című művében jelent meg, majd 1690-ben Joseph Raphson kiadott egy sokkal egyszerűbb leírást Analysis aequationum universalis címmel. Raphson is algebrai módszerként tekintette a Newton által kidolgozott módszert, és kizárólag polinomokkal dolgozott, de egymás után következő közelítések formájában írta le, nem mint Newton, aki sokkal komplikáltabb polinomsorozatként. Végül 1740-ben Thomas Simpson a Newton-módszert iteratív módszernek tekintette, amely általános nemlineáris egyenletek megoldására szolgál, fluxusféle számítások segítségével, lényegében megadva a fentiekben elhangzott leírást. Ugyanazon publikáción belül Simpson megadta a két egyenletből álló egyenletrendszerek általánosítását, és megjegyezte, hogy a Newton-módszer optimalizációs problémák megoldására is felhasználható úgy, hogy a fokszámot nullára állítjuk. 1879-ben Arthur Cayley először határozta meg a The Newton-Fourier imaginary problem című művében a Newton-módszer általánosításával járó nehézségeket olyan komplex polinomok gyökei esetén, amelyeknek a foka meghaladta a 2-t, és a kezdeti érték is komplex volt. Ez megnyitotta a racionális függvények iterációelmélete felé vezető utat.

Gyakorlati meggondolások

Általában a konvergencia kvadratikus: a hiba négyzetesen csökken minden lépésnél, tehát a helyes jegyek száma megduplázódik minden lépésnél. De van egy pár hátránya. Először, a Newton-módszerhez szükséges direkt kiszámolni a deriváltat. Ha a deriváltat megközelítjük a függvény két pontján áthaladó ferde egyenessel, akkor ebből következik a húrmódszer, mellyel sokkal hatékonyabb eredményekre juthatunk, figyelembe véve a számításokhoz szükséges erőfeszítéseket. Másodszor, ha a gyök túl távol van a kezdeti értéktől, a Newton-módszer nem konvergálhat. Ebből az okból kifolyólag a legtöbb gyakorlati alkalmazásnál meghatározzák az iterációk számának a maximumát, és esetleg az iterációs méretet is. Harmadszor, ha a keresett gyök multiplicitása egynél nagyobb, akkor a konvergencia csupán lineáris (a hiba egy konstanssal csökken minden lépés során), hacsak nem teszünk speciális lépéseket. Mivel a fentiekben említett hibákban a legkomolyabb probléma a konvergencia hiánya, W. H. Press és mások (1992-ben) bemutattak egy olyan verziót, amelyben a folyamat annak az intervallumnak a közepéről indul, amelyben feltételezzük a gyököt, és az iteráció akkor áll le, ha az olyan értéket generál, amely az intervallumon kívül esik. Széles körű számítógéprendszer-fejlesztők a húrmódszert kedvezőbbnek tartják a Newton‑módszerrel szemben, mert elég differenciahányadost használni a deriválttal szemben. Ezt folyamatosan frissíteni kell, ami nem a legelőnyösebb. A gyakorlatban a kisebb kód fenntartása sokkal előnyösebb, mint a másodrendű konvergencia.

Buktatói

Távoli kezdőpont

Ha a kezdeti pont nincs elég közel a gyökhöz, a konvergencia elmaradhat. Vegyük a következő függvényt:

${\displaystyle f(x)=x^{3}-2x+2\!}$

és a 0 kezdeti pontot. Az első iteráció után 1-et kapunk, majd a második visszatér a 0-ba, tehát a folyamat oszcillálni fog a két érték közt anélkül, hogy elérné a gyököt. Általában a folyamat viselkedése igen bonyolult lehet.

Ha a derivált nem folytonos

Ha a derivált nem folytonos a gyöknél, akkor a konvergencia nem fog megnyilvánulni, bármilyen intervallumot is veszünk a gyök számára.

Tekintsük a következő függvényt:

${\displaystyle f(x)={\begin{cases}0&{\mbox{ha }}x=0\\x+x^{2}\sin({\frac {2}{x}})&{\mbox{ha }}x\neq 0\end{cases}}}$

${\displaystyle f'(0)=1\!}$ és ${\displaystyle f'(x)=1+2x\sin(2/x)-2\cos(2/x)\!}$

Bármely intervallumot is veszünk a gyök számára, ez a derivált változtatni fogja az előjelét, mihelyt x megközelíti a 0-t jobbról, illetve balról, míg ${\displaystyle f(x)\geq x-x^{2}>0\!}$ ,ha ${\displaystyle 0<x<1\!}$.

Tehát ${\displaystyle f(x)/f'(x)\!}$ végtelen a gyök közelében, mely azt eredményezi, hogy a Newton-módszer nem fog konvergálni, akkor se, ha a függvény mindenhol deriválható; a derivált nem zéró a gyökben; ${\displaystyle f\!}$ végtelenszer differenciálható, kivéve a gyökben; és a derivált végtelen a gyök közelében.

Második derivált hiánya

Ha nem létezik a gyöknél a második derivált, akkor a konvergencia lehet, hogy nem lesz kvadratikus. Vegyük a:

${\displaystyle f(x)=x+x^{4/3}\!}$ függvényt,

és a függvény deriváltja:

${\displaystyle f'(x)=1+(4/3)x^{1/3}\!}$

és a második deriváltja:

${\displaystyle f''(x)=(4/9)x^{-2/3}\!}$

kivéve mikor ${\displaystyle x=0\!}$ ahol végtelen. Tudván ${\displaystyle x_{n}\!}$,

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {(1/3)x_{n}^{4/3}}{(1+(4/3)x_{n}^{1/3})}}\!}$

amely megközelítőleg 4/3, másodszor több pontossági bitje van, mint ${\displaystyle x_{n}\!}$-nek. Ez 2-szer több, mint amennyi szükséges lenne egy kvadratikus konvergenciához. Tehát ebben az esetben a Newton-módszer konvergenciája nem kvadratikus, habár a függvény mindenhol folytonosan differenciálható; a derivált nem nulla a gyökben; és ${\displaystyle f\!}$ határozatlanul differenciálható, kivéve a gyökben.

A derivált nulla

Ha a függvény deriváltja nulla a gyökben, akkor a konvergencia nem lesz kvadratikus. Vegyük a következőt:

${\displaystyle f(x)=x^{2}\!}$

akkor ${\displaystyle f'(x)=2x\!}$ és képletben ${\displaystyle x-f(x)/f'(x)=x/2\!}$. Tehát a konvergencia nem kvadratikus, habár a függvény végtelenszer differenciálható mindenütt.

Az iterációs pont állandó

Tekintsük az alábbi függvényt

${\displaystyle f(x)=1-x^{2}\!}$

A függvénynek maximuma van x=0 ban és megoldása f(x) = 0 ban x = ±1. Ha az állandó pontból indítjuk az iterációt, akkor x₀=0 (ahol a derivált nulla), x₁ nem meghatározható.

${\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}=0-{\frac {1}{0}}}$

A végeredmény hasonló lesz, ha a kezdőpont helyett bármely pont állandó. Még akkor is, ha a derivált nagyon kicsi, de nem nulla, a következő iteráció sokkal messzebb lesz a kívánt nullától.

Analízis

Tegyük fel, hogy az f függvénynek van egy gyöke ${\displaystyle \alpha }$-ban, f(${\displaystyle \alpha }$) = 0.

Ha f  folytonosan differenciálható, és ha a deriváltja nem tűnik el ${\displaystyle \alpha }$-ban, akkor létezik egy olyan környezete az ${\displaystyle \alpha }$ körül, amelyből egy x₀ kezdő pontot választva az {x_n}sorozat konvergálni fog ${\displaystyle \alpha }$ -hoz.

Ha f  folytonosan differenciálható, ha a deriváltja nem tűnik el ${\displaystyle \alpha }$-ban, és ha létezik a másodrendű deriváltja ${\displaystyle \alpha }$-ban, akkor a konvergencia kvadratikus, vagy gyorsabb. Ha második deriváltja ${\displaystyle \alpha }$-ban nem tűnik el, akkor a konvergencia csak kvadratikus.

Ha a derivált nem tűnik el ${\displaystyle \alpha }$ -ban, akkor a konvergencia általában lineáris. Különösen, ha f kétszer folytonosan differenciálható, ${\displaystyle f'(\alpha )=0\!}$ és ${\displaystyle f''(\alpha )\neq 0\!}$, akkor létezik egy olyan környezet az ${\displaystyle \alpha }$ körül, amelyből bármely x₀ kezdeti értéket véve a sorozat lineárisan fog konvergálni, log₁₀ 2 arányossággal. Vagy, ha ${\displaystyle f'(\alpha )=0\!}$ ha ${\displaystyle f'(x)\neq 0\!}$ adottak, ${\displaystyle \alpha }$ egy U környezetéből, ha r ${\displaystyle \alpha }$ multiplicitása és ha ${\displaystyle f\in C^{r}(U)}$, akkor létezik egy olyan környezete ${\displaystyle \alpha }$-nak , hogy bármely x₀ kezdő értéket véve ebből a környezetből, akkor az iteráció lineárisan fog konvergálni.

Azonban még a lineáris konvergencia sem garantált kóros szituációkban.

Gyakorlatban ezek az eredmények lokálisak, és nem ismerjük előzetesen a konvergencia környezetét, de vannak némi eredmények globális konvergencia esetén is. Például, ha adott ${\displaystyle \alpha }$ megfelelő U₊ környezete, ha f kétszeresen differenciálható U₊ és ha ${\displaystyle f'\neq 0\!}$, ${\displaystyle f\cdot f''>0\!}$ U₊-ban, akkor mindegyik x₀ U₊-ból a x_k sorozat monoton csökken az ${\displaystyle \alpha }$ felé .

Általánosítás

Nemlineáris egyenletrendszerek

Ha valaki a Newton-módszert k nemlineáris egyenlet megoldására akarná használni, amely abból áll, hogy megtaláljuk az ${\displaystyle F:\mathbb {R} ^{k}\to \mathbb {R} ^{k}}$ folytonosan differenciálható függvény gyökeit. Ekkor a fenti képletben balról kell megszorozni k inverzét a J_F Jacobi-mátrixszal (x_n), f '(x_n) -nel osztás helyett. Sok időt lehet megspórolni, ha megoldjuk a lineáris egyenletrendszert, a mátrix invertálása helyett:

${\displaystyle J_{F}(x_{n})(x_{n+1}-x_{n})=-F(x_{n})\,\!}$

az ismeretlen x_n+1 – x_n-re. Összefoglalva ez a módszer akkor működik, ha az x₀ kezdeti értek elég közel van a keresett gyökhöz. Általában egy más módszerrel határozzák meg azt a régiót, amelyben a gyök található, majd a Newton-módszert használják a közelítés „csiszolására”.

Nemlineáris egyenletek a Banach-térben

A Newton-módszer egy másik általánosítása az, hogy kapjunk meg a Banach-térben definiált F függvény egy gyökét. Ebben az esetben a képlet:

${\displaystyle X_{n+1}=X_{n}-(F'_{X_{n}})^{-1}[F(X_{n})]}$,

ahol ${\displaystyle F'_{X_{n}}}$ a Fréchet-derivált ${\displaystyle X_{n}}$-re alkalmazva. A módszer alkalmazásához szükséges, hogy a Fréchet-derivált invertálható legyen minden ${\displaystyle X_{n}}$ pontban.

Komplex függvények

Amikor komplex függvényekkel dolgozunk, a Newton-módszer közvetlenül alkalmazható a gyökök keresésére. Sok komplex függvény esetében egy fraktál határolja a kezdő értékeket, amelyek kiváltják a konvergálást a gyök felé.

Források

• Tjalling J. Ypma, Historical development of the Newton-Raphson method, SIAM Review 37 (4), 531–551, 1995. doi:10.1137/1037125.
• P. Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer Series in Computational Mathematics, Vol. 35. Springer, Berlin, 2004. ISBN 3-540-21099-7.
• C. T. Kelley, Solving Nonlinear Equations with Newton's Method, no 1 in Fundamentals of Algorithms, SIAM, 2003. ISBN 0-89871-546-6.
• J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables. Classics in Applied Mathematics, SIAM, 2000. ISBN 0-89871-461-3.
• W. H. Press, B. P. Flannery, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, 1992. ISBN 0-521-43108-5 (available free online, with code samples: [1] Archiválva 2016. március 3-i dátummal a Wayback Machine-ben), sections 9.4 [2] Archiválva 2012. március 4-i dátummal a Wayback Machine-ben and 9.6 [3] Archiválva 2012. március 4-i dátummal a Wayback Machine-ben.
• W. H. Press, B. P. Flannery, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes: The Art of Scientific Computing, Cambridge University Press, 2007. ISBN 0-521-88068-8 (available for a fee online, with code samples [4]).
• W. H. Press, B. P. Flannery, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes in Fortran, Cambridge University Press, 1992. ISBN 0-521-43064-X (online, with code samples: [5])
• Endre Süli and David Mayers, An Introduction to Numerical Analysis, Cambridge University Press, 2003. ISBN 0-521-00794-1.

További információk

• Newton-módszer^{[halott link]} PDF
• A Newton-módszer a Wolfram.com-on (angolul)
• Animations for Newton's method
• Newton's method on the Mathcad Application Server (with animation)
• Newton-Raphson Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica at Holistic Numerical Methods Institute
• Module for Newton’s Method by John H. Mathews
• worked example