refacut

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 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];


double sum=0.;


y[i]=(b[i]-sum)/LU[i*d+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 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];


double sum=0.;


y[i]=(b[i]-sum)/LU[i*d+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

punctului 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

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

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

54

refacut

Documents

Transcript of refacut