refacut
TRANSCRIPT
Metode numerice în algebra liniară şi metode iterative pentru
rezolvarea sistemelor neliniare.
Profesor Coordonator: Pohoață Alin
Student: Ion Silviu Lucian
Universitatea: Valahia, Târgoviste
Specializarea: Matematică-Informatică
Târgoviște
2014
Cuprins
1.ALGEBRA LINIARĂ...............................................................................................................................3
1.1 Spațiile vectoriale........................................................................................................................4
1.2 Transformările liniare..................................................................................................................5
1.3 Subspațiile, sectoarele și bazele..................................................................................................6
1.4Metoda eliminării complete (Gauss-Jordan).................................................................................7
1.4.1 Probleme rezolvate...............................................................................................................8
1.5 Metoda iterativă JacoAbi...........................................................................................................10
2.METODE NUMERICE ÎN ALEGBRA LINIARĂ.......................................................................................13
2.1Eliminarea. Gaussiana.................................................................................................................13
2.2Descompunerea LU....................................................................................................................16
2.3Rezolvarea. sistemelor. de ecuații. liniare. prin .factorizare .Crout și. Choleski..........................19
2.3.1Factorizar.ea Crout..............................................................................................................20
2.3.2Rezolvarea sistemelor de ecuații liniare cu factorizarea Crout............................................22
2.3.3 Factorizarea Cholesky.........................................................................................................23
2.3.4 Rezolvarea sistemelor de ecuații liniare cu factorizarea Cholesky.....................................26
3.ECUAȚII NELINIARE.......................................................................................................................28
3.1Rezolvarea numerică a ecuațiilor neliniare.................................................................................29
3.1.1. Generalități........................................................................................................................29
3.1 2. Metoda bipartiției..............................................................................................................30
3.1.3 Metoda coardei..................................................................................................................32
3.2 Metode de partiționare.............................................................................................................34
3.2.2 Metoda bisectiei -Algoritm................................................................................................36
3.2.3 Metoda secantei...........................................................................................................37
3.3 Metode de aproximații succesive..............................................................................................40
3.3.1 Metoda contracției........................................................................................................42
3.4 Metoda Newton........................................................................................................................44
3.4.1Metoda Newton Algoritm....................................................................................................46
3.5 Metoda iterativă Seidel-Gauss..................................................................................................51
Bibliografie..........................................................................................................................................54
2
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.
3
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.
4
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
5
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
6
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
1. rezolvat (Anotată A ) sau matriceaA ce trebuie inversatăA ( A ).
2. Se alAege un element nenul al mAatricei A, numitA pivot.
3. 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
: :
7
: :
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, atun Aci coloana acelui
elemAent se copiază; analog, Adacă pe coloana pivotuluAi există un element egal c Au 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 rezolvate1. Să se reAzolve următorul sistem de ecuaţAii liniare, folosind metodAa eliminării coAmplete:
/ - +A2 -3 =A -2
< 2A -6 A+9 =A 3
\-3 A+2 A+2 =-3
RAezolvare:
Vom foloAsi următoarea sAchemăA:
AA bA
……A….. ……….
A
XA
8
-1 A 2 -3
2 -6 A9
-3 2 2
-2A
3A
-3
AA1 -2 3
0 -2 A 3
0 A-4 11
2
-1
A3
1 0 0
0 A1 -3/2
0 A0 5
3
1/2
5A
1 0 0
A0 A1 0
0 0 1
3
A2
1
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
\ 5 A+2A + = A11
RezAolvare:
4 A 1 A 1
3 A1 A0
5 2 A 1
9 A
6
11
1 A 0 A 1
3 1A 0
-1 0A 1
3
6AA
-1
1 0A 1 3
9
0 1A -3
0 0A 2
-3
2
1 0A 0
0 1AA 0
0 0A 1
2
0
1
ObAservaţie. Pentru simpAlificarea calculelor, am Aales drept pivot mai întâi ele Amentul 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ă.
1.5 Metoda iterativă JacoAbi
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ă:
10
care repArezintă formula deA iterare a metodei Jac Aobi. Inspecţia sAumară a acestei forAmule
sugereazAă imediat motiAvul pentru Acare toate elementel Ae 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 se A referă la modul cum A 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 necunoscutev se detvermină în funcţiev de apro Aximaţ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 do Ai vectori : un A 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 co Apierea în el a
Aelementelor vecAtorului y.
AlgoritmuAl 1 - Sisteme de Aecuaţii liniare - MetodAa iterativă JacAobi
1. DefinireaA sistemului de eAcuaţii: rangul n, mAatricea coeficienţiloAr A, vectorul
termenilor Aliberi b;
2. DefinirAea parametrilor de iterare: aba Aterea relativă maximăA admisă Emax şi nuAmărul
maxim dAe iteraţii NAmax;
3. Calcul Aiterativ:
i. StabAilirea aproximaţiAei iniţiale, identică cu terAmenii liberi:
ii. IniţialAizarea procesului itAerativ: It <-- 0.
11
iii. IniţAializarea abaterii relat Aive maxime în iteraţia A curenta cu o valoare s Auperioară lui Emvax :
Dx <-- Emax + 1.
iv. 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;
v. TrecAerea la o nouă iteraţie: ItA <-- It + 1.
vi. CalculuAl noii aproximaţii în veActorul y:
vii. CalAculul abaterii relativeA maxime în iteraţia Acurentă:
viii. AcAtualizarea vectorului apAroximaţiilor din ulAtima iteraţie:
ix. Se rAevine la pasul 3.iv. A
4. StabAilirea condiţiilor de ieşAire din bucla iteratiAva:
i. dacă ADx <= Emax (metodAa converge), se afişează soluţia ap Aroximativă şi
numărul deA iteraţii efectuAate It; A
ii. dacăA Dx>Emax, dAar It=Nmax (meAtoda nu converge), sAe afişează mAesajul "Depăşire nAumăr
maxim iteraţiAi";
2.METODE NUMERICE ÎN ALEGBRA LINIARĂ
12
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
13
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ă.
Sistemul Operatiile Matricea Augumentata
14
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ă.
15
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:
16
PA = LU
Unde. L șiV 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. LUV 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){
17
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
18
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.
19
2.3.1Factorizar.ea 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. DeoarecVe 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; mV=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.:
20
( 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 elemeVntelor 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
1. Defi.nirea sistemu .lui de .ecuaţii: ra .ngul n, m.atricea coeficienţi .lor A, vecto.rul
term.enilor lib.eri b.
21
2. Facto.rizarea LR a matric .ei A după m.etoda Cro.ut :
i. 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; .
ii. Determ.inarea ele .mentelor subdiago .nale, inclusiv a . elementului .diagonal de p .e
coloana .p a matric .ei L (rela.ţia I):
iii. Pivo .tarea parţial .ă pe colo.ana .p;
iv. Determ.inarea eleme .ntelor situa .te la dr .eapta diagon.alei prin.cipale , pe . linia .p a
matri.cei R (rel.aţia II ):
v. 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.
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.
4. 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
}
22
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:
23
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 preala Abil, se poate dAetermina
elementuAl diagonAal :
după Acare, se calculează Arestul elemenAtelor de pe coloana j a maAtricei L:
24
„Şi în cazulA factorizării Cholesky exist Aă posibilitateAa aplicării metodeAi descrise în forAma
compactă, pe loc în matri Acea A. Pe de altă part Ae, este posiAbilă memorarea îAntr-o singură
matrice atât a matricAei originare A, cât şi a matricei de fa Actorizare 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 a A factorizării Cholesky se A 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 în Atotdeauna nesingulara” A( (Kolman, Bernard; Hill,
David R. 2007 pag. 56). A Prin urmaAre riscul împărţirii la un A 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:
i. pivotaArea parţială stricAă simetria maVtricei;
ii. 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);
}
25
}
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
1. Definirea sAistemului de ecuaţii: rangul n, A matricea coeficieAnţilor A, vectoruVl termenilor
liberi b.
2. VerifiAcarea simetriei matricei A A. Dacă matricea nu Aeste simetrică se lanAsează un mesaj de
eroare şi se întrerAupe algoritmul;
3. AFactorizarea CholeskAy pe loc în matriceAa A:
IniţializAarea coloanei curentAe j din matricea A L pentru care se deter Amină 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:
26
D_ j <-- ;
DeterminarAea elementelor subdAiagonale de pe coloana j a mAatricei L şi meAmorarea lor în
matricea A:
Se treceA la tratarea următ Aoarei coloane diAn matricea L : j <-- jA+1. Dacă j <= n se rAevine la
pasul A3.2. Dacă j > n se Atrece la pasul A4;
4. RezolvarAea sistemului inferiorA triunghiular L * y = b pArin substituAţie înainte şi
memoraArea soluţieiA în vectoruAl b;
5. RezolvAarea sistemului supeArior triunghiulaAr * x = y = b pArin substituţie înAapoi şi
memorarea Asoluţiei în vectorAul b.
3.ECUAȚII NELINIARE
FieA ecuaţia
27
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ân Ad cont de
continuitatea funcţiei f şiA de faptul ca şirurile şi sunt conAvergente avem:
sau
28
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.1RezolvarAea numerică a ecuAaţiilor neliniAare
3.1.1. GeneraAlităţ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 valor Ai ale lui x.
Expresia f(x) poAate conţine valAori numerice operaAtori aritmeticiA şi funcţii eAlementare.
RezolvaArea analitică (peA bază de formule)es Ate 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ă
29
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 transc Aendent)
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 bAipartiţiei
„MetoAda bipartiţiei sAau a 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 face A sAchimbarea de AsemAn conţine
soluţia căutAată” (Sadun, Lorenzo, 2008, pag. 60). AÎn continuare acest i Anterval este împărţit la
rândul lui în dAouă părţi egale şi analiză c Aontinuă î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>
30
#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++; }
31
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 a A 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) şiV 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 brVuş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 a Abscisei Ox cu Vsegmentul de
dreaptă (coAardă corespunzătoarAe porţiunii de grafic) care u Aneş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 d Ae lucru şi procedeul se a Aplică î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.
32
„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 d Areapta” (Sadun, A Lorenzo, 2008, pag.
45). Deci valoareAa h este poziAtivă, iar valoarea apAroximaţiei iniţiaAle se va conAsidera x1 V= 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 parc Aursul procesului iteArativ,
iar deplasareAa aproximaţiilor se face de l Aa 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 deriv Aatelor
de ordiAnul unu şi doi. AlegereaA punctului de pornire a Al iteraţiilor şi implic Ait 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 es Ate punct
de porniAre şi coarda se găAseşte la dreAapta graficului.
Fig.1.
3.2 MetoAde de partiţionare
După încadrarea Aunei soluţii exAacte, se pot aplica o serie A de metode iterative A care permit
determinarAea unei soluţii apro Aximative în limita pre Aciziei impuse. A Dintre acAestea, metAodele
de paArtiţionare acţionează direcAt asupra intervalAului în care a fo Ast încadrată soluţia, urm Aărind
"comprAimarea" acestuia pAână la limita imApusă de criteriuAl de oprire. Din acAeastă categoArie
33
fac parAte metoda bisecti Aei, metoda s Aecantei ş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 caracterize Aază printr-un numAăr mare de Viteraţii
necAesare atingerii preciziAei impuse, deci priAn timpi de calcAul mari.
3.2.1 MetodaA bisectiei
„Metoda biAsectiei, numită Auneori şi metoda dihotomiAei sau a înjumătăţiArii intervaleloAr,
este cea mai sim Aplă dintre metodelAe de rezolvareA a ecuaţiilor aAlgebrice şi transcAendente”
(Greub, Werner H. 1981, pag. 66). Se Aconsideră ca, printr-un proce Adeu oarecare, s-a reuAşit
localizarea rădăciniAi exacte a ecuaţieiA f(x)=0 în intervAalul [ , ]. În ipAAoteza în care
functiaf(x) este coAntinuă, iar rădăciAna este singuruAl zerou al lui Af(x) în [ ,A ], la
extremităţile intervalului funcţia ia valor Ai 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 inteVrvalului ( <-- 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
34
la alta - scade sAub valoarea limită 2A* , adică - < 2A* . Dacă, în aAcest momentV, 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);
}
35
}
int main()
{
cout << getRoot(-10, 10);
system("PAUSE");
return 0;
}
3.2.2 MetodAa bisectiei -Algoritm
1. Definirea funcAţiei f(x), a inAtervaAlului de lucru A [A , ], a Apreciziei şi a nAumAărului
maxim de AiteraţAii Nmax.
2. ProcesuAl iterativ:
i. IniţializaArea procesului iteArativ: It <-- 0;
ii. Dacă s-aA atins precizia dorit Ata ( - A< 2* ) sau Anumărul maxiAm de
iterAaţii Nmax se încheie bucla iteArativă şi se trecAe la pasul 3.
iii. Se trece laA o nouă iteraţAie: It <-A- It+1;
iv. ÎnjumăAtăţirea intervaAlului curent: A m <-- ( +A )/2 ;
v. 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;
36
vi. Se revAine la paAsul 2.ii;
3. 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ă nou Aă
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 acest Aei 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:
37
În cAontinuare, dintre intervale Ale [ 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
1. DefinirAea funcţiei f(x), a iAntervalului de lvucru [ , ], a precizieiA şi a numărAului
maxim Ade iteraţii NmaAx.
2. AProcesul Aiterativ:
i. IAniţializarea procesului iteratiAv: It A<-- 0;
ii. 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.
iii. Se treAce la o nouă iteraţiAe: It <-- AIt+1;
iv. CalculuAAl noii aproximaţii:
v. 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.
3. Calculul rădăcinii aproxAimative: x <-- (A + )/2.
Codul C++:
38
#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++;
}
39
if (i>iter) cout<<"problema nu se poate rezolva in nr.maxim de iteratii";
} else cout<<"interval invalid";
}
3.3 MetodeA de aproximaţAii 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 anumit Ae condiţii, Aconverge cătrAe soluţia exactAă” (Sadun, LAorenzo, 2008,
pag. 136). De această dată nu A se mai acţionează Aasupra intervalulAui în care a foAst izolată
soluţiAa exactă. AcestA interval este fovlosit numai pventru stabilirvea aproxi Amaţ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, rez Aolvarea
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:
40
a căAreiA rezolvare presupune dAeterminareaA punActului de intersecvţie a curbelor; y=
(x) şi y=g(x). Din considerente de A 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 parti Acular al ecuaţiei e Axplicite, ş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 apro Aximaţ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 d Aeosebesc 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 MetoAda contraAcţ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ţie Ai de convergenţă. AAstfeAl, pentru ca şirul
aproxiAmaţiilor succesAive să fie convergent, er Aoarea de aproximare tArebuie să scadă înAtre
41
două iteraţii consecutive, adică |Ae_(n+1)| < |e_n|, ceea ceA conduce la A|g'( )| < 1. AcAeasta
reprezintă oA condiţie necesară, dar nu A şi suficientă pentru as Aigurarea 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 sati Asfă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 contra Actantă". (a)
Funcţia g(x) eAste o aplicaţie strict co Antractantă pe un anumAit interval dacă proiAecţia acestui
interval peA axa Oy, prin curba AAy = g(x) se contractă. (b) În caz c Aontrar, 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.
42
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
1. DefinireaA funcţiei f(x), a aAproximaţiei iniţialAe x, a preciziei AEps şi a numărAului maxim
dAe iteraţii Nmax.
2. ConstruiArea funcţiei g(x) A= x + f(x).
3. PrAocesul iterativ:
i. IniţiAalizarea procesulAui iterativ: It A<-- 0;
ii. 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.
iii. Se treAce la o nouă iterAaţie: It <-- It+A1;
iv. Calculul nAoii aproximaţii: x <-- Ag(x)
v. Se revAine la pasul A3.2.
4. StabiAlirea condiţiilor de ieşiAre din bucla iteArativă:
i. DacăA |f(x)|<Eps - proces cAonvergent - soluţia Aaproximativă esAte x.
ii. DaAcă |f(x)|>=Eps şi It=Nmax, A se afişează mesajul " ADepăşire număr maAxim
iteraţii".
3.4 MetAoda 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).
43
„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. Folosi And pe x_1 ca
aproximaţieA iniţială, se reia procedeul, determi Anându-se o nouă aproximaţie xA_2 s.a.m.d.
pânAă când abaterea între dou Aă iteraţii succesAive scade sub o valAoare prag impusAă: |x_(n+1) -
x_n| < .
„Alegerea Aaproximaţiei iniţiale infl Auenţ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 s Apre infinit. (b) Într-o Asituaţie
44
mai fericAită, procesul rămâAne convergent, dar şirul A 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 comple Axe ca formă şi se A
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 rezolv Aare a unei ecuaţii nel Ainiare pentru cAare este posiAbilă
evaluarea deArivatei f '(x). Remarcaţi totAuşi precizarea din fraAză anterioară ("În aprAopierea
soluţiAei exacte...") şi nu uitaţi A condiţiilAe de convergenţă Aatât de alambicate, care se ref Aeră 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 d Ain urmă metodAa Newton pAoate fi aplicată ca Ao
procedură tAerminală, penAtru rafinarea efAicientă şi foarte rap Aidă 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
1. 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.
2. IniţiAalizarea procesAului iteratiAv: It <-- A0;
3. ProAcesul iterativ:
i. Se trece la o nAouă iteraţie: IAt <-- It+1;
ii. CalculAul corecţiei: dx <A-- - f(x) / f '(x)
iii. CalcAulul noii apAroximaţii: x <-- x + dx
iv. 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.
v. Se rAevine la pasul A3.1.
45
4. SAtabilirea condiţiilor dAe ieşire din buAclă iteratiAvă:
i. Dacă |dAx|<Eps - proces Aconvergent - soAluţia aproximatiAvă este Ax.
ii. Dacă |Adx|>=Eps şiA It=Nmax, se afişAează mesajulA "Depăşire nuAmăr maxim
AiteraţiiA".
5. Numele "MAetoda lui NewtAon" este derivat din fa Aptul 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 aproxim Aă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ă”.
6. Metoda lui NeAwton a fost folosită deA către matematicianul ja Aponez din secoluAl
17 Seki Kōwa pentru a rezolva ecuații cu o sin Agură variabilă, deși legă Atură cu calculul
lipsea.
7. 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.
8. Î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 ace AeașAi publicație, SAimpson oferă, vde aseme Anea,
46
genAeralizarea la sistemele A de două ecuații și A constată că metoda luvi Newton poate Afi
folosit pentru rezolvarAea problemelor de optiAmizare prin setarea gradientA de la zero.
9. 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 valori Ale inițiale complexe. Ace Ast 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.:
[x(1)] = [x(0)]-[Jf x(0)]-1·[f(x(0))][x(2)] = [x(1)]-[Jf x(1)]-1·[f(x(1))][x(m)] = [x(m-1)]-[Jf x(m-1)]-1·[f(x(m-1))]
(4)
und.e, (5)
47
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)
{
48
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;
49
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;
}
3.5 MetodAa iterativă Seidel-GAauss
Ca şiA în cazul metodei Jacobi, Aapariţia termeniloAr a_ii la numitorul aAcestei expreAsii
reflectă necAesitatea ca toate elemen Atele diagonale ale Amatricei A să fieA nenule.
O compaAraţie între formulele de iter Aare 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-Ga Auss calculeazăA noile aproximaAţii folosind Aşi
aproximaţiile deterAminate deja în iterAaţia curentă (A , j=1,...,i-1 ).
50
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 aduce A un plus de vitez Aă de coAnvergenţă faţă
de metoda Jacobi. Astfel, e Aste de aşteptat ca, po Arnind de la o aceeaşi apro Aximaţie iniţială,
metoda Seidel - Gauss să aAsigure precizia impusă într-uAn număr mai mic dAe iteraţii.
Ca şi în cazul A metodei Jacobi, condiţia Ade convergenţă a metod Aei Seidel - Gau Ass 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++)
51
{
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();
}
52
Bibliografie
1. Ebâncă, D., Metode numerice, Ed. Sitech, Craiova, 1994.
2. Groza G., Analiza numerica, Ed. MatrixRom, Bucuresti, 2005.
3. Iorga, V., Jora, B., Programare numerică, Ed. Teora, 1996
4. Bretscher, Otto (June 28, 2004), Linear Algebra with Applications (3rd ed.), Prentice Hall, ISBN 978-0-13-145334-0
5. Farin, Gerald; Hansford, Dianne (December 15, 2004), Practical Linear Algebra: A Geometry Toolbox, AK Peters, ISBN 978-1-56881-234-2
6. Nicholson, W., K., Linear Algebra and with Applications, PWS Publishing Company,
Boston, 1995.
7. Kolman, Bernard; Hill, David R. (May 3, 2007), Elementary Linear Algebra with Applications (9th ed.), Prentice Hall, ISBN 978-0-13-229654-0
8. Leon, Steven J. (2006), Linear Algebra With Applications (7th ed.), Pearson Prentice Hall, ISBN 978-0-13-185785-8
9. Ricardo, Henry (2010), A Modern Introduction To Linear Algebra (1st ed.), CRC Press, ISBN 978-1-4398-0040-9
10. Sadun, Lorenzo (2008), Applied Linear Algebra: the decoupling principle (2nd ed.), AMS, ISBN 978-0-8218-4441-0
11. Hoffman, Kenneth; Kunze, Ray (April 25, 1971), Linear Algebra (2nd ed.), Prentice Hall, ISBN 978-0-13-536797-1
53