Њутн-Рафсонов метод

Илустрација Њутновог метода.

У нумеричкој анализи, Њутн-Рафсонов метод, такође познат и као Њутнов метод, назван по Исаку Њутну и Џозефу Рафсону, је алгоритам за проналажење нула који производи сукцесивно боље апроксимације нула (или корена) реалне функције. Најосновнија верзија почиње са реалном функцијом f, њеним изводом f′ и почетном претпоставком x₀ за нулу функције f. Ако f задовољава одређене претпоставке и почетна претпоставка је близу, онда је

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

боља апроксимација нуле од x₀. Геометријски, (x₁, 0) је пресек са x-осом тангенте графика функције f у тачки (x₀, f(x₀)): то јест, побољшана претпоставка, x₁, је јединствена нула линеарне апроксимације функције f у почетној претпоставци, x₀. Процес се понавља као

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

док се не достигне довољно прецизна вредност. Број тачних цифара се отприлике удвостручује са сваким кораком. Овај алгоритам је први у класи Хаусхолдерових метода, а наследио га је Халијев метод. Метод се такође може проширити на комплексне функције и на системе једначина.

Опис

Сврха Њутновог метода је проналажење нуле функције. Идеја је да се почне са почетном претпоставком о нули, апроксимира функција њеном тангентом у близини те претпоставке, а затим се нула линеарне апроксимације узме као следећа претпоставка за нулу функције. Ово ће обично бити ближе нули функције од претходне претпоставке, а метод се може итерирати.

x_n+1 је боља апроксимација од x_n за нулу x функције f (плава крива)

Најбоља линеарна апроксимација произвољне диференцијабилне функције $f(x)$ у близини тачке $x=x_{n}$ је тангента на криву, са једначином

$$f(x)\approx f(x_{n})+f'(x_{n})(x-x_{n}).$$

Нула ове линеарне функције, место где она сече $x$-осу, може се узети као ближа апроксимативна нула $x_{n+1}$:

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

Итерација обично побољшава апроксимацију

Процес се може започети са било којом произвољном почетном претпоставком $x_{0}$, иако ће генерално захтевати мање итерација да конвергира ако је претпоставка близу једне од нула функције. Метод ће обично конвергирати ако је $f'(x_{0})\neq 0$. Штавише, за нулу вишеструкости 1, конвергенција је барем квадратна (погледати Брзина конвергенције) у некој довољно малој околини нуле: број тачних цифара апроксимације се отприлике удвостручује са сваким додатним кораком. Више детаља се може наћи у одељку #Анализа § Notes испод.

Хаусхолдерови методи су слични, али имају виши ред за још бржу конвергенцију. Међутим, додатна израчунавања потребна за сваки корак могу успорити укупне перформансе у поређењу са Њутновим методом, посебно ако су $f$ или његови изводи рачунски скупи за евалуацију.

Историја

У старовавилонском периоду (19–16. век п. н. е.), страница квадрата познате површине могла се ефикасно апроксимирати, а претпоставља се да је то рађено коришћењем посебног случаја Њутновог метода, описаног алгебарски испод, итеративним побољшањем почетне процене; еквивалентан метод се може наћи у делу Метрика Херона Александријског (1–2. век н.е.), па се често назива Херонов метод. Најранија позната појава типа Њутн-Рафсоновог метода може се пратити до рада персијског астронома и математичара Џамшида ал Кашија (1380–1429). У својој значајној публикацији из 1427. године, Miftāḥ al-Ḥisāb (مفتاح الحساب, у преводу Кључ аритметике)), описао је варијанту овог итеративног метода. Џамшид ал Каши је користио метод за решавање x^P − N = 0 како би пронашао корене од N, метод који је био алгебарски еквивалентан Њутновом методу, а сличан метод је пронађен у делу Trigonometria Britannica, коју је објавио Хенри Бригс 1633. године. Рад Ал-Кашија заснован је на ранијим доприносима полихистора ал-Бирунија (973–1048) и математичара Шарафа ал-Дина ал-Тусија (1135–1213). Доприноси ал-Кашија остали су вековима у великој мери непознати западној научној заједници, све до рада Франсоа Вијета (1540–1603). Године 1600, Вијет је поново открио технику сличну ал-Кашијевој у контексту решавања скаларних полиномских једначина шестог степена. Најранији штампани опис методе први пут се појавио отприлике у раду Исака Њутна у De analysi per aequationes numero terminorum infinitas (написано 1669, објављено 1711. од стране Вилијама Џоунса) и у De metodis fluxionum et serierum infinitarum (написано 1671, преведено и објављено као Метод флуксија 1736. од стране Џона Колсона). Међутим, иако је Њутн дао основне идеје, његов метод се разликује од модерног метода датог горе. Он је метод примењивао само на полиноме, почињући са почетном проценом корена и издвајајући низ корекција грешке. Користио је сваку корекцију да препише полином у терминима преостале грешке, а затим је решавао за нову корекцију занемарујући чланове вишег степена. Није експлицитно повезао метод са изводима нити представио општу формулу. Њутн је овај метод примењивао и на нумеричке и на алгебарске проблеме, производећи Тејлорове редове у другом случају.

Њутн је можда извео свој метод из сличног, мање прецизног метода математичара Франсоа Вијета, међутим, та два метода нису иста. Суштина Вијетовог сопственог метода може се наћи у раду математичара Шарафа ал-Дина ал-Тусија.

Јапански математичар Секи Кова користио је облик Њутновог метода 1680-их за решавање једначина са једном променљивом, иако је веза са рачуном недостајала.

Њутнов метод је први пут објављен 1685. године у A Treatise of Algebra both Historical and Practical Џона Волиса. Године 1690, Џозеф Рафсон је објавио поједностављен опис у Analysis aequationum universalis. Рафсон је такође примењивао метод само на полиноме, али је избегао Њутнов досадан процес преписивања извлачећи сваку сукцесивну корекцију из оригиналног полинома. Ово му је омогућило да изведе поновно употребљив итеративни израз за сваки проблем. Коначно, 1740. године, Томас Симпсон је описао Њутнов метод као итеративни метод за решавање општих нелинеарних једначина користећи рачун, суштински дајући опис изнад. У истој публикацији, Симпсон такође даје генерализацију на системе од две једначине и напомиње да се Њутнов метод може користити за решавање проблема оптимизације постављањем градијента на нулу.

Артур Кејли је 1879. године у The Newton–Fourier imaginary problem први уочио потешкоће у генерализацији Њутновог метода на комплексне корене полинома степена већег од 2 и комплексне почетне вредности. Ово је отворило пут проучавању теорије итерација рационалних функција.

Практична разматрања

Њутнов метод је моћна техника — ако је извод функције у нули различит од нуле, онда је конвергенција најмање квадратна: како се метод приближава нули, разлика између нуле и апроксимације се квадрира (број тачних цифара се отприлике удвостручује) у сваком кораку. Међутим, постоје неке потешкоће са методом.

Потешкоће у израчунавању извода функције

Њутнов метод захтева да се извод може директно израчунати. Аналитички израз за извод можда није лако добити или може бити скуп за евалуацију. У таквим ситуацијама, може бити прикладно апроксимирати извод коришћењем нагиба праве кроз две оближње тачке на функцији. Коришћење ове апроксимације резултирало би нечим сличним методу сечице, чија је конвергенција спорија од Њутновог метода.

Неуспех метода да конвергира ка нули

Важно је прегледати доказ квадратне конвергенције Њутновог метода пре његове примене. Конкретно, треба прегледати претпоставке направљене у доказу. За ситуације где метод не успева да конвергира, то је зато што претпоставке направљене у овом доказу нису испуњене.

На пример, у неким случајевима, ако се први извод не понаша добро у околини одређене нуле, могуће је да Њутнов метод неће конвергирати без обзира на то где је иницијализација постављена. У неким случајевима, Њутнов метод се може стабилизовати коришћењем узастопне над-релаксације, или се брзина конвергенције може повећати коришћењем истог метода.

У робусној имплементацији Њутновог метода, уобичајено је поставити ограничења на број итерација, ограничити решење на интервал за који се зна да садржи нулу и комбиновати метод са робуснијим методом за проналажење нула.

Спора конвергенција за нуле вишеструкости веће од 1

Ако нула која се тражи има вишеструкост већу од један, стопа конвергенције је само линеарна (грешке се смањују за константан фактор у сваком кораку) осим ако се не предузму посебни кораци. Када постоје две или више нула које су близу једна другој, може бити потребно много итерација пре него што се итерације довољно приближе једној од њих да би квадратна конвергенција била очигледна. Међутим, ако је вишеструкост m нуле позната, следећи модификовани алгоритам чува квадратну стопу конвергенције:

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

Ово је еквивалентно коришћењу узастопне над-релаксације. С друге стране, ако вишеструкост m нуле није позната, могуће је проценити m након извођења једне или две итерације, а затим користити ту вредност за повећање стопе конвергенције. Ако је вишеструкост m нуле коначна, онда ће g(x) = f(x)/f′(x) имати нулу на истом месту са вишеструкошћу 1. Примена Њутновог метода за проналажење нуле g(x) враћа квадратну конвергенцију у многим случајевима, иако генерално укључује други извод f(x). У посебно једноставном случају, ако је f(x) = x^m, онда је g(x) = x/m и Њутнов метод проналази нулу у једној итерацији са

$$x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}=x_{n}-{\frac {\;{\frac {x_{n}}{m}}\;}{\frac {1}{m}}}=0\,.$$

Спора конвергенција

Функција f(x) = x² има нулу у 0. Пошто је f непрекидно диференцијабилна у својој нули, теорија гарантује да ће Њутнов метод иницијализован довољно близу нуле конвергирати. Међутим, пошто је извод f ′ нула у нули, квадратна конвергенција није загарантована теоријом. У овом конкретном примеру, Њутнова итерација је дата са

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

Из овога је видљиво да би Њутнов метод могао бити иницијализован било где и конвергирати ка нули, али само линеарном брзином. Ако се иницијализује на 1, биле би потребне десетине итерација пре него што се постигне тачност од десет цифара.

Функција f(x) = x + x^4/3 такође има нулу у 0, где је непрекидно диференцијабилна. Иако први извод f ′ није нула у нули, други извод f ′′ тамо не постоји, тако да се квадратна конвергенција не може гарантовати. У ствари, Њутнова итерација је дата са

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}={\frac {x_{n}^{4/3}}{3+4x_{n}^{1/3}}}\approx x_{n}\cdot {\frac {x_{n}^{1/3}}{3}}.$

Из овога се може видети да је брзина конвергенције суперлинеарна, али субквадратна. Ово се може видети у следећим табелама, од којих лева показује Њутнов метод примењен на горњу функцију f(x) = x + x^4/3, а десна показује Њутнов метод примењен на f(x) = x + x². Квадратна конвергенција у итерацији приказана десно илустрована је редовима величине у растојању од итерације до праве нуле (0,1,2,3,5,10,20,39,...), који се приближно удвостручују од реда до реда. Док је конвергенција лево суперлинеарна, ред величине се множи само са око 4/3 од реда до реда (0,1,2,4,5,7,10,13,...).

xn	x + x4/3 n		xn	x + x2 n
1	2		1	2
1.4286 × 10−1	2.1754 × 10−1		3.3333 × 10−1	4.4444 × 10−1
1.4669 × 10−2	1.8260 × 10−2		6.6666 × 10−2	7.1111 × 10−2
9.0241 × 10−4	9.8961 × 10−4		3.9216 × 10−3	3.9369 × 10−3
2.5750 × 10−5	2.6511 × 10−5		1.5259 × 10−5	1.5259 × 10−5
2.4386 × 10−7	2.4539 × 10−7		2.3283 × 10−10	2.3283 × 10−10
5.0366 × 10−10	5.0406 × 10−10		5.4210 × 10−20	5.4210 × 10−20
1.3344 × 10−13	1.3344 × 10−13		2.9387 × 10−39	2.9387 × 10−39

Брзина конвергенције се разликује од броја итерација потребних да се достигне дата тачност. На пример, функција f(x) = x²⁰ − 1 има нулу у 1. Пошто је f ′(1) ≠ 0 и f је глатка, познато је да ће свака Њутнова итерација која конвергира ка 1 конвергирати квадратно. Међутим, ако се иницијализује на 0.5, првих неколико итерација Њутновог метода су приближно 26214, 24904, 23658, 22476, споро опадајући, при чему је тек 200. итерација 1.0371. Следеће итерације су 1.0103, 1.00093, 1.0000082 и 1.00000000065, што илуструје квадратну конвергенцију. Ово наглашава да квадратна конвергенција Њутнове итерације не значи да је потребно само неколико итерација; ово важи само када је низ итерација довољно близу нуле.

Конвергенција зависи од иницијализације

Функција f(x) = x(1 + x²)^−1/2 има нулу у 0. Њутнова итерација је дата са

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

Из овога се може видети да постоје три могућа феномена за Њутнову итерацију. Ако се иницијализује стриктно између ±1, Њутнова итерација ће конвергирати (супер-)квадратно ка 0; ако се иницијализује тачно на 1 или −1, Њутнова итерација ће бесконачно осциловати између ±1; ако се иницијализује било где другде, Њутнова итерација ће дивергирати. Иста ова трихотомија се јавља за f(x) = arctan x.

У случајевима када функција има више нула, може бити тешко контролисати, путем избора иницијализације, коју нулу (ако иједну) Њутнов метод идентификује. На пример, функција f(x) = x(x² − 1)(x − 3)e^{−(x − 1)2/2} има нуле у −1, 0, 1 и 3. Ако се иницијализује на −1.488, Њутнова итерација конвергира ка 0; ако се иницијализује на −1.487, дивергира ка ∞; ако се иницијализује на −1.486, конвергира ка −1; ако се иницијализује на −1.485, дивергира ка −∞; ако се иницијализује на −1.4843, конвергира ка 3; ако се иницијализује на −1.484, конвергира ка 1. Оваква суптилна зависност од иницијализације није неуобичајена; често се проучава у комплексној равни у облику Њутновог фрактала.

Дивергенција чак и када је иницијализација близу нуле

Размотримо проблем проналажења нуле функције f(x) = x^1/3. Њутнова итерација је

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

Осим ако се Њутнов метод не иницијализује тачно у нули 0, види се да низ итерација неће конвергирати. На пример, чак и ако се иницијализује на разумно тачној претпоставци од 0.001, првих неколико итерација су −0.002, 0.004, −0.008, 0.016, достижући 1048.58, −2097.15, ... до 20. итерације. Овај неуспех конвергенције није у супротности са аналитичком теоријом, пошто у овом случају f није диференцијабилна у својој нули.

У горњем примеру, неуспех конвергенције се огледа у неуспеху f(x_n) да се приближи нули како се n повећава, као и у чињеници да се узастопне итерације све више удаљавају једна од друге. Међутим, функција f(x) = x^1/3e^−x2 такође има нулу у 0. Њутнова итерација је дата са

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

У овом примеру, где f опет није диференцијабилна у нули, свака Њутнова итерација која не почиње тачно у нули ће дивергирати, али са оба x_{n + 1} − x_n и f(x_n) која конвергирају ка нули. Ово се види у следећој табели која приказује итерације са иницијализацијом 1:

xn	f(xn)
1	0.36788
1.6	9.0416 × 10−2
1.9342	2.9556 × 10−2
2.2048	1.0076 × 10−2
2.4396	3.5015 × 10−3
2.6505	1.2307 × 10−3
2.8437	4.3578 × 10−4
3.0232	1.5513 × 10−4

Иако конвергенција x_{n + 1} − x_n у овом случају није веома брза, може се доказати из итерационе формуле. Овај пример истиче могућност да критеријум за заустављање Њутновог метода заснован само на малој вредности x_{n + 1} − x_n и f(x_n) може погрешно идентификовати нулу.

Осцилаторно понашање

Тангенте функције x³ − 2x + 2 у 0 и 1 секу x-осу у 1 и 0 респективно, илуструјући зашто Њутнов метод осцилује између ових вредности за неке почетне тачке.

Лако је пронаћи ситуације за које Њутнов метод бескрајно осцилује између две различите вредности. На пример, да би Њутнов метод примењен на функцију f осциловао између 0 и 1, потребно је само да тангента на f у 0 сече x-осу у 1 и да тангента на f у 1 сече x-осу у 0. Ово је случај, на пример, ако је f(x) = x³ − 2x + 2. За ову функцију, чак је случај да ће Њутнова итерација иницијализована довољно близу 0 или 1 асимптотски осциловати између ових вредности. На пример, Њутнов метод иницијализован на 0.99 даје итерације 0.99, −0.06317, 1.00628, 0.03651, 1.00196, 0.01162, 1.00020, 0.00120, 1.000002, и тако даље. Ово понашање је присутно упркос постојању нуле функције f приближно једнаке −1.76929.

Недефинисаност Њутновог метода

У неким случајевима, није чак ни могуће извести Њутнову итерацију. На пример, ако је f(x) = x² − 1, онда је Њутнова итерација дефинисана са

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

Дакле, Њутнов метод се не може иницијализовати у 0, пошто би то учинило x₁ недефинисаним. Геометријски, то је зато што је тангента на f у 0 хоризонтална (тј. f ′(0) = 0), и никада не сече x-осу.

Чак и ако је иницијализација изабрана тако да Њутнова итерација може почети, исти феномен може блокирати да се итерација настави неограничено.

Ако f има некомплетан домен, могуће је да Њутнов метод пошаље итерације изван домена, тако да је немогуће наставити итерацију. На пример, функција природног логаритма f(x) = ln x има нулу у 1, и дефинисана је само за позитивно x. Њутнова итерација у овом случају је дата са

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

Дакле, ако се итерација иницијализује на e, следећа итерација је 0; ако се итерација иницијализује на вредности већој од e, онда је следећа итерација негативна. У оба случаја, метод се не може наставити.

Анализа

Претпоставимо да функција f има нулу у α, тј., f(α) = 0, и f је диференцијабилна у околини од α.

Ако је f непрекидно диференцијабилна и њен извод је различит од нуле у α, онда постоји околина од α таква да за све почетне вредности x₀ у тој околини, низ (x_n) ће конвергирати ка α.

Ако је f непрекидно диференцијабилна, њен извод је различит од нуле у α, и има други извод у α, онда је конвергенција квадратна или бржа. Ако други извод није 0 у α онда је конвергенција само квадратна. Ако трећи извод постоји и ограничен је у околини од α, онда:

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

где

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

Ако је извод 0 у α, онда је конвергенција обично само линеарна. Конкретно, ако је f двапут непрекидно диференцијабилна, f′(α) = 0 и f″(α) ≠ 0, онда постоји околина од α таква да, за све почетне вредности x₀ у тој околини, низ итерација конвергира линеарно, са брзином 1/2. Алтернативно, ако је f′(α) = 0 и f′(x) ≠ 0 за x ≠ α, x у околини U од α, где је α нула вишеструкости r, и ако је f ∈ C^r(U), онда постоји околина од α таква да, за све почетне вредности x₀ у тој околини, низ итерација конвергира линеарно.

Међутим, чак ни линеарна конвергенција није загарантована у патолошким ситуацијама.

У пракси, ови резултати су локални, и околина конвергенције није позната унапред. Али постоје и неки резултати о глобалној конвергенцији: на пример, дата је десна околина U₊ од α, ако је f двапут диференцијабилна у U₊ и ако је f′ ≠ 0, f · f″ > 0 у U₊, онда, за свако x₀ у U₊ низ x_k је монотоно опадајући ка α.

Доказ квадратне конвергенције за Њутнов итеративни метод

Према Тејлоровој теореми, свака функција f(x) која има непрекидан други извод може се представити развојем око тачке која је близу нуле функције f(x). Претпоставимо да је ова нула α. Онда је развој f(α) око x_n следећи:

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

где је Лагранжов облик остатка Тејлоровог реда

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

где је ξ_n између x_n и α.

Пошто је α нула, ово постаје:

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

Дељењем једначине са f′(x_n) и преуређивањем добија се

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

Подсећајући се да је x_{n + 1} дефинисано са

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

налази се да $$\underbrace {\alpha -x_{n+1}} _{\varepsilon _{n+1}}={\frac {-f''(\xi _{n})}{2f'(x_{n})}}{(\,\underbrace {\alpha -x_{n}} _{\varepsilon _{n}}\,)}^{2}\,.$$

То јест,

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

Узимањем апсолутне вредности обе стране добија се

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

Ова једначина показује да је ред конвергенције најмање квадратан ако су задовољени следећи услови:

1. f′(x) ≠ 0; за свако x ∈ I, где је I интервал [α − |ε₀|, α + |ε₀|];
2. f″(x) је непрекидно, за свако x ∈ I;
3. M |ε₀| < 1

где је M дато са

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

Ако ови услови важе,

$$\vert \varepsilon _{n+1}\vert \leq M\cdot \varepsilon _{n}^{2}\,.$$

Фуријеови услови

Претпоставимо да је f(x) конкавна функција на интервалу, која је строго растућа. Ако је негативна на левом крају и позитивна на десном крају, теорема о средњој вредности гарантује да постоји нула ζ функције f негде у интервалу. Из геометријских принципа, може се видети да је Њутнова итерација x_i која почиње на левом крају монотоно растућа и конвергентна, неопходно ка ζ.

Жозеф Фурије је увео модификацију Њутновог метода која почиње на десном крају:

$y_{i+1}=y_{i}-{\frac {f(y_{i})}{f'(x_{i})}}.$

Овај низ је монотоно опадајући и конвергентан. Преласком на лимес у овој дефиницији, може се видети да лимес y_i такође мора бити нула ζ.

Дакле, у случају конкавне растуће функције са нулом, иницијализација је у великој мери ирелевантна. Њутнова итерација која почиње било где лево од нуле ће конвергирати, као и Фуријеова модификована Њутнова итерација која почиње било где десно од нуле. Тачност у било ком кораку итерације може се директно одредити из разлике између локације итерације са леве стране и локације итерације са десне стране. Ако је f двапут непрекидно диференцијабилна, може се доказати коришћењем Тејлорове теореме да

$\lim _{i\to \infty }{\frac {y_{i+1}-x_{i+1}}{(y_{i}-x_{i})^{2}}}=-{\frac {1}{2}}{\frac {f''(\zeta )}{f'(\zeta )}},$

показујући да ова разлика у локацијама конвергира квадратно ка нули.

Све наведено се може проширити на системе једначина у више променљивих, иако су у том контексту релевантни појмови монотоности и конкавности суптилнији за формулисање. У случају појединачних једначина у једној променљивој, горе наведена монотона конвергенција Њутновог метода се такође може генерализовати да замени конкавност позитивношћу или негативношћу на произвољном изводу вишег реда од f. Међутим, у овој генерализацији, Њутнова итерација је модификована тако да се заснива на Тејлоровим полиномима уместо на тангенти. У случају конкавности, ова модификација се поклапа са стандардним Њутновим методом.

Грешка за n>1 променљивих

Ако тражимо нулу једне функције $f:\mathbf {R} ^{n}\to \mathbf {R}$ онда је грешка $\epsilon _{n}=x_{n}-\alpha$ вектор чије компоненте задовољавају $\epsilon _{k}^{(n+1)}={\frac {1}{2}}(\epsilon ^{(n)})^{T}Q_{k}\epsilon ^{(n)}+O(\|\epsilon ^{(n)}\|^{3})$ где је $Q_{k}$ квадратна форма: $(Q_{k})_{i,j}=\sum _{\ell }((D^{2}f)^{-1})_{i,\ell }{\frac {\partial ^{3}f}{\partial x_{j}\partial x_{k}\partial x_{\ell }}}$ евалуирана у нули $\alpha$ (где је $D^{2}f$ Хесијан матрица другог извода).

Примери

Коришћење Њутновог метода за израчунавање квадратних корена

Њутнов метод је један од многих познатих метода за израчунавање квадратних корена. За дати позитиван број a, проблем проналажења броја x таквог да је x² = a еквивалентан је проналажењу нуле функције f(x) = x² − a. Њутнова итерација дефинисана овом функцијом дата је са

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

Ово се поклапа са "Вавилонским" методом проналажења квадратних корена, који се састоји од замене апроксимативног корена x_n аритметичком средином x_n и ^a⁄_xn. Извођењем ове итерације, могуће је израчунати квадратни корен до било које жељене тачности користећи само основне аритметичке операције.

Следеће три табеле приказују примере резултата овог израчунавања за проналажење квадратног корена броја 612, са итерацијом иницијализованом на вредностима 1, 10 и −20. Сваки ред у колони "x_n" добија се применом претходне формуле на унос изнад њега, на пример

$306.5={\frac {1}{2}}\left(1+{\frac {612}{1}}\right).$

xn	f(xn)		xn	f(xn)		xn	f(xn)
1	−611		10	−512		−20	−212
306.5	9.3330 × 104		35.6	655.36		−25.3	28.09
154.2483686786	2.3180 × 104		26.3955056180	84.722		−24.7448616601	0.30818
79.1079978644	5.6461 × 103		24.7906354925	2.5756		−24.7386345374	3.8777 × 10−5
43.4221286822	1.2735 × 103		24.7386882941	2.6985 × 10−3		−24.7386337537	6.1424 × 10−13
28.7581624288	215.03		24.7386337538	2.9746 × 10−9
25.0195385369	13.977
24.7402106712	7.8024 × 10−2
24.7386338040	2.4865 × 10−6
24.7386337537	2.5256 × 10−15

Тачне цифре су подвучене. Види се да се са само неколико итерација може добити решење тачно на много децималних места. Прва табела показује да је то тачно чак и ако је Њутнова итерација иницијализована врло нетачном претпоставком од 1.

Приликом израчунавања било ког ненултог квадратног корена, први извод f мора бити различит од нуле у нули, и f је глатка функција. Дакле, чак и пре било каквог израчунавања, познато је да свака конвергентна Њутнова итерација има квадратну брзину конвергенције. Ово се у горњим табелама огледа у чињеници да када се Њутнова итерација приближи нули, број тачних цифара се приближно удвостручује са сваком итерацијом.

Решење cos(x) = x³ помоћу Њутновог метода

Размотримо проблем проналажења позитивног броја x за који важи cos x = x³. Ово можемо преформулисати као проналажење нуле функције f(x) = cos(x) − x³. Имамо f′(x) = −sin(x) − 3x². Пошто је cos(x) ≤ 1 за свако x и x³ > 1 за x > 1, знамо да наше решење лежи између 0 и 1.

Почетна вредност 0 ће довести до недефинисаног резултата, што илуструје важност коришћења почетне тачке близу решења. На пример, са почетном претпоставком x₀ = 0.5, низ дат Њутновим методом је: $${\begin{matrix}x_{1}&amp;=&amp;x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&amp;=&amp;0.5-{\dfrac {\cos 0.5-0.5^{3}}{-\sin 0.5-3\times 0.5^{2}}}&amp;=&amp;1.112\,141\,637\,097\dots \\x_{2}&amp;=&amp;x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&amp;=&amp;\vdots &amp;=&amp;{\underline {0.}}909\,672\,693\,736\dots \\x_{3}&amp;=&amp;\vdots &amp;=&amp;\vdots &amp;=&amp;{\underline {0.86}}7\,263\,818\,209\dots \\x_{4}&amp;=&amp;\vdots &amp;=&amp;\vdots &amp;=&amp;{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&amp;=&amp;\vdots &amp;=&amp;\vdots &amp;=&amp;{\underline {0.865\,474\,033\,1}}11\dots \\x_{6}&amp;=&amp;\vdots &amp;=&amp;\vdots &amp;=&amp;{\underline {0.865\,474\,033\,102}}\dots \end{matrix}}$$

Тачне цифре су подвучене у горњем примеру. Конкретно, x₆ је тачан на 12 децималних места. Видимо да се број тачних цифара након децималне запете повећава са 2 (за x₃) на 5 и 10, што илуструје квадратну конвергенцију.

Вишедимензионалне формулације

Системи једначина

k променљивих, k функција

Њутнов метод се може користити и за решавање система од k једначина, што се своди на проналажење (симултаних) нула k непрекидно диференцијабилних функција <math>f:\R^k\to \R.</math> Ово је еквивалентно проналажењу нула једне векторске функције <math>F:\R^k\to \R^k.</math> У формулацији датој горе, скалари x_n се замењују векторима x_n, и уместо дељења функције f(x_n) њеним изводом f′(x_n), потребно је лево помножити функцију F(x_n) инверзом њене k × k Јакобијеве матрице J_F(x_n). Ово резултира изразом

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

или, решавањем система линеарних једначина

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

за непознату x_{n + 1} − x_n.

k променљивих, m једначина, са m > k

k-димензионална варијанта Њутновог метода се може користити за решавање система од више од k (нелинеарних) једначина ако алгоритам користи генерализовани инверз не-квадратне Јакобијеве матрице J⁺ = (J^TJ)⁻¹J^T уместо инверза од J. Ако нелинеарни систем нема решење, метод покушава да пронађе решење у смислу нелинеарних најмањих квадрата. Погледати Гаус-Њутнов алгоритам за више информација.

Пример

На пример, следећи скуп једначина треба решити за вектор тачака $[x_{1},x_{2}],$ за дати вектор познатих вредности $[2,3]~.$.

${\begin{array}{lcr}5\ x_{1}^{2}+x_{1}\ x_{2}^{2}+\sin ^{2}(2\ x_{2})&=\quad 2\\e^{2\ x_{1}-x_{2}}+4\ x_{2}&=\quad 3\end{array}}$

вектор функције, $F(X_{k}),$ и Јакобијева матрица, $J(X_{k})$ за итерацију k, и вектор познатих вредности, $Y,$; су дефинисани испод. ${\begin{aligned}~&F(X_{k})~=~{\begin{bmatrix}{\begin{aligned}~&f_{1}(X_{k})\\~&f_{2}(X_{k})\end{aligned}}\end{bmatrix}}~=~{\begin{bmatrix}{\begin{aligned}~&5\ x_{1}^{2}+x_{1}\ x_{2}^{2}+\sin ^{2}(2\ x_{2})\\~&e^{2\ x_{1}-x_{2}}+4\ x_{2}\end{aligned}}\end{bmatrix}}_{k}\\~&J(X_{k})={\begin{bmatrix}~{\frac {\ \partial {f_{1}(X)}\ }{\partial {x_{1}}}}\ ,&~{\frac {\ \partial {f_{1}(X)}\ }{\partial {x_{2}}}}~\\~{\frac {\ \partial {f_{2}(X)}\ }{\partial {x_{1}}}}\ ,&~{\frac {\ \partial {f_{2}(X)}\ }{\partial {x_{2}}}}~\end{bmatrix}}_{k}~=~{\begin{bmatrix}{\begin{aligned}~&10\ x_{1}+x_{2}^{2}\ ,&&2\ x_{1}\ x_{2}+4\ \sin(2\ x_{2})\ \cos(2\ x_{2})\\~&2\ e^{2\ x_{1}-x_{2}}\ ,&&-e^{2\ x_{1}-x_{2}}+4\end{aligned}}\end{bmatrix}}_{k}\\~&Y={\begin{bmatrix}~2~\\~3~\end{bmatrix}}\end{aligned}}$

Приметите да је $F(X_{k})$; могло бити преписано да апсорбује $Y,$ и тиме елиминише Y из једначина. Једначине које треба решити за сваку итерацију су

${\begin{aligned}{\begin{bmatrix}{\begin{aligned}~&~10\ x_{1}+x_{2}^{2}\ ,&&2x_{1}x_{2}+4\ \sin(2\ x_{2})\ \cos(2\ x_{2})~\\~&~2\ e^{2\ x_{1}-x_{2}}\ ,&&-e^{2\ x_{1}-x_{2}}+4~\end{aligned}}\end{bmatrix}}_{k}{\begin{bmatrix}~c_{1}~\\~c_{2}~\end{bmatrix}}_{k+1}={\begin{bmatrix}~5\ x_{1}^{2}+x_{1}\ x_{2}^{2}+\sin ^{2}(2\ x_{2})-2~\\~e^{2\ x_{1}-x_{2}}+4\ x_{2}-3~\end{bmatrix}}_{k}\end{aligned}}$

и

$X_{k+1}~=~X_{k}-C_{k+1}$

Итерације треба понављати док ${\Bigg [}\sum _{i=1}^{i=2}{\Bigl |}f(x_{i})_{k}-(y_{i})_{k}{\Bigr |}{\Bigg ]}<E\ ,$ вредност $E\$ довољно мала да задовољи захтеве апликације.

Ако је вектор $X_{0}$ иницијално изабран да буде ${\begin{bmatrix}~1~&~1~\end{bmatrix}}\ ,$ то јест, $x_{1}=1\ ,$ и $x_{2}=1\ ,$ и $E$ је изабрано да буде 1.10⁻³, онда пример конвергира након четири итерације до вредности $X_{4}=\left[~0.567297,\ -0.309442~\right]~.$

Итерације

Следеће итерације су направљене током решавања.

Конвергентни низ итерација

Корак	Променљива	Вредност
0	x =	${\begin{bmatrix}\ 1\ ,&1\end{bmatrix}}$
	f(x) =	${\begin{bmatrix}\ 6.82682\ ,&6.71828\ \end{bmatrix}}$
1	J =	${\begin{bmatrix}\ 11~,&\quad 0.486395\\\ 5.43656\ ,&1.28172\end{bmatrix}}$
	c =	${\begin{bmatrix}\ 0.382211\ ,&1.27982\ \end{bmatrix}}$
	x =	${\begin{bmatrix}\ 0.617789\ ,&-0.279818\ \end{bmatrix}}$
	f(x) =	${\begin{bmatrix}\ 2.23852\ ,&3.43195\ \end{bmatrix}}$
2	J =	${\begin{bmatrix}\ 6.25618\ ,&-2.1453\\\ 9.10244\ ,&\quad -0.551218\end{bmatrix}}$
	c =	${\begin{bmatrix}0.0494549\ ,&0.0330411\ \end{bmatrix}}$
	x =	${\begin{bmatrix}\ 0.568334\ ,&-0.312859\ \end{bmatrix}}$
	f(x) =	${\begin{bmatrix}\ 2.01366\ ,&3.00966\ \end{bmatrix}}$
3	J =	${\begin{bmatrix}\ 5.78122\ ,&-2.25449\\\ 8.52219\ ,&\quad -0.261095\ \end{bmatrix}}$
	c =	${\begin{bmatrix}0.00102862\ ,&-0.00342339\ \end{bmatrix}}$
	x =	${\begin{bmatrix}\ 0.567305\ ,&-0.309435\ \end{bmatrix}}$
	f(x) =	${\begin{bmatrix}\ 2.00003\ ,&3.00006\ \end{bmatrix}}$
4	J =	${\begin{bmatrix}\ 5.7688~,&~-2.24118\\\ 8.47561\ ,&\quad -0.237805\end{bmatrix}}\$
	c =	${\begin{bmatrix}\ 7.73132\!\times \!10^{-6}~,&~6.93265\!\times \!10^{-6}\ \end{bmatrix}}$
	x =	${\begin{bmatrix}\ 0.567297\ ,&-0.309442\ \end{bmatrix}}$
	f(x) =	${\begin{bmatrix}~2\ ,~&~3~\end{bmatrix}}$

Комплексне функције

Главни чланак: Њутнов фрактал

Басени привлачења за x⁵ − 1 = 0; тамнија боја значи више итерација за конвергенцију.

Када се ради са комплексним функцијама, Њутнов метод се може директно применити за проналажење њихових нула. Свака нула има басен привлачења у комплексној равни, скуп свих почетних вредности које узрокују да метод конвергира ка тој одређеној нули. Ови скупови се могу мапирати као на приказаној слици. За многе комплексне функције, границе басена привлачења су фрактали.

У неким случајевима постоје региони у комплексној равни који нису ни у једном од ових басена привлачења, што значи да итерације не конвергирају. На пример, ако се користи реалан почетни услов за тражење корена x² + 1, све наредне итерације ће бити реални бројеви и стога итерације не могу конвергирати ни ка једном корену, пошто су оба корена нереална. У овом случају скоро сви реални почетни услови воде ка хаотичном понашању, док неки почетни услови итерирају или ка бесконачности или ка понављајућим циклусима било које коначне дужине.

Керт Макмулен је показао да ће за било који могући чисто итеративни алгоритам сличан Њутновом методу, алгоритам дивергирати на неким отвореним регионима комплексне равни када се примени на неки полином степена 4 или вишег. Међутим, Макмулен је дао генерално конвергентан алгоритам за полиноме степена 3. Такође, за било који полином, Хабард, Шлајхер и Садерленд су дали метод за одабир скупа почетних тачака тако да ће Њутнов метод сигурно конвергирати барем у једној од њих.

У Банаховом простору

Још једна генерализација је Њутнов метод за проналажење нуле функционала F дефинисаног у Банаховом простору. У овом случају формулација је

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

где је F′(X_n) Фрешеов извод израчунат у X_n. Потребно је да Фрешеов извод буде ограничено инвертибилан у сваком X_n да би метод био применљив. Услов за постојање и конвергенцију ка нули дат је Њутн-Канторовичевом теоремом.

Неш-Мозерова итерација

За више информација погледајте: Неш-Мозерова теорема

Током 1950-их, Џон Неш је развио верзију Њутновог метода коју је применио на проблем конструкције изометричних улагања општих Риманових многострукости у Еуклидски простор. Проблем „губитка извода“, присутан у овом контексту, учинио је стандардну Њутнову итерацију неприменљивом, јер се није могла наставити неодређено (а камоли конвергирати). Нешово решење је укључивало увођење оператора изглађивања у итерацију. Успео је да докаже конвергенцију свог изглађеног Њутновог метода, у сврху доказивања теореме о имплицитној функцији за изометрична улагања. Током 1960-их, Јирген Мозер је показао да су Нешове методе довољно флексибилне да се примене на проблеме изван изометричног улагања, посебно у небеској механици. Од тада, велики број математичара, укључујући Михаила Громова и Ричарда Хамилтона, пронашли су генерализоване апстрактне верзије Неш-Мозерове теорије. У Хамилтоновој формулацији, Неш-Мозерова теорема представља генерализацију Њутновог метода у Банаховом простору која се одвија у одређеним Фрешеовим просторима.

Модификације

Квази-Њутнови методи

Када је Јакобијан недоступан или прескуп за израчунавање у свакој итерацији, може се користити квази-Њутнов метод.

Чебишевљев метод трећег реда

Главни чланак: Чебишевљева итерација

Пошто Тејлорови развоји вишег реда нуде тачније локалне апроксимације функције f, разумно је питати се зашто се Њутнов метод ослања само на Тејлорову апроксимацију другог реда. У 19. веку, руски математичар Пафнутиј Чебишев је истраживао ову идеју развијајући варијанту Њутновог метода која је користила кубне апроксимације.

Над p-адским бројевима

У p-адској анализи, стандардни метод за показивање да полиномска једначина у једној променљивој има p-адски корен је Хенселова лема, која користи рекурзију из Њутновог метода на p-адским бројевима. Због стабилнијег понашања сабирања и множења у p-адским бројевима у поређењу са реалним бројевима (конкретно, јединична кугла у p-адским бројевима је прстен), конвергенција у Хенселовој леми може се гарантовати под много једноставнијим хипотезама него у класичном Њутновом методу на реалној правој.

q-аналог

Њутнов метод се може генерализовати са q-аналогом уобичајеног извода.

Модификовани Њутнови методи

Мелијева процедура

Нелинеарна једначина генерално има више решења. Али ако почетна вредност није одговарајућа, Њутнов метод можда неће конвергирати ка жељеном решењу или може конвергирати ка истом решењу које је раније пронађено. Када смо већ пронашли N решења једначине <math>f(x)=0</math>, онда се следећа нула може пронаћи применом Њутновог метода на следећу једначину:

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

Овај метод се примењује за добијање нула Беселове функције друге врсте.

Хиранова модификована Њутнова метода

Хиранова модификована Њутнова метода је модификација која чува конвергенцију Њутновог метода и избегава нестабилност. Развијена је за решавање комплексних полинома.

Интервални Њутнов метод

Комбиновање Њутновог метода са интервалном аритметиком је веома корисно у неким контекстима. Ово пружа критеријум за заустављање који је поузданији од уобичајених (који су мала вредност функције или мала варијација променљиве између узастопних итерација). Такође, ово може детектовати случајеве где Њутнов метод теоретски конвергира, али нумерички дивергира због недовољне прецизности покретног зареза (ово је типичан случај за полиноме великог степена, где врло мала промена променљиве може драматично променити вредност функције; видети Вилкинсонов полином).

Размотримо f → Шаблон:Mathcal¹(X), где је X реалан интервал, и претпоставимо да имамо интервално проширење F′ од f′, што значи да F′ узима као улаз интервал Y ⊆ X и даје као излаз интервал F′(Y) такав да:

$${\begin{aligned}F'([y,y])&=\{f'(y)\}\\[5pt]F'(Y)&\supseteq \{f'(y)\mid y\in Y\}.\end{aligned}}$$

Такође претпостављамо да 0 ∉ F′(X), па f има највише једну нулу у X. Тада дефинишемо интервални Њутнов оператор са:

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

где је m ∈ Y. Приметите да хипотеза о F′ имплицира да је N(Y) добро дефинисан и да је интервал (видети интервална аритметика за више детаља о интервалним операцијама). Ово природно води до следећег низа:

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

Теорема о средњој вредности осигурава да ако постоји нула функције f у X_k, онда је она такође у X_{k + 1}. Штавише, хипотеза о F′ осигурава да је X_{k + 1} највише половина величине од X_k када је m средина од Y, тако да овај низ конвергира ка [x*, x*], где је x* нула функције f у X.

Ако F′(X) стриктно садржи 0, употреба проширеног интервалног дељења производи унију два интервала за N(X); вишеструке нуле се стога аутоматски одвајају и ограничавају.

Примене

Проблеми минимизације и максимизације

Главни чланак: Њутнов метод у оптимизацији

Њутнов метод се може користити за проналажење минимума или максимума функције f(x). Извод је нула у минимуму или максимуму, тако да се локални минимуми и максимуми могу пронаћи применом Њутновог метода на извод. Итерација постаје:

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

Мултипликативни инверзи бројева и степених редова

Важна примена је Њутн-Рафсонова подела, која се може користити за брзо проналажење реципрочне вредности броја a, користећи само множење и одузимање, то јест броја x таквог да је 1/x = a. Можемо то преформулисати као проналажење нуле функције f(x) = 1/x − a. Имамо f′(x) = −1/x².

Њутнова итерација је

$$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-ax_{n}).$$

Дакле, Њутнова итерација захтева само два множења и једно одузимање.

Овај метод је такође веома ефикасан за израчунавање мултипликативног инверза степеног реда.

Решавање трансцендентних једначина

Многе трансцендентне једначине се могу решити до произвољне прецизности коришћењем Њутновог метода. На пример, проналажење кумулативне функције расподеле вероватноће, као што је нормална расподела, да би се уклопила у познату вероватноћу, генерално укључује интегралне функције без познатих начина за решавање у затвореном облику. Међутим, израчунавање извода потребних за њихово нумеричко решавање Њутновим методом је генерално познато, што омогућава нумеричка решења. За пример, погледајте нумеричко решење инверзне кумулативне функције нормалне расподеле.

Нумеричка верификација за решења нелинеарних једначина

Нумеричка верификација за решења нелинеарних једначина је успостављена вишеструким коришћењем Њутновог метода и формирањем скупа кандидатских решења.

Код

Следи пример могуће имплементације Њутновог метода у програмском језику Пајтон (верзија 3.x) за проналажење нуле функције f која има извод f_prime.

Почетна претпоставка ће бити x₀ = 1 а функција ће бити f(x) = x² − 2 тако да је f′(x) = 2x.

Свака нова итерација Њутновог метода биће означена са x1. Током израчунавања провераваћемо да ли именилац (yprime) постаје премали (мањи од epsilon),, што би био случај ако је f′(x_n) ≈ 0, пошто би у супротном могла бити уведена велика грешка.

def f(x):             
	return x**2 - 2   # f(x) = x^2 - 2

def f_prime(x):
	return 2*x        # f'(x) = 2x

def newtons_method(x0, f, f_prime, tolerance, epsilon, max_iterations):
    """Њутнов метод

    Args:
      x0:              Почетна претпоставка
      f:               Функција чију нулу покушавамо да пронађемо
      f_prime:         Извод функције
      tolerance:       Заустави се када се итерације промене за мање од овога
      epsilon:         Не делити бројем мањим од овога
      max_iterations:  Максималан број итерација за израчунавање
    """
    for _ in range(max_iterations):
        y = f(x0)
        yprime = f_prime(x0)

        if abs(yprime) < epsilon:         # Прекини ако је именилац премали
            break
        x1 = x0 - y / yprime             # Изврши Њутново израчунавање

        if abs(x1 - x0) <= tolerance:    # Заустави се када је резултат унутар жељене толеранције
            return x1                    # x1 је решење унутар толеранције и максималног броја итерација

        x0 = x1                          # Ажурирај x0 да би се процес поново покренуо

    return None                          # Њутнов метод није конвергирао

Види још

• Аиткенов делта-квадрат процес
• Метода половљења интервала
• Ојлеров метод
• Брзи инверзни квадратни корен
• Фишеров алгоритам бодовања
• Градијентни спуст
• Целобројни квадратни корен
• Канторовичева теорема
• Лагеров метод
• Методе за израчунавање квадратног корена
• Њутнов метод у оптимизацији
• Ричардсонова екстраполација
• Алгоритми за налажење корена
• Метода секанте
• Штефенсенова метода
• Метода субградијента

Литература

• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). „Chapter 9. Root Finding and Nonlinear Sets of Equations Importance Sampling”. Numerical Recipes: The Art of Scientific Computing (3rd изд.). New York: Cambridge Univ. Press. ISBN 978-0-521-88068-8. 
• Gil, Amparo; Segura, Javier; Temme, Nico (2007). Numerical methods for special functions. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-634-4. 
• Süli, Endre; Mayers, David (2003). An Introduction to Numerical Analysis. Cambridge University Press. ISBN 0-521-00794-1. 

Спољашње везе

• Hazewinkel Michiel, ур. (2001). „Newton method”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Weisstein, Eric W. „Newton's Method”. MathWorld. 
• Newton's method, Citizendium.
• „Mathews, J., The Accelerated and Modified Newton Methods, Course notes.”. Архивирано из оригинала 24. 05. 2019. г. 
• Wu, X., Roots of Equations, Course notes.