Metoda e Njutonit

Në analizën numerike, metoda e Njutonit, e njohur gjithashtu si metoda Njuton-Rapson, e quajtur sipas Isak Njutonit dhe Jozef Rapsonit, është një algoritëm për gjetjen e rrënjëve i cili prodhon përafrime të njëpasnjëshme më të mira për rrënjët (ose zerot) e një funksioni me vlera reale . Versioni më themelor fillon me një funksion me një ndryshore, $f$, të përcaktuar për një ndryshore reale x, derivatin e funksionit $f'$ dhe një supozim fillestar $x_{0}$ për një rrënjë të $f$ . Nëse funksioni plotëson supozime të mjaftueshme dhe supozimi fillestar është i afërt, atëherë

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

është një përafrim më i mirë i rrënjës se $x_{0}$ . Gjeometrikisht, $(x_{1},0)$ është prerja e boshtit x dhe tangjentja e grafikut të $f$ në $(x_{0},f_{(}x_{0}))$ : domethënë, supozimi i përmirësuar është rrënja unike e përafrimit linear në pikën fillestare. Procesi përsëritet si

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

derisa të arrihet një vlerë mjaftueshëm e saktë. Numri i shifrave të sakta dyfishohet afërsisht me çdo hap. Ky algoritëm është i pari në klasën e metodave të Homeholder, i pasuar nga metoda e Halley . Metoda mund të shtrihet edhe në funksione komplekse dhe në sisteme ekuacionesh.

Përshkrim

Ideja është që të fillohet me një supozim fillestar, pastaj të përafrohet funksioni me vijën e tij tangjente dhe në fund të llogaritet prerja me boshtin e abshisave e kësaj vije tangjente. Kjo ndërprerje e abshisave zakonisht do të jetë një përafrim më i mirë me rrënjën e funksionit origjinal sesa supozimi i parë dhe metoda mund të përsëritet .

$x_{n+1}$ është një përafrim më i mirë se $x_{n}$ për rrënjën x të funksionit f (kurba blu)

Nëse vija tangjente me lakoren $f(x)$ në $x=x_{n}$ ndërpret boshtin x në $x_{n+1}$, atëherë pjerrësia është

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

Zgjidhja për $x_{n+1}$ jep

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

Iterimi zakonisht përmirëson përafrimin

Ne e fillojmë procesin me një vlerë fillestare arbitrare $x_{0}$ . (Sa më afër zeros, aq më mirë. Por, në mungesë të ndonjë intuite se ku mund të qëndrojë zeroja, një metodë "hamëndëso dhe kontrollo" mund të ngushtojë kërkimin në një interval mjaft të vogël duke iu drejtuar teoremës së vlerës së ndërmjetme . ) Metoda zakonisht do të konvergjojë, me kusht që ky supozim fillestar të jetë mjaft afër zeros së panjohur dhe që $f'(x_{0})\neq 0$ . Për më tepër, për një zero me shumëfish 1, konvergjenca është të paktën kuadratike (shih Shkalla e konvergjencës ) në një afërsi të zeros, që do të thotë intuitivisht se numri i shifrave të sakta përafërsisht dyfishohet në çdo hap.

Metodat Householder janë të ngjashme, por kanë rend më të lartë të konvergjencës edhe më të shpejtë. Megjithatë, llogaritjet shtesë të kërkuara për çdo hap mund të ngadalësojnë performancën e përgjithshme në lidhje me metodën e Njutonit, veçanërisht nëse $f$ ose derivatet e tij janë të shtrenjta për t'u vlerësuar për sa u përket llogaritjeve.

Konsiderata praktike

Metoda e Njutonit është një teknikë e fuqishme - në përgjithësi konvergjenca është kuadratike: ndërsa metoda konvergjon në rrënjë, ndryshesa midis rrënjës dhe përafrimit është në katror (numri i shifrave të sakta afërsisht dyfishohet) në çdo hap. Megjithatë, ka disa vështirësi me metodën.

Vështirësi në llogaritjen e derivatit të një funksioni

Metoda e Njutonit kërkon që derivati të mund të llogaritet drejtpërdrejt. Një shprehje analitike për derivatin mund të mos jetë lehtësisht e arritshme ose mund të jetë e shtrenjtë për t'u vlerësuar. Në këto situata, mund të jetë e përshtatshme që të përafrohet derivati duke përdorur pjerrësinë e një vije përmes dy pikave të afërta të funksionit. Përdorimi i këtij përafrimi do të rezultonte në diçka të ngjashme me metodën sekante, konvergjenca e së cilës është më e ngadaltë se ajo e metodës së Njutonit.

Dështimi i metodës për të konvergjuar në rrënjë

Është e rëndësishme të rishikohet vërtetimi i konvergjencës kuadratike të metodës së Njutonit përpara se ta zbatoni atë. Në mënyrë të veçantë, duhen rishikuar supozimet e bëra në provë. Për situatat kur metoda nuk arrin të konvergojë, kjo ndodh sepse supozimet e bëra në këtë provë nuk përmbushen.

Tejkalimi

Nëse derivati i parë nuk sillet mirë në afërsi të një rrënjë të caktuar, metoda mund të tejkalojë dhe të ndryshojë nga ajo rrënjë. Një shembull i një funksioni me një rrënjë, për të cilin derivati nuk sillet mirë në afërsi të rrënjës, është

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

për të cilin rrënja do të tejkalohet dhe seria e x do të ndryshojë.

Pika stacionare

Nëse haset një pikë e stacionare e funksionit, derivati është zero dhe metoda do të përfundojë për shkak të pjesëtimit me zero .

Vlerësimi fillestar i dobët

Një gabim i madh në vlerësimin fillestar mund të kontribuojë në moskonvergjencën e algoritmit. Për të kapërcyer këtë problem, shpesh mund të linearizohet funksioni që është duke u optimizuar duke përdorur analizën matematike, logaritmet, diferencialet, apo edhe duke përdorur algoritme evolucionare, siç është tunelizimi stokastik . Vlerësimet e mira fillestare qëndrojnë afër vlerësimit përfundimtar të parametrave globalisht optimale.

Konvergjenca e ngadaltë për rrënjët e shumëfishimit më të madh se 1

Nëse rrënja e kërkuar ka shumëfish më të madh se një, shkalla e konvergjencës është thjesht lineare (gabimet reduktohen me një faktor konstant në çdo hap) përveç nëse ndërmerren hapa të veçantë. Kur ka dy ose më shumë rrënjë që janë afër njëra-tjetrës, atëherë mund të duhen shumë përsëritje përpara se përsëritjet të afrohen mjaftueshëm me njërën prej tyre që konvergjenca kuadratike të jetë e dukshme. Sidoqoftë, nëse dihet shumëfishiteti $m$ i rrënjës, algoritmi i modifikuar i mëposhtëm ruan shkallën e konvergjencës kuadratike:

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

Kjo është e barabartë me përdorimin e një mbirelaksimi të njëpasnjëshëm . Nga ana tjetër, nëse nuk dihet shumëfishiteti $m$ i rrënjës, është e mundur të vlerësohet $m$ pasi të kryhen një ose dy përsëritje, dhe më pas të përdoret kjo vlerë për të rritur shkallën e konvergjencës.

Analiza

Supozojmë se funksioni $f$ ka një zero në $\alpha$, dmth, $f(\alpha )=0$, dhe $f$ është i diferencueshëm në një afërsi të $\alpha$ .

Nëse $f$ është vazhdimisht i diferencueshëm dhe derivati i tij është jozero në $\alpha$, atëherë ekziston një fqinjësi e $\alpha$ e tillë që për të gjitha vlerat fillestare $x_{0}$ në atë fqinjësi, seria ($x_{n}$) do të konvergojë në $\alpha$ .

Nëse $f$ është vazhdimisht i diferencueshëm, derivati i tij është jozero në $\alpha$, dhe ka një derivat të dytë në $\alpha$, atëherë konvergjenca është kuadratike ose më e shpejtë. Nëse derivati i dytë nuk është 0 në $\alpha$, atëherë konvergjenca është thjesht kuadratike. Nëse derivati i tretë ekziston dhe kufizohet në një lagje të $\alpha$, atëherë:

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

ku

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

Nëse derivati është 0 në ${\ce {\alpha}}$, atëherë konvergjenca është zakonisht vetëm lineare. Në mënyrë të veçantë, nëse f është dy herë e diferencueshme vazhdimisht, $f'(\alpha )=0$ dhe $f''(\alpha )=0$, atëherë ekziston një fqinjësi e $\alpha$ e tillë që, për të gjitha vlerat fillestare $x_{0}$ në atë fqinjësi, seria e përsëritjeve konvergjon në mënyrë lineare, me normë ${\frac {1}{2}}$  Përndryshe, nëse $f'(\alpha )=0$ dhe $f'(x)\neq 0$ për $x\neq \alpha$, x në një afërsi U të $\alpha$, $\alpha$ është zero e shumëfishit $r$, dhe nëse $f\in C^{r}{(U)}$, atëherë ekziston një fqinjësi e $\alpha$ e tillë që, për të gjitha vlerat fillestare $x_{0}$ në atë afërsi, seria e përsëritjeve konvergjon në mënyrë lineare.

Megjithatë, edhe konvergjenca lineare nuk është e garantuar në situata patologjike.

Shembuj

Rrenja katrore

Shqyrtoni problemin e gjetjes së rrënjës katrore të një numri a, domethënë të numrit pozitiv x të tillë që $x^{2}=a$ . Metoda e Njutonit është një nga shumë metodat e llogaritjes së rrënjëve katrore . Mund ta riformulojmë duke kaluar numrin a nga ana e majtë për të marrë trajtën standarde $f(x)=0$ se si gjetja e zeros së $f(x)=x^{2}-a$ . Kemi $f'(x)=2x$ .

Për shembull, për gjetjen e rrënjës katrore të 612 me një supozim fillestar $x_{0}=10$, seria e dhënë nga metoda e Njutonit është:

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{\dfrac {10^{2}-612}{2\times 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\times 35.6}}&=&{\underline {2}}6.395\,505\,617\,978\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}90\,635\,492\,455\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.738\,6}}88\,294\,075\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {24.738\,633\,753\,7}}67\dots \end{matrix}}$

ku nënvizohen shifrat e sakta. Me vetëm disa përsëritje mund të merret një zgjidhje e saktë në shumë shifra dhjetore.

Rirregullimi i formulës si më poshtë jep metodën babilonase të gjetjes së rrënjëve katrore :

$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 )}$

dmth mesatarja aritmetike e hamendjes, $x_{n}\And {\frac {a}{x_{n}}}$

Zgjidhja e $\cos(x)=x^{3}$

Shqyrtoni problemin e gjetjes së numrit pozitiv ${\textstyle x}$ me ${\textstyle \cos x=x^{3}}$ . Mund ta riformulojmë atë si gjetjen e zeros në trajtën standarde si ${\textstyle f(x)=\cos(x)-x^{3}}$ . Ne kemi ${\textstyle f'(x)=-\sin(x)-3x^{2}}$ . Që nga viti ${\textstyle \cos(x)\leq 1}$ per te gjithe ${\textstyle x}$ dhe ${\textstyle x^{3}>1}$ për ${\textstyle x>1}$, ne e dimë se zgjidhja jonë qëndron midis 0 dhe 1.

Për shembull, me një supozim fillestar $x_{0}=0.5$, seria e dhënë nga metoda e Njutonit është (vini re se një vlerë fillestare prej 0 do të çojë në një rezultat të papërcaktuar, duke treguar rëndësinë e përdorimit të një pike fillestare që është afër zgjidhjes):

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{\dfrac {\cos 0.5-0.5^{3}}{-\sin 0.5-3\times 0.5^{2}}}&=&1.112\,141\,637\,097\dots \\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909\,672\,693\,736\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7\,263\,818\,209\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,1}}11\dots \\x_{6}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,102}}\dots \end{matrix}}$

Shifrat e sakta janë nënvizuar në shembullin e mësipërm. Në veçanti, $x_{6}$ është e saktë me 12 shifra dhjetore. Ne shohim se numri i shifrave të sakta pas pikës dhjetore rritet nga 2 (për $x_{3}$ ) në 5 dhe 10, duke ilustruar konvergjencën kuadratike.