Université Paris-Nord Année 2013-2014

Institut Galilée MACS - 1

Département de Mathématiques C. Basdevant, B. Delourme

Corrigé de l’examen d’Analyse Numérique du 5 mars 2014

Durée : 3h
Une feuille recto-verso de notes personnelles manuscrites est autorisée.

Exercice 1 : méthodes itératives

Soit A ∈ Mn (R) une matrice carrée n × n inversible telle que ses éléments diagonaux
soient tous non nuls et soit b un vecteur de Rn . On souhaite résoudre le système linéaire
Ax = b en utilisant la méthode itérative suivante :
α étant un réel non nul et le vecteur x0 ∈ Rn étant donné, on construit la suite (xk )k∈N
par la formule de récurrence

xk+1 = (I − αD−1 A)xk + αD−1 b. (1)

où I est la matrice identité et D la matrice diagonale constituée de la diagonale de A

(Dii = Aii ).
1. Montrez que si la suite (xk )k∈N converge vers x̄ ∈ Rn alors x̄ est solution du système
linéaire Ax̄ = b.

Corrigé : Supposons que la suite (xk )k→+∞ tende vers x̄. Alors (I − αD−1 A)xk tend
vers (I − αD−1 A)x̄. A la limite, on a donc

x̄ = (I − αD−1 A)x̄ + αD−1 b

si bien que Ax̄ = b puisque α est non nul.

2. Exprimez les coefficients de la matrice (I −αD−1 A) en fonction des coefficients de A.

Corrigé : On pose M = (I − αD−1 A). Alors


1 − α si i = j,
Mij =
−α Aij sinon.
Aii

3. On suppose que A est à diagonale strictement dominante et que 0 < α ≤ 1. Montrez

que
kI − αD−1 Ak∞ < 1. (2)
On rappelle qu’une matrice B ∈ Mn (R) est dite à diagonale strictement dominante
si,
Xn
∀i ∈ N, 1 ≤ i ≤ n, |Bi,j | < |Bi,i |.
j=1,j6=i

1
 Corrigé : Evaluons la norme infinie de M :
kM xk∞
kM k∞ = max .
x6=0 kxk∞
Or n n
X α X
(M x)i = Mij xj = − Aij xj + (1 − α)xi
j=1
A ii
j=1,j6=i

Donc, comme α > 0, 1 − α ≥ 0 et |xj | ≤ kxk∞ ∀j,

n
!
α X
|(M x)i | ≤ kxk∞ |Aij | + (1 − α)
|Aii | j=1,j6=i

La matrice étant à diagonale strictement dominante nj=1,j6=i |Ai,j | < |Aii |, on ob-
P
tient
kM k∞ < α + (1 − α) = 1.

4. Montrez que, sous les hypothèses de la question précédente, la méthode itérative (1)
converge.
Corrigé : Comme kM k∞ < 1 le rayon spectral ρ(M ) de la matrice d’itération est
strictement inférieur à 1 et la méthode itérative converge.
5. Quelle méthode étudiée en cours retrouve-t-on quand α = 1 ?
Corrigé : Quand α = 1 la méthode est celle de Jacobi, en effet (1) s’écrit Dxk+1 =
(D − αA)xk + α b et si l’on pose, comme en cours, A = D − E − F , avec α = 1 on
obtient Dxk+1 = (E + F )xk + b, la méthode de Jacobi.

Exercice 2 : résolution numérique des EDO

Soit f : R2 → R une fonction continue, lipschitzienne dans sa deuxième variable, de
constante de Lipschitz L. On s’intéresse au problème de Cauchy : trouver une fonction
y ∈ C 1 ([0, T ]) telle que 
y 0 (t) = f (t, y(t)) ∀t ∈]0, T ]
(3)
y(0) = y 0
T
Pour une discrétisation régulière tn = nh, 0 ≤ n ≤ N , h = N du segment [0, T ], on sou-
haite calculer les approximations yn ≈ y(tn ) de la solution exacte par le schéma suivant :

yn+1 = yn + h (f (tn , yn ) + f (tn+1 , yn+1 )) , 1 ≤ n ≤ N
2
(4)
y0 = y 0

1. La méthode est-elle implicite ou explicite ? Montrez que cette méthode est bien
définie si h < 2/L. Cette condition sera toujours supposée remplie dans la suite.
Corrigé : La méthode est implicite, pour calculer yn+1 il faut résoudre une équation
non linéaire. En effet, yn+1 satisfait yn+1 = g(yn+1 ) (yn+1 est un point fixe de g) où
la fonction g (qui dépend de yn de tn et de h) est donnée par
h
g(y) = yn + (f (tn , yn ) + f (tn + h, y)) .
2
2
 Si la fonction g est contractante, alors l’équation de point fixe aura une unique
solution. Or, puisque f est lipschitzienne dans sa deuxième variable,
h Lh
|g(y) − g(z)| = |f (tn + h, y) − f (tn + h, z)| ≤ |y − z|.
2 2
2
Autrement dit, si h < L
alors g est contractante et le schéma numérique est bien
défini.
2. Réécrivez le schéma (4) sous la forme générale d’un méthode à un pas :

yn+1 = yn + h Φ(tn , yn , h).

On explicitera la fonction Φ.
Corrigé : Définissons la fonction ϕ par :
(
(t, z, d) 7→ y ∗ = ϕ(t, z, d)
ϕ:
où y ∗ = z + d2 [f (t, z) + f (t + d, y ∗ )] .

Comme vu à la question précédente, cette fonction est parfaitement définie dès que
d < L2 . A l’aide de cette fonction, on voit que yn+1 = ϕ(tn , yn , h). Il s’en suit que le
schéma se réécrit comme une méthode à un pas
(
yn+1 = yn + h Φ(tn , yn , h)
avec Φ(t, y, h) = 21 [f (t, y) + f (t + h, ϕ(t, y, h)) ] .

3. On considère un schéma perturbé :


zn+1 = zn + h (f (tn , zn ) + f (tn+1 , zn+1 )) + εn , 1≤n≤N
2
(5)
z0 = z 0

Montrez que, sous la condition h < L2 , il existe des constantes A(Lh) et B(Lh) telles
que :
A(Lh)n − 1
|zn − yn | ≤ A(Lh)n |z0 − y0 | + B(Lh) max |εk |
A(Lh) − 1 k≤n
En déduire une propriété importante du schéma.
Corrigé : En soustrayant le schéma du schéma perturbé et en utilisant le caractère
lipschitzien de f on obtient :
Lh
|zn+1 − yn+1 | ≤ |zn − yn | + (|zn − yn | + |zn+1 − yn+1 |) + |εn |
2
d’où
Lh
1+ 2 1
|zn+1 − yn+1 | ≤ |z
Lh n
− yn | + |εn |
1− 2
1 − Lh
2
1+ Lh 1
et par récurrence en posant A(Lh) = 2
1− Lh
et B(Lh) = 1− Lh
:
2 2

A(Lh)n − 1
|zn − yn | ≤ A(Lh)n |z0 − y0 | + B(Lh) max |εk |
A(Lh) − 1 k≤n

3
 Cette inégalité prouve la stabilité du schéma, en effet : ∀α > 2, ∃ x0 (α) < 1 tel que
1+x
1−x
≤ exp(αx) pour 0 ≤ x ≤ x0 (α), ainsi A(Lh) ≤ exp(αLh) pour h ≤ h0 (α) < L2 ,
soit A(Lh)n ≤ exp(αLtn ) et ainsi :

|zn − yn | ≤ exp(αLtn )|z0 − y0 | + n B(Lh) exp(αLtn ) max |εk |

k≤n

4. En utilisant (et citant) des théorèmes vus en cours montrez que le schéma est consis-
tant et convergent.
Corrigé : On a vu en cours qu’un schéma à un pas est consistant si et seulement si
Φ(t, y, 0) = f (t, y), ∀y, ce qui est le cas ici, de plus on vient de démontrer la stabilité
du schéma et le théorème de Lax et Richtmayer nous dit qu’un schéma stable et
consistant est convergent.
5. On suppose que f ∈ C ∞ (R2 ) et on admet que la solution exacte est très régulière
sur [0, T ] (par exemple, y ∈ C 4 ([0, T ])). Démontrez que l’erreur locale de troncature
rn vérifie
y(tn+1 ) − y(tn )
rn = − Φ(tn , y(tn ), h) = K(tn )h2 + o(h2 )
h
où vous exprimerez K(tn ) en fonction de dérivées de la fonction y. En déduire l’ordre
du schéma.
Corrigé : A l’aide de développements de Taylor autour de tn+ 1 :
2

y(tn+1 ) − y(tn ) 1 0
rn = − (y (tn ) + y 0 (tn+1 ))
h 2
2
h2 (3)
 
0 h (3) 2 0 2
= y (tn+ 1 ) + y (tn+ 1 ) + o(h ) − y (tn+ 1 ) + y (tn+ 1 ) + o(h )
2 24 2 2 8 2

2
h
= − y (3) (tn+ 1 ) + o(h2 )
12 2

Le schéma est donc d’ordre 2.

Note : Une majoration utilisant des développements de Taylor-Lagrange évite de
garder des o(h2 ) :
h2 (3) h2 (3)
 
0 0
rn = y (tn+ 1 ) + y (tn+θ1 ) − y (tn+ 1 ) + y (tn+θ2 )
2 24 2 8
h2
|rn | ≤ sup |y (3) (t)|
6 t

6. Donnez une majoration de l’erreur en = |y(tn ) − yn | explicitant la convergence de

la méthode.
Corrigé : En utilisant l’inégalité de stabilité et la majoration de l’erreur locale de
troncature on obtient la convergence de la méthode, pour h ≤ h0 (α) :
 2 
h (3)
|y(tn )−yn | ≤ n B(Lh) exp(αLtn ) max |h rk | ≤ B(Lh) tn exp(αLtn ) sup |y (t)|
k≤n 6 t

4
Exercice 3 : polynôme d’interpolation
Soit f une fonction réelle, continue et dérivable sur [−1, 1] et x0 ∈]0, 1[.
Démontrez qu’il existe un unique polynôme Q de degré inférieur ou égal à 5 vérifiant :

Q(−x0 ) = f (−x0 ) Q(0) = f (0) Q(x0 ) = f (x0 )

Q0 (−x0 ) = f 0 (−x0 ) Q0 (0) = f 0 (0) Q0 (x0 ) = f 0 (x0 )

Attention : on ne demande pas de calculer ce polynôme !

Corrigé : Soit P5 l’espace vectoriel des polynômes de degré inférieur ou égal à 5.

Considérons l’application Φ de P5 dans R6 qui à un polynôme P associe le sextuplet
(P (−x0 ), P (0), P (x0 ), P 0 (−x0 ), P 0 (0), P 0 (x0 )). L’existence et l’unicité du polynôme Q est
équivalente à la bijectivité de Φ. L’application Φ étant une application linéaire entre deux
espace vectoriels de même dimension 6, elle est bijective si et seulement si elle est injective.
Pour vérifier l’injectivité de Φ il faut vérifier que son noyau est réduit au polynôme nul, or
si P ∈ ker(Φ) alors −x0 , 0 et x0 sont des racines doubles de P , P étant de degré inférieur
ou égal à 5 ce n’est possible que si P est le polynôme nul.