Methodes de Calculs Numeriques Resolues en Langage c - Dr. Hatem Mokhtari

8/3/2019 Methodes de Calculs Numeriques Resolues en Langage c - Dr. Hatem Mokhtari

1/82

CALCULS NUMERIQUES RESOLUS EN

LANGAGE CRappels de Cours, Exercices corrigs, Algorithmes, et leurs Codes C

Auteur : Dr . Hatem MOKHTARI, Matre de Confrences

Universit de Constantine, Facult des Sciences de Lingnieur, Dpartement

dElectronique


2/82

2/82

Prambule

Dans un monde o les quations ne peuvent avoir de solutions analytiques par le calcul direct,

intervient lanalyse et le calcul numrique qui permettent justement de palier cette lacune et

de proposer une solution approche au problme. Les domaines dapplication sont trsdiversifis et pour chaque problme ses conditions aux limites qui dictent le comportement de

la solution (signal lectrique, pression, temprature, etc .).

Lobjectif de ce polycopi est de donner une base de calcul avec un bref rappel de la thorie

mais en insistant plus sur laspect pratique que le formalisme thorique. Afin de ne pas

surcharger le document de thorie et dinterminables dmonstrations, nous avons prfr la

procdure suivante : poser le problme, rappeler les principes fondamentaux de la mthode

numrique en question, et daborder directement des applications concrtes. Nous navons

nanmoins pas nglig laspect algorithmique qui est la base mme dune programmation

exacte et russie. Cest la raison pour laquelle nous avons propos, avant chaque code en C du

problme en question, lalgorithme qui permet justement dcrire le programme de faon

lisible et comprhensible. Le code C est bien document avec des commentaires sur les lignes

juges essentielles au traitement dinstructions ou de boucles permettant lexcution du

programme. A travers ce document, le lecteur peut se rendre compte du ct applicatif qui est

mis en exergue avec des problmes classiques souvent rencontr en lectronique, en

lectromagntisme, en chimie ou en physique de faon gnrale.

Finalement, ce document a pour vocation et objectif de donner ltudiant ou au chercheur un

code C qui a t test et dont lalgorithme peut tre adapt dautres problmes en effectuant

de simples modifications.

Limagination est plus importante que le savoir .Albert Einstein

Dr. Hatem MOKHTARI | Calculs Numriques rsolus en Langage C


3/82

3/82

Table des Matires

Chapitre I : Rsolution dEquations Algbriques Non Linaires

Mthode de la Bissection, Mthode de Newton,

Mthode du Point Fixe

Chapitre II : Rsolution des systmes dquations de forme matricielle A.x = b

Mthode du Pivot de Gauss

Mthode de Jacobi

Mthode de Gauss-Seidel

Mthode de Newton-Raphson

Chapitre III : Rgression Linaire au sens des Moindres Carrs

Approximation de donnes exprimentales par : y = a.x + b

Chapitre IV : Interpolations Polynomiales

Mthode de Lagrange

Mthode de Newton

Chapitre V : Mthodes dIntgration Numrique

Mthode des Rectangles

Mthode des Trapzes

Mthode de Simpson

Mthode de Quadrature de Gauss-Legendre

Chapitre VI : Rsolution dquations diffrentielles ordinaires

Mthode dEuler

Mthode de Runge-Kutta

Rfrences Bibliographiques


4/82

4/82

CHAPITRE I

Rsolution dEquations Algbriques Non Linaires

Mthodes Etudies :

Bissection, Newton,

Point Fixe

I.1. Introduction


5/82

5/82

I .2. La mthode de la bissection

Une fonction change de signe au voisinage de la racine. Une racine se trouve dans lintervalle

[a,b] sif(a) etf(b) ont des signes opposs. Toutefois un changement de signe peut tre d non

pas seulement une racine mais aussi une singularit. Alors la mthode est utilise pour

trouver des solutions initiales.

Algorithme de la Bissection

Initialisationa(0) = a,b(0) = b, etx(0) = [a(0)+b(0)]/2

Boucle

Pour k 0 et tant que = |b(k) a(k)| >

Si f(x(k))f(a(k)) < 0 a(k+1) = a(k), b(k+1) = x(k)

Si f(x(k))f(b(k)) < 0 a(k+1) = x(k), b(k+1) = b(k)

x(k+1) = a(k+1)+b(k+1)

Afficher x(k)


6/82

6/82

Fin

Code C de la mthode de la bissection// Le but est de trouver la solution de lquation Ln(x) = 0 (i.e. vrifier que x = 1.0 comme

solution)

// lintervalle est [0,5]

Nom de fichier : BISSECTION.CPP

#include #include #include

#define A 0.0 // Borne Infrieure#define B 5.0 // Borne Suprieure#define N 100 // Nombre d'itrations

#define EPS 1.0e-15 // Prcision demande

double f(double x){

return log(x); // fonction tester Ln(x) = 0 dans [0, 5]}

void main(){

double *a, *b, *x;

a = (double *)calloc(N,sizeof(double));b = (double *)calloc(N,sizeof(double));x = (double *)calloc(N,sizeof(double));

a[0] = A; // Initialisation du pointeur *ab[0] = B; // Initialisation du pointeur *bx[0] = (a[0]+b[0])/2.0; // Initialisation du pointeur *x

int k=0;

while( k>=0 &&fabs(b[k] - a[k]) > EPS ) // Arrt si un des deux critres est faux

{if( f(x[k])*f(a[k]) < 0 ){

a[k+1] = a[k];b[k+1] = x[k];

}

if( f(x[k])*f(b[k]) < 0 ){

a[k+1] = x[k];b[k+1] = b[k];

}


7/82

7/82

x[k+1] = (a[k+1]+b[k+1])/2.0;

printf("K = %d \t X = %18.16g\n", k, x[k]);// Impression du nombre d'itrations, et la solution Ln(x) = 0k++;

}delete [] a; // Libration de la mmoiredelete [] b; // Libration de la mmoiredelete [] x; // Libration de la mmoire

}

Le rsultat est rsum par la fentre ci-dessous. La mthode converge aprs 57 itrations

donnant 1 comme solution Ln(x) = 0

I.3. La mthode de Newton


8/82

8/82

On utilise cette mthode lorsque lon peut calculer les drives def(x) de faon analytique. Le

principe de cette mthode consiste tracer la tangente enxi et de chercher lintersectionxi+1avec laxe horizontal et ainsi de suite.

Algorithme de la Mthode de NewtonDonnes : N, x, , f(xi) et f(xi)BouclePour i=1,NOn calculera :

= ()()Si | |< alors est une racineSinon on continue les itrations (cad i = i+1)

Code C de la mthode de Newton


9/82

9/82

// Dans lexemple ci-dessous nous cherchons la racine de lquation Ln(x) = 0 dans

lintervalle ]0, +[ avec x0 comme valeur initiale choisie par lutilisateur

Nom de fichier :Newton.cpp

#include

#include #include

#define EPS 1.0e-15 // Prcision voulue#define N 1000 // Nombre maximal d'itrations

double f(double x){return log(x); //Ln(x) comme test

}

double df(double x){

return 1.0/x; // Drive de Ln(x)}

voidmain(){

double x0; // Valeur Initialedouble *x; // tableau des valeurs Xi

x = (double *)calloc(N,sizeof(double));

printf("entrer la valeur initiale X0: \n");scanf("%lf",&x0);//L'utilisateur choisi une valeur de dpart

x[0] = x0;

for(int i=0;i


10/82

10/82

Remarque : La commande exit (0) ;permet de sortir du programme et darrter dimprimer

les valeurs dei et x[i+1]

Le rsultat est rsum par la fentre ci-dessous. La mthode converge aprs 6 itrations

donnant 1 comme solution Ln(x) = 0

Application de la mthode de Newton : Circuit RL avec diode de redressement

Le circuit ci-dessous prsente un redresseur simple alternance sur une charge inductive RL.

La rsolution de lquation diffrentielle :()= + (1)lorsque la tension ()= ()on dmontre [1] que le courant dans la charge R L :

(2)

Avec

(3)

(4)

(5)

Pour que le courant i(t)sannule, il faut trouver la solution de lquation

(6)


11/82

11/82

Il est clair quil ny a pas de solution analytique lquation (6). Nous nous proposons donc

dutiliser la mthode de Newton vu quil existe une drive de la fonction

()= ( ) + (7)La drive de f(t) est :

()= ( ) (8)/*Le programme en C de la rsolution de lquation (6) et utilisant la Mthode de Newton est

donn ci-dessous. Pour le calcul nous avons pris les valeurs numriques suivantes :L = 0.01 H

R = 5

f = 50 Hz ou T = 0.02 sec (= 314.159 rd/s)

= L/R = 0.002 secLa prcision EPS = 10

-15

*/

Nom de fichier :Newton_CircuitRL.cpp


#define EPS 1.0e-15 // Prcision voulue

#define N 1000 // Nombre maximal d'itrations#define Omega 314.159#define L 1.0e-2#define R 5.0#define Tau 2.0e-3#define phi atan(L*Omega/R)#define T 0.02

double f(double t) // la fonction f(t) = 0 dont il faut chercher les racines{

return sin(Omega*t - phi) + sin(phi)*exp(-t/Tau); // fonction test

}

double df(double t) // la driv de f(t){

return Omega*cos(Omega*t - phi) - (sin(phi)*exp(-t/Tau))/Tau;}

voidmain(){

double *x; // tableau des valeurs Xi

x = (double *)calloc(N,sizeof(double));


12/82

12/82

x[0] = T/2; // on initialise t T/2 vu que le courant s'annule aprs cette valeur

for(int i=0;i


13/82

13/82

#define EPS 1.0e-15 // Prcision voulue

double g(double x){

return exp(-x); // fonction test

}

voidmain(){

double x0,*x;x = (double *)calloc(N,sizeof(double)); // allocation dynamique

printf("Entrez une valeur initiale X0:");scanf("%lf",&x0);

x[0] = x0; // Initialisation de la valeur de dpart

int k=0;do{

x[k+1] = g(x[k]); // calcul des termes de la srie x(k+1)

if(fabs(x[k+1] - x[k]) EPS );// continuer les calcul tant que le critre n'est

pas atteind

delete [] x;}

Le rsultat est rsum par la fentre ci-dessous avec x0 = 0.5 comme valeur initiale


14/82

14/82

CHAPITRE II

Rsolution des systmes dquations de forme Matricielle A.x = b

Mthodes tudies :

Pivot de Gauss,

Jacobi,

Gauss-Seidel,

Newton-Raphson


15/82

15/82

II.1. Introduction

II.2. Mthode du Pivot Gauss

Il sagit de trouver les racines de lquation matricielle A .x = b avec x comme vecteur

inconnue,Aune matrice et bvecteur donn (connu).

Cette mthode est la plus simple et la plus classique, elle correspond exactement ce que lonfait " la main" :

de la premire quation, on exprime la premire inconnue x1en fonction des autresinconnues, puis on substitue cette expression dans les autres quations du systme, faisant

apparatre ainsi un sous-systme dans lequelx1nintervient pas,

on itre le mme schma jusqu ce que la matrice du systme devienne triangulaire

suprieure (toute la partie infrieure de la matrice sous la diagonale est remplie de zros),

une fois la triangularisation termine, on calculexn, puisxn-1, et ainsi de suite jusqux1;lesdiffrentes solutions sont ainsi calcules de proche en proche.

Le principe de triangularisation permet ainsi de transformer le systme initial

par un systme triangulaire quivalent de la forme

Pour liminer x1de la premire quation, on divise par le coefficient a11de la matrice ; ce

coefficient sappelle le pivot. Il est clairement indispensable que ce coefficient ne soit pas nul.

Nanmoins, ce critre, parfaitement acceptable mathmatiquement, nest pas suffisant

numriquement. En effet, ce coefficient peut tre trs faible, entranant ainsi lapparition de

trs grandes valeurs, et donc de grands risques dimprcisions et derreurs numriques.

En fait, la mthode du pivot de Gauss est rigoureuse mathmatiquement, mais elle conduit

gnralement de nombreux calculs ; la mthode est donc assez sensible aux erreurs

numriques, en particulier pour les systmes de grande taille.


16/82

16/82

Une implmentation de cette mthode doit donc imprativement mettre en oeuvre une

stratgie de choix du pivot, consistant recherche le plus grand pivot en valeur absolue ou en

module si lon utilise une matrice valeurs complexes. On a pour cela plusieurs possibilits :

la premire mthode, la plus simple, consiste observer que lon peut indiffremment

inverser lordre des quations, sans changer le systme ni sa solution ; on recherche donc lepivot dfini par || pour 1 et on permute les quations si ncessaire : larecherche du plus grand pivot se fait donc par colonne,

la deuxime mthode consiste rechercher le plus grand pivot par ligne plutt que par

colonne ; on recherche donc le pivot dfini par ||pour 1 linconvnient majeur de cette mthode est quelle ne conserve pas le systme initial, mais

quil faut obligatoirement tenir compte dun ragencement des solutions ; cette mthode est

donc plus complique que la prcdente puisque le programme doit mmoriser toute la

squence de ragencements successifs afin de pouvoir remettre les solutions dans le bon

ordre,

la troisime mthode consiste mixer les deux mthodes prcdentes, et donc chercherle

pivot dfini parmax(||,||) pour 1 ; la recherche se fait donc sur lignes etcolonnes : cettemthode a gnralement les mmes inconvnients que la prcdente.

Le code C ci-dessous illustre une implmentation de cette mthode de rsolution ; il est

constitu des blocs suivants :

les quatre premires fonctions al l oc_vect eur , f r ee_vect eur , al l oc_mat r i ceetf r ee_mat r i cesont des fonctions gnrales permettant de grer dynamiquement lestockage des matrices et vecteurs ; ces fonctions sont utilises ici, mais ne font pas partie de

lalgorithme du pivot de Gauss,

les fonctions t r ouve_pi vot , per mut e_l i gnesetgauss correspondent larsolution par le pivot de Gauss,

la fonction cont r ol enest l que pour vrifier que la solution trouve satisfait bien lesystme initial,

enfin, les fonctions r andometmai n permettent de tester avec un exemple particulier.

Nom de fichier : PivotGauss.cpp

#include


#define EPS 1.0e-12

//--------------------------------------------------------------// Fonction dallocation dun vecteur (n)//--------------------------------------------------------------double * alloc_vecteur (int n){

return (double *)malloc(n*sizeof(double));}


17/82

17/82

//--------------------------------------------------------------// Fonction de dsallocation d'un vecteur (n)//--------------------------------------------------------------void free_vecteur (double *v)

{if (v!=NULL) free((void *)v);

}

//--------------------------------------------------------------// Fonction d'allocation d'une matrice (n,n)// Remarque : on dsalloue en cas dchec en cours !//--------------------------------------------------------------double ** alloc_matrice (int n){

double **a;

a=(double **)malloc(n*sizeof(double *));if (a!=NULL){

for (int i=0; i


18/82

18/82

// Fonction de recherche du pivot maximum sur une colonne// et partir d'une ligne spcifie//--------------------------------------------------------------int trouve_pivot (double **A, int n, int ligne, int colonne){

double v,max;inti,pivot;for (i=ligne, max=0.0; imax){

pivot=i; // pivot identifie la ligne contenant le pivot max.max=v;

}}

if (max


19/82

19/82

int gauss (double **a, double *b, double *x, int n){

interr,pivot,indpivot,ligne,colonne;double **A,*B,coef;

A=alloc_matrice(n);if (A==NULL) return 0; // allocation matrice A

B=alloc_vecteur(n); // allocation vecteur B

if (B==NULL){

free_matrice(A,n);return 0;

}

for (ligne=0; ligne


20/82

20/82

break;}

}

if (err==1) // si on na pas rencontr derreur

{for (ligne=n-1; ligne>=0; ligne--) // calcul des solutions, en remontant

de la{ // dernire jusqu la premire

coef=B[ligne];for (colonne=1+ligne; colonne


21/82

21/82

// 1. on alloue dynamiquement a et b (x=b+n)// 2. la matrice a est alatoire entre -1 et +1, idem pour b// 3. on affiche a et b// 4. on calcule la solution x par la fonction gauss// 5. on affiche x, puis la diffrence (ax-b)

// 6. on dsalloue a et b

main (){

double **a,*b,*x;int n=5;

a=alloc_matrice(n); if (a==NULL) return 0;b=alloc_vecteur(2*n);

if (b==NULL){

free_matrice(a,n);return 0;

}

x=b+n;for (int i=0; i


22/82


23/82

23/82

Le code C ci-dessous regroupe les mthodes itratives cites plus haut, et en rajoutedautres (cf. littrature en Rfrences)

/*Rsolution de A x = b par :

Cramer , Inversion , Gauss , Gauss pivot partiel ,Gauss pivot total , Jordan , Dcomposition LU croot ,LU doolittle , Cholseky , et les methodes itratives de Jacobie et Gauss-Seidel.*/

#include "stdafx.h"

#include #include #include // -------------------------------------------------------------// Fonctions utiles pour la rsolution par Cramer et inversion// -------------------------------------------------------------

// fonction d'affichage matricevoid aff_mat(double a[19][19],int n){

int i,j;

printf("\n\n");for (i=0;i


24/82


25/82

25/82

// Mettre Zero les elements qui doivent etre des zro

void zero(double a[19][19],double b[19],int n){

int i,j;double eps=1e-4;for(i=0;i


26/82

26/82

comatrices(a,c,k,j,n);s = s + powl(-1,k+j)*a[k][j]*det(c,k);}return(s);

}

// -------------------------------------------------------------// Rsolution Par Cramer// -------------------------------------------------------------

void cramer(double a[19][19],double b[19],int n){

double A[19][19],x[19],deter;int i,j,k;

deter=det(a,n);

if (deter==0){printf("\n => Determinant nul, pas de solutions \n\n");system("PAUSE");//main();}

for(j=0;j


27/82

27/82

{printf("\n => Matrice non inversible, pas de solutions \n\n");system("PAUSE");

}

for(i=0;i


28/82

28/82

p=a[i][k]/a[k][k];for (j=k;j=0;i--){s=0;for(j=i+1;j


29/82

29/82

//rductionfor(i=k+1;i


30/82

30/82

temp=a[k][j];a[k][j]=a[ligne][j];a[ligne][j]=temp;

}

temp=b[k];b[k]=b[ligne];b[ligne]=temp;

for(i=0;i


31/82

31/82

zero(a,b,n);printf("\n--------- Gauss avec pivot total ---------\n");printf("\n * La matrice reduite :");aff_syst(a,b,n);

printf("\n * La resolution donne :\n\n");for (i=0;i


32/82

32/82

for(i=0;i


33/82

33/82

for(i=n-1;i>=0;i--){s=0;for(j=i+1;j


34/82

34/82

s=0;for (k=0;k


35/82

35/82

for (i=0;i


36/82

36/82

// -------------------------------------------------------------// Rsolution Par Jacobie// -------------------------------------------------------------

void jacobie(double a[19][19],double b[19],int n)

{double x[19],x1[19],x2[19],s,eps=1e-4;int i,j,k,iter=0;

//initialisation du vecteurprintf("\n * Veuillez initialisez le vecteur solution : \n\n");for (i=0;i


37/82

37/82

for (j=i+1;j


38/82

38/82

printf("\n\n * Nombre d'equation-inconues : \n\n * N = ");scanf_s("%d",&n);

reprendre_choix:

printf("------ => donner votre choix ------ : ");scanf_s("%s",&valider);

switch(valider){case 'A' : remplir(a,b,n);cramer(a,b,n); break;case 'B' : remplir(a,b,n);inversion(a,b,n); break;case 'C' : remplir(a,b,n);gauss(a,b,n); break;case 'D' : remplir(a,b,n);gauss_pivot_partiel(a,b,n); break;

case 'E' : remplir(a,b,n);gauss_pivot_total(a,b,n); break;case 'F' : remplir(a,b,n);jordan(a,b,n); break;case 'G' : remplir(a,b,n);LU_doolittle(a,b,n); break;case 'H' : remplir(a,b,n);LU_crout(a,b,n); break;case 'I' : remplir(a,b,n);cholesky(a,b,n); break;case 'J' : remplir(a,b,n);jacobie(a,b,n); break;case 'K' : remplir(a,b,n);gauss_seidel(a,b,n); break;case 'X' : printf("\nProgramme interompu par l'utilisateur.......\n\n");system("PAUSE");exit(0); break;default : goto reprendre_choix;}printf("\n");system("PAUSE");

return 0;}


39/82

39/82

CHAPITRE III

Rgression Linaire au sens des moindres carrsApproximation de donnes exprimentales par :

y = a.x +b


40/82

40/82

III .1. Problmatique

Nous nous intressons un problme qui se pose souvent aux exprimentateurs. A l'issue

d'une exprience, un exprimentateur a souvent enregistr des donnes relatives par exemple

l'observation d'un phnomne physique. Ces donnes sont toujours entaches de bruit (le

plus souvent d aux instruments utiliss). L'exprimentateur souhaite nanmoins comparer ses

donnes un modle. Nous ne nous intresserons ici qu'au cas o le modle est connu.L'exprimentateur souhaite donc uniquement s'assurer que le phnomne observ suit bien la

loi o le modle qu'il connat. Il souhaitera galement dterminer les valeurs numriques desparamtres intervenant dans ce modle, et qui ne sont pas connues priori.

III.2. Ajustement dune fonction linaire :y = a.x + b

L'exprimentateur est en possession de n donnes (xi, yi) issues de mesures par exemple. Laloi connue s'exprime comme y =f(x, p1, p2, , pm). Cette loi dpend des paramtres pqui ne

sont pas ncessairement connus. Pour vrifier si les donnes se superposent correctement laloif, il suffit de calculer les carts yi-f(x,pj) en faisant varier la valeur de pj jusqu' ce que

l'cart soit minimal (o nul si l'accord est parfait). Il faut bien videmment raliser ce calcul

pour tous les points exprimentaux. Les statistiques nous offrent une manire lgante de

calculer cela. On introduit pour cela une variable dpendant des paramtres pjque l'on

appelle 2. Cette variable est dfinie comme

On va ensuite chercher l'ensemble de paramtres pjqui va minimiser

2

Dans ce cas prcis, 2s'exprimera par lquation quadratique :

On cherche minimiser cette grandeur, on va donc chercher satisfaire les conditions

Et

on en dduit que

Et


41/82

41/82

On trouve ainsi les deux paramtres a et b qui minimisent le2, c'est dire les paramtres qui

fournissent le meilleur accord entre les donnes exprimentales (xi, y

i)et la fonction y. La

valeur numrique de 2 va nous renseigner sur cet accord. Une valeur nulle indiquera un

accord parfait entre les donnes et le modle, plus la valeur sera grande, moins bon sera

l'accord. C'est ensuite l'utilisateur de cette mthode de dterminer quelles valeurs peuvent

tre satisfaisantes ou pas.

Exemple dapplication

Soit les donnes exprimentales du tableau ci-dessous.

x y

0 1

1 1,5

2 2,1

3 2,6

4 3,5

5 4,9

6 5,3

7 6,2

On cherche donc les paramtres a et b qui minimisent2


#define N 8

double a, b;

// fonction qui calcul a et b selon les quations ci-dessusvoidcalcul_a_b(int n, double *a,double *b, double *x, double *y){

double A=0,B=0,C=0,D=0;double S1 =0.0,S2 = 0.0;double S3=0.0, S4=0.0;

for(int i=0;i


42/82

42/82

A *= n;B = S1*S2;C = n*S3;D = S1*S1;

*a = (A-B)/(C-D);*b = (S3*S2 - (A/n)*S1)/(C - D);

}

//Fonction qui calcule X2 minimaledouble Khi2(int n, double a,double b, double *x,double *y){

double valeur;

valeur = 0.0;

for(int k=0;k


43/82

43/82

// calcul de a et b

calcul_a_b(N,&a,&b,x,y);

printf("a = %18.16g \n\n",a);printf("b = %18.16g \n\n",b);

// callcul de X2double KHI2 = Khi2(N,a,b,x,y);printf("KHI2 = %18.16g \n\n",KHI2);

}

Lexcution de ce programme nous donne le rsultat suivant pour notre exemple prcis


44/82


45/82

45/82

Soit une fonctionf (inconnue explicitement)

connue seulement en certains pointsx0,x1xn

ou valuable par un calcul coteux.Principe :

reprsenterfpar une fonction simple, facile valuer

Problme : il existe une infinit de solutions !

Il faut se restreindre une famille de fonctions

polynmes,

exponentielles,

fonctions trigonomtriques

Interpolation polynomiale

polynmes de degr au plus n polynmes de Lagrange

diffrences finies de Newton

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8-4

-3

-2

-1

0

1

2


46/82

46/82


47/82

47/82


48/82

48/82

Le code C de linterpolation de Lagrange

// polynomeLagrange.cpp : dfinit le point d'entre pour l'application console.//

#include "stdafx.h"#include #include

double lagrange(double *x,double *y,int n,double val){

int i,j;double prod;

double som;som=0;for(i=0;i


49/82

49/82

int _tmain(int argc, _TCHAR* argv[]){

double val,res;double x[50],y[50];

int i,j;int n;printf("donner le degre du polynome \n");scanf_s("%d",&n);

for(j=0;j


50/82

50/82

IV.1. Mthode dinterpolation de Newton

Lalgorithme de Newton propose dinterpoler des donnes exprimentales (Xi,Yi) par le

polynme suivant :

()= + ( ) + ( )( ) + + ( )( ) ( )Avec

()= pour i=0,,nOn dmontre que le polynme Pn(x) scrit sous la forme :()= + ( ) +

( )( ) + +

! ( )( ) ( )On posera Cn

=

!Les

ny0se calculent par la formule gnrale :

= ()

Avec

= !!( )!


51/82

51/82

Exemple de calcul :

Nous voulons produire le polynme de Newton pour la fonction reprsente par lchantillon

du tableau suivant :

xi 0 1 2 3

yi 1 4 8 14

Le programme en C ci-dessous illustre notre exemple

/// INTERPOLATION POLYNOMIALE DE NEWTON

#include "stdafx.h"#include

#include #include

const double h=1.0; // Pas des abscisses quidistants Xi+1 - Xiconst int n=3; // degr du polynme

// Polynme de Newton pour la variable tdouble P(double t, double *x, double *C){

double val, Prod;

val = 0.0;

for(int i=1;i


52/82

52/82

}

// Combinaison de p parmi ndouble comb(int m, int p)

{return fact(m)/(fact(p)*fact(m-p));

}

//Calcul des Delta Y0 : somme des K termesdouble DeltaY(double *y,int k)

{double value = 0.0;

int m=0;do

{value += comb(k,m)*y[k-m]*pow(-1.0,m);

m++;}

while(m


53/82

53/82

free(x);

free(C);free(y);

system("pause");

return 0;}

En excutant ce programme, pour x=2 on trouve le rsultat suivant :

Ce qui correspond bien la valeur pour x=2 (cad y = 8)

Le polynme, aprs tous calculs, se rduit :

()= + + Prenons un autre exemple un peu plus complexe o le nombre de points est important

La fonction tudier est donne par le tableau ci-dessous :

Xi Yi

-10,00 0,37

-9,00 0,44

-8,00 0,53

-7,00 0,61

-6,00 0,70

-5,00 0,78

-4,00 0,85

-3,00 0,91

-2,00 0,96

-1,00 0,990,00 1,00

1,00 0,99

2,00 0,96

3,00 0,91

4,00 0,85

5,00 0,78

6,00 0,70

7,00 0,61

8,00 0,53

9,00 0,4410,00 0,37


54/82

54/82

Constatons quil y a 21 valeurs pour xi et 21 pour yi. Il suffit donc de poser n = 20 et le tour

est jou. Noublions pas que le pas constant h = 1 ici aussi et que les enregistrements de xi et

yi doivent bien tre renseigns dans le code source. Ce dernier scrit alors comme suit :

#include "stdafx.h"#include #include

#include

const double h=1.0;

const int n=20; //Polynme de degr 20

double P(double t, double *x, double *C)

{double val, Prod;

val = 0.0;

for(int i=1;i


55/82

55/82

{

value += comb(k,m)*y[k-m]*pow(-1.0,m);

m++;

}while(m


56/82

56/82

ree(C);

free(y);system("pause");

return 0;}

Lexcution du programme nous donne le rsultat suivant :

La valeur de 0.9600000000041672 correspond bien P20(2) qui en fait bien la valeur de 0.96

dans le tableau

Si nous souhaitons calculer une valeur intermdiaire de yi pour xi autre que celle du tableau, il

suffit de remplacer la valeur choisi dans le code : soir la ligne

value = P(2.0, x, C);

Exemple : si x=0.5, alors le rsultat est P20(0.5) = 0.99747872, ce qui est proche de 1,valeur de y pour x=0.


57/82

57/82

CHAPITRE V

Intgration numrique

Mthodes tudies :

Carrs, Trapzes,

Simpson,

Quadrature de Gauss-Legendre


58/82


59/82


60/82

60/82

Algorithme de la Mthode des Rectangles

Donnes : f(x), a, bLuti lisateur dfini la prcision souhaite et donc N

On dfinit un Tableau x[ ] de dimension NCalcul : h = (b-a)/NSomme = 0.0Pour i = 1 N{

x[i ] = a + i*hSomme = Somme + f(x[i] + h/2)

}SRectangles = h*Somme

Afficher SRectangles

Fin

Exemple ;

On souhaite calculer lintgrale de la fonction suivante :

()= Dans lintervalle : [0, 1]

Le code C de la Mthode des Rectangles


#define a 0.0 // Borne infrieure d'intgration#define b 1.0 // Borne suprieure d'intgration#define N 100 // Nombre de points

double f(double x)

{ return exp(-x); // fonction intgrer}

void main(){

double *x;

x = (double *)calloc(N, sizeof(double)); // Allocation dynamique des abscissesxi

double Somme, I;


61/82

61/82

double h = (b-a)/N; // Pas d'intgration

Somme = 0.0;for(int i=1;i


62/82

62/82

V.4.Mthode des Trapzes

Le principe de cette mthode est analogue celui de l'intgration par une srie de rectangles.

Dans cette mthode on cherche augmenter la prcision du calcul tout en vitant la

dissymtrie qui apparat dans la dfinition de l'intgration par rectangles. Nous allons donc ici

aussi tabuler en (n+1) points f0,f1,fndans l'intervalle d'intgration [x0,xn]. On va ensuiteinterpoler linairement (polynme d'ordre 1, c.a.d. une droite) pour approximer f(x) entre

deux points tabuls. On va donc remplacer les arcs xi, xi+1par leurs cordes

L'intgration va alors se faire en sommant l'aire des trapzes, soit

si l'chantillonnage des points est rgulier, c.a.d. sixi+1 xi= halors l'intgrale s'exprimera

en effet chaque trapze aura chacun de ces cts en commun avec les trapzes adjacents,

l'exception du premier et du dernier qui n'ont qu'un ct en commun.


63/82

63/82

Algorithme de la Mthode des Trapzes

Donnes : f(x), a, bLuti lisateur dfini la prcision souhaite et donc N

On dfinit un Tableau x[ ] de dimension NCalcul : h = (b-a)/NSomme = 0.0Pour i = 1 N-1{

x[i ] = a + i*hSomme = Somme + f(x[i] + h/2)

}Finpour

Somme = Somme + 0.5*( f(a) + f(b) )

STrapzes = h*Somme

Afficher STrapzes

Fin

Exemple ;

On souhaite calculer lintgrale de la fonction suivante :

()= Dans lintervalle : [0, 1]Le code C de la Mthode des Trapzes


#define a 0.0 // Borne infrieure d'intgration

#define b 1.0 // Borne suprieure d'intgration#define N 100 // Nombre de points

double f(double x){

return exp(-x); // fonction intgrer}

voidmain(){

double *x;

x = (double *)calloc(N, sizeof(double)); // Allocation dynamique des abscisses


64/82


65/82


66/82

66/82

i = i+1}Finpour

Sommepaire = 0.0

Pour i = 1 N-1{

Si i paire alorsx[i ] = a + i*h

Sommepaire = Sommepaire + f(x[ i])Sinon

i = i+1}Finpour

Somme = SommePaire + SommeImpaire

STrapzes = (h/3)*( f(a) + f(b) + Somme)

Afficher STrapzes

Fin

Le code C de la Mthode de Simpson

// METHODE D'INTEGRATION : SIMPSON


#define a 0.0 // Borne infrieure d'intgration#define b 1.0 // Borne suprieure d'intgration#define N 100 // Nombre de points

double f(double x){

return exp(-x); // fonction intgrer}

void main(){

double *x;

x = (double *)calloc(N, sizeof(double)); // Allocation dynamique des abscissesxi

double Somme_Paire, Somme_Impaire, I;

double h = (b-a)/N; // Pas d'intgration


67/82

67/82

int i;

Somme_Impaire = 0.0;for(int j=0; j


68/82

68/82

intgrer, on voit clairement lamlioration de la prcision de gauche droite dans le tableau

ci-dessus.

V.5. Mthode de Quadrature de Gauss-Legendre

Le domaine d'intgration [a, b] doit tre chang (au moyen d'un changement de variable) en [-1, 1] avant d'appliquer les mthodes de quadrature de Gauss. Le changement se droule ainsi :

L'approximation de la valeur de l'intgrale devient :

o xi sont les racines du polynme de Legendre de degret o wi sont les poids de ces racines,

Les premiers polynmes sont alors :

...

Une excellente prcision est garantie ds que n>2. Des tables permettent d'obtenir les valeurs

des points et leurs poids.

Exemple pour n = 3, Abscisses et Poids

mro Abscisse Poids

1

2

3


69/82

69/82

Code C de la mthode de Gauss-Legendre : Intgration

=

#include

#include

#include

#define EPS 3.0e-11

// Cette fonction calcul les poids w et les Abscisses x

void ploynomes_GaussLegendre(double x1,double x2,double *x,double

*w,int n)

{ int m,j,i;

double z1,z,xm,xl,pp,p3,p2,p1;

m=(n+1)/2;

xm=0.5*(x2+x1);

xl=0.5*(x2-x1);

for (i=1;i


70/82


71/82

71/82

Problme :On sait que le champ radiolectrique reu par un mobile GSM en zone urbaine suit une

distribution log-normale lorsque la puissance reue est exprime en Watt. Comme la notion

de dBm est plus largement utilise, cette mme puissance reu suit une distribution

gaussienne (ou normale) quand elle est exprime en dBm. La densit de probabilit estdonne par lquation :

()= 12 ()

Avec m la valeur mdiane (assurant 50% de probabilit) et lcart type

Loprateur Mobilis, par exemple, souhaite savoir avec quelle probabilit de couverture un

utilisateur de son rseau peut tre desservie avec un niveau de puissance radiolectrique

suprieure x0 = -50 dBm et infrieur x1 = 0 dBm, sachant que la mdiane de cette

puissance est de m= -75 dBm. Lcart type est de = 7 dB.

Solution :On calcule la probabilit par la formule :

( > ) = () Le programme en C (hrit du code C ci-dessus) et simplement crit en changeant la fonction

f(x) et les bornes dintgration. Les valeurs de m et sont des constantes que lon peut

dclarer avant le main() comme tant des constantes globales. Et le tour est jou !

// gausslegendre_GSM.cpp : dfinit le point d'entre pour l'application console.//#include "stdafx.h"#include #include #include

#define EPS 3.0e-11

#define S 7 // 7 dB cart type#define M1 -75.0 // -75 dBm de valeur mdiane#define PI 3.141592654#define N 100

// Cette fonction calcul les poids w et les Abscisses xvoid ploynomes_GaussLegendre(double x1,double x2,double *x,double *w,int n){

int m,j,i;double z1,z,xm,xl,pp,p3,p2,p1;


72/82


73/82


74/82


75/82


76/82


77/82


78/82

78/82

Lalgorithme de Runge Kutta dordre 4 est donn par les quations suivantes

Limplmentation de lexemple prcdent (voir Euler) par la mthode de Runge Kutta en C++

est donne ci-dessous

Code C++ :RUNGE-KUTTA4.CPP

#include "stdafx.h"#include #include #include #include

using namespace std;

#define h 0.1 // pas h#define N 20 // nombre de points

double f(double x,double y) // la fonction f(x,y){

return 1.3*exp(-x) - 2*y;}


double *x,*y; // tableau xn et yndouble k1,k2,k3,k4; // Les 4 variables de Runge-Kutta

x = (double *)calloc(N,sizeof(double));y = (double *)calloc(N,sizeof(double));

y[0]=5;

for(int n=0;n


79/82


80/82

80/82

Exercice 3

On se propose de rsoudre un problme classique en physique nuclaire. On considre

lquation de dsintgration dun noyau donne par :

dNdt

= NAvec comme condition initiale N(0)=N0

Pour utiliser la mthode Runge-Kutta, il suffit de poser f(x,y)= -y avec la condition initialey(0)=N0

La solution est donne par le code C++ ci-dessous

#include "stdafx.h"

#include #include #include #include

using namespace std;

#define h 0.5 // le pas h#define N 30 // nombre de points#define N0 10 // nombre de noyaux t=0#define lambda 0.5

double f(double x,double y) // la fonction f(x,y){

return -lambda*y; // la fonction f(x,y) = - lambnda*y}


double *x,*y; // tableau xn et yndouble k1,k2,k3,k4; // Les 4 variables de Runge-Kutta

x = (double *)calloc(N,sizeof(double));y = (double *)calloc(N,sizeof(double));

y[0]=N0;

for(int n=0;n


81/82


82/82

Documents

Methodes de Calculs Numeriques Resolues en Langage c - Dr. Hatem Mokhtari