Mathématiques et analyse numérique

A. Aghaei

ISBS 1– FI/FA
EPISEN - Université Paris Est Créteil
 Contenu du cours

 Introduction

 Algèbre de matrices

 Résolution d’équations et de systèmes linéaires

 Résolution d’équations et de systèmes non-linéaires

 Interpolation polynomiale et méthode des moindres carrés

 Intégration numérique de fonctions

 Résolution d'équations différentielles

 Équation non-linéaire

Comme au chapitre 2, le nombre d’équations scalaires est supposé ici égal au nombre d’inconnues scalaires.
Rappelons que dans le cas linéaire il n’y a alors que trois possibilités :

 il n’y a pas de solution, car les équations sont incompatibles,

 la solution est unique,
 l’ensemble des solutions est un continuum, car une au moins des équations peut être déduite des autres par
combinaison linéaire, de sorte qu’il n’y a pas assez d’équations indépendantes.

Pour des équations non linéaires, il y a des possibilités nouvelles :

 une équation scalaire à une inconnue peut ne pas avoir de solution

 il peut y avoir plusieurs solutions isolées

Nous supposons qu’il existe au moins une solution et que l’ensemble des solutions est fini
 Équation non-linéaire

Soit 𝑓 ∶ ℝ𝑛 → ℝ une application. On s’intéresse à la résolution de l’équation algébrique

𝑓(𝑥) = 0.

L’équation ci-dessus est en fait un système d’équations algébriques non-linéaires. Pour résoudre ce système, on a
généralement recours à des méthodes itératives. On se donne donc une première approximation x0 = 𝑥(0) d’une solution
de cette équation et on construit une suite d’itérés 𝑥(1), 𝑥(2), . . . , 𝑥(𝑘), . . . qui converge vers un 𝑥ҧ ∈ ℝ𝑛 telle que

lim 𝑥𝑛 = 𝑥ҧ où 𝑥ҧ vérifie 𝑓(𝑥)ҧ = 0

Une équation non linéaire 𝑓(𝑥) = 0 sans solution Une équation non linéaire 𝑓(𝑥) = 0 avec plusieurs solutions isolées
 Convergence

Il existe une série de méthodes numériques (point fixe, bissection, etc.) conduisant à chercher numériquement les zéros
d’une fonction non-linéaire 𝑓 (𝑥) = 0 d’une variable réelle 𝑥. Ce qui distingue ces différentes méthodes, c’est entre autre,
leur vitesse de convergence et leur robustesse.

En pratique, on ne peut pas faire un nombre infini d’itérations . On se donne alors une précision (ou tolérance) 𝜖 et on
utilise un critère d’arrêt :
𝑓(𝑥 (𝑘) ) < 𝜖

ou 𝑥 (𝑘+1) − 𝑥 (𝑘) < 𝜖

𝑘+1 𝑘
𝑥 −𝑥
ou 𝑘
<𝜖
𝑥
 Convergence

On dit qu’une méthode itérative converge s’il existe 𝑥 ∈ ℝ tel que

lim 𝑥 (𝑘) − 𝑥 = 0
𝑘→∞

On dira qu’une méthode itérative est d’ordre 𝑝 (𝑝 ≥ 1) s’il existe une constante 𝐶, indépendante de 𝑘, telle que

𝑘 𝑝
𝑥 − 𝑥 (𝑘+1) ≤ 𝐶 𝑥 − 𝑥

Si 𝑝 = 1, on parle de convergence linéaire (Convergence si 𝐶 < 1)→ on gagne la même quantité de précision à
chaque itération

Si 𝑝 = 2, on parle de convergence quadratique (Convergence si 𝐶 |𝑥 − 𝑥 (0)| < 1) → on gagne le double

de précision à chaque itération

Pour 𝑛 suffisamment élevé, la vitesse de convergence est évaluée ainsi : 𝑥 𝑘+2 − 𝑥 𝑘+1
𝑉𝑝 𝑥, 𝑛 = 𝑘+1
(𝑥 − 𝑥 𝑘 )𝑝
 Méthode du point fixe

Le principe de cette méthode consiste à transformer la fonction 𝑓(𝑥) = 0, où 𝑓 ∶ [𝑎 𝑏] → 𝑅, en une fonction 𝑔(𝑥) = 𝑥. La
fonction 𝑔(𝑥), avec 𝑔: [𝑎 𝑏] → 𝑅, est construite de manière à ce que 𝑔(𝛼) = 𝛼 quand 𝑓 (𝛼) = 0. Trouver la racine de 𝑓 (𝑥) se
résume donc à déterminer un 𝛼 ∈ [𝑎 𝑏] tel que :

𝛼=𝑔 𝛼

Si un tel point 𝛼 existe, il sera qualifié de point fixe de la fonction 𝑔(𝑥) et cette dernière est appelée fonction d’itération. Le schéma
numérique de cette méthode est donné par :

𝑥 0 donné
൝
𝑥 𝑘+1 = 𝑔 𝑥 𝑘 avec n ≥ 0

Remarque : Etant donnée 𝑓(𝑥) , il y a plusieurs choix possibles pour 𝑔(𝑥).

Exemple :
𝑥2 − 𝑎 = 0 ⟺ 𝑥2 + 𝑥 − 𝑎 = 𝑥
1 𝑎
⟺ 𝑥+ =𝑥
2 𝑥

Quel est le bon choix pour 𝑔(𝑥) ? Il sera nécessaire de demander que 𝑔 soit « contractante » :
 Méthode du point fixe

Applications contractantes : Soit 𝑔: 𝐼 ⊂ ℝ → ℝ. On suppose :

• 𝐼 est un intervalle fermé non vide de ℝ

• Pour tout 𝑥 ∈ 𝐼, 𝑔(𝑥) ∈ 𝐼
• La fonction 𝑔 est contractante : Il existe une constante 0 ≤ 𝐶 < 1 telle que

𝑔 𝑥 −𝑔 𝑦 ≤ 𝐶 𝑥 − 𝑦 pour tous 𝑥, 𝑦 ∈ 𝐼

Alors 𝑔 admet un unique point fixe 𝑥ҧ ∈ 𝐼

Avantage et inconvénient
Facilité d’implémentation. L’inconvénient de la méthode du point fixe est qu’elle converge très lentement et qu’il peut y avoir
de multiples fonctions d’itération 𝑔(𝑥) (bien que 𝑓 (𝑥) ait une unique solution) ⇒ divergence
 Méthode du point fixe

Démonstration du code sous Matlab

[x,iter]=PointFixe(4,3,0.0001); function [x,iter]=PointFixe(a,x0,tol)

x=x0;
2.1667 erreur=1;
iter=0;
2.0064 while (erreur>tol) && (iter<100)
iter=iter+1;
2.0000 g_x=0.5*(x+a/x);
erreur=abs(y-x);
2.0000 x=y;
disp(x)
end
Méthode de la bissection ou dichotomie
Méthode de la bissection ou dichotomie
Méthode de la bissection ou dichotomie
Méthode de la bissection ou dichotomie
Méthode de la bissection ou dichotomie
Méthode de la bissection ou dichotomie
Méthode de la bissection ou dichotomie
Méthode de la bissection ou dichotomie
 Méthode de la bissection ou dichotomie

Cette méthode repose sur le théorème de la valeur intermédiaire. Soit 𝑓 ∶ [𝑎 𝑏] → ℝ une fonction continue sur
l’intervalle [𝑎 𝑏]. Si 𝑓 𝑎 × 𝑓 𝑏 < 0, il existe au moins une racine de 𝑓 (𝑥) appartenant à l’intervalle [𝑎 𝑏]. On
1
prend alors 𝑚 = 2 (𝑎 + 𝑏), soit la moitié de l’intervalle [𝑎 𝑏]. Le schéma numérique est le suivant :

• Si 𝑓 (𝑚) = 0 → 𝑚 est la racine de 𝑓 (𝑥)

• Sinon, calculer le signe de 𝑓 (𝑎) × 𝑓 (𝑚) 𝑒𝑡 𝑓 (𝑏) × 𝑓 (𝑚)

• Si 𝑓 𝑎 × 𝑓 𝑚 > 0, la racine se trouve dans l’intervalle [𝑚 𝑏] (𝑚 devient 𝑎)

• Si 𝑓 𝑎 × 𝑓 𝑚 < 0, la racine se trouve dans l’intervalle [𝑎 𝑚] (𝑚 devient 𝑏)

• Répéter ce processus de division par 2 de l’intervalle jusqu’`a convergence de l’algorithme pour la tolérance
considérée
Avantage et inconvénient

La méthode de la bissection est simple à mettre en œuvre et elle ne requiert pas de valeur initiale. Toutefois, elle souffre
d’un inconvénient du fait que son seul critère d’arrêt consiste à contrôler la longueur de l’intervalle In `a chaque
itération. Ceci risque de rejeter la racine recherchée, car elle ne tient pas suffisamment compte du comportement
effectif de 𝑓 (𝑥).
Méthode de la fausse position (ou de Lagrange ou Regula-falsi)
Méthode de la fausse position (ou de Lagrange ou Regula-falsi)
Méthode de la fausse position (ou de Lagrange ou Regula-falsi)
Méthode de la fausse position (ou de Lagrange ou Regula-falsi)
Méthode de la fausse position (ou de Lagrange ou Regula-falsi)
Méthode de la fausse position (ou de Lagrange ou Regula-falsi)
Méthode de la fausse position (ou de Lagrange ou Regula-falsi)
Méthode de la fausse position (ou de Lagrange ou Regula-falsi)
 Méthode de la fausse position (ou de Lagrange ou Regula-falsi)

Cette méthode découle explicitement de celle de la bissection. Néanmoins, elle est plus efficace, car elle tient compte
non seulement du signe de la fonction aux extrémités de l’intervalle, mais aussi de sa valeur aux bornes de l’intervalle
considéré.

Dans cette méthode, on divise [𝑎𝑘 𝑏𝑘 ] en [𝑎𝑘 𝑤 𝑘 ] et [𝑤 𝑘 𝑏𝑘 ], où 𝑤𝑛 est l’abscisse du point d’intersection de la droite
passant par les points (𝑎𝑘 , 𝑓 (𝑎𝑘 )) et (𝑏𝑘 , 𝑓 (𝑏𝑘 )), avec l’axe des abscisses. Donc, 𝑏𝑘 se définit comme suit :

𝑏𝑘 − 𝑎𝑘 𝑏𝑘 − 𝑎𝑘 𝑎𝑘 𝑓 𝑏𝑘 − 𝑏𝑘 𝑓(𝑎𝑘 )
𝑤𝑘 = 𝑏𝑘 −𝑓 𝑏𝑘 × 𝑘 𝑘
=𝑎 −𝑓 𝑎 × =
𝑓 𝑏𝑘 − 𝑓 𝑎𝑘 𝑓 𝑏𝑘 − 𝑓 𝑎𝑘 𝑓 𝑏𝑘 − 𝑓 𝑎𝑘

Avantage et inconvénient
La méthode de la fausse position est simple à mettre en œuvre et elle ne requiert pas de valeur initiale. En effet,
l’algorithme est construit de façon analogue à celui de la bissection, en omettant de prendre la moitié de l’intervalle de
travail après chaque itération. Par rapport à ce dernier, l’algorithme de la fausse position est plus précis, mais converge
deux fois plus lentement.
Méthode de Newton
Méthode de Newton
Méthode de Newton
Méthode de Newton
 Méthode de Newton

Comme commenté précédemment, la méthode de la bissection exploite uniquement le signe de la fonction 𝑓 (𝑥) aux
extrémités des sous-intervalles. Si la fonction 𝑓 (𝑥) est différentiable, on peut établir une méthode plus efficace en
exploitant les valeurs de la fonction 𝑓 (𝑥) et de ses dérivées, 𝑓 ′ (𝑥), 𝑓 ′′ (𝑥), etc.

Géométriquement, la solution approchée 𝑥 𝑘+1 est le point d’intersection de l’axe des abscisses et de la tangente au
point (𝑥 𝑘 , 𝑓(𝑥 𝑘 )). Le schéma numérique est définit comme suit :

𝑓 𝑥 (𝑘)
𝑥 (𝑘+1) = 𝑥 (𝑘) − ′ (𝑘)
𝑓 (𝑥 )

Avantage et inconvénient
• La méthode de Newton nécessite à chaque itération l’évaluation de deux fonctions : 𝑓 (𝑥) et sa dérivée 𝑓 ′ 𝑥 .
• Toutefois, elle possède une vitesse de convergence accrue, car cette méthode est d’ordre 2.
• Sa vitesse de convergence est conditionnée par le choix d’une valeur initiale relativement proche du zéro recherché.
• La méthode de Newton converge de façon quadratique uniquement dans le cas où la racine recherchée de 𝑓 (𝑥) est
simple. Dans le cas contraire, elle converge de façon linéaire.
 Un exemple : Calcul de 2

On prend 𝑓(𝑥) = 𝑥 2 − 2. Donc 𝑓′(𝑥) = 2𝑥

D’où la méthode itérative

2
𝑓 𝑥 (𝑘) 𝑥 (𝑘) − 2 (𝑥 (𝑘) )2 +2
𝑥 (𝑘+1) (𝑘) (𝑘)
= 𝑥 − ′ (𝑘) = 𝑥 − =
𝑓 𝑥 2𝑥 (𝑘) 2𝑥 (𝑘)

Notons que si 𝑥 (0) > 0 alors 𝑥 (𝑘) > 0 pour tout 𝑘. On montre que la suite (𝑥 (𝑘) ) est positive, décroissante (à partir du
deuxième terme) et bornée. Donc elle converge.

Choisissons par exemple : 𝑥 (0) = 1. On a

(1)
(𝑥 (0) )2 +2
𝑥 = = 1,5
2𝑥 (0)

(2)
(𝑥 (1) )2 +2
𝑥 = = 1,41666666666667
2𝑥 (1)

(3)
(𝑥 (2) )2 +2 Rappel : 2 = 1,414213562373095 . . .
𝑥 = = 1,41421568627451
2𝑥 (2) Erreur : 0,00015 %
 Résolution de systèmes d’équations non-linèaires

Peut-on également résoudre des systèmes d’équations ?

Jusqu’à présent, nous nous sommes intéresses uniquement à des équations non-linéaires simples (i.e., ne dépendant que
d’une seule variable 𝑥). Cependant, certaines des méthodes vues précédemment permettent aussi de résoudre
numériquement des systèmes d’équations non-linéaires. Nous allons appliquer la méthode de Newton à un cas simple, à
savoir la résolution d’un système de deux équations non-linéaires à 2 inconnues, de la forme :

𝑓 𝑥, 𝑦 = 0
ቊ
𝑔 𝑥, 𝑦 = 0

Dans ce cas, le schéma numérique de l’algorithme de Newton devient :

−1
𝜕𝑓 𝑥, 𝑦 𝜕𝑓 𝑥, 𝑦
𝑥 𝑘+1 𝑥𝑘 𝜕𝑥 𝜕𝑦 𝑓(𝑥 𝑘 , 𝑦 𝑘)
= 𝑘 − .
𝑦 𝑘+1 𝑦 𝜕𝑔 𝑥, 𝑦 𝜕𝑔 𝑥, 𝑦 𝑔(𝑥 𝑘 , 𝑦 𝑘)
𝜕𝑥 𝜕𝑦

Notons que ce schéma fait maintenant intervenir des dérivées partielles et l’inverse d’une matrice.
 Résolution de systèmes d’équations non-linèaires

Calcul au moyen de routines Matlab

Matlab dispose également de commandes prédéfinies destinées à chercher les zéros d’une équation non-linéaire ou d’un
système d’équations non-linéaires :

• fzero : racine d’une équation

• fsolve : résolution de système d’ équations

La commande fzero cherche un zéro d’une fonction 𝑓(𝑥) autour de la valeur initiale 𝑥0 indiquée. La racine approchée 𝑥
renvoyée est prés d’un point ou fun change de signe. La commande renvoie NaN (Not a Number) dans le cas où la
recherche de la racine a échoué. L’argument options recèle les options d’optimisation indiquées dans optimset.