Newton-módszer

A Wikipédiából, a szabad enciklopédiából

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. 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[szerkesztés | forrásszöveg szerkesztése]

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ékkel é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 fel, hogy ismerjük a xn közelítést. Tovább módosíthatjuk az összefüggést egy még jobb xn+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:

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:

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

A folyamatot az x0 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 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ó.

Példa[szerkesztés | forrásszöveg szerkesztése]

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

\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 x6 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 ( x3-re), 5-re és 10-re növekszik, illusztrálva a kvadratikus konvergenciát.

Egy szám négyzetgyöke[szerkesztés | forrásszöveg szerkesztése]

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.

\,x^2 = 612

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

\,f(x) = x^2 - 612

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

 f'(x) = 2x. \,

10 kezdeti becsléssel, a folytatás Newton-módszerrel megadva,

\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[szerkesztés | forrásszöveg szerkesztése]

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 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[szerkesztés | forrásszöveg szerkesztése]

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

Ellenpéldák[szerkesztés | forrásszöveg szerkesztése]

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.

Távoli kezdőpont[szerkesztés | forrásszöveg szerkesztése]

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

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[szerkesztés | forrásszöveg szerkesztése]

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:

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

f'(0) = 1 \! és 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 f(x) \ge x - x^2 > 0 \! ,ha 0 < x < 1 \!.

Tehát 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; 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[szerkesztés | forrásszöveg szerkesztése]

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(x) = x + x^{4/3} \! függvényt,

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

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

és a második deriváltja:

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

kivéve mikor x = 0 \! ahol végtelen. Tudván x_n \!,

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 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 f \! határozatlanul differenciálható, kivéve a gyökben.

A derivált nulla[szerkesztés | forrásszöveg szerkesztése]

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

f(x) = x^2 \!

akkor f'(x) = 2x \! és képletben 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ó[szerkesztés | forrásszöveg szerkesztése]

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

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 x0=0 (ahol a derivált nulla), x1 nem meghatárzoható.

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[szerkesztés | forrásszöveg szerkesztése]

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

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

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

Ha a derivált nem tűnik el \alpha -ban, akkor a konvergencia általában lineáris. Különösen, ha f kétszer folytonosan differenciálható, f'(\alpha) = 0 \! és f''(\alpha) \ne 0 \!, akkor létezik egy olyan környezet az \alpha körül, amelyből bármely x0 kezdeti értéket véve a sorozat lineárisan fog konvergálni, log10 2 arányossággal. Vagy, ha f'(\alpha) = 0 \! ha f'(x) \ne 0 \! adottak, \alpha egy U környezetéből, ha r \alpha multiplicitása és ha f \in C^r(U), akkor létezik egy olyan környezete \alpha-nak , hogy bármely x0 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 \alpha megfelelő U+környezete, haf kétszeresen differenciálható U+ és ha f' \ne 0 \!, f \cdot f'' > 0 \! U+-ban, akkor mindegyik x0 U+-ból a xk sorozat monoton csökken az \alpha felé .

Általánosítás[szerkesztés | forrásszöveg szerkesztése]

Nemlineáris egyenletrendszerek[szerkesztés | forrásszöveg szerkesztése]

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 : Rk Rk folytonosan differenciálható függvény gyökeit. Ekkor a fenti képletben balról kell megszorozni kinverzét a JF Jacobi - mátrixszal (xn), f '(xn) -nel osztás helyett. Sok időt lehet megspórolni, ha megoldjuk a lineáris egyenletrendszert, a mátrix invertálása helyett:

J_F(x_n) (x_{n+1} - x_n) = -F(x_n)\,\!

az ismeretlen xn+1 - xn-re. Összefoglalva ez a módszer akkor működik, ha az x0 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[szerkesztés | forrásszöveg szerkesztése]

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:

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

ahol F'_{X_n} 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.

Komplex függvények[szerkesztés | forrásszöveg szerkesztése]

Az x5 ‒ 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é.

Források[szerkesztés | forrásszöveg szerkesztése]

További információk[szerkesztés | forrásszöveg szerkesztése]