Newton-módszer

Ezt a lapot át kellene olvasni, ellenőrizni a szavak helyesírását és a szöveg nyelvhelyességét.

0

A numerikus analízisben a Newton - módszer(más néven a Newton - Raphson módszer vagy a Newton - Fourier módszer) az egyik legjobb ismert módszer, amivel valós függvények esetén jól közelíthetjük a gyököket. 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, ahogy a következőkben le van írva. 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 konvergencia hibá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. Erről részletesen is szó lesz a Newton - módszer , mint egy optimalizáló algoritmus részben. Az algoritmus az első a Housholder algoritmusok osztályában, de ezeket meghaladja a Halley módszer.

[szerkesztés] 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ó.

A Newton - módszer illusztrációja. Az f függvény grafikonja kékkkel és az érintője pirossal). Látjuk, hogy x_{n + 1} jobb közelítése az f függvény x gyökének, mint x_n .

Feltételezzük , hogy f : [a, b] → R deriválható függvény, amely leképezi az [a, b] intervallumot a valós számok halmazába R-be. Könnyen kifejezhető a képlet, ami szerint a gyök felé konvergálunk. Tegyük fe , 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:

.

Itt f ' az f függvény deriváltját jelenti. Innen azonnal következik egy kis algebrai ismeret birtokában :

.

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 . 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ó.

[szerkesztés] Példa

Gondoljunk arra a feladatra, ahol x pozitív szám, és cos(x) = x³ a függvény. Átfogalmazhatjuk ezt a feladatot: keressük a f(x) = cos(x) − x³ függvény gyökét. Tudjuk, hogy f '(x) = −sin(x) − 3x², mert cos(x) ≤ 1 minden x-re és x³ > 1 , ha x>1. Tudjuk , hogy a gyökünk a 0 és 1 között található. Egy x₀ = 0.5 kezdeti értékkel próbálkozunk.

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.

[szerkesztés] 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 (amelyet 1669-ben írt és kiadta 1711-ben William Jones) és a De metodis fluxionum et serierum infinitarum-ban (amelyet 1671-ben írt, fordította és kiadta Method of Fluxionsnéven John Colson1763-ban). Ez a leírás nagy mé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 x_n- rákövetkező közelítést, hanem kiszámolt egy sorozat polinomot é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 Newton a módszert 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őfordul é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 Practicalnevű művében jelent meg . 1690-ban, Joseph Raphson kiadott egy sokkal egyszerűbb leírást Analysis aequationum universalisnéven. Raphson is algebrai módszerként tekintette a Newton által kidolgozott módszert, és kizárólag polinomokkal dolgozott, de mivel a módszert 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ódszerként tekinti, 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ó egyenletek általánosítását és megjegyzi ,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 komplex polinomok gyökei esté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.

[szerkesztés] 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. Press et al.(1992)-ben bemutatott 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 iteráció során olyan értéket generál, amely az intervallumon kívül esik. Széleskörű számítógéprendszer-fejlesztők a húrmódszert kedvezőbbnek tartják a Newton - módszerrel szemben, mert elég differenciálhá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.

[szerkesztés] Ellenpéldák

Az a x^3 - 2x + 2 függvény érintőegyenesei a 0 és 1 pontokban, amelyek az x tengelyt 1 illetve 0 pontokban metszik, illetve illusztrálja , hogy miért is oszcillál a Newton - módszer ezek a értékek közt bizonyos kezdeti értékek esetén.

[szerkesztés] 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:

é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.

[szerkesztés] 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:

Majd

és máshelyt.

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, mig for .

Tehát 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; végtelenszer differenciálható, kivéve a gyökben; és a derivált végtelen a gyök közelében.

[szerkesztés] 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:

függvényt,

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

és a második deriváltja:

kivéve mikor ahol végtelen. Tudván ,

amely megközelítőleg 4/3, másodszor több pontossági bitje van, mint -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 határozatlanul differenciálható, kivéve a gyökben.

[szerkesztés] 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:

akkor és képletben . Tehát a konvergencia nem kvadratikus, habár a függvény végtelenszer differenciálható mindenütt.

[szerkesztés] Analízis

Tegyük fel, hogy az f függvénynek van egy gyöke α-ban, f(α) = 0.

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

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

Ha a derivált nem tűnik el α -ban, akkor a konvergencia általában lineáris. Különösen, ha f kétszer folytonosan differenciálható, és , akkor létezik egy olyan környezet az α 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 ha adottak, α egy U környezetéből, ha r α multiplicitása és ha , akkor létezik egy olyan környezete α-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 α megfelelő U₊környezete, haf kétszeresen differenciálható U₊ és ha , U₊-ban, akkor mindegyik x₀ U₊-ból a x_k sorozat monoton csökken az α felé .

[szerkesztés] Általánosítás

[szerkeszté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 F : R^k → R^k folytonosan differenciálható függvény gyökeit. Ekkor a fenti képletben balról kell megszorozni kinverzé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:

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".

[szerkesztés] 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:

,

ahol a Fréchet derivált X_n-re alkalmazva. A módszer alkalmazásához szükséges, hogy a Fréchet derivált invertálható legyen minden X_n pontban.

[szerkesztés] Komplex függvények

Az x⁵ − 1 = 0 függvény gyűjtőtere; a sötétebb részek azt jelentik , hogy ott több iteráció konvergál.

Mikor komplex függvényekkel dolgozunk, akkor a Newton módszert direkt lehet alkalmazni 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é.

[szerkesztés] 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]), sections 9.4 [2] and 9.6 [3].
• 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.

[szerkesztés] Külső linkek

• Newton's method on Wolfram.com
• 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