Str. Calea Mărășești, nr. 157, Bacău, 600115 [608897]

1

c ROMÂNIA
MINISTERUL EDUCAȚIEI NAȚIONALE
UNIVERSITATEA „VASILE ALECSANDRI” DIN BACĂU
Facultatea de Științe
Str. Calea Mărășești, nr. 157, Bacău, 600115
Tel. +40 -234-542411, tel./ fax +40-234-571012
www.ub.ro ; e-mail: [anonimizat]

PROGRAMUL DE STUDII INFORMATICĂ
APLICATĂ ÎN ȘTIINȚĂ ȘI TEHNOLOGIE

LUCRARE DE DISERTA ȚIE

Coordonator științific:
Prof. univ. dr. Mihai Talmaciu Absolvent: [anonimizat]
2017

2
c
ROMÂNIA
MINISTERUL EDUCAȚIEI NAȚIONALE
UNIVERSITATEA „VASILE ALECSANDRI” DIN
BACĂU
Facultatea de Științe
Str. Calea Mărășești, nr. 157, Bacău, 600115
Tel. +40 -234-542411, tel./ fax +40-234-571012
www.ub.ro ; e-mail: [anonimizat]

PROGRAMUL DE STUDII INFORMATICĂ
APLICAT Ă ÎN ȘTIINȚĂ ȘI TEHNOLOGIE

REZOLVAREA SISTEMELOR ȘI
APLICAȚII

Coordonator științific:
Prof. univ. dr. Mihai Talmaciu Absolvent: [anonimizat]
2017

3

CUPRINS

CUPRINS ………………………….. ………………………….. ………………………….. ………………………….. … 3
ARGUMENT ………………………….. ………………………….. ………………………….. ……………………….. 4
CAPITOLUL I ………………………….. ………………………….. ………………………….. ………………………. 5
METODE DIRECTE ………………………….. ………………………….. ………………………….. ……….. 5
I 1.Metoda de eliminare a lui Gauss ………………………….. ………………………….. …………… 5
I 2. Factorizarea LU ………………………….. ………………………….. ………………………….. ……. 12
Implementare ………………………….. ………………………….. ………………………….. ……………….. 17
I.3 Factorizarea Cholesky ………………………….. ………………………….. ………………………… 19
Implementare ………………………….. ………………………….. ………………………….. ……………….. 21
I.4.Metoda rădăcinii pătrate ………………………….. ………………………….. …………………….. 22
I.5.Metoda lui Ritz de inversare a unei matrici simetrice și pozitiv definite ………… 28
CAPITOLUL II ………………………….. ………………………….. ………………………….. …………………… 35
METODE I TERATIVE ………………………….. ………………………….. ………………………….. ….. 35
II.1.Metoda lui Jacobi ………………………….. ………………………….. ………………………….. …. 36
Aplica ție. Sa se rezolve sistemul de ecuatii linia re prin metoda iterativa Jacobi .. 38
II .2. Metoda Gauss -Seidel ………………………….. ………………………….. ……………………….. 44
CAPITOLUL III ………………………….. ………………………….. ………………………….. ………………….. 52
Aplicații -Implementarea în C ++ a metodelor Gauss, Jacobi și Gauss -Siedel …………… 52
BIBLIOGRAFIE ………………………….. ………………………….. ………………………….. …………………. 69

4
ARGUMENT

Această lucrare cuprinde câteva metode numerice de rezolvare a sistemelor de ecuații
algebrice liniare cum ar fi:
 Metode directe ( Metoda lui Gauss , Metoda Radăcinii pătrate, Metoda Khaletski,
Metoda lui Ritz)
 Metode iterative ( Metoda lui Jaco bi, Metoda G auss-Seidel )
Rezolvarea sistemelor de ecuații algebrice liniare este una din temele care apar în
calculul numeric.
Metodele directe permit obținerea soluției exacte a sistemului considerat, făcând
abstracție de erorile de rotunjire, folosind un număr finit de operații. Eroarea care se introduce
prin rotunjirea calculelor devine destul de largă pentru sisteme unde ordinul n este destul de
mare.
Metodele iterative se caracterizează prin faptul că soluția sistemului considerat se
obține ca o limită a unui șir de vectori ce reprezintă soluția pentru diversele iterații efectuate.
În cadrul acestor metode se pune problema de alegere a acelei metode care e convenabilă din
punct de vedere al vitezei de convergență. Aceste metode pornesc de l a o valoare inițială
0x
pentru vectorul soluție și cu ajutorul unui algoritm de calcul iterativ se determină un șir de
aproximații succesive pentru vectorul soluție,
kx x x …,, ,2 1 , care trebuie să conveargă
către soluția exactă a sistemului. În cazul în care procedeul converge suficient de rapid
procedeul de calcul a sfârșit foarte repede și se obține o aproximație foarte bună. Unul din
avantajele principale ale metodelor iterative este faptul că eroarea de rotunjire poate fi
eliminată.

5
CAPITOLUL I
METODE DIRECTE

În acest capitol am utilizat următoarele referințe bibliografice: ( [3], [4], [10]).
Un sistem de ecuații algebrice liniare poate fi scris sub forma
in
jjij b xa
1
,
m i,…,1
unde
Rija sunt coeficienți,
jx sunt necunoscutele sistemului, iar
ib sunt termenii liberi.
Sunt posibile situațiile:
(i) dacă
nm atunci trebuie aleși n – m parametri pentru a obține o soluție;
(ii) dacă
nm atunci se caută o soluție care să minimizeze





 m
in
jjij i xa b
12
1 ;
(iii) pentru m = n, dacă
0 detA atunci sistemul are o soluție unică altfel (adică,
0 detA
) atunci sistemul poate a vea o infinitate de soluții sau poate să nu aibă nici o soluție.

I 1.Metoda de eliminare a lui Gauss

Fie un sistem de n ecuații liniare cu n necunoscute scris sub forma
b Ax , unde A este o
matrice pătrată, nesingulară, de dimensiune
nn , iar x și b sunt vectori coloană de
dimensiune n.
Metoda constă în a obține zerouri sub diagonala principală a matricii A succesiv, întâi
pe prima coloană, apoi pe coloana a doua ș.a.m.d., pe ultima linie a lui A rămânând doar
coefici entul
nna – modificat de operațiile de eliminare anterioare. Un pas (etapă) k al metodei
constă în obținerea de zerouri sub diagonala principală, în coloana k a matricei A. Etapa este
simbolizată prin indice superior atât pentru matricea A cât și pentru vectorul b. Notăm, inițial,
A A)1(
și
b b)1( .
În urma pasului
1k al fazei eliminării, sistemul are forma echivalentă
În urma pasului
1k al fazei eliminării, sistemul are forma echivalentă

6

















 



 

)1()1(
1)1()2(
2)1(
1
121
)1( )1(
1)1()1(
1)1(
11)1(
1)1( )1(
1)1()2(
2)2(
12)2(
2)2(
22)1(
1)1(
11)1(
1)1(
12)1(
11
0 00 00 00
k
nk
kk
k
nkk
k
nnk
nkk
nkk
nkk
kkk
kkk
knk
kkk
kkn k kn k k
bbbbb
xxxxx
a a aa a aa a aa a a aa a a a a


       
La pasul k (
1 …,,2,1 n k ) este eliminată necunoscuta
kx din ultimele n – k ecuații
și sistemul este adus la forma














 
)()(
1)()2(
2)1(
1
121
)( )(
1)(
1)(
11)( )(
1)()2(
2)2(
12)2(
2)2(
22)1(
1)1(
11)1(
1)1(
12)1(
11
0 0 0 00 0 0 00 00
k
nk
kk
k
nkk
k
nnk
nkk
nkk
kkk
knk
kkk
kkn k kn k k
bbbbb
xxxxx
a aa aa a aa a a aa a a a a


   

În final se obține sistemul
)( )( n nbxA
,
în care matricea
)(nA este superior triunghiulară.
Sistemul se rezolvă prin metoda substituției inverse potrivit relațiilor








. 1 …, ,1 , /)(
1)( )()()(
ni a xa b xabx
i
iin
ijji
iji
i in
nnn
n
n

Sistemul
b Ax poate fi transformat într -un sistem super ior triunghiular echivalent
(adică cu matricea sistemului triunghiulară superior) folosind rezultatele următoarei teoreme:
Teorema : Dacă
kji ijka A,1)()( ,
kk kAR)( , cu
n k …,,2,1 sunt nesingulare,
atunci există
nnTR , nesingulară și inferior triunghiulară astfel încât matricea
UAT
este superior triunghiulară.
Demonstrație . Fie
12 2 1 … TT T TTn n  un produs de matrici elementare
de forma
T
kk n k etI T , în care
nI este matricea unitate,
ke este coloana k a lui
nI , iar

7

 T
nk kk k t t t  1 0 0 , în care ultimele
kn elemente sunt neprecizate
deocamdată.
Înmulțind la stânga matricea sistemului A cu mat ricea de transformare T obținem
ATT T TATn n  12 2 1 …
,
sau exprimat printr -o secvență de transformări elementare:
1 1111 21
……


n n nk k k
A T AAT AAT AA A

în care fiecare operație anulează elementele subdiagonale din coloana k ale matricei
kA :
1
1 12 2 221 1 12 11
1
0 00 00 00
1 000 000 1 000 0 100 0 01

 









k
nn nknk kkkn kkn kn k
nkkkA
a aa aa aa a aa a a a
tt
     
     

  nk kk k k n k k k k aT aT aTaT a a aaT AT   2 1 2 1  
,
unde
ia este coloana i a matricei
kA .
k kk k kT
kk n kk t a a aetI aT  
.
Componenta i a coloanei transformate
kkaT este:

 . pentru pentru 'ki t a aki at a a a
ik kk ikikik kk ik ik

Remarcăm faptul că, în t impul transformării, primele k componente nu se modifică,
fiind afectate numai elementele subdiagonale.
Din condiția de anulare a acestora urmează
kkik
ikaat
, pentru
n ki …,,1 ,
determinându -se vectorul
kt , deci și matricea
kT .
Coloanele
ja (
kj ) se vor modifica astfel:
kkj j jT
kk n jk ta a aetI aT  
,
iar pe componente:

8

kkik
kj ij ikkj ij iaaa a ta a a ',
n kj …,,1 ,
n ki …,,1 .
Coloanele
ja (
kj ) au elementele subdiagonale deja anulate (
0kja pentru
kj )
astfel că transformarea le lasă nemodificate:
j jk a aT
.
Metoda de triangularizare și substituția inversă c onduc la un
)(3nO – algoritm.
Algoritmul :
Intrări : n = dimensiunea sistemului
A = matricea sistemului
b = vectorul termenilor liberi
Ieșiri : A = matricea sistemului triunghiular
b = termenii liberi ai sistemului triunghi ular
x = vectorul necunoscutelor
{
pentru
1:1 n k
pentru
n ki :1
{

kk ikaat /

nkk nki nki at a a :, :, :, 

k i i btb b 
}
pentru
1:ni
{
suma
 +
ni nii x a :1 :1, 

i i b x ( – suma) /
iia
}
}.

În implementarea algoritmului eliminării gaussiene, la fiecare pas k al eliminării se
efectuează împărțirea liniei pivot k la elementul diagonal
kka . În practică, este posibil ca
acest element să fie egal cu zero, situație în care este i mposibilă continuarea algoritmului.

9
Erorile de rotunjire în calculul elementelor matricii
)(kA sunt cu atât mai mici cu cât
elementul pivot
kka este mai mare în valoare absolutǎ. Astfel, se efectueazǎ pivotarea
parțialǎ pe coloane, ceea ce pentru pasul k al eliminării revine la a găsi elementul maxim al
matricei
)1(kA situat pe coloana k și liniile
ki , adică
|| max||iknikk a a
 și permută între
ele liniile
 și k. Permutarea a două linii sau coloane dintr -o matrice se poate face prin
înmulțirea cu o matrice de permutare care diferă de matricea unitate prin:
0kka a ,
1 k ka a
. Astfel înmulțirea:
APA k' are ca efect perm utarea liniilor
 și k din matricea
A, în timp ce:
kAAA" , produce permutarea coloanelor k și
.
Căutarea elementului maxim în valoare absolută în submatricea delimitată de ultimele
1kn
linii și coloane duce la performanțe mai bune de stabilitate numerică. Astfel se
efectuează pivotarea totală.
Aplicație . Să se rezolve cu ajutorul metodei lui Gauss sistemul :

35,8 99,6 69,1 65,3 21,245,15 28,2 04,8 21,7 77,321,12 46,2 78,7 45,8 92,365,10 9,1 1,4 62,2 3,8
4 3 2 14 3 2 14 3 2 14 3 2 1

x x x xx x x xx x x xx x x x
Rezolvare:
Matricea A și vectorul termenilor liberi b este:







99,6 69,1 65,321,228,2 04,821,7 77,346,2 78,7 45,8 92,39,1 1,4 62,23,8
0A ,







35,845,151210
0b
Calculând, constatăm că det A
 0. Deoarece
3,8)0(
11 a este elementul în modul maxim
din prima coloana a matricei A, nu este necesară o permutare a ecațiilor sistemului.
Regulile algoritmului indicat de metoda lui Gauss sunt:
-împărțim prima ecuație din sistem cu
3,80
11a :
204819,1 228916,0 493976,0 315663,04 3 2 1     x x x x
(*)
-ecuația (*) înmulțit ă cu
92,3)0(
12 a o scădem din ecuația a doua a sistemului:
722892,16 562651,1 843614,5 212602,74 3 2    x x x

10
-ecuația (*) înmulțită cu
77,3)0(
13 a o scădem din ecuația a treia a sistemului:
992169,19 416988,1 177711,6 019952,64 3 2    x x x

-ecuația (*) înmulțită cu
21,2)0(
14 a o scădem din ecuația a treia a sistemului:
687349,5 484096,6 598313,0 952386,24 3 2    x x x

Se obține sistemul echivalent cu matricea coeficienților și vectorul termenilor liberi
1c
:






484096,6 598313,0 952386,20416988,1 177711,6 019952,60562651,1 843614,5 212602,70228916,0 493976,0 315663,01
1A
și







687349,5992169,19722892,16204819,1
1c
Pentru sistemul cu ma tricea coeficienților




484096,6 598313,0 952386,2416988,1 177711,6 019952,6562651,1 843614,5 212602,7
și vectorul termenilor liberi




687349,5992169,19722892,16 .
observăm că elementul
212602,71
22a este în modul maxim pe coloana lui și deci nu este
necesară o permutare a ecuațiilor din acest sistem.
Procedând ca mai sus,obținem sistemul cu matricea coeficienților
2A și
vectorul termenilor liberi
2c .






844446,5 793695,1 0 0112732,0 300376,1 0 0216656,0 810195,0 1 0228916,0 493976,0 315663,01
2A
,







532649,12034516,6318566,2204819,1
2c ,
adăugând prima ecuație de la pasul an terior care nu se mai modifică.
În continuare, observăm că
300376,12
33a nu este elementul în modul maxim pe coloana
lui și de aceea vom schimba ultimele două ecuații între ele






112732,0 300376,1 0 0844446,5 793695,1 0 0216656,0 810195,0 1 0228916,0 493976,0 315663,01
2A
,







034516,6532649,12318566,2204819,1
2c
iar apoi aplicăm rețeta cunoscu tă și obținem:
1A

11







349783,4 0 0 0258328,3 1 0 0216656,0 810195,0 1 0228916,0 493976,0 315663,01
3A ,







051286,3987058,6318566,2204819,1
3c .
Analog se obține






1 0 0 0258328,3 1 0 0216656,0 810195,0 1 0228916,0 493976,0 315663,01
4A
,







70148,0987058,6318566,2204819,1
4c .
Rezolvând sistemul
4 4cx A , adică

   
  
 
70148,0987058,6 258328,3318566,2 216656,0 810195,0204819,1 228916,0 493976,0 315663,0
4
43
43
32
42
32
21
41
31
21
1
      
xx xx x xx x x x

începând cu ultima ecuație găsim

944103,2 )) 70148,0( 228916,0701406,4 493976,0) 33851,1( 315663,0( 204819,1(33851,1 )) 70148,0( 216656,0 701406,4 810195,0( 318566,2) (701406,4)) 70148,0( 258328,3( 987058,670148,0
4 41 3 31 2 21 1 14 42 3 32 2 243
43 3 34 4
               
xaxa xa c xxaxa c xx ac xc x

Se obține soluția:






70148,0701406,433851,1944103,2
x
.

12
I 2. Factorizarea LU

În acest capitol am utilizat următoarele referințe bibliografice: ( [3], [9], [10]).
Fiind dată matricea
)(ija A ,
n ji …,,2,1, a unui sistem nesingular ne propunem să
descompunem această matrice în produsul matricei inferior triunghiulare L cu matricea
superior triunghiulară U:










nnnnn
nn n n nu uu u uu u u u
A

  
0 0 00 00
00 00 0 0
3 332 23 221 13 12 11
3 2 133 32 3122 2111
.
Motivul acestei descompuneri constă în transformarea sistemului dat
b Ax în două
sisteme liniare:
b Ly și
y Ux a căror matrici sunt triunghiulare și deci rezolvarea lor este
ușoară. Relația ce leagă elementele celor trei matrici poate fi scrisă
ijji
kkjik a u 
), min(
1 ,
n ji …,,2,1,
.
Sunt posibile mai multe factorizări LU. Matricele L și U au în total
)1(nn elemente
nenule, în timp ce
LUA ne furnizează
2n relații. Este necesară particularizarea, de
exemplu, a ele mentelor diagonale a uneia din matricile L sau U. Dacă se consideră elementele
diagonale ale matricii U unitare se obține factorizarea Crout, în timp ce dacă elementele
diagonale ale lui L sunt unitare se obține factorizarea Doolittle.
Considerăm, întâi,
n iii ,…,2,1,1 . Atunci
11 11a u .
Pentru
1i ,
1j avem
n ja u a u j j j j …,,2,1,1 1 1 111  .
Pentru
1i ,
1j avem
n iuaa ui
i i i …,,2,1,
111
1 1 111   .
La pasul k (
nk1 ) avem
ki
,
kj ,
 kj kjkk j k j k a u u u   … 22 11

n kju a uk
ssjks kj kj …,, ,1
1 
 .
ki
,
kj ,
ik kkik k i ki a u u u   …22 11

n ki u auk
sskis ik
kkik …,,1 ,1 1
1


 
  .
Fie, acum
1iiu ,
n i …,,2,1 .

13
Pentru
1j ,
1i avem
n ia a ui i i i …,,2,1,1 1 1 111  

Pentru
1i ,
1j avem
n j a u a u j j j j …,,2,1,/11 1 1 1 111    
.
La pasul k (
nk1 ) avem
ki
,…,n,
kj :
ik kkik k i ki a u u u   …22 11


1
1k
sskis ik ik u a 
.
ki
,
n kj ,…,1 :
 kj kjkk j k j k a u u u   … 22 11




 
1
11 k
ssjks kj
kkkj u a u 

Factorizarea Crout conduce la următorul
)(3nO – algoritm.
Algoritmul
Intrări : n = dimensiunea matricii
A = matricea de factorizat
Ieșiri : L, U (folosesc același spațiu de memorie ca A)
{
pentru
n k :1
{
pentru
nki :
{

kk ki a as1:1 1:1 

s a aik ik
}
pentru
n kj :1
{

jk kk a as 1:1 1:1  

kk kj kj as a a /) (

14
}
}
}.

Din teorema are loc următor ul rezultat:
Teorema :Dacă toate submatricele principale
)(kA ale unei matrici A nesingulare de
ordinul n sunt nesingulare atunci există o factorizare LU, unde L este triunghiulară inferior și
U este superior triunghiulară.
Aplicație .Sa se determine solutia sistemului urmator, folosind factorizarea LU:

Sistemul se scrie in forma matriceala:
Ax = b ,
unde
, ,
Deoarece

rezult ă că matricea A este nesingular ă și are to ți determinan ții de col ț nenuli, dec i se poate
folosi factorizarea LU pentru rezolvarea acestui sistem.

Rezolvare folosind factorizarea Crout

A. Factorizarea Crout
Presupunem c ă
,

15
și ne propunem s ă determin ăm coeficien ții lij, ujk. Pentru aceasta, folosim defini ția înmul țirii
matricel or. Astfel, avem:
a11 = λ 11· 1 λ11 = 1
a12 = λ 11· µ12 µ12 = 1
a13 = λ 11· µ13 µ13 = −1
a21 = λ 21· 1 λ21 = 2
a22 = λ 21· µ12 + λ 22 · 1 λ22 = −3
a23 = λ 21 · µ13 + λ 22 · µ23 µ23 = −1
a31 = λ 31· 1 λ31 = 1
a32 = λ 31 · µ12 + λ 32 · 1 λ32 = 2
a33= λ 31· µ13 + λ 32 · µ23 + λ 33 · 1 λ33 = 1
sau

B. Rezolvarea sistemelor triunghiulare
Pentru rezolvarea sistemului ini țial, avem de rezolvat dou ă sisteme triunghiulare:

a cărui soluție este
,
și respectiv:
,
a cărui soluție este
.

16
Rezolvare folosind factorizarea Doolittle
A. Factor izarea Doolittle
Presupunem c ă

și ne propunem s ă determin ăm coeficientii lij, µjk, la fel ca și în exemplul
precedent. Astfel avem:
a11 = 1 · µ 11 µ11 = 1
a12 = 1 · µ 12 µ12 = 1
a13 = 1 · µ 13 µ13 = −1
a21 = λ 21· µ11 λ21 = 2
a22 = λ 21· µ12 + 1 · µ 22 µ22 = −3
a23 = λ 21· µ13 + 1 · µ 23 µ23 = 3
a31 = λ 31· µ11 λ31 = 1
a32 = λ 31· µ12 + λ 32 · µ22 λ32 =
a33 = λ 31· µ13 + λ 32 · µ23 + 1 · µ 33 µ33 = 1
sau
.

B. Rezolvarea sistemelor triunghiulare
Pentru rezolvarea sistemului ini țial, avem de rezolvat dou ă sisteme triunghiulare:
,
a cărui soluție este

17
,
și respectiv:
,
a cărui soluție este

.
Implementare
A. Algoritm
Date de intrare: un sistem de ecuații.
Date de ie șire: soluția sistemului
Algoritmul const ă din următoarele etape:
1. generarea matricei A a sistemului, și a vectorului coloana b
• n = num ărul de linii ale matricei A (numarul de ecua ții ale sistemului)
2. a) factorizarea Crout
pentru i =
µii = 1
pentru i =
pentru j =

pentru j =

18
b) factorizarea Doolittle
pentru i =
λii = 1
pentru i =
pentru j =

pentru j =

3. Rezolvarea celor două sisteme triunghiulare

pentru i =

pentru i =

19
I.3 Factorizarea Cholesky

În acest capitol am utilizat următoarele referințe bibliografice: ( [3], [7], [10]).
Fie A o matrice simetrică și pozitiv definită (adică
0
11 
n
in
jjiijxxa pentru orice
0x
). Deoarece factorizarea LU strică simetria matricii A, factorizarea Cholesky menține
simetria matricii A, având și avantajul unui timp de execuție mai mic pe calculator. Această
factorizare constă în descompunerea lui A sub forma
TLLA , unde L este o matrice inferior
triunghiulară, ceea ce revine la
ijji
kjkik a 
), min(
1
,
n ji …,,2,1, .
La primul pas avem
11 11 112
11 a a   .
Pentru
1i ,
1j avem
111
1 1 111 i
i i iaa .
La pasul k (
nk2 ) avem
kji ,
kk kk k ka2 2
22
1… 


1
12k
sks kk kk a  
.

Pentru
ki ,
kj :
ik kkik k i ki a  …22 11
n ki ak
sksis ik
kkik …,,1 ,1 1
1


 

.

Aplicație . Sa se rezolve sistemul:

Rezolvare
A. Factorizarea Cholesky
Matricea sistemului este

20
Se observa ca aij = a ji, adica matricea A este simetrica. Deoarece
1 > 0, , ,

matricea A este pozitiv definit ă. Aplicand factorizarea Cholesky ave m:
.

Folosind defini ția produsului a dou ă matrice, ob ținem:

Se observ ă că pentru g ăsirea elementelor λij , i = , j = , este suficient s ă
calcul ăm dezvolt ările corespunz ătoare elementelor aij , i = , j= .
B. Rezolvarea sistemelor triunghiulare
Pentru a determina solu ția sistemului ini țial, avem de rezolvat dou ă sistem e
triunghiulare:
,
cu soluția

21

și
,
cu soluția
.

Implementare
A. Algoritm
Date de intrare : un sistem de ecua ții
Date de ie șire: solu ția sistemului
Algoritm
1. generarea matricei A a sistemului (simetric ă și pozitiv definit ă) și a vectorului b
• n = numărul de ecua ții ale sistemului (num ărul de linii ale matricei A)
2. factorizarea Cholesky
λ11 = a11
pentru i =
pentru j =
,
3. rezolvarea sistemelor triunghiulare

pentru i =

22
,
pentru i =
.

I.4.Metoda rădăcinii pătrate

În acest capitol am utilizat următoarele referințe bibliografice: ( [3], [7], [9]).
Cu notațiile și definițiile din capitolul precedent matricea simetrică
jijiaA este
strict pozitivă( sau p ozitiv definită) dacă
0 , xxA deci dacă

0 0
, x xxa ijn
jiji
Teoremă . Matricea A este simetrică și strict pozitivă dacă și numai dacă
există matricea nesingulară subdiagonală
B astfel încât
*BBA .
Demonstrație . Dacă
*BBA , unde B este nesingulară, atunci
A este
evident simetrică. Avem
0 , , ,2
2* * * *    xB xBxB xxBB xxA pentru,
0x
căci
*B este de asemenea nesingulară.
Afirmația reciprocă o vom demonstra prin inducție după dimensiunea spațiului.
Pentru n=1,
a A ,
a , din ipoteză,
0x ,
0 , xxA adică
02xa , de
unde
0a . Vom lua atunci
 La B ) ( și deci
)() (*a aa BBA  .
Să presupunem afirmația adevărată pentru n -1 și fie
n jijia A,…,1 , o
matrice simetrică și strict pozit ivă. Scriem






nna AA A
A
1221 11
unde

23

 




  

n nn
nn nn jiji
aa
A a a A a A
11
21 1 1 121 ,…,1 ,11 , …,, , .
Deoarece
A este simetrică, rezultă că
11A este simetrică. Tot de aici
rezultă că
 n n na a A1 1 12 …,,  . Vom folosi în continuare notațiile:







nn

 1
*
1…,, ,







n
n

,…,1*
1
 .
Fie
 0, ,…,1 1  x x x xn și
 0, ,…,1 1~
 nx x x . Avem

0 , ,11~~
 xxA xxA
și deci
11A este strict pozitivă. Conform ipotezei,
11B o matrice nesingulară,
subdiagonală, astfel încât
*
11 11 11 BB A . Vom arăta că descompune rea căutată
*BBA se
poate realiza cu o matrice B de forma






b BB
B
1211 0
unde
0=
1 1
1211,
00
  




n nB  și
b .
Trebuie deci să avem



















nna AA A
b BB BBBB BB
bB B
b BB
12*
12 11
2 *
12 12*
11 12*
12 11*
11 11
**
12*
11
1211
00
și deci

*
11 12 12*
11 11 11
BB ABB A


2 *
12 12 b BB ann 
Este deci suficient să luăm

24


*
12 1221*
11 12 12
BB a bB A B
nn
de unde

 
*
12*
11 12*
121*
11 11 12*
121
111*
11 12*
12*1*
111*
11 122
AAA a A BB A aAB B A a A B B A a b
nn nnnn nn
  
  
Răm âne să arătăm că

0*
121
11 12  AAA ann
și atunci

*
121
11 12 AAA a bnn
Fie pentru aceasta

1*
121
11
1






nAA
y




















 
nn nn nn a AAA a AAAA A A
a AA A
yA
*
121
11 12*
121
11 12*
12*
121
11
12*
12 11 0
1

unde
11
00
0




n . Avem atunci

0 ,*
121
11 12  AAA a yyAnn
ceea ce încheie demonstrația.
Din demonstrație reținem că
n i,…,1 putem alege
0iib .
Teorema precedentă co nstituie fundamentul teoretic pentru metoda
rădăcinii pătrate, folosită pentru rezolvarea unor sisteme de forma
bxA , unde
A este o
matrice simetrică și strict pozitivă. În această metodă, după descompunerea
*BBA cu
B
nesingulară, subdiagonală, sistemul este echivalent cu

bBxB1 * 
sistem a cărui rezolvare este simplă deoarece
*B este o matrice nesingulară
supradiagonală.

25
Vom prezenta în continuare formulele prin care se ajunge la rezolvarea sistemului
(2.6.) precum și cele ce realizează rezolvarea acestui ultim sistem.
Dacă
n jijib B,…,1 , , deoarece pentru
ji avem
0jib rezultă că


kjji
kki ji bb a
, min
1
de unde obținem succesiv

n ibaba b
i
i ,…,2 ,
111
111 11

Pentru trecerea de la coloana
1i la coloana
i scriem pentru început

21
12
1 
  i
kki iikii
kki ii b b bb a
Rezultă de aici

21
1
i
kki ii ii b a b
Continuăm cu determinarea celorlalte elemente de pe coloana
i .
Tot din (2.6.), pentru
ij :

ii ijkii
kkjkii
kkj ij bb bb bb a   
 1
1 1
și deci

nji bb abb kii
kkj ij
iiij 

 
1
11
Pentru rezolvarea sistemului (2.6.), notând
 bB c ccn1
1,…,  avem
bcB
de unde deducem:

n ibcb b
cbbc
iii
kk ki i
i ,…,21
1111
1




Analog se rezolvă apoi sistemul
cxB* :

26

ni xb cbxbcx
kn
ikiki
iiinnn
n




11

Aplicație . Să se rezolve cu ajutorul metodei radăcinii pătrate sistemul

9,0 22,0 44,0 66,07,0 22,0 32,0 54,05,0 44,0 32,0 42,03,0 66,0 54,0 42,0
4 3 2 14 3 2 14 3 2 14 3 2 1

x x x xx x x xx x x xx x x x
Rezolvare. Matri cea A și vectorul termenilor liberi sunt






1 22,0 44,0 66,022,0 1 32,0 54,044,0 32,0 1 42,066,0 54,0 42,0 1
A și





9,07,05,03,0
b
Matricea A este simetrică. Pentru a verifica dacă A este pozitiv definită va trebui să
găsim toți determinanții principali ai matricei A strict pozitivi:
,0 574752,0
1 32,0 54,032,0 1 42,054,0 42,0 1
,0 8236,01 42,042,0 1,011    

0 286152,0
1 44,0 44,0 66,022,0 1 32,0 54,044,0 32,0 1 42,066,0 54,0 42,0 1
 
.

Deci A este pozitiv definită.
Există deci o descompunere a matricei A în produsul
*BB , unde
B este
o matrice subdiagonală.
Conform formulelor de mai sus avem

27

,66,0166,0,54,0154,0,42,0142,0,1
1114
141113
131112
1211 11

babbabbaba b
elemente ce reprezintă prima coloană din matricea
B .
În continuare obținem elementele coloanei a doua din matricea
B :

, 907524,0 8236,0 1764,012
12 22 22   b a b

102697,0907524,042,054,032,0
221213 23
23 bbb ab

. 179389,0907524,042,066,0 44,0
2212 14 24
24 bbb ab
Analog obținem

. 7056,0, 185333,0, 835376,0
443433

bbb
Rezolvăm sistemul
bcB , unde






7056,0 185333,0 179389,0 66,00 835376,0 102697,0 54,00 0 907524,0 42,00 0 0 1
B ,
și obținem :
. 04598,17056,0) 593358,0 185333,0 41211,0 179389,03,066,0(9,0) (, 593358,0835376,0) 41211,0 102697,03,054,0(7,0) (, 41211,0907524,03,042,05,0,3,013,0
443 34 2 24 1 14 4
433223 1 13 3
322112 2
2111
1
   
bcbcbcb bcbcbcb bcbcbbcbbc

28
Cu vectorul






04598,1593358,041211,03,0
c
se va rezolva sistemul
cxB* , unde






7056,0 0 0 0185333,0 835376,0 0 0179389,0 102697,0 907524,0066,0 54,0 42,0 1
*B
astfel:
03917,1) 48239,1 185333,0 593358,0(835376,01) (148239,17056,004598,1
4 34 3
333444
4
   
xbcbxbcx

0434873,0)) 48239,1 179389,0 03917,1 102697,0( 41211,0(907524,01)) ( (1
424 323 2
222
      xbxb cbx

25779,1 )) 48239,166,0 03917,154,0 0434873,042,0(3,0(11)) ( (1
4 14 3 13 2 12 1
111
    xbxb xb cbx

Vect orul soluție este:





48239,103917,10434837,025779,1
x
.

I.5.Metoda lui Ritz de inversare a unei matrici simetrice și pozitiv definite

În acest capitol am utilizat următoarele referințe bibliografice: ( [5], [7], [10]).
Propoziția 1. Fie
A simetrică, pozitiv definită și
mx x…,,1
A
-ortogonali și nenuli. Fie
m m
kH : ,

29

m kxxAxxHk
i i ii i
k ,…,1 ,, 1*


Amintim că
 yx yxj j ,* și că
vu, sunt
A ortogonali dacă
0 , vuA .
Atunci
m j x xAHj j k ,…,1 , și
1A Hm .
Demonstrație . Fie
k j …,,1 ,

k
i i ij ii
j kxxAxAxxxAH
1*
,
jk
i i ij i ixxxAxAxx 
1 ,, .
Pentru
mk avem
j j m x xAH , de unde rezultă că
j m xIAH 0,
m j …,,1 .
Deoarece
mx x…,,1 sunt
A ortogonali și nuli formează bază. Din ultimele două relații
rezultă
IAHm 0 ceea ce este echivalent cu
1A Hm .
Propoziția 2( Algoritm pentru
1A ). Fie
, …,,1 my y
mx x…,,1
și
mH HH …,,,1 0 astfel în câ
0H 0. Pentru
m k ,…,1 se alege
ky
astfel î ncât
  k k k yA H y1 0 și
k k k k yA H y x1 . Fie
m kxxAxxH H
k kk k
k k …,,1 ,,*
1 
. Atunci
1A Hm .
Demonstrație . Pentru
1k vom alege
my1 astfel încât
1y 0 și
1 1y x . Să
presupunem că am construit
, …,,, …,,1 1 1 1   k k x x y y
 1 1…,,kH H
astfel încât
1 1…,,kx x să fie
A ortogonali și nenul i. Se poate
construi
1kH și fie ca în enunț
ky astfel încât
  k k k yA H y1 0 și
k k k k yA H y x1 ,

k kk k
k kxxAxxH H,*
1
.
atunci

 k
i i iii
kxxAxxH
1*
,
.
Vom arăta că
kx x…,,1 sunt
A ortogonali. Arătăm doar că
0 ,k jxxA pentru
1 …,,1 k j
. Deci
k jxxA,
     k j k k j k j k k k j yxA yA HxA yxA yA H yxA , , , ,1 1

30

0 , , ,1   k j k j k j k yAx yxA yAxA H. Rezultă că
kx x…,,1 sunt
A
ortogonali. Atunci
mx x…,,1 sunt
A ortogonali, nenuli și deci
1A Hm .

Aplicație . Folosind metoda lui Ritz să se inverseze următoarea matrice






501 1 11 501 11 1 5021 1 2 50
A .
Rezolvare . Observăm că matricea
A este simetrică și ne rămâne de arătat că este pozitiv
definită, adică toți determinanții principali ai matricei
A trebuie să fie strict pozitivi:
,0 24965022 50,0 50  

.10 22771,6
501 1 11 501 11 1 5021 1 2 50
,0 124704
501 11 5021 2 50
6


Deci
A pozitiv definită.
Se aleg vectorii coloană
4 3 2 1 ,,, yyyy formați din coloanele lui
A :





11250
1y
,





11502
2y ,





15011
3y ,





50111
4y .

Fie





0000000000000000
0H .

Fie





11250
1y astfel încât

31

 kyAHy0 10. Observăm că
 1 0 1 y yAHyk 0 deci algoritmul poate
continua și vom calcula
1x
 1 0 1 y yAHyk




11250 . Atunci

1 1*
11
0 1,xxAxxH H ,
unde
*
11xx
 









1 1 2 501 1 2 502 2 4 10050 50 100 2500
112 50
11250 ,

1xA






501 1 11 501 11 1 5021 1 2 50




11250
=




1011012022506 ,
1 1,xxA





1011012022506




11250
125906
,





000008,0 000008,0 000016,0 000397,0000008,0 000008,0 000016,0 000397,0000016,0 000016,0 000032,0 000794,0000397,0 000397,0 000794,0 019856,0
,1 1*
11
xxAxx
. Deci
1H




000008,0 000008,0 000016,0 000397,0000008,0 000008,0 000016,0 000397,0000016,0 000016,0 000032,0 000794,0000397,0 000397,0 000794,0 019856,0
.
Fie





11502
2y . Verificăm dacă algoritmul poate continua, adică dacă
 2 1 2 yAH y
0. Făcând calculele obținem





000802,0 000802,0 001604,0 019904,0000802,0 000802,0 001604,0 019904,0001604,0 001604,0 003209,0 039807,0040109,0 040109,0 080219,0 995187,0
1AH
,





121630,0121630,0243261,0081521,6
2 1yAH și

32
deci





 
878370,0878370,0756739,49081521,4
2 1 2 yAH y 0.
Luăm




 
878370,0878370,0756739,49081521,4
2 1 2 2 yAH y x
și

2 2*
2 2
1 2,xxAxxH H , unde




  

771533,0 771533,0 704806,43 585084,3771533,0 771533,0 704806,43 585084,3704806,43 704806,43 733091, 2475 083182,203585084,3 585084,3 083182,203 658815,16
*
2 2xx
,





715327,88715327,88430655, 2481805839,102
2xA
,
351707, 124043 ,2 2 xxA ,
2 2*
2 2
,xxAxx




  
000006,0 000006,0 000352,0 000029,0000006,0 000006,0 000352,0 000029,0000352,0 000352,0 019959,0 001637,0000029,0 000029,0 001637,0 000134,0
.
Obținem






000014,0 000014,0 000368,0 000368,0000014,0 000014,0 000368,0 000368,0000368,0 000368,0 019990,0 000843,0000368,0 000368,0 000843,0 019990,0
2H
.
Fie





15011
3y , verificăm
 3 2 3 yAHy 0 și găsim






001430,0 001430,0 019176,0 019176,0001430,0 001430,0 019176,0 019176,0037190,0 037190,0 998570,0 001430,0037190,0 037190,0 001430,0 998570,0
2AH
,





108441,0108441,0819459,2819459,2
3 2yAH ,

33
deci






 
108441,1891559,49819459,1819459,1
3 2 3 yAH y 0 rezultă, algoritmul poate continua și luăm
3x





 
108441,1891559,49819459,1819459,1
3 2 3 yAH y
și

3 3*
3 3
2 3,xxAxxH H , unde




  

228641,1 301836,55 016762,2 016762,2301836,55 167686, 2489 775647,90 775647,90016762,2 775647,90 310431,3 310431,3016762,2 775647,90 310431,3 310431,3
*
3 3xx
,






952514,108047486, 2492828749,45828749,45
3xA
,
3 3,xxA
669324, 124619 ,




  

000010,0 000444,0 000016,0 000016,0000444,0 019974,0 000728,0 000728,0000016,0 000728,0 000027,0 000027,0000016,0 000728,0 000027,0 000027,0
,3 3*
3 3
xxAxx
. Deci




    

000024,0 000430,0 000430,0 000384,0000430,0 019988,0 000360,0 000360,0000384,0 000360,0 020017,0 000816,0000384,0 000360,0 000816,0 020017,0
3H
.
Fie





50111
4y . Verificăm condiția
 4 3 4 yAH y 0. Calculăm
și obținem






002399,0 020735,0 019583,0 019583,0042189,0 999123,0 000828,0 000828,0038781,0 000806,0 999239,0 000761,0038781,0 000808,0 000761,0 999239,0
3AH ,

34






179876,0106907,3936717,2936717,2
4 3yAH. Deci condiția este îndeplinită și luăm





 
820124,49106907,2936717,1936717,1
4 3 4 4 yAH y x
iar

4 4*
4 4
3 4,xxAxxH H , unde




    

044744, 2482 966384,104 487490,96 487490,96966384,104 439058,4 080484,4 080484,4487490,96 080484,4 750873,3 750873,3487490,96 080484,4 750873,3 750873,3
*
4 4xx
,






025853, 2485651808,51782263,48782263,48
4xA
,
076293, 124102 ,4 4 xxA ,




    

044744, 2482 966384,104 000777,0 000777,0966384,104 000036,0 000033,0 000033,0487490,96 000033,0 000030,0 000030,0487490,96 000033,0 000030,0 000030,0
,4 4*
4 4
xxAxx
. Obținem




      

020024,0 000416,0 000393,0 000393,0000416,0 020024,0 000393,0 000393,0000393,0 000393,0 020047,0 000786,0000393,0 000393,0 000786,0 020047,0
4H
și
1A




      
020024,0 000416,0 000393,0 000393,0000416,0 020024,0 000393,0 000393,0000393,0 000393,0 020047,0 000786,0000393,0 000393,0 000786,0 020047,0
.

35
CAPITOLUL I I
METODE I TERATIVE
În acest capitol am utilizat următoarele referințe bibliografice: ( [9], [10], [11]).
Numărul de operații pentru metodele directe de rezolvare a sistemelor algebrice liniare
este
)(3nO (n fiind numărul de ecuații și necunoscute), î n timp de metodele iterative pot
conduce la un număr mai mic de operații.
Principiul general de rezolvare este similar cu cel de la rezolvarea ecuației
0)(xf , în
care ecuația este scrisă sun forma
)(xgx
,
conducând la pr ocesul iterativ
)(1 k k xg x
.
Fie
nji ij n aA MA   ,1)( ),(R și
,nbR
niibb1)( .
Pentru rezolvarea sistemului algebric de ecuații liniare
b Ax considerăm clasa de
metode iterative
b Aupu uBkk k
1
,
unde
)(RnMA și
k R sunt parametrii care definesc metoda iterativă.
Pornind de la un element arbitrar
0u se construiește un șir
Nkku)( unde fiecare
element reprezintă o aproximație a soluției sistemului
b Ax , dacă această soluție există.
Aceasta constituie o metodǎ iterativǎ de rezolvare a sistemului algebric.
Ne interesează condițiile în care șirul de aproximații
Nkku)( converge către soluția
sistem ului.
Pentru matricea A introducem notațiile:





 
nnaa
A diagD

00
)(11
,






 00 0 00 0 0 0
1 2 121 inf
nn n n a a aaA

,

36





 
0 0 0 0 00 00
2 12 231 11 12 12
sup

n nn n
a a aa a a a
A

II.1.Metoda lui Jacobi

În acest capitol am utilizat următoarele referințe bibliografice: ( [9], [10], [11]).
Se consideră un sist em de n ecuații cu n necunoscute de forma:





n n nn 22n 11n2 nn2 2 22 1211 nn1 2 12 111
b xa… xa xa………. ………. ………. ………. ……….b xa… xa xab xa… xa xa
.

Se consideră sistemul de ecuații dat, pentru care avem îndeplinită condiția:
n,1i,0 aii
.
Rezolvarea sistemului prin metoda Jacobi începe prin a pune în evidență în partea
stângă a semnului egal a necunoscutei
ix din ecuația i:

 
 
  



 nn 1n1n,n 22n 11n n n22 nn2 323 121 2 211 nn1 2 12 1 1
a x a… xaxa b x.. ………. ………. ……….axa…xaxa b xaxa… xab x
.
Pentru ușurința scrierii se trece la forma matriceală, notând:
















nnn222111
n21
nn2n
nn1n22n2
222111n1
1112
ababab
u;
xxx
x;
0aa
aaaa0aaaa
aa0
A

 .
Sistemul se scrie sub forma:
u Axx
.

37
Metoda Jacobi constă în faptul că pune acest sistem într -o formă ce permite calculul
iterativ:

u Ax x)k( )1k(
pornind de la o aproximație inițială x(0) a soluției sistemului.

În practică, este mai utilă scrierea relației de recurență referitoare la componente:

,….1,0k,n,1i, xa ba1xn
ij1j)k(
jij i
ii)1k(
i






Pentru stabilirea condițiilor în care algoritmul metodei Jacobi converge, se dau valori
lui k în relația de calcul iterativ:

u)IA… A( xA x….. ………. ……….u)IA( xAu Ax xu Ax x
1k )0(k )k()0(2 )1( )2()0( )1(

 .
Se poate demonstra că dacă toate valorile proprii ale matricei A sunt mai mici decât
unitatea, în modul, seria matriceală este convergentă și are suma:

1 k 2)AI(… A… AAI .
Condiția de convergență a metodei Jacobi cere ca:

0 Alimk
k
 .
Dacă această condiție este îndeplinită, notând

)k(
kxlimx

se poate scrie:

u)AI(0x1
adică, după înmulțirea la stânga cu (I -A),

u Axx .
Rezultă că vectorul x obținut reprezintă chiar soluția sistemului.
Dar, condiția ca toate valorile proprii ale matricei A să fie mai mici decât unitatea în
modul, cere ca:

38

n,1i,1aan
ij1j iiij
 .

Această relație reprezintă pentru metoda iterativă Jacobi o condiție necesară de
convergență.
În matricea sistemului inițial, trebuie ca fiecare element de pe diagonala pri ncipală,
în modul, să fie mai mare decât suma modulelor celorlalte elemente din linia respectivă. Este
posibil ca sistemul, în forma sa inițială să nu respecte această condiție necesară de
convergență. Înainte de a începe aplicarea algoritmului metodei, es te necesară o reordonare și
renumerotare a ecuațiilor în sistem astfel încât condiția de convergență să fie îndeplinită.
Sistemele pentru care se pretează metoda Jacobi au matricea diagonal dominantă.

Aplicație. Să se rezolve sistemul de ecua ții liniare prin metoda iterativ ă Jacobi:

Se porne ște rezolvarea de la solu ția ini țială
În prima etap ă se expliciteaz ă necunoscutele sistemului:

Înlocuind solu ția ini țială, se ob ține solu ția aproximativ ă după prima itera ție:

39
Următoarele trei itera ții conduc la solu țiile:

După cea de -a patra itera ție se ob țin valori apropiate de solu ția exact ă:
.

Aplicație. Folosind metoda Jacobi, să se aproximeze soluția pentru următoarele sisteme, de
forma
axA , astfel încât eroarea să fie ma i mică decât
410 :
a)
1,17 2,4 5,02,9 5,0 5,2 5,183,10 5,1 1,3
3 23 2 13 2 1

x x xx x xx x x b)
1 101 10 21 10 21 2 2 10
4 3 2 14 3 2 14 3 2 14 3 2 1

x xxxxx xxxxx xxx x x
Rezolvare:
a) Matricea A și vectorul termenilor liberi a este:

,
2,45,015,05,25,115,11,3




A





1,172,983,10
a
Elementele matricei A satisfac condițiile (3.7) și anume

,5,05,15,2,,15,11,3 ,
3
212 223
21 11
  


jjjjj
a aa a

.5,012,4,2
13 33  
jja a
deci, matricea A este dominant diagonală pe linii.
Transformăm sistemul inițial î ntr-un sistem echivalent de forma
bxBI) ( cu
ADIB1
și
aDb1 unde

40






100010001
I,





2,40 005,200 01,3
D ,





238095,0 0 00 400000,0 00 0 322581,0
1D

și





000000,1 119048,0 238095,0200000,0 000000,1 600000,0322581,0 483871,0 000000,1
1AD .
Obținem




   

0 119048,0 238095,0200000,0 0 600000,0322581,0 483871,0 0
B
,





071429,468,3493548,3
b .

Pentru acest sistem este îndeplinită condiția
1 max
11 
qaaBm
ijj iiji
mi
. Avem
.1 806452,0) 357143,0; 800000,0; 806452,0(max max3
13 1   

ijjjiib B

Deci metoda converge iar q=0,806452.
Șirul iteratelor
b xB xn n1 este convergent la soluția sistemului
axA
, oricare ar fi
0x .
Scris pe componente acest șir arată astfel

  
  
  071429,4 119048,0 238095,068,3 2,0 6,0493548,3 322581,0 483871,0
1
21
1 31
31
1 21
31
2 1
      
   
n n nn n nn n n
x x xx x xx x x
Pentru x(0) ={ 0, 0, 0 } rezultatele iteratelor sunt:
x(0) = { 0 0 0 }
x(1) = { 3.493548 3.68 4.071429 }
x(2) = { 0.399539 0.769585 2.801536 }
x(3) = { 2.217447 2.879969 3.884683 }
x(4) = { 0.846891 1.572595 3.200611 }
x(5) = { 1.70016 2.531743 3.682574 }
x(6) = { 1.080584 1.923389 3.365231 }

41
x(7) = { 1.477318 2.358603 3.585172 }
x(8) = { 1.195782 2.076575 3.4389 }
x(9) = { 1.379431 2.274751 3.539507 }
x(10) = { 1.251086 2.14444 3.472189 }
x(11) = { 1.335855 2.234911 3.518261 }
x(12) = { 1.277217 2.174835 3.487307 }
x(13) = { 1.316271 2.216208 3.50842 }
x(14) = { 1.289441 2.188553 3.494196 }
x(15) = { 1.307411 2.207496 3.503877 }
x(16) = { 1.295122 2.194778 3.497343 }
x(17) = { 1.303384 2.203458 3.501783 }
x(18) = { 1.297752 2.197613 3.498783 }
x(19) = { 1.301548 2.201593 3.500819 }
x(20) = { 1.298965 2.198908 3.499442 }
x(21) = { 1.300709 2.200733 3.500376 }
x(22) = { 1.299524 2.1995 3.499744 }
x(23) = { 1.300325 2.200337 3.500173 }
x(24) = { 1.299781 2.199771 3.499883 }
x(25) = { 1.300149 2.200155 3.500079 }
x(26) = { 1.2999 2.199895 3.499946 }
x(27) = { 1.300068 2.200071 3.500036 }
x(28) = { 1.299954 2.199952 3.499975 }
x(29) = { 1.300031 2.200033 3.500017 }
x(30) = { 1.299979 2.199978 3.499989 }
x(31) = { 1.300014 2.200015 3.500008 }
x(32) = { 1.29999 2.19999 3.499995 }
x(33) = { 1.300007 2.200007 3.500004 }
Pentru evaluarea erorii vom folosi formula (3.6) ( în raport cu
 ) și obținem:
 
.10 0000708,0000017,0 166677,4) 000009,0; 000017,0; 000017,0(max 166677,4806452,01806452,0
432 33 33
 
      x x z x

42
Matricea A și vectorul termenilor liberi a este:

Elementele matricei A satisfac condițiile (3.8.) și anume

,122 10 ,4
21 11  
iia a

,112 10 ,4
212 22  

iiia a

.111 10,112 10 ,
3
14 444
313 33
  


iiiii
a aa a
deci, matricea A este dominant diagonal ă pe coloane.
Fie















1,00 0 001,00 00 01,000 0 01,0
,
100000 100000 100000 10
,
1000010000100001
1D D I .
Făcând schimbarea
4,…,1 , jayx
jjj
j sistemul dat devine
ayDA1 , cu





11,01,01,01,011,02,01,01,0 12,01,02,02,01
1DA
.
Luând
1 DAIC se obține sistemul echivalent

ayCI
cu
.
0 1,0 1,0 1,01,0 0 1,0 2,01,0 1,0 0 2,01,0 2,0 2,0 0




  
C
.
1111
,
101111 101211 102122 10









 a A

43
Pentru acest sistem este îndeplinită condiția
1 max
111 
qaaCm
jii jjji
mj .
Avem
.15,0)3,0;4,0;4,0;5,0(max max4
14 11  
ijijc C Deci metoda converge iar
5,0q
.
Șirul iteratelor
 a yC yn n 1 este convergent la soluția sistemului
 ayCI
, oricare ar fi
0y .
Scris pe componente, acest șir arată astfel:

   
   1 1,0 1,0 2,01 1,0 2,0 2,0
1
41
31
1 21
41
31
2 1
      
    
n n n nn n n n
y y y yy y y y

   1 1,0 1,0 2,01
41
21
1 3       n n n ny y y y

   1 1,0 1,0 1,01
31
21
1 4       n n n ny y y y
Pentru y ( 0 ) = { 0, 0, 0, 0 } rezultat ele iteratelor sunt:
y(0) = { 0 0 0 0 }
y(1 ) = { 1 1 1 1 }
y(2 ) = { 0.5 0.6 0.6 0.7 }
y(3) = { 0.69 0.77 0.77 0.83 }
y(4) = { 0.609 0.702 0.702 0.777 }
y(5) = { 0.6415 0.7303 0.7303 0.7987 }
y(6) = { 0.62801 0.7188 0.7188 0.78979 }
y(7) = { 0.633501 0.7 23539 0.723539 0.793439 }
y(8) = { 0.63124 0.721602 0.721602 0.791942 }
y(9) = { 0.632165 0.722397 0.722397 0.792556 }
y(10) = { 0.631785 0.722072 0.722072 0.792304 }
y(11) = { 0.631941 0.722205 0.722205 0.792407 }
y(12) = { 0.631877 0.722151 0.722151 0.79 2365 }
y(13) = { 0.6319 03 0.722173 0.722173 0.792382 }
Pentru evaluarea erorii vom folosi formula (3.6.) (în raport cu
1 ) și obtinem:

44

 
.10 000087,0000017,0 000022,0 000022,0 000026,05,015,0
44
113 12
113

     
jj j z z z z
Soluția sistemului dat se obține ținând seama de substituția făcută. Deci soluția finală este:
x={ 0.0631903 0.0722173 0.0722173 0.0792382 }

II .2. Metoda Gauss -Seidel

În acest capitol am utilizat următoarele referințe bibli ografice: ( [3], [7], [10]).
În această metodă, care este o rafinare a metodei lui Jacobi, pentru rezolvarea unui sistem
de forma (3.1.), în construcția iteratei
nx se folosesc componentele lui
nx anterior
calculate.
Pentru
 m jijibB,…,1 , se notează






00 00 0
1 121
mm m b bb
L
 și





mmmm
bb bb b
R

0 002 221 11
unde R=B -L. Sistemul (3.1.), adică
bxBI , este echivalent cu sistemul
bxRLI 
. Calculând det(I -L) observăm că este diferit de zero, de unde rezultă
că există
1LI astfel încât
bxRLI  este echivalent cu
 bxRLIILI 1
. Aplicând
1LI obținem
 bLIxRLII1 1  
. Deci s istemul (3.1.) este identic cu sistemul

cxCI (3.9.)
unde
C=
RLI1 , c=
bLI1 .
Metoda Gauss -Seidel constă în aproximarea soluției sistemului (3.1.) cu
ajutorul șirului Jacobi asociat sistemului (3.9.). Pentru
 mx0 considerăm deci
 c xC xn n1
adică
bLI xRLI xn n 1 1 1     .Aplicăm (I -L) și
obținem

45

b xR xLIn n1, ceea ce se mai poate scrie:

b xR xL xn n n1 (3.10.)
Componentele șirului precedent sunt date prin:

  m k b xb xb xkn
jm
kjjkn
jk
jjkn
k ,…,1 ,11
1  

 (3.11.)
Vom nota



 m
kjjk jk
jjk k b q b q1
1 ,
 m k ,…,1 și
kmkq q

1max .
În cazul în care
ADIB1 șirul iteratelor este:

  m kaaxaaxaax
kkk n
jm
kj kkjk n
jk
j kkjk n
k ,…,1 ,11
1  

 .
Teorema 2. Dacă q<1 atunci sistemul (3.1.) are pentru orice
mb
soluție unică z, pentru orice
 mx0 șirul
nnx construit prin (3.10.) converge către
această soluție și au loc evaluările:

  
 
1 0 1
1 1x xqqx xqqz xn
n n n
(3.12.)
Demonstrație . Vom arăta că
q C și vom aplica apoi teorema 1.
Pentru
xCy ,
my y y ,…,1 avem:

 xq yk k ,
 m k ,…,1 (3.13.)
Într-adevar,
xRLIy1 care este identic cu
LIyxR  sau
xRyLy
, ceea ce pe componente se scrie:

jm
kjjk jk
jjk k xb yb y 

 1
1 ,
 m k ,…,1
Pentru
1k avem
jm
jjxb y

11 1 , de unde deducem

 
      xq x b x b ym
jj jm
jj 1
11
11 1

46
Să presupunem inegalitațile (3.13.) adevărate pentru
kj unde
mk .
Atunci

Din (3.13.) obținem
 xq y sau
q xC
x și deci
q C
. Deoarece
1q se poate aplica teorema 1.Rezultă că sistmul (3.1.) are pentru
orice
mb soluție unică z, șirul (3.10) converge la această soluție și au loc evaluările
(3.12.).
Vom nota cu
nnz șirul Jacobi asociat sistemului (3.1.) și cu
nnx
șirul (3.10.), pe care îl vom numi șirul Gauss -Seidel corespunzător sistemului (3.1.).
Numărul q este cel din teorema 2.
Teorema 3. Dacă

 m k bm
jjk ,…,1 1
1

și (3.14.)

 m k bm
kjjk ,…,1 1

atunci (3.1.) are pentru orice
mb soluție unică z, șirurile
nnx și
nnz
converg către această soluție și au loc:

  
 
  




     
1 0 11 0 1 1 1
1 1x xqqx xqqxzz z BI q z z BI zz
n
n n nmn
n n n






 



     

x q x b q bx b y b x b y b y
km
kjj k jm
jj km
kjjj kk
jjj k jm
kjj k jk
jj k k
1
11
1111
11
11
11 1

47
Demonstrație . Vom arăta pentru început că
1q . Prin ipoteză avem
11q ceea ce
este echivalent cu
1
11
m
jjb și vom demonstra prin inducție că
.1kq Presupunând
afirmația adevărată până la k evaluăm
1kq .
Fie
 

   m
kjj k jk
jj k k b q b q
11
11 1 .
Dacă
0
11
 jk
jj k q b atunci
1
11 1  
 m
kjj k k b q (conform cu (3.14.)). În caz contrar,
există
k j ,…,10 astfel încât
0
0 01 j j k q b . Conform ipotezei de inducție avem
0 0 0 1 1 j k j j k b q b 
și deci din prima dintre formulele (3.14.) rezultă

1
11 1
11 10 0
0     
 
 m
jj k j j km
jjjj k k b q b b q
Avem deci
1q . Conform teoremei 2 sistemul (3.1.) are pentru orice
mb
soluție unică z și avem

  
 
 1 0 1
1 1x xqqx xqqxzn
n n n
Vom arăta în continuare că în ipotezele considerate converge și șirul
Jacobi asociat sistemului (3.1.). Din prima dintre relațiile (3.14.) deducem că
1B și de
aici

1
nB
n N (3.15.)
Fie
m
my y y   ,…,1 si
yB yn n ,
n
mn ny y y ,…,1 .
Avem


 yq ykn
k ,
mn1 ,
nk1 (3.16.)
Într-adevăr, dacă în (3.16.) considerăm n=1 va rezulta k=1. Conform
ipotezei avem


  yq y b yjm
jj 1
111
1 ceea ce înseamnă că relațiile (3.16.) sunt
adevărate pentru n=1. Să presupunem (3.16.) adevărate pentru n<m. Pentru
1nk avem

   n
jm
kjjkn
jk
jjkn
jm
jjkn
k yb yb yb y 

   1
1 11

48
Folosind ipoteza de inducție și (3.15.) obținem
   
.1
11
11
11
11
 

 

 




       
     
yq y b q b y B b y q by b yq b y b y b y
km
kjjk jk
jjknm
kjjk jk
jjknm
kjjk jk
jjkn
jm
kjjkn
jk
jjkn
k
Pentru n=m, din (3.16.) deducem atunci


  yq ym
sau

  yq yBm

și deci

q Bm
 (3.17.)
Pentru
n N,
mn , notăm cu


mn partea întreagă a lui
mn și fie
r N,
mr
astfel încât
rmmnn 
 . . Folosind (3.15.) și (3.17.) avem


 





   
  
mn
mn
mn
mn
q B B B B B Bm r m r m n

Reținem deci că



mn
nq B (3.18.)
Reamintim că
 1 1   n n nz z BIz z de unde obținem

.1 0 11 0 1 1 1
   



    
z z B BIz zB BI z z BI z z
nn n n n

Folosind și (3.18.) obținem

(3.19.)
ceea ce încheie demonstrația.
Din (3.15.) rezultă că evaluarea aposteriori din (3.19.) are loc sub forma



n n nz z BI z z1 1


 


   

1 0 1 1 1z z BI q z z BI z zmn
n n n

49
Observație . Sistemul Ax=a este echivalent cu sistemul (3.1.), unde
ADIB1 si b=
AD1 .
Atunci relațiile (3.14.) pentru sistemul (3.1.) devin:

1
1
m
kjj kkjk
aa și
1
1
m
kj kkjk
aa
,.)14.3(

sau

iim
kjjjk a a
1 și
kkm
kjjk a a
1
,.)14.3(

Aplicație . Folosind metoda Gauss -Seidel, să se rezolve cu o eroare mai mică decat
310
sistemul

78,2 21,1 14,0 25,0555,1 15,0 13,1 41,0515,0 3,0 25,0 02,1
3 2 13 2 13 2 1

x x xx x xx x x
Rezolvare . Matricea A și vectorul termenilor liberi asociați sistemului este:




 

21,1 14,0 25,015,0 13,1 41,03,0 25,0 02,1
A
și





78,2555,1515,0
a .
Elementele matricei A satisfac condițiile
,.20.3 și anume
.21,1 14,0 25,0,13,1 15,0, 13,1 15,041,0,02,13,0 25,0,
332
1322 32 223
212113
21
     


a aa ași a aa a
jjjjjjj

Transformăm sistemul dat într -un sistem echivalent de forma
bxBI
, cu
ADIB1 ,
aDb1 unde
,
826446,0 0 00 884956,0 00 0 980392,0
,
21,10 00 13,100 0 02,1
,
100010001
1














D D I

50

.
1 115702,0 206612,0132743,0 1 362832,0294118,0 245098,0 1
1




   
AD
Obținem





0 115702,0 206612,0132743,0 0 362832,0294118,0 245098,0 0
B
și





297521,2376106,1504902,0
b , pentru care sunt
verificate condițiile ( 3.14. ), adică
10 115702,0 206612,0,11 132743,0,1 1 132743,00 362832,0,11 294118,0 245098,00,1
3
13323
123
11
        


jjjjjj
bbsi bb

și deci șirul Gauss -Seidel converge la soluția sistemului dat. Calculăm
kmkq q

1max :
539216,0 294118,0 245098,03
11 1   
jjb q

328388,0 132743,00 539216,0 362832,03
22 1 12 2     
jjb q b q

149404,0328388,0 115702,0 539216,0 206612,033 2 23 1 13 3
       b q b q b q
și
obținem q=0,539216.
Deoarece q=0,539216<1, șirul iteratelor Gauss -Seidel,

b xR xL xn n n1 ,
converge la soluția sistemului dat, oricare ar fi
0x .
Atunci avem





0 115702,0 206612,00 0 362832,00 0 0
L
,





0 0 0132743,0 0 0294118,0 245098,00
R
și șirul itera telor Gauss -Seidel, scris pe componente este

51

  
  
  297521,2 115702,0 206612,0376106,1 132743,0 362832,0504902,0 294118,0 245098,0
2 1 31
3 1 21
31
2 1
      
 
n n nn n nn n n
x x xx x xx x x
Luând x(0) ={ 0, 0, 0 }, primele iterate calculate cu 3 zecimale exacte sunt:
x(1) = { 0.504902 1.559301 2.582254 }
x(2) = { 1.64657 2.316311 2.905724 }
x(3) = { 1.92725 2.461089 2.98046 7 }
x(4) = { 1.984718 2.491862 2.995901 }
x(5) = { 1.9968 2.498295 2.999142 }
x(6) = { 1.99933 2.499643 2.99982 }
x(7) = { 1.99986 2.499925 2.999962 }
Pentru evaluarea erorii folosim formula
 
      
 
000282,0 1702142,1 000142,0; 000282,0; 00053,0 max 1702142,1539216,01539216,06 7 7x x z x

.10 00033,03

52
CAPITOLUL I II
APLICA ȚII
Implementarea în C ++ a metodelor Gauss, Jacobi și
Gauss -Siedel

În acest capitol am utilizat următoarele referințe bibliografice: ([ 6], [9], [10], [11], [12]).

Metode directe
3.1. Tema
Rezolvarea numerică a sistemelor algebrice lin iare prin metoda de eliminare a lui Gauss.
Un sistem de n ecuații liniare cu n necunoscute are forma
b Ax , unde A este o matrice
pătrată, nesingulară, de dimensiune
nn , iar x și b sunt vectori coloană de dimensiune n.

3.2. Metoda
Notăm, inițial,
b bA A )1( )1(, , indicele superior reprezentând etapa.
Relațiile de recurență în metoda de eliminare a lui Gauss sunt:



 

, , ,, ,0,
)()()(
)()(
)1(
kjki
aaa
akjkiki a
a
k
kkk
kjk
ik k
ijk
ij
k
ij




 

,,…,1, , ,,
)()()(
)()(
)1(
n ji ki
aba
bki b
b
k
kkk
kk
ik k
ik
i
k
i

1 ,…,1 n k
.
Sistemul se rezolvă prin metod a substituției inverse conform relațiilor







 
.1…,,1 ,1
1)( )(
)()()(
nixa b
axabx
n
ijji
iji
i i
iiin
nnn
nn

53
3.3. Exemplu
Să se aplice metoda de eliminare a lui Gauss pentru rezolva rea sistemul


4 51 42 3
3 2 13 23 2 1
x xxx xx xx

Rezolvare.
Matricea asociată sistemului (în etapa 1) este





51114011 3
A , iar vectorul termenilor
liberi este





412
b .
k = 1
.314,1 ,2,314,34,0,1 ,4 ,0,1 ,1 ,3
)1(
11)1(
1)1(
31 )1(
3)2(
3 )1(
11)1(
1)1(
21 )1(
2)2(
2)1(
1)2(
1)1(
11)1(
13)1(
31 )1(
33)2(
33 )1(
11)1(
12)1(
31 )1(
32)2(
32)2(
31)1(
11)1(
13)1(
21 )1(
23)2(
23 )1(
11)1(
12)1(
21 )1(
22)2(
22)2(
21)1(
13)2(
13)1(
12)2(
12)1(
11)2(
11
       
abab b
abab b b baaaa a
aaaa a aaaaa a
aaaa a aa a a a a a

k = 2
.313,1 ,2,313,0 ,0,1 ,4 ,0,1 ,1 ,3
)2(
22)2(
2)2(
32 )2(
3)3(
3)2(
2)3(
2)2(
1)3(
1)2(
22)2(
23)2(
32 )2(
33)3(
33)3(
32)3(
31)2(
23)3(
23)2(
22)3(
22)2(
21)3(
21)2(
13)3(
13)2(
12)3(
12)2(
11)3(
11
  
abab b b b b baaaa a a aa a a a a aa a a a a a

Soluțiile sunt:
1)3(
33)3(
33
abx
,
01 3
3)2(
2)2(
2)2(
222 



 
jjjxa b
ax
,
11 3
2)1(
1)1(
1)1(
111 



 
jjjxa b
ax
,
adică soluția sistemului este

54






101
x.

3.4.Algoritmul
Algoritmul asociat metodei Gauss este
Intrări: n = numărul de ecuații și necunoscute ale sistemului
A = matricea sistemului
b = vectorul termenilor liberi
Ieșiri: x = vectorul soluție
{
pentru k
 1 : n – 1
{
pentru i
 1 : n
pentru j
 1 : n
dacă
ki atunci
k
ijk
ij a a1
altfel
dacă
kj atunci
01k
ija
altfel
)()()( )( )1(/k
kkk
kjk
ikk
ijk
ija aa a a 
pentru i
 1 : n
dacă
ki atunci
k
ik
i b b1
altfel
k
kkk
kk
ikk
ik
i aba b b /1
}

n
nnn
n n ab x /
pentru i
 n – 1 : 1
{

0s
pentru j
 i + 1 : n

ji
ijxass 

i
iii
i i asb x /) (
}
}

55

3.5.Programul sursă C ++
// Metoda Gauss de eliminare
#include <stdio >
#include <conio >
#include <iostream >
#include <math >
using namespace std;
#define max 15
int main ( )
{
float s;
float a[max+1][max+1][max+1],b[max+1][max+1],x[max+1];
int n,i,j,k;
clrscr();
cout << "dati dimensiunea matricii" << endl;
cin >> n;
cout << "dati matricea sistemul ui " << endl;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
cout << "a[" << i << j << "]=";
cin >> a[i][j][1];
}
cout << endl;
cout << "dati vectorul termenilor liberi " << endl;
for (i=1;i<=n;i++)
{
cout << "b[" << i << "]=";
cin >> b[i][1];
}
cout << endl;
for (k=1;k<=n -1;k++)
{
for (i=1;i<=n;i++)

56
for (j=1;j<=n;j++)
{
if (i<=k)a[i][j][k+1]=a[i][j][k];
else if (j<=k)a[i][j][k+1]=0;
else a[i][j][k+1]=a[i ][j][k] -a[i][k][k]*a[k][j][k]/a[k][k][k];
}
for (i=1;i<=n;i++)
if (i<=k)b[i][k+1]=b[i][k];
else b[i][k+1]=b[i][k] -a[i][k][k]*b[k][k]/a[k][k][k];
}
x[n]=b[n][n]/a[n][n][n];
for (i=n -1;i>=1;i –)
{s=0;
for (j=i+1; j<=n;j++)
s=s+a[i][j][i]*x[j];
x[i]=(b[i][i] -s)/a[i][i][i];
}
cout << "Solutia aproximativa este:" << endl;
for (i=1;i<=n;i++)
cout << x[i] << ' ';
cout << endl;
getche();
}

57

58
Metode iterative

3.1. Tema
Rezolvarea numerică a si stemelor algebrice liniare prin metodele Jacobi și Gauss –
Seidel.
Un sistem de n ecuații liniare cu n necunoscute are forma
b Ax , unde A este o
matrice pătrată, nesingulară, de dimensiune
nn , iar x și b sunt vectori col oană de dimensiune
n.

3.2. Metoda
Considerăm aproximația inițială
) ,…, ()0( )0(
1)0(
nx x x un element din R
n, unde
indicele superior reprezintă etapa.
Construim șirul
) ,…, ()( )(
1)( k
nk kx x x definit prin formulele de recurență:
 în metoda Ja cobi:
iii k
jn
ijj iiij k
iabxaa
x  
 )(
1)1(
,
n i,1 ;
 în metoda Gauss -Seidel:
iii k
jn
ij iiij k
ji
j iiij k
iabxaa
xaa
x   

 )(
1)1(1
1)1(
,
n i,1 .
Utilizăm verificarea condiției
 
n
ik
ik
ix x
1)( )1( pentru convergența șirului.

3.3. Exemplu
a) Să se rezolve, folosind meto da iterativă Jacobi, sistemul


4 51 42 3
3 2 13 23 2 1
x xxx xx xx .
Rezolvare.
Matricea asociată sistemului (în etapa 1) este





51114011 3
A iar vectorul termenilor
liberi este





412
b .
Șirul de recurențe pentru soluție este

59




   

54
51
5141
4132
31
31
)(
2)(
1)1(
3)(
3)1(
2)(
3)(
2)1(
1
k k kk kk k k
x x xx xx x x
Inițializăm





000)0(x și alcătuim tabelul

Etapa
1x
2x
3x
0 0 0 0
1
32
41
54
2
6051
201
6053
3
180170
2407
300288
4
36003517
960233
36003459

1
0
1
Se obține astfel soluția aproximativă


101
321
xxx .

b) Să se rezolve, folosind metoda Gauss -Seidel, sistemul


1 23 31 2
3 2 13 2 13 2 1
x xxx x xx xx .
Rezolvare.
,67,21
222 )0(3
3222 )1(1
1222 )1(
2111 )0(3
2111 )1(
1
   
 
abxaa
xaa
xabxaa
x
jjj
jjjj
jj

60

.17288,864880,2888,14414,3641,121,31
333 )3(2
1333 )3(
3222 )2(3
3222 )3(1
1222 )3(
2111 )2(3
2111 )3(
1333 )2(2
1333 )2(
3222 )1(3
3222 )2(1
1222 )2(
2111 )1(3
2111 )2(
1333 )1(2
1333 )1(
3
         
  
abxaa
xabxaa
xaa
xabxaa
xabxaa
xabxaa
xaa
xabxaa
xabxaa
x
j
jjj
jj
j
jjj
jjj
jjj
jj
j
jjj
jjj
jj
Tabelul soluțiilor este

Etapa
1x
2x
3x
0 0 0 0
1
21
67
31
2
121
3641
14414
3
2888
864880
17288

0
1
0

Se obține astfel soluția aproximativă


010
321
xxx .

3.4. Algoritmul
Algoritmul asociat metodei Jacobi este
Intrări: n = numărul de ecuații și necunoscu te ale sistemului
A = matricea sistemului
b = vectorul termenilor liberi
y = aproximația anterioară a soluției

 = precizia

61
Ieșiri: x = aproximația soluției
{
repetă
{
pentru i
 1 : n
{

01s
pentru j
 1 : n
dacă
ij atunci

j ijyas s 1 1

ii i i asb x /)1 (
}

0s
pentru i
 1 : n

| |i iyxss 
pentru i
 1 : n

i ix y
}
până când (
s )
}

Algoritmul asociat metodei Gauss -Seidel este
Intrări: n = numărul de ecuaț ii și necunoscute ale sistemului
A = matricea sistemului
b = vectorul termenilor liberi
y = aproximația anterioară a soluției

 = precizia
Ieșiri: x = aproximația soluției

{
pentru i
 1 : n

i ix y

62

1s
cât timp
s
{
pentru i
 1 : n
{

01s
pentru j
 1 : n
dacă
ij atunci

j ijxas s 1 1

ii i i asb x /)1 (
}

0s
pentru i
 1 : n

| |i iyxss 
pentru i
 1 : n

i ix y
}

3.5. Programul sursă C ++
// Metoda Jacobi pentru rezolvarea sistemelor
#include <stdio .h>
#include <conio .h>
#include <iostream >
#include <m ath.h>
using namespace std;
#define max 10
int main ( )
{
float s,s1,eps;
float a[max+1][max+1],b[max+1] ,x[max+1],y[max+1];
int n,i,j;
cout << "dati numarul de ecuatii si necunoscute " << endl;
cin >> n;

63
cout << "dati matricea sistemului " << endl;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
cout << "a[" << i << j << "]=";
cin > > a[i][j];
}
cout << endl;
cout << "dati vectorul termenilor liberi " << endl;
for (i=1;i<=n;i++)
{
cout << "b[" << i << "]=";
cin >> b[i];
}
cout << endl;
cout << "dati aproximatia initiala a solutiei " << endl ;
for (i=1;i<=n;i++)
{
cout << "x[" << i << "]=";
cin >> y[i];
}
cout << endl;
cout << "dati eroarea " << endl; cin >> eps; cout << endl;
s=eps+1;
while (s>=eps)
{
for (i=1;i<=n;i++)
{
s1=0;
for (j=1;j<=n;j++)
if (j!=i)s1=s1+a[i][j]*y[j]; x[i]=(b[i] -s1)/a[i][i];
}
s=0;
for (i=1;i<=n;i++)
s=s+abs(x[i] -y[i]);

64
for (i=1;i<=n;i++)
y[i]=x[i];
}
cout << "Solutia aproximativa este " << endl;
for (i=1;i<=n;i++)
cout << x[i] << endl;
getche();
}

65

// Metoda Gauss_Seidel pentru rezolvarea sistemelor
#include <stdio .h>
#include <conio .h>
#include <iostream >
#include <math .h>
using nam espace std;

#define max 10
int main ( )
{
float s,s1,eps;
float a[max+1][max+1],b[max+1],x[max+1],y[max+1];
int n,i,j;
clrscr();
cout << "dati numarul de ecuatii si necunoscute " << endl; cin >> n;
cout << "dati matricea sistemului " << endl;

66
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
cout << "a[" << i << j << "]="; cin >> a[i][j];
}
cout << endl;
cout << "dati vectorul termenilor liberi " << endl;
for (i=1;i<=n;i++)
{
cout << "b[" << i << "]="; cin >> b [i];
}
cout << endl;
cout << "dati aproximatia initiala a solutiei " << endl;
for (i=1;i<=n;i++)
{
cout << "x[" << i << "]="; cin >> x[i]; y[i]=x[i];
}
cout << endl;
cout << "dati eroarea " << endl;
cin >> eps;
cout << endl;
s=eps+1;
while (s>=eps)
{
for (i=1;i<=n;i++)
{
s1=0;
for (j=1;j<=n;j++)
if (j!=i)s1=s1+a[i][j]*x[j]; x[i]=(b[i] -s1)/a[i][i];
}
s=0;
for (i=1;i<=n;i++)
s=s+abs(x[i] -y[i]);
for (i=1;i<=n;i++)
y[i]=x[i];

67
}
cout << "Solutia aproximativa este " << endl;
for (i=1;i<=n;i++)
cout << x[i] << endl;
getche();
}

68

69
BIBLIOGRAFIE

[1]. Bucur, C. M., Metode numeri ce, Ed. Facla, Timișoara, 1973.
[2]. Ciurea, E., Algoritmi Introducere în algoritmica grafurilor , Ed. Tehnică, București,
2001.
[3]. Dodescu, Gh., Toma, M., Metode de calcul numeric , E. D. P., București, 1976.
[4]. Dodescu, Gh., Metode numerice în algebră , Ed. tehnică , București, 1979.
[5]. Ichim, I., Marinescu, G., Metode de aproximare numerică , Ed. Academiei R. S.
R., București, 1986.
[6]. Ignat, C., Ilioi, C., Jucan, T., Elemente de informatică și calcul numeric , Univ.
„Al. I. Cuza”, Iași, Fac. de Matematică, 1989.
[7]. Mihu, C., Metode numerice în algebra liniară , Ed. Tehnică, București , 1977.
[8]. Scheiber, E., Metode numerice , Univ. Transilvania din Brașov, Facultatea de
Matematică – Informatică, (electronic).
[9]. Talmaciu Mihai, Patriciu Alina -Mihaela, Calcul numeric, note de curs
[10]. Talmaciu Mihai, Patriciu Alina -Mihaela, Metode numerice, note de seminar
pentru studentii Facultății de Inginerie
[11]. Talmaciu ,M., Patriciu , A.M., Recipiente numerice în Pascal și C, Editura
EduSoft, Bacău, 2005.
[12]. Talmaciu , M., Patriciu , A.M., Metode numerice, Volumul I, Editura Tehnica
Info, Chișinău, 2005.