Chinuiți la școală pentru rezolvarea ecuațiilor din lecțiile de matematică, mulți elevi sunt adesea siguri că își pierd timpul și, totuși, o astfel de abilitate va fi utilă în viață nu numai celor care decid să calce pe urmele lui Descartes, Euler sau Lobaciovski.

În practică, de exemplu, în medicină sau economie, există adesea situații în care un specialist trebuie să afle când concentrația substanței active a unui anumit medicament atinge nivelul necesar în sângele pacientului sau este necesar să se calculeze timpul. necesare pentru ca o anumită afacere să devină profitabilă.

Cel mai adesea, vorbim despre rezolvarea ecuațiilor neliniare tipuri variate. Pentru a face acest lucru cât mai repede posibil, mai ales cu utilizarea computerelor, metodele numerice permit. Sunt bine studiate și și-au dovedit de mult eficacitatea. Printre acestea se numără metoda tangentei lui Newton, care face obiectul acestui articol.

Formularea problemei

În acest caz, există o funcție g, care este definită pe segmentul (a, b) și o preia anumite valori, adică fiecare x aparținând (a, b) poate fi asociat număr specific g(x).

Este necesar să se stabilească toate rădăcinile ecuației din intervalul dintre punctele a și b (inclusiv capete), pentru care funcția este setată la zero. Evident, acestea vor fi punctele de intersecție ale lui y = g(x) cu OX.

În unele cazuri, este mai convenabil să înlocuiți g(x)=0 cu unul similar, g 1 (x) = g 2 (x). În acest caz, abscisele (valoarea x) ale punctelor de intersecție ale graficelor g 1 (x) și g 2 (x) acționează ca rădăcini.

Rezolvarea unei ecuații neliniare este, de asemenea, importantă pentru problemele de optimizare pentru care condiția extremul local- conversia la 0 a derivatei functiei. Cu alte cuvinte, o astfel de problemă poate fi redusă la găsirea rădăcinilor ecuației p(x) = 0, unde p(x) este identic cu g"(x).

Metode de rezolvare

Pentru unele tipuri de ecuații neliniare, cum ar fi ecuațiile pătrate sau trigonometrice simple, rădăcinile pot fi găsite în moduri destul de simple. În special, fiecare elev cunoaște formulele, cu ajutorul cărora puteți găsi cu ușurință valorile argumentului punctelor în care trinomul pătrat este zero.

Metodele de extragere a rădăcinilor ecuațiilor neliniare sunt de obicei împărțite în analitice (directe) și iterative. În primul caz, soluția dorită are forma unei formule, cu ajutorul căreia, pentru un anumit număr de operații aritmetice, puteți găsi valoarea rădăcinilor dorite. Au fost dezvoltate metode similare pentru exponențiale, trigonometrice, logaritmice și simple ecuații algebrice. În rest, trebuie să folosiți metode numerice speciale. Sunt ușor de implementat cu ajutorul computerelor, care vă permit să găsiți rădăcinile cu precizia necesară.

Printre acestea se numără și așa-numita metodă numerică a tangentelor, cea din urmă propusă de marele om de știință Isaac Newton la sfârșitul secolului al XVII-lea. În secolele următoare, metoda a fost îmbunătățită în mod repetat.

Localizare

Metodele numerice pentru rezolvarea ecuațiilor complexe care nu au soluții analitice sunt de obicei efectuate în 2 etape. Mai întâi trebuie să le localizați. Această operație constă în găsirea unor astfel de segmente pe OX pe care există o rădăcină a ecuației care se rezolvă.

Să luăm în considerare un segment. Dacă g(x) pe ea nu are discontinuități și ia valori de diferite semne la punctele de capăt, atunci între a și b sau în sine există cel puțin 1 rădăcină a ecuației g(x) = 0. fi unic, se cere ca g(x) să fie monoton. După cum se știe, va avea o astfel de proprietate cu condiția ca g’(x) să aibă semn constant.

Cu alte cuvinte, dacă g(x) nu are discontinuități și crește sau scade monoton, iar valorile sale la punctele finale nu au aceleași semne, atunci există 1 și doar 1 rădăcină g(x).

În acest caz, ar trebui să știți că acest criteriu nu va funcționa pentru rădăcinile ecuațiilor care sunt multiple.

Rezolvarea ecuației prin împărțirea la jumătate

Înainte de a lua în considerare tangente numerice mai complexe și varietățile sale), merită să vă familiarizați cel mai mult într-un mod simplu identificarea rădăcinilor. Se numește dihotomie și se referă la găsirea intuitivă a rădăcinilor pe baza teoremei că, dacă pentru g (x), continuu pe, condiția diferitelor semne este îndeplinită, atunci pe segmentul luat în considerare există cel puțin 1 rădăcină g ( x) = 0.

Pentru a-l găsi, trebuie să împărțiți segmentul în jumătate și să desemnați punctul de mijloc ca x 2 . Atunci sunt posibile două opțiuni: g (x 0) * g (x 2) sau g (x 2) * g (x 1) sunt egale sau mai mici de 0. O alegem pe cea pentru care una dintre aceste inegalități este adevărată. Repetăm procedura descrisă mai sus până când lungimea devine mai mică decât o anumită valoare preselectată care determină acuratețea determinării rădăcinii ecuației pe .

Avantajele metodei includ fiabilitatea și simplitatea acesteia, iar dezavantajul este necesitatea de a identifica inițial punctele în care g(x) ia semne diferite, deci nu poate fi folosit pentru rădăcini cu multiplicitate chiar. În plus, nu se generalizează în cazul unui sistem de ecuații sau când vine vorba de rădăcini complexe.

Exemplul 1

Să dorim să rezolvăm ecuația g(x) = 2x 5 + x - 1 = 0. Pentru a nu căuta mult timp un segment potrivit, construim un grafic folosind, de exemplu, binecunoscutul program Excel . Vedem că este mai bine să luăm valori din interval ca segment pentru localizarea rădăcinii. Putem fi siguri că cel puțin o rădăcină a ecuației dorite există pe ea.

g "(x) \u003d 10x 4 + 1, adică aceasta este o funcție crescătoare monotonă, prin urmare există doar o rădăcină pe segmentul selectat.

Înlocuiți punctele finale în ecuație. Avem 0 și respectiv 1. La primul pas, luăm ca soluție punctul 0,5. Atunci g(0,5) = -0,4375. Deci, următorul segment pentru împărțirea la jumătate va fi. Punctul său de mijloc este 0,75. În ea, valoarea funcției este 0,226. Luăm în considerare segmentul și punctul său de mijloc, care este situat în punctul 0,625. Calculați valoarea lui g(x) la 0,625. Este egal cu -0,11, adică negativ. Pe baza acestui rezultat, alegem segmentul . Obținem x = 0,6875. Atunci g(x) = -0,00532. Dacă precizia soluției este 0,01, atunci putem presupune că rezultatul dorit este 0,6875.

Baza teoretica

Această metodă de găsire a rădăcinilor folosind metoda tangentei lui Newton este populară datorită convergenței sale foarte rapide.

Se bazează pe faptul dovedit că, dacă x n este o aproximare a unei rădăcini f(x)=0 astfel încât f" C 1 , atunci următoarea aproximare va fi în punctul în care ecuația tangentei la f(x) dispare. , adică

Înlocuiți x = x n+1 și setați y la zero.

Apoi tangenta arată astfel:

Exemplul 2

Să încercăm să folosim metoda tangentei clasice a lui Newton și să găsim o soluție la o ecuație neliniară care este dificil sau imposibil de găsit analitic.

Să fie necesar să se dezvăluie rădăcinile pentru x 3 + 4x - 3 = 0 cu o anumită precizie, de exemplu 0,001. După cum știți, graficul oricărei funcții sub forma unui polinom de grad impar trebuie să traverseze axa OX cel puțin o dată, adică nu există niciun motiv să ne îndoim de existența rădăcinilor.

Înainte de a rezolva exemplul nostru folosind metoda tangentei, reprezentăm f (x) \u003d x 3 + 4x - 3 punct cu punct. Acest lucru este foarte ușor de făcut, de exemplu, folosind o foaie de calcul Excel. Din graficul rezultat, se va vedea că se intersectează cu axa OX și funcția y \u003d x 3 + 4x - 3 crește monoton. Putem fi siguri că ecuația x 3 + 4x - 3 = 0 are o soluție și este unică.

Algoritm

Orice rezolvare a ecuațiilor prin metoda tangentei începe cu calculul lui f "(x). Avem:

Apoi derivata a doua va arăta ca x * 6.

Folosind aceste expresii, putem scrie o formulă pentru identificarea rădăcinilor ecuației folosind metoda tangentei sub forma:

În continuare, este necesar să se aleagă o aproximare inițială, adică să se determine ce punct să se considere ca punct de plecare (rev. x 0) pentru procesul iterativ. Luăm în considerare capetele segmentului. Ne este potrivită cea pentru care condiția funcției și derivata a 2-a a acesteia la x 0 este adevărată. După cum puteți vedea, atunci când înlocuiți x 0 = 0, este încălcat, dar x 0 = 1 este destul de potrivit.

atunci dacă ne interesează rezolvarea prin metoda tangentelor cu acuratețe e, atunci valoarea lui x n poate fi considerată ca satisfăcând cerințele problemei, cu condiția ca inegalitatea |f(x n) / f’(x n)|< e.

La primul pas al tangentelor avem:

x 1 \u003d x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) \u003d 1- 0,2857 \u003d 0,71429;
întrucât condiția nu este îndeplinită, mergem mai departe;
obținem o nouă valoare pentru x 2 , care este egală cu 0,674;
observăm că raportul dintre valoarea funcției și derivata ei în x 2 este mai mic de 0,0063, oprim procesul.

Metoda tangentei în Excel

Rezolvarea exemplului anterior poate fi mult mai ușoară și mai rapidă dacă nu faceți calcule manual (pe calculator), ci folosiți posibilitățile procesor de foi de calcul de la Microsoft.

Pentru a face acest lucru, în Excel, trebuie să creați pagina nouași umpleți celulele sale cu următoarele formule:

în C7 scriem „= PUTEREA (B7; 3) + 4 * B7 - 3”;
în D7 introducem „= 4 + 3 * GRAD (B7; 2)”;
în E7 scriem „= (PUTERE (B7; 3) - 3 + 4 * B7) / (3 * PUTEREA (B7; 2) + 4)";
în D7 introducem expresia „= B7 - E7”;
în B8 introducem formula-condiție „= DACA (E7< 0,001;"Завершение итераций"; D7)».

Într-o sarcină specifică, deja în celula B10, va apărea inscripția „Finalizarea iterațiilor”, iar pentru rezolvarea problemei va trebui să luați numărul scris în celula situată pe un rând mai sus. Pentru aceasta, puteți selecta și o coloană separată „întindere” introducând acolo o formulă condiționată, conform căreia rezultatul va fi scris acolo dacă conținutul într-una sau alta celulă a coloanei B ia forma „Finalizarea iterațiilor”.

Implementare în Pascal

Să încercăm să obținem soluția ecuației neliniare y = x 4 - 4 - 2 * x folosind metoda tangentei în Pascal.

Folosim o funcție auxiliară care va ajuta la efectuarea unui calcul aproximativ f "(x) \u003d (f (x + delta) - f (x)) / delta. Ca o condiție pentru finalizarea procesului iterativ, vom alege îndeplinirea inegalității | x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

Programul este remarcabil prin faptul că nu necesită calcularea manuală a derivatei.

metoda acordurilor

Luați în considerare un alt mod de a identifica rădăcinile ecuațiilor neliniare. Procesul de iterație constă în faptul că, ca aproximări succesive la rădăcina dorită pentru f(x)=0, se iau valorile punctelor de intersecție ale coardei cu abscisele punctelor de capăt a și b cu OX. , notat cu x 1 , ..., x n . Avem:

Pentru punctul în care coarda se intersectează cu axa OX, expresia se va scrie astfel:

Fie derivata a doua pozitivă pentru x £ (cazul opus se reduce la cel luat în considerare dacă scriem f(x) = 0). În acest caz, graficul y \u003d f (x) este o curbă convexă în partea de jos și situată sub coardă AB. Pot exista 2 cazuri: cand functia este pozitiva la punctul a sau este negativa la punctul b.

În primul caz, alegem capătul a ca fiind fix și luăm punctul b pentru x 0. Apoi aproximările succesive după formula prezentată mai sus formează o succesiune care scade monoton.

În al doilea caz, capătul b este fixat la x 0 = a. Valorile x obținute la fiecare pas de iterație formează o secvență care crește monoton.

Astfel, putem afirma că:

fix în metoda acordurilor este acel capăt al segmentului în care semnele funcției și derivata a doua a acesteia nu coincid;
aproximații pentru rădăcina x - x m - se află pe partea în care f (x) are un semn care nu coincide cu semnul lui f "" (x).

Iterațiile pot fi continuate până când sunt îndeplinite condițiile pentru apropierea rădăcinilor la acest pas și la pasul de iterație anterior modulo abs(x m - x m - 1)< e.

Metoda modificată

Metoda combinată a acordurilor și tangentelor vă permite să stabiliți rădăcinile ecuației, abordându-le din diferite părți. O astfel de valoare, la care graficul f(x) intersectează OX, vă permite să rafinați soluția mult mai rapid decât folosind fiecare dintre metode separat.

Să presupunem că trebuie să găsim rădăcinile f(x)=0 dacă acestea există pe . Puteți utiliza oricare dintre metodele descrise mai sus. Cu toate acestea, este mai bine să încercați o combinație a acestora, care va crește semnificativ acuratețea rădăcinii.

Considerăm cazul cu o aproximare inițială corespunzătoare condiției ca derivatele prima și a doua să aibă semne diferite la un anumit punct x.

În astfel de condiții, rezolvarea ecuațiilor neliniare prin metoda tangentei vă permite să găsiți o rădăcină cu exces dacă x 0 =b, iar metoda folosind acorduri la un capăt fix b duce la găsirea unei rădăcini aproximative cu dezavantaj.

Formule folosite:

Acum trebuie căutată rădăcina dorită x în interval. La pasul următor, trebuie să aplicați deja metoda combinată acestui segment. Procedând astfel, obținem formule de forma:

Dacă există o diferență de semn între derivata întâi și a doua, atunci, argumentând într-un mod similar, pentru a rafina rădăcina, obținem următoarele formule recursive:

Ca o condiție, inegalitatea estimată | b n +1 - a n +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

Dacă inegalitatea de mai sus este adevărată, atunci un punct este luat ca rădăcină a ecuației neliniare pe un interval dat, care se află exact la mijloc între soluțiile găsite la o anumită etapă de iterație.

Metoda combinată este ușor de implementat în mediul TURBO PASCAL. Cu o dorință puternică, puteți încerca să efectuați toate calculele folosind metoda tabelară în programul Excel.

În acest din urmă caz, se selectează mai multe coloane pentru rezolvarea problemei folosind acorduri și separat pentru metoda propusă de Isaac Newton.

În acest caz, fiecare linie este utilizată pentru a înregistra calcule la un anumit pas iterativ pentru două metode. Apoi, în partea din stânga a zonei de soluții, pe pagina de lucru activă, este evidențiată o coloană în care se introduce rezultatul calculării modulului diferenței valorilor pasului următor de iterație pentru fiecare dintre metode. Un altul poate fi folosit pentru a introduce rezultatele calculelor conform formulei de calcul a construcției logice „IF”, folosită pentru a afla dacă condiția este îndeplinită sau nu.

Acum știi cum să rezolvi ecuații complexe. Metoda tangentei, după cum ați văzut deja, este implementată destul de simplu, atât în Pascal, cât și în Excel. Prin urmare, puteți stabili oricând rădăcinile unei ecuații care este dificil sau imposibil de rezolvat folosind formule.

Toți oamenii caută în mod natural cunoașterea. (Aristotel. Metafizica)

Metode numerice: Rezolvarea ecuațiilor neliniare

Problemele de rezolvare a ecuațiilor apar în mod constant în practică, de exemplu, în economie, atunci când dezvoltați o afacere, doriți să știți când profitul atinge o anumită valoare, în medicină, atunci când studiați efectul medicamentelor, este important să știți când concentrația a unei substanțe atinge un nivel dat etc.

În problemele de optimizare, este adesea necesar să se determine punctele în care derivata unei funcții devine 0, ceea ce este o condiție necesară local extremum.

În statistică, atunci când se construiesc estimări folosind metoda celor mai mici pătrate sau metoda probabilității maxime, trebuie să se rezolve și ecuații neliniare și sisteme de ecuații.

Deci, există o întreagă clasă de probleme legate de găsirea soluțiilor neliniară ecuații, de exemplu, ecuații sau ecuații etc.

În cel mai simplu caz, avem o funcție definită pe segmentul ( A, b ) și luând anumite valori.

Fiecare valoare X din acest segment putem potrivi numărul , acesta este funcţional dependența, un concept cheie al matematicii.

Trebuie să găsim o astfel de valoare la care astfel se numesc rădăcinile funcției

Vizual, trebuie să determinăm punctul de intersecție al graficului funcțieicu axa absciselor.

Metoda Bisecției

Cea mai simplă metodă de găsire a rădăcinilor unei ecuații este metoda bisecției sau dihotomie.

Această metodă este intuitivă și toată lumea ar acționa într-un mod similar atunci când rezolvă o problemă.

Algoritmul este după cum urmează.

Să presupunem că am găsit două puncte și așa că și avem variat semne, atunci între aceste puncte există cel puțin o rădăcină a funcției .

Împărțiți segmentul în jumătate și introduceți mijloc punct .

Atunci fie , sau .

Să lăsăm acea jumătate a segmentului pentru care valorile de la capete au semne diferite. Acum împărțim din nou acest segment în jumătate și lăsăm acea parte a acestuia, la limitele căreia funcția are semne diferite și așa mai departe, pentru a obține precizia necesară.

Evident, vom restrânge treptat zona în care se află rădăcina funcției și, prin urmare, o vom determina cu un anumit grad de precizie.

Rețineți că algoritmul descris este aplicabil pentru orice funcție continuă.

Avantajele metodei bisectării includ fiabilitatea ridicată și simplitatea.

Dezavantajul metodei este faptul că, înainte de a începe aplicarea acesteia, este necesar să găsiți două puncte, valorile funcției în care au semne diferite. Este evident că metoda nu este aplicabilă rădăcinilor de multiplicitate pară și nici nu poate fi generalizată în cazul rădăcinilor complexe și la sistemele de ecuații.

Ordinea de convergență a metodei este liniară, la fiecare pas precizia se dublează, cu cât se fac mai multe iterații, cu atât se determină mai precis rădăcina.

Metoda lui Newton: fundamente teoretice

Metoda clasică a lui Newton sau tangente constă în faptul că if este o aproximare a rădăcinii ecuației , atunci următoarea aproximare este definită ca rădăcina tangentei la funcția desenată în punctul .

Ecuația tangentei la o funcție într-un punct are forma:

În ecuația tangentei, să punem și .

Atunci algoritmul calculelor secvențiale din metoda lui Newton este următorul:

Convergența metodei tangentei este pătratică, ordinea convergenței este 2.

Astfel, convergența metodei tangentei lui Newton este foarte rapidă.

Amintește-ți acest fapt minunat!

Fără modificări, metoda este generalizată la cazul complex.

Dacă rădăcina este o rădăcină a celei de-a doua multiplicități sau mai mare, atunci ordinea de convergență scade și devine liniară.

Exercitiul 1. Folosind metoda tangentelor, găsiți soluția ecuației pe intervalul (0, 2).

Exercițiul 2. Folosind metoda tangentelor, găsiți soluția ecuației pe intervalul (1, 3).

Dezavantajele metodei lui Newton includ localitatea acesteia, deoarece este garantată să converge pentru o aproximare de pornire arbitrară numai dacă condiția , în caz contrar, există convergență doar într-o anumită vecinătate a rădăcinii.

Dezavantajul metodei lui Newton este necesitatea de a calcula derivate la fiecare pas.

Vizualizarea metodei lui Newton

Metoda lui Newton (metoda tangentei) se aplică dacă ecuația f(X) = 0 are o rădăcină și sunt îndeplinite următoarele condiții:

1) funcția y= f(X) este definită și continuă pentru ;

2) f(A)· f(b) < 0 (funcția ia valori ale diferitelor semne la capetele segmentului [ A; b]);

3) derivate f"(X) și f""(X) păstrați semnul pe segmentul [ A; b] (adică funcția f(X) fie crește, fie scade pe interval [ A; b], menținând în același timp direcția convexității);

Ideea principală a metodei este următoarea: pe intervalul [ A; b] se alege un astfel de număr X 0 , sub care f(X 0 ) are acelasi semn ca f"" (X 0 ), adică starea f(X 0 )· f"" (X) > 0 . Astfel, se alege un punct cu abscisă X 0 , unde tangenta la curba y= f(X) pe segmentul [ A; b] traversează axa Bou. Pentru un punct X 0 În primul rând, este convenabil să alegeți unul dintre capetele segmentului.

Luați în considerare metoda lui Newton pe un exemplu specific.

Să ni se dea o funcție crescătoare y \u003d f (x) \u003d x 2 -2, continuă pe intervalul (0;2), și având f"(x) = 2 X > 0 și f "" (x) = 2 > 0 .

Imagine1 . f(x)=x 2 -2

Ecuația tangentă în vedere generala are reprezentarea:

y-y 0 = f" (x 0) (x-x 0).

În cazul nostru: y-y 0 \u003d 2x 0 (x-x 0). Ca punct x 0 alegeți un punct B 1 (b; f(b)) = (2,2). Desenăm o tangentă la funcție y = f(x)în punctul B 1 și notăm punctul de intersecție al tangentei și a axei Bou punct x 1. Obținem ecuația primei tangente: y-2=2 2(x-2), y=4x-6.

Ox: x 1 =

Imagine2. Rezultatul primei iterații

y=f(x) Bou printr-un punct x 1, obținem un punct B2 =(1,5; 0,25). Desenați din nou o tangentă la funcție y = f(x)în punctul B 2 și notăm punctul de intersecție al tangentei și a axei Bou punct x2.

Ecuația celei de-a doua tangente: y-0.25=2*1.5(X-1.5), y = 3 X - 4.25.

Punctul de intersecție al tangentei și al axei Ox: x 2 =.

Imagine3. A doua iterație a metodei lui Newton

Apoi găsim punctul de intersecție al funcției y=f(x)și o perpendiculară pe axă Bou prin punctul x 2, obținem punctul B 3 și așa mai departe.

Imagine4. Al treilea pas al metodei tangentei

Prima aproximare a rădăcinii este determinată de formula:

= 1.5.

A doua aproximare a rădăcinii este determinată de formula:

A treia aproximare a rădăcinii este determinată de formula:

În acest fel , i-a aproximarea rădăcinii este determinată de formula:

Calculele sunt efectuate până când zecimalele necesare în răspuns se potrivesc sau se atinge precizia specificată e - până când inegalitatea este îndeplinită | xi- xi-1 | < e.

În cazul nostru, să comparăm aproximarea obținută în pasul al treilea cu răspunsul real calculat pe calculator:

Figura 5. Rădăcina lui 2 calculată pe un calculator

După cum puteți vedea, deja la al treilea pas am primit o eroare mai mică de 0,000002.

Astfel, este posibil să se calculeze valoarea valorii „rădăcină pătrată a lui 2” cu orice grad de precizie. Această metodă minunată a fost inventată de Newton și vă permite să găsiți rădăcinile unor ecuații foarte complexe.

Metoda lui Newton: Aplicație C++

În acest articol, automatizăm procesul de calcul al rădăcinilor ecuațiilor prin scrierea unei aplicații de consolă în C++. Îl vom dezvolta în Visual C++ 2010 Express, care este un mediu de dezvoltare C++ gratuit și foarte convenabil.

Să începem cu Visual C++ 2010 Express. Va apărea fereastra de pornire a programului. În colțul din stânga, faceți clic pe „Creați proiect”.

Orez. unu. Pagină de start Visual C++ 2010 Express

În meniul care apare, selectați „Win32 Console Application”, introduceți numele aplicației „Newton_Method”.

Orez. 2. Creați un proiect

// Newton_method.cpp: definește punctul de intrare pentru aplicația consolă

#include „stdafx.h”

#include

folosind namespace std;

float f(double x) //returnează valoarea funcției f(x) = x^2-2

float df(float x) //returnează valoarea derivatei

float d2f(float x) // valoare derivată a doua

int _tmain(int argc, _TCHAR* argv)

int exit = 0, i=0;//exit și variabile buclă

dublu x0,xn;// aproximații calculate pentru rădăcină

dublu a, b, eps;// limitele segmentului și precizia necesară

cout<<"Please input \n=>";

cin>>a>>b; // introducem limitele segmentului pe care vom căuta rădăcina

cout<<"\nPlease input epsilon\n=>";

cin>>eps; // introduceți precizia de calcul dorită

dacă (a > b) // dacă utilizatorul a amestecat limitele segmentului, schimbați-le

dacă (f(a)*f(b)>0) // dacă semnele funcției de pe marginile segmentului sunt aceleași, atunci nu există rădăcină

cout<<"\nError! No roots in this interval\n";

dacă (f(a)*d2f(a)>0) x0 = a; // pentru a selecta un punct de plecare, verificați f(x0)*d2f(x0)>0 ?

xn = x0-f(x0)/df(x0); // numără prima aproximare

cout<<++i<<"-th iteration = "<

while(fabs(x0-xn) > eps) // până când ajungem la precizia necesară, vom continua să calculăm

xn = x0-f(x0)/df(x0); // direct formula lui Newton

cout<<++i<<"-th iteration = "<

cout<<"\nRoot = "<

cout<<"\nExit?=>";

) în timp ce (ieșire!=1); // până când utilizatorul intră în exit = 1

Să vedem cum funcționează. Faceți clic pe triunghiul verde din colțul din stânga sus al ecranului sau apăsați F5.

Dacă apare o eroare de compilare „Eroare LNK1123: Nu se poate converti în COFF: fișierul este invalid sau corupt”, atunci aceasta este tratată fie prin instalarea primului Service pack 1, fie în setările proiectului Proprietăți -> Linker, dezactivați legătura incrementală.

Orez. 4. Rezolvarea erorii de compilare a proiectului

Vom căuta rădăcinile funcției f(x) =x2-2.

Mai întâi, să testăm aplicația pe datele de intrare „greșite”. Nu există rădăcini pe segment, programul nostru ar trebui să dea un mesaj de eroare.

Avem o fereastră de aplicație:

Orez. 5. Introducerea datelor de intrare

Introducem limitele segmentelor 3 și 5, iar precizia este de 0,05. Programul, așa cum ar trebui, a dat un mesaj de eroare că nu există rădăcini pe acest segment.

Orez. 6. Eroare „Nu există rădăcini pe acest segment!”

Nu vom pleca încă, așa că mesajul „Exit?” introduceți „0”.

Acum să testăm aplicația pe datele de intrare corecte. Să introducem un segment și o precizie de 0,0001.

Orez. 7. Calcularea rădăcinii cu precizia necesară

După cum putem vedea, precizia necesară a fost deja atinsă la a patra iterație.

Pentru a ieși din aplicație, introduceți „Exit?” => 1.

Metoda secantei

Pentru a evita calcularea derivatei, metoda lui Newton poate fi simplificată prin înlocuirea derivatei cu o valoare aproximativă calculată din cele două puncte anterioare:

Procesul iterativ arată astfel:

Acesta este un proces iterativ în doi pași, deoarece le folosește pe cele două anterioare pentru a găsi următoarea aproximare.

Ordinea de convergență a metodei secantei este mai mică decât cea a metodei tangentei și este egală în cazul unei singure rădăcini.

Această valoare minunată se numește raportul de aur:

Verificăm acest lucru presupunând, pentru comoditate, că .

Astfel, până la infinitezimale de ordin superior

Renunțând la termenul rămas, obținem o relație de recurență, a cărei soluție se caută în mod natural sub forma .

După înlocuire, avem: și

Pentru convergență este necesar ca aceasta să fie pozitivă, deci .

Deoarece nu este necesară cunoașterea derivatei, atunci cu aceeași cantitate de calcule în metoda secantei (în ciuda ordinului inferior de convergență), este posibil să se obțină o precizie mai mare decât în metoda tangentei.

Rețineți că lângă rădăcină, trebuie să împărțiți la un număr mic, iar acest lucru duce la o pierdere a preciziei (mai ales în cazul rădăcinilor multiple), prin urmare, alegând un relativ mic, se efectuează calcule înainte de a executa și continuați-le până când modulul diferenței dintre aproximările învecinate scade.

De îndată ce începe creșterea, calculele sunt oprite și ultima iterație nu este utilizată.

Această procedură pentru determinarea sfârșitului iterațiilor se numește tehnică Harvick.

Metoda parabolelor

Luați în considerare o metodă în trei etape în care aproximarea este determinată de cele trei puncte anterioare și .

Pentru a face acest lucru, înlocuim, în mod similar cu metoda secantei, funcția cu o parabolă de interpolare care trece prin punctele , și .

În forma lui Newton, arată astfel:

Un punct este definit ca cel al rădăcinilor acestui polinom, care este mai aproape ca modul de punct.

Ordinea de convergență a metodei parabolelor este mai mare decât cea a metodei secantei, dar mai mică decât cea a metodei lui Newton.

O diferență importantă față de metodele considerate anterior este faptul că, chiar dacă este reală pentru real și aproximațiile de pornire sunt alese reale, metoda parabolelor poate duce la o rădăcină complexă a problemei inițiale.

Această metodă este foarte utilă pentru găsirea rădăcinilor polinoamelor de grad înalt.

Metodă simplă de iterație

Problema găsirii de soluții la ecuații poate fi formulată ca o problemă de găsire a rădăcinilor: , sau ca o problemă de găsire a unui punct fix.

Lăsa și - compresie: (în special, faptul că - compresie, așa cum este ușor de observat, înseamnă că).

După teorema lui Banach, există un punct fix unic

Poate fi găsită ca limită a unei proceduri iterative simple

unde aproximarea inițială este un punct arbitrar din intervalul .

Dacă funcția este diferențiabilă, atunci un criteriu de compresie convenabil este numărul . Într-adevăr, după teorema Lagrange

Astfel, dacă derivata este mai mică de unu, atunci este o contracție.

Condiție este esențială, deoarece dacă, de exemplu, pe , atunci nu există un punct fix, deși derivata este egală cu zero. Rata de convergență depinde de valoarea lui . Cu cât este mai mică, cu atât convergența este mai rapidă.

La fel ca aproximarea. Termenul P. este folosit uneori în sensul unui obiect de aproximare (de exemplu, inițiala P.) ... Enciclopedie matematică

metoda lui Newton- Metoda lui Newton, algoritmul lui Newton (cunoscut și ca metoda tangentei) este o metodă numerică iterativă pentru găsirea rădăcinii (zero) unei funcții date. Metoda a fost propusă pentru prima dată de fizicianul, matematicianul și astronomul englez Isaac Newton ...... Wikipedia

O metodă tangentă

Metoda Gauss - Newton- Metoda lui Newton (cunoscută și ca metoda tangentei) este o metodă numerică iterativă pentru găsirea rădăcinii (zero) unei anumite funcții. Metoda a fost propusă pentru prima dată de fizicianul, matematicianul și astronomul englez Isaac Newton (1643 1727), sub numele de ... ... Wikipedia

Metoda Newton-Raphson- Metoda lui Newton (cunoscută și ca metoda tangentei) este o metodă numerică iterativă pentru găsirea rădăcinii (zero) unei anumite funcții. Metoda a fost propusă pentru prima dată de fizicianul, matematicianul și astronomul englez Isaac Newton (1643 1727), sub numele de ... ... Wikipedia

Metoda tangentei- Metoda lui Newton (cunoscută și ca metoda tangentei) este o metodă numerică iterativă pentru găsirea rădăcinii (zero) unei anumite funcții. Metoda a fost propusă pentru prima dată de fizicianul, matematicianul și astronomul englez Isaac Newton (1643 1727), sub numele de ... ... Wikipedia

Metoda tangentei (metoda lui Newton)- Metoda lui Newton (cunoscută și ca metoda tangentei) este o metodă numerică iterativă pentru găsirea rădăcinii (zero) unei anumite funcții. Metoda a fost propusă pentru prima dată de fizicianul, matematicianul și astronomul englez Isaac Newton (1643 1727), sub numele de ... ... Wikipedia

Rezolvarea numerică a ecuațiilor- iar sistemele lor constă într-o determinare aproximativă a rădăcinii sau rădăcinilor unei ecuații sau unui sistem de ecuații și este utilizat în cazurile în care este imposibil sau consuma mult timp să se calculeze valoarea exactă. Cuprins 1 Enunțarea problemei 2 Metode numerice ... Wikipedia

Metoda de aproximare secvenţială- o metodă de rezolvare a problemelor matematice folosind o astfel de succesiune de aproximări care converge către o soluție și este construită în mod recurent (adică, fiecare nouă aproximare este calculată pe baza celei anterioare; aproximarea inițială este aleasă în ... ... Marea Enciclopedie Sovietică

Fie rădăcina ecuației f(x)=0 separată pe segmentul , iar derivata întâi și a doua a lui f’(x) și f""(x) sunt continue și de semn constant pentru хн .

Fie ca următoarea aproximare a rădăcinii x n să fie obținută (aleasă) la un pas al rafinamentului rădăcinii . Apoi să presupunem că următoarea aproximare obținută cu ajutorul corecției h n , rezultă valoarea exactă a rădăcinii

x \u003d x n + h n. (1.2.3-6)

Socoteală h n valoare mică, reprezentăm f(x n + h n) ca o serie Taylor, limitându-ne la termeni liniari

f(x n + h n) "f(x n) + h n f'(x n). (1.2.3-7)

Considerând că f(x) = f(х n + h n) = 0, obținem f(х n) + h n f ’(х n) » 0.

Prin urmare, h n "- f (x n) / f'(x n). Înlocuiți valoarea h nîn (1.2.3-6) și în locul valorii exacte a rădăcinii X obținem o altă aproximare

Formula (1.2.3-8) vă permite să obțineți o succesiune de aproximări x 1, x 2, x 3 ..., care, în anumite condiții, converge către valoarea exactă a rădăcinii X, acesta este

Interpretarea geometrică a metodei lui Newton este după cum urmează
(Fig.1.2.3-6). Luăm capătul drept al segmentului b ca aproximare inițială x 0 și în punctul corespunzător B 0 de pe graficul funcției y \u003d f (x) construim o tangentă. Punctul de intersecție al tangentei cu axa x este luat ca o nouă aproximare mai precisă x 1 . Repetarea acestei proceduri de mai multe ori vă permite să obțineți o succesiune de aproximări x 0, x 1, x 2 , . . ., care tinde spre valoarea exactă a rădăcinii X.

Formula de calcul a metodei lui Newton (1.2.3-8) poate fi obținută dintr-o construcție geometrică. Deci într-un triunghi dreptunghic x 0 B 0 x 1 catete
x 0 x 1 = x 0 V 0 / tga. Considerând că punctul B 0 se află pe graficul funcției f(x), iar ipotenuza este formată dintr-o tangentă la graficul f (x) în punctul B 0, obținem

(1.2.3-9)

(1.2.3-10)

Această formulă coincide cu (1.2.3-8) pentru a n-a aproximare.

Din fig. 1.2.3-6 se poate observa că alegerea punctului a ca aproximare inițială poate duce la faptul că următoarea aproximare x 1 va fi în afara segmentului pe care este separată rădăcina. X. În acest caz, convergența procesului nu este garantată. În cazul general, alegerea aproximării inițiale se face în conformitate cu următoarea regulă: pentru aproximarea inițială, ar trebui să ia un astfel de punct x 0 н, la care f (x 0) × f '' (x 0) > 0, adică semnele funcției și derivata a doua a acesteia se potrivesc.

Condițiile de convergență pentru metoda lui Newton sunt formulate în următoarea teoremă.

Dacă rădăcina ecuației este separată pe segment, și f'(x 0) și f''(x) sunt diferite de zero și își păstrează semnele la xo, atunci dacă alegem un astfel de punct ca aproximarea inițială x 0 О , ce f(x 0).f¢¢(x 0)>0 , apoi rădăcina ecuației f(x)=0 poate fi calculat cu orice grad de precizie.

Estimarea erorii a metodei lui Newton este determinată de următoarea expresie:

(1.2.3-11)

unde este cea mai mică valoare la

Cea mai mare valoare la

Procesul de calcul este încheiat dacă ,

unde este precizia specificată.

În plus, următoarele expresii pot servi drept condiție pentru obținerea unei precizii date la rafinarea rădăcinii prin metoda Newton:

Schema algoritmului metodei Newton este prezentată în fig. 1.2.3-7.

Partea stângă a ecuației originale f(x) și derivata sa f’(x) din algoritm sunt proiectate ca module software separate.

Orez. 1.2.3-7. Diagrama algoritmică a metodei lui Newton

Exemplul 1.2.3-3 Rafinați rădăcinile ecuației x-ln(x+2) = 0 folosind metoda Newton, cu condiția ca rădăcinile acestei ecuații să fie separate pe segmentele x 1 н[-1.9;-1.1] şi x 2 n [-0,9;2].

Prima derivată f'(x) = 1 - 1 / (x + 2) își păstrează semnul pe fiecare dintre segmente:

f'(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 la xО [-0,9; 2].

A doua derivată f "(x) \u003d 1 / (x + 2) 2\u003e 0 pentru orice x.

Astfel, condițiile de convergență sunt îndeplinite. Deoarece f "" (x)> 0 pe întregul interval de valori permise, atunci pentru a rafina rădăcina pentru aproximarea inițială x 1 alege x 0 \u003d -1,9 (deoarece f (-1,9) × f ”(-1,9)> 0). Obținem o succesiune de aproximări:

Continuând calculele, obținem următoarea succesiune a primelor patru aproximări: -1,9; –1,8552, -1,8421; -1,8414 . Valoarea funcției f(x) în punctul x=-1,8414 este egală cu f(-1,8414)=-0,00003 .

Pentru a rafina rădăcina x 2 н[-0.9;2], alegem ca aproximații inițiale 0 =2 (f(2)×f”(2)>0). Pe baza x 0 = 2, obținem o succesiune de aproximări: 2,0;1,1817; 1,1462; 1,1461. Valoarea funcției f(x) în punctul x=1,1461 este egală cu f(1,1461)= -0,00006.

Metoda lui Newton are o rată mare de convergență, dar la fiecare pas necesită calcularea nu numai a valorii funcției, ci și a derivatei acesteia.

metoda acordurilor

Interpretarea geometrică a metodei acordurilor este după cum urmează
(Fig.1.2.3-8).

Să desenăm un segment de dreaptă prin punctele A și B. Următoarea aproximare x 1 este abscisa punctului de intersecție al coardei cu axa 0x. Să construim ecuația unui segment de dreaptă:

Să punem y=0 și să găsim valoarea x=x 1 (o altă aproximare):

Repetăm procesul de calcul pentru a obține următoarea aproximare a rădăcinii - x 2 :

În cazul nostru (Fig.1.2.11) iar formula de calcul a metodei acordurilor va arăta ca

Această formulă este valabilă atunci când punctul b este luat ca punct fix, iar punctul a acționează ca o aproximare inițială.

Luați în considerare un alt caz (Fig. 1.2.3-9), când .

Ecuația dreptei pentru acest caz are forma

Următoarea aproximare x 1 la y = 0

Apoi formula recursivă pentru metoda acordurilor pentru acest caz are forma

De remarcat că pentru punctul fix din metoda acordurilor se alege capătul segmentului pentru care este îndeplinită condiția f (x)∙f¢ (x)>0.

Astfel, dacă punctul a este luat ca punct fix , atunci x 0 = b acționează ca o aproximare inițială și invers.

Condițiile suficiente care să asigure calculul rădăcinii ecuației f(x)=0 folosind formula coardelor vor fi aceleași ca și pentru metoda tangentei (metoda lui Newton), dar în locul aproximării inițiale se alege un punct fix. Metoda acordurilor este o modificare a metodei lui Newton. Diferența este că următoarea aproximare în metoda Newton este punctul de intersecție a tangentei cu axa 0X, iar în metoda coardelor - punctul de intersecție a coardei cu axa 0X - aproximările converg către rădăcina din laturi diferite.

Estimarea erorii metodei acordurilor este determinată de expresie

(1.2.3-15)

Condiția de terminare a procesului de iterație prin metoda acordurilor

(1.2.3-16)

Dacă M 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Exemplul 1.2.3-4. Precizați rădăcina ecuației e x - 3x = 0, separată pe un segment cu o precizie de 10 -4 .

Să verificăm condiția de convergență:

Prin urmare, a=0 ar trebui să fie ales ca punct fix și x 0 \u003d 1 ar trebui luat ca aproximare inițială, deoarece f (0) \u003d 1> 0 și f (0) * f "(0)> 0 .