Metoda lui Newton

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 25 ianuarie 2022; verificările necesită 3 modificări .

Metoda lui Newton , algoritmul lui Newton (cunoscut și ca metoda tangentei ) este o metodă numerică iterativă pentru găsirea rădăcinii ( zero ) a unei anumite funcții . Metoda a fost propusă pentru prima dată de fizicianul , matematicianul și astronomul englez Isaac Newton ( 1643-1727 ) . Căutarea unei soluții se realizează prin construirea de aproximări succesive și se bazează pe principiile iterației simple . Metoda are convergență pătratică . O modificare a metodei este metoda acordurilor și tangentelor . De asemenea, metoda lui Newton poate fi folosită pentru a rezolva probleme de optimizare în care este necesară determinarea zeroului primei derivate sau gradientului în cazul unui spațiu multidimensional.

Descrierea metodei

Motivație

Pentru a rezolva numeric ecuația prin metoda iterației simple , aceasta trebuie redusă la o ecuație echivalentă: , unde este maparea contracției . $f(x)=0$ $x=\varphi(x)$ $\varphi$

Pentru cea mai bună convergență a metodei în punctul următoarei aproximări , condiția trebuie îndeplinită . Se caută soluția acestei ecuații sub forma , atunci: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

\varphi '(x^{*})=1+\alpha '(x^{*})f(x^{*})+\alpha (x^{*})f'(x^{* *})=0.

Presupunând că punctul de aproximare este „destul de aproape” de rădăcină și că funcția dată este continuă , formula finală pentru este: ${\tilde {x}}$ $(f(x^{*})\aproximativ f({\tilde {x)))=0)$ $\alpha(x)$

\alpha (x)=-{\frac {1}{f'(x))).

Având în vedere acest lucru, funcția este definită: $\varphi(x)$

\varphi (x)=x-{\frac {f(x)}{f'(x))).

În anumite condiții, această funcție realizează o mapare de contracție într-o vecinătate a rădăcinii.

Dovada

Să fie dată o funcție a unei variabile reale care este de două ori continuu diferențiabilă în domeniul său de definiție și a cărei derivată nu dispare niciodată:

\scriptstyle {f(x)\colon {\mathbb {X}}\la \mathbb{R} ,\;f(x)\in {\mathrm {C}}^{2}({\mathbb {X} });\quad \forall x\in {\mathbb {X}}\;f'(x)\neq 0.}

Și este necesar să se demonstreze că funcția efectuează o mapare de contracție lângă rădăcina ecuației . $\scriptstyle {\varphi (x)=x-{\frac {f(x)}{f'(x)))}$ $\scriptstyle {f(x)=0}$

Datorită diferențiabilității continue a funcției și inegalității lui zero, derivata sa întâi este continuă . $\scriptstyle {f(x)}$ $\scriptstyle {\varphi (x)}$

Derivata este: $\scriptstyle {\varphi '(x)}$

\scriptstyle {\varphi '(x)={\frac {f(x)f''(x)}{\left(f'(x)\right)^{2))}.}

În condițiile impuse , este și continuă. Fie rădăcina dorită a ecuației: , prin urmare, în vecinătatea ei : $\scriptstyle {f(x)}$ $\scriptstyle {{\tilde {x}}}$ $\scriptstyle {f({\tilde {x)))=0}$ $\scriptstyle {\varphi '(x)\aprox 0}$

\scriptstyle {\forall \varepsilon \colon 0<\varepsilon <1,\;\există \delta >0\;\forall x\in {\mathbb {X}}\;|x-{\tilde {x}} |<\delta \colon |\varphi '(x)-0|<\varepsilon .}

Apoi, conform teoremei lui Lagrange :

\scriptstyle {\forall x_{1},\;x_{2}\in {\mathrm {U}}_{\delta}({\tilde {x))}\;\există \xi \in {\mathrm {U}}_{\delta }({\tilde {x}})\colon |\varphi (x_{1})-\varphi (x_{2})|=|\varphi '(\xi )|| x_{1}-x_{2}|<\varepsilon |x_{1}-x_{2}|.}

Datorită faptului că , în același cartier deltă, sunt adevărate următoarele: $\scriptstyle {\varphi ({\tilde {x))}={\tilde {x}}}$

\scriptstyle {\forall x\in U_{{\delta }}({\tilde {x}})\colon \;|\varphi (x)-{\tilde {x}}|<\varepsilon |x-{ \tilde{x}}|.}

Funcția astfel obținută în vecinătatea rădăcinii implementează o mapare de contracție . ■ $\scriptstyle {\varphi (x)}$ $\scriptstyle {U_{\delta}({\tilde {x)))}$

În acest caz, algoritmul pentru găsirea unei soluții numerice a ecuației este redus la o procedură de calcul iterativă : $f(x)=0$

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

Conform teoremei lui Banach , succesiunea de aproximări tinde spre rădăcina ecuației . $f(x)=0$

Interpretare geometrică

Ideea principală a metodei este următoarea: aproximarea inițială este stabilită lângă rădăcina ipotetică, după care este trasată o tangentă la graficul funcției studiate în punctul de aproximare, pentru care intersecția cu axa absciselor este găsite. Acest punct este luat ca următoarea aproximare. Și așa mai departe, până când se ajunge la precizia necesară.

Fie 1) o funcţie cu valoare reală să fie continuu diferenţiabilă pe intervalul ; 2) există un punct cerut : ; 3) există , de asemenea, astfel încât pentru și pentru ; 4) ideea este astfel încât . Apoi , formula pentru aproximarea iterativă la k poate fi derivată din semnificația geometrică a tangentei după cum urmează: $f(x)\colon (a,\,b)\la \mathbb {R}$ $(a,\,b)$
$x^{*}\in (a,\,b)$ $f(x^{*})=0$
$C > 0$ $\delta>0$
$\vert f'(x)\vert \geqslant C$ $x\in (a,\,x^{*}-\delta ]\cup [x^{*}+\delta ,\,b)$
$f'(x)\neq 0$ $x\in (x^{*}-\delta ,\,x^{*})\cup (x^{*},\,x^{*}+\delta )$
$x_{n}\in (a,\,b)$ $f(x_{n})\neq 0$
$x_{n}$ $x^{{*}}$

f'(x_{n})=\mathrm {tg} \,\alpha _{n}={\frac {\Delta y}{\Delta x))={\frac {f(x_{n} })-0}{x_{n}-x_{n+1}}}={\frac {0-f(x_{n})}{x_{n+1}-x_{n}}},

unde este unghiul de înclinare al dreptei tangente la grafic în punctul . $\alpha _{n}$ $y(x)=f(x_{n})+(x-x_{n})\cdot \mathrm {tg} \,\alpha _{n)$ $f$ $(x_{n};f(x_{n}))$

Prin urmare (în ecuația dreptei tangente presupunem ) expresia dorită pentru are forma: $y(x_{n+1})=0$ $x_{{n+1}}$

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

Dacă , atunci această valoare poate fi folosită ca următoarea aproximare a . $x_{n+1}\in (a,\,b)$ $x^{{*}}$

Dacă , atunci există un „zbor” (rădăcina se află lângă graniță ). În acest caz, este necesar (folosind ideea metodei bisecției ) să se înlocuiască cu până când punctul „revine” în zona de căutare . $x_{n+1}\notin (a,\,b)$ $x^{{*}}$ $(a,\,b)$ $x_{{n+1}}$ ${\frac {x_{n}+x_{n+1}}{2}}$ $(a,\,b)$

Remarci. 1) Prezența unei derivate continue face posibilă construirea unei tangente în continuă schimbare pe întreaga zonă a căutării unei soluții . 2) Cazurile de amplasare a graniței (la un punct sau la un punct ) a soluției dorite sunt considerate în mod similar. 3) Din punct de vedere geometric, egalitatea înseamnă că linia tangentă la grafic în punctul - este paralelă cu axa și nu se intersectează cu aceasta la sfârșit. 4) Cu cât constanta este mai mare și cu atât constanta din paragraful 3 al condițiilor este mai mică, cu atât intersecția tangentei la grafic și a axei este mai apropiată de punctul , adică cu atât valoarea este mai apropiată de cea dorită . $(a,\,b)\;$
$A$ $b$ $x^{{*}}$
$f'(x_{n})=0$ $f$ $(x_{n};f(x_{n}))$ $BOU$ $f(x_{n})\neq 0$
$C > 0$ $\delta>0$ $x_{n}\in (a,\,x^{*}-\delta ]\cup [x^{*}+\delta,\,b)$ $f$ $BOU$ $(x^{*};\;0)$ $x_{{n+1}}$ $x^{*}\in (a,\,b)$

Procesul iterativ începe cu o aproximare inițială , iar între și punctul dorit nu ar trebui să existe alte zerouri ale funcției , adică „cu cât mai aproape de rădăcina dorită , cu atât mai bine”. Dacă nu există ipoteze despre găsire , încercarea și eroarea pot restrânge gama de valori posibile prin aplicarea teoremei valorii intermediare . $x_{0}\in (a,\,b)$ $x_{0}\in (a,\,b)$ $x^{*}\in (a,\,b)$ $f$ $x_{0}$ $x^{{*}}$ $x^{{*}}$

Pentru predefinit , procesul iterativ se termină dacă și . În special, pentru matricea de afișare și poate fi calculată pe baza scalei de afișare a graficului , adică dacă și se încadrează într-o singură verticală și într-un rând orizontal. $\varepsilon _{x}>0$ $\varepsilon _{f}>0$ $\left\vert {\frac {f(x_{n})}{f'(x_{n))}}\dreapta\vert \aprox \vert x_{n+1}-x_{n}\ vert<\varepsilon_{x}$ $\vert f(x_{n+1})\vert </varepsilon _{f)$
$\varepsilon _{x}$ $\varepsilon _{f)$ $f$ $x_{n}$ $x_{{n+1}}$ $f(x_{n})$ $f(x_{n+1})$

Algoritm

Aproximația inițială este setată . $x_{0}$
Până la îndeplinirea condiției de oprire, care poate fi luată ca sau (adică eroarea se află în limitele cerute), se calculează o nouă aproximare: . $|x_{n+1}-x_{n}|<\varepsilon$ $|f(x_{n+1})|<\varepsilon$ $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n))}}$

Exemplu

Luați în considerare problema găsirii pozitive , pentru care . Această sarcină poate fi reprezentată ca sarcina de a găsi zeroul funcției . Avem o expresie pentru derivata . Deoarece pentru toți și pentru , este evident că soluția se află între 0 și 1. Să luăm valoarea ca o aproximare inițială , atunci: $X$ $\cos x=x^{3}$ $f(x)=\cos xx^{3}$ $f'(x)=-\sin x-3x^{2}$ $\cos x\leqslant 1$ $X$ $x^{3}>1$ $x>1$ $x_{0}=0{,}5$

{\begin{matrice}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})))&=&1{,}112\;141 \;637\;097,\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})))&=&\subliniază {0 {,}}909\;672\;693\;736,\\x_{3}&=&x_{2}-{\dfrac {f(x_{2})}{f'(x_{2})} }&=&\underline {0{,}86}7\;263\;818\;209,\\x_{4}&=&x_{3}-{\dfrac {f(x_{3})}{ f'(x_{3})}}&=&\underline {0{,}865\;47}7\;135\;298,\\x_{5}&=&x_{4}-{\dfrac { f(x_{4})}{f'(x_{4})}}&=&\underline {0{,}865\;474\;033\;1}11,\\x_{6}&= &x_{5}-{\dfrac {f(x_{5})}{f'(x_{5})}}&=&\underline {0{,}865\;474\;033\;102}. \end{matrice}}

Cifrele semnificative valide sunt subliniate . Se poate observa că numărul lor crește de la pas la pas (se dublează aproximativ cu fiecare pas): de la 1 la 2, de la 2 la 5, de la 5 la 10, ilustrând rata de convergență pătratică .

Condiții de utilizare

Să luăm în considerare o serie de exemple care indică deficiențele metodei.

Contraexemple

Dacă aproximarea inițială nu este suficient de aproape de soluție, atunci metoda poate să nu convergă.

Lăsa

f(x)=x^{3}-2x+2.

Apoi

x_{{n+1}}=x_{{n}}-{\frac {x_{n}^{3}-2x_{n}+2}{3x_{n}^{2}-2}}.

Să luăm zero ca aproximare inițială. Prima iterație va da unitatea ca o aproximare. La rândul său, al doilea va da din nou zero. Metoda va fi în buclă și nu va fi găsită nicio soluție. În general, construcția unei secvențe de aproximări poate fi foarte confuză .

Dacă derivata nu este continuă în punctul rădăcinii, atunci metoda poate diverge în orice vecinătate a rădăcinii.

Luați în considerare o funcție:

f(x)={\begin{cases}0,&x=0,\\x+x^{2}\sin \left({\dfrac {2}{x}}\right),&x\ neq 0.\end{cazuri}}

Atunci și peste tot, cu excepția 0. $f'(0)=1$ $f'(x)=1+2x\sin(2/x)-2\cos(2/x)$

În vecinătatea rădăcinii, derivata își schimbă semnul când se apropie de zero din dreapta sau din stânga. În timp ce pentru . $X$ $f(x)\geqslant xx^{2}>0$ $0<x<1$

Astfel, nu este mărginită în apropierea rădăcinii, iar metoda va diverge, chiar dacă funcția este diferențiabilă peste tot, derivata sa este diferită de zero la rădăcină, diferențiabilă la infinit peste tot, cu excepția rădăcinii, iar derivata sa este mărginită în jurul rădăcinii. . $f(x)/f'(x)$ $f$

Dacă nu există o derivată a doua la punctul rădăcină, atunci rata de convergență a metodei poate fi redusă considerabil.

Luați în considerare un exemplu:

f(x)=x+x^{4/3}.

Atunci și cu excepția cazului în care nu este definit. $f'(x)=1+(4/3)x^{1/3)$ $f''(x)=(4/9)x^{-2/3)$ $x=0$

La pasul următor, avem : $x_{n}$

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

Rata de convergență a secvenței rezultate este de aproximativ 4/3. Acesta este semnificativ mai mic decât 2, ceea ce este necesar pentru convergența pătratică, așa că în acest caz putem vorbi doar de convergență liniară, deși funcția este diferențiabilă continuu peste tot , derivata la rădăcină nu este egală cu zero și este infinit derivabilă peste tot . decât la rădăcină. $f$

Dacă derivata la punctul rădăcină este egală cu zero, atunci rata de convergență nu va fi pătratică, iar metoda în sine poate încheia căutarea prematur și poate oferi o aproximare incorectă pentru o anumită precizie.

Lăsa

f(x)=x^{2}.

Atunci și de aici . Astfel, convergența metodei nu este pătratică, ci liniară, deși funcția este infinit derivabilă peste tot. $f'(x)=2x$ $xf(x)/f'(x)=x/2$

Restricții

Fie dată ecuația , unde și este necesar să-i găsim soluția. $f(x)=0$ $f(x)\colon \mathbb {X} \to \mathbb {R}$

Mai jos este formularea teoremei principale, care ne permite să oferim condiții clare de aplicabilitate. Poartă numele matematicianului și economistului sovietic Leonid Vitalievici Kantorovich ( 1912-1986 ) .

teorema lui Kantorovich.

Dacă există constante astfel încât: $A,\;B,\;C$

${\frac {1}{|f'(x)|}}<A$ pe , adică există și nu este egal cu zero; $[a,\;b]$ $f'(x)$
$\left|{\frac {f(x)}{f'(x)}}\right|<B$ pe , adică limitat; $[a,\;b]$ $f(x)$
$\exists f''(x)$ pe , și ; $[a,\;b]$ $|f''(x)|\leqslant C\leqslant {\frac {1}{2AB))$

Mai mult, lungimea segmentului considerat . Atunci următoarele afirmații sunt adevărate: $|ab|<{\frac {1}{AB}}\left(1-{\sqrt {1-2ABC}}\right)$

există o rădăcină a ecuației ; $[a,\;b]$ $x^{*}$ $f(x)=0\colon \exists x^{*}\in [a,\;b]\colon f(x^{*})=0$
dacă , atunci succesiunea iterativă converge către această rădăcină: ; $x_{0}={\frac {a+b}{2}}$ $\left\{x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})))\right\}\to x^ {*}$
eroarea poate fi estimată prin formula . $|x^{*}-x_{n}|\leqslant {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}$

Din ultima afirmație a teoremei, în special, convergența pătratică a metodei urmează:

|x^{*}-x_{n}|\leqslant {\frac {B}{2^{n-1}}}(2ABC)^{2^{n-1}}={\frac {1}{2}}{\frac {B}{2^{n-2}}}\left((2ABC)^{2^{n-2}}\right)^{2}=\alpha | x^{*}-x_{n-1}|^{2}.

Apoi, constrângerile funcției inițiale vor arăta astfel: $f(x)$

funcția trebuie să fie limitată;
funcţia trebuie să fie netedă , de două ori diferenţiabilă ;
prima sa derivată este separată uniform de zero; $f'(x)$
derivata a doua a acesteia trebuie să fie uniform mărginită. $f''(x)$

Context istoric

Metoda a fost descrisă de Isaac Newton în manuscrisul On the Analysis by Equations of Infinite Series ( latina: De analysi per aequationes numero terminorum infinitas ) adresat lui Barrow în 1669 și în The Method of Fluxions and Infinite Series ( latina: De metodis fluxionum). et serierum infinitarum” ) sau „ Geometrie analitică ” ( lat. „Geometria analytica” ) în colecțiile de lucrări ale lui Newton, care a fost scrisă în 1671 . În scrierile sale, Newton introduce concepte precum extinderea unei funcții într- o serie , infinitezimale și fluxiuni ( derivate în sensul actual). Aceste lucrări au fost publicate mult mai târziu: prima a fost publicată în 1711 datorită lui William Johnson, a doua a fost publicată de John Colzon în 1736 după moartea creatorului. Cu toate acestea, descrierea metodei diferă semnificativ de expunerea sa actuală: Newton și-a aplicat metoda exclusiv la polinoame . El a calculat nu aproximări succesive , ci o succesiune de polinoame și, ca rezultat, a primit o soluție aproximativă . $x_{n}$ $X$

Metoda a fost publicată pentru prima dată în tratatul „Algebra” de John Wallis în 1685, la cererea căruia a fost descrisă pe scurt de însuși Newton. În 1690, Joseph Raphson a publicat o descriere simplificată în „Analysis aequationum universalis” ( latina: „Analysis aequationum universalis” ). Raphson a văzut metoda lui Newton ca fiind pur algebrică și și-a limitat aplicarea la polinoame, dar a descris metoda în termeni de aproximări succesive în loc de secvența mai dificil de înțeles de polinoame folosită de Newton. În cele din urmă, în 1740, metoda lui Newton a fost descrisă de Thomas Simpson ca o metodă iterativă de ordinul întâi pentru rezolvarea ecuațiilor neliniare folosind o derivată, așa cum este prezentată aici. În aceeași publicație, Simpson a generalizat metoda la cazul unui sistem de două ecuații și a remarcat că metoda lui Newton poate fi aplicată și problemelor de optimizare prin găsirea zeroului derivatei sau gradientului . $x_{n}$

În 1879, Arthur Cayley , în The Newton-Fourier imaginary problem, a fost primul care a subliniat dificultățile în generalizarea metodei lui Newton în cazul rădăcinilor imaginare ale polinoamelor de grad mai mare decât a doua și aproximațiile inițiale complexe. Această lucrare a deschis calea pentru studiul teoriei fractale .

Generalizări și modificări

Metoda secantei

Metoda secantei aferentă este metoda „aproximativă” a lui Newton și evită calcularea derivatei. Valoarea derivatei în formula iterativă este înlocuită cu estimarea acesteia pentru cele două puncte de iterație anterioare:

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

Astfel, formula principală are forma

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

Această metodă este similară cu cea a lui Newton, dar are o rată de convergență puțin mai mică. Ordinea de convergență a metodei este egală cu raportul de aur - 1,618 ...

Remarci. 1) Pentru a începe procesul iterativ, sunt necesare două valori diferite ale lui și . 2) Spre deosebire de „metoda Newton reală” (metoda tangentei), care necesită doar stocarea (și temporar în timpul calculelor și ), metoda secantei necesită salvarea , , , . 3) Se utilizează dacă calculul este dificil (de exemplu, necesită o cantitate mare de resurse ale mașinii: timp și/sau memorie). $x_{0}$ $x_{1}$
$x_{n)$ $f(x_{n})$ $f'(x_{n})$ $x_{n-1)$ $x_{n)$ $f(x_{n-1})$ $f(x_{n})$
$f'(x)$

Metoda unei tangente

Pentru a reduce numărul de apeluri la valorile derivatei unei funcții, se utilizează așa-numita metodă cu o singură tangentă.

Formula de iterație pentru această metodă este:

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

Esența metodei este de a calcula derivata o singură dată, în punctul inițial de aproximare , și apoi de a utiliza această valoare la fiecare iterație ulterioară: $x_{0}$

\alpha (x)=\alpha _{0}=-{\dfrac {1}{f'(x_{0}))).

Cu această alegere , următoarea egalitate este valabilă la punctul : $\alpha _{0}$ $x_{0}$

\varphi '(x_{0})=1+\alpha _{0}f'(x_{0})=0,

iar dacă segmentul pe care se presupune prezența unei rădăcini și se alege aproximarea inițială este suficient de mic, iar derivata este continuă, atunci valoarea nu va diferi foarte mult de și, prin urmare, graficul va trece aproape orizontal, intersectând linie dreaptă , care la rândul său va asigura convergența rapidă a secvenței punctelor de aproximare la rădăcină. $x^{*}$ $x_{0}$ $\varphi '(x)$ $\varphi '(x^{*})$ $\varphi '(x_{0})=0$ $y=\varphi (x)$ $y=x$

Această metodă este un caz special al metodei iterației simple . Are o ordine liniară de convergență.

Caz multidimensional

Să generalizăm rezultatul obţinut la cazul multidimensional.

Să fie necesar să găsim o soluție la sistem:

\left\{{\begin{array}{lcr}f_{1}(x_{1},\;x_{2},\;\ldots,\;x_{n})&=&0,\ \\ldots &&\\f_{m}(x_{1},\;x_{2},\;\ldots ,\;x_{n})&=&0.\end{array}}\right.

Alegând o valoare inițială , se găsesc aproximări succesive prin rezolvarea sistemelor de ecuații : ${\vec {x}}^{[0]}$ ${\vec {x}}^{[j+1]}$

f_{i}+\sum _{k=1}^{n}{\frac {\partial f_{i}}{\partial x_{k}}}(x_{k}^{[j+ 1 ]}-x_{k}^{[j]})=0,\qquad i=1,\;2,\;\ldots ,\;m,

unde . ${\vec {x}}^{[j]}=(x_{1}^{[j]},\;x_{2}^{[j]},\;\ldots ,\;x_ {n}^{[j]}),\quad j=0,\;1,\;2,\;\ldots$

Așa cum se aplică problemelor de optimizare

Să fie necesar să se afle minimul unei funcții a mai multor variabile . Această sarcină este echivalentă cu problema găsirii zeroului gradientului . Să aplicăm metoda lui Newton de mai sus: $f({\vec {x}})\colon \mathbb {R} ^{n}\la \mathbb {R}$ $\nabla f({\vec {x}))$

\nabla f({\vec {x}}^{[j]})+H({\vec {x}}^{[j]})({\vec {x}}^{[j +1]}-{\vec {x}}^{[j]})=0,\quad j=1,\;2,\;\ldots ,\;n,

unde este Hessianul funcției . $H({\vec {x)})$ $f({\vec {x)))$

Într-o formă iterativă mai convenabilă, această expresie arată astfel:

{\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-H^{-1}({\vec {x}}^{[ j]})\nabla f({\vec {x}}^{[j]}).

De remarcat că în cazul unei funcții pătratice, metoda lui Newton găsește un extremum într-o iterație.

Găsirea matricei Hessian este costisitoare din punct de vedere computațional și adesea nu este posibilă. În astfel de cazuri, metodele cvasi-newtoniene pot servi ca alternativă , în care o aproximare a matricei Hessian este construită în procesul de acumulare a informațiilor despre curbura funcției.

Metoda Newton-Raphson

Metoda Newton-Raphson este o îmbunătățire a metodei extreme a lui Newton descrisă mai sus. Principala diferență este că la următoarea iterație, una dintre metodele de optimizare unidimensională selectează pasul optim:

{\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda _{j}H^{-1}({\vec { x}}^{[j]})\nabla f({\vec {x}}^{[j]}),

unde Pentru a optimiza calculele, se folosește următoarea îmbunătățire: în loc să recalculăm Hessianul funcției obiectiv la fiecare iterație , ne limităm la aproximarea inițială și o actualizăm o singură dată în pași sau nu o actualizăm deloc. $\lambda _{j}=\arg \min _{\lambda }f({\vec {x}}^{[j]}-\lambda H^{-1}({\vec {x} }^{[j]})\nabla f({\vec {x}}^{[j]})).$ $H(f({\vec {x))^{[0]}))$ $m$

Aplicat problemelor cu cele mai mici pătrate

În practică, există adesea sarcini în care este necesară ajustarea parametrilor liberi ai unui obiect sau ajustarea modelului matematic la date reale. În aceste cazuri, apar probleme cu cele mai mici pătrate :

F({\vec {x)))=\|{\vec {f}}({\vec {x}})\|=\sum _{{i=1}}^{m}f_{i} ^{2}({\vec {x}})=\sum _{{i=1}}^{m}(\varphi _{i}({\vec {x}})-{\mathcal {F }}_{i})^{2}\to \min .

Aceste probleme se disting printr-un tip special de gradient și matrice Hessiană :

\nabla F({\vec {x)))=2J^{T}({\vec {x))){\vec {f}}({\vec {x}}),

H({\vec {x)))=2J^{T}({\vec {x)))J({\vec {x)))+2Q({\vec {x))),\qquad Q ({\vec {x)))=\sum _{{i=1}}^{m}f_{i}({\vec {x}})H_{i}({\vec {x}}) ,

unde este matricea Jacobi a funcției vectoriale , este matricea hessiană pentru componenta sa . $J({\vec {x)))$ ${\vec {f))({\vec {x))}$ $H_{i}({\vec {x)))$ $f_{i}({\vec {x)))$

Apoi următorul pas este determinat din sistem: ${\vec {p}}$

\left[J^{T}({\vec {x}})J({\vec {x}})+\sum _{{i=1}}^{m}f_{i}({\vec {x)))H_{i}({\vec {x)))\right]{\vec {p}}=-J^{T}({\vec {x}}){\vec {f} }({\vec {x}}).

Metoda Gauss-Newton

Metoda Gauss-Newton se bazează pe presupunerea că termenul domină peste . Această cerință nu este îndeplinită dacă reziduurile minime sunt mari, adică dacă norma este comparabilă cu valoarea proprie maximă a matricei . În caz contrar, puteți scrie: $J^{T}({\vec {x)))J({\vec {x)))$ $Q({\vec {x)))$ $\|{\vec {f}}({\vec {x}})\|$ $J^{T}({\vec {x)))J({\vec {x)))$

J^{T}({\vec {x}})J({\vec {x}}){\vec {p}}=-J^{T}({\vec {x}}){\vec {f}}({\vec {x}}).

Astfel, atunci când norma este aproape de zero, iar matricea are rang de coloană complet , pasul diferă puțin de cel newtonian (ținând cont de ), iar metoda poate realiza o rată de convergență pătratică, deși derivatele secunde nu sunt luate în considerare. cont. O îmbunătățire a metodei este algoritmul Levenberg-Marquardt bazat pe considerații euristice . $\|Q({\vec {x)))\|$ $J({\vec {x)))$ ${\vec {p}}$ $Q({\vec {x)))$

Generalizare la plan complex

Până acum, în descrierea metodei, au fost folosite funcții care realizează mapări în setul de valori reale . Cu toate acestea, metoda poate fi aplicată și pentru a găsi zeroul unei funcții a unei variabile complexe . Cu toate acestea, procedura rămâne aceeași:

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

Un interes deosebit este alegerea aproximării inițiale . Având în vedere faptul că o funcție poate avea mai multe zerouri, în cazuri diferite metoda poate converge către valori diferite și este destul de firesc să dorim să aflăm care zone vor asigura convergența către o anumită rădăcină. Această întrebare l-a interesat pe Arthur Cayley încă din 1879 , dar a fost posibil să o rezolve abia în anii 70 ai secolului XX , odată cu apariția tehnologiei computerelor. S-a dovedit că la intersecțiile acestor regiuni (de obicei sunt numite regiuni de atracție ), se formează așa-numitele fractali - infinite figuri geometrice auto-similare. $z_{0}$

Datorită faptului că Newton și-a aplicat metoda exclusiv la polinoame , fractalii formați ca urmare a unei astfel de aplicații au devenit cunoscuți ca fractalii lui Newton sau piscinele lui Newton .

Implementare

scala

obiect NewtonMethod { precizie val = 1e-6 Metoda @tailrec def ( x0 : Double , f : Double => Double , dfdx : Double => Double , e : Double ): Double = { val x1 = x0 - f ( x0 ) / dfdx ( x0 ) if ( abs ( x1 ) - x0 ) < e ) x1 else metoda ( x1 , f , dfdx , e ) } def g ( C : dublu ) = ( x : dublu ) => x * x - C def dgdx ( x : Double ) = 2 * x def sqrt ( x : Double ) = x potriviți { case 0 => 0 case x if ( x < 0 ) => Double . NaN caz x dacă ( x > 0 ) => metoda ( x / 2 , g ( x ), dgdx , precizie ) } }

Python

din math import sin , cos din tastarea import Callable import unittest def newton ( f : apelabil [[ float ], float ], f_prime : apelabil [[ float ], float ], x0 : float , eps : float = 1e-7 , kmax : int = 1e3 ) -> float : """ rezolvă f(x) = 0 prin metoda lui Newton cu precizie eps :param f: f :param f_prime: f' :param x0: punctul de plecare :param eps: precizie dorită :return: rădăcina lui f(x) = 0 """ x , x_prev , i = x0 , x0 + 2 * eps , 0 în timp ce abs ( x - x_prev ) >= eps și i < kmax : x , x_prev , i = x - f ( x ) / f_prime ( x ), x , i + 1 întoarce x clasa TestNewton ( test unitar . TestCase ): def test_0 ( self ): def f ( x : float ) -> float : return x ** 2 - 20 * sin ( x ) def f_prime ( x : float ) -> float : return 2 * x - 20 * cos ( x ) x0 , x_star = 2 , 2,7529466338187049383 sine . assertAlmostEqual ( newton ( f , f_prim , x0 ), x_star ) if __name__ == '__main__' : unittest . principal ()

PHP

<?php // PHP 5.4 function newtons_method ( $a = - 1 , $b = 1 , $f = function ( $x ) { return pow ( $x , 4 ) - 1 ; }, $derivată_f = funcție ( $x ) { return 4 * pow ( $x , 3 ); }, $eps = 1E-3 ) { $xa = $a ; $xb = $b ; $iteratie = 0 ; în timp ce ( abs ( $xb ) > $eps ) { $p1 = $f ( $xa ); $q1 = $derivată_f ( $xa ); $xa -= $p1 / $q1 ; $xb = $p1 ; ++ $iterație ; } return $xa ; }

Octava

funcția res = nt () eps = 1e-7 ; x0_1 = [ - 0,5 , 0,5 ]; max_iter = 500 ; xopt = new (@ resh , eps , max_iter ); xopt endfunction function a = new ( f, eps, max_iter ) x = - 1 ; p0 = 1 ; i = 0 _ în timp ce ( abs ( p0 ) > = eps ) [ p1 , q1 ]= f ( x ); x = x - p1 / q1 ; p0 = p1 ; i = i + 1 ; sfârşitul i a = x ; funcția finală [p,q] = resh ( x ) % p= -5*x.^5+4*x.^4-12*x.^3+11*x.^2-2*x+1; p = - 25 * x .^ 4 + 16 * x .^ 3 - 36 * x .^ 2 + 22 * x - 2 ; q = - 100 * x .^ 3 + 48 * x .^ 2 - 72 * x + 22 ; funcția finală

Delphi

// funcţia funcţie calculată fx ( x : Double ) : Double ; începe Rezultatul := x * x - 17 ; sfârşitul ; // funcţie derivată a funcţiei f(x) dfx ( x : Double ) : Double ; începe Rezultat := 2 * x ; sfârşitul ; rezolvarea funcției ( fx , dfx : TFunc < Double , Double >; x0 : Double ) : Double ; const eps = 0,000001 ; var x1 : dublu ; începe x1 := x0 - fx ( x0 ) / dfx ( x0 ) ; // prima aproximare în timp ce ( Abs ( x1 - x0 ) > eps ) începe // până când se atinge precizia 0,000001 x0 := x1 ; x1 := x1 - fx ( x1 ) / dfx ( x1 ) ; // aproximările ulterioare se termină ; Rezultat := x1 ; sfârşitul ; // Apel solve ( fx , dfx , 4 ) ;

C++

#include <iostream> #include <math.h> double fx ( double x ) { return x * x - 17 ;} // funcția calculată double dfx ( double x ) { return 2 * x ;} // derivată funcție typedef double ( * function )( double x ); // atribuirea funcției de tip rezolvare dublă ( funcția fx , funcția dfx , dublu x0 , dublu eps = 1e-8 ) { dublu xi = x0 ; //Punctul curent la a i-a iterație în timp ce ( fabs ( fx ( xi )) >= eps ) // până când se atinge precizia 0,00000001 xi = xi - fx ( xi ) / dfx ( xi ); // aproximările ulterioare returnează xi ; } int main () { std :: cout << solve ( fx , dfx , 4 ) << std :: endl ; returnează 0 ; }

C

typedef double ( * function )( double x ); Metoda Tangente duble ( funcția f , funcția df , xn dublu , eps dublu ) { dublu x1 = xn - f ( xn ) / df ( xn ); dublu x0 = xn ; în timp ce ( abs ( x0 - x1 ) > eps ) { x0 = x1 ; x1 = x1 - f ( x1 ) / df ( x1 ); } întoarcere x1 ; } //Selectați estimarea inițială xn = Funcția mea ( A ) * Derivată My2 ( A ) > 0 ? B : A ; double MyFunction ( double x ) { return ( pow ( x , 5 ) - x - 0.2 ); } //Funcția ta double MyDerivative ( double x ) { return ( 5 * pow ( x , 4 ) - 1 ); } //Prima derivată double My2Derivative ( double x ) { return ( 20 * pow ( x , 3 )); } //Derivată a doua //Exemplu de apelare a unei funcții dublu x = TangentsMethod ( MyFunction , MyDerivative , xn , 0.1 )

Haskell

import Data.List ( iterare ' ) principal :: IO () principal = print $ rezolva ( \ x -> x * x - 17 ) ( * 2 ) 4 -- Funcția de rezolvare este universală pentru toate tipurile reale ale căror valori pot fi comparate. rezolva = esolve 0,000001 esolve epsilon func deriv x0 = fst . head $ dropWhile pred pairs where pred ( xn , xn1 ) = ( abs $ xn - xn1 ) > epsilon -- Funcția pred determină dacă a fost atinsă precizia necesară. next xn = xn - func xn / deriv xn -- Următoarea funcție calculează o nouă aproximare. iters = iterate ' next x0 -- O listă infinită de iterații. pairs = zip iters ( tail iters ) -- O listă infinită de perechi de iterații de forma: [(x0, x1), (x1, x2) ..].

Literatură

Akulich I. L. Programare matematică în exemple și sarcini: Proc. indemnizație pentru economia studenților. specialist. universități. - M . : Şcoala superioară, 1986. - 319 p. : bolnav. - BBK 22.1 A44 . - UDC 517,8 .
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Metode de calcul pentru ingineri: Proc. indemnizatie. - M . : Şcoala superioară, 1994. - 544 p. : bolnav. - BBK 32,97 A62 . - UDC 683.1 . — ISBN 5-06-000625-5 .
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Metode numerice. - Ed. a 8-a. - M . : Laboratorul de Cunoștințe de bază, 2000.
Vavilov S. I. Isaac Newton . - M .: Ed. Academia de Științe a URSS, 1945.
Volkov E. A. Metode numerice. — M. : Fizmatlit, 2003.
Gill F., Murray W., Wright M. Optimizare practică. Pe. din engleza. — M .: Mir, 1985.
Korn G., Korn T. Manual de matematică pentru oameni de știință și ingineri. - M . : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Fundamentele matematice ale ciberneticii. - Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmi pentru rezolvarea problemelor de programare neliniară. — M .: MEPhI, 1982.
Morozov AD Introducere în teoria fractalilor. — MEPhI, 2002.

Vezi și

Link -uri

„Piscinele lui Newton” la fractalworld.xaoc.ru
„Isaac Newton” la www.scottish-wetlands.org
„Lucrări matematice ale lui Kantorovich” pe site-ul Institutului de Matematică al SB RAS
Hazewinkel, Michiel, ed. (2001), metoda Newton , Enciclopedia matematicii , Springer , ISBN 978-1-55608-010-4
Weisstein, Metoda lui Eric W. Newton (engleză) pe site-ul Wolfram MathWorld .
Metoda lui Newton, Citizendium.
Mathews, J., Metodele Newton accelerate și modificate, Note de curs.
Wu, X., Rădăcinile ecuațiilor, Note de curs.

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică