Previous Up Next

Chapitre 15  Le calcul intégral et les équations différentielles

15.1  La méthode des trapèzes et du point milieu pour calculer une aire

Dans Xcas, il existe déjà une fonction qui calcule la valeur approchée d’une intégrale (en accélérant la méthode des trapèzes par l’algorithme de Romberg) qui est : romberg
Soit une fonction définie et continue sur l’intervalle [a ; b].
On sait que ∫ab f(t)dt peut être approchée par l’aire, soit :
- du trapèze de sommets a,b,b+i*f(b),a+i*f(a) soit,
- du rectangle de sommets a,b,b+i*f((a+b)/2),a+i*f((a+b)/2).
La méthode des trapèzes (resp point milieu) consiste à partager l’intervalle [a ; b] en n parties égales et à faire l’approximation de l’intégrale sur chaque sous-intervalle par l’aire des trapèzes (resp rectangles) ainsi définis.

15.1.1  La méthode des trapèzes

On partage [a ; b] en n parties égales et trapeze renvoie la somme des aires des n trapèzes déterminés par la courbe représentative de f et la subdivision de [a ; b].

trapeze(f,a,b,n):={
local s,k;
s:=evalf((f(a)+f(b))/2);
for (k:=1;k<n;k++) {
s:=s+f(a+k*(b-a)/n);
}
return s/n*(b-a);
}

On partage [a ; b] en 2p parties égales et trapezel renvoie la liste de la somme des aires des n=2k trapèzes déterminés par la courbe représentative de f et la subdivision de [a ; b], liste de longueur p+1, obtenue en faisant varier k de 0 à p.
On pourra ensuite, appliquer à cette liste une accélération de convergence.
On remarquera qu’à chaque étape, on ajoute des "nouveaux" points à la subdivision, et que le calcul utilise la somme s précédente en lui ajoutant la contribution s1 des "nouveaux" points de la subdivision.

trapezel(f,a,b,p):={
local s,n,k,lt,s1,j;
s:=evalf((f(a)+f(b))/2);
n:=1;
lt:=[s*(b-a)];
for (k:=1;k<=p;k++) {
s1:=0;
for (j:=0;j<n;j++) {
s1:=s1+f(a+(2*j+1)*(b-a)/(2*n));
}
s:=s+s1;
n:=2*n;
lt:=concat(lt,s/n*(b-a));
}
return lt;
}

On met ce programme dans un niveau éditeur de programmes (que l’on ouvre avec Alt+p), puis on le teste et on le valide avec OK.
On tape (on partage [0;1] en 26=64 parties égales) :
trapezel(x->x^2+1,0,1,6)
On obtient :
[1.5,1.375,1.34375,1.3359375,1.333984375,1.33349609375,
1.33337402344]

On sait que int(x^2+1,x,0,1)=4/3=1.3333333333
On tape (on partage [0;1] en 26=64 parties égales) :
trapezel(exp,0,1,6)
On obtient :
[1.85914091423,1.75393109246,1.72722190456,1.72051859216,
1.71884112858,1.71842166032,1.71831678685]

On sait que int(exp(x),x,0,1)=e-1=1.71828182846

15.1.2  La méthode du point milieu

On partage [a ; b] en n parties égales et ptmilieu renvoie la somme des aires des n rectangles déterminés par la courbe représentative de f et les milieux des segments de la subdivision de [a ; b].

ptmilieu(f,a,b,n):={
local s,k;
s:=0.0;
for (k:=0;k<n;k++) {
s:=s+f(a+(b-a)/(2*n)+k*(b-a)/n);
}
return s/n*(b-a);
}

On partage [a ; b] en 3p parties égales et ptmilieul renvoie la liste de la somme des aires des n=3k rectangles déterminés par la courbe représentative de f et les milieux de la subdivision de [a ; b], liste de longueur p+1, obtenue en faisant varier k de 0 à p.
On peut ensuite appliquer à cette liste une accélération de convergence.
On remarquera qu’à chaque étape, on ajoute des "nouveaux" points à la subdivision, et, que le calcul utilise la somme s précédente en lui ajoutant la contribution s1 des "nouveaux" points de la subdivision.

ptmilieul(f,a,b,p):={
local s,n,k,lt,s1,j;
s:=evalf(f((a+b)/2));
n:=1;
lt:=[s*(b-a)];
for (k:=1;k<=p;k++) {
s1:=0.0;
for (j:=0;j<n;j++) {
s1:=s1+f(a+(6*j+1)*(b-a)/(6*n))+f(a+(6*j+5)*(b-a)/(6*n));
}
s:=s+s1;
n:=3*n;
lt:=concat(lt,s*(b-a)/n);
}
return lt;
}

On met ce programme dans un niveau éditeur de programmes (que l’on ouvre avec Alt+p), puis on le teste et on le valide avec OK.
On tape (on partage [0;1] en 34=81 parties égales) :
ptmilieul(x->x^2+1,0,1,4)
On obtient :
[1.25,1.32407407407,1.33230452675,1.33321902149,1.33332063202] On sait que int(x^2+1,x,0,1)=4/3=1.3333333333
On tape (on partage [0;1] en 34=81 parties égales) :
ptmilieul(exp,0,1,4)
On obtient :
[1.6487212707,1.71035252482,1.7173982568,
1.71818362241,1.71827091629]

On sait que int(exp(x),x,0,1)=e-1=1.71828182846

15.2  Accélération de convergence : méthode de Richardson et Romberg

Hypothèse : soit v une fonction qui admet un développement limité au voisinage de zéro à l’ordre n :
v(h)=v(0)+c1· h+c2· h+...+cn· hn+O(hn+1)
On veut accélérer la convergence de v vers v(0) quand h tend vers 0.

15.2.1  La méthode de Richardson

Le principe

La méthode de Richardson consiste à faire dispataitre le terme en c1· h en faisant par exemple la combinaison 2· v(h/2)−v(h).
On a en effet :
v(h)=v(0)+c1· h+c2· h2+...+cn· hn+O(hn+1)
v(h/2)=v(0)+c1· h/2+c2· h2/4+...+cn· h2/2n+O(hn+1)
Posons :
u(h)=2· v(h/2)−v(h)
On a donc u(h)=v(0)−c2· h2/2+...−cn· hn· 2n−1−1/2n−1+O(hn+1)
u tend donc plus vite que v vers v(0) quand h tend vers 0.
On peut continuer et faire subir la même chose à u.

L’algorithme général

On considère r ∈ ]0;1[ (on peut prendre r=1/2) et on pose :
v0,0(h)=v(h)=v(0)+c1· h+c2· h2+...+cn· hn+O(hn+1)
v1,0(h)=v(r· h)=v(0)+c1· r· h+c2· r2· h2+...+cn· rn· hn+O(hn+1)
v2,0(h)=v(r2· h)=v(0)+c1· r2· h+c2· r4· h2+...+cn· r2n· hn+O(hn+1)
Soit :
v1,1(h)=1/1−r(v(r· h)−r· v(h))=1/1−r(v1,0(h)−r· v0,0(h))
v1,1(h)=v(0)+c2· r· h2+...+cn· r· (rn−1)/(r−1)· hn+O(hn+1)
on on n’a pas de terme en h dans v1,1(h) et de la même façon en posant :
v2,1(h)=v1,1(r· h)=1/1−r(v(r2· h)−r· v1,0(h))=1/1−r(v2,0(h)−r· v1,0(h))
v2,1(h)=v(0)+c2· r3· h2+...+O(hn+1)
on n’a pas de terme en h dans v2,1(h)
On obtient la suite des fonctions vk,1=v1,1(rk−1· h) (k>1) qui n’ont pas de terme en h dans leur développements limités et qui convergent vers v(0).
On peut faire subir à la suite vk,1 le même sort qu’à la suite vk,0 et obtenir la suite vk,2 (k>2):
on pose v2,2(h)=1/1−r2(v2,1(h)−r2· v1,1(h))
et on n’a pas de terme en h2 dans v2,2(h) etc....
On obtient ainsi les formules de récurrence :

vk,0(h)=v(rk· h)
vk,p(h)=
1
1−rp
(vk,p−1(h)−rp· vk−1,p−1(h))

On a alors :

vk,p(h)=v(0)+O(hp+1)

15.2.2  Application au calcul de S=∑k=11/k2

On a :

Rp=S
p
k=1
1
k2
=
k=p+1
1
k)2

D’après la comparaison avec une intégrale on a :



p+1
1
x2
dx<Rp<


p
1
x2
dx

Donc

1
p+1
<Rp<
1
p

donc S0,p=Sp=SRp=S−1/p+O(1/p2)
On forme pour p=1..2n−1 :
S1,p=S1p=2*S2pSp puis,
S2,p=S2p=(22*S12pS1p)/(22−1) puis,
Sk,p=(2k*Sk−1,2pSk−1,p)/(2k−1)
À la main :
S0,1=1,
S0,2=5/4=1.25,
S0,3=49/36=1.36111111,
S0,4=205/144=1.42361111111
S1,1=2*S0,2S0,1=3/2=1.5
S1,2=2*S0,4S0,2=1.59722222222
S2,2=(4*S1,2S1,1)/3=1.62962962963
Dans la liste S on met 1,1+1/4,1+1/4+1/9,...1+1/4+...+1/22n,
S a 2n termes d’indices 0 à 2n−1,
puis on forme
S1=1.5,1+1/4+2/9+2/16,...S[2n−1]−S[2n−1−1]
(on doit mettre -1 dans S[2n−1]−S[2n−1−1] car les indices de S commencent à 0)
S1 a 2n−1 termes d’indices 0 à 2n−1−1
puis on continue avec une suite S2 de termes pour k=1..2n−2 :
(4*S1[2*k−1]−S1[k−1])/3 etc...
On écrit le programme suivant :

richardson(n):={
local s0,s1,k,j,st,S,puiss;
s0:=[1.];
st:=1.0;
for (k:=2;k<=2^n;k++) {
st:=st+1/k^2;
s0:=concat(s0,st);
}
//attention s0=S a 2^n termes d'indices 0 (2^n)-1
S:=s0;
for (j:=1;j<=n;j++){
  s1:=[];
  puiss:=2^j;
  //j-ieme acceleration s1 a 2^(n-j) termes d'indices 
  // allant de 0 a 2^(n-j)-1
  for (k:=1;k<=2^(n-j);k++) {
     st:=(puiss*s0[2*k-1]-s0[k-1])/(puiss-1);
     s1:=concat(s1,st);
  }
  s0:=s1;
}
return S[2^n-1],s1[0];
}:;

La première valeur est la somme des 2n premiers termes, calculée sans accélération , la deuxième valeur a été obtenue après avoir accéléré cette somme n fois.
On tape :
richardson(6)
On obtient :
1.62943050141, 1.64493406732
On a du calculer 26=64 termes (1 et 8 décimales exactes).
On tape :
richardson(8)
On obtient avec plus de décimales :
1.6410354363087,1.6449340668481 (2 et 12 décimales exactes)
On a du calculer 28=256 termes.
On sait que S=∑k=11/k22/6≃ 1.6449340668482

15.2.3  Application au calcul de la constante d’Euler

Par définition la constante d’Euler γ est la limite quand n tend vers l’infini de :

un=
n
k=1
1
k
−ln(n)

(voir aussi 13.3.4 et 13.5.2)
On a donc : γ=S=1+∑k=2+∞1/k+ln(1−1/k) On a :

Rp=S−1−
p
k=2
1
k
+ln(
k−1
k
)=
k=p+1
1
k
+ln(1−
1
k
)

D’après la comparaison avec l’intégrale de la fonction décroissante f(x)=ln(x)−ln(x−1)−1/x pour x≥ 1 on a :



p+1
f(x)dx<−Rp<


p
f(x)dx

Donc

pln(1−
1
p+1
)+1<−Rp<(p−1)ln(1−
1
p
)+1

donc S0,p=Sp=SRp=Spln(1−1/p+1)+1+O(1/p2)=1/2p+O(1/p2)
On écrit le programme suivant :

richard(n):={
local s0,s1,k,j,st,S,puiss;
s0:=[1.0];
st:=1.0;
for (k:=2;k<=2^n;k++) {
st:=st+1/k+evalf(ln(1-1/k),24);
s0:=concat(s0,st);
}
//attention s0=S a 2^n termes d'indices 0 (2^n)-1
S:=s0;puiss:=1;
for (j:=1;j<=n;j++){
  s1:=[];
  puiss:=2*puiss;
  //j-ieme acceleration s1 a 2^(n-j) termes d'indices 
  // allant de 0 a 2^(n-j)-1
  for (k:=1;k<=2^(n-j);k++) {
     st:=(puiss*s0[2*k-1]-s0[k-1])/(puiss-1);
     s1:=concat(s1,st);
  }
  s0:=s1;
}
return S[puiss-1],s1[0];
}:;

La première valeur est la somme des 2n premiers termes, calculée sans accélération , la deuxième valeur a été obtenue après avoir accéléré cette somme n fois.
Avec 24 digits, on tape :
richard(8)
On obtient :
0.5791675183377178935391464, 0.5772156649015050409260531
On a du calculer 26=64 termes (1 et 8 décimales exactes).
On tape :
richard(12)
On obtient plus de décimales :
0.5773377302469791589300024, 0.5772156649015328606067501 (3 décimales exactes sans accélération et 21 décimales exactes avec accélération)
On a du calculer 212=4096 termes.
On tape : Digits:=24;
evalf(euler_gamma)
On obtient : 0.5772156649015328606065119

15.2.4  La constante d’Euler à epsilon près et ma méthode de Richardson

La constante d’Euler est la limite dela suite u définit par :

u(n):={
  local res,j;
  res:=0;
  pour j de n jusque 1 pas -1 faire 
    res:=res+1./j; 
  fpour;
  return res-evalf(ln(n),24);
}:;

On va écrire la fonction Richardson qui va calculer la limite de la suite u à epsilon près avec 24 digits. On ècrit la fonction en travaillant sur les lignes :

Richardson(u,eps):={
  local Lprec,Lnouv,n,j;
  n:=8;
  Lprec:=[u(n)];
  repeter
    n:=2*n;
    Lnouv:=[u(n)];
    pour j de 1 jusque size(Lprec) faire 
      Lnouv[j]:=(2^j*Lnouv[j-1]-Lprec[j-1])/(2^j-1);
    fpour;
    Lprec:=Lnouv;
    afficher(Lprec);
  jusqua abs(Lnouv[size(Lnouv)-1]-Lnouv[size(Lnouv)-2])<eps;
  return Lnouv[size(Lnouv)-1];
}:;

On tape :
Richardson(u,1e-9)
On obtient :
0.5772156649019757368597692
On tape :
Richardson(u,1e-21)
On obtient :
0.5772156649015328606066475

15.2.5  La méthode de Romberg

C’est l’application de la méthode de Richardson à la formule des trapèzes dans le calcul d’une intégrale.

La formule d’Euler Mac Laurin

La formule à l’ordre 4
On a :
01g(t)dt=1/2(g(0)+g(1))+bernoulli(2)(g′(0)−g′(1))+1/4!bernoulli(4)(g(3)(0)−g(3)(1))+∫01P4(t)g(4)(t)dt
P4(t)=1/4!B4(t) avec
Bn(0)=bernoulli(n) et où Bn est le n-ième polynôme de Bernoulli.
La suite Pn est définie par :
P0=1,et pour k≥1 Pk=Pk−1 et ∫01Pk(u)du=0.
Pour la démonstration voir le fasicule Tableur, statistique à la section : Suites adjacentes et convergence de ∑k=0n (−1)k/2k+1.
Théorème pour la formule des trapèzes
Si fC2p+2([a;b]), il existe des constantes c2k pour k=0..p telles que :

I=
b


a
 f(x)dx=T(h)+c1h2+..cph2p+O(h2p+2)

avec

h=
ba
n
  et   T(h)=
h
2
(f(a)+f(b))+h 
n−1
k=1
 f(a+k· h)

On aura reconnu que T(h) est la formule des trapèzes pour le calcul de ∫ab f(x)dx avec h=ba/n.
Application de ce théorème pour la formule du point milieu
Soit un intervalle [a;a+h] de longueur h si on applique la formule du point milieu à I=∫aa+h f(t)dt on a m(h)=h*f((a+a+h)/2) et si on applique la formule des trapèzes aux intervalles [a;a+h/2] et [a+h/2,a+h] on a t(h/2)=h*(f(a)+f(a+h))/4+h*f((a+a+h)/2)/2=t(h)/2+m(h)/2 donc quand on coupe [a;b] en n intervalles de longueur h si on note M(h) la formule obtenue pour le point milieu et T(h) celle obtenue pour les trapèzes, on a :
M(h)=2*T(h/2)−T(h)
D’après la formule d’Euler Mac Laurin :
T(h)=Ic1h2c2*h4−.....cp*h2p+O(h2p+2) et donc
M(h)=I+c1/2*h2+c2*h4*(23−1)/23+...cp*h2p*(22p−1−1)/22p−1+O(h2p+2)
On en déduit que les termes de ces deux développements sont de signes contraires et donc si on fait le même nombre d’accélération de convergence à T(h) et à M(h) on obtiendra un encadrement de I.

L’algorithme de Romberg

On applque l’algorithme de Richardson à T(h) avec r=1/2.
On pose :

Tn,0=T(
ba
2n
)
Tn,1=
4Tn,0Tn−1,0
3
Tn,k=
22kTn,k−1Tn−1,k−1
22k−1

Théorème :
On a :

Tn,p=I+O(
1
22np
)

On partage successivement l’intervalle [a;b] en 1=20, 2=21,4=22,...,2n et on calcule la formule des trapèzes correspondante : T0,0,T1,0,..,Tn,0 c’est ce que fait le programme trapezel fait en 15.1.1 que je recopie ci-dessous.

trapezel(f,a,b,n):={
local s,puiss2,k,lt,s1,j;
s:=evalf((f(a)+f(b))/2);
puiss2:=1;
lt:=[s*(b-a)];
for (k:=1;k<=n;k++) {
    s1:=0;
    for (j:=0;j<puiss2;j++) {
        s1:=s1+f(a+(2*j+1)*(b-a)/(2*puiss2));
    }
    s:=s+s1;
    puiss2:=2*puiss2;
    lt:=concat(lt,s*(b-a)/puiss2);
}
return lt;
}

On va travailler tout d’abord avec deux listes : l0 et l1 au début l0=[T0,0] et l1=[T1,0], on calcule T1,1 et l1=[T1,0,T1,1], puis on n’a plus besoin de l0 donc on met l1 dans l0 et on recommence avec l1=[T2,0], on calcule T2,1 et T2,2, et l1=[T2,0,T2,1,T2,2] puis on met l1 dans l0 et on recommence avec.....pour enfin avoir Tn,0, Tn,1,... Tn,n dans l1.

Les programmes

On applque l’algorithme de Romberg à Tk,0=l[k]l=trapezel(f,a,b,n).

intt_romberg(f,a,b,n):={
local l,l0,l1,puis,k,j;
l:=trapezel(f,a,b,n);
//debut de l'acceleration de Romberg
l0:=[l[0]];
//on fait n accelerations
for (k:=1;k<=n;k++) {
   l1:=[l[k]];
   //calcul des T_{k,j} (j=1..k) dans l1
   for (j:=1;j<=k;j++) {
      puis:=2^(2*j);
      l1[j]:=(puis*l1[j-1]-l0[j-1])/(puis-1);
    }
    l0:=l1;
}
return l1;    
}

On applque l’algorithme de Romberg à Mk,0=l[k]l=ptmilieul(f,a,b,n) que je rappelle ci-dessous.

ptmilieul(f,a,b,n):={
local s,puiss3,k,lt,s1,j;
s:=evalf(f((a+b)/2));
puiss3:=1;
lt:=[s*(b-a)];
for (k:=1;k<=n;k++) {
s1:=0.0;
for (j:=0;j<puiss3;j++) {
s1:=s1+f(a+(6*j+1)*(b-a)/(6*puiss3))+f(a+(6*j+5)*(b-a)/(6*puiss3));
}
s:=s+s1;
puiss3:=3*puiss3;
lt:=concat(lt,s*(b-a)/puiss3);
}
return lt;
}

On procède comme précédemment en remplacant les puissances de 2 par des puissances de 3 et le calcul de T(h) par celui de M(h).

intm_romberg(f,a,b,n):={
local l,l0,l1,puis,k,j;
l:=milieul(f,a,b,n);
//debut de l'acceleration de Romberg
l0:=[l[0]];
//on fait n accelerations
for (k:=1;k<=n;k++) {
   l1:=[l[k]];
   //calcul des M_{k,j} (j=1..k) dans l1
   for (j:=1;j<=k;j++) {
      puis:=3^(2*j);
      l1[j]:=(puis*l1[j-1]-l0[j-1])/(puis-1);
    }
    l0:=l1;
}
return l1;    
}

On peut raffiner en calculant puis=2(2*j) dans la boucle (en rajoutant puis:=1; avant for (j:=1;j<=k;j++).. et en remplacant puis:=2(2*j); par puis:=puis*4;) et aussi en n’utilisant qu’une seule liste...
On met ces programmes successivement dans un niveau éditeur de programmes (que l’on ouvre avec Alt+p), puis on les teste et on les valide avec OK.
On tape (on partage [0;1] en 23=8 parties égales) :
intt_romberg(x->x^2+1,0,1,3)
On obtient :
[[1.3359375,1.33333333333,1.33333333333,1.33333333333]
On sait que int(x^2+1,x,0,1)=4/3=1.3333333333
On tape (on partage [0;1] en 24=16 parties égales) :
intt_romberg(exp,0,1,4)
On obtient :
1.71884112858,1.71828197405,1.71828182868,
1.71828182846,1.71828182846]

On sait que int(exp(x),x,0,1)=e-1=1.71828182846.
Dans la pratique, l’utilisateur ne connait pas la valeur de n qui donnera un résultat correct sans faire trop de calculs. C’est pourquoi, on va faire le calcul de la méthode des trapèzes au fur et à mesure et changer le test d’arrêt : on s’arrête quand la différence de deux termes consécutifs est en valeur absolue plus petit que epsi.

intrap_romberg(f,a,b,epsi):={
local l0,l1,puis,puiss2,k,j,s,s1,test;
//initialisation on a 1 intervalle
s:=evalf((f(a)+f(b))/2);
puiss2:=1;
l0:=[s*(b-a)];
k:=1;
test:=1;
while (test>epsi) {
   //calcul de la methode des trapezes avec 2^k intervalles
   s1:=0;
   for (j:=0;j<puiss2;j++) {
        s1:=s1+f(a+(2*j+1)*(b-a)/(2*puiss2));
   }
   s:=s+s1;
   puiss2:=2*puiss2;
   l1:=[s*(b-a)/puiss2];
   //debut de l'acceleration de Romberg
   //calcul des T_{k,j} (j=1..k) dans l1
   j:=1;
   while ((test>epsi) and (j<=k)) {
      puis:=2^(2*j);
      l1[j]:=(puis*l1[j-1]-l0[j-1])/(puis-1);
      test:=abs(l1[j]-l1[j-1]);
      j:=j+1;
    }
    l0:=l1;
    k:=k+1;
}
return [k-1,j-1,l1[j-1]];    
}

On renvoie la liste [p,q,val] où val=Tq,p (p=le nombre d’accélérations).
On tape :
intrap_romberg(sq,0,1,1e-12)
On obtient :
[2,2,0.333333333333]
(on a donc dû partager [0;1] en 22=4 parties égales et on a fait 2 accélérations)
On tape :
intrap_romberg(exp,0,1,1e-12)
On obtient :
[5,4,1.71828182846]
(on a donc dû partager [0;1] en 25=32 parties égales et on a fait 4 accélérations)
On peut aussi appliquer l’algorithme de Romberg à M(h) on le même programme en remplacant les puissances de 2 par des puissances de 3 et le calcul de T(h) par celui de M(h).

intmili_romberg(f,a,b,epsi):={
local l0,l1,puis,puiss3,k,j,s,s1,test;
//initialisation on a 1 intervalle
s:=evalf(f((a+b)/2));
puiss3:=1;
l0:=[s*(b-a)];
k:=1;
test:=1;
while (test>epsi) {
   //calcul de la methode du point milieu avec 3^k intervalles
   s1:=0;
   for (j:=0;j<puiss3;j++) {
      s1:=s1+f(a+(6*j+1)*(b-a)/(6*puiss3))+
          f(a+(6*j+5)*(b-a)/(6*puiss3));
   }
   s:=s+s1;
   puiss3:=3*puiss3;
   l1:=[s*(b-a)/puiss3];
   //debut de l'acceleration de Romberg
   //calcul des T_{k,j} (j=1..k) dans l1
   j:=1;
   while ((test>epsi) and (j<=k)) {
      puis:=3^(2*j);
      l1[j]:=(puis*l1[j-1]-l0[j-1])/(puis-1);
      test:=abs(l1[j]-l1[j-1]);
      j:=j+1;
    }
    l0:=l1;
    k:=k+1;
}
return [k-1,j-1,l1[j-1]];    
}

On tape :
inmili_romberg(sq,0,1,1e-12)
On obtient :
[2,2,0.333333333333]
(on a donc dû partager [0;1] en 32=9 parties égales et on a fait 2 accélérations)
On tape :
intmili_romberg(exp,0,1,1e-12)
On obtient :
[4,3,1.71828182846]
(on a donc dû partager [0;1] en 34=81 parties égales et on a fait 3 accélérations)

Application au calcul de ∑k=1f(k)

On peut aussi reprendre le programme sur les séries ∑k=1f(k) et écrire pour faire n accélérations :

serie_romberg(f,n):={
local l,l0,l1,puis,k,j,t,p;
// calcul des sommes s1,s2,s4,s8,...s2^n que l'on met ds l
 l:=[f(1)];
p:=1;
for (k:=1;k<=n;k++) {
t:=0.0
for (j:=p+1;j<=2*p;j++){
t:=t+f(j)
}
t:=l[k-1]+t;
l:= concat(l,t);
p:=2*p;
}
//debut de l'acceleration de Richardson
l0:=[l[0]];
for (k:=1;k<=n;k++) {
   l1:=[l[k]];
   //calcul des S_{k,j} (j=1..k) dans l1
   for (j:=1;j<=k;j++) {
      puis:=2^(j);
      l1[j]:=(puis*l1[j-1]-l0[j-1])/(puis-1);
    }
    l0:=l1;
}
return l1;    
}

On met ce programme dans un niveau éditeur de programmes (que l’on ouvre avec Alt+p), puis on le teste et on le valide avec OK.
On définit f :
On tape :
f(x):=1/x^2
On tape (on calcule ∑k=164 f(k)) :
serie_romberg(f,6)
On obtient cette somme après avoir subit 0,1,..6 accélérations :
[1.62943050141,1.64469373999,1.64492898925,1.64493403752,
1.64493409536,1.64493407424,1.64493406732]
Avec le programme richardson on avait :
1.62943050141, 1.64493406732
On tape (on calcule ∑k=1256 f(k)) :
serie_romberg(f,8)
On obtient cette somme après avoir subit 0,1,..8 accélérations avec plus de déciamles :
[1.6410354363087,1.6449188676629,1.6449339873839,1.6449340668192,
1.6449340668791,1.6449340668489,1.6449340668477,1.644934066848,
1.6449340668481]
On sait que π2/6=1.6449340668482

15.2.6  Deux approximations de l’intégrale

On calcule en même temps l’accélération de convergence pour la méthode des trapèzes et pour la méthode du point milieu.
On remarquera qu’ici on découpe l’intervalle [a;b] en 2 puis en 22... 2k morceaux et que le calcul de sm (somme des valeurs de f aux " points milieux") sert dans le calcul du st suivant (somme des valeurs de f aux "points de subdivision"+(f(a)+f(b))/2) comme contribution des nouveaux points.

inttm_romberg(f,a,b,epsi):={
local lt0,lt1,lm0,lm1,puis,puiss2,k,j,st,sm,s1,test;
//initialisation on a 1 intervalle
st:=evalf((f(a)+f(b))/2);
sm:=evalf(f((a+b)/2));
puiss2:=1;
lt0:=[st*(b-a)];
lm0:=[sm*(b-a)];
k:=1;
test:=1;
while (test>epsi) {
   //calcul de la methode des trapezes avec 2^k intervalles
    st:=st+sm;
   //calcul de la methode des milieux avec 2^k intervalles
   puiss2:=2*puiss2;
   s1:=0.0;
   for (j:=0;j<puiss2;j++) {
        s1:=s1+f(a+(2*j+1)*(b-a)/(2*puiss2));
   }
  
   sm:=s1;
   lm1:=[sm*(b-a)/puiss2];
   lt1:=[st*(b-a)/puiss2];
   //debut de l'acceleration de Romberg
   //calcul des T_{k,j} (j=1..k) dans lt1
   //calcul des M_{k,j} (j=1..k) dans lm1
   j:=1;
   while ((test>epsi) and (j<=k)) {
      puis:=2^(2*j);
      lt1[j]:=(puis*lt1[j-1]-lt0[j-1])/(puis-1);
      lm1[j]:=(puis*lm1[j-1]-lm0[j-1])/(puis-1);
      test:=abs(lt1[j]-lm1[j]);
      j:=j+1;
    }
    lt0:=lt1;
    lm0:=lm1;
    k:=k+1;
}
return [k-1,j-1,lt1[j-1],lm1[j-1]];    
}

15.3  Les méthodes numériques pour résoudre y′=f(x,y)

Dans Xcas, il existe déjà les fonctions qui tracent les solutions de y′=f(x,y), ce sont : plotode, interactive_plotode et une fonction odesolve qui calcule la valeur numérique en un point d’une solution de y′=f(x,y) et y(t0)=y0 Soit f une fonction continue de [a;b] × ℝ dans ℝ.
On considère l’équation différentielle :

y(t0)=y0
y′(t)=f(t,y(t))

Problème de Cauchy Soit U un ouvert de ℝ2 et f une application continue de U dans ℝ. On appelle solution du problème de Cauchy (E):

y(t0)=y0
y′(t)=f(t,y(t))

tout couple (I,g) où I est un intervalle contenant t0 et g est une I-solution de (E) c’est à dire une fonction de classe C1(I,ℝ) vérifiant g(t0)=y0 et g′(t)=f(t,g(t)) pour tI.
Théorème de Cauchy-Lipschitz faible Soit f, une fonction continue de [a;b] × ℝ dans ℝ, lipschitzienne par rapport à la seconde variable c’est à dire :
il existe K>0 tel que pour tout t∈[a;b] et pour tout (y1,y2)∈ ℝ2, |f(t,y1)−f(t,y2)|≤ K|y1y2|.
Alors, quel que soit (t0,y0)∈ [a;b] × ℝ, il existe une [a;b]-solution unique au problème de Cauchy (E) que l’on appellera y.

15.3.1  La méthode d’Euler

La méthode d’Euler consiste à approcher la solution de cette équation différentielle au voisinage de t0 par sa tangente en ce point. Cette tangente a comme pente y′(t0)=f(t0,y(t0))=f(t0,y0).
On a donc pour t proche de t0 par exemple pour t∈ [t0h ; t0+h] :
y(t)≃ y0+f(t0,y0)· (tt0) : on dit que h est le pas de l’approximation.
En principe plus h est petit, meilleure est l’approximation.
Soit h un pas, on pose t1=t0+h, et y1=y0+f(t0,y0)· (t1−t0)=y0+f(t0,y0h on a l’approximation :
y(t1)=y(t0+h)≃ y1
et on réitère cette approximation, donc si t2=t1+h :
y(t2)=y(t1+h)≃ y1+f(t1,y1)· (t2t1)=≃ y1+f(t1,y1h.
On écrit donc la fonction euler_f, qui réalise une seule étape de cette méthode et qui permet de passer d’un point d’abscisse t0 au point d’abscisse t0+h, ces points étant situés sur le graphe de la solution approchée par cette méthode.

euler_f(f,t0,y0,h):={
local t1,y1;
t1:=t0+h;
y1:=y0+h*f(t0,y0);
return (t1,y1);
}

Pour tracer le graphe de la solution approchée sur [t0;t1], on écrit :
segment(point((t0,y0)),point(euler_f(f,t0,y0,h)))
Pour trouver une solution approchée sur [a;b] de l’équation différentielle :
y′(t)=f(t,y(t)), y(t0)=y0, avec t0∈ [a;b],
il suffit de partager [a;b] en parties égales de longueur h et d’appliquer plusieurs fois la fonction euler_f avec le pas h puis avec le pas −h.
Voici le programme qui trace la solution sur [a;b] dans l’écran DispG et qui utilise la fonction euler_f.
Les derniers segments servent à s’arrêter exactement en a et en b.

trace_sol(f,t0,y0,h,a,b):={
local t1,y1,td0,yd0,l1,j;
td0:=t0;
yd0:=y0;
h:=abs(h);
while (t0<b-h){
    l1:=euler_f(f,t0,y0,h);
    t1:=l1[0];
    y1:=l1[1];
    segment(t0+i*y0,t1+i*y1);
    t0:= t1;
    y0:=y1;
}
segment(t0+i*y0,b+i*(y0+(b-t0)*f(t0,y0)));
//on trace avec -h
t0:=td0;
y0:=yd0;
while ( t0>a+h){
    l1:=euler_f(f,t0,y0,-h);
    t1:=l1[0];
    y1:=l1[1];
    segment(t0+i*y0,t1+i*y1);
    t0:= t1;
    y0:=y1;
}
segment(t0+i*y0,a+i*(y0+(t0-a)*f(t0,y0))); 
}

ou encore pour avoir le dessin dans l’écran graphique obtenu comme réponse, on écrit une fonction qui renvoie la séquencee des segments à dessiner :

trace_euler(f,t0,y0,h,a,b):={
local td0,yd0,l1,j,ls;
td0:=t0;
yd0:=y0;
h:=abs(h);
ls:=[];
while (t0<b-h){
    l1:=euler_f(f,t0,y0,h);
    ls:=ls,segment(t0+i*y0,point(l1));
    (t0,y0):=l1;
}
ls:=ls,segment(t0+i*y0,point(euler_f(f,t0,y0,b-t0)));
//on trace avec -h en partant de td0 et de yd0 
//(td0 et  yd0 sont les valeurs du debut)
t0:=td0;
y0:=yd0;
while ( t0>a+h){
    l1:=euler_f(f,t0,y0,-h);
    ls:=ls,segment(t0+i*y0,point(l1));
    (t0,y0):=l1;
}
ls:=ls,segment(t0+i*y0,point(euler_f(f,t0,y0,a-t0))); 
return ls;
}

15.3.2  La méthode du point milieu

La méthode du point milieu consiste à approcher, au voisinage de t0, la solution de l’équation différentielle y′(t)=f(t,y(t)), y(t0)=y0 t0∈ [a;b], par une paralléle à la tangente au "point milieu de la solution obtenue par la méthode d’Euler" :
Le "point milieu de la solution obtenue par la méthode d’Euler" est le point de coordonnées :
(t0+h/2,y0+h/2f(t0,y0))
et sa tangente a donc comme pente :
α=f(t0+h/2,y0+h/2f(t0,y0))
La méthode du point milieu fait passer du point (t0,y0) au point (t1,y1) avec :
t1=t0+h et y1=y0+h*α=y0+h*f(t0+h/2,y0+h/2*f(t0,y0)).
On remarquera que :
euler_f(f,t0,y0,h/2)=(t0+h/2,y0+h/2*f(t0,y0))
On va donc écrire la fonction :
ptmilieu_f(f,t0,y0,h)=(t0+h,y0+h*f(t0+h/2,y0+h/2*f(t0,y0)))
qui réalise une seule étape de cette méthode et qui permet de passer d’un point d’abscisse t0 au point d’abscisse t0+h, ces points étant situés sur le graphe de la solution approchée par cette méthode.

ptmilieu_f(f,t0,y0,h):={
local t1,y1;
t1:=t0+h;
y1:=y0+h*f(t0+h/2,y0+h/2*f(t0,y0));
return (t1,y1);
}

Il reste à écrire une fonction qui renvoie la séquence des segments obtenus par cette méthode, pour avoir le dessin dans l’écran graphique obtenu comme réponse.
On peut écrire la même fonction que précédemment en remplacant simplement tous les appels à euler_f par ptmilieu_f.
Mais on va plutôt rajouter un paramètre supplémentaire methode qui sera soit la fonction euler_f soit la fonction ptmilieu_f. On écrit :
trace_methode(methode,f,t0,y0,h,a,b)
methode qui est une fonction des variables f,t0,y0,h

trace_methode(methode,f,t0,y0,h,a,b):={
local td0,yd0,l1,j,ls;
td0:=t0;
yd0:=y0;
h:=abs(h);
ls:=[];
while (t0<b-h){
    l1:=methode(f,t0,y0,h);
    ls:=ls,segment(t0++i*y0,point(l1));
    (t0,y0):=l1;
}
ls:=ls,segment(t0+i*y0,point(methode(f,t0,y0,b-t0)));
//on trace avec -h en partant de td0 et de yd0 
//(td0 et yd0 sont les valeurs du debut)
t0:=td0;
y0:=yd0;
while ( t0>a+h){
    l1:=methode(f,t0,y0,-h);
    ls:=ls,segment(t0+i*y0,point(l1));
    (t0,y0):=l1;
}
ls:=ls,segment(t0+i*y0,point(methode(f,t0,y0,a-t0))); 
return ls;
}

15.3.3  La méthode de Heun

La méthode de Heun consiste à approcher, au voisinage de t0, la solution de l’équation différentielle y′(t)=f(t,y(t)), y(t0)=y0 t0∈ [a;b], par une parallèle à la droite de pente 1/2*(f(t0,y0)+f(t0+h,y0+h*f(t0,y0))) c’est à dire, par une pente égale à la moyenne des pentes des tangentes :
- de la solution au point (t0,y0) (la pente de la tangente en ce point vaut f(t0,y0)) et
- de la solution obtenue par la méthode d’Euler au point d’abscisse t0+h (point de coordonnées (t0+h,y0+h*f(t0,y0)) et la pente de la tangente en ce point vaut f(t0+h,y0+h*f(t0,y0))).
Donc, la méthode de Heun fait passer du point (t0,y0) au point (t1,y1) avec :
t1=t0+h et y1=y0+h/2*(f(t0,y0)+f(t0+h,y0+h*f(t0,y0))).
On remarquera que :
euler_f(f,t0,y0,h)=(t0+h,y0+h*f(t0,y0))
On va donc écrire la fonction :
heun_f(f,t0,y0,h)=
(t0+h,y0+h/2*(f(t0,y0)+f(t0+h,y0+h*f(t0,y0))))

qui réalise une seule étape de cette méthode et qui permet de passer d’un point d’abscisse t0 au point d’abscisse t0+h, ces points étant situés sur le graphe de la solution approchée par cette méthode.

heun_f(f,t0,y0,h):={
local t1,y1;
t1:=t0+h;
y1:=y0+h/2*(f(t0,y0)+f(t0+h,y0+h*f(t0,y0)));
return (t1,y1);
}

Il reste à écrire une fonction qui renvoie la séquence des segments obtenus par cette méthode, pour avoir le dessin dans l’écran graphique obtenu comme réponse.
On peut écrit la même fonction que précédemment en remplacant simplement tous les appels à euler_f par heun_f ou encore utiliser la fonction trace_methode avec comme valeur de methode le fonction heun_f.
On valide les differentes fonctions :
euler_f, ptmilieu_f, heun_f et trace_methode.
On tape par exemple pour avoir le tracé de la solution sur [-1;1] de :
y′=y vérifiant y(0)=1 par les 3 méthodes avec un pas de 0.1 :
f(t,y):=y trace_methode(euler_f,f,0,1,0.1,-1,1) et
trace_methode(ptmilieu_f,f,0,1,0.1,-1,1) ou
trace_methode(heun_f,f,0,1,0.1,-1,1) ou


Previous Up Next