Cours dAnalyse Numrique

Professeur Longin SOME,Laboratoire dAnalyse Numrique dInformatique et de Biomathmatique

(LANIBIO),Unit de Formation en Sciences Exactes et Appliques

(UFR/SEA), Universit de Ouagadougou.

Anne Acadmique 2012 - 2013

Table des matires

1 Chap 1 : Rsolution numrique de systmes linaires Ax = b 31.1 Gnralits sur les vecteurs et les matrices . . . . . . . . . . . 3

1.1.1 1.1 Les vecteurs de Rn= R R ::: R . . . . . . . . 31.1.2 Matrice de Mnp (R) . . . . . . . . . . . . . . . . . . . . 51.1.3 Applications des normes . . . . . . . . . . . . . . . . . 10

1.2 Mthodes "thoriques" de rsolution de Ax = b : Cramer,Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2.1 Mthodes des dterminants ou de cramer . . . . . . . . 121.2.2 Mthode de linverse . . . . . . . . . . . . . . . . . . . 12

1.3 Mthode directes : Gauss, Jordan, Choleski, ... . . . . . . . . 131.3.1 Rsolution des systmes triangulaires et diagonaux . . 131.3.2 Mthode directe de Gauss . . . . . . . . . . . . . . . . 151.3.3 Mthode de Jordan . . . . . . . . . . . . . . . . . . . . 171.3.4 Mthode de Choleski ou des racines carres . . . . . . . 18

1.4 Mthodes itratives de rsolution de systmes linaires : Ja-cobi, Gauss-Seidel, SOR . . . . . . . . . . . . . . . . . . . . . 211.4.1 Algorithmes des mthodes itratives . . . . . . . . . . . 211.4.2 Mthode itrative de Jacobi . . . . . . . . . . . . . . . 231.4.3 Mthode itrative de Gauss-Seidel . . . . . . . . . . . . 251.4.4 Mthodes SOR = Successive Over - Relaxation . . . . 26

2 Chap 2 : Interpolation et Approximation, Intgration et D-rivation numriques 282.1 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.2 Approximation (polynmiale) . . . . . . . . . . . . . . . . . . 34

2.2.1 Polynme epn de meilleure approximation uniforme (m.a. u) dune fonction ' . . . . . . . . . . . . . . . . . . 34

2.2.2 Polynme eqn de m. a. des moindres carrs de ' . . . . 371

2.2.3 Polynme eqn de m.a.m.c discrtes de ' . . . . . . . . . 392.3 Intgration numrique . . . . . . . . . . . . . . . . . . . . . . 40

2.3.1 Problmatique . . . . . . . . . . . . . . . . . . . . . . . 402.3.2 Formule de quadrature . . . . . . . . . . . . . . . . . . 402.3.3 Formules de Newton - cotes . . . . . . . . . . . . . . . 422.3.4 Formules dintgration numrique de Gauss . . . . . . 43

2.4 Drivation numrique . . . . . . . . . . . . . . . . . . . . . . . 44

2.4.1 Le problme . . . . . . . . . . . . . . . . . . . . . . . . 442.4.2 Quelques formules dapproximations des drives : M-

thode des dirences nies. . . . . . . . . . . . . . . . . 45

3 Chap 3 : Rsolution numrique des ODEs et des PDEs parla mthode des dirences nies 473.1 Gnralits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.2 Rsolutions des ODEs ou des systmes dODEs . . . . . . . . 48

3.2.1 Formules thoriques . . . . . . . . . . . . . . . . . . . . 483.2.2 Rsolution numrique par les dirences nies . . . . . 49

3.3 Rsolution numrique des EDP . . . . . . . . . . . . . . . . . 50

2

Chapitre 1

Chap 1 : Rsolution numriquede systmes linaires Ax = b

1.1 Gnralits sur les vecteurs et les ma-trices

1.1.1 1.1 Les vecteurs de Rn= R R ::: RDenition 1 b 2 Rn , b = (b1; :::;bi; :::;bn); bi2 R:

a) Vecteur ligneb = (b1; :::;bi; :::;bn) vecteur ligne, format 1 nb) Vecteur colonne

b =

0BBBB@b1::bi::bn

1CCCCA vecteur colonne, format n1Sous Matlab>>b = [b1;b2;b3] - % b vecteur ligne

b =b1 b2 b3

>>b = [b1;b2;b3]0 - % b vecteur colonne

3

b =b1b2b3

c) Vecteurs particuliers

- Vecteur nul ou de "0"( zeros en anglais)

z =(0; :::;0) ou z =

0@ 0::0

1ASous Matlab>> z= zeros (1,n); % vecteur nul (ligne) de n coordonnes>>z= zeros (1,n)0; % vecteur nul (colonne) de n coordonnes>>z= zeros (n,1); % vecteur nul (colonne) de n coordonnes- Vecteur de "1"(ones en anglais)

w =(1;1:::1) ou w =

0BB@11::1

1CCASous Matlab>> w= ones (1,n);% vecteur ligne de "1", n coordonnes>> w= ones (1,n);% vecteur colonne de "1", n coordonnes>> w= ones (n,1);% vecteur colonne de "1", n coordonnesRemarque : les vecteurs nuls ou de 1permettent, en programmation

informatique, dinitialiser respectivement dans les boucles de somme ou deproduit :

X

Y

:

d) Normes vectorielles :k:k

Denition 2 soit E un Rev. On appelle norme vectorielle dans E;toute application notek:k : E ! R+

v 7! kvkvriant les proprits suivantes :(i) kvk 0; kvk = 0 si v = 0E (positivit)(ii) kvk = jjkvk; 8 2 R;8 v 2 E (homognit circulaire)(iii) ku+ vk kuk+ kvk; 8 u;v 2 E (ingalit triangulaire)

4

Example 3 E = R ; kxk = jxj ( valeur absolue)E = R2; x =(x1 ;x2) ; kxk =

px21+ x2

2norme euclidienne

Normes de Holder dans Rn Soit p 2 N ou p =1. Pour tout x 2 Rn

kxkp =

nXi=1

jxijp! 1

p

est une norme dnomme norme p de Hlder.Cas classiques : p = 1; 2; 1p = 1 : norme_un : kxk1 =

nXi=1

jxij (norme des valeurs absolues)

p = 2 : norme_deux : kxk2 =

nXi=1

jxij2!1

2

(norme euclidienne)

p =1 : norme_innie : kxk1 = maxi=1;n

jxijAdditif (Matlab)p = 1 : norme_moins_inf kxk1 = min

i=1;njxij

Sous Matlab x = [x1; x2:::xn] ; N1 = norm (x; 1) N2 = norm (x; 2)Ou

N2 = norm (x) N inf = norm (x; inf) N_ inf = norm (x; inf)

NB :o help norm -

Remark 4 Syntaxe : norm (x; p) avec p = 1; 2 inf, -inf

1.1.2 Matrice de Mnp (R)Denition 5 Soient n; p 2 N;on appelle matrice de format (n; p) ou de typen p; coe cient rels, tout tableau de la forme suivant :

5

A =

26666664a11 a12 ::: a1j ::: a1pa21 a22 ::: a2j ::: ap::: ::: ::: ::: ::: :::ai1 ai2 ::: aij ::: aip::: ::: ::: ::: ::: :::an1 an2 ::: anj ::: anp

37777775Remark 6 On peut remplacer [] par () : Lensemble des matrices de format(n; p) cocient dans R se noteMnp (R).

a) Notations? A = (aij)1in

1jn;

? Matrice comme une ligne de vecteurs

En posant ; a:j =

0BB@a1ja2j:::anj

1CCA colonne j=) [a:1 a:2:::a:j:::a:p]?Matrice comme une colonne de vecteurs. En

En posant ai: = [ai1 ai2:::aip] ligne i

=) A =

26666664a1:a2::::ai::::an:

37777775b) Matrices particulieres.? matrices 1 p ou vecteurs lignesv = [v11 v12:::v1p] [v1 v2:::vp]

? matrices n 1 ou vecteurs colonnes

C =

26666664c11c12:::ci1:::cn1

37777775 26666664c1c2:::ci:::cn

377777756

? matrices scalaires : n = p = 1S = (s11) = (s)Saisie de matrice de0 00 et de 010 sous Matlab. n = 10 p = 15 z = zeros (n; p) 0 = ones (n; p)Cas gnral A = [ligne 1; ligne 2; ligne der] -A =

Introduction utiles (commandes) help : aide save : enregistrer la session load : ramne une session enregistre whos : donne la liste de toutes les variables de la session clc : (clear commande window)

eacer lcran ou la fentre de commande(travail) edit quit exitc) les matrices carres dordre n : Mn (R)A = (aij)1i;jn? Matrice nulle : n = 10

z = zeros (n)? Matrice de1: 0 = ones (n)? Matrice identit : I = eye (n)

I =

0BB@1 0 ::: 00 ::: ::: :::::: ::: 00 ::: ::: 1

1CCA? A =

2664a11 ::: :::: a1n: : : :: : : :an1 ::: ::: ann

3775 Matrice diagonale associe

7

D =

0BB@a11 0 ::: 00 : : :: : : 00 ::: 0 ann

1CCA dij = 0 si i 6= jaij si i = j9 fonction diag- diag (matrice carre) =vecteur form par la diagonale de la matrice- diag (vecteur) = matrice carre diagonale ayant vecteur comme diago-

nale D = diag (diagA) Matrice triangulaire suprieur (Up) associ

U =

2664a11 0 ::: a1n0 : : :: : : :an1 ::: 0 ann

3775 Uij = 0 si i jaij si i j9 fonction tri(u)

U =tri u (A) -? Matrice triangulaire infrieure (low)

L =

266664a11 0 ::: ::: 0a21 : : : :::: : : : :: : : : 0an1 ::: ::: an;n1 ann

377775 L = tril (A) - (Matlab extrait la matrice triangulaire infrieur de

A).Autres fonctions sur les matrices carres dordre n :det () : calcule le dterminant

exemple :

a11 ::: a1n: : :an1 ::: ann

inv () : calcule linverseexemple : A1 =

1

detA

t

(com (A))

Normes de matrices carres

Denition 7 On appelle norme matricielle sur Mn (R), toute applicationnote jjj jjj dnie de :

8

Mn (R) ! RuA 7! jjjAjjj

qui vrie les 4 proprits suivantes :(i) : jjjAjj j 0;8 A 2Mn (R) ; jjjAjjj = 0 () A = 0 (positivit)(ii) : jjjAjjj =j j jjjAjjj;8 2 R;8 A 2Mn (R) (homogneit circulaire)(iii) : jjjA + Bjjj jjjAjjj + jjjBjjj;8 A;B 2 Mn (R) (ingalit triangu-

laire)(iv) : jjjABjjj jjjAjjj jjjBjjj;8 A;B 2Mn (R) (consistance)

Exemples

exemple 1 : Norme matricielle de Frobenius

jjjAjjjF =

nXi=1

nXj=1

j aij j2! 1

2

exemple 2 : Norme matricielle subordonne des normes vectorielles Dnition : Soit k k une norme vectorielle alors jjj jjj

dnie par :jjjAjjj = max

x6=0kAxkkxk = maxjjxjj=1

k Axk est une norme baptise norme matriciellesubordonne la norme vectorielle. Cas des normes subordones k kp(Holder)? jjjAjjjpq = max kAxkpkAxkq

x 6= 0? jjjAjjjp = max kAxkpkxkp

x 6= 0-exemples de p-normes classiques

p = 1 jjjAjjj1 = maxj=1;n

nXi=1

j aij j

p = 2 jjjAjjj2 = ((AAt))12 o () : le rayon spectral (M) = max ji

p =1 jjjAjjj1 = maxj=1;n

nXi=1

jaijj

(dessin)

Calcul sous matlab

9

9 fonction norm ()syntaxe : jjjAjjjp = norm(A; p), avec p = 1; 2; inf; fro0Ainsi (sur matlab)o A = [ligne 1; ligne 2; :::; ligne n] -o N1 = norm(A; 1) -o N2 = norm(A; 2) -oo N2 = norm(A) -o Ninf = norm(A; inf) -o Nfro = norm(A;0 fro0) -

1.1.3 Applications des normes

a) Cas des normes vectorielles : Convergence dune suite (xk)k de vec-teurs.

suite (xk)k0 :k = 0; x(0) =

266664x01x02::x0n

377775 ; x(1) =266664x11x12::x1n

377775 ; etcConvergence : lim

k!+1x(k) = y () lim

k!+1jx(k) yj = 0

Dans la pratique on arrte les calculs ds que :-Erreur absolue : jjx(k) x(k+1)jj epsilon x lavanceou

- Erreur relative :jjx(k) x(k+1)jjjjx(k+1)jj epsilon

b) Cas des normes matricielles : Conditionnement de la matrice dun sys-tmeSoit Ax = b un systme linaire dordre n avec :A = matrice du systme, A donneb = second membre du systme, b donnx = vecteur inconnu calculer.NB :

1

3ne sera jamais saisi avec exactitude dans un ordinateur

exemple : e; :

Denition 8 (Conditionnement ou nombre de contion dune matrice)Soit A une matrice carre dordre n: on appelle nombre de condition le

rel positif not cond(A) et dni par :

10

cond(A) = jjAjj:jjA1jjo jj:jj dsigne la norme matricielle.

Son utilit : msurer la abilit des solutions de systmes linaires dematrice A.En eet considrons un systme et ses perturbations :Ax = b (S)(A+A)x0 = b (P1)Ax0 = b+b (P2)(A+A)x0 = b+b

Considrons (P1); on dmontre que lerreur commise en prenant x0 =

x+x vriejjxjjjjxjj cond(A)

jjAjjjjAjj . Il est alors clair que

jjxjjjjxjj est petite

lorsque cond(A) est petit. On dira alors que le systme est bien conditionn.Dans le cas contaire, il est mal conditionne car toute petite perturbationdes donnes provoque une grosse erreur sur les solutions.Sous matlab9 la fonction cond()syntaxe : cond(A); cond(A; p); o p = 1; 3; inf; "fro"Autre application des normes matricielles : Convergence dalgorithmesPour rsoudre Ax = b; surtout lorsque lordre n de la matrice A est trs

grand, on construit une suite (x(k))k2N de vecteurs selon lalgorithme suivant :x(0) donn dans Rnx(k+1) = x(k) +

o :

est une matrice carre dordre n appele matrice ditration est un vecteur de Rn appel second membre associ :On espre que lim

k!+1x(k) = x; solution du systme

Theorem 9 (Condition su sante)Si jjjj < 1 alors lalgorithme converge, o jj:jj est une norme matricielle

subordonne une norme vectorielle.

Conv () limk!+1

k = 0() () < 1(= jjjj < 1() jjjj

11

1.2 Mthodes "thoriques" de rsolution deAx = b : Cramer, Inverse

1.2.1 Mthodes des dterminants ou de cramer

Pour rsoudre Ax = b, dordre n, on calcule les (n + 1) dterminantssuivants :

- = det(A) =

a11 : : a1n: : : :: : : :an1 : : ann

dterminant principal

- xi =

a11 : b1 : a1n: : : : :: : : : :: : : : :an1 : bn : ann

dterminant associ xi

Alors

xi =xi; i = 1; n

Nombre doprations lmentaire : ; ; Cot :

Nc = (n+ 1)!(n+ 1) 1Exemple : n = 5; Nc = 4319

n = 10; Nc = 4:108

Rappel : Dterminant

n = 2;

a ba0 b0 = ab0 a0b

n = 3;

a b ca0 b0 c0

a00 b00 c00

= (ab0c00 + a0b00c+ a00bc0) (cb0a00 + c0b00a+ c00ba0)1.2.2 Mthode de linverse

Pour rsoudre Ax = b; on calcule linverse A1 de A alors x = A1b. Mais

A1 =1

det(A)tCA

vers le cot :

12

- 1 dterminant dordre n- n2 dterminant dordre (n 1)- n2 divisionsCot Ninv = (n+ 1)! + n!n2 + 2n2 n 1Remarque :Ces deux mthodes, formules simples, sont non pratiques (cf n 3)Que faire ?Dvelopper des mthodess plus pratiques. Il existe deux grandes familles

de pratiques :- Les mthodes directes : on obtient la solution au bout dun nombre ni

dopration lmentaires (n 100):- Les mthodes itratives : on obtient une suite (x(k))kN telle que lim

k!+1x(k) =

x; solution du systme

1.3 Mthode directes : Gauss, Jordan, Cho-leski, ...

1.3.1 Rsolution des systmes triangulaires et diago-naux

a) triangulaire suprieur (Up)8>>>>>>>>>>>:

a11x1 + a12x2 + :::+ a1nxn = b1a22x2 + a23x3:::+ a2n = b2

:::::::::::::::::an1xi + :::+ ainxn = bi

:::::::::::::::::annxn = bn

On le rsoud du bas vers haut(n) =) xn = 1

ann:bn

(n 1) =) xn1 = 1an1;n1

:[bn1 an1xn](i) =)

xii =1

aii:[bi

i+1Xj=n

aijxj]

13

b) Triangulaire infrieur (Low)8>>>>>>>>>>>:

a11x1 = b1a21x1 + a22x2 = b2

:::::::::::::::::::::::::ai1x1 + ai2x2 + ::::::+ aiixi + :::::::+ ainxn = bi

:::::::::::::::::::::an1x1 + an2x2 + ::::::::::::::::::::::::+ annxn = bn

On le rsoud du haut vers le basx1 =

1

/a11:b1

x2 =1

a22[b2 a21x1]

:::

xi =1

aii[bi

i1Xj=1

aijxj]; i = 1; n

Cot dun syte triangulaire : NT = n2:Si on pouvait ramener tout le systme Ax = b 1 ou 2 systmes triangu-

laires...Les chercheurs ont imagin la factorisation de la matrice A- type 1 : A = L U avec L ! inf et U ! sup (Gauss,

Choleski)- tupe 2 : A = Q:R avec Q ! unitaire et R ! supSous matlab :o help LUo help QR

c) Systmes diagonaux8>>>>>>>>>>>:

a11x1 = b1a22x2 = b2

:::aiixn = bi

:::a22x2 = bn

Rsolution immdiate :

xi =biaii; i = 1; n

14

1.3.2 Mthode directe de Gauss

a) PrincipeIl sagit de rendre triangulaire suprieur le systme ;Pratiquement ;On pose eA(0) = (Ajb); matrice agrandie ou matrice largie ou matrice

augmente. Matrice de format n (n+ 1):On eectue des transformations qui donnent au nisheA(n) = (jb) o est une matrice triangulaire suprieureAinsi (Ajb) ::: (jb)b) Algorithme -Formules de Gauss

1. On choisit une ligne "pleine" quon place en premire position. Lepremier coe ient (non nul) sappelle le pivot.

2. En utilisant la ligne pivot, on annule tous les coe cient situs en des-sous du pivot.

3. On repte les tapes (1) et (2) au sous systme obtenu en ignorant laligne du pivot.

4. On itre :

eA(0) =

a11 a12 : a1j : a1n a1;n+1a21 a22 : a2j : a2n a2;n+1: : : : : : :ai1 : : : : ain ai;n+1: : : : : : :an1 : : anj : ann an;n+1

5. eA(1) =

a(1)11 a

(1)12 : a

(1)1j : a

(1)1n a

(1)1;n+1

0 a(1)22 : a

(1)2j : a

(1)2n a

(1)2;n+1

: : : : : : :

0 : : : : a(1)in a

(1)i;n+1

: : : : : : :

0 a(1)n2 : a

(1)nj : a

(1)nn a

(1)n;n+1

6. Formules de passage de eA(0) eA(1)8

8>>:x+ 2y + 3z = 16y + 2z + 3t = 10z + 2t+ 3x = 16t+ 2x+ 3y = 18

Systme dordre 4ordre choisi des inconnues : (x; y; z; t)

eA(1) =1 2 3 0 160 1 2 3 103 0 1 2 162 3 0 1 18

eA(2) =

1 2 3 0 160 1 2 3 100 6 8 2 320 1 6 1 14

1 2 3 0 160 1 2 3 100 3 4 1 160 1 6 1 14

eA(3) =

1 2 3 0 160 1 2 3 100 0 2 10 140 0 4 4 4

1 2 3 0 160 1 2 3 100 0 1 5 70 0 1 1 1

16

eA(4) =1 2 3 0 160 1 2 3 100 0 1 5 70 0 0 6 6

Rsolution=)t = 1z = 7 5t = 2; z = 2y = 10 2z 3t = 10 4 3 = 3; y = 3x = 16 2 3 3 2 = 4; x = 4

(x; y; z; t) = (4; 3; 2; 1) o

0BB@xyzt

1CCA =0BB@4321

1CCAd) Cot de la mthode de Gauss

NG =4n3 + 15n2 n 12

6soit NG ' 23n3 pour les grands systmes

1.3.3 Mthode de Jordan

a) PrincipeRendre diagonal le systme(Ajb) ::: (Djb) o D est une matrice diagonaleRemarque : presque du Gauss deux fois. En eet, il su t dannuler tous

les coe cients situs et part et dautre du pivot.b) Algo - Formules (cf Gauss)c) Cot :

NJ =2n3 + 7n2 + 5n

2o NJ ' n2 pour n grand

Remarque : Lorsquon sarrange pour avoir un systme diagonal avec des"1" sur la diagonale, dit quon a fait du Gauss - Jordan.d) Exemple8>>>:x 2y + 2z t = 92x+ 5y 3z + 5t = 272x 3y + 4z + 2t = 5x+ 5y + 2z + 10t = 35

17

eA(1) =1 2 2 1 92 5 3 5 272 3 4 2 51 5 2 10 35

eA(2) =

1 2 2 1 90 1 1 3 90 1 0 4 130 3 4 9 26

eA(3) =

1 0 4 5 90 1 1 3 90 0 1 1 40 0 1 0 1

eA(4) =

1 0 0 9 250 1 0 4 130 0 1 1 40 0 0 1 3

eA(5) =

1 0 0 0 20 1 0 0 10 0 1 0 10 0 0 1 3

=)

0BB@xyzt

1CCA =0BB@

2113

1CCA

1.3.4 Mthode de Choleski ou des racines carres

deux conditions :- A symtrique ie At = A- A dnie positive ie (Ax; x) 0

Vrication :* Symtrie :

o A = [ligne 1; ligne 2; :::; ligne n];o A == A0 -

1 :: 1: : :1 ::: 1

18

*dnie positive ? les calculs le dironta) PrincipeOn factorise A sous la forme :A = L Lt avec L; triangulaire infrieur. AlorsAx = b() L Ltx = b

()

L:y = b; infLt:x = y; sup

Sous Matlabfonction chol()chol(A) = Lt

b) ExempleRsoudre par choleski (si possible)

Ax = b avec A =

1 2 2 12 5 3 52 3 4 21 5 2 10

On a : At = AEssayons de factoriser A en L LtEcrivons L avec des coe cients inconnus calculer

Lt =

0BB@l11 l21 l31 l410 l22 l32 l420 0 l33 l430 0 l44

1CCAL =

0BB@l11 0 0 0l21 l22 0 0l31 l32 l33 0l41 l42 l43 l44

1CCA0BB@1 2 2 12 5 3 52 3 4 21 5 2 10

1CCAl211 = 1; on prend l11 = 1l11l21 = 2 =) l21 = 2 =) l31 = 2 =)l41 = 11ere colonne okl21l11 = 2l221 + l

222 = 5 =) l222 = 5 4 = 1 =) l22 = 1

l21l31 + l22l33 = 3 =) 2l31 + l32 = 3 =) 4 + l32 = 3 =)l32 = 1l21l41 + l22l42 = 5 =) 2l41 + l42 = 5 =) 2 + l42 = 5 =)l42 = 3l31l11 = 2 =)l31 = 2l31l21 + l32l22 = 3 =) 4 + 1 = 3l231 + l

232 + l

233 = 4 =) 4 + 1 + l233 = 4 =) l233 = 1 =)l33 = i

19

l31l41 + l32 + l33l43 = 2 =) 2 + 3 + il43 = 2 =)l43 = il41l11 = 1l241 + l

242 + l

243 + l44 = 10 =) 1 + 9 1 + l244 = 10 =)l44 = 1

L =

0BB@1 0 0 02 1 0 02 1 i 01 3 i 1

1CCA*L:y = b()

0BB@1 0 0 02 1 0 02 1 i 01 3 i 1

1CCA0BB@y1y2y3y4

1CCA =0BB@

927535

1CCA- y = 9- 2y1 + y2 = 27 =) y2 = 27 + 2 9 =)y2 = 9- 2y1 + y2 + iy3 = 5 =) iy3 = 5 18 + 9 = 4 =)y3 = 4i- y1 + 3y2 iy3 + y4 = 35 =) y4 = 35 + 9 + 27 4 =)y4 = 3

*Lt:x = y ()

0BB@1 2 2 10 1 1 30 0 i i0 0 0 1

1CCA0BB@x1x2x3x4

1CCA =0BB@

994i3

1CCA- x4 = 3- x3 x4 = 4 =) x3 = 4 3 =) x3 = 1- x2 + x3 + 3x4 = 9 =) x2 = 9 1 + 9 =) x2 = 1- x1 2x2 + 2x3 x4 = 9 =) x1 = 9 2 2 3 =) x1 = 2

On obtient :

x = (2;1; 1;3)Remarque : L se calcule colonne par colonne. Pour chaque colonne on

calcule dabord llment diagonal liiSous Matlabo A = [ligne 1; ligne 2; :::; ligne n] - % matrice du systmeo b = [ ]0 - % second membre du systmeo Lt = chol(A) - % calcul de Lto y = Lt0 n b - % rsolution de Ly = bo x = Lt n y - % rsolution de Ltx = yc) Formules de choleskiEcrivant L = (lij)1 i; j n et utilisant lgalit L:Lt = A:On obtient les formules suivantes :

20

lkk =

vuutakk k1Xj=1

l2kl; j = 1; n

lik =1

lkk(aik

k1Xj=1

lij:lkj); i = k + 1; n

d) Cot de la mthode de choleskiLa rsolution de Ax = b par choleski cote.

Nchol =2n3 + 15n2 + n

6 opration lmentairesoit

N ' n3

3 pour n grandComparaison :

n = 5 n = 10Gauss 119 845Choleski 105 585Jordan 225 1375

1.4 Mthodes itratives de rsolution de sys-tmes linaires : Jacobi, Gauss-Seidel, SOR

Ax = b; A matrice carre dordre n; inversible. Mthodes valables 8n 2 N; surtout n grand.

1.4.1 Algorithmes des mthodes itratives

a) PrincipePour rsoudre Ax = b; on construit une suite (xk)k2N cenxe converger

vers x; solution du systme. On construit (xk)k2N gnralement sous la forme :x(0) x dans Rnx(k+1) = :x(k) +

Avec : matrice n n; appel matrice ditration : second membre associ

b) Consistance - convergence de lalgorithme

21

Denition 10 (Consistance)Lalgorithme est dit consistance si, lorsque (xk)k0 converge, sa limite est

ncessairement solution du sytme.

Proposition 11 Lalgorithme est consistant ssi :I inversible = (I )A1b

Remark 12 On construit gnralement des algorithmes consistants.

Denition 13 (Convergence)Lalgorithme concistant est dit convergence si lim

k!+1x(k) = x (solution de

Ax = b) 8 x(0) x.

Theorem 14 Lalgorithme converge () limk!+1

(k) = 0 () () < 1 carjjjj < 1o jj:jj est une norme matricielle subordonne.

Remark 15 Pour jj:jj subordonne, on a toujours () jjjj

c) Critre darrt des calculesLorsquon est assur de la convergence, on arrte les calculs en utilisant

lun ou lautre des critres suivants :- Fixer lavance le nombre 00N 00it ditrations alors x

(Nit) ' x- Se xer une prcision ; mesure de lerreur :* Erreur absolue : jjx(k) xjj <

soit dans la pratique jjx(k) x(k+1)jj < * Erreur relative :

jjx(k) xjjjjxjj <

soit dans la pratiquejjx(k) x(k+1)jjjjx(k+1)jj <

d) Construittion des algorithmesMthode : Matrice splitting (dcomposition de matrice)On crit A =M N; avec M facilement inversibleAlors Ax = b() (M N)x = b

()Mx = Nx+ b (*)()x =M1Nx+M1b (**)

On pose : =M1N

22

=M1b-Classic splitting of A

A = [ E n D n F ]

avec D =

0BB@a11 0 : 00 : : :: : : 00 : 0 ann

1CCA dij = aii si i = j0 si i 6= jE =

0BB@0 0 : 0a21 : : :: : : 0an1 : ann 0

1CCA eij = aij si i > j0 si i jF =

0BB@0 a12 : a1n0 : : :: : : an1;n0 : 0 0

1CCA dij = aii si i < j0 si i jAinsi A = D E F classic splittingSous Matlabo A = [ligne 1; ligne 2; :::; ligne n] -o D = disg(diag(A)) -o E = tril(A) +Do F = triu(A) +DApplication Pour M = D et N = E + F : mthode de Jacobi Pour M = D E et N = F : mthode de Gauss-Seidel Pour Mw =

D wEw

et Nw =(1 w)w

D + F avec w 2]0; 2[ : mthodede SOR

1.4.2 Mthode itrative de Jacobi

a) Algorithmex(0) donne

x(k+1) = J:x(k) +

Avec J = D1(E + F ) = D1b

b) Convergence

23

Theorem 16 Si A est diagonale strictement dominante alors lalgorithmede Jacobi converge.

Denition 17 A = (aij)1i;jn est dite diagonale dominante si jaiij >nX

j=1;j 6=ijaijj; 8i = 1; n

Proof. 8 i = 1; n; jaiij >nXj 6=ijaijj ()

Xj 6=i

jaijjjaiij < 1; 8i = 1; n

()nXj=1

jJijj < 1; 8i = 1; n

() maxi=1;n

nXj=1

jJijj < 1; 8i = 1; n

() jjJ jj1 < 1c) Pour programmerx(k) calcul, on dsire calculer x(k+1)

globalementA = [ ]D = diag(diag(A))E = triu(A) +DF = triu(A) +DJ = inv(D) (E + F ) = inv(D) bepsilon = 1e 5 (105)n = length(beta)nk = zeros(n; 1)nk1 = betanit = 0ER = norm(xk xk1)=norm(xk1)while ER > epsilon

xk = xk1xk1 = J xk + betanit = nit + 1ER = norm(xk xk1)=norm(xk1)

endx = xk1

24

nombreit = nitPar point : x(k+1)i ; i = 1; nLalgorithme quivalent

M:x(k+1) = N:x(k) + bD:x(k+1) = (E + F )x(k) + b

La ie quation :

aiix(k+1)i =

nXj=1;j 6=i

aijx(k) + bi

=)x(k+1)i =

nXj 6=i

aijaiix(k)j +

biaii; i = 1; n

Remark 18 La formule indique quil faut ncessairement deux (2) placesnecessaires pour les calculs :1 pour x(k) et 1 pour x(k+1)

1.4.3 Mthode itrative de Gauss-Seidel

a) Lalgorithmex(0) donnex(k+1) = G:x(k) + ; k = 0; 1; ::::

avec G = (D E)1:F = (D E)1:b

b) Convergence

Theorem 19 Lalgorithme converge si A est diagonale strictement domi-nante.

c) Calculs- Globalement cf Jacobi- Par point :

M:x(k+1) = N:x(k) + b(D E):x(k+1) = F:x(k) + b

ie quationiXj=1

aijx(k+1)j =

nXj=i+1

aijx(k)j + bi

25

aiix(k+1)i =

i1Xj=1

aijx(k+1)j

nXj=i+1

aijx(k)j + bi

x(k+1)i =

1aii(i1Xj=1

aijx(k+1)j +

nXj=i+1

aijx(k)) +

biaii; i = 1; n

Remark 20 La formule indique quil ne faut pas ncessairement deux (2)places mmoires pour les calculs. On peut utiliser une seule place mmoirepour les calculs en procdant par balayage.

x(k) =

2666664x(k)1

:

x(k)i

:

x(k)n

3777775 ; x(k+1) =2666664x(k+1)1

:

x(k+1)i

:

x(k+1)n

3777775 ;266666664

x(k+1)1

x(k+1)2

:

x(k)i

:

x(k)n

377777775;

1.4.4 Mthodes SOR = Successive Over - Relaxation

a) Lalgorithmex(0) x dans Rnx(k+1) = Rwx

(k) + w

avec Rw =M1w :Nw = (D wEw

)1(1 ww

D + F )

w =M1w :b = (

D wEw

)1:b

w 2]0; 2[ : paramtre de relaxationb) Convergence

Theorem 21 Si A est symtrique, dnie positive et si w 2]0; 2[ alors SORconverge.

c) Calculs* Globalement cf Jacob* PonctuellementMw:x

(k+1) = Nw:x(k) + b

(D wEw

)x(k+1) = [(1ww)D + F ]x(k) + b

ie quation :

26

aiiwx(k+1)i =

i1Xj=1

aijx(k+1)j +

1 ww

aiix(k)i

nXj=i+1

aijx(k)j + bi

=)x(k+1)i =

w

aii

i1Xj=1

aijx(k+1)j + (1 w)x(k)i

w

aii

Xaijx

(k)j + w

biaii; i = 1; n

Remark 22 Mme avantage de place mmoire que Gauss.

27

Chapitre 2

Chap 2 : Interpolation etApproximation, Intgration etDrivation numriques

2.1 Interpolation

0 - Gnralitsa) Le problme

Dans ltude dun phnomne ' = '(t); jai obtenu les rsulats suivantspar mesure :

t0 t1 ::: ti ::: tny0 y1 ::: yi ::: ynyi = '(ti); i = 1; n:Question : je voudrais avoir une approximation analytique '(t) = :::

me permettant de calculer, sans plus mesurer pour tout t 2 [t0; tn] . ' ufonctionRponse : 9 2 approches approche 1 : ponctuelle , interpolationje trouve f ; f(ti) = yi; i = 1; n:

approche 2 : globale , approximationje trouve f ; jjf 'jj soit minimaleb) Les 6 classes de fonctions lmentaires

cf introduction (chap 0)c) Dmarche

28

Etape 1 : choisir la classe de la fonction o chercher f:Etape 2 : choisir entre interpoler et approcher.Dans cette partie : classe choisie : classe des polynmes mthode choisie : interpolation=) interpolation polynmialeOn cherche pn(t) = antn + an1tn1 + :::+ a1t+ a0; an 6= 0; tel que :

pn(ti) = yi; i = 0; n

d) ExistenceThormeLe polynme dinterpolation pn existe et est unique. En faisant varier i

de 0 n on obtient le systme8>>>>>>>>>>>:

antn0 + an1t

n10 + :::+ a1t0 + a0 = y0

antn1 + an1t

n11 + :::+ a1t1 + a0 = y1

:::::::::::::::::::::::::::::::::::::::ant

ni + an1t

n1i + :::+ a1ti + a0 = yi

:::::::::::::::::::::::::::::::::::::::ant

nn + an1t

n1n + :::+ a1tn + a0 = yn

sytme de (n+1) quations (n+1) inconnues ai et la matrice du systmeest :

A =

0BBBB@tn0 t

n10 ::: t0 1

tn1 tn11 ::: t1 1

::: ::: ::: ::: :::tni t

n1i ::: ti 1

tnn tn1n ::: tn 1

1CCCCADont le dterminant est de type vandermondedet(A) = (t1 t0)(t2 t1)(t2 t0):::(tn tn1) =

Yi>j

(ti tj) 6= 0 carti 6= tj pour i 6= j:NB : On calcule rarement, sinon jamais, les ai en rsolvant le systme

prcdent.Il existe plusieurs techniques dont les plus classiques sont

Linterpolation de Lagrange linterpolation de Newton

29

1) Linterpolation par Lagrangea) Polynmes de base de Lagrange

Pour ti; i = 0; n xs, dirents, on dnit (n+ 1) polynmes de dn.

Li(t) =(t t0)(t t1)(t t2) :::

enl#ver(t ti) ::: (t tn)

(ti t0)(ti t1)(ti t2) ::: (ti ti) enl"ver

::: (ti tn)ou

Li(t) =Yj 6=i

(t tj)(ti tj)

Proprits des ti :

i) Li(tj) = ji =

1 si j = i0 si j 6= 0

ii)nXi=0

Li(t) = 1

b) Formule de pn par Lagrange

pn(t) =nXi=0

yiLi(t)

Preuve

pn(tj) =nXi=0

yiLi(tj) =nXi=0

yiji = yj

c) Erreur dinterpolationDnitionn(t) = '(t) pn(t)Remarquen(ti) = '(ti) pn(ti)

= yi yi= 0 , i = 0; n

pour t = ti; n(t) 6= 0 prioriThormeSi ' 2 Cn+1([t0; tn]) alors

jn(t)j Mn+1(n+ 1)!

jL(t)j

30

avec L(t) =nYi=0

(t ti) et Mn+1 = jj 'n+1jj = supt2[t0;tn]

j'n+1(t)jPreuve :

On montre que n(t) 1(n+ 1)!

L(t)'n+1(t)

Remarque : Estimation grossireComme t 2 [t0; tn]) jt tij (tn t0)

=) jn(t)j Mn+1(n+ 1)!

(tn t0)n+1d) Cas des points quidistants

On suppose ti donn et un pas constantt = ht0 = t0t1 = t0 + ht2 = t1 + h = t0 + 2h

ti = t0 + i:h

on crit :t = t0 + s:h

s =t t0h

est appel variable rduire. Les Li(t) dviennent li(s) comme

suit :

Li(t) =Yj=0

(t tj)(ti tj) =

Yj=i0

(t0 + s:h t0 j:h)(ti + i:h t0 j:h) =

Yj=i0

s ji j li(s)

Proposition :Dans le cas des points quidistants les polynmes de Lagrange sont :

li(s) =Yj=i0

s ji j ; i = 0; n

Remarque : Les li ne dpendent pas des tj, mais uniquement de n: Onpeut donc pour n x, les tabuler. Les polynme dinterpolation devient :

ep(s) = nXi=0

yili(s)

Attention :

31

Pour estimer '(t) par ep(s); on calcule le s correspondant t en crivantt = t0 + s:h; Ainsi : s =

t t0h

2) Linterpolation par NewtonLemme :Soient (n+1) abscisses distinctes ti; i = 0; n; alors la famille f1; (t t0); (t t0)(t t1); (t t0)(t t1)(t t2); :::; (t t0)(t t1) ::: (t tn)g

est une base de Pn( lensemble des polynmes de d n)Rappel : Base canonique (1; t; t2; :::; tn)Consquence : Le polynme dinterpolation par newton scrit :

pn(t) = C01+C1(tt0)+C2(tt0)(tt1)+:::+Cn(tt0)(tt1):::(ttn1)

o les Ci sont les obtenus dans le diagramme de Newtona) Dirences divises - Diagramme de NewtonDnition 1 : (dirences divises)Soient ti; i = 0; n des abscisses dans [a; b]: On appelle dirence divise

de f : Dodre 0; le rel not f [ti] = f(ti); i = 0; n

Dodre 1; le rel not f [ti; tj] =f [tj] f [ti]tj ti ; i 6= j;= 0; n

Dodre 2; le rel not f [ti; tj] =f [ti; tj] f [tj; tk]

ti tk ; i; j; k dirent 2 2; 0; n

Formule du polynme dinterpolation par Newton

pn = '[t0]+'[t0; t1](tt0)+'[t0; t1; t2](tt0)(tt1)+:::+'[t0; t1; :::; tn](tt0)(tt1):::(ttn1)

Comment calculer les dirence divises intervenues dans la formule ?Diagramme

(aprs)Les coe cients de la formule sont ceux situs en dbut de chaque colonne

des dirences divises.b) Erreur dinterpolation cf Lagrangec) Cas des points quidistants : Dirences non divises=) 2 formules : Newton Progressive

32

Newton rgressive3 - ExempleDonnes

ti 1 0 12 1'(ti) 4 3 2 6

T.A.F (=Travail faire)1) Dterminer le polynme de dgr le plus lv possible qui interpole

ces donnes.2) Estimer la valeur du phnomne t = 1

2:

3) Estimer la valeur de la vitesse du phnomne t =3

4Rponse1) n+ 1 = 4 =) n = 3: Dtermination de p3Mthode choisie : Newton

(diagramme aprs)

p3(t) = 4 (t+ 1) 6(t+ 1)(t 0) + 16(t+ 1)t(t 12)

2) '(12) ' p3(1

2)

On a :p3(12) = 4 (

1

2) 6(1

2)(1

2) + 16(

1

2)(1

2)(1)

= 4 12+3

2+ 4 = 9 =) '(1

2) ' 9

3) '0(3

4) ' p0(3

4)

p3(t) = 3 t 6t 6t2 + 16(t2 + t)(t 12)

= 3 7t+ 6t2 + 16(t3 12t2 + t2 1

2t)

p3(t) = 16t3 + 2t2 15t+ 3

Exercice1) Ecrire p3 suivant les puissances dcroissantes de t2) Calculer p3 par Lagrange et comparer

SOUS MATLAB p3 = [16 2 15 3]

33

t = [1 : 0:1 : 1] f = polyval(t; p3) plot(t; f;0 r0) hold on td = [1 0 0:5 1] fd = [4 3 2 6] plot(td; fd;0 0)Approximation au sens des moindes carrs discrtestiyi; i = 0; n soit m n

pm approxime les donnes aux sens des moindres carrs si

pn = minp2Pn

(nXi=0

jpm(ti) yij2dx)12

si m = n; pn polynme dinterpolationApproximation polynmiale des moindes carrs est :

pn = minp2Pn

(

bZa

(p(x) '(x))2dx)12

2.2 Approximation (polynmiale)

1ercas : ' connue explicitement

=)mthodes

8>>>>>:- norme uniforme : jjf jju = max

x2[a;b]jf(x)j

- norme des carrs : jjf jjmc = (f; f) 12 = (bZa

w(x)f 2(x)dx)12

2eme cas : ' connue en (n+ 1) abscisses=) norme des carrs discrtes : jjf jjmcd =< f; f > 12=

(mXi=0

w(xi)f2(xi))

12

2.2.1 Polynme epn de meilleure approximation uniforme(m. a. u) dune fonction '

a) Dnition

34

Soit ' une fonction donne sur [a; b]: Soit Pn; lespace vectoriel des po-lynmes pn de d n: On appelle polynme de m. a. u de ' dans [a; b] lepolynme ep dnie par :jj' epnjju = min

pn2Pnjj' pnjju = min

pn2Pn[maxx2[a;b]

jj'(x) pn(x)jju]b) Existence unicit

Theorem 23 Le polynme epn de m. a. u existe et est unique.c) Dtermination de epn

Theorem 24 (de Tchebychev) :Soit ' une fonction dnie sur [a; b]: Soit epn un polynme de d n: Soit

n = ' pn et M = jjnjju: Si n prend alternativement les valeurs M;+M en au moins (n + 2) abscisses dans [a; b]: Alors epn est le polynme dem. a. u de ' dans [a; b]:

d) Exemple

Donne : '(t) = t3 t2 14t+

1

4; t 2 [1; 1]

Problme : Trouver ep2 de m. a. u de 'Rponse : ep = t2 + 1

2t+

1

4VrionsPosons 2 = ' ep2On a : 2(t) = '(t) epn(t)

= t3 t2 14t+

1

4 (t2 + 1

2t+

1

4)

2(t) = t3 3

4t; t 2 [1; 1]

Petite tude

2(1) = 1 + 34= 1

4

2(1) = 1 34=1

4

02(t) = 3t2 3

4= 3(t2 1

4) = 3(t 1

2)(t+

1

2)

2(12) = 1

8+3

8=2

8=1

4

2(1

2) = 1

4

35

Tableau de variable

(dessin)

M = jj2jj = 14; n+ 2 = 2 + 2 = 4 abscisse dalternance

Comment -t-on trouv epn?Cas particulier o ' est elle mme un polynme de dgr n+ 1:Supposons f = pn+1 sur [a; b]; f(x) = pn+1(x) = a1xn+1+a2xn+:::+an+2On se ramne t 2 [1; 1] par p(x) = x+ = tOn trouve '(t) = b1tn+1 + b2tn + :::+ bn+2PropositionLe polynme epn de m. a. u de ' dans [1; 1] est donn par

epn(t) = '(t) b122Tn+1(t)

o Tm dsigne le polynme de dgr m de TchebychevRappel et complmentOn montre aisment que : cos(mx) = pm(cosx)Exemple : cos(2x) = cos2 x sin2 x

= cos2 x (1 cos2 x)= 2 cos2 x 1= p2(cosx)

cos(m) = pm(cos )posant : x = cos() cest dire = arccosxpn = Tm

Tm(x) = cos(m arccos x)

m = 0; T0(x) = 1m = 1; T1(x) = xm = 2; T2(x) = 2x

2 1m = 3; T3(x) = 4x

3 3xRelation de rcurrence :

Tn(x) = 2xTn1(x) Tn2(x)Les (Tn) forment une famille de polynme orthogonaux dans [1; 1] rela-

tivement la fonction poids w(x) =1p1 x2

ie :

36

1Z1

1p1 x2Tn(x) Tm(x)dx =

8>:0; si n 6= m; si n = m = 0

2; si n = m 6= 0

Mthode gnrale de calcul de ep2(t)crire ep2(t) = at2 + bt+ c; a; b; c?poser 2(t) = '(t) ep2(t)Etudier 2 sur [1; 1]; appliquer la rgle +M;M en au moins 2 + 2 = 4

points dalternance.

2.2.2 Polynme eqn de m. a. des moindres carrs de 'a) Dnitioneqn est le polynme de meilleure approximation de ' au sens des moindres

carrs (Least square) si eqn vrie :jj' eqnjjmc = min

qn2Pnjj' qnjjmc

o :

jjf jjmc = (bZa

w(x)f 2(x)dx)12

RemarqueRappel : (!u ;!v ) = !u t !v

(1; n) (n; 1)Produit scalaire (1; 1)(!u ;!u ) 0 carr scalaire ; jj!u jj =

p(!u ;!u )

Nouveau produit scalaire :

(f; g) =

bZa

w(x)f(x)g(x)dx

=) (f; f)w =bZa

w(x)f 2(x)dx 0

jjf j =

vuuut bZa

w(x)f 2(x)dx

b) Calcul de eqn- caractrisation

37

eqn m. a. m. c de '() (' eqn) 2 P?n() (' eqn; pn) = 0; 8pk 2 Pn

eqn est m.a.m.c() bZa

w(x)('(x) eqn(x)) = 0; 8p-Mthode de calculLa relation scrit encore

bZa

w(x)eqn(x)pk(x)dx = bZa

w(x)'(x)pk(x)dx; 8pk 2 Pn

* On pose eqn(x) = anxn+an1xn1+ :::+a1x+a0; les (n+1) constantes dterminer.* On crit lorthogonalit pour pk(x) = 1; x; x2; :::; xn

=) systme de (n+ 1) quations (n+ 1) inconnuesc) Exemple

'(t) = t3 t2 14t+

1

4; t 2 [1; 1]:

T.A.F : Dterminer le polynme eq2 de m.a.m.c de '.Nous prenons w 1:Posons eq2(x) = ax2 + bx+ c; a; b; c?Ecrivons lorthogonalit pour pk(x) = 1; x; x2

pk(x) = 1;

1Z1

1 eq2(t) 1dt = 1Z1

1 '(t) 1dt

[a

3t3 +

b

2t2 + ct]11 = [

1

4t4 1

3t3 1

3t2 +

1

4t]11

2

3a+ 2c = 2

3+ 2 1

41

3a+ c = 1

3+1

4= 1

12

=) a+ 3c = 14

pk(t) = t,

[a

4t4 +

b

3t3 +

c

2t2]11 = [

1

5t5 1

4t4 1

4:1

3t3 +

1

4:1

2t2]11

=) 23b =

2

5 2 1

4 13

38

=) 13b =

1

5 112

=) b = 35 14=7

20

=) b = 720

pk(t) = t2;

[a

5t5 +

b

4t4 +

c

3t3]11 = [

1

6t6 +

1

5t5 1

4:1

4t4 +

1

4:1

3t3]11

=) 25a+

2

3c = 2

5+ 2 1

4 13

=) 3a+ 5c = 3 55

+3 54 3 = 3 +

5

4= 7

4

=) 3a+ 5c = 74

On a :

(a+ 3c = 1

43a+ 5c = 7

4

=) 4c = 34 74= 1 =) c = 1

4

=) a = 14 3c = 1

4 34= 1 =) a = 1

On obtient : eq2(t) = t2 + 720t+

1

4

2.2.3 Polynme eqn de m.a.m.c discrtes de 'Hypothse : ' est connue en (n + 1) abscisses ti; i = 0;m: On mme les

mmes calculs que dans le paragraphe 2, en remplaant

bZa

parmXi=0

:

eq est un polynme m.a.m.c de '()mXi=0

w(ti)eqn(ti)pk(ti) = mXi=0

w(ti)'(ti)pk(ti); pk(t) = 1; t; t2

:Exercice :

ti 1 12

01

21

'(ti) 32

01

40 0

T.A.F : Dterminer eq2 de d2 qui approche ' au sens des monidre carrsdiscrtes.

39

On touve : eq2(t) = t2 + 35t+

1

4jj jjm:d

eq2(t) = t2 + 720t+

1

4jj jjm:c

eq2(t) = t2 + 12t+

1

4jj jju

'(t) = t3 t2 14t+

1

4on a [1; 1]t = 1 : 0:1 : 1yu = t:^2 + t=2 + 1=4ymc = t:^2 + 7 t=20 + 1=4ymcd = t:^2 + 3 t=5 + 1=4ft = t:^3 t:^2 t=4 + 1=4plot(t; yu; t; ymc; t; ymcd; t; ft)

2.3 Intgration numrique

2.3.1 Problmatique

1er cas : Donne : fonction ' partiellement connue en (n+1) abscisses ti;i = 0; n ti 2 [a; b]

question : I =

bZa

w(t)'(t)dt ?

2eme cas : Donne : fonction ' = '(t); connue explicitement avec parexemple ' de primitive inaccessibles.

exemple : '(t) = et2

2

question : I =

bZa

w(t)'(t)dt ?

Reponse

2.3.2 Formule de quadraturebZa

w(t)'(t)dt =

nXi=0

Ai'(t) +R

40

o :

bZa

w(t)'(t)dt est lintgrale exacte

nXi=0

Ai'(t) est lintgrale approche

R est le appel reste ou erreurAi; i = 0; n (poids) et R sont les constantes calculer de manire

ce que : R = 0 ou du moins su sament petit.Calcul des Ai et de RRgle : Utiliser le polynme dinterpolation par LagrangeOn a : '(t) = pn(t) + n(t)

=nXi=0

'(ti)Li(t) + n(t)

Multipliant par w et intgrant sur [a; b]; il vientbZa

w(t)'(t)dt =nXi=0

'(t)

bZa

w(t)Li(t)dt+

bZa

w(t)n(t)dt

=) Ai =bZa

w(t)Li(t)dt; i = 0; n

=) R =bZa

w(t)n(t)dt

Majoration de R

Si ' 2 Cn+1([a; b]) avec jj'(n+1)jj = Mn+1 Alors jnj 1(n+ 1)!

nYi=0

jt tij Mn+1jnj Mn+1

(n+ 1)!(b a)n+1

Par suite

R Mn+1(n+ 1)!

bZa

w(t)nYi=0

(t ti)dt

41

2.3.3 Formules de Newton - cotes

Hypothse : Les points ti sont quidistants t0; t1 = t0+h; :::; ti = t0+ ih;

:::; tn = t0 + nh avec h =tn t0n

Proposition : Alors Ani = Ai; i = 0; nOn distingue deux types de formules

-type ferm : I =

tnZt0

'(t)dt

-type ouvert : I =

tn+1Zt1

'(t)dt

Formules des trapzes

Aire dun trapze A = (b+B)h2

(gure)

On obtient : Ai = ('(ti) + '(ti+1))2

hEn somme A ' A0 A1 :::An1

' h2['(t0) + '(t1) + '(t2) + :::+ '(tn1) + '(tn)]

' h2['(t0) +

n1Xi=1

'(ti) + '(tn)]

I =

tnZt0

'(t)dt = h[12'(t0) +

n1Xi=1

'(ti) +12'(tn)] +R

Avec Newton cotes on a :

R = '(n+1)()(n+1)!

bZa

L(t)dt

Exemple :

t1Zt0

'(t)dt = h2['(t0) + '(t1)] h312'2(); 2 [t0; t1]

42

Formule de SIMPSON

n = 2;t2Zt0

'(t)dt =h

3['(t0) + 4'(t1) + '(t2)] h

5

90'2();

generale :tnZt0

'(t)dt =h

3['(t0)+4'(t1)+2'(t2)+4'(t3)+2'(t4)+ :::+

'(tn)] +R

Formule gnrale de PONCELET

On suppose n pairtn+1Zt1

'(t)dt = h[14'(t0) +

74'(t1) + 2

n42Xi=0

'(t2i+2) +74'(tn1) + 14'(tn)] +R

2.3.4 Formules dintgration numrique de Gauss

Notons que la formule gnrale de quadrature est exacte cest dire R = 0lorsque ' 2 Pn:En eet, dans ce cas ' = pn; n = 0:Question : Peut on avoir une formule qui soit exacte lorsque ' est un

polynme de degr largement suprieur n?Rponse : Oui deux conditions- 1ere condition : Les ti ne doivent plus tre donns !- 2eme condition : La fonction ' doit tre explicitement connue !ThormeIl existe (n + 1) abscisses ti ; i = 0; n; (n + 1) constants A

i ; i = 0; n; et

une constante R telles que la formule

bZa

w(t)'(t)dt =

nXi=0

Ai'(ti ) +R

soit

exacte lorque ' est un polynme de d 2n+ 1Calcul des ti (abscisses de Gauss)Les ti sont racines du polyme pn+1 de d

n+1 dune famille de polymesorthogonaux dans [a; b] relativement la fonction poids W:Pratiquement : [a; b] et W donns =) famille identie.On prend le polynme du degr n+ 1 et on calcule ses racines.

43

Calcul des Ai

Ai =

bZa

w(t)Li(t)dt; i = 0; n

obZa

w(t)tkdt =

nXi=0

Ai (ti )k; k = 0; 1; 2; :::; n

2.4 Drivation numrique

2.4.1 Le problme

Variables de la fonction : '- temps (t)- espace (x)

Drives

- 1eres'0(t) ! vitesse'0(x) ! convection

-2nde'00(t) ! acclration

'00(x) ! diusion

-3eme'3(t) ! ?'3(x) ! dissipation

Question :Hypothse 1 : ' = '(y), connue explicitement sur [a; b]Question 1 : Calculer 'k(y); 8y 2 [a; b]Reponse : Pas de problmeRemarque : Le calcul de 'k(y); peut savrer ardu, ou bien on dsire

calculer seulement 'k(y); i = 0; n:Solution 2 : Drivation numriqueQuestion 2 : Calculer 'k(yi); yi 2 [a; b]:

Calculer 'k(y); y 2 [a; b]:Rponse : Drivation numriqueFormule gnrale de la drivation numrique

'k(y) =nXi=0

i(y)'(yi) + rn(y)

44

Avec :- 'k(y) drive exacte

-nXi=0

i(y)'(yi) drive numrique

- rn(y) reste ou erreuro les fonctions i(y); qui dpendent de k; sont calculer, ainsi que la

fonction rn(y), qui doit tre trs petit (n).Solution : On peut utiliser le pn dinterpolation '(t) = pn(t) + n(t)=) 'k(t) = pkn(t) + kn(t)Avec :- pkn(t) drive numrique- kn(t) erreurUne application de la drive numrique :- rsolution numrique dquations direntielles ordinaires (ODEs)- rsolution numrique dquations aux drives partielles (PDEs)

2.4.2 Quelques formules dapproximations des drives :Mthode des dirences nies.

Approche empirique

'0(ti) = limt!ti

'(t) '(ti)t ti

=) '0(t) ' '(ti1) '(ti)ti1 ti (1) dcentre gauche

ou encore

'0(t) ' '(ti+1) '(ti)ti+1 ti (2) dcentre droite

Cas uniforme : ti+1 = ti = ti ti1 = h(1) + (2)

2=) '0(t) ' '(ti+1) '(ti1)

2hcentre

Approximation par la formule de taylor

Rappel :

f(x) = f(x0)+(x x0)1!

f 0(x0)+(x x0)2

2!f00(x0)+:::+

(x x0)nn!

f (n)(x0)+

0(x x0)nCas particulier : discretisation uniforme

45

t0 donn ; t1 = t0 + h; :::; ti = t0 + ih; tn = t0 + nh;

h =tn t0n

Ainsi ti+1 ti = h:On a successivement :

'(ti1) = '(ti) h1!'0(ti) +

h2

2!'00(ti) + 0(h2) (1)

'(ti+1) = '(ti) +h

1!'0(ti) +

h2

2!'00(ti) + 0(h2) (1)

a) approximation de '0(ti)

(1) =) '0(ti) = '(ti) '(ti1)h

+h

2'00(ti)

Approximation dordre 1 : j'0(ti) 'i 'i1h

j c:h1

on crit :'0(t) =

'(ti) '(ti1)h

+ 0(h)

(2) =) '0(ti) = '(ti+1) '(ti)h

h2'00(ti)

=)'0(ti) =

'(ti+1) '(ti)h

+ 0(h)

(2) (1)2

=) '0(ti) = '(ti+1) '(ti1)2h

+ 0(h2)

Remarque : Stencil = pts intervenus dans les calculs

b) Approximation de '00(ti)

(1) + (2)

2=)'

00(ti) ='(ti1) 2'(ti) + '(ti+1)

h2+ 0(h2)

cale pour les problmes de diusion

46

Chapitre 3

Chap 3 : Rsolution numriquedes ODEs et des PDEs par lamthode des dirences nies

3.1 Gnralits

Fonction une variable : u = u(t)=) drives : u0; u00; :::; uk; :::

fonction deux variables : u = u(t; x)

=) drives partielles : 1ere : @u@t ut; @u

@x ux

2eme :@2u

@t2 utt; @

2u

@x@t utx;

3eme : uttt; utxt; :::a) Dnition dODE et de PDE Soit u = u(t)On appelle ODE en u toute galit de la forme R(t; u; u0; u00; :::) = 0(1)ou F (t; u; u0; u00; :::) = f(t) (1 bis)

Soit u = u(t; x)On appelle PDE en u, toute galit de la forme :S(t; x; u; ut; ux; utt; :::) = 0 (2)ouG(t; x; u; ut; ux; utt; :::) = g(t; x) (2 bis)

b) Classication des ODEs et des PDEs

47

On classe les ODEs et les PDEs selon leur :Ordre : Ordre de la drive (resp. partielle) la plus lve. degr : exposant de la drive (resp. partielle) la plus lve. homongnt : Si f(t) = 0 ou g(t; x) = 0; on dit que lODE ou lePDE est homogne. Elle est non homogne sinon.

Linarit : Si F ouG est un polynme en u; u0; u00; ::: (resp. u; ut; ux; :::)de degr 1, on dit que lODE ou le PDE est linaire. Elle est dite nonlinaire sinon.Exemple : a0u+ a1u0 + :::+ apu(p) = f(t) linaire- coe cients constants si ai = cte 2 R; 8i = 0; p:- coe cients variables si 9 i0; ai0 = ai0(t):

3.2 Rsolutions des ODEs ou des systmesdODEs

3.2.1 Formules thoriques

Matlab : Fonction dsolvesyntaxe : dsolve(quation, condition initiale)! solution avec t comme

variable odsolve(quation, condition initiale, x)! solution avec x

comme variable.-quation : Dpu-Condition initiale : u() = :::: en nombre gal lordre de lODE ou PDE

Exemple 1 : d solve(0D2y = a2y0;0 y(0) = 1; Dy(a) = 00)

Problme 2 :

8>:y00 = a2yy(0) = 1

y0(

a) = 0

>> y = d solve( )Rponse : y = cos(at)

Exemple 2 :

8>>>:u00 = au+ b(v u)v00 = av b(v u)u(0) = v(0) = ku0(0) = v0(0) = 0

48

>> y = d solve(0D2u = au + b(v u)0; `D2v = av b(v u)0;0 u(0) = k0;0Du(0) = 00;0 v(0) = k0;0Dv(0) = 00)

>> u = y:u - % donne la solution de u>> v = y:v - % donne la valeur de la solution de v

Rponse :

u =1

2ke(

pat) +

1

2e(

pat)

v =1

2ke(t

pa) +

1

2ke(t

pa)

Cas des grands systmesOn utilise les fonctions ODE ...Exemple : ode 45

ode 23ode 15 s ! s = sti = raideode 113

3.2.2 Rsolution numrique par les dirences niesode, 8 t 2 [a; b]condition initiale

u(t)?; 8 t 2 [a; b] il nexiste pas de formule explicite- Discrtiser - Ecrire ODE en chaque ti- remplacer u0(ti); u00(ti); ::: par des dirences nies choisies. On se trouve

avec un systme dquation en u(tj)Exemple : Mthode dEuler pour ODEs ramne un systme dordre 1

Problme de Cauchyy0 = f(t; y) (1:1)y(t0) = y0 (1:2)

En ti =) y0(ti) = f(ti; y(ti)); i = 0; n Formule dEuler retrograde

y0(ti) ' y(ti) y(ti1)h

=)y(ti) = y(ti1) + hf(ti; y(ti)); i = 1; ny(t0) = y0

Schma de type progressif Formule DEuler progreessif

y0(ti) =y(ti+1) y(ti)

h

49

=)y(ti+1) = y(ti) + hf(ti; y(ti)); i = 1; ny(t0) = y0

Formule de type explicite

3.3 Rsolution numrique des EDP

Discrtiser (t; x) en (ti; xj): Ecrire lEDP aux points (ti; xj): Approcher les drives partielles par des dirences nies. Remplacer dans la PDE et rsoudre en u(ti; xj)Exemple :

ut(ti; xj) ' u(t

i; xj) u(ti1; xj)h

dcentr gauche en temps

uxx(ti; xj) ' u(t

i; xj1) 2u(ti; xj) + u(ti; xj+1)k2

gauche en espace.

( A suivre)

50