ANALYSE NUMÉRIQUE
Analyse numérique
Ma123 – AERO 1
(IPSA) Inst. Polytech. des Sciences Avancées 2020 1 / 21
Algorithmes de résolution d’équation
On s’intéresse dans ce cours à la résolution d’équations à
une seule inconnue réelle.
f (x) = 0
Une telle équation peut se présenter sous la forme
f (x) = 0 où f est une fonction. Les solutions de
l’équation sont aussi appelés des zéros de f .
(IPSA) Inst. Polytech. des Sciences Avancées 2020 2 / 21
Algorithmes de résolution d’équation
Point fixe
Une équation peut aussi se présenter sous la forme
g(x) = x. Les solutions de l’équation sont les points fixes
de g
(IPSA) Inst. Polytech. des Sciences Avancées 2020 3 / 21
Algorithmes de résolution d’équation
Méthode du point fixe
Pour rappel, la méthode du point fixe consiste à
considérer des suites définies par x0 choisi et la
récurrence
xn+1 = g(xn )
Si la suite converge, elle converge vers un point fixe de g,
une valeur α vérifiant g(α) = α.
Rappelons que la convergence de la suite n’est pas
assurée en général.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 4 / 21
Algorithmes de résolution d’équation
Méthode de Newton
Dans le cas d’une équation f (x) = 0, où f est dérivable,
la méthode de Newton consiste à considérer une suite
définie par x0 ∈ R, et la récurrence
f (xn )
xn+1 = xn −
f 0 (xn )
Si la suite converge vers une valeur α où f 0 (α) 6= 0, α
est un zéro de f .
On a vu que la convergence de la méthode de Newton
est qualifiée de quadratique, en général plus rapide que
celle du point fixe, qui est linéaire.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 5 / 21
Algorithmes de résolution d’équation
Méthode de dichotomie
La méthode de dichotomie s’applique dans le cas où on
doit résoudre une équation f (x) = 0, avec f une
fonction continue.
On suppose connus deux réels a < b tels que f (a) et
f (b) ont des signes opposés.
Il y a donc une solution de l’équation placée entre a et b
d’après le théorème des valeurs intermédiaires.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 6 / 21
Algorithmes de résolution d’équation
Description de l’algorithme de
dichotomie
La méthode consiste à construire deux suites qui
constitueront des encadrements de plus en plus précis de
la solution.
On pose a0 = a et b0 = b pour initialiser les suites. Et on
construit de proche en proche les termes suivants.
a0 + b 0
On pose c0 = , le milieu de [a0 , b0 ].
2
L’idée de l’algorithme consiste à se demander si la
solution est dans l’intervalle [a0 , c0 ] ou dans [c0 , b0 ].
(IPSA) Inst. Polytech. des Sciences Avancées 2020 7 / 21
Algorithmes de résolution d’équation
On calcule f (c0 ). Si f (c0 ) = 0, il n’est pas utile de
poursuivre l’algorithme puisque c0 est exactement une
solution de l’équation : on a trouvé ce que l’on cherchait
à déterminer !
Si f (c0 ) a un signe opposé à celui de f (a0 ), on pourra
poser a1 = a0 et b1 = c0 . Dans ce cas, on aura f (a1 ) et
f (b1 ) de signes opposés et donc une solution placée dans
[a1 , b1 ].
Si en revanche f (c0 ) a le même signe que f (a0 ), on
posera a1 = c0 et b1 = b0 . On aura f (a1 ) et f (b1 ) de
signes opposés.
Il y aura donc, dans ce cas aussi, une solution dans
l’intervalle [a1 , b1 ].
(IPSA) Inst. Polytech. des Sciences Avancées 2020 8 / 21
Algorithmes de résolution d’équation
On réitère l’algorithme à partir de a1 et b1 pour
déterminer a2 et b2 . Et ainsi de suite...
Dans certains cas, à une étape donnée, on s’interrompt
car f (cn ) = 0 à une certaine étape.
Sinon, à chaque étape f (an ) et f (bn ) sont de signes
opposés, et donc on a une solution dans l’intervalle
[an , bn ].
Par ailleurs, il est à remarquer qu’à chaque étape, la
longueur Ln = bn − an de l’intervalle considéré est
divisée par 2.
L0
On a donc Ln = n . On a des encadrements de plus en
2
plus précis d’une solution α de l’équation.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 9 / 21
Algorithmes de résolution d’équation
Les suites (an ) et (bn ) sont adjacentes, an est croissante,
bn décroissante et la différence Ln = bn − an tend vers 0.
Les deux convergent vers une même limite α.
On peut majorer l’erreur commise en estimant α avec an
b−a
en remarquant que |α − an | ≤ Ln ≤ n .
2
Pour discuter de la vitesse de convergence, on se réfère
1
donc à une suite géométrique de raison . On peut
2
parler d’une convergence linéaire, comme pour une
méthode de point fixe.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 10 / 21
Algorithmes de résolution d’équation
1
C’est le rapport qui indique la vitesse de convergence.
2
On peut avoir avec la méthode de point fixe des
méthodes convergeant plus rapidement que celle de
dichotomie si g est contractante avec un rapport de
1
Lipschitz k ≤ .
2
(IPSA) Inst. Polytech. des Sciences Avancées 2020 11 / 21
Algorithmes de résolution d’équation
Remarques
La méthode de dichotomie est une méthode qui permet
de trouver une solution avec des hypothèses assez
réduites sur le problème (f continue, et la connaissance
de a et b avec f (a)f (b) < 0).
Certains algorithmes combinent la dichotomie pour
déterminer une première approximation de la solution et
ensuite une autre méthode (par exemple celle de
Newton) pour ensuite améliorer rapidement la précision.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 12 / 21
Algorithmes de résolution d’équation
Remarques (suite)
Une des limites importantes de la méthode de
dichotomie est qu’elle ne peut pas être généralisée à des
problèmes à plusieurs inconnues (systèmes d’équations)
ou au cas d’une inconnue complexe, à la différence des
méthodes du point fixe ou de Newton.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 13 / 21
Algorithmes de résolution d’équation
Méthode de la sécante
Soit une fonction f dont on cherche les zéros.
La méthode de la sécante consiste à construire une suite
xn de proche en proche dont on souhaite qu’elle tende
vers un zéro de f .
On fixe x0 et x1 deux réels distincts, les premiers termes
de la suite.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 14 / 21
Algorithmes de résolution d’équation
On considère la droite reliant les deux points du graphe
de f d’abscisses x0 et x1 . On considère le point
d’intersection de cette droite avec l’axe (Ox). On définit
x2 son abscisse.
On réitère le procédé : à partir des points d’abscisse x1
et x2 du graphe, on considère la droite les reliant et son
intersection avec l’axe (Ox), ce qui définit x3 .
Et ainsi de suite.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 15 / 21
Algorithmes de résolution d’équation
Explicitons la récurrence.
Plaçons dans le cadre du calcul de x2 .
Soit y = αx + β la droite passant par les points
d’abscisse x0 et x1 du graphe.
On a αx0 + β = f (x0 ) et αx1 + β = f (x1 ).
Donc αx0 x1 + βx1 = x1 f (x0 ) et
αx0 x1 + βx0 = x0 f (x1 ).
D’où on tire (x1 − x0 )β = x1 f (x0 ) − x0 f (x1 )
(IPSA) Inst. Polytech. des Sciences Avancées 2020 16 / 21
Algorithmes de résolution d’équation
Par ailleurs α(x1 − x0 ) = f (x1 ) − f (x0 ).
Noter que l’on cherche x2 tel que αx2 + β = 0. En
multipliant par x1 − x0 , on aura :
(f (x1 ) − f (x0 ))x2 + x1 f (x0 ) − x0 f (x1 ) = 0
et donc l’expression de x2 donnée par
x0 f (x1 ) − x1 f (x0 )
x2 =
f (x1 ) − f (x0 )
(IPSA) Inst. Polytech. des Sciences Avancées 2020 17 / 21
Algorithmes de résolution d’équation
La méthode de la sécante
On fixe x0 et x1 et on définit de proche en proche :
xn f (xn+1 ) − xn+1 f (xn )
xn+2 =
f (xn+1 ) − f (xn )
(IPSA) Inst. Polytech. des Sciences Avancées 2020 18 / 21
Algorithmes de résolution d’équation
Remarque
Noter que cette méthode est construite sur une
récurrence, mais xn+2 dépend de xn et de xn+1 . C’est un
type de récurrence différent de celle du pont fixe ou de
Newton.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 19 / 21
Algorithmes de résolution d’équation
La méthode de la sécante est une méthode de
quasi-Newton
On peut aussi présenter la récurrence de la méthode de
la sécante ainsi :
f (xn+1 )
xn+2 = xn+1 − f (xn+1 )−f (xn )
xn+1 −xn
Lorsque xn et xn+1 sont voisins, le quotient
f (xn+1 ) − f (xn )
est proche de f 0 (xn+1 ), il s’avère que
xn+1 − xn
la méthode de la sécante est en quelque sorte une
approximation de la méthode de Newton. On parle de
méthode de quasi-Newton.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 20 / 21
Algorithmes de résolution d’équation
Notons que si xn converge vers l avec f 0 (l) 6= 0, on aura
f (l)
l=l− 0 et donc f (l) = 0. C’est donc bien une
f (l)
méthode qui converge vers un zéro de f lorsqu’elle
converge.
Noter que la méthode de la sécante converge moins
rapidement que celle de Newton mais qu’elle a sur la
méthode de Newton l’avantage, parfois très précieux, de
ne pas reposer sur la connaissance de f 0 . Dans les cas
favorables, elle s’avère converger plus rapidement que les
méthodes de point fixe générales.
(IPSA) Inst. Polytech. des Sciences Avancées 2020 21 / 21