Eseu pe tema:
-
introducere
- 1 Descrierea metodei
- 1.1 Justificare
- 1.2 Interpretare geometrică
- 1.3 Algoritmul
- 1.4 Exemplu
- 2 Condiții de utilizare
- 2.1 Eșantioane contrare
- 2.2 Restricții
- 3 Istoricul istoric
- 4 Generalizări și modificări
- 4.1 Metoda cu un singur tangent
- 4.2 Cazul multidimensional
- 4.3 Aplicate la probleme de optimizare
- 4.4 Metoda Newton-Raphson
- 4.5 Se aplică la problemele cu cele mai mici pătrate
- 4.6 Metoda Gauss-Newton
- 4.7 Extinderea la planul complex
notițe
Metoda lui Newton. Algoritmul lui Newton (cunoscut și ca metoda tangentă) este o metodă numerică iterativă pentru găsirea rădăcinii (zero) a unei funcții date. Metoda a fost inițial propusă de fizicianul englez, matematicianul și astronomul Isaac Newton (1643-1727), sub numele căruia și-a câștigat faima. Soluția este căutată prin construirea unor aproximări succesive și se bazează pe principiile iterației simple. Metoda are convergență patrată. Metoda este îmbunătățită prin metoda acordurilor și tangentelor. Metoda lui Newton poate fi, de asemenea, utilizată pentru a rezolva problemele de optimizare în care este necesar să se determine zero-ul primului derivat sau gradient în cazul unui spațiu multidimensional.
1. Descrierea metodei
1.1. Argumentare
Pentru a rezolva numeric ecuația prin metoda simplă de iterație, aceasta trebuie redusă la următoarea formă: unde este maparea contracției.
Pentru cea mai bună convergență a metodei la următorul punct de aproximare, condiția trebuie îndeplinită. Soluția acestei ecuații este căutată sub formă, atunci:
Sub ipoteza că punctul de aproximare este "suficient de apropiat" de rădăcină și că funcția dată este continuă, formula finală pentru aceasta este:
Având în vedere acest lucru, funcția este definită de expresia:
Această funcție realizează o mapare a contracțiilor în vecinătatea rădăcinii [1]. iar algoritmul pentru găsirea soluției numerice a ecuației se reduce la o procedură iterativă de calcul:
Prin teorema lui Banach, secvența de aproximări tinde spre rădăcina ecuației.
Ilustrația metodei lui Newton (albastru reprezintă funcția a cărei zero se găsește, roșu este tangenta la următorul punct de aproximare). Aici putem vedea că aproximarea ulterioară este mai bună decât cea anterioară.
1.2. Interpretare geometrică
Ideea de bază a metodei este următoarea: o aproximare inițială este stabilită în apropierea rădăcinii putative apoi construită tangent la punctul de aproximarea funcției, care este la intersecția cu abscisa. Acest punct este considerat urmatoarea aproximare. Și așa mai departe, până când se obține precizia necesară.
Să fie o funcție reală definită pe segment și să se diferențieze pe ea. Apoi, formula calculului aproximativ iterativ poate fi dedusă după cum urmează:
unde α este unghiul de înclinare a tangentei în punctul respectiv.
Prin urmare, expresia necesară pentru este:
Procesul iterativ începe cu unele X0 aproximare inițială (cu cât mai aproape de zero, cu atât mai bine, dar în cazul în ipoteza găsirii unei soluții disponibile, prin încercare și eroare, puteți restrânge intervalul de valori posibile, folosind teorema valorilor intermediare).
1.3. algoritmul
- Setați aproximația inițială x0.
- În timp ce condiția de oprire nu este îndeplinită, care poate fi considerată ca sau (adică eroarea în limitele cerute), se calculează o nouă aproximație :.
1.4. exemplu
Ilustrația aplicării metodei Newton la funcția f (x) = cosx - x 3 cu aproximația inițială la punctul x0 = 0,5.
Conform metodei de determinare practică, rata convergenței poate fi estimată ca tangenta pantei graficului de convergență, adică în acest caz este egală cu două.
Considerăm problema găsirii unui x pozitiv. pentru care cosx = x 3. Această problemă poate fi reprezentată ca fiind problema găsirii zero a funcției f (x) = cosx - x 3. Avem expresia derivatului f '(x) = - sinx - 3x 2. Deoarece pentru toate x și x 3> 1 pentru x> 1. este evident că soluția se află între 0 și 1. Să luăm x0 = 0.5 ca aproximație inițială. atunci:
Sublinierea marchează cifrele corecte semnificative. Se poate observa că numărul lor crește de la pas la pas (aproximativ dublarea cu fiecare pas): de la 1 la 2, de la 2 la 5, de la 5 la 10, ilustrând viteza patratică a convergenței.
2. Condiții de utilizare
O ilustrare a divergenței metodei Newton aplicată unei funcții cu o aproximare inițială la un punct.
Să luăm în considerare o serie de exemple care indică dezavantajele metodei.
2.1. contraexemple
- Dacă aproximația inițială nu este suficient de apropiată de soluție, atunci metoda poate să nu converge.
Luăm zero ca aproximație inițială. Prima iterație dă unitate ca aproximație. La rândul său, al doilea din nou dă zero. Metoda se blochează și soluția nu va fi găsită. În cazul general, construirea unei secvențe de aproximare poate fi foarte confuză.
Graficul derivatului funcției pe măsură ce se apropie de zero de la dreapta.
- Dacă derivatul nu este continuu în punctul rădăcinii, atunci metoda se poate diferenția în orice vecinătate a rădăcinii.
Apoi și peste tot, cu excepția 0.
În vecinătatea rădăcinii, modificările derivatelor semnează pe măsură ce x se apropie de zero la dreapta sau la stânga. În acel moment, în ceea ce privește.
Astfel, nu se limitează la vecinătatea rădăcinii, iar metoda va diverge, deși funcția de pretutindeni diferențiabilă, derivatul său nu este zero la rădăcină, este infinit diferențiabilă pretutindeni, cu excepția la rădăcină, iar derivatul său este limitat în vecinătatea rădăcinii.
- Dacă nu există un al doilea derivat la punctul rădăcină, atunci rata de convergență a metodei poate fi redusă semnificativ.
Apoi și cu excepția cazului în care nu este definită.
În pasul următor avem:
Rata de convergență a secvenței rezultate este de aproximativ 4/3. Acest lucru este semnificativ mai mic de 2, de dorit pentru convergența pătratice, astfel încât, în acest caz, putem vorbi doar de convergență liniară, deși funcția este continuu diferențiabilă pretutindeni, derivatul nu este zero la rădăcină, și infinit diferențiabilă pretutindeni, cu excepția la rădăcină.
- Dacă derivatul la punctul rădăcină este zero, atunci rata convergenței nu va fi patratică, iar metoda în sine poate opri prematur căutarea și poate da o aproximație care este incorectă pentru o anumită precizie.
Apoi și de aici. Astfel, convergența metodei nu este patratică, ci liniară, deși funcția este peste tot unde poate fi diferențiată infinit.
2.2. restricţii
Să se dea ecuația, acolo unde este necesar să găsim soluția.
Mai jos este formularea teoremei principale, care ne permite să oferim condiții clare de aplicabilitate. Este numit după matematicianul sovietic și economist, Premiul Nobel pentru Economie în 1975 „pentru contribuția sa la teoria alocării optime a resurselor“ KANTOROVICH KANTOROVICH (1912-1986) și este una dintre numeroasele teorii care rezultă din cercetările sale științifice.
Dacă există constante astfel încât:
- pe, care este, există și nu este zero;
- pe care este limitat;
- pe, și;
Și lungimea segmentului considerat. Apoi afirmă următoarele afirmații:
- există o rădăcină a ecuației;
- dacă, atunci secvența de iterație converge la această rădăcină :;
- eroarea poate fi estimată prin formula.
Din ultimele afirmații ale teoremei, în special convergența patratică a metodei urmează:
Apoi restricțiile privind funcția inițială vor arăta astfel:
- funcția trebuie să fie limitată;
- funcția trebuie să fie netedă, de două ori diferențiată;
- primul său derivat este separat uniform de zero;
- al doilea derivat al acestuia trebuie să fie limitat uniform.
3. Istoricul istoric
În 1879, Arthur Cayley în lucrarea sa „Problema numerelor complexe Newton - Fourier“ (. Engleză «Newton-Fourier imaginar problemă») a fost primul care a remarcat dificultatea în generalizarea metodei lui Newton pentru cazul rădăcinilor imaginare ale polinoame de grad mai mare decât al doilea și cuprinzătoare aproximările inițiale. Această lucrare a deschis calea studierii teoriei fractalilor.
4. Generalizări și modificări
Ilustrație a aproximărilor succesive ale metodei unei tangente aplicate unei funcții cu aproximație inițială la un punct.
4.1. Metoda one-tangentă
Pentru a reduce numărul apelurilor la valorile funcției derivate, se folosește așa-numita metodă cu un singur tangent.
Formula de iterație pentru această metodă este:
Esența metodei este de a calcula derivatul o singură dată, în punctul de aproximare inițială, și apoi utilizați această valoare la fiecare iterație ulterioară:
Cu această alegere în acest punct, se aplică următoarea egalitate:
iar în cazul în care segmentul în care se presupune prezența rădăcinii și aproximarea inițială este ales suficient de mică, iar derivatul este continuă, valoarea nu va fi mult diferite și, prin urmare, graficul va avea loc aproape orizontal, trecând linia dreaptă, care, la rândul său, va oferi o convergență rapidă a punctelor de aproximare la rădăcină.
Această metodă poate fi de asemenea considerată ca modernizarea metodei acordurilor (secante), unde numărul trebuie ales egal cu
4.2. Cazul multidimensional
Generalizăm rezultatul în cazul multidimensional.
Să fie necesară găsirea unei soluții la sistem:
Alegerea unei anumite valori inițiale, aproximări succesive se găsesc prin rezolvarea sistemelor de ecuații:
4.3. Aplicată la probleme de optimizare
Să fie necesar să găsim minimul unei funcții a mai multor variabile. Această problemă este echivalentă cu problema găsirii zero a gradientului. Să aplicăm metoda Newton descrisă mai sus:
unde este funcția hessiană.
Într-o formă iterativă mai convenabilă, această expresie arată astfel:
Trebuie remarcat faptul că, în cazul unei funcții patrate, metoda lui Newton găsește un extremum într-o singură iterație.
Găsirea matricei hessiană este asociată cu costuri computationale mari și de multe ori nu este posibilă. În astfel de cazuri, metode cvasi-newtoniene pot servi ca o alternativă, în care aproximarea matricei Hesse este construită în procesul de acumulare a informațiilor despre curbura funcției.
4.4. Metoda Newton-Raphson
Metoda Newton-Raphson este o îmbunătățire a metodei lui Newton de a găsi extrema descrisă mai sus. Principala diferență este că la următoarea iterație una dintre metodele de optimizare unidimensională selectează pasul optim:
care este folosit pentru a optimiza calcul următoarele îmbunătățiri: în loc de la fiecare iterație re-calcula Hessianul a funcției obiectiv este limitată la aproximarea inițială și o actualizează o singură dată în etapele sau nu actualizate deloc.
4.5. Aplicată la cele mai puțin pătrate probleme
În practică, există adesea probleme în care este necesar să se adapteze parametrii liberi ai unui obiect sau să se adapteze modelul matematic la date reale. În aceste cazuri apar problemele cu cele mai mici pătrate:
Aceste probleme se disting printr-un tip special de gradient și matricea hessiană:
unde este matricea Jacobi a funcției vectoriale, este matricea hessiană a componentei sale.
Apoi următoarea direcție este determinată de sistem:
4.6. Metoda Gauss-Newton
Metoda Gauss-Newton se bazează pe ipoteza că termenul domină peste. Această cerință nu este respectată dacă discrepanțele minime sunt mari, adică dacă norma este comparabilă cu valoarea maximă proprie a matricei. În caz contrar, puteți scrie:
Astfel, atunci când rata este aproape de zero, iar matricea are deplină direcție rang stolbtsevoy diferă puțin de Newtonian (subiect), iar metoda poate atinge rata de convergență pătratică, cu toate că a doua și derivații nu sunt capturate. Îmbunătățirea metodei este algoritmul Levenberg-Marquardt, pe baza considerentelor euristice.
4.7. Generalizarea la planul complex
Bazine Newton pentru un polinom de gradul cinci. În culori diferite, zonele de atracție pentru rădăcini diferite sunt vopsite. Zonele mai întunecate corespund mai multor iterații.
Până în prezent, descrierea metodei a utilizat funcții care realizează mapări într-un set de valori reale. Cu toate acestea, metoda poate fi de asemenea utilizată pentru a găsi zero la o funcție a unei variabile complexe. Procedura rămâne neschimbată:
Un interes deosebit este alegerea aproximării inițiale. Datorită faptului că funcția poate avea mai multe zerouri, în diferite cazuri, metoda poate converge la valori diferite, și este destul de firesc să aibă dorința de a afla care oferă zone de convergență într-o anumită rădăcină. Această întrebare interesată de Arthur Cayley în 1879, dar nu a fost posibil să se rezolve până în anii 1970 cu apariția tehnologiei computerelor. Sa dovedit că, la intersecțiile acestor domenii (acestea sunt numite domenii de atractie) sunt formate așa-numitele fractali - forme geometrice auto-similare infinit.
Pentru că Newton a aplicat metoda lui numai polinoame, fractali, formate ca urmare a unor astfel de utilizare, a dobândit numele lui Newton sau Newton fractali piscine.
literatură
notițe
- Dovada: Fie o funcție de o variabilă reală este de două ori continuu diferențiabilă în domeniul său, al cărui derivat este zero, nicăieri: Și trebuie să demonstreze că funcția efectuează o mapare contracție lângă rădăcina ecuației. Având în vedere diferențiabilitatea continuă a funcției și inegalitatea primului său derivat, zero este continuă. Derivatul este: În condițiile impuse, este, de asemenea, continuu. Să - rădăcina necesară a ecuației, prin urmare, în vecinătatea sa: Apoi, în conformitate cu teorema: Având în vedere faptul că, în aceeași vecinătate a deltei se realizează: Astfel, funcția obținută în apropierea rădăcinii efectuează o cartografiere contracție.
Articole similare
Trimiteți-le prietenilor: