Matematica ca știință a apărut în legătură cu nevoia de a rezolva probleme practice: măsurători la sol, navigație etc. Drept urmare, matematica era matematică numerică și scopul ei era obținerea unei soluții sub forma unui număr. Rezolvarea numerică a problemelor aplicate a interesat întotdeauna matematicienii. Cei mai mari reprezentanți ai trecutului au combinat în studiile lor studiul fenomenelor naturale, obținând descrierea lor matematică, i.e. modelul său matematic și cercetările sale. Analiza modelelor complicate a necesitat crearea unor metode speciale, de obicei numerice, pentru rezolvarea problemelor. Numele unora dintre aceste metode indică faptul că au fost dezvoltate de cei mai mari oameni de știință ai timpului lor. Acestea sunt metodele lui Newton, Euler, Lobachevsky, Gauss, Cebyshev, Hermite.

Timpul prezent este caracterizat de o expansiune bruscă a aplicațiilor matematicii, în mare parte asociată cu crearea și dezvoltarea tehnologiei informatice. Ca urmare a apariției computerelor în mai puțin de 40 de ani, viteza operațiunilor a crescut de la 0,1 operații pe secundă cu numărare manuală la 10 operațiuni pe secundă pe computerele moderne.

Opinia răspândită despre atotputernicia calculatoarelor moderne dă naștere la impresia că matematicienii au scăpat de toate necazurile asociate rezolvării numerice a problemelor, iar dezvoltarea de noi metode de rezolvare a acestora nu mai este atât de semnificativă. În realitate, situația este diferită, deoarece nevoile evoluției, de regulă, pun înaintea sarcinilor științei care sunt la limita capacităților sale. Extinderea aplicației matematicii a dus la matematizarea diferitelor ramuri ale științei: chimie, economie, biologie, geologie, geografie, psihologie, medicină, tehnologie etc.

Există două circumstanțe care au dus inițial la dorința de matematizare a științelor:

în primul rând, numai utilizarea metodelor matematice face posibilă acordarea unui caracter cantitativ studiului unuia sau altuia fenomen al lumii materiale;

în al doilea rând, și acesta este principalul lucru, doar modul matematic de a gândi face un obiect. Această metodă de cercetare se numește experiment de calcul - studiul este pe deplin obiectiv.

Recent, a apărut un alt factor care are un impact puternic asupra proceselor de matematizare a cunoștințelor. Aceasta este dezvoltarea rapidă a tehnologiei informatice. Utilizarea computerelor pentru rezolvarea problemelor științifice, de inginerie și aplicate în general se bazează în întregime pe matematizarea lor.

modele matematice.

Tehnologia modernă pentru studiul problemelor complexe se bazează pe construirea și analiza, de obicei cu ajutorul unui calculator, a modelelor matematice ale problemei studiate. De obicei, un experiment de calcul, așa cum am văzut deja, constă dintr-o serie de etape: stabilirea unei probleme, construirea unui model matematic (formularea matematică a problemei), dezvoltarea unei metode numerice, dezvoltarea unui algoritm pentru implementarea unei metode numerice, dezvoltarea un program, depanarea unui program, efectuarea de calcule, analizarea rezultatelor.

Deci, utilizarea computerelor pentru rezolvarea oricărei probleme științifice sau de inginerie este asociată inevitabil cu trecerea de la un proces sau fenomen real la modelul său matematic. Astfel, aplicarea modelelor în cercetarea științifică și practica ingineriei este arta modelării matematice.

Un model este de obicei numit un sistem reprezentat sau realizat material care reproduce principalele caracteristici cele mai semnificative ale unui fenomen dat.

Principalele cerințe pentru modelul matematic sunt adecvarea fenomenului luat în considerare, i.e. ar trebui să reflecte suficient trăsăturile caracteristice ale fenomenului. În același timp, ar trebui să aibă o simplitate comparativă și accesibilitate a cercetării.

Modelul matematic reflectă dependența dintre condițiile de apariție a fenomenului studiat și rezultatele acestuia în anumite construcții matematice. Cel mai adesea, următoarele concepte matematice sunt folosite ca astfel de construcții: funcție, funcțional, operator, ecuație numerică, ecuație diferențială obișnuită, ecuație diferențială parțială.

Modelele matematice pot fi clasificate după diferite criterii: statice și dinamice, concentrate și distribuite; deterministă și probabilistică.

Luați în considerare problema găsirii rădăcinilor ecuației neliniare

Rădăcinile ecuației (1) sunt acele valori ale lui x care, la înlocuire, îl transformă într-o identitate. Doar pentru cele mai simple ecuații se poate găsi o soluție sub formă de formule, adică. formă analitică. Mai des este necesară rezolvarea ecuațiilor prin metode aproximative, cele mai răspândite dintre care, în legătură cu apariția computerelor, sunt metodele numerice.

Algoritmul pentru găsirea rădăcinilor prin metode aproximative poate fi împărțit în două etape. În primul rând, se studiază locația rădăcinilor și se efectuează separarea acestora. Există o zonă în care există o rădăcină a ecuației sau o aproximare inițială a rădăcinii x 0 . Cel mai simplu mod de a rezolva această problemă este studierea graficului funcției f(x) . În cazul general, pentru a-l rezolva, este necesar să se implice toate mijloacele de analiză matematică.

Existența pe intervalul găsit a cel puțin unei rădăcini a ecuației (1) rezultă din condiția Bolzano:

f(a)*f(b)<0 (2)

De asemenea, se presupune că funcția f(x) este continuă pe segmentul dat. Cu toate acestea, această condiție nu răspunde la întrebarea despre numărul de rădăcini ale ecuației pe un interval dat. Dacă cerința de continuitate a funcției este completată cu cerința monotonității acesteia și aceasta decurge din constanța semnului derivatei întâi, atunci putem afirma existența unei rădăcini unice pe un segment dat.

La localizarea rădăcinilor, este, de asemenea, important să cunoașteți proprietățile de bază ale acestui tip de ecuație. De exemplu, amintiți-vă câteva proprietăți ale ecuațiilor algebrice:

unde sunt coeficienții reali.

• a) O ecuație de grad n are n rădăcini, dintre care pot fi atât reale, cât și complexe. Rădăcinile complexe formează perechi conjugate complexe și, prin urmare, ecuația are un număr par de astfel de rădăcini. Pentru o valoare impară a lui n, există cel puțin o rădăcină reală.
• b) Numărul de rădăcini reale pozitive este mai mic sau egal cu numărul de semne variabile din succesiunea coeficienților. Înlocuirea x cu -x în ecuația (3) vă permite să estimați numărul de rădăcini negative în același mod.

La a doua etapă a rezolvării ecuației (1), folosind aproximarea inițială obținută, se construiește un proces iterativ care face posibilă rafinarea valorii rădăcinii cu o anumită precizie predeterminată. Procesul iterativ constă în perfecţionarea succesivă a aproximării iniţiale. Fiecare astfel de pas se numește iterație. Ca rezultat al procesului de iterație, se găsește o succesiune de valori aproximative ale rădăcinilor ecuației. Dacă această secvență se apropie de adevărata valoare a rădăcinii x pe măsură ce n crește, atunci procesul iterativ converge. Se spune că un proces iterativ converge la cel puțin ordinul m dacă este îndeplinită următoarea condiție:

unde С>0 este o constantă. Dacă m=1, atunci se vorbește de convergență de ordinul întâi; m=2 - despre pătratică, m=3 - despre convergența cubică.

Ciclurile iterative se încheie dacă, pentru o anumită eroare admisibilă, sunt îndeplinite criteriile pentru abaterile absolute sau relative:

sau micimea reziduului:

Această lucrare este dedicată studiului unui algoritm de rezolvare a ecuațiilor neliniare folosind metoda lui Newton.

Există multe metode diferite de rezolvare a ecuațiilor neliniare, unele dintre ele sunt prezentate mai jos:

• 1)Metoda iterației. Când rezolvăm o ecuație neliniară prin iterație, folosim ecuația sub forma x=f(x). Se setează valoarea inițială a argumentului x 0 și precizia e. Prima aproximare a soluției x 1 se găsește din expresia x 1 \u003d f (x 0), a doua - x 2 \u003d f (x 1) , etc. În cazul general, aproximarea i+1 se găsește prin formula xi+1 =f(xi). Repetăm ​​această procedură până la |f(xi)|>e. Condiția de convergență a metodei iterației |f"(x)|
• 2)metoda lui Newton. La rezolvarea unei ecuații neliniare prin metoda Newton se stabilesc valoarea inițială a argumentului x 0 și precizia e. Apoi, în punctul (x 0, F (x 0)) trasăm o tangentă la graficul F (x). ) și determinați punctul de intersecție al tangentei cu axa absciselor x 1. În punctul (x 1, F (x 1)) construim din nou o tangentă, găsim următoarea aproximare a soluției dorite x 2 etc. Repetăm ​​această procedură până la |F(xi)| > e. Pentru a determina punctul de intersecție (i + 1) al tangentei cu axa absciselor, folosim următoarea formulă

x i+1 \u003d x i -F (x i) F "(x i).

Condiția de convergență pentru metoda tangentei F(x 0) F""(x)>0 etc.

3). metoda dihotomiei. Tehnica soluției se reduce la împărțirea treptată a intervalului inițial de incertitudine la jumătate conform formulei

C la \u003d a la + în / 2.

Pentru a-l alege pe cel necesar dintre cele două segmente rezultate, este necesar să găsim valoarea funcției la capetele segmentelor rezultate și să luăm în considerare cea pe care funcția își va schimba semnul, adică condiția f ( a k) * f (în k)<0.

Procesul de împărțire a segmentului se efectuează până când lungimea intervalului de incertitudine curent este mai mică decât precizia specificată, adică în k - a k< E. Тогда в качестве приближенного решения уравнения будет точка, соответствующая середине интервала неопределённости.

4). metoda acordurilor. Ideea metodei este că o coardă este construită pe segmentul care contractă capetele arcului graficului funcției y=f(x) și punctul c, intersecția coardei cu axa absciselor. , este considerată o valoare aproximativă a rădăcinii

c = a - (f(a) x (a-b)) / (f(a) - f(b)),

c \u003d b - (f (b) × (a-b)) / (f (a) - f (b)).

Următoarea aproximare se caută pe intervalul sau în funcție de semnele valorilor funcției în punctele a,b,c

x* O dacă f(c) H f(a) > 0;

x* O dacă f(c) x f(b)< 0 .

Dacă f "(x) nu își schimbă semnul în , atunci notând c \u003d x 1 și luând în considerare a sau b ca aproximare inițială, obținem formulele iterative ale metodei acordurilor cu un punct fix din dreapta sau din stânga.

x 0 \u003d a, x i + 1 \u003d x i - f (x i) (b-x i) / (f (b) -f (x i), cu f "(x) H f "(x)\u003e 0;

x 0 \u003d b, x i + 1 \u003d x i - f (x i) (x i -a) / (f (x i) -f (a), cu f "(x) H f "(x)< 0 .

Convergența metodei acordurilor este liniară

Ecuații algebrice și transcendentale. Metode de localizare a rădăcinilor.

Cea mai generală formă a ecuației neliniare:

f(x)=0 (2.1)

unde este functia f(x) este definită și continuă pe un interval finit sau infinit [a, b].

Definiție 2.1. Orice număr care inversează o funcție f(x) la zero se numește rădăcina ecuației (2.1).

Definiția 2.2. Un număr se numește rădăcina multiplicității k-a, dacă este împreună cu funcția f(x) derivatele sale de până la ordinul (k-1) inclusiv sunt egale cu zero:

Definiția 2.3. O singură rădăcină se numește rădăcină simplă.

Ecuațiile neliniare cu o variabilă sunt subîmpărțite în algebrice și transcendentale.

Definiție 2.4 . Ecuația (2.1) se numește algebrică dacă funcția F(x) este algebrică.

Prin transformări algebrice, din orice ecuație algebrică, se poate obține o ecuație în formă canonică:

unde sunt coeficienții reali ai ecuației, x este necunoscutul.

Din algebră se știe că fiecare ecuație algebrică are cel puțin o rădăcină reală sau două rădăcini conjugate complexe.

Definiția 2.5. Ecuația (2.1) se numește transcendentală dacă funcția F(x) nu este algebrică.

Rezolvarea ecuației (2.1) înseamnă:

• 1. Stabiliți dacă ecuația are rădăcini.
• 2. Determinați numărul de rădăcini ale ecuației.
• 3. Găsiți valorile rădăcinilor ecuației cu o precizie dată.

Ecuațiile întâlnite în practică adesea nu pot fi rezolvate prin metode analitice. Pentru rezolvarea unor astfel de ecuații se folosesc metode numerice.

Algoritmul pentru găsirea rădăcinii unei ecuații folosind o metodă numerică constă în două etape:

• 1) departament sau localizare rădăcină, adică stabilirea unui interval care conține o singură rădăcină:
• 2) clarificare valorile rădăcinii prin metoda aproximărilor succesive.

Metode de localizare a rădăcinilor. Baza teoretică a algoritmului de separare a rădăcinilor este teorema Cauchy asupra valorilor intermediare ale unei funcții continue.

Teorema 2.1. Dacă funcția y \u003d f (x) este continuă pe segmentul [a, b] și f (a) \u003d A, f (b) \u003d B, atunci pentru orice punct C situat între A și B, există un punct care.

Consecinţă. Dacă funcția y \u003d f (x) este continuă pe segmentul [a, b] și ia valori de diferite semne la capetele sale, atunci pe acest segment există cel puțin o rădăcină a ecuației f (x) \u003d 0.

Fie domeniul definiției și continuității unei funcții un segment finit [a,b]. Împărțiți segmentul în n părți: ,

Calculând secvențial valorile funcției în puncte, găsim astfel de segmente pentru care condiția este îndeplinită:

acestea. , sau, . Aceste segmente conțin cel puțin o rădăcină.

Teorema 2.2. Dacă funcția y \u003d f (x) este continuă pe segmentul [a; b), f (a) f (b)<0 и f`(х) на интервале (а;b) сохраняет знак, то внутри отрезка [а;b] существует единственный корень уравнения f(х) = 0.

Pentru a separa rădăcinile, puteți folosi și graficul funcției la= f (X). Rădăcinile ecuației (2.1) sunt acele valori X, la care graficul funcției y=f(x) traversează axa x. Construcția unui grafic al unei funcții, chiar și cu o precizie scăzută, oferă de obicei o idee despre locația rădăcinilor ecuației (2.1). Dacă trasarea funcției y \u003d f (x) cauzează dificultăți, atunci ecuația inițială (2.1) ar trebui convertită în forma c1(x)= c2(x) astfel încât graficele funcţiilor la= c1(x)și la= c2(x) au fost destul de simple. Abcisele punctelor de intersecție ale acestor grafice vor fi rădăcinile ecuației (2.1).

Exemplul 1 Separați rădăcinile ecuației x 2 -2cosx=0.

Soluţie. Să luăm în considerare două moduri de a separa rădăcinile.

• a) Calea grafică. Să rescriem ecuația sub forma x 2 =2cosx și să construim un grafic al funcțiilor y=x 2 și y=2cosx în același sistem de coordonate (Figura 5). întrucât aceste grafice se intersectează în două puncte, ecuația are două rădăcini situate simetric față de origine pe intervalele (-/2; 0) și (0; /2).
• b) Metoda analitică. Lăsa f(x)= x 2 -2cosx. pentru că f(x) este o funcție pară, este suficient să luăm în considerare numai valorile nenegative ale lui x. Datorită inegalității 2cosx2

Derivat f"(x)=2(x+sinx). Pe intervalul (0; /2) f"(x)>0, prin urmare, f(x) aici crește monoton și graficul său poate traversa axa X nu mai mult de un punct. observa asta f(0)=- 2<0, аf(/2)=(/2) 2>0. Aceasta înseamnă că ecuația are o rădăcină pozitivă situată pe intervalul (0; /2). Deoarece funcția este pară, ecuația are și o rădăcină negativă, simetrică față de cea pozitivă. Acum să trecem la rafinarea rădăcinii. Pentru a aplica metoda combinată de rafinare a rădăcinii, trebuie să vă asigurați că f ""(x) pe (0; /2) păstrează semnul și alegeți aproximarea inițială a rădăcinii pentru aplicarea metodei tangentei. Acesta trebuie să îndeplinească condiția: f(x)f ""(x)>0. pentru că f ""(x)=2(1+cosx) este pozitiv pe , atunci /2 poate fi luat ca aproximare inițială a rădăcinii în metoda tangentei. Prin urmare, se poate pune X=/21,570796, X 1 =0 (vezi diagrama algoritmului). În cazul nostru, metoda acordurilor va da o valoare aproximativă a rădăcinii cu un dezavantaj, iar metoda tangentei - cu un exces.

Luați în considerare un pas iterativ de rafinare a rădăcinii. Calculați valorile f(0), f(/2), f"(/2). Valori noi X 1 și X afla, respectiv, dupa formulele:

|x-x 1 |=0,387680,4>10 -4 =.

Precizia specificată nu este atinsă, iar calculele trebuie continuate.

Număr de iterație	X 1		f(x 1 )			|x- x 1 |

Prin urmare, valoarea aproximativă a rădăcinii cu precizia necesară a fost găsită în urma a trei iterații și este aproximativ egală cu 1,0217.

Datorită simetriei graficului funcţiei f(x) valoarea celei de-a doua rădăcini este aproximativ egală cu -1,0217.

Clarificarea rădăcinilor.

Formularea problemei . Să presupunem că rădăcina dorită a ecuației (2.1) este separată, i.e. segment [a; b], care are una și o singură rădăcină a ecuației. Orice punct al acestui segment poate fi luat ca valoare aproximativă a rădăcinii. Eroarea acestei aproximări nu depășește lungimea [A; b].În consecință, problema găsirii unei valori aproximative a rădăcinii cu o precizie dată se reduce la găsirea segmentului [a; b] (b - A<), содержащего только один корень уравнения (2.1). Эту задачу обычно называют задачей rafinamente de rădăcină.

Descrierea metodelor numerice. Metodele numerice fac posibilă găsirea de soluții la anumite probleme, știind dinainte că rezultatele obținute vor fi calculate cu o anumită eroare, prin urmare, pentru multe metode numerice, este necesar să se cunoască în prealabil „nivelul de precizie” la care soluția rezultată. va corespunde.

În acest sens, problema găsirii rădăcinilor unui polinom de forma (3.1)

prezintă un interes deosebit, deoarece formulele pentru găsirea rădăcinilor chiar și a unei ecuații cubice sunt destul de complicate. Dacă este necesar să găsim rădăcinile unui polinom al cărui grad este, de exemplu, 5, atunci nu se poate face fără ajutorul metodelor numerice, mai ales că probabilitatea ca un astfel de polinom să aibă rădăcini naturale (sau întregi, sau exacte cu un partea fracționară „scurtă”) este destul de mică și nu există formule pentru găsirea rădăcinilor unei ecuații de grad mai mare de 4. De facto, toate operațiunile ulterioare vor fi reduse la clarificarea rădăcinilor, ale căror intervale sunt aproximativ cunoscute dinainte. Cel mai simplu mod de a găsi aceste rădăcini „aproximate” este să folosești metode grafice.

Pentru a găsi rădăcinile unui polinom, există mai multe metode numerice: metoda iterației, metoda coardelor și tangentelor, metoda semidiviziunii, metoda secantei.

Metoda bisecției(cunoscută și ca „metoda de împărțire a unui segment în jumătate”) este, de asemenea, recursiv, adică prevede repetarea, ținând cont de rezultatele obținute.

Esența metodei de jumătate de împărțire este următoarea:

• - este dată funcţia F(x);
• - se determină eroarea admisibilă Q;
• - se definește un interval [ a , b ] care conține exact soluția ecuației.

1) Calculăm valoarea coordonatei E, luând mijlocul segmentului, i.e.

E \u003d (a + b) / 2 (3.2)

• 2) Calculați valorile F(a), F(b), F(E) și efectuați următoarea verificare: Dacă F(E)>Q, atunci rădăcina este găsită cu precizia specificată. Dacă F(E)
• 3) Treci la punctul 1.

Metoda iterațiilor simple (metoda aproximărilor succesive). Înlocuim ecuația (2.1) cu o ecuație echivalentă

x=(x) (3.3)

se poate face în diferite moduri, de exemplu

x=x+cf(x), c0. (3.4)

Să presupunem că se alege o aproximare inițială a rădăcinii ecuației (3.3). Definim o secvență numerică prin formule

X n+1 =(x n ), n=0,1,2,… (3.5)

O astfel de secvență se numește iterativă.

Dacă pe segmentul care conține x 0 și toate aproximările ulterioare x n , nN, funcția (x) are o derivată continuă "(x) și |"(x)|q<1, то итерационная последовательность (3.5) сходится к единственному на корню уравнения (3.3). Скорость сходимости определяется неравенством

Din această inegalitate, în special, rezultă că rata de convergență a metodei iterației simple depinde de valoarea lui q: cu cât q este mai mic, cu atât convergența este mai rapidă.

Prin urmare, în practică, la găsirea rădăcinilor prin metoda iterației simple, este de dorit să se reprezinte ecuația (2.1) sub forma (3.3) în așa fel încât derivata „(x) în vecinătatea rădăcinii să fie posibil. mai mic ca valoare absoluta.Pentru aceasta se foloseste uneori parametrul c din formula (3.4).

Metoda lui Newton (metoda tangentei). Dacă se cunoaște o aproximare inițială suficient de bună pentru care este valabilă următoarea inegalitate:

apoi puteți calcula singura rădăcină a ecuației folosind formula lui Newton

Ca o aproximare inițială, puteți utiliza limitele intervalului și:

Dacă este pornit.

La fiecare iterație a acestei metode, cantitatea de calcule este mai mare decât în ​​metodele bisecțiilor și iterațiilor, deoarece este necesar să se găsească nu numai valoarea funcției, ci și derivata acesteia. Cu toate acestea, rata de convergență a metodei lui Newton este mult mai mare.

Teorema. Fie rădăcina ecuației, adică , și este continuă. Apoi există o vecinătate a rădăcinii astfel încât, dacă aproximarea inițială aparține acestei vecinătăți, atunci pentru metoda lui Newton șirul de valori converge către at. Eroarea celei de-a aproximații a rădăcinii poate fi estimată prin formula:

unde este cea mai mare valoare a modulului derivatei a doua pe segment, este cea mai mică valoare a modulului primei derivate pe segment.

Regula oprire:

Metoda acordurilor și tangentelor (combinate). Această metodă se bazează pe construirea unui grafic schematic al unei funcții, determinarea intervalelor de intersecție a acesteia cu axa absciselor și apoi „comprimarea” acestui interval folosind coarde și tangente construite la graficul acestei funcții.

De remarcat că există și separat metoda acordurilor (dată valoarea rădăcinii cu o deficiență) și metoda tangentelor (cu un exces). Cu toate acestea, avantajul metodei combinate constă în „comprimarea pe două fețe” a segmentului considerat.

Luați în considerare următorul caz:

• - se da functia F(x) si se construieste graficul acesteia;
• - se determină eroarea admisibilă Q
• - pe baza graficului se definește un segment pe care graficul funcției intersectează axa absciselor, prin urmare, pe acest segment există o rădăcină a polinomului luat în considerare (o notăm cu A)

Algoritmul suplimentar este redus la următoarele acțiuni:

• 1) construim o tangentă la graficul funcției în punctul F(b)
• 2) calculăm coordonata x a intersecției tangentei cu axa absciselor conform formulei (3.9) și o notăm cu b "
• 3) construim o coardă la graficul funcției care trece prin punctele F(a) și F(b).
• 4) Calculăm punctul de intersecție al coardei cu axa absciselor după formula (2) și îl notăm cu a".

Astfel, obținem un nou segment , care (conform definițiilor unei coarde și unei tangente) conține încă soluția ecuației A.

Acum luăm segmentul ca un nou segment și repetăm ​​pașii 1-4 până când diferența F(b)-F(a) devine mai mică decât eroarea încorporată inițial Q. De asemenea, observăm că după aceasta se recomandă să luăm media aritmetică. F ca soluție dorită (a) și F(b).

Astfel, dacă coarda (tangenta) dă valoarea rădăcinii cu un exces, atunci această rădăcină este luată ca nouă limită dreaptă, iar dacă cu o deficiență, atunci cea stângă. În ambele cazuri, rădăcina exactă se află între punctele de intersecție ale coardei și tangenta cu axa absciselor.

Observații asupra metodei acordurilor și tangentelor. Deoarece rezolvarea problemei necesită găsirea derivatei funcției F(x), metoda coardelor și tangentelor este destul de dificil de implementat la nivel de program, deoarece regulile de calculare a derivatelor într-o formă generală sunt destul de greoaie pentru „înțelegerea” unui computer; la specificarea directă a derivatei pentru fiecare grad al polinomului, memoria computerului este serios încărcată, ceea ce încetinește foarte mult munca și setarea funcției și, în consecință, derivata acesteia direct în codul programului este inacceptabilă. Cu toate acestea, folosind această metodă, convergența intervalului la rădăcină are loc cel mai rapid, mai ales dacă metoda acordurilor și tangentelor este combinată cu metoda bisecției, deoarece mijlocul noului segment oferă adesea o soluție complet satisfăcătoare.

Metoda secantei. Metoda secantei poate fi obținută din metoda lui Newton prin înlocuirea derivatei cu o expresie aproximativă - formula diferenței:

Formula (3.8) folosește cele două aproximări anterioare u. Prin urmare, pentru o valoare inițială dată, este necesar să se calculeze următoarea aproximare, de exemplu, prin metoda Newton cu o înlocuire aproximativă a derivatei cu formula

Algoritmul metodei secantei:

1) sunt date valoarea inițială și eroarea. Calcula

2) pentru n= 1,2, ….. în timp ce condiția este îndeplinită, se calculează prin formula (3.8).

Formularea problemei

Separarea rădăcinilor

Rafinarea rădăcinii

1.2.3.2. Metoda iterației

1.2.3.4. metoda acordurilor

Formularea problemei

Ecuații algebrice

( 1.2.1-1)

ecuație transcendentală

(1.2.1-2)

Rafinarea iterativă a rădăcinilor.

În etapa de separare a rădăcinilor, se rezolvă problema găsirii celor mai înguste segmente posibile, care conține una și o singură rădăcină a ecuației.

Etapa de rafinare a rădăcinii are ca scop calcularea unei valori aproximative a rădăcinii cu o precizie dată. În acest caz, se folosesc metode iterative pentru calcularea aproximărilor succesive la rădăcină: x 0 , x 1 , ..., x n , ..., în care fiecare aproximare ulterioară x n+1 este calculată pe baza x n anterior. Fiecare pas se numește iterație. Dacă șirul x 0 , x 1 , ..., x n , … ca n ® ¥ are o limită egală cu valoarea rădăcinii , atunci se spune că procesul iterativ converge.

Există diferite moduri de a separa și rafina rădăcinile, despre care vom discuta mai jos.

Separarea rădăcinilor

Rădăcina ecuației f(x)=0 este considerată separată (localizată) pe segment dacă această ecuație nu are alte rădăcini pe acest segment. Pentru a separa rădăcinile ecuației, este necesar să împărțiți intervalul de valori admisibile ale funcției f(x) în segmente suficient de înguste, fiecare dintre ele conținând doar o rădăcină. Exista graficși analitic metode de separare a rădăcinilor.

Rafinarea rădăcinii

Sarcina de a rafina rădăcina ecuației cu precizie separată de interval este de a găsi o astfel de valoare aproximativă a rădăcinii pentru care inegalitatea . Dacă ecuația nu are una, ci mai multe rădăcini, atunci etapa de rafinare este efectuată pentru fiecare rădăcină separată.

Metoda semidiviziunii

Fie rădăcina ecuației f(x)=0 separată pe segment, adică există o singură rădăcină pe acest segment, iar funcția pe acest segment este continuă.

Metoda bisecției vă permite să obțineți o succesiune de segmente imbricate , , …,,…, astfel încât f(a i).f(b i)< 0 , unde i=1,2,…,n, iar lungimea fiecărui segment următor este jumătate din lungimea celui precedent:

Îngustarea secvențială a segmentului în jurul valorii necunoscute a rădăcinii asigură execuția la un pas n inegalități |b n - a n |< e. Поскольку при этом для любого хÎ будет выполняться неравенство | - х| <, то с точностью любое

Poate fi luată ca o valoare aproximativă a rădăcinii, de exemplu, punctul său de mijloc

În metoda bisecției, de la iterație la iterație, lungimea segmentului inițial este redusă constant la jumătate (Fig. 1.2.3-1). Prin urmare, la a n-a etapă, următoarea estimare a erorii rezultatului este valabilă:

( 1.2.3-1)

unde este valoarea exactă a rădăcinii, x n н este valoarea aproximativă a rădăcinii la pasul a n-a.

Comparând estimarea erorii rezultată cu precizia dată, putem estima numărul necesar de pași:

(1.2.3-2)

Din formula se poate observa că scăderea valorii e(creșterea preciziei) duce la o creștere semnificativă a numărului de calcule, prin urmare, în practică, metoda semidiviziunii este utilizată pentru o găsire relativ brută a rădăcinii, iar rafinarea sa ulterioară este efectuată folosind alte metode mai eficiente .

Orez. 1.2.3-2. Schema algoritmului metodei bisectiei

Schema algoritmului de bisectie este prezentata in fig. 1.2.3-2. Algoritmul de mai sus presupune că partea stângă a ecuației f(x) este proiectată ca un modul software.

Exemplul 1.2.3-1. Specificați rădăcina ecuației x 3 +x-1=0 cu o precizie de =0,1, care este localizată pe segmentul .

Rezultatele sunt prezentate convenabil utilizând Tabelul 1.2.3-3.

Tabelul 1.2.3-3

k	A	b	fa)	f(b)	(a+b)/2	f((a+b)/2)	un k	b k
			-1		0.5	-0.375	0.5
	0.5		-0.375		0.75	0.172	0.5	0.75
	0.5	0.75	-0.375	0.172	0.625	-0.131	0.625	0.75
	0.625	0.75	-0.131	0.172	0.688	0.0136	0.625	0.688

După a patra iterație, lungimea segmentului |b 4 -a 4 | = |0,688-0,625| = 0,063 a devenit mai mic decât valoarea e, prin urmare, pentru valoarea aproximativă a rădăcinii, puteți lua valoarea mijlocului acestui segment: x \u003d (a 4 + b 4) / 2 \u003d 0,656 .

Valoarea funcției f(x) în punctul x = 0,656 este f(0,656) = -0,062 .

Metoda iterației

Metoda iterației presupune înlocuirea ecuației f(x)=0 cu o ecuație echivalentă x=j(x). Dacă rădăcina ecuației este separată pe segmentul , atunci pe baza aproximării inițiale x 0 н, puteți obține o succesiune de aproximări la rădăcină

x 1 \u003d j (x 0), x 2 \u003d j (x 1), ..., , ( 1.2.3-3)

unde funcția j(x) se numește funcție iterativă.

Condiția de convergență pentru metoda iterației simple este determinată de următoarea teoremă.

Lasă rădăcina X* ecuații x=j(x) separate pe un segmentși a construit o succesiune de aproximări conform regulii x n \u003d j (x n -1) . Atunci dacă toți membrii secvenței x n =j(x n -1) н și există așa ceva q(0 asta pentru toata lumea x О efectuat|j'(x)| = q<1, atunci această secvență este convergentă și limita șirului este valoarea rădăcinii X* , adică procesul de iterație converge către rădăcina ecuației indiferent de aproximarea inițială.

Astfel, dacă este îndeplinită condiția de convergență a metodei iterației, atunci șirul x 0 , x 1 , x 2 , …, x n ,…, obținut cu formula x n +1 = j(x n ), converge la valoarea exactă a rădăcinii:

Condiția j(x)н pentru xн înseamnă că toate aproximațiile x 1 , x 2 , …, x n ,… obținute prin formula iterativă trebuie să aparțină segmentului în care este separată rădăcina.

Pentru a estima eroarea metodei iterației, condiția

pe număr q poate lua cea mai mare valoare |j"(x)| , iar procesul de iterații ar trebui continuat până la inegalitatea

(1.2.3-5)

În practică, se utilizează adesea o formulă simplificată de estimare a erorilor. De exemplu, dacă 0

|x n -1 - x n | £ .

Folosind formula iterativă x n +1 = j(x n) vă permite să obțineți valoarea rădăcinii ecuației f(x)=0 cu orice grad de precizie .

Ilustrarea geometrică a metodei iterației. Pe planul X0Y, trasăm graficele funcțiilor y=x și y=j(x ). Rădăcina ecuației x=j(x) este abscisa punctului de intersecție a graficelor funcției y = j(x ) și direct y=x. Să luăm o aproximare inițială x 0 н . Pe curba y \u003d j (x) corespunde punctului A 0 \u003d j (x 0). Pentru a găsi următoarea aproximare, trageți o linie dreaptă orizontală prin punctul A 0 până la intersecția cu linia dreaptă y \u003d x (punctul B 1) și coborâți perpendiculara pe intersecția cu curba (punctul A 1), adică x 1 \u003d j (x 0) . Continuând construcția în mod similar, avem o linie întreruptă A 0, B 1, A 1, B 2, A 2 ..., pentru care abscisele comune ale punctelor sunt o aproximare succesivă x 1, x 2, . .., x n („scara”) la rădăcina X*. Din fig. 1.2.3-3a se poate observa că procesul converge către rădăcina ecuației.

Considerăm acum o altă formă a curbei y = j(x) (Fig. 1.2.6b). În acest caz, linia întreruptă A 0 , B 1 , A 1 , B 2 , A 2 ... are forma unei „spirale”. Cu toate acestea, în acest caz, se observă și convergență.

Este ușor de observat că în primul caz derivata satisface condiția 0< j’(x)< 1, а во втором случае производная j’(x)<0иj’(x)>-unu. Astfel, este evident că dacă |j'(x)|<1, то процесс итераций сходится к корню.

Acum considerăm cazurile în care |j'(x) |> 1. În fig. 1.2.3-4a arată cazul când j'(x)>1, iar în fig. 1.2.3-4b - când j'(x)< -1. В обоих случаях процесс итерации расходится, то есть, полученное на очередной итерации значение х все дальше удаляется от истинного значения корня.

Modalități de îmbunătățire a convergenței procesului de iterație. Luați în considerare două opțiuni pentru reprezentarea funcției j(x) în tranziția de la ecuația f(x) la x=j(x).

1. Fie funcția j(x) diferențiabilă și monotonă în vecinătățile rădăcinii și să existe un număr k £ |j‘(x)|, unde k ³ 1 (adică procesul diverge). Să înlocuim ecuația x=j(x) cu ecuația ei echivalentă x=Y(x ) , Unde Y(x) = 1/j(x)(să trecem la funcția inversă). Apoi

ceea ce înseamnă q=1/k< 1 и процесс будет сходиться.

2. Reprezentăm funcția j(x) ca j(x) = x - lf(x), unde l este coeficientul , nu este egal

zero. Pentru ca procesul să converge, este necesar ca
0<|j¢(x)| = |1 - lf¢(x)| < 1. Возьмем l= 2/(m 1 +M 1 ), unde m 1 și M 1 sunt valorile minime și maxime ale lui f'(x) (m 1 =min|f'(x)|, M 1 =max|f'(x)|) pentru хн, i.e. 0£ m 1 £ f¢(x) £ M 1 £1. Apoi

iar procesul va converge, formula recursivă are forma

Dacă f¢(x)< 0, то в рекуррентной формуле f(x) следует умножить на -1 .

Parametrul λ poate fi determinat și de regula:

Dacă , atunci , și dacă , atunci , unde .

Schema algoritmului metodei iterației este prezentată în fig. 1.2.3-5.

Ecuația originală f(x)=0 a fost transformată într-o formă convenabilă pentru iterații: partea stângă a ecuației originale f(x) și funcția de iterare fi(x) din algoritm sunt proiectate ca module software separate.

Orez. 1.2.3-5. Diagrama algoritmului metodei iterației

Exemplul 1.2.3-2. Rafinați rădăcina ecuației 5x – 8∙ln(x) – 8 =0 cu o precizie de 0,1, care este localizată pe intervalul .

Aducem ecuația într-o formă convenabilă pentru iterații:

Prin urmare, pentru valoarea aproximativă a rădăcinii ecuației, luăm valoarea x 3 =3,6892, care asigură precizia necesară a calculelor. În acest punct f(x 3)=0,0027.

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) și 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 .

Rezultatele calculului obținute folosind formula
1.2.3-14 sunt prezentate în Tabelul 1.2.3-4.

Tabelul 1.2.3-4

Orez. 1.2.3-10. Schema algoritmului metodei acordurilor

Ecuația neliniară este

1) ecuație algebrică sau transcendentală

2) ecuație algebrică

3) ecuație trigonometrică

4) ecuație transcendentală

Subiectul 1.2. Metode de rezolvare a ecuațiilor neliniare

Formularea problemei

Separarea rădăcinilor

1.2.2.1. Separarea grafică a rădăcinilor

1.2.2.2. Ramura analitică a rădăcinilor

Rafinarea rădăcinii

1.2.3.1. Metoda semidiviziunii

1.2.3.2. Metoda iterației

1.2.3.3. metoda lui Newton (metoda tangentei)

1.2.3.4. metoda acordurilor

1.2.3.5. Compararea metodelor de rezolvare a ecuaţiilor neliniare

1.2.4. Sarcini de testare pe tema „Metode de rezolvare a ecuațiilor neliniare”

Formularea problemei

Una dintre cele mai importante și mai frecvente probleme de analiză matematică este problema determinării rădăcinilor unei ecuații cu o necunoscută, care poate fi reprezentată în formă generală ca f(x) = 0. În funcție de forma funcției f( x), se disting ecuațiile algebrice și transcendentale. Ecuații algebrice se numesc ecuații în care valoarea funcției f(x) este un polinom de gradul al n-lea:

f (x) \u003d P (x) \u003d a n x n + a 2 x 2 + ... + a 1 x + a 0 \u003d 0. ( 1.2.1-1)

Orice ecuație non-algebrică se numește ecuație transcendentală. Funcția f(x) în astfel de ecuații este cel puțin una dintre următoarele funcții: exponențială, logaritmică, trigonometrică sau trigonometrică inversă.

Soluția ecuației f (x) \u003d 0 este mulțimea de rădăcini, adică astfel de valori ale variabilei independente pentru care ecuația se transformă într-o identitate. Cu toate acestea, valorile exacte ale rădăcinilor pot fi găsite doar analitic pentru unele tipuri de ecuații. În special, formulele care exprimă soluția unei ecuații algebrice pot fi obținute numai pentru ecuații care nu sunt mai mari de gradul al patrulea. Există și mai puține oportunități de a obține o soluție exactă a ecuațiilor transcendentale. Trebuie remarcat faptul că problema găsirii valorilor exacte ale rădăcinilor nu este întotdeauna corectă. Deci, dacă coeficienții ecuației sunt numere aproximative, acuratețea valorilor calculate ale rădăcinilor cu siguranță nu poate depăși acuratețea datelor originale. Aceste circumstanțe ne obligă să luăm în considerare posibilitatea de a găsi rădăcinile ecuației cu o precizie limitată (rădăcini aproximative).

Problema găsirii rădăcinii unei ecuații cu o precizie dată ( > 0) este considerată rezolvată dacă se calculează o valoare aproximativă care diferă de valoarea exactă a rădăcinii cu cel mult valoarea e

(1.2.1-2)

Procesul de găsire a rădăcinii aproximative a ecuației constă în două etape:

1) separarea rădăcinilor (localizarea rădăcinilor);

Ecuațiile care conțin funcții necunoscute ridicate la o putere mai mare decât unu se numesc neliniare.
De exemplu, y=ax+b este o ecuație liniară, x^3 - 0,2x^2 + 0,5x + 1,5 = 0 este neliniară (în general scrisă ca F(x)=0).

Un sistem de ecuații neliniare este soluția simultană a mai multor ecuații neliniare cu una sau mai multe variabile.

Există multe metode rezolvarea ecuațiilor neliniareși sisteme de ecuații neliniare, care sunt de obicei clasificate în 3 grupe: numerice, grafice și analitice. Metodele analitice fac posibilă determinarea valorilor exacte ale soluției ecuațiilor. Metodele grafice sunt cele mai puțin precise, dar permit în ecuații complexe determinarea celor mai aproximative valori, din care în viitor puteți începe să găsiți soluții mai precise ale ecuațiilor. Rezolvarea numerică a ecuațiilor neliniare presupune parcurgerea a două etape: separarea rădăcinii și rafinarea acesteia la o anumită precizie specificată.
Separarea rădăcinilor se realizează în diverse moduri: grafic, folosind diverse programe de calculator specializate etc.

Să luăm în considerare mai multe metode de rafinare a rădăcinilor cu o precizie specifică.

Metode pentru rezolvarea numerică a ecuațiilor neliniare

metoda semidiviziunii.

Esența metodei de împărțire pe jumătate este de a împărți intervalul în jumătate (с=(a+b)/2) și de a arunca partea din interval în care nu există rădăcină, adică. condiția F(a)xF(b)

Fig.1. Folosind metoda semidiviziunii în rezolvarea ecuațiilor neliniare.

Luați în considerare un exemplu.

Să împărțim segmentul în 2 părți: (a-b)/2 = (-1+0)/2=-0,5.
Dacă produsul F(a)*F(x)>0, atunci începutul segmentului a este transferat la x (a=x), în caz contrar, sfârșitul segmentului b este transferat în punctul x (b=x ). Împărțim din nou segmentul rezultat în jumătate etc. Toate calculele sunt prezentate în tabelul de mai jos.

Fig.2. Tabelul rezultatelor calculului

În urma calculelor, obținem valoarea, ținând cont de precizia cerută, egală cu x=-0,946

metoda acordurilor.

Când se utilizează metoda acordurilor, este specificat un segment în care există o singură rădăcină cu precizia specificată e. Se trasează o linie (coardă) prin punctele din segmentul a și b, care au coordonatele (x(F(a); y(F(b))). În continuare, punctele de intersecție ale acestei drepte cu axa absciselor (punctul z) sunt determinate.
Dacă F(a)xF(z)

Fig.3. Utilizarea metodei acordurilor în rezolvarea ecuaţiilor neliniare.

Luați în considerare un exemplu. Este necesar să se rezolve ecuația x^3 - 0,2x^2 + 0,5x + 1,5 = 0 până la e

În general, ecuația arată astfel: F(x)= x^3 - 0,2x^2 + 0,5x + 1,5

Găsiți valorile lui F(x) la capetele segmentului:

F(-1) = - 0,2>0;

Să definim derivata a doua F''(x) = 6x-0.4.

F''(-1)=-6,4
F''(0)=-0,4

La capetele segmentului se respectă condiția F(-1)F’’(-1)>0, prin urmare, pentru a determina rădăcina ecuației, folosim formula:

Toate calculele sunt prezentate în tabelul de mai jos.

Fig.4. Tabelul rezultatelor calculului

În urma calculelor, obținem valoarea, ținând cont de precizia cerută, egală cu x=-0,946

Metoda tangentei (Newton)

Această metodă se bazează pe construcția tangentelor la grafic, care sunt desenate la unul dintre capetele intervalului. În punctul de intersecție cu axa X (z1), este construită o nouă tangentă. Această procedură continuă până când valoarea obținută este comparabilă cu parametrul de precizie dorit e (F(zi)

Fig.5. Folosind metoda tangentelor (Newton) în rezolvarea ecuațiilor neliniare.

Luați în considerare un exemplu. Este necesar să se rezolve ecuația x^3 - 0,2x^2 + 0,5x + 1,5 = 0 până la e

În general, ecuația arată astfel: F(x)= x^3 - 0,2x^2 + 0,5x + 1,5

Să definim prima și a doua derivată: F'(x)=3x^2-0.4x+0.5, F''(x)=6x-0.4;

F''(-1)=-6-0,4=-6,4
F''(0)=-0,4
Condiția F(-1)F''(-1)>0 este îndeplinită, deci calculele se fac după formula:

Unde x0=b, F(a)=F(-1)=-0,2

Toate calculele sunt prezentate în tabelul de mai jos.

Fig.6. Tabelul rezultatelor calculului

În urma calculelor, obținem valoarea, ținând cont de precizia cerută, egală cu x=-0,946

Luați în considerare problema găsirii rădăcinilor ecuației neliniare

Rădăcinile ecuației (1) sunt acele valori ale lui x care, la înlocuire, îl transformă într-o identitate. Doar pentru cele mai simple ecuații se poate găsi o soluție sub formă de formule, adică. formă analitică. Mai des este necesară rezolvarea ecuațiilor prin metode aproximative, cele mai răspândite dintre care, în legătură cu apariția computerelor, sunt metodele numerice.

Algoritmul pentru găsirea rădăcinilor prin metode aproximative poate fi împărțit în două etape. În primul rând, se studiază locația rădăcinilor și se efectuează separarea acestora. Există o zonă în care există o rădăcină a ecuației sau o aproximare inițială a rădăcinii x 0 . Cel mai simplu mod de a rezolva această problemă este studierea graficului funcției f(x) . În cazul general, pentru a-l rezolva, este necesar să se implice toate mijloacele de analiză matematică.

Existența pe intervalul găsit a cel puțin unei rădăcini a ecuației (1) rezultă din condiția Bolzano:

f(a)*f(b)<0 (2)

De asemenea, se presupune că funcția f(x) este continuă pe segmentul dat. Cu toate acestea, această condiție nu răspunde la întrebarea despre numărul de rădăcini ale ecuației pe un interval dat. Dacă cerința de continuitate a funcției este completată cu cerința monotonității acesteia și aceasta decurge din constanța semnului derivatei întâi, atunci putem afirma existența unei rădăcini unice pe un segment dat.

La localizarea rădăcinilor, este, de asemenea, important să cunoașteți proprietățile de bază ale acestui tip de ecuație. De exemplu, amintiți-vă câteva proprietăți ale ecuațiilor algebrice:

unde sunt coeficienții reali.

• a) O ecuație de grad n are n rădăcini, dintre care pot fi atât reale, cât și complexe. Rădăcinile complexe formează perechi conjugate complexe și, prin urmare, ecuația are un număr par de astfel de rădăcini. Pentru o valoare impară a lui n, există cel puțin o rădăcină reală.
• b) Numărul de rădăcini reale pozitive este mai mic sau egal cu numărul de semne variabile din succesiunea coeficienților. Înlocuirea x cu -x în ecuația (3) vă permite să estimați numărul de rădăcini negative în același mod. iterație dihotomie newton neliniară

La a doua etapă a rezolvării ecuației (1), folosind aproximarea inițială obținută, se construiește un proces iterativ care face posibilă rafinarea valorii rădăcinii cu o anumită precizie predeterminată. Procesul iterativ constă în perfecţionarea succesivă a aproximării iniţiale. Fiecare astfel de pas se numește iterație. Ca rezultat al procesului de iterație, se găsește o succesiune de valori aproximative ale rădăcinilor ecuației. Dacă această secvență se apropie de adevărata valoare a rădăcinii x pe măsură ce n crește, atunci procesul iterativ converge. Se spune că un proces iterativ converge la cel puțin ordinul m dacă este îndeplinită următoarea condiție:

unde С>0 este o constantă. Dacă m=1, atunci se vorbește de convergență de ordinul întâi; m=2 - despre pătratică, m=3 - despre convergența cubică.

Ciclurile iterative se încheie dacă, pentru o anumită eroare admisibilă, sunt îndeplinite criteriile pentru abaterile absolute sau relative:

sau micimea reziduului:

Această lucrare este dedicată studiului unui algoritm de rezolvare a ecuațiilor neliniare folosind metoda lui Newton.

Departament: ASOIiU

Lucrări de laborator

Pe tema: GĂSIREA RĂDĂDINII UNEI ECUAȚII NELINIARE. METODE DE REZOLVARE A UNUI SISTEM DE ECUATII NELINIARE

Moscova, 2008

GĂSIREA RĂDĂDINII UNEI ECUAȚII NELINIARE

1. Enunțarea problemei

Să fie dată o funcție care este continuă împreună cu numeroasele sale derivate. Este necesar să găsiți toate sau unele rădăcini reale ale ecuației

Această sarcină este împărțită în mai multe subsarcini. În primul rând, este necesar să se determine numărul de rădăcini, să se investigheze natura și locația acestora. În al doilea rând, găsiți valorile aproximative ale rădăcinilor. În al treilea rând, alegeți rădăcinile care ne interesează dintre ele și calculați-le cu exactitatea necesară e. Prima și a doua sarcină sunt rezolvate, de regulă, prin metode analitice sau grafice. În cazul în care se caută doar rădăcinile reale ale ecuației (1), este util să se întocmească un tabel cu valorile funcției. Dacă funcția are semne diferite în două noduri vecine ale tabelului, atunci între aceste noduri se află un număr impar de rădăcini ale ecuației (cel puțin una). Dacă aceste noduri sunt apropiate, atunci cel mai probabil există o singură rădăcină între ele.

Valorile aproximative găsite ale rădăcinilor pot fi rafinate folosind diferite metode iterative. Să luăm în considerare trei metode: 1) metoda dihotomiei (sau împărțirea segmentului la jumătate); 2) metoda iterației simple și 3) metoda lui Newton.

2. Metode de rezolvare a problemei

2.1 Metoda de împărțire a unui segment în jumătate

Cea mai simplă metodă de găsire a rădăcinii ecuației neliniare (1) este metoda semidiviziunii.

Să fie dată o funcție continuă pe segment.Dacă valorile funcției de la capetele segmentului au semne diferite, i.e. atunci aceasta înseamnă că în interiorul segmentului dat există un număr impar de rădăcini. Să avem, pentru certitudine, o singură rădăcină. Esența metodei este de a reduce la jumătate lungimea segmentului la fiecare iterație. Găsim mijlocul segmentului (vezi Fig. 1) Calculați valoarea funcției și selectați segmentul pe care funcția își schimbă semnul. Împărțiți din nou noul segment în jumătate. Și continuăm acest proces până când lungimea segmentului este egală cu eroarea predeterminată în calcularea rădăcinii e. Construcția mai multor aproximări succesive conform formulei (3) este prezentată în Figura 1.

Deci, algoritmul metodei dihotomiei:

1. Setați distanța și eroarea e.

2. Dacă f(a) și f(b) au aceleași semne, emite un mesaj despre imposibilitatea de a găsi rădăcina și stop.

Fig.1. Metoda împărțirii în jumătate a unui segment pentru rezolvarea unei ecuații de forma f(x)=0.

3. Altfel se calculează c=(a+b)/2

4. Dacă f(a) și f(c) au semne diferite, puneți b=c, în caz contrar a=c.

5. Dacă lungimea noului segment este , atunci calculați valoarea rădăcinii c=(a+b)/2 și opriți, în caz contrar treceți la pasul 3.

Deoarece lungimea segmentului este redusă de 2 N ori în N pași, eroarea dată în găsirea rădăcinii e va fi atinsă în iterații.

După cum se poate observa, rata de convergență este scăzută, dar avantajele metodei includ simplitatea și convergența necondiționată a procesului iterativ. Dacă segmentul conține mai mult de o rădăcină (dar un număr impar), atunci va fi întotdeauna găsită una.

Cometariu. Pentru a determina intervalul în care se află rădăcina, este necesară o analiză suplimentară a funcției, bazată fie pe estimări analitice, fie pe utilizarea unei metode de soluție grafică. De asemenea, este posibil să se organizeze o căutare a valorilor funcției în diferite puncte până când condiția de schimbare a semnului funcției este îndeplinită

2.2 Metoda simplă de iterație

Când utilizați această metodă, ecuația neliniară originală (1) trebuie rescrisă în formă

Să notăm rădăcina acestei ecuații ca C * . Fie cunoscută aproximarea inițială a rădăcinii. Înlocuind această valoare în partea dreaptă a ecuației (2), obținem o nouă aproximare

etc. Pentru pasul (n+1), obținem următoarea aproximare

(3)

Astfel, conform formulei (3), obținem o secvență С 0 , С 1 ,…,С n +1 , care tinde spre rădăcina С * la n®¥. Procesul iterativ se oprește dacă rezultatele a două iterații succesive sunt apropiate, adică condiția

(4)

Să studiem condiția și rata de convergență a șirului numeric (C n ) pentru n®¥. Amintiți-vă definiția ratei de convergență. O secvență (C n ) convergentă către limita С * are o rată de convergență de ordin a dacă, pentru n®¥, condiția

Să presupunem că are o derivată continuă, atunci eroarea la pasul (n+1)-a iterație e n +1 =C n +1 -C * =g(C n)-g(C *) poate fi reprezentată ca o serie

e n+1 » C n+1 – C * = g¢(C *) (C n -C *) +¼@ g¢(C *) e n +¼

Astfel, obținem asta cu condiția

çg¢(C *) ç<1(6)

secvența (3) va converge către rădăcină cu o viteză liniară a=1. Condiția (6) este o condiție pentru convergența metodei iterației simple. Evident, succesul metodei depinde de cât de bine este aleasă funcția.

De exemplu, pentru a extrage rădăcina pătrată, adică pentru a rezolva o ecuație de forma x \u003d a 2, puteți pune

x \u003d g 1 (x) \u003d a / x (7a)

x=g 2 (x)=(x+a/x)/2.(7b)

Este ușor să arăți asta

½g 1" (C)½=1,

½g 2" (C)½<1.

Astfel, primul proces (7a) nu converge deloc, în timp ce al doilea (7b) converge pentru orice aproximare inițială C 0 >0.

Orez. 2. Interpretarea grafică a metodei iterațiilor simple pentru rezolvarea unei ecuații de forma x=g(x).

Construirea mai multor aproximări succesive prin formula (3)

С 0 , С 1 , …, С n = C *

prezentat în figura 2.

2.3 Metoda lui Newton

În literatură, această metodă este adesea numită metoda tangentei, precum și metoda liniarizării. Alegem aproximația inițială С 0 . Să presupunem că abaterea С 0 de la valoarea adevărată a rădăcinii С * este mică, apoi, extinzând f(C *) într-o serie Taylor în punctul С 0 , obținem

f(C *) = f(C 0) + f¢(C 0) (C * -C 0) +¼(8)

Dacă f¢(C 0) ¹ 0 , atunci în (8) ne putem limita la termeni liniari în DC =C-C 0 . Având în vedere că f(C *)=0, din (9) putem găsi următoarea aproximare pentru rădăcină

C 1 \u003d C 0 - f (C 0) / f¢ (C 0)

sau pentru aproximația (n+1).

C n+1 = C n – f (C n) / f ¢(C n) (9)

Pentru a încheia procesul iterativ, poate fi utilizată una dintre cele două condiții

çC n +1 – C n ç

çf(C n +1) ç

Studiul convergenței metodei lui Newton se realizează în mod similar cu cazul precedent. Obțineți asta în mod independent în condițiile

½f""(C)/2f"(C)½<1.

Metoda lui Newton are o rată de convergență pătratică ().

Orez. 3. Interpretarea grafică a metodei lui Newton de rezolvare a unei ecuații de forma f(x)=0.

Construirea mai multor aproximări succesive prin formula (9)

С 0 , С 1 , …, С n = C *

prezentat în figura 3.

1. Pentru o funcție dată f(x)

Determinați numărul de rădăcini reale ale ecuației f(x)=0, locația acestora și valorile aproximative (construiți un grafic sau imprimați un tabel de valori).

· Calculați una dintre rădăcinile găsite (oricare) cu o precizie de e=0,5*10 -3 .

Pentru calcule, utilizați metoda împărțirii segmentului la jumătate (determinați numărul de iterații), apoi găsiți aceeași rădăcină folosind metoda lui Newton (determinând și numărul de pași de iterație).

Comparați rezultatele.

Opțiuni de sarcină

1.x3 –3x 2 +6x – 5 = 0 2.x3 +sinx –12x-1=0

3. x 3 –3x 2 –14x – 8 = 0 4. 3x + cos x + 1 =0

5. x 2 +4sin x -1 = 0 6. 4x -ln x = 5

7. x 6 –3x 2 +x – 1 = 0 8. x 3 – 0,1x 2 +0,3x –0,6 = 0

9.10. (x -1) 3 + 0,5e x = 0

11.12.x5 -3x2 + 1 = 0

13. x 3 -4x 2 -10x -10 = 0 14.

15. 16.

19. 20.

23. 24. x 4 - 2.9x 3 +0.1x 2 + 5.8x - 4.2=0

25.x4 +2.83x3 - 4.5x2 -64x-20=0 26.

METODE DE REZOLVARE A UNUI SISTEM DE ECUATII NELINIARE

1. Formularea problemei

Să fie necesar să se rezolve un sistem de n ecuații neliniare:

(1)

Nu există metode directe de rezolvare a sistemului (1). Doar în unele cazuri acest sistem poate fi rezolvat direct. De exemplu, pentru cazul a două ecuații, uneori este posibil să se exprime o variabilă necunoscută în termenii alteia și astfel să se reducă problema la rezolvarea unei ecuații neliniare în raport cu o necunoscută.

Sistemul de ecuații (1) poate fi scris pe scurt sub formă vectorială:

. (2)

Ecuația (2) poate avea una sau mai multe rădăcini în domeniul D. Se cere să se stabilească existența rădăcinilor ecuației și să se găsească valorile aproximative ale acestor rădăcini. Pentru găsirea rădăcinilor se folosesc de obicei metode iterative, în care alegerea aproximării inițiale este de o importanță fundamentală. Aproximarea inițială este uneori cunoscută din considerente fizice. În cazul a două necunoscute, aproximarea inițială poate fi găsită grafic: trasați curbele f 1 (x 1 , x 2)=0 și f 2 (x 1 , x 2)=0 pe planul (x 1 , x 2). ) și găsiți punctele lor de intersecție. Pentru trei sau mai multe variabile (precum și pentru rădăcini complexe), nu există modalități satisfăcătoare de a selecta aproximarea inițială.

Să luăm în considerare două metode iterative principale pentru rezolvarea sistemului de ecuații (1), (2) - metoda iterației simple și metoda lui Newton.

2. Metode de rezolvare a unui sistem de ecuaţii neliniare

2.1 Metoda simplă de iterație

Să reprezentăm sistemul (1) sub forma

(3)

sau sub formă vectorială:

(4)

Algoritmul metodei de iterație simplă este următorul. Alegem o aproximare zero

Următoarea aproximare se găsește prin formulele:

sau mai detaliat:

(5)

Procesul iterativ (5) continuă până când modificările tuturor necunoscutelor din două iterații succesive devin mici, i.e.

În practică, inegalitatea este adesea folosită în locul ultimei condiții:

(6)

unde este norma rms a unui vector n-dimensional , adică

Atunci când se utilizează această metodă, succesul este determinat în mare măsură de o alegere bună a aproximării inițiale: ar trebui să fie suficient de aproape de soluția adevărată. În caz contrar, este posibil ca procesul iterativ să nu convergă. Dacă procesul converge, atunci rata sa de convergență este liniară.

2.2. metoda lui Newton

În literatura tradusă, puteți găsi numele Metoda Newton-Raphson. Această metodă converge mult mai rapid decât metoda simplă de iterație.

Să fie cunoscută o aproximare a rădăcinii, astfel încât

Atunci sistemul original (2) poate fi scris după cum urmează:

Expandând ecuația (7) într-o serie Taylor în vecinătatea punctului și limitându-ne la termeni liniari în abatere, obținem:

sau sub formă de coordonate:

(8)

Sistemul (8) poate fi rescris ca:

(9)

Sistemul rezultat (9) este un sistem de ecuații algebrice liniare în raport cu incremente

Valoarea funcțiilor F 1 , F 2 , …, F n și a derivatelor acestora din (9) se calculează la

.

Determinantul sistemului (9) este J jacobian:

(10)

Pentru existența unei soluții unice a sistemului de ecuații (9), aceasta trebuie să fie diferită de zero. După rezolvarea sistemului (9), de exemplu, prin metoda Gauss, găsim o nouă aproximare:

.

Verificăm starea (6). Dacă nu este satisfăcut, găsim și Jacobianul (10) cu o nouă aproximare și din nou rezolvăm (9), astfel, găsim a 2-a aproximare și așa mai departe.

Iterațiile se opresc de îndată ce condiția (6) este îndeplinită.

Folosind metoda lui Newton, găsiți soluții la un sistem de ecuații neliniare cu o precizie dată. Examinați convergența procesului iterativ.

Opțiuni de sarcină

1 2

3 4

5 6

7 8

9 10

11 12

13 14.

15. 16.

17. 18.

19. 20.

21. 22.