Ne analizen numerike , metoda e Njutonit , e njohur gjithashtu si metoda Njuton-Rapson , e quajtur sipas Isak Njutonit dhe Jozef Rapsonit, eshte nje algoritem per gjetjen e rrenjeve i cili prodhon perafrime te njepasnjeshme me te mira per rrenjet (ose zerot) e nje funksioni me vlera reale . Versioni me themelor fillon me nje funksion me nje ndryshore, ${\displaystyle f}$, te percaktuar per nje ndryshore reale x, derivatin e funksionit ${\displaystyle f'}$ dhe nje supozim fillestar ${\displaystyle x_{0}}$ per nje rrenje te ${\displaystyle f}$ . Nese funksioni ploteson supozime te mjaftueshme dhe supozimi fillestar eshte i afert, atehere

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

eshte nje perafrim me i mire i rrenjes se ${\displaystyle x_{0}}$ . Gjeometrikisht, ${\displaystyle (x_{1},0)}$ eshte prerja e boshtit x dhe tangjentja e grafikut te ${\displaystyle f}$ ne ${\displaystyle (x_{0},f_{(}x_{0}))}$ : domethene, supozimi i permiresuar eshte rrenja unike e perafrimit linear ne piken fillestare. Procesi perseritet si

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

derisa te arrihet nje vlere mjaftueshem e sakte. Numri i shifrave te sakta dyfishohet afersisht me cdo hap. Ky algoritem eshte i pari ne klasen e metodave te Homeholder, i pasuar nga metoda e Halley . Metoda mund te shtrihet edhe ne funksione komplekse dhe ne sisteme ekuacionesh.

Pershkrim [ Redakto | Redakto nepermjet kodit ]

Ideja eshte qe te fillohet me nje supozim fillestar, pastaj te perafrohet funksioni me vijen e tij tangjente dhe ne fund te llogaritet prerja me boshtin e abshisave e kesaj vije tangjente. Kjo nderprerje e abshisave zakonisht do te jete nje perafrim me i mire me rrenjen e funksionit origjinal sesa supozimi i pare dhe metoda mund te perseritet .

Nese vija tangjente me lakoren ${\displaystyle f(x)}$ ne ${\displaystyle x=x_{n}}$ nderpret boshtin x ne ${\displaystyle x_{n+1}}$, atehere pjerresia eshte

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

Zgjidhja per ${\displaystyle x_{n+1}}$ jep

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

Ne e fillojme procesin me nje vlere fillestare arbitrare ${\displaystyle x_{0}}$ . (Sa me afer zeros, aq me mire. Por, ne mungese te ndonje intuite se ku mund te qendroje zeroja, nje metode "hamendeso dhe kontrollo" mund te ngushtoje kerkimin ne nje interval mjaft te vogel duke iu drejtuar teoremes se vleres se ndermjetme . ) Metoda zakonisht do te konvergjoje, me kusht qe ky supozim fillestar te jete mjaft afer zeros se panjohur dhe qe ${\displaystyle f'(x_{0})\neq 0}$ . Per me teper, per nje zero me shumefish 1, konvergjenca eshte te pakten kuadratike (shih Shkalla e konvergjences ) ne nje afersi te zeros, qe do te thote intuitivisht se numri i shifrave te sakta perafersisht dyfishohet ne cdo hap.

Metodat Householder jane te ngjashme, por kane rend me te larte te konvergjences edhe me te shpejte. Megjithate, llogaritjet shtese te kerkuara per cdo hap mund te ngadalesojne performancen e pergjithshme ne lidhje me metoden e Njutonit, vecanerisht nese ${\displaystyle f}$ ose derivatet e tij jane te shtrenjta per t'u vleresuar per sa u perket llogaritjeve.

Konsiderata praktike [ Redakto | Redakto nepermjet kodit ]

Metoda e Njutonit eshte nje teknike e fuqishme - ne pergjithesi konvergjenca eshte kuadratike: ndersa metoda konvergjon ne rrenje, ndryshesa midis rrenjes dhe perafrimit eshte ne katror (numri i shifrave te sakta afersisht dyfishohet) ne cdo hap. Megjithate, ka disa veshtiresi me metoden.

Veshtiresi ne llogaritjen e derivatit te nje funksioni [ Redakto | Redakto nepermjet kodit ]

Metoda e Njutonit kerkon qe derivati te mund te llogaritet drejtperdrejt. Nje shprehje analitike per derivatin mund te mos jete lehtesisht e arritshme ose mund te jete e shtrenjte per t'u vleresuar. Ne keto situata, mund te jete e pershtatshme qe te perafrohet derivati duke perdorur pjerresine e nje vije permes dy pikave te aferta te funksionit. Perdorimi i ketij perafrimi do te rezultonte ne dicka te ngjashme me metoden sekante , konvergjenca e se ciles eshte me e ngadalte se ajo e metodes se Njutonit.

Deshtimi i metodes per te konvergjuar ne rrenje [ Redakto | Redakto nepermjet kodit ]

Eshte e rendesishme te rishikohet vertetimi i konvergjences kuadratike te metodes se Njutonit perpara se ta zbatoni ate. Ne menyre te vecante, duhen rishikuar supozimet e bera ne prove. Per situatat kur metoda nuk arrin te konvergoje, kjo ndodh sepse supozimet e bera ne kete prove nuk permbushen.

Tejkalimi [ Redakto | Redakto nepermjet kodit ]

Nese derivati i pare nuk sillet mire ne afersi te nje rrenje te caktuar, metoda mund te tejkaloje dhe te ndryshoje nga ajo rrenje. Nje shembull i nje funksioni me nje rrenje, per te cilin derivati nuk sillet mire ne afersi te rrenjes, eshte

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

per te cilin rrenja do te tejkalohet dhe seria e x do te ndryshoje.

Pika stacionare [ Redakto | Redakto nepermjet kodit ]

Nese haset nje pike e stacionare e funksionit, derivati eshte zero dhe metoda do te perfundoje per shkak te pjesetimit me zero .

Vleresimi fillestar i dobet [ Redakto | Redakto nepermjet kodit ]

Nje gabim i madh ne vleresimin fillestar mund te kontribuoje ne moskonvergjencen e algoritmit. Per te kapercyer kete problem, shpesh mund te linearizohet funksioni qe eshte duke u optimizuar duke perdorur analizen matematike, logaritmet, diferencialet, apo edhe duke perdorur algoritme evolucionare, sic eshte tunelizimi stokastik . Vleresimet e mira fillestare qendrojne afer vleresimit perfundimtar te parametrave globalisht optimale.

Konvergjenca e ngadalte per rrenjet e shumefishimit me te madh se 1 [ Redakto | Redakto nepermjet kodit ]

Nese rrenja e kerkuar ka shumefish me te madh se nje, shkalla e konvergjences eshte thjesht lineare (gabimet reduktohen me nje faktor konstant ne cdo hap) pervec nese ndermerren hapa te vecante. Kur ka dy ose me shume rrenje qe jane afer njera-tjetres, atehere mund te duhen shume perseritje perpara se perseritjet te afrohen mjaftueshem me njeren prej tyre qe konvergjenca kuadratike te jete e dukshme. Sidoqofte, nese dihet shumefishiteti ${\displaystyle m}$ i rrenjes, algoritmi i modifikuar i meposhtem ruan shkallen e konvergjences kuadratike: ^[1]

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

Kjo eshte e barabarte me perdorimin e nje mbirelaksimi te njepasnjeshem . Nga ana tjeter, nese nuk dihet shumefishiteti ${\displaystyle m}$ i rrenjes, eshte e mundur te vleresohet ${\displaystyle m}$ pasi te kryhen nje ose dy perseritje, dhe me pas te perdoret kjo vlere per te rritur shkallen e konvergjences.

Analiza [ Redakto | Redakto nepermjet kodit ]

Supozojme se funksioni ${\displaystyle f}$ ka nje zero ne ${\displaystyle \alpha }$, dmth, ${\displaystyle f(\alpha )=0}$, dhe ${\displaystyle f}$ eshte i diferencueshem ne nje afersi te ${\displaystyle \alpha }$ .

Nese ${\displaystyle f}$ eshte vazhdimisht i diferencueshem dhe derivati i tij eshte jozero ne ${\displaystyle \alpha }$, atehere ekziston nje fqinjesi e ${\displaystyle \alpha }$ e tille qe per te gjitha vlerat fillestare ${\displaystyle x_{0}}$ ne ate fqinjesi, seria ( ${\displaystyle x_{n}}$) do te konvergoje ne ${\displaystyle \alpha }$ . ^[2]

Nese ${\displaystyle f}$ eshte vazhdimisht i diferencueshem, derivati i tij eshte jozero ne  ${\displaystyle \alpha }$, dhe ka nje derivat te dyte ne  ${\displaystyle \alpha }$, atehere konvergjenca eshte kuadratike ose me e shpejte. Nese derivati i dyte nuk eshte 0 ne ${\displaystyle \alpha }$, atehere konvergjenca eshte thjesht kuadratike. Nese derivati i trete ekziston dhe kufizohet ne nje lagje te ${\displaystyle \alpha }$, atehere:

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

ku

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

Nese derivati eshte 0 ne ${\displaystyle {\ce {\alpha}}}$, atehere konvergjenca eshte zakonisht vetem lineare. Ne menyre te vecante, nese f eshte dy here e diferencueshme vazhdimisht, ${\displaystyle f'(\alpha )=0}$ dhe ${\displaystyle f''(\alpha )=0}$, atehere ekziston nje fqinjesi e ${\displaystyle \alpha }$ e tille qe, per te gjitha vlerat fillestare ${\displaystyle x_{0}}$ ne ate fqinjesi, seria e perseritjeve konvergjon ne menyre lineare, me norme ${\displaystyle {\frac {1}{2}}}$  ^[3] Perndryshe, nese ${\displaystyle f'(\alpha )=0}$ dhe ${\displaystyle f'(x)\neq 0}$ per ${\displaystyle x\neq \alpha }$, x ne nje afersi U te ${\displaystyle \alpha }$, ${\displaystyle \alpha }$ eshte zero e shumefishit ${\displaystyle r}$, dhe nese ${\displaystyle f\in C^{r}{(U)}}$, atehere ekziston nje fqinjesi e ${\displaystyle \alpha }$ e tille qe, per te gjitha vlerat fillestare ${\displaystyle x_{0}}$ ne ate afersi, seria e perseritjeve konvergjon ne menyre lineare.

Megjithate, edhe konvergjenca lineare nuk eshte e garantuar ne situata patologjike.

Shembuj [ Redakto | Redakto nepermjet kodit ]

Rrenja katrore [ Redakto | Redakto nepermjet kodit ]

Shqyrtoni problemin e gjetjes se rrenjes katrore te nje numri a, domethene te numrit pozitiv x te tille qe ${\displaystyle x^{2}=a}$ . Metoda e Njutonit eshte nje nga shume metodat e llogaritjes se rrenjeve katrore . Mund ta riformulojme duke kaluar numrin a nga ana e majte per te marre trajten standarde ${\displaystyle f(x)=0}$ se si gjetja e zeros se ${\displaystyle f(x)=x^{2}-a}$ . Kemi ${\displaystyle f'(x)=2x}$ .

Per shembull, per gjetjen e rrenjes katrore te 612 me nje supozim fillestar ${\displaystyle x_{0}=10}$, seria e dhene nga metoda e Njutonit eshte:

${\displaystyle {\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 nenvizohen shifrat e sakta. Me vetem disa perseritje mund te merret nje zgjidhje e sakte ne shume shifra dhjetore.

Rirregullimi i formules si me poshte jep metoden babilonase te gjetjes se rrenjeve katrore :

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

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

Zgjidhja e ${\displaystyle \cos(x)=x^{3}}$[ Redakto | Redakto nepermjet kodit ]

Shqyrtoni problemin e gjetjes se numrit pozitiv ${\textstyle x}$ me ${\textstyle \cos x=x^{3}}$ . Mund ta riformulojme ate si gjetjen e zeros ne trajten standarde si ${\textstyle f(x)=\cos(x)-x^{3}}$ . Ne kemi ${\textstyle f'(x)=-\sin(x)-3x^{2}}$ . Qe nga viti ${\textstyle \cos(x)\leq 1}$ per te gjithe ${\textstyle x}$ dhe ${\textstyle x^{3}>1}$ per ${\textstyle x>1}$, ne e dime se zgjidhja jone qendron midis 0 dhe 1.

Per shembull, me nje supozim fillestar ${\displaystyle x_{0}=0.5}$, seria e dhene nga metoda e Njutonit eshte (vini re se nje vlere fillestare prej 0 do te coje ne nje rezultat te papercaktuar, duke treguar rendesine e perdorimit te nje pike fillestare qe eshte afer zgjidhjes):

${\displaystyle {\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 jane nenvizuar ne shembullin e mesiperm. Ne vecanti, ${\displaystyle x_{6}}$ eshte e sakte me 12 shifra dhjetore. Ne shohim se numri i shifrave te sakta pas pikes dhjetore rritet nga 2 (per ${\displaystyle x_{3}}$ ) ne 5 dhe 10, duke ilustruar konvergjencen kuadratike.

1. ^ "Accelerated and Modified Newton Methods" . Arkivuar nga origjinali me 24 maj 2019 . Marre me 4 mars 2016 . {{ cite web }} : Mungon ose eshte bosh parametri |language= ( Ndihme! )
2. ^ Ryaben'kii, Victor S.; Tsynkov, Semyon V. (2006), A Theoretical Introduction to Numerical Analysis , CRC Press, fq. 243, ISBN   9781584886075 {{ citation }} : Mungon ose eshte bosh parametri |language= ( Ndihme! ) .
3. ^ Suli & Mayers 2003 , Exercise 1.6