Author
zinalacin
View
114
Download
0
Embed Size (px)
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 =
[email protected]::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 =
[email protected] 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 =
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 =
[email protected]:::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 =
[email protected] 0 ::: 00 ::: ::: :::::: ::: 00 ::: ::: 1
1CCA? A =
2664a11 ::: :::: a1n: : : :: : : :an1 ::: ::: ann
3775 Matrice diagonale associe
7
D =
[email protected] 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
1CCA [email protected]
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
=)
1CCA [email protected]
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 =
[email protected] l21 l31 l410 l22 l32 l420 0 l33 l430 0 l44
1CCAL =
[email protected] 0 0 0l21 l22 0 0l31 l32 l33 0l41 l42 l43 l44
[email protected] 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 =
[email protected] 0 0 02 1 0 02 1 i 01 3 i 1
1CCA*L:y = b()
[email protected] 0 0 02 1 0 02 1 i 01 3 i 1
1CCA [email protected]
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 ()
[email protected] 2 2 10 1 1 30 0 i i0 0 0 1
1CCA [email protected]
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 =
[email protected] 0 : 00 : : :: : : 00 : 0 ann
1CCA dij = aii si i = j0 si i 6= jE =
[email protected] 0 : 0a21 : : :: : : 0an1 : ann 0
1CCA eij = aij si i > j0 si i jF =
[email protected] 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 =
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 : @[email protected] ut; @u
@x ux
2eme :@2u
@t2 utt; @
2u
@[email protected] 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