TPs Calcul Numérique

I.3 - Méthode De Gauss - Seidel

Objectif : Résolution d'un système linéaire d'une manière itérative

On utilise cette méthode Pour les très grosses matrices, Elle converge vers la solution progressivement et plus rapidement.

Idée de base est de résoudre une équation de type : F(x)=X ; avec une suite de type : Xk⁺¹ =F(Xk) ;X⁰ donnée.

Si |Xk⁺¹ - Xk | <î alors Xk solution.

Pour faire ça on décompose la matrice A tel que A = F - E ; alors

AX=BF(F--E)X=BIFX--EX=BIFX=EX+B

I X=F⁶'EX+F⁶'BIX=?X+K

Où

F=(

0

0 a22

~ ~ ~ ~

0 0
·
·
· ann

a11 0

~

~

0

1 S 0 0

a11

V

0 1 a22

S ~ 0 U

~ ~ ~ ~ U

0 0
·
·
· 1 ann

S T

alors F⁶' =

n

2n

H = ~0 ^--a2 ~ --a ^--a2 0 ~ --a

~ ~ ~ ~
^--ani ^--an2 ~ 0

Donc à chaque itération on a :

t6 n

1

t 7W.8 = 7'.' 8 -- > atix, 7W8

X bt -- > at,x, Y ; j: 1, 2

^attj=1 j=t+1

Remarque : pour assurer la convergence il faut que A soit dominante. Le programme

//TP3 Calcul Numérique //Méthode Gauss-Seidel

#include<iostream.h> #include<iomanip.h> #include<math.h> #include<conio.h> #include<alloc.h>

double **DefMat(int n,int m)//Allocation dynamique du matrice {double * *tmp=(double* *)malloc(n*sizeof(double*)); for(int i=0;i<n;i++)

tmp[i]=(double*)malloc(m*sizeof(double));

return tmp;

}

void charger(double **M,int n,int m)//Chargement du matrice {int x=0;

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

{for(int j=0;j<m;j++)

{cin>>M[i] [j];

gotoxy(x+=8,wherey()- 1);

}

cout<<endl;

x=0;

}

}

int dominante(double **A,int n)//vérification du domination {for(int i=0;i<n;i++)

{double som=0;

for(int j=0;j<n,j !=i;j++) som+=fabs(A[i] [j]);

if(som >= fabs(A[i][i]) ) return 0;

}

return 1;

}

double* Xkplus1(double **A,double *X0,int n)//calcul du X(k+1) {double *tmp=(double*)malloc(n*sizeof(double));

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

{double S 1=0,S2=0;

for(int j=0;j<=i-1 ;j++) S1+=A[i][j]*tmp[j]; for( j=i+1;j<n ;j++) S2+=A[i][j]*X0[j];

tmp[i]=(double)(A[i] [n] - S1 - S2)/(double)A[i] [i]; }

return tmp;

}

//test de convergence

short test(double *X0,double *eps,double *Xk,int n) {for(int i=0;i<n;i++)

if( fabs(Xk[i] - X0[i]) > eps[i]) return 0;

return 1;

}

//resolution

double *Solve(double **A,double *X0,double *eps,int n,int kmax=6) {for(int k=0;k<kmax;k++)

{double *Xk=Xkplus1 (A,X0,n);

short ok=test(X0,eps,Xk,n);

if(ok) return Xk;

X0=Xkplus 1 (A,X0,n);

}

return NULL;//en cas pas de solution en kiem itération }

void main()

{char rep;

do

{clrscr();

cout<<" Méthode De Gauss - Seidel\n";

int dim;

cout<<"\nEntere La Dimension Du Matrice :";

cin>>dim;

//X0 initial

double *X0=(double*)malloc(dim*sizeof(double)); for(int t=0;t<dim;t++) X0[t]=1;

//le vecteur epselon

double *eps=(double*)malloc(dim*sizeof(double)); for( t=0;t<dim;t++) eps[t]=0.2;

//La matrice augmentée A

double * *A=DefMat(dim,dim+1);

charger(A,dim,dim+1 );//Chargement de A

cout<<endl;

int ok=dominante(A,dim);

if(ok)//test de la domination

{//Resolution

double * Sol=Solve(A,X0,eps,dim);

if(Sol) for(t=0;t<dim;t++) cout<<"X"<<t<<" = "<<setprecision(2)<<Sol[t]<<endl; else cout<<"On a pas une solution par cette méthode ! ! !";

free(Sol);//libération du mmoire

}

else cout<<"\nLa Matrice n'est pas dominante ! ! !\n"; //libération du mémoire

free(A);free(X0);free(eps);

cout<<"\nVoulez vous répéter o/n : ";cin>>rep;

}while (rep == 'o');

}

II - Interpolation D'une Fonction Par Un Polynôme

On a un ensemble de n+1 points : x0 .... X_n et pour chaque point on connaît la valeur d'une fonction f inconnue (à-priori): f(x0) ... . f(x_n)

La question qui se pose c'est : Quelle est la valeur de f sur les points intermédiaire ?

Pour cela on doit supposer un modèle mathématique de f qui est souvent un polynôme.

Pour l'interpolation polynomiale on a 2 méthodes :

Méthode De Newton

Méthode De Lagrange