Metode Numerice In Algebra Liniara Si Metode Iterative Pentru Rezolvarea Sistemelor Neliniare

Politehnica

Metode Numerice In Algebra Liniara Si Metode Iterative Pentru Rezolvarea Sistemelor Neliniare

Byadmin ianuarie 1, 2024

Metode numerice în algebra liniară și metode iterative pentru rezolvarea sistemelor neliniare

Cuprins

1.ALGEBRA LINIARĂ

1.1 Spațiile vectoriale

1.2 Transformările liniare

1.3 Subspațiile, sectoarele și bazele

1.4Metoda eliminării complete (Gauss-Jordan)

1.4.1 Probleme rezolvate

2.METODE NUMERICE ÎN ALEGBRA LINIARĂ

2.1Eliminarea. Gaussiana.

2.2Descompunerea LU

2.3Rezolvarea sistemelor de ecuații liniare prin factorizare Crout și Choleski

2.3.1Factorizarea Crout

2.3.2Rezolvarea sistemelor de ecuații liniare cu factorizarea Crout

2.3.3 Factorizarea Cholesky

2.3.4 Rezolvarea sistemelor de ecuații liniare cu factorizarea Cholesky

2.3.5 Metoda iterativă Jacobi

2.3.6 Metoda iterativă Seidel-Gauss

3.ECUAȚII NELINIARE

3.1Rezolvarea numerică a ecuațiilor neliniare

3.1.1. Generalități

3.1 2. Metoda bipartiției

3.1.3 Metoda coardei

3.2 Metode de partiționare

3.2.1 Metoda bisectiei

3.2.2 Metoda bisectiei Algoritm

3.2.3 Metoda secantei

3.3 Metode de aproximații succesive

3.3.1 Metoda contracției

3.4 Metoda Newton

3.4.1Metoda Newton Algoritm

Bibliografie

1.ALGEBRA LINIARĂ

Algebra numerică liniară este studiul algoritmilor care rezolvă calcule de algebră liniară, cele mai importante dintre acestea fiind operațiile cu matrice pe calculatoare. Algebra liniară este o parte fundamentală a ingineriei și științei calculatoarelor, în domenii ca prelucrarea imaginilor și semnalelor, telecomunicații, informatică de gestiune, știința materialelor, simulări, biologie structurală, bioinformatică, dinamică fluidelor și multe alte domenii. Sunt construite programe care se ocupă cu dezvoltarea, analiza și implementarea algoritmilor care rezolvă probleme variate de algebră liniară, în mare parte axându-se pe rolul matricelor în diferențe finite și metode cu număr finit de elemente.

Probleme comune din algebra liniară includ calcularea descompunerii LU, descompunerea QR, descompuneri cu o singură valoare și determinarea valorilor proprii.

„Algebra liniară este ramura matematicii care se ocupă cu spațiile vectoriale și mapări liniare între astfel de spații. Este studiul liniilor, planurilor și subspațiilor și al intersectării acestora folosind algebra. Algebra liniară calculează coordonatele punctelor în spațiu, astfel încât operațiile făcute pe vectori sunt definite cu operații care folosesc punctele vectorilor din spațiu” (Ebâncă, D – 1994, pag 13).

Setul de puncte de coordonate care satisfac ecuațiile liniare de pe un hiperplan într-un spațiu n-dimensional. Condițiile în care n hiperplanuri se intersectează într-un singur punct sunt un obiectiv important în studiul alge brei liniare. O astfel de cercetare este motivată inițiale de sistemul de ecuații liniare care conțin foarte multe necunoscute. Astfel de ecuații sunt reprezentate în mod normal folosind formalismul matricelor și vectorilor.

Algebra liniară folosește atât matematică pură cât și aplicată. Pentru început, algebra abstractă furnizează axiome pentru spațiul vectorial, cu un anumit număr de generalizări. Analiza funcțională studiază versiunea infinit-dimensională a teoriei spațiilor vectoriale. Combinată cu calcule, algebra liniară facilitează găsirea soluțiilor sistemelor liniare ale ecuațiilor diferențiale. Tehnicile din algebra liniară sunt folosite și în geometria analitică, inginerie, fizică, științe naturale, știința calculatoarelor, animație pe calculatoare și științe sociale (în special în economie). Deoarece algebra liniară este o teorie atât de bine dezvoltată, modelele matematice neliniare sunt aproximate uneori de modele liniare.

Studiul algebrei liniare a evoluat din studiul determinanților, care erau folosiți pentru rezolvarea sistemelor de ecuații liniare. Determinanții erau folosiți de Leibniz în anul 1693, șu ulterior, în anul 1750 Gabriel Cramer a dezvoltat Legea Lui Cramer pentru rezolvarea sistemelor liniare. Mai târziu, Gauss a dezvoltat teoria rezolvării sistemelor liniare folosind Eliminarea Gaussiană care a fost folosită prima dată în geodezie.

Studiul algebrei matricelor a înveput să se dezvolte prima dată în Anglia la jumătatea secolului XIX. În anul 1844 Hermann Grassmann a publicat „Teoria Extensiilor” care include fundamentele a ceea ce numim astăzi algebră liniară. În anul 1848, James Joseph Sylvester a introdus termenul de matrice. În timpul studiului despre transformări liniare, Arthur Cayley a putut defini multiplicarea matricelor și inversarea matricelor. Cayley folosea o singură literă pentru a defini matricele, tratând matricea ca pe un obiect agregat. De asemenea, el a realizat conexiunea între matrice și determinanți și a scris „ar fi multe lucruri de spus despre această teorie a matricelor care ar trebui, după părerea mea, să fie înaintea determinanților”( Arthur Cayley, 1900, pag 23).

În 1882, Hüseyin Tevfik Pasha a scris cartea intitulată Algebră Liniară. Prima definiție modernă, fiind și cea mai exactă, a unui spațiu vectorial a fost enunțată de Peano în 1888. Din anul 1900a evoluat o nouă teorie a transformărilor liniare pe spații vectoriale cu dimensiuni finite. Algebra liniară a luat prima ei formă modernă în prima jumătate a secolului XX, când multe idei și metode din secolele anterioare au fost generalizate ca aparținând algebrei abstracte.„ Folosirea matricelor în mecanica cuantică, relativitate specială și statistică a ajutat transpunerea algebrei liniare în matematică pură/ dezvoltarea calculatoarelor a dus la creșterea cercetărilor pentru eficiența algoritmilor eliminării Gaussiene și descompunerii matricelor, iar algebra liniară a devenit un instrument esențial pentru modelări și simulări”( Ebâncă, D – 1994, pag 22).

1.1 Spațiile vectoriale

Principala structură a algebrei liniare sunt spațiile vectoriale. Un spațiu vectorial pe un câmp F este un set de V împreună cu două operații binare. Elementele din V se numesc vectori și elementele din F se numesc scalari. Prima operație, adunarea vectorilor, ia doi vectori v și w și creează un vector nou cu valoare v+w. a doua operație ia orice scalar a și orice vector v și crează vectorul av. Dacă multiplicarea se face prin rescalarea vectorului v de către un scalar a, multiplicarea se numește multiplicare scalară a vectorului v de către a. Operațiile de adunare și înmulțire într-un spațiu vectorial satisface axiomele de mai jos. În lista următoare, u, v și w sunt vectori arbitrari în V iar a și b sunt scalari arbitrari în F.

Asociativitatea adunării: u+ (v+w)=(u+v)+w

Comutativitatea adunării: u+v=v+u

Identitatea elementelor la adunare: există un element 0 care aparține lui V numit vector zero, astfel încât v+0=v pentru oricare v aparținând lui V.

Elementul invers în adunare: pentru fiecare v care aparține mulțimii V există un element –v aparținând aceleiași mulțimi numit aditiv invers al lui v, astfel încât v+(-v)=0.

Distributivitatea înmulțirii scalare legată de adunarea vectorilor: a(u+v)=au+av

Distributivitatea înmulțirii scalare legată de adunarea câmpurilor: (a+b)v=ab+bv

Compatibilitatea înmulțirii scalare cu înmulțirea câmpurilor: a(bv)=(ab)v

Identitatea elementelor în înmulțirea scalară: 1v=v denotă identitatea înmulțirii în F.

Elementele unui spațiu vectorial general V pot fi obiecte de orice natură, de exemplu funcții, polinoame, vectori sau matrice. Algebra liniară are proprietăți comune pentru toate spațiile vectoriale.

1.2 Transformările liniare

„Similar ca la teoria altor structuri algebrice, algebra liniară studiază legăturile dintre spațiile vectoriale și structura vector-spațiu. Având două spații vectoriale V și W și un câmp F, o transformare liniară (numită și mapare liniară, sau operator liniară) este o hartă.”( Groza G – 2005, pag 30.)

care este compatibilă cu adunarea și înmulțirea scalară.

pentru orice vector u,v ∈ V și scalar a ∈ F.

Adițional pentru fiecare vector u, v ∈ V și scalari a, b ∈ F:

Când o mapare liniară bijectivă există între două spații vectoriale (fiecare vector din al doiea spațiu este asociat cu exact unul din primul spațiu vectorial), cele două spații se numesc izomorfe. Pentru că un izomorfism păstrează structura liniară, două spații vectoriale izomorfe sunt esențial aceleași din punct de vedere algebric. O întrebare esențială în algebra liniară este unde o mapare este izomorfă sau nu și această întrebare poate primi răspuns prin verificarea dacă determinantul este diferit de zero. Dacă o mapare nu este un izomorfism, algebra liniară este interesată să găsească un rang (sau imagine) și setul de elemente care sunt cartografiate la zero numite nucleul mapării.

1.3 Subspațiile, sectoarele și bazele

Prin analogie cu teoria altor obiecte algebrice, algebra liniară este interesată în subsetul spațiului vectorial care este el însuși un spațiu vectorial. „Aceste subseturi se numesc subspații liniare. Pentru început, rangul și nucleul unei mapări liniare sunt ambele subspații, și se numesc spațiu de rang sau spațiu nul” ( Groza G – 2005, pag 50). Un alt mod important de a forma subspații este prin luarea combinațiilor liniare de seturi de vectori v1, v2, …, vk , unde a1, a2, …, ak sunt scalari. Setul de cominații liniare se numește sector și formează un spubspațiu.

„O combinație liniară a oricărui sistem de vectori cu toți coeficienții egali cu zero se numește vectorul zero al lui V iar vectorii se numesc liniar independenți” ( Groza G – 2005, pag 44). Având un set de vectori dintr-un subspațiu vectorial, dacă orice vector w este o combinație liniară a altor vectori și dacă setul nu este liniar independent, atunci subspațiul va rămâne la fel dacă îndepărtăm vectorul w din set. Un set de vectori liniar dependenți este redundant în sensul că un subspațiu liniar independent va putea avea același sector de vectori în subspațiu. De aceea zonă de interes se află într-un set de vectori liniar independenți care are ca sector un spațiu vectorial V, acest sector se va numi bază. Orice set de vectori care are valori în V se va numi bază, și orice set de vectori liniari independenți din V poate fi extins într-o bază. Rezultă că dacă acceptăm axioma alegerilor fiecare spațiu vectorial are o bază cu excepția situațiilor în care bază nu este naturală sau nu poate fi construită. Pentru început, există o bază pentru numerele reale considerate spațiu vectorial al numerelor raționale, dar nu are o bază construită explicit.

„Oricare două baze dintr-un spațiu vectorial V au același cardinal, ceea ce înseamnă aceeași dimensiune a lui V. dimensiunea unui spațiu vectorial este definită de Teorema dimensiunii spațiilor vectoriale” ( Groza G – 2005, pag 66). Dacă o bază V are un număr finit de elemente, V se numește un spațiu vectorial cu dimensiune finită. Dacă V are dimensiunea finită și U este un subspațiu al său atunci dimensiunea lui U este mai mică sau egală cu dimensiunea lui V.

„O restricție considerată a spațiilor vectoriale de dimensiuni finite este cea enunțată mai sus. O teoremă fundamentală a algebrei liniare spune că toate spațiile vectoriale de aceeași dimensiune sunt izomorfe oferind astfel un mod ușor de a caracteriza izomorfismul”( Iorga, V., Jora, B 1996 pag 45).

1.4Metoda eliminării complete (Gauss-Jordan)

Metoda elAiminării comAplete se poate fAolosi, printre altAele, pentAru:

rezolvareAa unui sistemA de ecuațiAi liniare;

calculuAl inversei uneiA matrice nesAingulare.

EtapeleA aplicării acestei mAetode sunt:

Se alcAătuiește un tabel caAre conține maAtricea sistemului ceA trebuie

rezolvat (Anotată A ) sau matriceaA ce trebuie inversatăA ( A ).

Se alAege un element nenul al mAatricei A, numitA pivot.

ElementelAe din tabel se mAodifică Aastfel:

a) eleAmentele de pe linia pAivotului se împaArt la pivot;

b) coloana Apivotului se compAletează cu zero; A

c) restul Aelementelor se calcuAlează după regulAa dreptunghiuAlui:

se formeazAă un dreptunghi, A având elemenAtul ce trebuie înlocuiAt și pivotul ca vârfuri;

din pArodusul elementeloA de pe diagonaAlă pivotuluAi se scade Aprodusul elemeamentală a algebrei liniare spune că toate spațiile vectoriale de aceeași dimensiune sunt izomorfe oferind astfel un mod ușor de a caracteriza izomorfismul”( Iorga, V., Jora, B 1996 pag 45).

1.4Metoda eliminării complete (Gauss-Jordan)

Metoda elAiminării comAplete se poate fAolosi, printre altAele, pentAru:

rezolvareAa unui sistemA de ecuațiAi liniare;

calculuAl inversei uneiA matrice nesAingulare.

EtapeleA aplicării acestei mAetode sunt:

Se alcAătuiește un tabel caAre conține maAtricea sistemului ceA trebuie

rezolvat (Anotată A ) sau matriceaA ce trebuie inversatăA ( A ).

Se alAege un element nenul al mAatricei A, numitA pivot.

ElementelAe din tabel se mAodifică Aastfel:

a) eleAmentele de pe linia pAivotului se împaArt la pivot;

b) coloana Apivotului se compAletează cu zero; A

c) restul Aelementelor se calcuAlează după regulAa dreptunghiuAlui:

se formeazAă un dreptunghi, A având elemenAtul ce trebuie înlocuiAt și pivotul ca vârfuri;

din pArodusul elementeloA de pe diagonaAlă pivotuluAi se scade Aprodusul elementelorA celeilalte diagonaleA, iar rezultatul seA împarte la pivot. ASchematic, Aregula dreptunghiului se pArezintă astfel:

a……A……x

: :

b……A……c

b = piAvotul;

x = elemAentul ce trebuie înlAocuit;

x'= nAoua valoare a elemeAntului x .

d) (faculAtativ) dacă pe linia Apivotului există un elemeAnt egal cu zero, atunAci coloana acelui elemAent se copiază; analog, Adacă pe coloana pivotuluAi există un element egal cAu zero, atunci liniaA acelui element seA copiază.

4. Se reiAau pașii 2 și 3 până când dAe pe fiecare linie s-a aleAs câte un pivot. A

1.4.1 Probleme rezolvate

1. Să se reAzolve următorul sistem de ecuațAii liniare, folosind metodAa eliminării coAmplete:

/ -+A2-3=A -2

< 2A-6A+9=A 3

\-3A+2A+2=-3

RAezolvare:

Vom foloAsi următoarea sAchemăA:

DeducemA că soluția sistAemului este: x1A = 3, x2 = 2, A x3 = 1. A

2. Să se rezAolve urmăAtorul sistem dAe ecuații liniare, Afolosind metoda

elimiAnării compleAte:

/ 4+5A+=A 9

< 3+A = 6

\ 5A+2A+= A11

RezAolvare:

ObAservație. Pentru simpAlificarea calculelor, am Aales drept pivot mai întâi eleAmentul al doAilea al diagonalei princAipale (în cazul nostru,1). SoluAția sistemului esteA: xA1 = 2, x2 = 0, x3 = 1.

ObservațiAi

Metoda GaAuss-Jordan constă în transfoArmări succesive ale sistAemului inițial în forme ecAhivalente.

În rezolvarea unAui sistem prin această Ametodă nu este obligatovriu ca pivotuvl să fie ales Ade pe diagonală Aprincipală.

2.METODE NUMERICE ÎN ALEGBRA LINIARĂ

2.1Eliminarea. Gaussiana.

„În. algebra liniară., eliminarea. Gaussiană. cunoscută. de asemenea. și ca reducere a rândurilor. este un algoritm. care rezolvă sisteme. liniare. de ecuații.. Este de asemenea. înțeles că. o secvență. de operații. realizate. pe matrice. cu coeficienți. asociați.” ( Bretscher, Otto 2004, pag 111) .. Această. metodă. poate. fi folosită. pentru a găsi. rangul. matricei., pentru. a calcula. determinantul. unei. matrice., și pentru. a calcula. inversul. unei. matrice. pătratice. inversibile. . Metoda. a primit numel.e după matematicianul Carl Friedrich Gauss. și a fost. cunoscută de matematicienii. chinezi. din 179. p. Ch.

Pentru. a realiza. reducerea. de rânduri. pe o matrice., folosim. o secvență. de operații. realizate. pe o matrice. cu coeficienți. asociați. până. când. colțul. din stânga. jos devine. egal cu zero. Sunt. trei tipuri. de operații. elementare. pe rânduri.. Prima dintre ele. este inversarea. a două rânduri.. A doua. operație. ce se poate. face este înmulțirea. unui rând. cu un număr diferit. de zero.. Iar a treia. metodă este multiplicarea. unui rând cu alt rând. „Folosind aceste operații o matrice poate fi transformată într-o matrice triunghiulară și devine eșalonată pe rânduri. După ce toți coeficienții importanți (fiecare cifră diferită de zero) devine egală cu 1, și fiecare coloană conține un coeficient diferit de zero, matricea se numește redusă la formă eșalonată” ( Bretscher, Otto 2004, pag 111). Această formă finală este unică, cu alte cuvinte, și este independentă de secvențele de linii și de operațiile folosite. Folosind operații pe linii pentru a converti o matrice într-un eșantion redus se numește eliminare Gauss-Jordan. Unii autori folosesc termenul de eliminare gaussiană pentru a face referire la procesul de transformare a matricei într-o matrice triunghiulară. Din motive de calcul, când se rezolvă sistemele de ecuații liniare, este preferabil să se oprească operațiile pe linii până când matricea este complet redusă.

„Procesul de reducere a liniilor folosește operații elementare pe linii și poate fi divizat în două părți. Prima parte reduce sistemul dat la o formă eșalonată, de la care se spune că nu mai există soluții, există o soluție unică sau sunt soluții infinite. A doua parte continuă să folosească operațiile pe linii până când se găsește soluția, cu alte cuvinte pune matricea redusă într-o formă eșalonată”( Farin, Gerald; Hansford, Dianne 2004, pag 66).

Un alt punct de vedere care se dovedește a fi foarte folositor pentru analizarea algoritmului, este acela că reducerea rândurilor produce o decompoziție matriceală a matricei originale. Operațiile elementare pe rânduri pot fi văzute că înmulțirea matricei originale la stânga cu matrice elementare. Alternativ, o secvență de operații elementare care reduc o singură linie poate fi văzută ca o înmulțire a matricei cu o matrice Frobenius. Atunci prima parte a algoritmului calculează o descompunere LU, în timp ce a doua parte scrie matricea originală ca un produs a unei singure matrice invesibile determinate unic și a unei matrice unice redusă la eșaloane pe rânduri.

Pentru fiecare rând dintr-o matrice, dacă rândul nu conține doar zero atunci coeficientul diferit de zero se numește pivot al acelui rând. Dacă pivoții sunt pe aceeași coloană atunci o operație pe rânduri poate fi folosită pentru a face unul dintre acești coeficienți să fie egali cu zero. Apoi folosind operația de inversare a rândurilor se poate ajunge la situația în care coeficienții pivoți care sunt cei mai mari din punct de vedere al valorii să fie situați către stânga și cei mici către dreapta fiind poziționați de la dreapta la stânga. Atunci când se ajunge la o astfel de situație matricea se numește eșalonată pe linii. Deci ultimele linii ale matricei vor conține doar zerouri, și toate liniile care conțin doar zero sunt situate sub liniile cu elemente nenule. Cuvântul eșantion este folosit deoarece se poate vedea că liniile sunt situate în funcție de dimensiunea lor, cea mai mare fiind prima și cele mai mici urmând în ordine descrescătoare după aceasta.

Exemplu:

Să presupunem că scopul este acela de a oferi un set de soluții următorului sistem de ecuații liniare:

Tabelul de mai jos arată modul în care reducerea liniilor este aplicată simultan sistemului de ecuații dinamice, și este asociată cu matricea augumentată. În practică, chiar dacă se face rezolvarea unui sistem de ecuații liniare se face uz de matricea augumetată, care este mai ușor de folosit în calcule. Procedura de reducere a liniilor poate fi enunțată pe scurt astfel: se elimină x din toate ecuațiile L1 și apoi se elină y din toate ecuațiile L2. Această operație va pune matricea într-o formă triunghiulară. Apoi, utilizând substituția fiecare necunoscută va putea fi calculată.

A doua coloană descrie operațiile de pe fiecare linie care au fost făcute. După ce y este eliminat rezultatul este un sistem de ecuații liniare puse în formă triunghiulară, și prima parte a algoritmului este completă. Din punct de vedere al calculelor este mai rapid să se rezolve variabilele în ordine inversă, proces cunoscut ca substituție inversă. Ca rezultat z=-1, y=3 și x=2. Este o soluție unică a sistemului de ecuații original.

În loc să ne oprim odată ce matricea este în formă eșalonată, se poate continua până când matricea este eșalonată pe linii. Procesul de reducere până când matricea este redusă se face prin eliminarea Gauss Jordan, pentru a se distinge de cazul în care reducerea se oprește după ce se ajunge la formă eșalonată.

2.2Descompunerea LU

„.În analiza. numerică., descompunerea. LU unde LU. înseamnă Lower Upper., numită și descompunere. LU în factori., factorizează. o matrice. ca un produs. al matricei. triunghiulare inferioare. cu matricea. triunghiulară. superioară.” ( Farin, Gerald; Hansford, Dianne 2004, pag 66).

Produsul. include. uneori. o matrice. de permutare.. Descompunerea. LU p.oate fi văzută .ca o matrice din eliminarea Gaussiană. Calculatoarele rezolvă de obicei sistemele de ecuații liniare de gradul. doi folosind. și este. de aseme.nea un pas. cheie când se. face inversarea unei. matrice, sau când. se calculează. determinantul. unei matrice.. Descompunere.a LU a fost inventată. de matematicianul. Alan Turning.

Fie A o. matrice .pătratică.. O desc.ompunere LU se .referă la factorizarea. lui A prin permutări. și aranjamente. de linii. și coloane. în doi factori., o matrice triunghiulară. inferioară L și o matrice triunghiulară. superioară U.

A = LU

În matricea. triunghiulară. inferioară. toate elementele. aflate deasupra. diagonalei sunt zero, în matricea. triunghiulară. superioară. toate elementele. aflate sub diagonală sunt zero. De exemplu pentru o matrice cu 3 linii și 3 coloane descompunerea LU arată astfel:

„Fără aranjamente. și permutări. specifice. în matrice., factorizarea. poate. să nu se materializeze.. De exemplu, . este ușor de. verificat dacă . Dacă atunci cel. puțin. un. element. din și trebuie. să fie zero., ceea. ce implică. faptul. că L și U sunt matrice singulare.. Este imposibil. dacă. a este nesingulară.” ( Farin, Gerald; Hansford, Dianne 2004, pag 80).

. Aceasta. este o. problemă procedural.ă. Poate fi o facto.rizare prin pași sub.secvențiali care să meargă. pe același .principiu al .procedurii .de bază.

Rezultă .că o .permutare .corectă pe lin.ii sau. co.loane este s.uficientă pentru descompun.erea LU. . Desco.mpunerea LU p.rin pivotare parț.ială se referă la factorizarea. LU prin. permutăr.i do.ar pe l.inii:

PA = LU

Unde. L și U. sunt. matricea. triun.ghiulară infer.ioară și matric.ea triung.hiulară superioară., iar P e.ste ma.tricea de .permutare care atunci. când este înmulțită. la stânga cu. A, rearanjează liniile. din A.. rezul.tă că toate matricele. pătratice .pot fi factorizate. în acest .fel și că factorizarea. este. stabilă. din. punct. de vedere. numeric. în practică.. Aceasta face ca descompunerea. LU să fie o tehnică. utilă din punct. de vedere practi.c.

O descompunere. LU cu pivot .complet implic.ă atât liniile cât. și coloanele. atunci când. vine. vorba de permutări..

PAQ = LU

Unde. L, U și P. sunt. definite. ca înainte., iar Q este matricea. permutărilor. care rearanjează. coloanele. din A.

O descompunere. LDU este o descompunere. de formă A = LDU. unde D. este o matrice diagonalizată., iar L și. U sunt matrice. unitate., ceea ce înseamnă. că toate valorile. de pe diagonalele. principale. ale lui. L și U sunt. egale cu. unu.

Mai sus. se cerea. ca A să fie o matrice. pătratică., dar aceste. descompuneri. pot fi toate generalizate. la matrice. normale.. L și P sunt. matrice. pătratice. care au fiecare același. număr de linii. ca A în. timp ce. U este. de exact. aceeași. formă .ca A. Ma.tricea triun.ghiulară supe.rioară trebuie .interpre.tată ca având doar eleme.nte ega.le cu zero. sub diagonal.a principală ca.re începe. din colțul. stânga. sus. .

Codul C++:

void Doolittle(int d,double*S,double*D){

for(int k=0;k<d;++k){

for(int j=k;j<d;++j){

double sum=0.;

for(int p=0;p<k;++p)sum+=D[k*d+p]*D[p*d+j];

D[k*d+j]=(S[k*d+j]-sum); // not dividing by diagonals

}

for(int i=k+1;i<d;++i){

double sum=0.;

for(int p=0;p<k;++p)sum+=D[i*d+p]*D[p*d+k];

D[i*d+k]=(S[i*d+k]-sum)/D[k*d+k];

}

void solveDoolittle(int d,double*LU,double*b,double*x){

double y[d];

for(int i=0;i<d;++i){

double sum=0.;

for(int k=0;k<i;++k)sum+=LU[i*d+k]*y[k];

y[i]=(b[i]-sum); // not dividing by diagonals

}

for(int i=d-1;i>=0;–i){

double sum=0.;

for(int k=i+1;k<d;++k)sum+=LU[i*d+k]*x[k];

x[i]=(y[i]-sum)/LU[i*d+i];

}

2.3Rezolvarea sistemelor de ecuații liniare prin factorizare Crout și Choleski

Prin. definiție., descompunerea. unei matrice. A(n,n) într-un. produs. de două ma.trice:

A = L * R

unde .L(n,n) este o. matrice. inferior. triunghiulară., iar R(n,n) este. o matrice. superior .triunghiulară., se numește. factorizare. LR a matricei A.. De. exemplu., pentru. o matrice. Ade dimensiuni. 4 * 4. factorizarea. LR. are. form.ă:

În. cazul. folosirii. factorizării., rezolvarea. unui. sistem. de. ecuații. liniare. A .* x = .b se reduce. la rezolvarea. succesivă. a două .sisteme triunghiulare.:

A .* x. = b. <==> ( L. * .R ) . * x. = b. <==> L .* . ( R. * x ) = b

Mai. întâi. se rezolvă. sistemul. inferior. triunghiular.:

L. * .y = b.

în. raport cu y (prin substituție. înainte.) și apoi. sistemul. superior. triunghiular.:

R. * .x = y.

în raport cu .x (prin. substituție. înapo.i) , necunoscutele. principale. ale problemei..
„ Aplicarea. procedurilor. compac.te de fac.torizare (pe loc, î.n matricea A) pr.esupune determi.narea a n.^2+n eleme.nte ale m.atricelor L și R., folos.ind cele. n^2 ec.uații car.e se pot scrie.. Pen.tru ca. sistem.ul de .ecuații as.tfel obțin.ut să adm.ită soluț.ie unică .este necesară precizarea. a prio.ri a n din. cele n^2.+n necu.noscute. ” (Farin, . Gerald; Hansford, Dianne 2004, pag 102).

M.etodele. de facto.rizare. utiliza.te aleg ca nec.unoscute depende.nte, ale căr.or valor.i se pre.cizează a .priori, cele .n elemente d.iagonale a.le unei.a din matrice.le L sau. R. Se dis.ting astfel dou.ă tipuri de f.actorizări:

(i) fac.torizarea Cro.ut, care i.mpune matricea. R cu diagonal.a unitate;
(ii) factoriza.rea Doolitle, . care impu.ne matricea .L cu diago.nala unit.ate.

Da.că matricea A e.ste simetric.ă și pozitiv. definită, cel.e două matrice. de facto.rizare satis.fac relația, astfel în.cât factorizarea.devine:

c.unoscută su.b numele d.e factoriza.re Cho.lesky.

2.3.1Factorizarea Crout

„Impu.nând elementele .diagonale ale matricei. R egale .cu unitatea, fact.orizarea Cro.ut determ.ină restul eleme.ntelor necunoscute din m.atricele L și R pri.n rezolvar.ea unui si.stem format. din n^2 ecuații, c.u .tot atâ.tea n.ecunos.cute..”( . Nicholson, W., 1.995, pag .211) Ecua.țiile ca.re formează ace.st siste.m se deduc. din relația .de .definiție A =. L * R. și forma .lor depi.nde de raportul în c.are se afl.ă indicii i și. j ai unu.i element .a_ ij din m.atricea A. .Putem avea următoarele .trei cazu.ri:

Cele .trei ec.uații de. mai sus p.ot fi scrise co.mpact sub. formă:

(**)

Tehnica. factorizări.i Crout .nu realiz.ează rezol.varea propriu.-zisă a acestui sis.tem de ecuații., ci determină .necunoscutel.e _ij și _ij printr-o. aranjare. convenabilă. a ecuațiilor..

Astfel., vom. considera. ca .au fost determinate .elementele. nenule de .pe primele p.-1 coloane din matricea. L și primel.e p-1 linii din .matricea R și. vom parti.culariză relația. (**)
Pentru .determinarea elemen.telor nenule de p.e coloana p a matricei .L, în relația (**) se imp.une j=p și se individu.alizează elemen.tele acestei coloan.e. Deoarece pe coloana p a matric.ei L singurele elemente. nenule_i.p corespund uno.r indici i=p,.. ..,n, li.mită de sumare va fi eg.ală cu p, a.stfel încât se .poate sc.rie:

„Am ad.mis însă ca toate .elementele de pe pri.mele p-1 coloane .din matri.ea L (_im; m=1,. …,p-1), respectiv. de pe primele. p-1 linii. din matricea .R (_mp; m=1,…,p-1) au fost. determinate în p.realabil.” ( Nicholson, W.., 1995, p.ag 211) De a.semenea, _.pp = 1 (ip.oteza inițială a .metodei). În. aceste condiț.ii, relația de. mai sus .permite c.alculul tut.uror elemen.telor nenule .de pe coloan.a p a mat.ricei L.:

( I )

Pentru dete.rminarea elementelor .nenule de. pe linia p .a matricei R., în relați.a (**).se impune i=.p și se i.ndividualizează .elementel.e acestei l.inii. Totodat.ă, deoarec.e pe lini.a p a matricei. R elementele .nenule necunos.cute _pj cor.espund un.ui indice j.=p+1,…,n (deo.arece _pp=1 .este cunoscut), l.imita de sumare .este egală c.u p, astf.el încât relaț.ia (**) capătă for.mă:

Și în acest. caz toate elemen.tele de pe primele .p-1 coloane din m.atricea L (_pm; m=1,…,p-1), respect.iv de pe primele p-1 li.nii din matrice.a R (_mj; m.=1,…,p-1) au fost de.terminate în p.realabil. De asem.enea, elem.entul diagon.al _pp din .matricea L a .fost determ.inat anteri.or. Astfel, .relația de ma.i sus permite .calculul elementelor nenul.e de p.e linia p a ma.tricei R:

( II )

Aplica.rea relațiilo.r ( I ) și. ( II ) pentru. toate valorile. lui p=1,…, .n permit .determinarea tuturor ele.mentelor nenule d.in matricele. L și R, . realiz.ând astfe.l factoriz.area Crout .a matrice.i A.

Aceste relații e.vidențiază f.aptul ca la ca.lculul elem.entelor nenu.le de colo.ană p a matri.cei L, respectiv .de pe lin.ia p a m.atricei R, s.e foloses.c numai .elemente de pe. coloana, respectiv. linia .p a matrice.i A. Ca urm.are, noile v.alori calculat.e _ip și _pj pot f.i suprapus.e peste. elemen.tele a_ip., respec.tiv a_pj, înloc.uindu-le pe. acestea din urm.ă. Astfel, factorizarea. Crout. se poa.te desfăș.ura pe loc, în m.atricea A, n.e fiind .necesară o.cuparea de memori.e auxiliar.ă pen.tru matricele. L și R..

2.3.2Rezolvarea sistemelor de ecuații liniare cu factorizarea Crout

Defi.nirea sistemu.lui de .ecuații: ra.ngul n, m.atricea coeficienți.lor A, vecto.rul term.enilor lib.eri b.

Facto.rizarea LR a matric.ei A după m.etoda Cro.ut :

Inițiali.zarea numărului. coloanei. / linie.i din m.atricele L. și R pentru care .se calcule.ază elem.entele nen.ule: p .<– 1; .

Determ.inarea ele.mentelor subdiago.nale, inclusiv a. elementului .diagonal de p.e coloana .p a matric.ei L (rela.ția I):

Pivo.tarea parțial.ă pe colo.ana .p;

Determ.inarea eleme.ntelor situa.te la dr.eapta diagon.alei prin.cipale , pe. linia .p a matri.cei R (rel.ația II ):

Se tre.ce la trata.rea următoarei coloa.ne/linii din matr.icele L și R: p <– p+1. .Dacă .p <= n se. revine la pasul .2.2. Dacă p > n se trece. la pasul. 3.

Rezolvarea. sistemului. inferior .triunghiular .L * y = b, prin su.bstituție înai.nte, folosind. elementele .diagonale. și sub.diagonale. din matric.ea A și m.emorarea soluție.i yi.n .vectorul b.

Re.zolvarea sistemulu.i superior .triunghiu.lar R * .x = y .= b prin subst.ituție înapoi, folosind elementele suprad.iagonale din matr.icea A și me.morarea soluției x. în vector.ul b.

Codul C++:

void Crout(int d,double*S,double*D){

for(int k=0;k<d;++k){

for(int i=k;i<d;++i){

double sum=0.;

for(int p=0;p<k;++p)sum+=D[i*d+p]*D[p*d+k];

D[i*d+k]=S[i*d+k]-sum; // not dividing by diagonals

}

for(int j=k+1;j<d;++j){

double sum=0.;

for(int p=0;p<k;++p)sum+=D[k*d+p]*D[p*d+j];

D[k*d+j]=(S[k*d+j]-sum)/D[k*d+k];

}

void solveCrout(int d,double*LU,double*b,double*x){

double y[d];

for(int i=0;i<d;++i){

double sum=0.;

for(int k=0;k<i;++k)sum+=LU[i*d+k]*y[k];

y[i]=(b[i]-sum)/LU[i*d+i];

}

for(int i=d-1;i>=0;–i){

double sum=0.;

for(int k=i+1;k<d;++k)sum+=LU[i*d+k]*x[k];

x[i]=(y[i]-sum); // not dividing by diagonals

}

2.3.3 Factorizarea Cholesky

„Dacă. o matrice pătrat.ă A este sim.etrică și poz.itiv definită, e.i i se poate aplica. o factorizare sp.ecială, mai efic.iența din pu.nct de vedere. numeric, numită f.actorizare Ch.olesky” ( Nicholson., W., 1995, . pag 211). .Simetr.ia înseamnă. satisface.rea egalită.ți (T indică transpu.nerea) sau a._ ij = a_ ji pent.ru toți indicii i,j.=1,…,n. O matric. A se nu.mește pozitiv defin.ită dacă ineg.alitatea:

este satisfăcut.ă pentru orice vecto.r x, iar anularea produ.sului matriceal are. loc num.ai atunci când x este. identic cu vect.orul nul. Propr.ietatea defini.rii pozitive a .matriceiA joacă un rol esențial. în stabi.litatea numeric.ă a calcul.elor efectuate în .cursul factoriz.ării Cholesky.
Dacă cele. două proprietăți s.unt satisfăcute, facto.rizarea Cholesky. descompune matricea A în.tr-un produs d.e două mat.rice triunghiul.are de ti.pul LR, cu. proprietatea remar.cabilă :

.Pentru acest tip de facto.rizare, se pot scr.ie (n^2+n)/2 ecu.ații indepen.dente care co.nțin tot atâtea. necunoscute (e.lementele nenule din .matricea L). În consecință., factorizarea .Cholesky a unei matrice. este unică, nefiind. necesară precizarea .a priori a valorilor. unor necunoscute..
Pentru stabilirea. relațiilor generale. de calcul după. care se desfășoară. factorizarea. Cholesky, expresia. se explicitează. în funcție de elementele. matricelor Ași L.:

(***)

ÎnA ipotezaA determinăriiA prealAabile a elAementelor de Ape primelAe j-1 cAoloane ale matricei L, relația (***) seA explicitează peAntru a evidențiAa elementul Adiagonal :

și se face partAicularizarea i = j:

DeoareceA toți termenii _ jm ( m=1,…,j-1 ) au foAst calculați în prealaAbil, se poate dAetermina elementuAl diagonAal :

după Acare, se calculează Arestul elemenAtelor de pe coloana j a maAtricei L:

„Și în cazulA factorizării Cholesky existAă posibilitateAa aplicării metodeAi descrise în forAma compactă, pe loc în matriAcea A. Pe de altă partAe, este posiAbilă memorarea îAntr-o singură matrice atât a matricAei originare A, cât și a matricei de faActorizare L”( Kolman, BernAard; Hill, David AR. 2007 pag. 56). Astfel, foArma finală a matricei A are urmăAtoarea structură: pe diagonală și deasupra acesteia se vor găAsi elementele originare Aale matricei A; sub diAagonală se află elementeleA matricei L, iar diagonalAa acesteia este meAmorată separat înAtr-un vector.
„O particularitate aA factorizării Cholesky seA referă la aplicarea Atehnicilor de pivoAtare. În acest sensA, dacă matriceaA A satisfacAe condițiile pentrAu a admite o factorizaAre Cholesky (este simetrică și pozitiAv definită), ea va fi înAtotdeauna nesingulara” A( (Kolman, Bernard; Hill, David R. 2007 pag. 56). A Prin urmaAre riscul împărțirii la unA element nulA în relațiAa ( IV ) nu există și nici erAorile de rotAunjire nu pot afeActa semnificaAtiv rezultatele cAalculelor. PArin urmare, nu mai este neceAsară aplicarea pivotăArii. Mai multA decât atât, aplAicarea tehnicilAor de pivotare nicinuA este permisă Adeoarece:

pivotaArea parțială stricAă simetria matricei;

pivAotarea completă păstreazăA simetria, daAr conduce, de regulă, A la pierderea proprietății de "definire Apozitivă" a matriceAi A.

În ambele cazuAri se încalcă condiAțiile care asigură existenAța factorizării ChAolesky.

Codul C++:

void CholeskyRow(int d,double*S,double*D){

for(int k=0;k<d;++k){

for(int j=0;j<d;++j){

double sum=0.;

for(int p=0;p<j;++p)sum+=D[k*d+p]*D[j*d+p];

D[k*d+j]=(S[k*d+j]-sum)/D[j*d+j];

}

double sum=0.;

for(int p=0;p<k;++p)sum+=D[k*d+p]*D[k*d+p];

D[k*d+k]=sqrt(S[k*d+k]-sum);

}

void solveCholesky(int d,double*LU,double*b,double*x){

double y[d];

for(int i=0;i<d;++i){

double sum=0.;

for(int k=0;k<i;++k)sum+=LU[i*d+k]*y[k];

y[i]=(b[i]-sum)/LU[i*d+i];

}

for(int i=d-1;i>=0;–i){

double sum=0.;

for(int k=i+1;k<d;++k)sum+=LU[k*d+i]*x[k];

x[i]=(y[i]-sum)/LU[i*d+i];

}

2.3.4 Rezolvarea sistemelor de ecuații liniare cu factorizarea Cholesky

Definirea sAistemului de ecuații: rangul n, A matricea coeficieAnților A, vectorul termenilor liberi b.

VerifiAcarea simetriei matriceiA A. Dacă matricea nu Aeste simetrică se lanAsează un mesaj de eroare și se întrerAupe algoritmul;

AFactorizarea CholeskAy pe loc în matriceAa A:

InițializAarea coloanei curentAe j din matriceaA L pentru care se deterAmină elementeleA nenule: j <– 1;

Calculul expAresiei de sub raAdical pentru dAeterminarea elementAului diagonAal_ jj :

și verificaArea semnului Aacesteia. Dacă S <A 0 se transmite unA mesaj de eroare Ași se întrerupe algoritmul. Dacă S >= A0 se trece la pasul 3.iiAi;

DetermAinarea elementului diagAonal _ jj și memAorarea lui într-uAn vector distinct:

D_ j <–;

DeterminarAea elementelor subdAiagonale de pe coloana j a mAatricei L și meAmorarea lor în matricea A:

Se treceA la tratarea următAoarei coloane diAn matricea L : j <– jA+1. Dacă j <= n se rAevine la pasul A3.2. Dacă j > n se Atrece la pasul A4;

RezolvarAea sistemului inferiorA triunghiular L * y = b pArin substituAție înainte și memoraArea soluțieiA în vectoruAl b;

RezolvAarea sistemului supeArior triunghiulaAr * x = y = b pArin substituție înAapoi și memorarea Asoluției în vectorAul b.

2.3.5 Metoda iterativă Jacobi

MetodaA iterativă Jacobi, A numită și metodaA iterațiilor simultane, A folosește o desAfacere A = N – P, în careA matricele N și P se aleg Aconform relaAției:

N =A D

P = -v L – R

unde DA, L și R sunt matAricele din desfAacerea standard, A iar Atoate elemenAtele diagonale a_Aii sunt nenAule. Folosind aAceastă desfacere înA relația generală de Arecurența, seA obține formaA matriceala a relaAției de recurența Apentru metoda JAacobi:

D * Ax_(k+A1) = – ( L + AR ) * xA_k + Ab

Pentru Aun element x_i alA vectorului necunAoscutelor, la iteArația k+1, rAelația de recuArența capata fAormă:

care repArezintă formula deA iterare a metodei JacAobi. Inspecția sAumară a acestei forAmule sugereazAă imediat motiAvul pentru Acare toate elementelAe diagonale a_ii trebuAie să fie nenule.
„Metoda iteraAtivă Jacobi este convergentă daAcă, pentru fiecare liAnie din matricAea A, sumă valorilor absolAute ale termenilor dinA afară diagonalei Aprincipale nu depășAește valoarea absolută a tAermenului diagonAal” (Hoffman, KennethA; Kunze, Ray 1971, pag. 124). MatAricele care saAtisfac aceastăA proprietate Ase numesc diagonalA dominaAnte.
O particularAitate a metodei Jacobi seA referă la modul cumA este folosită aproAximația anterioară x_k pentruA calculul noii aproAximații x_(k+1). AAstfel, se constaAtă ca noile aproximaAții ale fiecăreiA necunoscutevse detvermină în funcțiev de aproAximațiile anterioare aleA tuturor celorlalte necAunoscute A( j <> i ). Din acest mAotiv, noua aproxiAmație nu oA poate înlocui pAe cea anterioară în Avectorul x și, în cAonsecință, aplicarea Ametodei Jacobi necesită Afolosirea a cel puțin doAi vectori : unA vector x, cAare memorează A aproximația anterioarăA și un vector y, careA memorează aproxAimația nou calculată. La Asfârșitul fiecărei iterații Avectorul x este aActualizat, prin coApierea în el a Aelementelor vecAtorului y.

AlgoritmuAl 1 – Sisteme de Aecuații liniare – MetodAa iterativă JacAobi

DefinireaA sistemului de eAcuații: rangul n, mAatricea coeficiențiloAr A, vectorul termenilor Aliberi b;

DefinirAea parametrilor de iterare: abaAterea relativă maximăA admisă Emax și nuAmărul maxim dAe iterații NAmax;

Calcul Aiterativ:

StabAilirea aproximațiAei inițiale, identică cu terAmenii liberi:

InițialAizarea procesului itAerativ: It <– 0.

InițAializarea abaterii relatAive maxime în iterațiaA curenta cu o valoare sAuperioară lui Emvax : Dx <– Emax + 1.

Dacă As-a atins numărul maxAim de iterații (It=Nmax) sauA abaterea Dx a trecut sub valoaArea admisă (A Dx <= Emax ), se încheie pArocesul iterativ și se trece laA pasul 4;

TrecAerea la o nouă iterație: ItA <– It + 1.

CalculuAl noii aproximații în veActorul y:

CalAculul abaterii relativeA maxime în iterația Acurentă:

AcAtualizarea vectorului apAroximațiilor din ulAtima iterație:

Se rAevine la pasul 3.iv. A

StabAilirea condițiilor de ieșAire din bucla iteratiAva:

dacă ADx <= Emax (metodAa converge), se afișează soluția apAroximativăși numărul deA iterații efectuAate It; A

dacăA Dx>Emax, dAar It=Nmax (meAtoda nu converge), sAe afișează mAesajul "Depășire nAumăr maxim iterațiAi";

2.3.6 Metoda iterativă Seidel-Gauss

Ca șiA în cazul metodei Jacobi, Aapariția termeniloAr aii la numitorul aAcestei expreAsii reflectă necAesitatea ca toate elemenAtele diagonale ale Amatricei A să fieA nenule.
O compaArație între formulele de iterAare ale metodelor JacAobi și Seidel A- Gauss evidențiază următoarea Aparticularitate:

în cazul metodeAi Jacobi noile apAroximații se determinăA folosind eAxclusiv aproximațiile Adin iterația anteArioară;

prin cAontrast, metoda Seidel-GaAuss calculeazăA noile aproximaAții folosind Ași aproximațiile deterAminate deja în iterAația curentă (A, j=1,…,i-1 ).

ConsecințaA imediată a acestAei particularități o reAprezintă posibilitatea utilizăArii unui singur vector pAentru memorarea aAproximațiilor succesivAe. Pe măsurăA determinării noiAlor aproxiAmații , acesteaA înlocuiesc în vectovrul x vechile aproAximații , care nu Amai suAnt folosite înA iterația Acurentă.
„O Aaltă consecință aA utilizării aproximAațiilor deja calculate Apentru detAerminarea celorlalte apAroximații se referă la Aconvergența metodei” (Hoffman, Kenneth; Kunze, Ray 1971, pag. 77). De regulă, metoda Seidel – Gauss aduceA un plus de vitezAă de coAnvergență față de metoda Jacobi. Astfel, eAste de așteptat ca, poArnind de la o aceeași aproAximație inițială, metoda Seidel – Gauss să aAsigure precizia impusă într-uAn număr mai mic dAe iterații.
Ca și în cazulA metodei Jacobi, condiția Ade convergență a metodAei Seidel – GauAss o reprezintă formAa diagonal dominantăA a matricei coeficienAților A.

Codul C++:

#include<stdio.h>

#include<conio.h>

#include<math.h>

#define e 0.01

void main()

{

int i,j,k,n;

float a[10][10],x[10];

float sum,temp,error,big;

printf("Introduceti numarul de ecuatii ");

scanf("%d",&n) ;

printf("Introduceti coeficientii: \n");

for(i=1;i<=n;i++)

{

for(j=1;j<=n+1;j++)

{

printf("a[%d][%d]= ",i,j);

scanf("%f",&a[i][j]);

}

for(i=1;i<=n;i++)

{

x[i]=0;

}

do

{

big=0;

for(i=1;i<=n;i++)

{

sum=0;

for(j=1;j<=n;j++)

{

if(j!=i)

{

sum=sum+a[i][j]*x[j];

}

temp=(a[i][n+1]-sum)/a[i][i];

error=fabs(x[i]-temp);

if(error>big)

{

big=error;

}

x[i]=temp;

printf("\nx[%d] =%f",i,x[i]);

}printf("\n");

}

while(big>=e);

printf("\n\n are solutii");

for(i=1;i<=n;i++)

{

printf("\nx[%d]=%f",i,x[i]);

}

getch();

}

3.ECUAȚII NELINIARE

FieA ecuația

f (x) A= A0

unde f : [ a , b ] A→ R este continuAă iar f (a) f (b) A< 0.

Împărțim segAmentul [ a , b ] îAn două părți. DAistingem urmAătoarele cazAuri:

1. și atunAci este rădăciAna căutată șAi oprim procAedeul;

2. și în aAcest caz selectăAm din cele Adouă intAervale și pe acela pentru caAre valorile funcAției în capetAe au semne conAtrare.

Acest inteArval îl notăm [A a1 , b1 ] și apoi Acontinuăm proAcedeul.

Se obțAine, fie rădăAcina exactă, fie uAn șir de intervaleA închise cuprinseA unele în Aaltele

astfeAl încât

pentru n = 1, 2,…

Prin urmarAe avem

„CapetAele din stânga ale Aacestor intervaAle a1, a2, …,A an, … formeazăA un șir cresAcător și mărginAit superior Ade b, iar capeAtele din dreaApta b1, b2, A …, bn, A… formeaAză un șAir descresAcător și măArginită inferior Ade a” (Leon, StAeven J, 2006, pag. 65). ADin tAeorema „cleștelui” urmeazAă

( fiind limiAtă lor comună).

arătăm ca numAărul este rădăcina eAcuației (4.1). TrecâAnd la limită și ținânAd cont de continuitatea funcției f șiA de faptul ca șirurile și sunt conAvergente avem:

sau

adică

ObseArvație 1Metoda presAupune ca rădăcinile lAui (4.1) au fost sepAarate pe [a, b].

Observație 2Dacă este oA valoare aproxiAmativă a lui la pasul An atunci avemA

.

ObseArvație 3 „Metodă este comodăA peAntru obținereAa unei Aestimări inițAialAe a rădăciAnii separate, A pentru utilAizarea ei îAn alte metode Ași Aeste ușor prograAmAabilă pe calAAculator.” (Leon, SAteven J, 2006, pag. 67)

ObservAație 4 Procedeul conAvAerge lent.

ObseArvație 5 „În cazul în carAe rădăcinile nu au fost Aseparate luăm dupAă caz o valoAare foarte mică Apentru a1 (de exeAmplu -10 n cu n AN *) și b1 = 0A sau a1 A= 0A și b1 =A 10 n aAstfel încât să avem f (aA1) f (b1) < 0.” (LAeon, Steven J, 2006, pag. 80)

Observație 6 În moAmentuAl opririi Aprocedeului maiA putem îmbuAnătăți precizia Acalculelor făcând Amedia aritmAetică a ultimeAlor două valorAi an și bn (A n N * ), adiAcă

.

3.1Rezolvarea numerică a ecuațiilor neliniare

3.1.1. Generalități

Ecuațiile repArezintă expAresii matematicAe care conțin Ao variabiAlă (necunoscuAtă) și pot fi puse suAb forma geneArală:

f(x) = 0 (1)

„Egalitatea esAte valabilă numaAi pentru o mulțimAe finită și discretă de valorAi ale lui x. Expresia f(x) poAate conține valAori numerice operaAtori aritmeticiA și funcții eAlementare. RezolvaArea analitică (peA bază de formule)esAte posibilă numai îAn anumite caAzuri particuAlare sau Apentru ecuații poliAnomiale de gArad inferior” (RicardAo, Henry 2010 pag. 36). RezAolvarea numAerică permAite rezoAlvarea tutuAror tipuriA de ecuațiiA cu aproximațiiA oricât deA bune. FAenomenul deA aproximare nu Aeste un impedimAent deoaArece, în final soAluția va fi exprimatAă cu un nuAmăr finit de cifre Asemnificative. Deci AmetodeleA de rezolvAare numeArică sunt singurAul instrumentA viabil pAentru rezolAvarea ecuAațiilor. TrebuiAe însă mențioAnat ca rezolvareaA globală aAutomată (pentru tAot intervalul de variațiAe a variabiAlei x) este posibilAă numaiA pentru Aecuații polinAomiale. Pentru celAelalte tipuri Ade ecuații A (de tip transcAendent) aplicarAea corecAtă a metodAelor numerice estAe posibilă numAai după ce aAu fost ideAntificate intervaleAle care conAțin valorile sAoluției. În plus Autilizarea metodAelor numerice loAcale trebuie precedată Ade verificareAa condițiilor în carAe acestea pot fi aAplicate. Acestea de Aobicei se referă la propriAetățile funcției f(x) (deA exemplu continuitAatea) sau la cAele ale derivatAelor fuAncției.

3.1 2. Metoda bipartiției

„MetoAda bipartiției sAau metoda înjuAmătățirii intervalAului este o meAtodă simplă, puțin pretenAțioasă din punctul de Avedere a proprieAtăților funcției fA (x) ” (Sadun, Lorenzo, 2008, pag. 45). TotușAi este necesar însă Aca funcția să fie conAtinuă. Presupunem caA intervalul [a,b] conține o soAluție a ecuației. AAtunci:

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

„ProceduraA împarte înA două intervalul Aîn care sAe știe ca există Ao soluAție. Apoi esteA evaluată funAcția la Acapetele subintervaAlelor obținAute. DeoAarece funcția Aeste continuăA, rezultă ca suAbintervAalul pe care se faceA sAchimbarea de AsemAn conține soluția căutAată” (Sadun, Lorenzo, 2008, pag. 60). AÎn continuare acest iAnterval este împărțit la rândul lui în dAouă părți egale și analiză cAontinuă în același fAel. Astfel subinteArvalul care conține soluAția este restrâns pAe parcursul aplicAării metodei atâta tAimp cât numAărul de cifre semnificative Adisponibil permite mAărirea rezoAluției.

Procesul iAterativ este următorulA:

1. Se caAlculează mijAlocul inteArvalului x0 = (Aa + b)/2 ;

2. Se anaAlizează semnuAl funcțieiA la capătul Ajumătăților deA interval. PAorțiunea de A interval uAnde are locA schimbareAa de semAn conțiAne soluțiAa. ProcesuAl înjumătățirii Ase va aplica îAn continuareA pentruA acest subinAterval:

DacăA f(a)f(x0) < A0 atunci bA := x0 ; MergAi la pasul 1A;

Dacă f(x0)fA (b) < 0 atunciA a := x0 ; MergAi la pasul 1.

// metoda bipartitiei

#include <conio.h>

#include <stdio.h>

#include <math.h>

float a,b,eps,x;

int i;

float bipart(float a,float b,float eps);

float f(float x);

void main(void) {

clrscr();

printf("metoda bipartitiei :\n");

printf("a="); scanf("%f",&a);

printf("b="); scanf("%f",&b);

printf("precizia:"); scanf("%f",&eps);

x=bipart(a,b,eps);

printf("x=%f",x);

printf("\n numarul de iteratii este = %d", i);

getch();

}

float bipart(float a,float b,float eps) {

float x;

i=0;

do {

x=(a+b)/2;

if(f(a)*f(x)<=0) {

b=x;

} else {

a=x;

}

i++; }

while(fabs(b-a)>=eps);

return x;

}

float f(float x) {

return (cos(x)/sin(x)-x); // ctg(x)-x ?

}

3.1.3 Metoda coardei

„ Metoda coardeiA sau a metodaA părților proporționaleA cere satisfaceArea următoarelor condiții refeAritoare la modul de variație aA funcției f(x) pe iAntervalul unde se aAplică metoda. Astfel primele doAuă derivate ale funcției Af(x) să fie contAinue pe interAvalul (a,b) și să-și conserve semAnul” (Sadun, LorenzoA, 2008, pag. 60).

Din punct dAe vedere geometric acAeste condiții au uArmătoarea interpreAtare:

* dacă pArima derivată Aeste continuă funcția areA variație netedă, fAără salturi bruște și fără frânturAi ale graficului;

* dacă prima derivată își conservă semnul variația funcției este monotonă;

* dacă deriAvată a două își consAervă semnul funcția nu Aconține puncte deA inflexiune.

„Soluția aAproximativă este calcuAlată la intersecția aAbscisei Ox cu segmentul de dreaptă (coAardă corespunzătoarAe porțiunii de grafic) care uAnește punctele de coorAdonate (a,f(a)) A și (b, Af(b))” (Sadun, Lorenzo, 2008, pag. 55). După Adeterminarea unei aproxiAmații a soluției Aaceastă deviAne noul capăt al intervalului dAe lucru și procedeul se aAplică în continAuare până când variaAțiile soluției aproximative deviAn nesemnifiAcative.

Soluția aproAximativă la pasul Aurmător se determAină în funcție de Acea de la pasul precedentA printr-un proces de Atranslație cu incremAentul h :

xk+1A = xk + h A (4)

În funcție de poAziția relativă a coardAei față de grafic puteAm avea două sitAuații.

„Dacă cAoarda se află laA stânga graficAului atunci pAunctul de porAnire al aproximațiilor este pAunctul a, punctul b răAmânând punct fix Ape parcursul proAcesului iteratAiv, iar deplasareAa aproximațiilor se facAe de la stânga la dAreapta” (Sadun, A Lorenzo, 2008, pag. 45). Deci valoareAa h este poziAtivă, iar valoarea apAroximației inițiaAle se va conAsidera x1 = a.

Dacă AcoardAa se află la dAreapAta graficului AatunciA punctul de pAornire al aproximațiilor esAte punctul b, punctul a răAmânând punct fix pe parcAursul procesului iteArativ, iar deplasareAa aproximațiilor se face de lAa dreapta la stâAnga. Deci valoAarea h este negAativă, iar valoarea aproAximației inițiale se Ava consideraA x1 = b. Soluția aprAoximativă xk+1A la pasul k+1 se determină în fAuncție de cea de la pasulA precedent xk confAorm relației:

Încadrarea întAr-unul dintre cele doAuă cazuri se faAce în funcție de semnele derivAatelor de ordiAnul unu și doi. AlegereaA punctului de pornire aAl iterațiilor și implicAit alegerea relației Ade calcul corespunAde valorii pozitive a Aprodusului dintre vaAloarea funcției șiA valoarea derivatei Aa doua în punctul respectiv. AAstfel dacă f(a)f'(Aa) A> 0, rezultăA ca a estAe punct de pornire și coAarda se găsește lAa stânga graficului, A iar dacă f(b)f'(b) >A 0, rezultă ca b esAte punct de porniAre și coarda se găAsește la dreAapta graficului.

Fig.1.

3.2 Metode de partiționare

După încadrarea Aunei soluții exAacte, se pot aplica o serieA de metode iterativeA care permit determinarAea unei soluții aproAximative în limita preAciziei impuse. A Dintre acAestea, metAodele de paArtiționare acționează direcAt asupra intervalAului în care a foAst încadrată soluția, urmAărind "comprAimarea" acestuia pAână la limita imApusă de criteriuAl de oprire. Din acAeastă categoArie fac parAte metoda bisectiAei, metoda sAecantei și metoda cAăutării cu pas vaAriabil. DeoareAce la fiecareA iterație, intervAalul de lucrAu încadreazAă permanenAt soluția Aexactă, conveArgentă acestorA metodeA este garantaAtă. Din păcaAte, ele se caracterizeAază printr-un numAăr mare de iterații necAesare atingerii preciziAei impuse, deci priAn timpi de calcAul mari.

3.2.1 Metoda bisectiei

„Metoda biAsectiei, numită Auneori și metoda dihotomiAei sau a înjumătățiArii intervaleloAr, este cea mai simAplă dintre metodelAe de rezolvareA a ecuațiilor transcendente și aAlgebrice” (Greub, Werner H. 1981, pag. 66). Se Aconsideră ca, printr-un proceAdeu oarecare, s-a reuAșit localizarea rădăciniAi exacte a ecuațieiA f(x)=0 în intervAalul [,]. În ipAAoteza în care functia f(x) este coAntinuă, iar rădăciAna este singuruAl zerou al lui Af(x) în [,A], la extremitățile intervalului funcția ia valorAi de semnAe contrare: f(A) * f()<0.

DeterminareaA aproximației ' a rădăciniAi exacte cu o precAizie folosinAd metoda bisectiAei folosește următoarea schemAa (vezi și figura de Amai sus): intervalul [,] sAe înjumătățeAște prin puncAtul m=(A+)/2 și sAe calculeazAă prodAusul f(m) * f(). DacăA f(m) * f() estAe pozitiv, rădăcAina se găsește între și m.În AAacest caz, se reține valoAarea lui m ca exAtremitatea dreaptă a intervalului (<– m) șiA se reia procedeul. Dacă f(m) * f() esteA negativ, rădăcinaA se găsește între mA și . De aceAastă dată, se modifică extremAitatea stângă a intervAalului (<– m) și se rAeia procedeul. AcAeastă schemă se aplică înA mod repetat până câAnd lungimea interAvalului [,] – modificat Ade la o iterație la alta – scade sAub valoarea limită 2A*, adică – < 2A*. Dacă, în aAcest moment, se conAsideră ca rădăcină Aaproximativă 'A=(+)/2, acAesta nu se îndepărteAază de soluția exaActă cu mAai mult de . Desigur, A într-un caz baAnal, este posAibil ca, în cuArsul înjAumătățirii intervAalelor succesive [A,], punctul m Asă coincidă cu rădăAcina exactă . AceastăA situație se recAunoaște prin anularea pArodusului f(m) * f(), cAaz în care schAema de calcul se întrerupe, disApunând în acesAt caz chiar de răAdăcina exactAă '=m=.

Cod c++ pentru metoda bisectiei:

#include <iostream>

using namespace std;

double f(double x)

{

return 3*x + 3;

}

double sigma = 0.00001;

double getRoot(double a, double b)

{

double c;

if(b-a < sigma) return (a+b) / 2.0; // S-a gasit radacina, o returnez

else

{

c = (a+b) / 2.0;

if(f(a) * f(c) < 0) return getRoot(a, c);

else return getRoot(c, b);

}

int main()

{

cout << getRoot(-10, 10);

system("PAUSE");

return 0;

}

3.2.2 Metoda bisectiei Algoritm

Definirea funcAției f(x), a inAtervaAlului de lucru A [A,], a Apreciziei și a nAumAărului maxim de AiterațAii Nmax.

ProcesuAl iterativ:

InițializaArea procesului iteArativ: It <– 0;

Dacă s-aA atins precizia doritAta (- A< 2*) sau Anumărul maxiAm de iterAații Nmax se încheie bucla iteArativă și se trecAe la pasul 3.

Se trece laA o nouă iterațAie: It <-A- It+1;

ÎnjumăAtățirea intervaAlului curent: A m <– (+A)/2 ;

StabiAlirea nouluiA interval de lucru:

Dacă fA (m) * f()A<0, rădăcAina se găseștAe în [m , A]; se actualAizează limitaA stânga: <– m și se trece la pasul 2.vi;

Dacă f(Am) * f()>0, rădăcinaA se găseștAe în [ , m]; sAe actualizează limita Adreapta: <– m și se trece la pAasul 2.vi;

Dacă f(m) A* f()=0, rădăcina eAste m; se actualizeazAă ambele liAmite: <–A m,<– m și seA trece la pasuAl 2.vi;

Se revAine la paAsul 2.ii;

Calculul rădăAcinii aproximativve: x <– (A+)/2.v

3.2.3 Metoda secantei

„MetodaA secantei, numită și Ametoda părților provporționale, restrAânge intervAalul [,] ce încadrAează soluția exactă îAn iterația curentă Aprin raportarea laA valorile fuAncției la extreAmitățile intervalului” A (Sadun, LoArenzo, 2008, pag. 45) . Astfel, dacă nouAă aproximAație x se alegAe astfel încât soluția exactă Asă se găsească înA intervalul [A, x], valoarAea luiA x rezultă din egaliAtatea proporțiilor:

InterpretareAa geometrică a acestAei relații corespundAe construcției Adin figura. AAstfel, pe inteArvalul [,] curba y=fA (x) este aproximatăA prin dreaptă cAe trece prin cAele două puncte A șAi B de la extremitățile inteArvalului. În aceste Acondiții, soluția exactAă () urmează Aa fi aproximată prinA abscisă punctului de intersAecție a dreptei AB cu axa OXA, notată cuA x. Noua aproAximație x se deterAmină impunând condițiaA ca în ecuația drevptei AB :

punctul (x,y) să se găsească pe axa OX, adică y=0:

În cAontinuare, dintre intervaleAle [A, x ] și [ x ,] A se reține aAcela ce încaAdrează soluția – acel Ainterval la extremitățile Acăruia funcția f(x) A ia valori dAe semne conAtrare. Aplicând o relAație asemenatoare nouluiA interval se obține o noAuă aproximațiAe a soluțviei exacte și procesul conAtinuă până la satisfacerea unuiA criteriu de ovprire.

AlgoritAmul pentru MetodAa secanteiA

DefinirAea funcției f(x), a iAntervalului de lvucru [, ], a precizieiA și a numărAului maxim Ade iterații NmaAx.

AProcesul Aiterativ:

IAnițializarea procesului iteratiAv: It A<– 0;

DaAcă s-a atins precizia Adorită (- A< 2*) sau numAărul maxim de iteArații Nmax se încheie buAcla iterativaA și se trece la pAasul 3.

Se treAce la o nouă iterațiAe: It <– AIt+1;

CalculuAl noii aproximații:

StabAilirea noului intervaAl de lucru:

Dacă Af(m) * f()<0, rădAăcina se găseAște în [ x,]; se actAualizează limita sAtânga:<– A x și se revinAe la pasul 2. Aii.

Dacă fA (m) * f()>0A, rădăcina se Agăsește în [A,x]; se actuAalizează limita dAreapta:<– x și sAe revine la pasul A2.ii.

DacAă f(m) * f(A)=0, rădăcinaA este x; se acAtualiAzează ambele limiAte: <– xA, <– x șAi se revine la AApasul 2.ii.

Calculul rădăcinii aproxAimative: x <– (A+ )/2.

Codul C++:

#include<iostream.h>

#include<math.h>

#define eps 0.00000000001

#define iter 200

double f(double x)

{

return x*x*x-2*x*x*cos(x)+x-3;

}

void main()

{

unsigned char i;

double x,x0,x1,a,b,y;

cout<<"a=";cin>>a;cout<<"b=";cin>>b;

i=0;x0=a;x1=b;x=x0;y=f(x);

if (f(x0)*f(x1)<0)

{

while ( (i<=iter) && ((y<-eps) || (y>eps)) )

{

x=x0-f(x0)*(x1-x0)/(f(x1)-f(x0));

y=f(x);

if (f(x0)*y<0) x1=x;

else x0=x;

cout<<"\n\nf("<<x<<")="<<f(x)<<" la iteratia "<<(int)i;

i++;

}

if (i>iter) cout<<"problema nu se poate rezolva in nr.maxim de iteratii";

} else cout<<"interval invalid";

}

3.3 Metode de aproximații succesive

„După Acum reiese și diAn numele lor, meAtodele de aproximații suAccesive determiAnă o soluție aproAximativă a unei ecuații Aneliniare prin conAstruirea unui șAir de aproximațAii succesive care, în anumitAe condiții, Aconverge cătrAe soluția exactAă” (Sadun, LAorenzo, 2008, pag. 136). De această dată nuA se mai acționează Aasupra intervalulAui în care a foAst izolată soluțiAa exactă. AcestA interval este fovlosit numai pventru stabilirvea aproxiAmației inițiale, care poateA fi aleasă, în Aprincipiu, oriunde înA interiorulA acestuAia.

O caracteristicăA a metodelor dAe aproximații sucAcesive se referă la inAterpretarea geo- metrica Ace se asociazAă procesului iteratAiv. Pentru metodele Ade partiționare, rezAolvarea ecuației f(x)=0 sAe face prin determinaArea din aproape Aîn aproape, până laA o precizie impuAsă, a punc- tului de iAntersecție a curbeAi y=f(x) cu axAaA absciselorA. Metodele Ade Aaproximații succesivAe înlocuiesc ecAuația sub forma iAmpAlicita f(x)=0 cuA o ecuație ecAhivAalentă expArimAată însă expliAcit:

a căAreiA rezolvare presupune dAeterminareaA punActului de intersecvție a curbelor; y=(x) și y=g(x). Din considerente deA simplificare a calculelor, se Acaută ca expresiile funcțiilor A(x) și g(x) să aibă o coAmplexitate cât mai reAdusă posibilv. În acevst sens, cele Amai răspândiAte metode utAilizează un caz partiAcular al ecuației eAxplicite, și anumAe, acela pentru Acare curbă y = (x) Ase reduce la o dreaptă, A iar ecuația explicitvă căpăta formAă:

DeterminAarea rădăcinii aproximative seA face pornind de la o aproAximație inAițială x_0, corectatăA apoi succesiv folosind o forAmulă de recurența vde forAmă:

Dacă șiruAl aproximațiilor succeAsive este convergent, el tinde cătrAe soluția exactăA a ecuațAiilor echivalente Af(x)=0, rAespectiv x=g(x). DiferiteAle metode de aAproximații sucAcesive folositeA în practică se dAeosebesc prin modul dAe construire a ecuAației explicAite, în pArticular, vprin alegerea funAcției g(x), aleAgere care determiAnă și condițiileA specifice dAe convergenAță. În compaArație cu metoAdele de partițioAnare, conveArgența metoAdelor de aproxAimații sucAcesive este, de rvegulă, mai rapiAdă, dar dinA păAcate nu întotdeauAna asigurată. A

3.3.1 Metoda contracției

ÎnlocAuirea ecuației A f(x)=0 printr-oA ecuație expliAcită x=g(x) se Apoate realiza, Ade regulAă, pe mai multe cAăi. Cea mai simplAă dintre acestea determinăA funcția g(x) suAb formă:

g(x) A= x + f(x)

În continuare, Avom considera ca metoAda contracției, nuAmită uneori improApriu și metoda aproxAimațiilor succesive, esteA generată de funcțiAa g(x) de acAeastă formă. ȘiAul aproximațiiloAr succesive este geneArat pornind de la aproAximația inițială x_0 , cu relațAia de recurența:

Se poate arAăta ca între eroArile de aproxiAmare în două Aiterații succesive e_n și Ae_(n+1) există relația :

care pAermite stabilirea uAnei forme primare a condițieAi de convergență. AAstfeAl, pentru ca șirul aproxiAmațiilor succesAive să fie convergent, erAoarea de aproximare tArebuie să scadă înAtre două iterații consecutive, adică |Ae_(n+1)| < |e_n|, ceea ceA conduce la A|g'()| < 1. AcAeasta reprezintă oA condiție necesară, dar nuA și suficientă pentru asAigurarea convergenței. AO valoare subuniAtară în modul a deriAvatei g'() garantează eAxistența unuiA interval [,], în Ajurul soluției exacte A, în care pAoate fi aleasă aproxiAmația inițială Ax_0, astfel încât Aprocesul iterativ să fie Aconvergent. De fapt, A o condiție deA forma |g'(Ax)| < 1 trebuiAe satisfăcutAA în întregul interval [,]. Chiar dacă condițiva |g'()| < 1 este satiAsfăcută, dar aproximațiAa inițială este aleasAă departe de soluțAia exactă , strucAtura funcției g(x) pAoate conduce la Aun proces divergAent.
ConvergențaA procesului iterAativ este guvernată de o teAorema de punct fix care, A în princAipiu, impune următoarelAe condiții: pentru un inAterval [,], oriAcât de larg, alegereAa unei aproximAații inițiale x_0 în Ainteriorul acestAuia, care să asigure conAvergentă, este varbitrară dacă Ași numai dacă funcția g(xA) este o aplicație strict Acontractantă pe acelA interval (vezi figura de mai jAos).

InterpretareaA geometrică a noțiunii Ade "aplicație strict contraActantă". (a) Funcția g(x) eAste o aplicație strict coAntractantă pe un anumAit interval dacă proiAecția acestui interval peA axa Oy, prin curba AAy = g(x) se contractă. (b) În caz cAontrar, când proiecția Aintervalului Arespectiv pe axa Oy, A prin curba y = g(xA) se dilată, g(x) nAu mai este oA aplicație Astrict contractaAntă.

Evoluția unoAr procese iteratiAve convergente sau dAivergente este ilAustrată în figurAă de mai jos. A În funcție de Asemnul derivatei g'A în vecinătatea Asoluției , cAonvergentă pAoate fi monotonAă (cazurile a și b), Apentru g'()>0, sau Aoscilantă (cazuriAle c și d), pentruA g'()<0. De asemeneAa, în cazurile e și f Asunt prezentate douăA procese divergentAe, unul mAonoton și celălalt Aoscilant. Cazul |g'A ()|=1 este deosebit dAe sensibil deoarece, în Afuncție de forma curbei y=g(x), seA poate obține atât conveArgentă (cazul g), cât și dAivergență (cazul h) șAirului aproximațiilor succesive.

3.3.2Ecuații neliniare – Metoda contracției

DefinireaA funcției f(x), a aAproximației inițialAe x, a preciziei AEps și a numărAului maxim dAe iterații Nmax.

ConstruiArea funcției g(x) A= x + f(x).

PrAocesul iterativ:

InițiAalizarea procesulAui iterativ: It A<– 0;

DaAcă s-a atins precizAia dorită (|f(x)|<EpAs) sau numărul maxAim de iterAații (It=Nmax) seA întrerupe bucla itAerativa și se trecAe la pasul A4.

Se treAce la o nouă iterAație: It <– It+A1;

Calculul nAoii aproximații: x <– Ag(x)

Se revAine la pasul A3.2.

StabiAlirea condițiilor de ieșiAre din bucla iteArativă:

DacăA |f(x)|<Eps – proces cAonvergent – soluția Aaproximativă esAte x.

DaAcă |f(x)|>=Eps și It=Nmax, A se afișează mesajul "ADepășire număr maAxim iterații".

3.4 Metoda Newton

„Una dintAre cele mai cunoscute șAi mai folosite tehnici deA rezolvare a ecuațiAilor neliniare este metoda ANewton, denumita uneori și metoda ANewton-Raphson sauAmetoda tangentelor” (HoffAman, Kenneth; Kunze, A Ray 1971, pag. 69). EAa se deosebește Ade alte metoAde de aproximații sAuccesive prin faptulA ca pentru fieAcare punct dinA șirul aproxiAmațiilor este Anecesară atâtA evaluarea funcției Af(x) ce defineșAte ecuația, cât și a deArivatei acesteia f '(x).

„ValoareaA aproximativă Aa rădăcinii Aexacte se Acalculează folosAind un șirA de aproximațiAi succesive {x_0, x_A1, x_2, … } construit Adupă următorul moAdel” (HoAffman, Kenneth; Kunze, Ray 1971A, pag. 77). PornindA de la aproximațiAa x_0, curbă yA=f(x) este aproximată în Apunctul de coordonAate (x_0, f(x_0)) prin tAangenta la ea. NoAua aproximație x_1 se obține lAa intersecția acestei tangențAe cu axa absciselor. FolosiAnd pe x_1 ca aproximațieA inițială, se reia procedeul, determiAnându-se o nouă aproximație xA_2 s.a.m.d. pânAă când abaterea între douAă iterații succesAive scade sub o valAoare prag impusAă: |x_(n+1) – x_n| <.

„Alegerea Aaproximației inițiale inflAuențează în bună mAăsură procesul iteraAtiv. (a) Dacă aproAximația inițială esteA prea departe deA soluția exactă, este posAibil ca, datorită Aunei forme Aaparte a curbei y = f(x), A noile aproximațiAi să fie aruncate sApre infinit. (b) Într-o Asituație mai fericAită, procesul rămâAne convergent, dar șirulA aproximațiilor suAccesive se înAdreaptă către o altăA rădăcina decât ceva căutată” (HoffmanA, Kenneth; Kunze, Ray 1971, pag. 99).

Din punct dAe vedere formal, meAtoda Newton foloAsește formulă de reAcurența (iterare):

CondițiileA de convergență ale Ametodei NAewton sunt relativ compleAxe ca formă și seA referă nu numaiA la funcția f(x), A ci și la primele Asale două derivate, fA '(x) și f ''(x). A
Marele avantaAj al metodei ANewton este rata mAare de convergență. În apropierAea soluției exacte, se Aasigură practic dublarAea numărului de cifre exaActe ale soluției calcAulate la fiecaAre iterație. AceastAă proprietate remarcaAbilă este "cartea de Avizită" ce recomanAdă metoda NewAton ca fiinAd cea mai eficieAntă cale de rezolvAare a unei ecuații nelAiniare pentru cAare este posiAbilă evaluarea deArivatei f '(x). Remarcați totAuși precizarea din fraAză anterioară ("În aprAopierea soluțiAei exacte…") și nu uitațiA condițiilAe de convergență Aatât de alambicate, care se refAeră atât la funcAția f(x), cât și la primeAle sale două derivAate. DinA acesteAA cauze, despre metAoda Newton se spuneA ca are proAprietăți locale deA convergență fAoarte bune, dAar se poate compAorta lameAntabil la nivel gloAbal. În situațiile dAin urmă metodAa Newton pAoate fi aplicată ca Ao procedură tAerminală, penAtru rafinarea efAicientă și foarte rapAidă a unei aproximAații obținute prin aplicareaA, în prima fază, a uAnei alte metode, Amai puțin sensibilAe din punctul de veAdere al convergenAței dar, în prinAcipiu, mai lentăA.

3.4.1Metoda Newton Algoritm

DefinAirea funvcției f(x), a derivateiA f '(x), a aproxAimației inițiale x, a pAreciziei Eps șiA a numărului maxAim de iterații ANmax.

InițiAalizarea procesAului iteratiAv: It <– A0;

ProAcesul iterativ:

Se trece la o nAouă iterație: IAt <– It+1;

CalculAul corecției: dx <A– – f(x) / f '(x)

CalcAulul noii apAroximații: x <– x + dx

DacăA s-a atinsv precizia dorită (|dx| <= Eps) sau Anumărul maxim de iterațAii (It=Nmax) se întreruApe bucla iterativa și sAe trece la pasuAl 4.

Se rAevine la pasul A3.1.

SAtabilirea condițiilor dAe ieșire din buAclă iteratiAvă:

Dacă |dAx|<Eps – proces Aconvergent – soAluția aproximatiAvă este Ax.

Dacă |Adx|>=Eps șiA It=Nmax, se afișAează mesajulA "Depășire nuAmăr maxim AiterațiiA".

Numele "MAetoda lui NewtAon" este derivat din faAptul că Isaac NewtoAn a descris un Acaz special al Ametodei în DAe analysi pAer aequationes nAumero terminorum infiniAtas (scris în 1669, Apublicat în 1A711 de către AWilliam Jones) și înA De metoAdis fluxionumA et serierumA infinitarum (sAcrisă în 1671, tradus Ași publicat ca MeAtoda fluctuațiilor înA 1736 deA către John ColsAon). Cu toatAe acestea, metAoda lui difAeră substanțAial de metoda mAodernă de mai Asus: Newton aAplică metoda Anumai pentru polinoame. AEl nu calcula aproximAări succesive A, dar calculeAază o secvență Ade polinoame și numai Ala sfârșit el ajunge la o Aaproximare a rădăcinAii x. În cele dAin urmă, NewtoAn consideră metAoda ca pur algebricAă și nu face niAci o mențiune cu pArivire la calculul numeriAc. Metoda lui IsAaac Newton poate fAi derivată de Ala o metoAdă similară, dar mai puțiAn precisă, metoda lAui Vieta. EAsența meAtodei Vieta lui pAoate fi găsită în lucrărilAe matematicianuluiA persan Sharaf alA-Din al-Tusi, , înA timp ce AAAsuccesorul său Jamshīd al-Kāshī aA folosit o formAă a metodei lui ANewton pentAlui Newton pAentru calcularea rădAăcini pătrate a fost cAunoscut mult mai devAreme și este adesea nAumit „metoda babiloAniană”.

Metoda lui NeAwton a fost folosită deA către matematicianul jaAponez din secoluAl 17 Seki Kōwa pentru a rezolva ecuații cu o sinAgură variabilă, deși legăAtură cu calculul lipsea.

Metoda lui NewtoAn a fost publicată prima Adată în 1685, înTratAât istoric și pracAtic de algebră de John Wallis. AÎn 1690, Joseph Raphson aA publicat o descrAiere simplificatAă în Analysis aequatiAonum universalis. RaphsoAn prezenta metoda Alui Newton ca o metodă pur algAebrică și limita utilizarea sa la funcții Apolinomiale, darA el descrie metoda îAn termeni de aproximAări succesivexn în loc Ade mai complicatăA secvență deA polinoamAe utilizate de NewtAon.

În cele Adin urmă, în 1740A, Thomas Simpson a dAescris metoda luAi Newton ca oA metodă iterativAă pentru rezolvarea Aecuațiilor generale nelivniare utilizând cavlcul, oferindv, în esență, descriereav de mai sus. În aceAeașAi publicație, SAimpson oferă, vde asemeAnea, genAeralizarea la sistemeleA de două ecuații șiA constată că metoda luvi Newton poate Afi folosit pentru rezolvarAea problemelor de optiAmizare prin setarea gradientA de la zero.

Arthur Cayley înA 1879, în ProblemaA imaginar NewtAon-Fourier a fost primAul care a observatA dificultăți în generaAlizarea metodei lui NewtAon la rădăcinile coAmplexe de polinoame cu un grad Amai mare de 2 și valoriAle inițiale complexe. AceAst lucru a deschis calea Apentru studiul teoriei iterațAiilor funcțiilor rațAionale.

Metoda Newton pentru sisteme de ecuații neliniare

Fie sistemul de ecuații:

(1)

Unde. funcțiile. fk:A Rn, A deschis., fk C1(A), iar. Jacobianul.

)x=(x1, x2, …, xn) (2)

Soluția. y=(y1, y2, …, yn) a sistemului. (1) se determină. cu ajutorul. șirului aproximațiilo.r succesive, astfel:

Se alege (arbitrar) prima aproximație a soluției y:

x(0)=(x(0)1, x(0)2, …, x(0)n) (3)

Se determină. succesiv aproximațiile. soluției y.:

und.e, (5)

unde k=0,1,2,…,m,…

Aproximația. y=x(m) se consideră. satisfăcătoare când.

,

unde. >0, dar suficient. de mic, reprezintă. precizia soluției., prescrisă inițial..

Codul C++:

#include <iostream>

#include <cmath>

using namespace std;

double find_root(double num, int root)

{

double x = 0.0;

double xn = 0.0;

double val;

int repeat = 0;

int i;

for (i = 0; i <= num; i++)

{

val = i*i-num;

if (val > 0.0)

{

xn = (i+(i-1))/2.0;

break;

}

while (!(repeat++ >= 100 || x == xn))

{

x = xn;

xn = x – (pow(x, (double)root) – num) / (root * pow(x, (double)root-1));

}

return xn;

}

int main()

{

double num;

int root;

string root_name;

cout << "Enter a number: ";

cin >> num;

cout << "Enter the number of the root you want to find for this number: ";

cin >> root;

if (root <= 1)

{

cout << "The root must be greater than 1.\n";

system ("pause");

return 0;

}

if (root == 2) root_name = "nd";

if (root == 3) root_name = "rd";

if (root > 3) root_name = "th";

cout << "The " << root << root_name << " root of " << num << " is " << find_root(num, root) << ".\n";

system ("pause");

return 0;

}

Bibliografie

Ebâncă, D., Metode numerice, Ed. Sitech, Craiova, 1994.

Groza G., Analiza numerica, Ed. MatrixRom, Bucuresti, 2005.

Iorga, V., Jora, B., Programare numerică, Ed. Teora, 1996

Bretscher, Otto (June 28, 2004), Linear Algebra with Applications (3rd ed.), Prentice Hall, ISBN 978-0-13-145334-0

Farin, Gerald; Hansford, Dianne (December 15, 2004), Practical Linear Algebra: A Geometry Toolbox, AK Peters, ISBN 978-1-56881-234-2

Nicholson, W., K., Linear Algebra and with Applications, PWS Publishing Company, Boston, 1995.

Kolman, Bernard; Hill, David R. (May 3, 2007), Elementary Linear Algebra with Applications (9th ed.), Prentice Hall, ISBN 978-0-13-229654-0

Leon, Steven J. (2006), Linear Algebra With Applications (7th ed.), Pearson Prentice Hall, ISBN 978-0-13-185785-8

Ricardo, Henry (2010), A Modern Introduction To Linear Algebra (1st ed.), CRC Press, ISBN 978-1-4398-0040-9

Sadun, Lorenzo (2008), Applied Linear Algebra: the decoupling principle (2nd ed.), AMS, ISBN 978-0-8218-4441-0

Hoffman, Kenneth; Kunze, Ray (April 25, 1971), Linear Algebra (2nd ed.), Prentice Hall, ISBN 978-0-13-536797-1

, Linear Algebra, Graduate Texts in Mathematics (4th ed.), Springer, ISBN 978-0-8018-5414-9

Arthur Cayley în 1879, în Problema imaginar Newton-Fourier