mn2
DESCRIPTION
lab 2TRANSCRIPT
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