# Chapitre 14 Le calcul intégral et les équations différentielles

## 14.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.

### 14.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`

### 14.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`

## 14.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.

### 14.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)

### 14.2.2 Application au calcul de S=∑k=1∞1/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=S−Rp=S−1/p+O(1/p2)
On forme pour p=1..2n−1 :
S1,p=S1p=2*S2p−Sp puis,
S2,p=S2p=(22*S12p−S1p)/(22−1) puis,
Sk,p=(2k*Sk−1,2p−Sk−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,2−S0,1=3/2=1.5
S1,2=2*S0,4−S0,2=1.59722222222
S2,2=(4*S1,2−S1,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=1∞1/k2=π2/6≃ 1.6449340668482

### 14.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 12.3.4 et 12.4.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=S−Rp=S−pln(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`

### 14.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`

### 14.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
où 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 P′k=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 f∈ C2p+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= |
b−a
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=b−a/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)=I−c1h2−c2*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( |
b−a
2n
| )

Tn,1= |
4Tn,0−Tn−1,0
3

Tn,k= |
22kTn,k−1−Tn−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 14.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 à `T``k,0``=l[k]` où `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 à `M``k,0``=l[k]` où `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=1∞f(k)

On peut aussi reprendre le programme sur les séries ∑k=1∞f(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`

### 14.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]];
    }

## 14.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 t∈ I.
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|y1−y2|.
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.

### 14.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∈ [t0−h ; t0+h] :
y(t)≃ y0+f(t0,y0)· (t−t0) : 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,y0)· h 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)· (t2−t1)=≃ y1+f(t1,y1)· h.
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;
    }

### 14.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)`
où `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;
    }

### 14.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