RECHERCHE DES RACINES



MÉTHODES NUMÉRIQUES

1. Complexité

1.1. NP-Complétude

2. Partie entière

3. Algorithme d'Héron

4. Algorithme d'Archimède

5. Calcul du nombre d'Euler

6. Systèmes d'équations linéaires

6.1. Une équation à une inconnue

6.2. Deux équations à deux inconnues

6.3. Trois équations à trois inconnues

6.4. N équations à n inconnues

7. Polynômes

8. Régressions et interpolations

8.1. Régression linéaire à une variable explicative

8.1.1. Droite de régression

8.1.2. Méthodes des moindres carrés

8.1.3. Analyse de la variance de la régression

8.2. Régression logistique

8.3. Interpolation polynômiale

8.3.1. Courbes de Bézier

8.3.2. Méthodes d'Euler

8.3.3. Polynôme de collocation

9. Recherche de racines

9.1. Méthodes des parties proportionnelles

9.2. Méthode de la bissection

9.3. Méthode de la sécante (Regula Falsi)

9.4. Méthode de Newton

10. Aires et sommes de riemann

10.1. Méthode des rectangles

10.2. Méthode des trapèzes

11. Programmation linéaire

11.1. Algorithme du simplexe

12. Méthode de Monte-Carlo

12.1. Calcul d'une intégrale

12.2. Calcul de PI

12.3. Dichotomie

13. Analyse en composantes principales (A.C.P.)

14. Analyse factorielle des correspondances (A.F.C.)

15. Khi-2

16. Méthode des différences finies

17. Réseaux de neurones formels

17.1. Modèle de neurone

17.2. Fonctions de transfert

17.3. Architecture de réseau

18. Algorithmes génétiques

18.1. Codage et population initiale

18.2. Les opérateurs

18.2.1. Opérateur de sélection

18.2.2. Opérateur de croisement

18.2.3. Opérateur de mutation

Bien des équations rencontrées en pratique ou en théorie ne peuvent pas être résolues exactement par des méthodes formelles ou analytiques. En conséquence, seule une solution numérique approchée peut être obtenue en un nombre fini d'opération.

Evariste Galois a démontré, en particulier, que l'équation equation ne possède pas de solution algébrique (sauf accident...) si equation est un polynôme de degré supérieur à 4.

Il existe un grand nombre d'algorithmes permettant de calculer les racines de l'équation equation avec une précision théorique arbitraire. Nous n'en verrons que les principaux. Attention, la mise en oeuvre de tels algorithmes nécessite toujours une connaissance approximative de la valeur cherchée et celle du comportement de la fonction près de la racine. Un tableau des valeurs de la fonction et sa représentation graphique permettent souvent d'acquérir ces connaissances préliminaires.

Si l'équation à résoudre est mise sous la forme equation, nous traçons les courbes représentant g et h. Les racines de l'équation equation étant données par les abscisses des points d'intersection des deux courbes.

Remarque: Avant de résoudre numériquement l'équation equation, il faut vérifier que la fonction f choisie. Il faut par exemple, que la fonction soit strictement monotone au voisinage de la racine equation, lorsque la méthode de Newton est appliquée. Il est souvent utile, voire indispensable, de déterminer un intervalle [a,b] tel que:

- f est continue sur equation ou equation

- equation

- equation unique, equation

MÉTHODE DES PARTIES PROPORTIONNELLES

La mise en oeuvre, sur calculatrice, de cette méthode est particulièrement simple. Les conditions à vérifier étant seulement:

- f est continue

- f est monotones dans un voisinage de la racine equation

Dans un petit intervalle, nous pouvons remplacer une courbe par un segment de droite. Il y a plusieurs situations possible mais en voici une particulière généralisable facilement à n'importe quoi:

equation
  (57.206)

Sur cette figure nous tirons à l'aide des théorèmes de Thalès (cf. chapitre de Géométrie Euclidienne):

equation   (57.207)

d'où :

equation   (57.208)

Si equation, nous pouvons négliger f(a) au dénominateur et il vient :

equation   (57.209)

L'algorithme consiste donc à réaliser les étapes suivantes :

1. Choisir a et b, calculer f(a) et f(b

2. Déterminer equation. Si equation est assez petit, nous arrêtons le calcul et affichons x et f(x)

3. Sinon nous procédons comme suit:

- Nous remplaçons b par a et f(b) par f(a

- nous remplaçons a par x et f(a)  par f(x)

- nous retournons au point (2)

MÉTHODE DE LA BISSECTION

La condition préalable à satisfaire pour cette méthode est de trouver un intervalle equation tel que:

1.  f(x) est continue sur [a,b]

2. equation

Il faut encore fixer equation qui est définit comme la borne supérieure de l'erreur admissible.

La méthode consiste à appliquer successivement les 4 étapes suivantes:

1. Calcul de equation

2. Evaluation de  f(x)

3. Si equation alors le travail est terminé, il faut afficher x et  f(x)

4. Sinon on procède comme suit:

- on remplace a par x si equation

- on remplace b par x si equation ou equation

- on retourne en (1)

L'étape (3) impose la condition equation pour l'arrêt des calculs. Il est parfois préférable de choisir un autre critère de fin de calcul. Celui-ci impose à la solution calculée d'être confinée dans un intervalle de longueur equation contenant equation. Ce test s'énonce comme suit:

3'. Si equation, le travail est terminé et equation est affiché. Il est bien sûr évident que equation

MÉTHODE DE LA SÉCANTE (REGULA FALSI)

equation
  (57.210)

Les conditions préalables sont les suivantes:

Il faut déterminer un intervalle [a,b] tel que:

1.  f(x) est continue sur [a,b]

2. equation

Si equation est le point de coordonnées equation, alors les points equation sont alignés sur la sécante. La proportion suivante (Thalès) est donc vraie:

equation   (57.211)

nous en déduisons:

equation   (57.212)

La méthode consiste à appliquer successivement les étapes suivantes:

1. Calcul de equation

2. Evaluation de equation

3. Si equation, le travail est terminé. Il faut afficher equation

4. Sinon nous procédons comme suit:

- nous remplaçons a par equation si equation

- nous remplaçons b par equation si equation ou equation

- nous retournons en (1)

La condition (3) peut être remplacée par la condition:

3'. Si equation, alors le travail est terminé et nous affichonsequation

Remarque: Si l'intervalle [a,b] contient plusieurs racines, cette méthode converge vers l'une d'entre elles. Toutes les autres sont malheureusement perdues.

MÉTHODE DE NEWTON

Considérons la figure suivante:

equation
  (57.213)

Si equation est une approximation de la racine equation, nous remarquons que equation en est une meilleure. equation est l'intersection de la tangente à la courbe en equation et de l'axe des abscisses. equation est encore une meilleure approximation de equation, equation est obtenu de la même manière que equation mais à partir de equation.

Le méthode de Newton consiste en la formalisation de cette constatation géométrique.

Pour utiliser cette technique, rappelons que si nous prenons une fonction f qui est dérivable en equation, alors nous pouvons la réécrire sous la forme:

equation   (57.214)

equation est la dérivée de f en equation et equation est une fonction qui tend vers 0 comme equation pour equation lorsque x tend vers equation (c'est un terme correctif qui sous-tend la suite des termes du développement de Taylor).

En appliquant ce résultat à la résolution de equation, nous obtenons:

equation   (57.215)

La fonction equation empêche la résolution de cette équation par rapport à equation. En négligeant le terme equation, l'équation se réécrit:

equation   (57.216)

et se résout aisément par rapport à equation:

equation   (57.217)

Mais equation ne satisfait pas, en générale, l'égalité equation. Mais comme nous l'avons déjà souligné, equation est plus petit que equation si la fonction f satisfait à certaines conditions.

La méthode de Newton consiste à remplacer l'équation:

equation   (57.218)

par:

equation   (57.219)

et à résoudre itérativement cette équation.

Les conditions suivantes sont suffisantes pour assurer la convergence de la méthode:

Dans un intervalle [a,b] comprenant equation et equation il faut que:

1. La fonction soit deux fois dérivable

2. La dérivée f ' ne s'annule pas (monotonie)

3. La deuxième dérivée soit continue et ne s'annule pas (pas de point d'inflexion)

Remarque: Il suffit souvent de vérifier les conditions (1) et (2) pour que le processus soit convergent.

La condition (2) est évidente, en effet si equation alors l'itération peut conduire à une erreur de calcul (singularité).

La condition (3) est moins évidente, mais le graphique suivant illustre un cas de non-convergence. Dans ce cas, le processus à une boucle calculant alternativement equation et equation.

equation
  (57.220)

Si la fonction f est donnée analytiquement, sa dérivée peut-être déterminée analytiquement. Mais dans bien des cas, il est utile, voire indispensable de remplacer equation par le quotient différentiel:

equation   (57.221)

h doit être choisi suffisamment petit pour que la différence:

equation   (57.222)

soit elle aussi suffisamment petite.

L'itération s'écrit alors:

equation   (57.223)

Convergence de la méthode:

Si la méthode de résolution est convergente, l'écart entre equation et equation diminue à chaque itération. Ceci est assuré, par exemple, si l'intervalle [a,b] contenant equation, voit sa longueur diminuer à chaque étape. La méthode de Newton est intéressante car la convergence est quadratique:

equation   (57.224)

alors que la convergence des autres méthodes est linéaire:

equation   (57.225)

Considérons, par exemple, la méthode de la bissection vue précédemment. A chaque itération la longueur de l'intervalle [a,b] diminue de moitié. Ceci nous assure que l'écart equation est réduit de moitié à chaque étape du calcul:

equation   (57.226)

Pour démontrer la convergence quadratique de la méthode de Newton, il faut utiliser les développements limités de et ' au voisinage de equation:

equation   (57.227)

Mais:

equation   (57.228)

donc:

equation   (57.229)

En soustrayant equation à gauche et à droite de l'égalité et en mettant les deux termes du seconde membre au même dénominateur, il vient:

equation   (57.230)

et dès que equation est assez petit, le dénominateur peut être simplifié.

equation   (57.231)

ce qui montre bien que la convergence est quadratique.

AIRES ET SOMMES DE RIEMANN

Considérons la figure suivante :

equation
  (57.232)

Nous désirons calculer l'aire comprise entre l'axe x, la courbe de f et les droites d'équations equation et equation. Nous supposons dans ce cas que la fonction est à valeurs positives:

equation   (57.233)

Ce problème, dans sa généralité, est difficile voire impossible à résoudre analytiquement. Voici donc quelques méthodes numériques permettant le calcul approché de cette aire (ces méthodes sont utilisées parfois dans les entreprises par les employés qui n'ont que des tableurs de type MS Excel ou OpenOffice Calc pour calculer des intégrales).

MÉTHODE DES RECTANGLES

Nous subdivisons l'intervalle equation en n sous-intervalles dont les bornes sont equation. Les longueurs de ces sous intervalles sont equation. Nous construisons les rectangles dont les côtés sont equation et equation.

equation
  (57.234)

L'aire de ces rectangles vaut:

equation   (57.235)

Si les equation sont suffisamment petits, equation est une bonne approximation de l'aire cherchée. Nous pouvons recommencer cet exercice en choisissant equation et equation comme côtés des rectangles. Nous obtenons alors:

equation   (57.236)

La figure correspondante est la suivante:

equation
  (57.237)

Encore une fois, l'aire de ces rectangles approche l'aire cherchée. Afin de simplifier la programmation, il est utile de choisir des intervalles de longueur identique:

equation   (57.238)

Si nous avons n rectangles, h vaut alors equation. Les aires equation et equation deviennent:

equation   (57.239)

MÉTHODE DES TRAPÈZES

Afin d'augmenter la précision des calculs, il est possible de calculer:

equation   (57.240)

Dans le cas où tous les intervalles sont de longueur égale, equation vaut:

equation   (57.241)

Il existe une foule d'autres méthodes permettant la résolution de ce problème (dont la méthode de Monte-Carlo que nous verrons plus loin).

Dans le cas où la fonction f n'est pas à valeurs positives, nous ne parlons plus d'aire mais de "somme de Riemann". Les sommes à calculer sont alors:

equation   (57.242)

et:

equation   (57.243)

Tous les calculs doivent êtres conduits de la même manière, mais les résultats peuvent être positifs, négatifs ou nuls.


page suivante : 11. Programmation linéaire