Newton módszere - Newton's method

A numerikus analízis , Newton-módszer , más néven a Newton-Raphson módszer elnevezett Isaac Newton és Joseph Raphson , egy gyökkereső algoritmus , amely gyárt egymás jobb közelítések a gyökereket (vagy nulla) egy igazi -valued funkciót . A legegyszerűbb változata kezdődik egy egyváltozós függvény f definiált egy valós változó x , a függvény -származékot f ' , és egy kezdeti becslés x ₀ a gyökér a f . Ha a függvény kielégítő feltételezéseket teljesít, és a kezdeti találgatás közel van, akkor

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

a gyök jobb közelítése, mint x ₀ . Geometriailag ( x ₁ , 0) a metszéspontja a x -tengely és a tangens a grafikon a F at ( x ₀ , F  ( x ₀ )) : ez a javított becslés az egyedülálló gyökér a lineáris közelítés a kezdeti ponton. A folyamatot megismételjük, mint

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

amíg kellően pontos értéket el nem ér. Ez az algoritmus az első a Householder módszerek osztályában , amelyet Halley módszere követett . A módszer kiterjeszthető komplex függvényekre és egyenletrendszerekre is .

Leírás

Az f függvény kék színnel, az érintővonal pedig pirossal látható. Látjuk, hogy x _{n + 1} jobb közelítés, mint x _n az f függvény x gyökére .

Az ötlet az, hogy egy kezdeti találgatással kezdjük, amely ésszerűen közel van a valódi gyökhöz , majd a függvényt érintő vonalával közelítjük a számítás segítségével , és végül kiszámítjuk ennek az érintővonalnak az x -intercepcióját elemi algebrával . Ez az x -intercept általában jobban közelíti az eredeti függvény gyökerét, mint az első találgatás, és a módszer iterálható .

Formálisan, tegyük fel, hogy f  : ( a , b ) → ℝ egy differenciálható függvény az intervallum ( a , b ) értékekkel a valós számok  ℝ , és van néhány aktuális közelítés x _n . Ezután levezethetjük a jobb közelítés képletét, x _{n + 1} a jobb oldali diagramra hivatkozva. Az egyenlet a húzott érintő a görbe y = f  ( x ) a X = X _n jelentése

${\ displaystyle y = f '(x_ {n}) \, (x-x_ {n})+f (x_ {n}),}$

ahol f ′ a származékot jelöli . Ennek az egyenesnek az x -intercepcióját ( x értéke, amely y = 0 -t ad) a következő közelítésnek, x _{n + 1} -nek tekintjük a gyökhöz , így az érintőleges egyenlet teljesül, ha : ${\ displaystyle (x, y) = (x_ {n+1}, 0)}$

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

Az x _{n + 1} megoldása megadja

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

A folyamatot tetszőleges x ₀ kezdőértékkel kezdjük . (Minél közelebb van a nullához, annál jobb. De ha nincs intuíció arról, hogy hol lehet a nulla, a "találgatás és ellenőrzés" módszer a közbenső érték tételre való hivatkozással ésszerűen kis intervallumra szűkítheti a lehetőségeket .) A módszer általában konvergál, feltéve, hogy ez a kezdeti találgatás elég közel van az ismeretlen nullához, és ha f ′ ( x ₀ ) ≠ 0 . Ezenkívül az  1 többszörös nulla esetén a konvergencia legalább másodfokú (lásd a konvergencia mértékét ) a nulla szomszédságában , ami intuitív módon azt jelenti, hogy a helyes számjegyek száma nagyjából megkétszereződik minden lépésben. További részletek az alábbi elemzési részben találhatók.

A háztartási módszerek hasonlóak, de magasabb rendűek a még gyorsabb konvergencia érdekében. Az egyes lépésekhez szükséges extra számítások azonban lelassíthatják a teljes teljesítményt Newton módszeréhez képest, különösen akkor, ha f vagy származékai számítási szempontból drágák.

Történelem

A "Newton -módszer" név Isaac Newton leírásából származik, amely a módszer speciális esetét tartalmazza a De analysi per aequationes numero terminorum infinitas (1669 -ben, 1716 -ban William Jones kiadása ) és a De metodis fluxionum et serierum infinitarum ( 1671 -ben íródott, John Colson 1736 -ban lefordította és közzétette az Fluxions módszerével ). Módszere azonban lényegesen eltér a fent ismertetett modern módszertől. Newton a módszert csak polinomokra alkalmazta, kezdve a kezdeti gyökbecsléssel és kivonva a hibajavítások sorozatát. Mindegyik javítást felhasználta a polinom átírására a fennmaradó hiba szempontjából, majd a magasabb fokú kifejezések figyelmen kívül hagyásával megoldott egy új korrekciót. Nem kapcsolta kifejezetten a módszert a származékokhoz, és nem mutatott be általános képletet. Newton ezt a módszert alkalmazta numerikus és algebrai problémákra is, utóbbi esetben Taylor -sorozatokat állított elő.

Newton módszerét Vieta hasonló, de kevésbé pontos módszeréből származtathatta . A lényege Vieta módszere megtalálható a munka a perzsa matematikus Sharaf al-Din al-Tusi , míg az utódja Jamshid al-Kashi használt forma Newton módszerrel megoldani x ^P - N = 0 , hogy megtalálják gyökereit N ( Ypma 1995). Newton négyzetgyök -számítási módszerének egy különleges esete volt ismert az ókorban, és gyakran babiloni módszernek is nevezik .

Newton módszerét Seki Kōwa , 17. századi japán matematikus használta az egyváltozós egyenletek megoldására, bár a számítással való kapcsolat hiányzott.

Newton módszerét először 1685 -ben jelentette meg John Wallis A traktátusa az algebrából mind történeti, mind gyakorlati c . 1690 -ben Joseph Raphson egyszerűsített leírást tett közzé az Analysis aequationum universalis -ban . Raphson is csak polinomokra alkalmazta a módszert, de elkerülte Newton fárasztó átírási folyamatát azzal, hogy minden egymást követő korrekciót kivont az eredeti polinomból. Ez lehetővé tette számára, hogy minden problémához újrafelhasználható iteratív kifejezést származtasson. Végül 1740 -ben Thomas Simpson leírta Newton módszerét, mint iteratív módszert az általános nemlineáris egyenletek számítás segítségével történő megoldására, lényegében megadva a fenti leírást. Ugyanebben a kiadványban Simpson két egyenlet rendszereit is általánosítja, és megjegyzi, hogy Newton módszere használható az optimalizálási problémák megoldására a gradiens nullára állításával.

Arthur Cayley 1879 -ben A Newton – Fourier képzeletbeli probléma című könyvben elsőként vette észre a nehézségeket Newton módszerének általánosításában a 2 -nél nagyobb fokú polinomok összetett gyökereire és összetett kezdeti értékekre. Ez megnyitotta az utat a racionális függvények iterációinak elméletének tanulmányozásához .

Gyakorlati szempontok

A Newton -módszer erőteljes technika - általában a konvergencia másodfokú: ahogy a módszer konvergál a gyökön, a gyök és a közelítés közötti különbség négyzetben van (a pontos számjegyek száma nagyjából megkétszereződik) minden lépésnél. Van azonban némi nehézség a módszerrel.

A függvény deriváltjának kiszámításának nehézségei

Newton módszere megköveteli, hogy a derivált közvetlenül kiszámítható legyen. A származék analitikai kifejezése nem biztos, hogy könnyen beszerezhető, vagy költséges lehet annak értékelése. Ezekben a helyzetekben helyénvaló lehet a derivált közelítése a függvény két közeli pontján átmenő egyenes meredekségével. Ennek a közelítésnek az alkalmazása olyasmit eredményezne, mint a szekáns módszer, amelynek konvergenciája lassabb, mint Newton módszeré.

A módszer nem sikerült a gyökérhez konvergálni

Fontos, hogy áttekintsük a Newton -módszer másodfokú konvergenciájának bizonyítékait, mielőtt végrehajtjuk. Konkrétan felül kell vizsgálni a bizonyításban tett feltételezéseket. Azokban a helyzetekben, amikor a módszer nem konvergál , annak oka az, hogy az ebben a bizonyításban tett feltételezések nem teljesülnek.

Túllépés

Ha az első derivált nem megfelelően viselkedik egy adott gyökér szomszédságában, akkor a módszer túlléphet, és eltérhet attól a gyöktől. Példa egy olyan gyökű függvényre, amelynél a származék nem megfelelően viselkedik a gyökér szomszédságában

${\ displaystyle f (x) = | x |^{a}, \ quad 0 <a <{\ tfrac {1} {2}}}$

amelynél a gyök túl lesz hajtva és az x sorrendje eltér. Az egy = 1/2, a gyök továbbra is túl lesz hajtva, de a sorozat két érték között ingadozik. For1/2< A <1 , a gyökér továbbra is előre-, de a sorozat konvergál, és a ≥ 1 gyökér nem lesz előre- egyáltalán.

Bizonyos esetekben Newton módszere stabilizálható egymást követő túllazítás alkalmazásával , vagy ugyanezzel a módszerrel növelhető a konvergencia sebessége.

Álló pont

Ha a függvény álló pontjával találkozunk, a derivált értéke nulla, és a módszer véget ér a nullával való osztás miatt .

Rossz kezdeti becslés

A kezdeti becslés nagy hibája hozzájárulhat az algoritmus nem konvergenciájához. Ennek a problémának a kiküszöbölésére gyakran linearizálható a számítás, naplók, differenciálok vagy éppen evolúciós algoritmusok, például a sztochasztikus alagút segítségével optimalizált függvény . A jó kezdeti becslések közel állnak a globálisan optimális paraméterbecsléshez. A nemlineáris regresszióban a négyzetes hibák összege (SSE) csak "közel" a parabolikushoz a végső paraméterbecslések tartományában. Az itt talált kezdeti becslések lehetővé teszik a Newton – Raphson módszer gyors konvergenciáját. Csak itt van az SSE hessiai mátrixa pozitív, és az SSE első deriváltja közel nulla.

A nem konvergencia enyhítése

A Newton -módszer robosztus megvalósításában gyakori, hogy korlátokat szabunk az iterációk számának, a megoldást egy olyan intervallumhoz kötjük, amelyről ismert, hogy tartalmazza a gyökeret, és kombinálják a módszert egy robusztusabb gyökérkereső módszerrel.

Lassú konvergencia az 1 -nél nagyobb sokszínűségi gyökereknél

Ha a keresett gyök szorzata egynél nagyobb, akkor a konvergencia aránya csak lineáris (a hibákat minden lépésben állandó tényezővel csökkentjük), hacsak nem teszünk különleges lépéseket. Ha két vagy több gyök közel van egymáshoz, sok ismétlésbe telhet, mire az iterációk elég közel kerülnek az egyikhez, hogy a másodfokú konvergencia nyilvánvaló legyen. Ha azonban a gyök többszörössége ismert, a következő módosított algoritmus megőrzi a másodfokú konvergencia arányát: ${\ displaystyle m}$

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

Ez egyenértékű az egymást követő túllazítás alkalmazásával . Másrészt, ha a gyök m többszörössége nem ismert, akkor egy vagy két iteráció elvégzése után meg lehet becsülni , majd ezt az értéket felhasználva növelni kell a konvergencia mértékét. ${\ displaystyle m}$

Ha a gyök m szorzata véges, akkor g ( x ) = f ( x ) / f ' ( x ) gyökere ugyanabban a helyen lesz, többszörösséggel. Newton módszerének alkalmazása a g ( x ) gyökének megtalálására másodfokú konvergencia sok esetben, bár általában magában foglalja az f ( x ) második deriváltját . Egy különösen egyszerű esetben, ha f ( x ) = x ^m, akkor g ( x ) = x / m és Newton metódusa egyetlen iterációban találja meg a gyököt

${\ displaystyle x_ {n+1} = x_ {n}-{\ frac {g (x_ {n})} {g '(x_ {n})}} = x_ {n}-{\ frac {x_ { n}/m} {1/m}} = 0 \}}$

Elemzés

Tegyük fel, hogy a függvény f van egy nulla α , azaz, f  ( α ) = 0 , és f differenciálható egy szomszédságában az α .

Ha f folytonosan differenciálható, és annak származéka nem nulla a  α , akkor létezik egy szomszédságában az α olyan, hogy az összes kiindulási értékek x ₀ , hogy a környéken, a szekvencia ( x _n ) lesz Converge a α .

Ha a függvény folyamatosan differenciálható, és származéka nem 0 az α -nál, és van egy második deriváltja α -nál, akkor a konvergencia másodfokú vagy gyorsabb. Ha a második derivált nem 0 meg α , akkor a konvergencia csupán kvadratikus. Ha a harmadik derivált létezik és az α szomszédságában van , akkor:

${\ displaystyle \ Delta x_ {i+1} = {\ frac {f '' (\ alfa)} {2f '(\ alpha)}} (\ Delta x_ {i})^{2}+O (\ Delta x_ {i})^{3} \ ,,}$

ahol

${\ displaystyle \ Delta x_ {i} \ triangleq x_ {i}-\ alpha \ ,.}$

Ha a derivált α esetén 0 , akkor a konvergencia általában csak lineáris. Pontosabban, ha f kétszer folyamatosan differenciálható, f ′ ( α ) = 0 és f ″ ( α ) ≠ 0 , akkor létezik egy olyan α szomszédság , hogy az adott x ₀ minden kiindulási érték esetén az iterációk sorrendje konvergál lineárisan, a sebesség 1/2 Alternatív módon, ha f ' ( α ) = 0 és f' ( x ) ≠ 0 az X ≠ α , x  egy szomszédságában U a α , α , hogy egy nulla a multiplicitás R , és ha f ∈ C ^r ( U ) , akkor létezik olyan α szomszédság , hogy az összes x ₀ kezdőérték esetén az iterációk sorrendje lineárisan konvergál.

A patológiás helyzetekben azonban még a lineáris konvergencia sem garantált.

A gyakorlatban ezek az eredmények helyi jellegűek, és a konvergencia szomszédsága nem ismert előre. De a globális konvergenciával kapcsolatban is vannak eredmények: például, ha az α jobboldali U ₊ szomszédságát adjuk meg , ha f kétszer differenciálható U _{+ -ban,} és ha f ′ ≠ 0 , f · f ″ > 0 az U _{+ -ban} , akkor minden x ₀ az U _{+ -ban,} az x _k sorozat monoton csökken α _-ra .

A másodfokú konvergencia bizonyítása Newton iteratív módszeréhez

Szerint a Taylor-tétel , minden olyan funkciót, f  ( x ) , amely a folyamatos második derivált leírható egy expanziós a körül a pont, amely közel van a gyöke f  ( x ) . Tegyük fel, hogy ez a gyök α . Ekkor f  ( α ) tágulása x _n körül :

${\ displaystyle f (\ alpha) = f (x_ {n})+f '(x_ {n}) (\ alpha -x_ {n})+R_ {1} \,}$

( 1 )

ahol a Taylor sorozat bővítési maradékának Lagrange formája található

${\ displaystyle R_ {1} = {\ frac {1} {2!}} f '' (\ xi _ {n}) (\ alpha -x_ {n})^{2} \ ,,}$

ahol ξ _n között van x _n és α .

Mivel α a gyök, az ( 1 ):

${\ displaystyle 0 = f (\ alpha) = f (x_ {n})+f '(x_ {n}) (\ alpha -x_ {n})+{\ tfrac {1} {2}} f " (\ xi _ {n}) (\ alfa -x_ {n})^{2} \,}$

( 2 )

A ( 2 ) egyenletet f ′ ( x _n ) -vel elosztva és átrendezve kapjuk

${\ displaystyle {\ frac {f (x_ {n})} {f '(x_ {n})}}+\ bal (\ alpha -x_ {n} \ right) = {\ frac {-f "( \ xi _ {n})} {2f '(x_ {n})}} \ bal (\ alpha -x_ {n} \ jobb)^{2}}$

( 3 )

Ne feledje, hogy az x _{n + 1} értékét a

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

( 4 )

az egyik azt találja

${\ displaystyle \ underbrace {\ alpha -x_ {n+1}} _ {\ varepsilon _ {n+1}} = {\ frac {-f '' (\ xi _ {n})} {2f '(x_ {n})}} (\, \ merevítő {\ alpha -x_ {n}} _ {\ varepsilon _ {n}} \,)^{2} \ ,.}$

Vagyis

${\ displaystyle \ varepsilon _ {n+1} = {\ frac {-f '' (\ xi _ {n})} {2f '(x_ {n})}} \ cdot {\ varepsilon _ {n}} ^{2} \,}$

( 5 )

Mindkét oldal abszolút értékét figyelembe véve

${\ displaystyle \ left | {\ varepsilon _ {n+1}} \ right | = {\ frac {\ left | f '' (\ xi _ {n}) \ right |} {2 \ left | f '( x_ {n}) \ jobb |}} \ cdot {\ varepsilon _ {n}}^{2} \ ,.}$

( 6 )

A ( 6 ) egyenlet azt mutatja, hogy a konvergencia mértéke legalább másodfokú, ha az alábbi feltételek teljesülnek:

1. f ′ ( x ) ≠ 0 ; minden x ∈ I esetén , ahol I a [ α - r , α + r ] intervallumnéhány r ≥ | α - x ₀ | ;
2. f ″ ( x ) folytonos, minden x ∈ I esetén ;
3. x ₀ van elegendően közel a gyökér α .

A kellően közeli kifejezés ebben az összefüggésben a következőket jelenti:

Végül ( 6 ) a következőképpen fejezhető ki:

${\ displaystyle \ bal | {\ varepsilon _ {n+1}} \ jobb | \ leq M {\ varepsilon _ {n}}^{2} \,}$

ahol M az ε _n ² változó együttható szupremumja az 1. feltételben meghatározott I intervallumon , azaz:

${\ displaystyle M = \ sup _ {x \ in I} {\ frac {1} {2}} \ left | {\ frac {f '' (x)} {f '(x)}} \ right |. \,}$

Az x ₀ kezdőpontot úgy kell megválasztani, hogy az 1–3. Feltételek teljesüljenek, ahol a harmadik feltétel megköveteli, hogy M | ε ₀ | <1 .

Vonzásmedencék

A diszjunkt részhalmazai A medencék vonzás -az régióiban a valós számegyenes, hogy az egyes régiókon belül iteráció bármely pontján vezet egy bizonyos kiváltó lehet végtelen számú és tetszőlegesen kicsi. Például az f  ( x ) = x ³ - 2 x ² - 11 x + 12 = ( x - 4) ( x - 1) ( x + 3) függvény esetében az alábbi kezdeti feltételek egymást követő vonzáskörzetekben vannak:

2,352 875 27	konvergál ahhoz	4;
2,352 841 72	konvergál ahhoz	−3;
2,352 837 35	konvergál ahhoz	4;
2,352 836 327	konvergál ahhoz	−3;
2,352 836 323	konvergál ahhoz	1.

Hiba elemzés

A Newton -módszer csak akkor garantálja a konvergenciát, ha bizonyos feltételek teljesülnek. Ha a másodfokú konvergencia bizonyításában tett feltételezések teljesülnek, a módszer konvergál. A következő alfejezetekben a módszer konvergenciájának elmulasztása azt jelzi, hogy a bizonyításban szereplő feltételezések nem teljesültek.

Rossz kiindulópontok

Bizonyos esetekben a függvény konvergenciához szükséges feltételei teljesülnek, de a kezdőpontnak választott pont nem abban az intervallumban van, ahol a módszer konvergál. Ez megtörténhet például, ha az a függvény, amelynek a gyökere keresett, aszimptotikusan megközelíti a nullát, mivel x a ∞ vagy a −∞ értékhez megy . Ilyen esetekben más módszert, például kettéosztást kell használni, hogy jobb becslést kapjunk a kezdőpontként használt nulláról.

Az iterációs pont helyhez kötött

Tekintsük a funkciót:

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

Maximuma x = 0 , oldatai pedig f  ( x ) = 0 x = ± 1 -nél . Ha az iterációt az álló helyről kezdjük x ₀ = 0 (ahol a derivált nulla), x ₁ nem lesz definiált, mivel a (0,1) érintő párhuzamos az x tengelyével:

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

Ugyanez a probléma merül fel, ha a kiindulópont helyett bármely iterációs pont helyhez kötött. Még ha a derivált kicsi, de nem nulla, a következő iteráció sokkal rosszabb közelítés lesz.

A kezdőpont ciklusba lép

Az x ³ -2 x + 2 érintővonalai 0 -nál és 1 -nél metszik az x -tengelyt 1 -nél, illetve 0 -nál, ami illusztrálja, hogy Newton módszere miért ingadozik ezen értékek között néhány kiindulópont esetében.

Egyes funkcióknál egyes kiindulópontok végtelen ciklusba léphetnek, megakadályozva a konvergenciát. Hagyja

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

és a 0 -t vegyük kiindulópontnak. Az első iteráció 1 -et állít elő, a második pedig 0 -ra tér vissza, így a szekvencia váltakozik a kettő között anélkül, hogy gyökérré konvergálna. Valójában ez a 2-ciklus stabil: vannak olyan környékek 0 és 1 körül, ahonnan minden pont aszimptotikusan iterál a 2-ciklushoz (és így nem a függvény gyökeréhez). Általában a szekvencia viselkedése nagyon összetett lehet (lásd Newton fraktál ). Ennek az egyenletnek a valódi megoldása az−1,769 292 35 ….

Származékos kérdések

Ha a függvény nem folyamatosan differenciálható a gyökér szomszédságában, akkor lehetséges, hogy Newton metódusa mindig eltérni fog, és meghiúsul, hacsak a megoldást nem találjuk ki az első próbálkozáskor.

A származék nem létezik gyökérben

Egy egyszerű példa egy függvényre, ahol Newton metódusa eltér, és megpróbálja megtalálni a nulla kockagyökét. A kockagyök folytonos és végtelenül differenciálható, kivéve x = 0 , ahol a származéka nem definiált:

${\ displaystyle f (x) = {\ sqrt [{3}] {x}}.}$

Bármely x _n iterációs pont esetén a következő iterációs pont a következő lesz:

${\ displaystyle x_ {n+1} = x_ {n}-{\ frac {f (x_ {n})} {f '(x_ {n})}} = x_ {n}-{\ frac {{x_ {n}}^{\ frac {1} {3}}} {{\ frac {1} {3}} {x_ {n}}^{{\ frac {1} {3}}-1}}} = x_ {n} -3x_ {n} =-2x_ {n}.}$

Az algoritmus felülmúlja a megoldást, és az y tengely túloldalán landol , távolabb, mint eredetileg; Newton módszerének alkalmazása valójában megkétszerezi a megoldástól való távolságokat minden iterációnál.

Valójában az iterációk a végtelenségig eltérnek minden f  ( x ) = | esetén x | ^α , ahol 0 < α <1/2. Az α = korlátozó esetben1/2(négyzetgyök), az iterációk korlátlanul váltakoznak az x ₀ és - x ₀ pontok között , tehát ebben az esetben sem konvergálnak.

Megszakított származék

Ha a derivált nem folytonos a gyökérnél, akkor előfordulhat, hogy a konvergencia nem következik be a gyök bármely szomszédságában. Fontolja meg a funkciót

${\ displaystyle f (x) = {\ begin {case} 0 & {\ text {if}} x = 0, \\ x+x^{2} \ sin {\ frac {2} {x}} & {\ szöveg {if}} x \ neq 0. \ end {tok}}}$

Származéka:

${\ displaystyle f '(x) = {\ begin {case} 1 & {\ text {if}} x = 0, \\ 1+2x \ sin {\ frac {2} {x}}-2 \ cos {\ frac {2} {x}} és {\ text {if}} x \ neq 0. \ end {tokok}}}$

Bármely szomszédságában a gyökér, hogy ez a származékos folyamatosan változik megjelölés x közelít a 0 a jobb (vagy bal oldali), míg f  ( x ) ≥ x - x ² > 0 a 0 < x <1 .

Így f  ( x )/f ' ( x ) korlátlan a gyökér közelében, és Newton módszere szinte mindenhol eltérni fog annak szomszédságában, annak ellenére, hogy:

• a funkció mindenhol differenciálható (és így folyamatos);
• a gyökérszármazék nem nulla;
• f végtelenül differenciálható, kivéve a gyökeret; és
• a derivált a gyök szomszédságában van határolva (ellentétben f  ( x )/f ' ( x )).

Nem másodfokú konvergencia

Bizonyos esetekben az iterációk konvergálnak, de nem olyan gyorsan, mint ígérték. Ezekben az esetekben az egyszerűbb módszerek ugyanolyan gyorsan konvergálnak, mint Newton módszere.

Nulla származék

Ha az első derivált nulla a gyöknél, akkor a konvergencia nem lesz másodfokú. Hagyja

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

akkor f ′ ( x ) = 2 x és következésképpen

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

Tehát a konvergencia nem másodfokú, annak ellenére, hogy a függvény mindenhol végtelenül differenciálható.

Hasonló problémák akkor is előfordulnak, ha a gyökér csak "majdnem" duplája. Például hagyjuk

${\ displaystyle f (x) = x^{2} (x-1000) +1.}$

Ezután az első néhány iteráció kezdődően X ₀ = 1 vannak

x ₀ = 1

x ₁ =0,500 250 376 …

x ₂ =0,251 062 828 …

x ₃ =0,127 507 934 …

x ₄ =0,067 671 976 …

x ₅ =0,041 224 176 …

x ₆ =0,032 741 218 …

x ₇ =0,031 642 362 …

hat ismétlés szükséges ahhoz, hogy elérjük azt a pontot, ahol a konvergencia másodfokúnak tűnik.

Nincs második származéka

Ha a gyökérben nincs második derivált, akkor előfordulhat, hogy a konvergencia nem másodfokú. Hagyja

${\ displaystyle f (x) = x+x^{\ frac {4} {3}}.}$

Azután

${\ displaystyle f '(x) = 1+{\ tfrac {4} {3}} x^{\ frac {1} {3}}.}$

És

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

kivéve, ha x = 0, ahol nincs meghatározva. Adott x _n ,

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

amelynek kb 4/3annyiszor annyi pontossággal, mint x _n . Ez kevesebb, mint kétszer annyi, mint amennyi a másodfokú konvergenciához szükséges. Tehát a Newton -módszer konvergenciája (ebben az esetben) nem másodfokú, pedig: a függvény mindenhol folyamatosan differenciálható; a derivált nem nulla a gyöknél; és f végtelenül differenciálható, kivéve a kívánt gyökeret.

Általánosítások

Komplex funkciók

Vonzómedencék x ^{5 esetén} - 1 = 0 ; a sötétebb azt jelenti, hogy több iterációt kell konvergálni.

Ha összetett függvényekkel foglalkozunk , Newton módszerét közvetlenül alkalmazhatjuk nulláik megtalálására. Minden nullának van vonzómedencéje a komplex síkban, minden olyan kiindulási érték halmaza, amely miatt a módszer az adott nullához konvergál. Ezeket a készleteket az ábrán látható módon lehet leképezni. Sok összetett funkció esetében a vonzásmedencék határai fraktálok .

Bizonyos esetekben a komplex síkban vannak olyan régiók, amelyek nincsenek ezen vonzáskörzetek egyikében sem, vagyis az iterációk nem konvergálnak. Például, ha valaki valódi kezdeti feltételt használ az x ² + 1 gyökének megkeresésére , akkor az összes későbbi iteráció valós szám lesz, és így az iterációk nem konvergálhatnak egyik gyökérhez sem, mivel mindkét gyök nem valós. Ebben az esetben szinte minden valódi kezdeti feltétel kaotikus viselkedéshez vezet , míg egyes kezdeti feltételek vagy a végtelenségig, vagy bármilyen véges hosszúságú ciklusokig ismétlődnek.

Curt McMullen kimutatta, hogy minden lehetséges tisztán iteratív algoritmushoz, amely hasonló a Newton -módszerhez, az algoritmus eltérni fog a komplex sík egyes nyitott területein, ha valamilyen 4 vagy magasabb fokú polinomra alkalmazzák. McMullen azonban általánosan konvergens algoritmust adott a 3. fokú polinomokra.

Csebev harmadik rendű módszere

Nash – Moser iteráció

Egyenletrendszerek

k változó, k függvény

Newton módszerét is használhatjuk egyenletrendszerek megoldására, ami a folyamatosan differenciálható függvények (egyidejű) nulláinak megtalálását jelenti . Ez egyenértékű egyetlen vektorértékű függvény nulláinak megtalálásával . A fentebb megadott megfogalmazásban a skalárokat vektorok váltják fel, és ahelyett, hogy a függvényt a származékával osztanánk el, a bal oldali helyett a szorzatot kell megszorozni a jakobi mátrix inverzével . Ennek eredménye a kifejezés ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle f: \ mathbb {R} \ to \ mathbb {R}}$${\ displaystyle F: \ mathbb {R} ^{k} \ to \ mathbb {R} ^{k}}$${\ displaystyle x_ {n}}$${\ displaystyle \ mathbf {x} _ {n}}$${\ displaystyle f (x_ {n})}$${\ displaystyle f '(x_ {n})}$${\ displaystyle F (\ mathbf {x} _ {n})}$${\ displaystyle k \ x k}$ ${\ displaystyle J_ {F} (\ mathbf {x} _ {n})}$

${\ displaystyle \ mathbf {x} _ {n+1} = \ mathbf {x} _ {n} -J_ {F} (\ mathbf {x} _ {n})^{-1} F (\ mathbf { x} _ {n})}$.

Ahelyett, hogy ténylegesen kiszámítanánk a jakobi mátrix inverzét, időt takaríthatunk meg és növelhetjük a numerikus stabilitást a lineáris egyenletrendszer megoldásával

${\ displaystyle J_ {F} (\ mathbf {x} _ {n}) (\ mathbf {x} _ {n+1}-\ mathbf {x} _ {n}) =-F (\ mathbf {x} _ {n})}$

az ismeretlenért . ${\ displaystyle \ mathbf {x} _ {n+1}-\ mathbf {x} _ {n}}$

k változó, m egyenlet, m > k -val

A Newton -módszer k -dimenziós változata használható k (nemlineáris) egyenleteknél nagyobb rendszerek megoldására is, ha az algoritmus a nem négyzet alakú jakobi mátrix általánosított inverzét használja J ⁺ = ( J ^T J ) ⁻¹ J ^T inverze helyett J. Ha a nemlineáris rendszernek nincs megoldása, akkor a módszer nem lineáris legkisebb négyzetek értelmében próbál megoldást találni . További információkért lásd Gauss – Newton algoritmusát .

Egy Banach térben

Egy másik általánosítás Newton módszere egy Banach -térben meghatározott funkcionális F gyökere megtalálására . Ebben az esetben a készítmény

${\ displaystyle X_ {n+1} = X_ {n}-{\ bigl (} F '(X_ {n}) {\ bigr)}^{-1} F (X_ {n}), \,}$

ahol F ′ ( X _n ) az X _n -nél számított Fréchet -származék . Ahhoz, hogy a módszer alkalmazható legyen, a Fréchet -deriváltnak minden X _n -nél korlátlanul megfordíthatónak kell lennie. A gyök létezésének és konvergenciájának feltétele a Newton – Kantorovich -tétel .

Több mint p -adic számok

A p -adic elemzésben az a standard módszer, amellyel egy polinomiális egyenletet egy változóban p -adic gyökkel lehet megjeleníteni, Hensel lemma , amely a Newton -módszerből származó rekurziót használja a p -adikus számokra. A valódi számokhoz képest stabilabb összeadási és szorzási viselkedés miatt a p -adikus számokban (konkrétan az egységgömb a p -adics -ban gyűrű), a Hensel -lemma konvergenciája sokkal egyszerűbb hipotézisek mellett garantálható, mint a a klasszikus Newton -féle módszer a valós vonalon.

Newton -Fourier módszer

A Newton – Fourier módszer Joseph Fourier kiterjesztése Newton módszerére, hogy határokat biztosítson a gyökközelítés abszolút hibájára, miközben másodfokú konvergenciát biztosít.

Tegyük fel, hogy f  ( x ) kétszer folyamatosan differenciálható az [ a , b ] lapon, és hogy f tartalmaz gyökeret ebben az intervallumban. Tegyük fel, hogy f ′ ( x ), f ″ (x) ≠ 0 ezen az intervallumon (ez a helyzet például akkor, ha f  ( a ) <0 , f  ( b )> 0 és f ′ ( x )> 0 , és f ″ ( x )> 0 ezen az intervallumon). Ez garantálja, hogy ezen az intervallumon belül egyedi gyökér van, nevezzük α -nak . Ha konkáv, hanem lefelé homorú felfelé, majd cserélje f  ( x ) a - f  ( x ) , mivel ugyanaz a gyökerek.

Legyen x ₀ = b az intervallum jobb végpontja, és z ₀ = a legyen az intervallum bal végpontja. Adott x _n , határozza meg

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

ami csak Newton módszere, mint korábban. Ezután határozza meg

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

ahol a nevező f ′ ( x _n ) és nem f ′ ( z _n ) . Az x _n iterációk szigorúan csökkennek a gyökéig, míg a z _n iterációk szigorúan a gyökéig növekednek. Is,

${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {x_ {n+1} -z_ {n+1}} {(x_ {n} -z_ {n})^{2}}} = {\ frac {f '' (\ alfa)} {2f '(\ alfa)}}}$

így x _n és z _n közötti távolság négyzetesen csökken.

Kvázi-Newton módszerek

Ha a Jacobian nem érhető el, vagy túl drága ahhoz, hogy minden iterációnál kiszámítsa, kvázi Newton-módszert lehet használni.

q-analóg

Newton módszere általánosítható a szokásos derivált q-analógjával .

Módosított Newton -módszerek

Maehly eljárása

Egy nemlineáris egyenletnek általában több megoldása van. De ha a kezdeti érték nem megfelelő, akkor Newton módszere nem konvergálhat a kívánt megoldással, vagy konvergálhat a korábban talált megoldással. Ha már találtunk N megoldást , akkor a következő gyök megtalálható Newton módszerének alkalmazásával a következő egyenletre: ${\ displaystyle f (x) = 0}$

${\ displaystyle F (x) = {\ frac {f (x)} {\ prod _ {i = 1}^{N} (x-x_ {i})}} = 0.}$

Ezt a módszert alkalmazzák a második típusú Bessel -függvény nulláinak megszerzésére .

Hirano módosított Newton -módszere

Hirano módosított Newton -módszere olyan módosítás, amely megőrzi a Newton -módszer konvergenciáját és elkerüli az instabilitást. Összetett polinomok megoldására fejlesztették ki.

Interval Newton módszer

Newton módszerének intervallum -aritmetikával való kombinálása bizonyos esetekben nagyon hasznos. Ez olyan leállási feltételt biztosít, amely megbízhatóbb a szokásosnál (amelyek a függvény kis értéke, vagy a változó kis eltérése az egymást követő iterációk között). Ezenkívül észlelhet olyan eseteket, amikor Newton metódusa elméletileg konvergál, de számszerűleg eltér az elégtelen lebegőpontos pontosság miatt (ez jellemzően a nagyfokú polinomokra vonatkozik, ahol a változó nagyon kicsi változása drámaian megváltoztathatja a függvény értékét) ; lásd Wilkinson -féle polinom ).

Vegyük , ahol egy igazi intervallum, és tegyük fel, hogy van egy intervallum kiterjesztése az jelenti, hogy vesz bemenetként egy intervallumot , és kiadja egy intervallum olyan, hogy: ${\ displaystyle f \ in {\ mathcal {C}}^{1} (X)}$${\ displaystyle X}$${\ displaystyle F '}$${\ displaystyle f '}$${\ displaystyle F '}$${\ displaystyle Y \ subseteq X}$${\ displaystyle F '(Y)}$

${\ displaystyle {\ begin {aligned} F '([y, y]) & = \ {f' (y) \} \\ [5pt] F '(Y) & \ supseteq \ {f' (y) \ y közepén \ Y -ban \ \. \ végén {igazítva}}}$

Feltételezzük azt is , hogy különösen legfeljebb egy gyökere van . Ezután definiáljuk az intervallum Newton operátort: ${\ displaystyle 0 \ notin F '(X)}$${\ displaystyle f}$${\ displaystyle X}$

${\ displaystyle N (Y) = m-{\ frac {f (m)} {F '(Y)}} = \ left \ {\ left.m-{\ frac {f (m)} {z}} ~ \ jobb | ~ z \ in F '(Y) \ jobb \}}$

hol . Ne feledje, hogy a hipotézis azt jelenti, hogy jól definiált és intervallum (az intervallumműveletekről további részletekért lásd az intervallum -aritmetikát ). Ez természetesen a következő sorrendhez vezet: ${\ displaystyle m \ Y -ban}$${\ displaystyle F '}$${\ displaystyle N (Y)}$

${\ displaystyle {\ begin {aligned} X_ {0} & = X \\ X_ {k+1} & = N (X_ {k}) \ cap X_ {k}. \ end {aligned}}}$

Az átlagérték -tétel biztosítja, hogy ha van in gyök , akkor az is benne van . Sőt, a hipotézis biztosítja, hogy a legfeljebb fele akkora , ha az a felezőpontja , ezért ezt a sorozatot felé közeledik , ahol a gyökere az . ${\ displaystyle f}$${\ displaystyle X_ {k}}$${\ displaystyle X_ {k+1}}$${\ displaystyle F '}$${\ displaystyle X_ {k+1}}$${\ displaystyle X_ {k}}$${\ displaystyle m}$${\ displaystyle Y}$${\ displaystyle [x^{*}, x^{*}]}$${\ displaystyle x^{*}}$${\ displaystyle f}$${\ displaystyle X}$

Ha szigorúan tartalmazza , akkor a kiterjesztett intervallum osztás használata két intervallumból álló uniót eredményez  ; ezért több gyök automatikusan szétválasztott és határolt. ${\ displaystyle F '(X)}$${\ displaystyle 0}$${\ displaystyle N (X)}$

Alkalmazások

Minimalizálási és maximalizálási problémák

Newton módszerével minimális vagy maximum függvényt találhatunk . A derivált minimum vagy maximum nulla, így a helyi minimumokat és maximumokat Newton módszerének a deriváltra történő alkalmazásával lehet megtalálni. Az iteráció a következő lesz: ${\ displaystyle f (x)}$

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

Számok és hatványsorok többszörös inverzei

Fontos alkalmazás Newton-Raphson részlege , amelyet fel lehet használni, hogy gyorsan megtalálja a kölcsönös számos olyan , kizárólag a szorzás és kivonás, vagyis a szám x olyan, hogy1/x= a . Ezt úgy fogalmazhatjuk át, hogy f ( x ) = nulláját találjuk1/x- a . Van f '( x ) = -1/x ².

Newton iterációja az

${\ displaystyle x_ {n+1} = x_ {n}-{\ frac {f (x_ {n})} {f '(x_ {n})}} = x_ {n}+{\ frac {{\ frac {1} {x_ {n}}}-a} {\ frac {1} {x_ {n}^{2}}}} = x_ {n} (2 tengely_ {n}).}$

Ezért Newton iterációjához csak két szorzás és egy kivonás szükséges.

Ez a módszer nagyon hatékony egy hatványsor multiplikatív inverzének kiszámítására is .

Transzcendentális egyenletek megoldása

Számos transzcendentális egyenlet megoldható Newton módszerével. Adva az egyenlet

${\ displaystyle g (x) = h (x),}$

A g ( x ) és / vagy h ( x ) egy transzcendentális funkciót , írunk

${\ displaystyle f (x) = g (x) -h (x).}$

Az eredeti egyenletet megoldó x értékek ekkor f  ( x ) gyökei , amelyek Newton módszerével megtalálhatók.

Különleges funkciók nulláinak megszerzése

Newton módszerét alkalmazzuk a Bessel -függvények arányára annak érdekében, hogy megszerezzük gyökerét.

Numerikus ellenőrzés a nemlineáris egyenletek megoldásaihoz

A nemlineáris egyenletek megoldásainak numerikus ellenőrzését Newton módszerének többszörös használatával és a megoldásjelöltek halmazának kialakításával hozták létre.

CFD modellezés

Egy iteratív Newton-Raphson eljárást alkalmaztunk annak érdekében, hogy stabil Dirichlet-határfeltételeket írjunk elő a CFD-ben , mint egy meglehetősen általános stratégiát az elektrokémiai cellakötegek jelenlegi és potenciális eloszlásának modellezésére.

Példák

Négyzetgyök

Tekintsük a probléma megtalálni a négyzetgyöke számos olyan , vagyis a pozitív szám x , hogy x ² = a . Newton módszere egy a sok négyzetgyök számítási módszer közül . Ezt úgy fogalmazhatjuk át, hogy f ( x ) = x ² - a nulláját találjuk . Nálunk f ′ ( x ) = 2 x .

Például, ha a 612 négyzetgyökét keresi x ₀ = 10 kezdeti találgatással , a Newton -módszerrel megadott sorrend:

${\ displaystyle {\ begin {mátrix} x_ {1} & = & x_ {0}-{\ dfrac {f (x_ {0})} {f '(x_ {0})}} & = & 10-{\ dfrac {10^{2} -612} {2-szer 10}} & = & 35,6 \ qquad \ qquad \ qquad \ quad \; \, {} \\ x_ {2} & = & x_ {1}-{\ dfrac {f (x_ {1})} {f '(x_ {1})}} & = & 35,6-{\ dfrac {35,6^{2} -612} {2-szer 35,6}} & = & { \ aláhúzás {2}} 6,395 \, 505 \, 617 \, 978 \ dots \\ x_ {3} & = & \ vdots & = & \ vdots & = & {\ aláhúzás {24.7}} 90 \, 635 \, 492 \, 455 \ pont \\ x_ {4} & = & \ vdots & = & \ vdots & = & {\ aláhúzva {24.738 \, 6}} 88 \, 294 \, 075 \ dot \\ x_ {5} & = & \ vdots & = & \ vdots & = & {\ aláhúzva {24.738 \, 633 \, 753 \, 7}} 67 \ pont \ end {mátrix}}}$

ahol a megfelelő számjegyeket aláhúzzák. Csak néhány iterációval sok tizedesjegy pontosságú megoldást kaphatunk.

Ha a képletet az alábbiak szerint átrendezzük, a babiloni módszer a négyzetgyök keresésére szolgál :

${\ displaystyle x_ {n+1} = x_ {n}-{\ frac {f (x_ {n})} {f '(x_ {n})}} = x_ {n}-{\ frac {x_ { n}^{2} -a} {2x_ {n}}} = {\ frac {1} {2}} {\ biggl (} 2x_ {n}-{\ Bigl (} x_ {n}-{\ frac {a} {x_ {n}}} {\ Bigr)} {\ biggr)} = {\ frac {1} {2}} {\ Bigl (} x_ {n}+{\ frac {a} {x_ { n}}} {\ Bigr)}}$

azaz a találgatás számtani átlaga , x _n ésa/x _n.

A cos ( x ) = x ^{3 megoldása}

Tekintsük a probléma megtalálni a pozitív szám x és cos ( x ) = x ³ . Ezt úgy fogalmazhatjuk át, hogy f ( x ) = cos ( x ) - x ³ nulláját találjuk . Van f ′ ( x ) = −sin ( x ) - 3 x ² . Mivel cos ( x ) ≤ 1 minden x és x ³ > 1 az x > 1 , tudjuk, hogy a mi megoldásunk hazugság 0 és 1 között.

Például egy x ₀ = 0,5 kezdeti tippeléssel a Newton -módszerrel megadott sorrend a következő (vegye figyelembe, hogy a 0 kezdőérték egy nem definiált eredményhez vezet, ami megmutatja a megoldáshoz közeli kezdőpont használatának fontosságát):

${\ displaystyle {\ begin {mátrix} x_ {1} & = & x_ {0}-{\ dfrac {f (x_ {0})} {f '(x_ {0})}} & = & 0,5- { \ dfrac {\ cos 0,5-0,5^{3}} {-\ sin 0,5-3 \ alkalommal 0,5^{2}}} & = & 1.112 \, 141 \, 637 \, 097 \ dots \\ x_ {2 } & = & x_ {1}-{\ dfrac {f (x_ {1})} {f '(x_ {1})}} & = & \ vdots & = & {\ aláhúzva {0.}} 909 \, 672 \, 693 \, 736 \ pont \\ x_ {3} & = & \ vdots & = & \ vdots & = & {\ aláhúzva {0.86}} 7 \, 263 \, 818 \, 209 \ pont \\ x_ {4} & = & \ vdots & = & \ vdots & = & {\ aláhúzva {0,865 \, 47}} 7 \, 135 \, 298 \ pont \\ x_ {5} & = & \ vdots & = & \ vdots & = & {\ aláhúzva {0,865 \, 474 \, 033 \, 1}} 11 \ pont \\ x_ {6} & = & \ vdots & = & \ vdots & = & {\ aláhúzva {0,865 \, 474 \, 033 \, 102}} \ pontok \ end {mátrix}}}$

A fenti példában a megfelelő számjegyek alá vannak húzva. Különösen az x ₆ helyes 12 tizedesjegyig. Látjuk, hogy a tizedespont utáni helyes számjegyek száma 2 -ről ( x _{3 esetén} ) 5 -re és 10 -re nő , ami a másodfokú konvergenciát illusztrálja.

Kód

Az alábbiakban egy példát mutatunk be a Newton módszerének a Julia programozási nyelvben, amellyel egy olyan függvény gyökerét találjuk meg, famelynek származéka van fprime.

A kezdeti találgatás x ₀ = 1 lesz, a függvény pedig f ( x ) = x ² - 2, így f ′ ( x ) = 2 x .

Newton módszerének minden új iterációját a jelzi x1. A számítás során ellenőrizni fogjuk, hogy a nevező ( yprime) nem lesz -e túl kicsi (kisebb, mint epsilon), ami akkor is így lenne, ha f ′ ( x _n ) ≈ 0 , mivel különben nagy mennyiségű hiba léphet fel.

x0            = 1         # The initial guess
f(x)          = x^2 - 2   # The function whose root we are trying to find
fprime(x)     = 2x        # The derivative of the function
tolerance     = 1e-7      # 7 digit accuracy is desired
epsilon       = 1e-14     # Do not divide by a number smaller than this
maxIterations = 20        # Do not allow the iterations to continue indefinitely
solutionFound = false     # Have not converged to a solution yet

for i = 1:maxIterations
  y      = f(x0)
  yprime = fprime(x0)

  if abs(yprime) < epsilon            # Stop if the denominator is too small
    break
  end

  global x1 = x0 - y/yprime           # Do Newton's computation

  if abs(x1 - x0) <= tolerance        # Stop when the result is within the desired tolerance
    global solutionFound = true
    break
  end

  global x0 = x1                      # Update x0 to start the process again
end

if solutionFound
  println("Solution: ", x1)           # x1 is a solution within tolerance and maximum number of iterations
else
  println("Did not converge")         # Newton's method did not converge
end

Lásd még

Megjegyzések

Hivatkozások

• Gil, A .; Segura, J .; Temme, NM (2007). Numerikus módszerek speciális funkciókhoz . Ipari és Alkalmazott Matematikai Társaság. ISBN 978-0-89871-634-4.
• Süli, Endre ; Mayers, David (2003). Bevezetés a numerikus elemzésbe . Cambridge University Press. ISBN 0-521-00794-1.

További irodalom

• Kendall E. Atkinson, An Introduction to Numerical Analysis , (1989) John Wiley & Sons, Inc, ISBN  0-471-62489-6
• Tjalling J. Ypma, A Newton – Raphson módszer történeti fejlődése, SIAM Review 37 (4), 531–551, 1995. doi : 10.1137/1037125 .
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Numerikus optimalizálás: Elméleti és gyakorlati szempontok . Universitext (Az 1997 -es francia fordítás második átdolgozott kiadása, szerk.). Berlin: Springer-Verlag. xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-X. MR  2265882 .
• P. Deuflhard, Newton -módszerek nemlineáris problémákhoz. Affin változatlanság és adaptív algoritmusok. Springer sorozat a számítási matematikában, Vol. 35. Springer, Berlin, 2004. ISBN  3-540-21099-7 .
• CT Kelley, Nemlineáris egyenletek megoldása Newton-módszerrel , 1. szám az Algoritmusok alapjai, SIAM, 2003. ISBN  0-89871-546-6 .
• JM Ortega, WC Rheinboldt, Ilineratív megoldás nemlineáris egyenletek több változóban. Classics in Applied Mathematics, SIAM, 2000. ISBN  0-89871-461-3 .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "9. fejezet. Gyökérkereső és nemlineáris egyenlethalmazok fontossági mintavétele" . Numerikus receptek: A tudományos számítástechnika művészete (3. kiadás). New York: Cambridge University Press. ISBN 978-0-521-88068-8.. Lásd különösen a 9.4. , 9.6 . És 9.7 .
• Avriel, Mordecai (1976). Nemlineáris programozás: elemzés és módszerek . Prentice Hall. 216–221. ISBN 0-13-623603-0.

Külső linkek

• "Newton -módszer" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Newton módszere" . MathWorld .
• Newton módszere, a Citizendium.
• Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
• Wu, X., Egyenletek gyöke, Tanfolyamjegyzetek.