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

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

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

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

Опис

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

alt=Илустрација Њутновог метода|thumb|right|upright=1.4| је боља апроксимација од за нулу функције (плава крива)

Најбоља линеарна апроксимација произвољне диференцијабилне функције у близини тачке је тангента на криву, са једначином

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

alt=Илустрација Њутновог метода|thumb|right|upright=1.4|Итерација обично побољшава апроксимацију

Процес се може започети са било којом произвољном почетном претпоставком , иако ће генерално захтевати мање итерација да конвергира ако је претпоставка близу једне од нула функције. Метод ће обично конвергирати ако је . Штавише, за нулу вишеструкости 1, конвергенција је барем квадратна (погледати Брзина конвергенције) у некој довољно малој околини нуле: број тачних цифара апроксимације се отприлике удвостручује са сваким додатним кораком. Више детаља се може наћи у одељку испод.

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

Историја У старовавилонском периоду (19–16. век п. н. е.), страница квадрата познате површине могла се ефикасно апроксимирати, а претпоставља се да је то рађено коришћењем посебног случаја Њутновог метода, описаног алгебарски испод, итеративним побољшањем почетне процене; еквивалентан метод се може наћи у делу Метрика Херона Александријског (1–2. век н.е.), па се често назива Херонов метод. Најранија позната појава типа Њутн-Рафсоновог метода може се пратити до рада персијског астронома и математичара Џамшида ал Кашија (1380–1429). У својој значајној публикацији из 1427. године, Miftāḥ al-Ḥisāb (, у преводу Кључ аритметике)), описао је варијанту овог итеративног метода. Џамшид ал Каши је користио метод за решавање како би пронашао корене од , метод који је био алгебарски еквивалентан Њутновом методу, а сличан метод је пронађен у делу 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 Ако нула која се тражи има вишеструкост већу од један, стопа конвергенције је само линеарна (грешке се смањују за константан фактор у сваком кораку) осим ако се не предузму посебни кораци. Када постоје две или више нула које су близу једна другој, може бити потребно много итерација пре него што се итерације довољно приближе једној од њих да би квадратна конвергенција била очигледна. Међутим, ако је вишеструкост нуле позната, следећи модификовани алгоритам чува квадратну стопу конвергенције:

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

Спора конвергенција Функција има нулу у 0.J. E. Dennis, Jr. and Robert B. Schnabel. Numerical methods for unconstrained optimization and nonlinear equations. SIAM Пошто је непрекидно диференцијабилна у својој нули, теорија гарантује да ће Њутнов метод иницијализован довољно близу нуле конвергирати. Међутим, пошто је извод нула у нули, квадратна конвергенција није загарантована теоријом. У овом конкретном примеру, Њутнова итерација је дата са

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

Функција такође има нулу у 0, где је непрекидно диференцијабилна. Иако први извод није нула у нули, други извод тамо не постоји, тако да се квадратна конвергенција не може гарантовати. У ствари, Њутнова итерација је дата са

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

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

Брзина конвергенције се разликује од броја итерација потребних да се достигне дата тачност. На пример, функција има нулу у 1. Пошто је и је глатка, познато је да ће свака Њутнова итерација која конвергира ка 1 конвергирати квадратно. Међутим, ако се иницијализује на 0.5, првих неколико итерација Њутновог метода су приближно 26214, 24904, 23658, 22476, споро опадајући, при чему је тек 200. итерација 1.0371. Следеће итерације су 1.0103, 1.00093, 1.0000082 и 1.00000000065, што илуструје квадратну конвергенцију. Ово наглашава да квадратна конвергенција Њутнове итерације не значи да је потребно само неколико итерација; ово важи само када је низ итерација довољно близу нуле.Anthony Ralston and Philip Rabinowitz. A first course in numerical analysis, second edition

Конвергенција зависи од иницијализације Функција има нулу у 0. Њутнова итерација је дата са