1. Introduction

2. Méthode itérative générale

3. Méthode de Newton-Raphson

4. Résolution d'une équation polynomiale

    4.1. Application de la méthode de Newton au calcul d'une racine carrée
 
    4.2. Application à la recherche des valeurs nulles des équations transcendantes

5. Méthode de Bairstow

6. Résolution des systèmes d'équations non-linéaires
    6.1. Généralisation de la méthode de Newton-Raphson
    6.2. Utilisation d'une méthode de minimisation de fonctions

1. Introduction

Dans la pratique, la plupart des problèmes se ramènent à la résolution d’une équation de la forme : 
La résolution de cette équation dépend de la classe à laquelle appartient la fonction  f. Si  f est un polynôme de degré n, on sait que l’équation possède n racines complexes. Si l’équation est transcendante, elle peut avoir un nombre fini, voire nul, ou infini de racines. Le problème est alors de trouver la racine dont on sait l’existence et dont, parfois, on connaît une valeur approchée.
Les méthodes de résolution sont toujours des méthodes itératives.

2. Méthode itérative générale

On suppose que l’équation a été mise sous la forme :  (ceci est toujours possible en définissant par exemple  puisque lorsque,  ).

À partir d’une valeur initiale x₁, que l’on se donne, on engendre la suite :

Si la suite des mesures x₁, x₂, x₃,…, x_n converge vers une valeur x₀, alors : , et  ; x₀ est une racine.

Supposons que l’équation admette une racine x₀ sur l’intervalle [a,b]. On peut légitimement supposer que f(x) prendra des valeurs sur cet intervalle. Si l’on n’ajoute pas d’hypothèses supplémentaires, on ne peut être sûr de la convergence. Il est donc impossible de donner une condition nécessaire sans expliciter la fonction f. C’est donc une étude de cas.

3. Méthode de Newton-Raphson

Cette méthode s’applique à des équations du type , pour lesquelles on peut calculer la dérivée de f :  f’(x). Soit x₁ une valeur approchée de la racine s inconnue. Posons : x₂=x₁+h, et cherchons l’accroissement qu’il faut donner à x₁, de façon à ce que :

Après développement en série de Taylor à l’ordre 2, on obtient :

ou approximativement : 
 

c’est à dire :

et plus généralement, la solution :,soit 
Interprétation géométrique :

La valeur x₂ est l’abscisse du point d’intersection avec l’axe ox de la tangente au graphe y=f(x) en x₁.

Sens de l’approximation :

Si l’on avait fait aucune approximation dans l’écriture de , on aurait obtenu, pour la racine s, l'expression suivante :

donc :

Ce qui conduit à la conclusion suivante :

• Si ,

x₂ est plus proche de s que x₁, et il est du même côté : x₂ est donc une meilleure approximation. Si la racine est simple, et si f’ conserve un signe constant au voisinage de la racine, la suite est une suite monotone bornée par 0 ; elle converge, donc l’algorithme converge.

• Si ,

x₁ et x₂ sont de part et d’autre de s : l’approximation x₂ peut alors être moins bonne que x₁. mais si la racine est simple, f(x₂) sera de signe contraire à celui de f(x₁) : f(x₁) et f(x₂) seront alors de même signe et l’algorithme converge.

L’application de la méthode de Newton implique le calcul du polynôme  et de sa dérivée .
Écrivons le polynôme  sous la forme :

La division de  par le monôme  où  est une valeur arbitraire donne :

où R est une constante de valeur.

En divisant de nouveau le polynôme de degré n-1 par , on obtient :

Donc :

 

La valeur de la constante S est donnée par : .

L’application de la formule de Newton peut donc se faire sous la forme : 

Les valeurs de R et de S s’obtiennent donc au moyen des relations de récurrence qu’on établit en égalant les puissances successives de x dans les diverses expressions du polynôme :

De même, les coefficients  s’obtiennent au moyen de formules analogues :

On peut remarquer que le calcul de R et de S est analogue à celui du calcul des polynômes  et .
 

4.1. Application de la méthode de Newton au calcul d’une racine carré

Soit l’équation 
 

La formule de Newton s'écrit :

 

soit la formule de récurrence :

Quand n tend vers l’infini, x_n+1 tend vers x_n et par conséquent : 
Cet algorithme converge quelque soit la valeur de x₁ d’initialisation, pourvu que .
 

4.2. Application à la recherche des valeurs non nulles des équations transcendantes

Dans le cas d'un problème unidimensionnel de conduction de la chaleur dans une barre par exemple de longueur, la solution analytique de la température obtenue par la méthode d'orthogonalisation est la somme d'une réponse en régime transitoire et d'une réponse en régime permanent. Selon l'axe  de la barre, cette solution est de la forme :

                                     (1)

à cette solution, on ajoute l'équation transcendante donnée par :

                                                                                 (2)

Pour déterminer la température  à tout instant  et en tout point , on doit résoudre l'équation transcendante (2) afin d'obtenir les racines .
L'équation (2) est du type : et 

En traçant sur le même graphe  et , on obtient les courbes de la figure 2.

D'après ce graphe, on voit bien qu'il existe une solution par intervalle  où . Cette solution est l'intersection de la courbe  avec celle de .

D'où pour l'intervalle  comme cela est indiqué sur le graphique, on a les cinq racines suivantes pour une valeur égale à  du terme  () :

1^ère racine = 0.988241
2^ème racine = 3.542166
3^ème racine = 6.509659
4^ème racine = 9.580092
5^ème racine = 12.684082

5. Méthode de Bairstow

La méthode de Bairstow permet de calculer des racines réelles ou complexes d’une équation polynomiale à coefficients réels. La méthode consiste à extraire (le plus exactement possible) les racines (réelles ou complexes) deux à deux (à la fin, il en reste éventuellement une), jusqu’à épuisement des n racines.
Soit à trouver les racines de l’équation polynomiale suivante :

On effectue la division eucludiènne de f par le trinôme , où p et q sont à priori deux nombres quelconques :

Les coefficients  dépendent de p et q, de même que r et S.

Si  r=S=0, alors f(x)=0 permet de donner  (donc deux racines de f(x) déjà).

Si r et/ou S ne sont pas nuls, la méthode de Bairstow va consister à déterminer par approximations successives les valeurs de p et q qui annulent r et s :

Ce système peut être non linéaire. On le supposera linéaire au voisinage de chaque couple (p,q) fixé.

Pour cela ,on se donne 2 valeurs p₀ et q₀ arbitraires. On calcule alors successivement  et  de telle sorte que :

Soit au premier ordre en  et  :

Si l’on pose :

et

La solution du système précédent est (Cramer) :

Les expressions qui entrent dans le calcul de d, P et Q vont être évaluées par étapes. Les coefficients  sont liés aux coefficients  du polynôme initial par l’intermédiaire ses relations suivantes :

relations auxquelles on peut ajouter :

en ayant défini  et  par :  et .

Ce tableau (I) permet de calculer les , r et S en fonction de p et q.

Posant maintenant :

, avec k=0, 1, 2, …, n-1 et 

En dérivant le tableau (I) par rapport à p, on obtient :

 

Ce tableau (II) permet de calculer les C_i (i=0 ,1, 2, …, n-1).

Posons maintenant :

, 

En dérivant le tableau (I) par rapport à q, il vient :

la comparaison des tableaux (II) et (III) montre que :

, pour 

On en conclut alors :

et 

Les tableaux (I) et (III) permettent de calculer les dérivée partielles :

et par conséquent, les quantités d, P, Q recherchées sont :

Mise en œuvre de la méthode :

Le calcul du premier trinôme  s’obtient à l’issue des phases de calcul suivantes :

1. On fixe arbitrairement deux valeurs p₀ et q₀.
2. On calcule alors les deux valeurs :

On constitue le tableau : , et le tableau .
On calcule d, P et Q et on en déduit :  et 

3. Si  et , alors les racines de  sont les racines du polynôme initial.
4. Sinon, on remonte en 2 en reportant des valeurs  et , et ainsi de suite.

Les deux premières racines ayant été extraites, on applique de nouveau la méthode de Bairstow au polynôme quotient.

6. Résolution des systèmes d’équations non linéaires

6.1.  Généralisation de la méthode de Newton-Raphson

La méthode Newton peut s ‘appliquer à la résolution d’un système de plusieurs équations non linéaires :

A partir d’un couple de valeurs approchées (x₁,y₁) d’une solution du système, on peut déterminer deux accroissements h et k à donner à x₁ et y₁ de manière à ce que :

En développant en 1^er ordre, il vient :

 

où l’on a posé :

et

Les quantités h et k s’obtiennent donc, en résolvant le système linéaire suivant :

avec :

Le calcul est alors relancé jusqu’à ce que h et k deviennent inférieures à une valeur e que l’on se donne (selon la précision voulue pour le calcul).
Ainsi, l’algorithme correspondant est :

avec : 

ou encore :

Cette méthode de résolution peut être généralisée pour la résolution de système de n équations non linéaires à n inconnues.
 

6.2.  Utilisation d’une méthode de minimisation de fonctions

La résolution du système non linéaire suivant :

peut se ramener à la recherche du minimum de la fonction : qui étant écrite sous la forme d’une somme de deux fonctions est positive ou nulle.

Puisque les méthodes de minimisation d’une fonction (annulation de la dérivée, par exemple) ne donnent pas forcément le minimum absolu d’une fonction, il est nécessaire de vérifier que le minimum trouvé est bien la solution recherchée ; c’est à dire celle pour laquelle on a .