Universitatea Tehnică a Moldovei

Facultatea СIM

RaportMetode Numerice

Lucrare de laborator nr 2

A elaborat st. gr.FI-141: Eladii Vadim

A verificat: V. Moraru

Chişinău 2015

Scopul lucrarii:1.Sa se rezolve sistemul de ecuatii liniare Ax=b,utilizind:

Metoda lui Cholesky; Metoda iterativa a lui Jacobi cu eroare ԑ=10-3; Metoda iterativa a lui Gauss-Seidel cu eroare ԑ=10-5;

2.Sa se determine numarul necesar de iteratii pentru aproximarea solutiei sistemului cu eroarea data ԑ. Sa se compare rezultatele.3.Sa se implementeze metodele date intr-un limbaj de programare.Varianta 1:

A=( 9 −3 1−3 6 −11 −1 4 ) b=( 4−75 )

1)Rezolvarea sistemului de ecuatii liniare Ax=b prin metoda lui Cholesky:

9 x1−3 x2+x3=8

−3 x1+6x2−x3=−7x1−x2+4 x3=5

a)Descompunem sistemul Ax=b in doua sisteme triunghiulare: LTy=b; Lx=y; ,unde LT, L-sunt matrici:b)Deci pentru aflarea solutiei sistelemului trebuie sa calculam elementele matricei LT

conform formulelor:

l11=√a11=√9=3

l12=a12√a11

=−1

l13=a13√a11

= 1√9

=13

l22=√a22−l122 =√5

l23=a23−l13 l12l11

=−29

l33=√a33−l132 −l232 =√4−( 13

2

)−(−292

)=√ 31181c)Determinam componentele vectorului y:y1=

b1l11

=43

y2=b2−l12 y1l22

= −173∗√5

y3=b3−l13 y1−l23 y2

l33=2.03

d) Acum putem determina solutiile:x3=

y3l33

=2.031.96

=1,03

x2=y2−l23 x3l22

=−1.02

x1=y1−l12 x2−l13 x3

l11=0

Deci,solutia sistemului este vectorul x=(1,1,0);

2. Rezolvarea sistemului de ecuatii liniare prin metoda iterativa a lui Jacobi cu eroarea ԑ =10 -3 : a) Descompunem sistemul Ax=b in :

{ 9 x1−3 x2+x3=8−3 x1+6 x2−x3=−7x1−x2+4 x3=5

≤¿ {x1=49+ 39x2−

19x3

x2=−76

+ 36x1+

16

x3=54−14x1+

14x2

x3

Q=(0 3

9−19

36

0 16

−14

14

0 ) x(0)=d=(49

−7654

) b)Verificam conditia de convergenta:

i=1 ∑j=1

3

|q1 j|=|q11|+|q12|+|q13|=0+39−19=29<1

i=2 ∑j=1

3

|q2 j|=|q21|+|q22|+|q23|=36+0+ 1

6= 46<1

i=3 ∑j=1

3

|q3 j|=|q31|+|q32|+|q33|=−14

+ 14=0<1

c)Vom rezolva sistemul utilizind in calitate de solutia initiala vectorul x(0):

{ x1(k+1)=3

9x2(k)−1

9x3

(k)+ 49

x2(k+1)=3

6x1

(k)+ 16x3

(k)−76

x3(k+1 )=−1

4x1

(k)+ 14x2(k)+ 5

4 Prima iteratie

x1(1)=3

9x2(0)−1

9x3(0)+ 4

9= 112

x2(1)=3

6x1(0)+ 1

6x3

(0 )−76=−4354

x3(1)=−1

4x1

(0)+ 14x2

(0)+ 54=6172

Verificam daca solutiile obtinute sunt acceptabile pentru eroarea stabilita:

‖x i(1 )−xi(0 )‖=max {|x1(1 )−x1

(0 )|,|x2(1 )−x2(0)|,|x3(1 )−x3

(0)|}=max {0,36 ;0,37 ;0,402 }

¿0,402>ԑ

Deoarece 0,402>ԑ,solutia n-a fost determinata si deci procesul iterativ trebuie continuat:

Iteratia a douax1

(2)=39x2(1)−1

9x3

(1)+ 49=−0,085

x2(2)=3

6x1(1)+ 1

6x3(1)−7

6=−0,9838

x3(2)=−1

4x1

(1 )+ 14x2

(1 )+ 54=1.0302

Verificam daca solutiile obtinute sunt acceptabile pentru eroarea stabilita:

‖x i(2 )−x i(1)‖=max {|x1(2)−x1

( 1)|,|x2(2)−x2(1 )|,|x3(2)−x3

(1 )|}=max {0,002; 0,187 ;0,183 }

¿0,187>ԑ

Deoarece 0,187 >ԑ,solutia n-a fost determinata si deci procesul iterativ trebuie continuat:

Iteratia a treiax1

(3)=39x2(2)−1

9x3(2)+ 4

9=0,0017

x2(3)=3

6x1(2)+ 1

6x3

(2)−76=−1,037

x3(3)=−1

4x1

(2)+ 14x2

(2)+ 54=0,9828

Verificam daca solutiile obtinute sunt acceptabile pentru eroarea stabilita:‖x i(3 )−xi

(2 )‖=max {|x1(3 )−x1(2)|,|x2(3 )−x2

(2)|,|x3(3 )−x3(2)|}=max {0,083 ;0,053 ;0,047 }

¿0,083>ԑDeoarece 0,083>ԑ,solutia n-a fost determinata si deci procesul iterativ trebuie continuat: ect...

Solutia aproximativa este x=(0 ;1;−1);

3. Rezolvarea sistemului de ecuatii liniare prin metoda iterativa Gauss-Seidel cu eroarea ԑ=10-5 :

{ x1(k+1)=3

9x2(k)−1

9x3

(k)+ 49

x2(k+1)=3

6x1

(k)+ 16x3

(k)−76

x3(k+1 )=−1

4x1

(k)+ 14x2(k)+ 5

4Prima iteratie

x1(1)=3

9x2(0)−1

9x3(0)+ 4

9= 112

x2(1)=3

6x1(1)+ 1

6x3(0)−7

6=¿0.917

x3(1)=−1

4x1

(1 )+ 14x2

(1 )+ 54=1,0302

Verificam daca solutiile obtinute sunt acceptabile pentru eroarea stabilita:

‖x i(1 )−xi(0 )‖=max {|x1(1 )−x1

(0 )|,|x2(1 )−x2(0)|,|x3(1 )−x3

(0)|}=max {0,36 ;0,248 ;0,2198 }

¿0,36>ԑ

Deoarece 0,36>ԑ,solutia n-a fost determinata si deci procesul iterativ trebuie continuat:

Iteratia a douax1

(2)=39x2(1)−1

9x3

(1)+ 49=0.065

x2(2)=3

6x1(2)+ 1

6x3

(1)−76=−0.962

x3(2)=−1

4x1

(2)+ 14x2

(2)+ 54=0.9933

Verificam daca solutiile obtinute sunt acceptabile pentru eroarea stabilita:

‖x i(2 )−xi(1)‖=max {|x1(2)−x1

( 1)|,|x2(2)−x2(1 )|,|x3( 2)−x3

(1 )|}=max {0,018 ;0,166 ;0,036 }

¿0,166>ԑDeoarece 0,166>ԑ,solutia n-a fost determinata si deci procesul iterativ trebuie continuat:

Iteratia a treiax1

(3)=39x2(2)−1

9x3(2)+ 4

9=0.014

x2(3)=3

6x1(3)+ 1

6x3

(2)−76=−0.997

x3(3)=−1

4x1

(3)+ 14x2

(3)+ 54=0.9975

Verificam daca solutiile obtinute sunt acceptabile pentru eroarea stabilita:‖x i(3 )−x i

(2 )‖=max {|x1(3 )−x1(2)|,|x2(3 )−x2

(2)|,|x3(3 )−x3(2)|}=max {0,075 ;0,035 ;0,042 }

¿0,075>ԑDeoarece 0,075>ԑ,solutia n-a fost determinata si deci procesul iterativ trebuie continuat: ect...Solutia aproximativa este x(5)=(1 ;1;0);

Programul implementat in limbajul C++:#include <iostream>#include <stdio.h>#include <math.h>#include<stdlib.h>#define n 3using namespace std;float A[3][3]={ 9,-3,1,-3,6,-1,1,-1,4};float B[3]={4,-7,5};void cholesky(){ int i,j,k,k1=0; float t,x[n],l[n][n],y[n]; l[0][0]=sqrt(A[0][0]); for(i=1;i<n;i++)

{l[i][0]=A[i][0]/l[0][0]; } for(k=1;k<n;k++)

{t=0; for(j=0;j<k-1;j++) t+=l[k][j]*l[k][j]; l[k][k]=sqrt(A[k][k]-t); for(i=k+1;i<n;i++)

{t=0; for(j=0;j<k-1;j++)

t+=l[i][j]*l[k][j]; l[i][k]=(A[i][k]-t)/l[k][k];}k1++;}

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

for(j=i+1;j<n;j++) {l[i][j]=l[j][i]; }

for(i=0;i<n;i++) {t=0;

for(j=0;j<i;j++) t+=l[i][j]*y[j];

t=B[i]-t;y[i]=t/l[i][i]; }

for(i=n-1;i>=0;i--) {t=0;

for(j=n-1;j>i;j--) t+=l[i][j]*x[j];

t=y[i]-t;x[i]=t/l[i][i]; }

cout<<"==Metoda lui Cholesky"<<endl<<endl; for(i=0;i<n;i++) printf("%7.3f ",x[i]); cout<<endl<<endl;}void jacobi(){int i,j,m,k1=0; float v,x[n],q[n][n],d[n],s[n][n],t[n][n],x1[n],er; for(i=0;i<n;i++)

for(j=0;j<n;j++) {if(i==j)

{s[i][j]=1/A[i][j]; t[i][j]=0;} else

{s[i][j]=0; t[i][j]=A[i][j];}

} for(i=0;i<n;i++)

for(j=0;j<n;j++) {v=0;

for(m=0;m<n;m++)v+=s[i][m]*t[m][j];

q[i][j]=-v; } for(i=0;i<n;i++)

{v=0;for(m=0;m<n;m++)

v+=s[i][m]*B[m];d[i]=v; }

for(i=0;i<n;i++) x[i]=d[i];

do {k1++; for(i=0;i<n;i++)

x1[i]=x[i];for(i=0;i<n;i++)

{v=0; for(m=0;m<n;m++)

v+=x1[m]*q[i][m]; x[i]=v+d[i];}

er=fabs(x1[0]-x[0]);for(m=0;m<n;m++)

if(er<fabs(x1[m]-x[m]))er=fabs(x1[m]-x[m]); }

while(er>0.001); cout<<"==Metoda lui Jacobi cu eroarea 0.001"<<endl<<endl; for(i=0;i<n;i++)

printf("%7.3f ",x[i]);cout<<endl; cout<<"\n==Numarul de iteratii:"<<k1<<endl<<endl;}

void gauss_seidel(){ int i,j,m,k1=0,k; float v,x[n],q[n][n],d[n],s[n][n],t[n][n],x1[n],er; for(i=0;i<n;i++) for(j=0;j<n;j++)

{ if(i==j) {s[i][j]=1/A[i][j];

t[i][j]=0; }else

{ s[i][j]=0; t[i][j]=A[i][j];}

}; for(i=0;i<n;i++)

for(j=0;j<n;j++) { v=0;

for(m=0;m<n;m++)

v+=s[i][m]*t[m][j];q[i][j]=-v;

}for(i=0;i<n;i++) { v=0;

for(m=0;m<n;m++) v+=s[i][m]*B[m];d[i]=v;

}for(i=0;i<n;i++) x[i]=d[i];

do{k1++;for(i=0;i<n;i++)

x1[i]=x[i];for(i=0;i<n;i++)

{v=0; for(m=0;m<n;m++)

v+=x[m]*q[i][m]; x[i]=v+d[i];}

er=fabs(x1[0]-x[0]);for(m=1;m<n;m++)

if(er<fabs(x1[m]-x[m]))er=fabs(x1[m]-x[m]);} while(er>0.00001); cout<<"==Metoda a lui Gauss-Seidel cu eroarea 0.00001"<<endl<<endl; for(i=0;i<n;i++)

printf("%7.5f ",x[i]); cout<<endl;

cout<<"\n==Nrumarul de iteratii:"<< k1<<endl<<endl;}int main(){int p; do { cout<<"1.Metoda lui Cholesky "<<endl;

cout<<"2.Metoda iterativa a lui Jacobi"<<endl;cout<<"3.Metoda iterativa a lui Gauss-Seidel"<<endl;cout<<"4.Exit"<<endl;cin>>p;switch (p){ case 1 :{cholesky ();break;}

case 2 :{jacobi();break;}case 3 :{gauss_seidel();break;}

default:break; }; }

while(p!=4);}

Rezultatele obtinute:

Concluzie: Dupa realizarea lucrarii de laborator numarul 2 am invatat 3 metode de rezolvare a sistemelor de ecuatii liniare: metoda lui Cholesky,metoda iterativa a lui Jacobi si metoda iterativa a lui Gauss-Seidel . Implementindule intr-un program am observat numarul de iteratii necesare pentru obtinerea unor solutii cit mai apropiate