LES MÉTHODES (ANALYSES) NUMÉRIQUES



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

L'analyse numérique est une discipline des mathématiques. Elle s'intéresse tant aux fondements théoriques qu'à la mise en pratique des méthodes permettant de résoudre, par des calculs purement numériques, des problèmes d'analyse mathématique.

Définition: "L'analyse numérique" est l'étude des algorithmes permettant de résoudre les problèmes de mathématiques continues (distinguées des mathématiques discrètes).

Cela signifie qu'elle s'occupe principalement de répondre numériquement à des questions à variable réelle ou complexe comme l'algèbre linéaire numérique sur les champs réels ou complexes, la recherche de solutions numériques d'équations différentielles et d'autres problèmes liés survenant dans les sciences physiques et l'ingénierie.

Certains problèmes de mathématique continue peuvent être résolus de façon exacte par un algorithme. Ces algorithmes sont appelés alors "méthodes directes". Des exemples sont l'élimination de Gauss-Jordan pour la résolution d'un système d'équations linéaires et l'algorithme du simplexe en programmation linéaire (voir plus loin).

Cependant, aucune méthode directe n'est connue pour certains problèmes (et il est même démontré que pour une classe de problèmes dits "NP complets", il n'existe aucun algorithme fini de calcul direct en temps polynômial). Dans de tels cas, il est parfois possible d'utiliser une méthode itérative pour tenter de déterminer une approximation de la solution. Une telle méthode démarre depuis une valeur devinée ou estimée grossièrement et trouve des approximations successives qui devraient converger vers la solution sous certaines conditions. Même quand une méthode directe existe cependant, une méthode itérative peut être préférable car elle est souvent plus efficace et même souvent plus stable (notamment elle permet le plus souvent de corriger des erreurs mineures dans les calculs intermédiaires).

L'utilisation de l'analyse numérique est grandement facilitée par les ordinateurs. L'accroissement de la disponibilité et de la puissance des ordinateurs depuis la seconde moitié du 20ème siècle a permis l'application de l'analyse numérique dans de nombreux domaines scientifiques, techniques et économiques, avec souvent des effets révolutionnaires.

Lors de simulations numériques de systèmes physiques, les conditions initiales sont très importantes dans la résolution d'équations différentielles (voir les différents chapitres du site ou apparaissent des effets chaotiques). Le fait que nous ne puissions les connaître avec exactitude fait que les résultats des calculs ne peuvent jamais êtres parfaitement exactes (nous le savons très bien pour la météo qui en est l'exemple connu le plus flagrant). Cet effet, est une conséquence des résultats de la physique fondamentale (basée sur des mathématiques pures) qui démontre que l'on ne peut connaître parfaitement un système en y effectuant des mesures puisqu'elles perturbent directement ce dernier (principe d'incertitude de Heisenberg) et elles font l'objet de la théorie du Chaos (classique ou quantique).

Sens de la vie

Avec les nouveaux outils informatiques à disposition en ce début de 21ème siècle, il est devenu pratique et passionnant de connaître les méthodes numériques afin de s'amuser dans certains logiciels (OpenGL, 3D Studio Max, Maple, Matlab, Mathematica, Comsol, etc.) à simuler sous forme graphique 2D ou 3D des systèmes physiques.

Remarques:

R1. Beaucoup de méthodes numériques utilisées en informatique se basent sur des raisonnements qui ont déjà été étudiés dans d'autres sections de ce site et sur lesquelles nous ne reviendrons pas.

R2. Ce chapitre étant à la limite entre l'ingénierie et la mathématique appliquée, nous avons décidé de donner parfois des exemples d'applications des outils développés.

Définition: Un "algorithme" est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, en un nombre fini d'étapes (dont la quantité, ou réciproquement le temps d'exécution est définie par le terme "coût"), à un certain résultat, et cela indépendamment du type de données

Les algorithmes sont intégrés dans des calculateurs par l'intermédiaire de "programmes".

Définition: Un "programme" est la réalisation (l'implémentation) d'un algorithme au moyen d'un langage donné (sur une architecture donnée). Il s'agit de la mise en oeuvre du principe.

Axiomes de la programmation (anecdotique) :

A1. Plus nous écrivons de code, plus nous produirons d'erreurs

A2. Il n'existe pas de programmes sans de possibles erreurs (du au programme lui-même, à l'électronique sous-jacente ou le plus souvent à l'utilisateur même)

Basiquement voici la démarche minimale à suivre lors du développement d'un produit informatique (au niveau du code):

M1. Auditer les besoins présents et anticiper les besoins futurs

M2. Définir les objectifs

M3. Calculer la faisabilité, le risque d'erreur, la durée nécessaire au développement

M4. Créer les algorithmes en langage formel (cela comprend la gestion des erreurs!)

M5. Optimiser la complexité et contrôler les algorithmes

M6. Choix d'une stratégie de développement (modulable ou autre)

M7. Traduire les algorithmes dans la technologie choisie (ce choix est un sujet assez sensible...)

Remarque: Il faudrait dans l'étape (7) respecter les normes de nommage et de représentation du code ainsi que les conventions (traditions) de fréquence d'insertions des commentaires.

M8. Tests (maintenance préventive)

Remarque: Le débogage (la gestion des erreurs) d'un programme et les tests de fonctionnement doivent prendre autant, voir plus, de temps que le développement du programme lui-même.

Lors du développement d'un programme scientifique, il peut être intéressant, voire même rigoureux de s'attarder la notion de "complexité" de ce dernier. Sans aller trop loin, voyons un peu de quoi il s'agit :

COMPLEXITÉ

La complexité d'un algorithme est la mesure du nombre d'opérations fondamentales qu'il effectue sur un jeu de données. La complexité est donc exprimée comme une fonction de la taille du jeu de données.

Les hypothèses permettant un calcul de cette complexité sont :

H1. equation (les quatre opérations fondamentales ont le même coût)

H2. Un accès mémoire equation une opération arithmétique

H3. Un contrôle de comparaison equation une opération arithmétique

H4. Un seul processeur

Nous notons equation l'ensemble des données de taille n et T(n) le coût (en temps) de l'algorithme sur la donnée ou le jeu de données de taille n.

- La "complexité au meilleur" est donnée par la fonction:

equation   (57.1)

C'est le plus petit temps qu'aura exécuté l'algorithme sur un jeu de données (de lignes de code) de taille fixée, ici à n dont le coût (la durée) d'exécution est C(d). C'est une borne inférieure de la complexité de l'algorithme sur un jeu de données de taille n.

- La "complexité au pire":

equation   (57.2)

C'est le plus grand temps qu'aura à exécuté l'algorithme sur un jeu de données de taille fixée, ici à n. Il s'agit donc d'un maximum, et l'algorithme finira toujours avant d'avoir effectué equation opérations. Cependant, cette complexité peut ne pas refléter le comportement usuel de l'algorithme, le pire cas pouvant ne se produire que très rarement, mais il n'est pas rare que le cas moyen soit aussi mauvais que le pire cas.

- La "complexité moyenne":

equation   (57.3)

Il s'agit de la moyenne des complexités de l'algorithme sur des jeux de données de taille n (en toute rigueur, il faut bien évidemment tenir compte de la probabilité d'apparition de chacun des jeux de données). Cette moyenne reflète le comportement général de l'algorithme si les cas extrêmes sont rares ou si la complexité varie peu en fonction des données. Cependant, la complexité en pratique sur un jeu de données particulier peut être nettement plus important que la complexité moyenne, dans ce cas la complexité moyenne ne donnera pas une bonne indication du comportement de l'algorithme.

En pratique, nous ne nous intéressons qu'à la complexité au pire, et à la complexité moyenne

Définition: Un algorithme est dit "algorithme optimal" si sa complexité est la complexité minimale parmi les algorithmes de sa classe.

Comme nous l'avons fait sous-entendre précédemment, nous nous intéressons quasi-exclusivement à la complexité en temps des algorithmes. Il est parfois intéressant de s'intéresser à d'autres de leurs caractéristiques, comme la complexité en espace (taille de l'espace mémoire utilisé), la largeur de bande passante requise, etc.

Pour que le résultat de l'analyse d'un algorithme soit pertinent, il faut avoir un modèle de la machine sur laquelle l'algorithme sera implémenté (sous forme de programme). Nous prenons habituellement comme référence, la machine à accès aléatoire (RAM)" et à processeur unique, où les instructions sont exécutées l'une après l'autre, sans opérations simultanées et sans processus stochastiques (contrairement au possibles machines quantiques futures).

Les algorithmes usuels peuvent êtres classés en un certain nombre de grandes classes de complexité dont l'ordre O varie d'une certaine manière:

- Les algorithmes sub-linéaires dont la complexité est en général de l'ordre O(log(n))

- Les algorithmes linéaires en complexité O(n) et ceux en complexité en O(n log(n)) sont considérés comme rapides.

- Les algorithmes polynomiaux en O(nk) pour equation sont considérés comme lents, sans parler des algorithmes exponentiels (dont la complexité est supérieur à tout en n) que l'on s'accorde à dire impraticables dès que la taille des données est supérieur à quelques dizaines d'unités.

Remarque: Une bonne complexité est de type O(nk) pour equation. Une mauvaise complexité est de type equation ou equation.

exempleExemples:

E1. Evaluation d'un polynôme :

equation   (57.4)

L'évaluation directe de la valeur de P(x) conduit à une complexité

equation   (57.5)

Nous devons à Horner un algorithme plus performant qui utilise une factorisation du polynôme sous la forme :

equation   (57.6)

Nous pouvons facilement montrer que cette factorisation maintient le même nombre d'additions equation mais réduit le nombre de multiplication à (n). La complexité qui en découle est donc O(n). Le gain est incontestablement important. De plus, cette factorisation évite tout calcul de puissance.

E2. Un autre exemple connu de complexité algorithmique est la recherche d'une information dans une colonne triée. Un algorithme simple appelé "recherche dichotomique" consiste à prendre la cellule au milieu de la colonne et de voir si nous y trouvons la valeur recherchée. Sinon, la recherche doit continuer dans la partie supérieure ou inférieure du tableau (cela dépend de l'ordre lexicographique).

L'algorithme est récursif et permet de diminuer par deux, à chaque étape, la taille de l'espace de recherche. Si cette taille, initialement, est de n cellules dans la colonne, elle est de n/2 à l'étape 1, equation à l'étape 2, et plus générale à equation à l'étape k.

Au pire, la recherche se termine quand il n'y a plus qu'une seule cellule de la colonne à explorer, autrement dit quand k est tel que equation. Nous en déduisons le nombre maximal d'étapes: c'est le plus petit k tel que equation, soit equation, soit:

equation   (57.7)

à comparer avec une recherche séquentielle dans une colonne de 25'000 données dont la complexité linéaire est O(n) soit 25'000 alors qu'avec la méthode dichotomique nous avons une complexité sub-linéaire equation. Le gain est donc considérable!

E3. Soit A et B deux matrices carrées de dimension n. Les principales opérations sur ces matrices ont les complexités suivantes (nous laisserons le soin au lecteur de vérifier car c'est vraiment trivial) :

- Lecture (itérations) : O(n2)

- Calcul de la trace : equation

- Addition :equation tel que equation

- Multiplication : equation tel que equation

- Déterminant (par la méthode directe de Cramer). Nous renvoyons le lecteur au chapitre d'Algèbre Linéaire pour le détail des méthodes de calcul du déterminant d'une matrice. Nous pouvons alors montrer que la complexité d'un déterminant d'ordre n est n multiplications, n-1 additions plus n fois la complexité d'un déterminant d'ordre n-1. Par cumul, nous arrivons à :

equation   (57.8)

En faisant l'hypothèse que l'ordinateur utilisé effectue une opération élémentaire en equation secondes (ce qui est déjà une bonne machine). Nous obtenons alors les temps de calculs suivants pour plusieurs valeurs de n :

n

5

10

15

20

50

t

equation

equation

equation

equation

equation

     Tableau: 55.1  - Temps de calcul d'un déterminant

d'où la nécessité de faire un calcul de complexité avant de mettre l'algorithme en route (à moins que vous ne travailliez exclusivement pour les générations futures, à condition qu'il y en ait encore...).

Finalement, pour résumer un peu, nous distinguons quelques types de complexités classiques : O(1) indépendant de la taille de la donnée, O(log(n)), complexité logarithmique, O(n) complexité linéaire, O(n log(n)), complexité quasi-linéaire, O(n2), complexité quadratique, O(n3), complexité cubique, O(kn) complexité exponentielle, O(n!), complexité factorielle.

NP-COMPLÉTUDE

Nous allons introduire pour la culture générale le concept de NP-complétude, c'est-à-dire que nous allons tenter de définir sans trop de formalisme (comme à l'habitude) la classe des problèmes dit "NP-complets". Ces problèmes sont ceux pour lesquels personne à l'heure actuelle ne connaît d'algorithme efficace (i.e. seulement des algorithmes exponentiels). Ce sont des problèmes vraiment difficiles par opposition à ceux pour lesquels nous connaissons des algorithmes de complexité polynomiale.

Définitions:

D1. Les problèmes de "classe P" sont des bons problèmes dans le sens où le calcul de leur solution est faisable dans un temps raisonnable avec un algorithme à complexité polynomiale. Plus formellement, ce sont les problèmes pour lesquels nous pouvons construire une machine déterministes (voir la remarque après les définitions) dont le temps d'exécution est de complexité polynomiale (le sigle "P" signifiant "Polynomial Time").

D2. Les problèmes de "classe E" sont des problèmes dans le sens où le calcul de leur solution est faisable dans un temps exponentiel par nature de type equation. Plus formellement, ce sont les problèmes pour lesquels nous pouvons construire une machine déterministes dont le temps d'exécution est de complexité exponentielle (le sigle "E" signifiant "Exponential Time").

D3. Les problèmes de la "classe NP" sont ceux pour lesquels nous pouvons construire une machine de Turing non déterministe (voir la remarque après les définitions) dont le temps d'exécution est de complexité polynomiale (le sigle "NP" provient de "Nondeterministic Polynomial time" et non de "Non Polynomial").

Remarque: Contrairement aux machines déterministes qui exécutent une séquence d'instructions bien déterminée, les machines non déterministes ont la remarquable capacité de toujours choisir la meilleure séquence d'instructions qui mène à la bonne réponse lorsque celle-ci existe. Il va sans dire qu'une telle machine ne peut pas exister autrement que dans l'esprit d'un théoricien (à moins qu'avec les ordinateurs quantiques...)! Néanmoins, comme nous le verrons par la suite, ce concept abstrait n'est pas sans intérêt et constitue en fait la base de toute la théorie de la NP-complétude.

Il importe de remarquer à ce stade de la discussion que la classe P est incluse dans la classe NP, nous écrivons equation, car si nous pouvons construire une machine déterministe pour résoudre efficacement (en un temps au pire polynomial) un problème, nous pouvons certainement (du moins dans notre esprit) en construire une non déterministe qui résout aussi efficacement le même problème. Par ailleurs, il ne faut pas croire que ce concept de divination optimale qu'est la machine déterministe permet de tout résoudre puisqu'il existe en informatique théorique d'autres types de problèmes n'appartenant pas à la classe NP qui sont les problèmes indécidables.

Pour savoir si un problème donné appartient ou non à la classe NP, il s'agit simplement de l'exprimer sous la forme dont la réponse est soit OUI, soit NON. Le problème appartient alors à la classe NP si par définition, nous arrivons à démontrer à l'aide d'un algorithme de complexité polynomiale que n'importe quelle instance OUI du problème est bel et bien correcte. Nous n'avons pas à nous préoccuper des instances NON du problème puisque la machine non déterministe, par définition, prend toujours la bonne décision (lorsque celle-ci existe).

Par exemple, le problème consistant à trouver un cycle hamiltonien (cycle qui passe une et une seule fois par tous les sommets du graphe - voir chapitre de Théorie des graphes) dans un graphe appartient à NP puisque, étant donné un cycle, il est trivial de vérifier en temps linéaire qu'il contient bien une et une seule fois chaque sommet.

Un autre exemple de problème difficile des mathématiques est la factorisation d'un entier en produit de facteurs premiers. Nous ne savons pas à ce jour s'il existe un algorithme polynomial qui réussisse cette opération. Autrement dit, nous ne savons pas si ce problème est dans P. En revanche, étant donné des nombres premiers equation il est trivial de vérifier que equation : ce problème est donc dans NP. Il semblerait (nous n'avons pas vérifié ce résultat et ni la possibilité de le faire) que la complexité du meilleur algorithme de factorisation en nombre premier soit du type :

equation   (57.9)

il resterait donc du travail à faire (si un internaute peut nous fournir les détails qui ont amené à ce résultat, nous sommes preneurs).

Remarque: Si un problème est dans NP, alors il existera un algorithme en temps exponentiel pour le résoudre mais le contraire n'est pas toujours vrai (il faut donc être prudent).

Parmi l'ensemble des problèmes NP, il en existe un sous-ensemble qui contient les problèmes les plus difficiles : nous les appelons les problèmes "NP-complet" N.P.C. Ainsi, un problème NP-complet possède la propriété que tout problème dans NP peut être transformé en celui-ci en temps polynomial.

La raison essentielle pour laquelle les problèmes NPC sont les plus difficiles parmi les problèmes de NP est que ces premiers peuvent toujours servir comme des sous-routines pour solutionner ces derniers. Cette réduction à un ou des sous-routines assez facilement faisable puisque réalisable, si elle existe, en temps polynomial. Un problème NPC est donc complet en ce sens qu'il contient l'essentiel de la complexité des problèmes appartenant à NP, et qu'une solution polynomiale à ce problème implique une solution polynomiale à tous les problèmes NP.

Autrement formulé, les problèmes NPC ont une complexité exponentielle et ils ont tous la même classe de complexité (modulo les polynômes).

Finalement, ce qu'il importe de bien comprendre et de retenir de tout cette théorie, son idée maîtresse, est que si nous trouvons un jour un algorithme de complexité polynomiale pour un seul de ces problèmes vraiment difficiles que sont les problèmes NPC, alors d'un seul coup NP devient égal à P et tous les problèmes difficiles deviennent faciles !

Pour résumer, être dans P, c'est trouver une solution en un temps polynomial, tandis qu'être dans NP, c'est prouver en un temps polynomial qu'une proposition de réponse est une solution du problème. Ainsi, tout problème qui est dans P se trouve dans NP. Un champ de recherche majeur des mathématiques actuelles est l'investigation de la réciproque : a-t-on P=NP? Autrement dit, peut-on trouver en un temps polynomial ce que l'on peut prouver en temps polynomial?

Remarque: Ce problème est si important en informatique qu'il fait partie (arbitrairement) des 7 problèmes du millénaire, dont la résolution est primée 1 million de dollars par le Clay Mathematic Institute.

Passons maintenant à l'étude de quelques applications types des méthodes numériques dont il est très souvent fait usage dans l'industrie. Nous irons du plus simple au plus compliqué et sans oublier que beaucoup de méthodes ne se trouvant pas dans ce chapitre peuvent parfois être trouvées dans d'autres sections du site!

PARTIE ENTIÈRE

Le plus grand entier inférieur ou égal à un nombre réel x est par [x], qui se lit "partie entière de x".

Ainsi, le nombre M est entier si et seulement si [M]=M. De même, le naturel A est divisible dans l'ensemble des naturels par le naturel B si et seulement si:

equation   (57.10)

Nous notons aussi {x} pour désigner la partie fraction de x; on a ainsi:

equation   (57.11)

Soit equation. Alors nous avons les propriétés suivantes :

P1. equation, equation, equation où equation

P2. equation, lorsque equation

P3. equation, si equation

P4. equation

P5. equation si equation, equation si equation

P6.equation si equation

P7. Si equation, alors [x / a] représente le nombre d'entiers positifs inférieurs ou égaux à x qui sont divisibles par a.

Démonstrations:

La première partie de P1 est simplement la définition de [x] sous forme algébrique. Les deux autres parties sont des réarrangements de la première partie. Dans ce cas, nous pouvons écrire

equation  (57.12)

equation.

Pour P2, la somme est vide pour equation et, dans ce cas, on adopte la convention selon laquelle la somme vaut 0. Alors, pour equation, la somme compte le nombre d'entiers positifs n qui sont plus petits ou égaux à x. Ce nombre est évidemment [x].

La démonstration de P3 sera supposée évidente.

Pour prouver P4, nous écrivons :

equation, equation   (57.13)

n et m sont des entiers et où equation et equation. Alors:

equation   (57.14)

En écrivant equation, où equation, nous avons

equation   (57.15)

equation.

Il s'ensuit que:

equation0 si equation-1 si equation   (57.16)

et on obtient la démonstration P5.

Pour démontrer P6, nous écrivons :

equation   (57.17)

equation, et :

equation   (57.18)

equation. Nous obtenons ainsi:

equation   (57.19)

puisque equation. Par ailleurs:

equation   (57.20)

et nous avons ainsi le résultat.

Pour la dernière partie, nous observons que, si equation sont tous les entiers positifs equation qui sont divisibles par a, il suffit de prouver que equation. Puisque  equation, alors:

equation   (57.21)

c'est-à-dire :

equation   (57.22)

soit le résultat attendu.

equationC.Q.F.D.

Remarque: La méthode d'arrondi de valeurs réelles est donnée dans le chapitre d'Économétrie.

ALGORITHME D'HÉRON

Soit à calculer la racine carrée:

equation   (57.23)

Il existe un algorithme dit "algorithme d'Héron" qui permet de calculer la valeur de cette racine carrée.

Démonstration:

equation   (57.24)

Nous obtenons alors la relation:

equation   (57.25)

equationC.Q.F.D.

exempleExemple:

Soit à calculer :

equation   (57.26)

Nous prenons equation :

Itération
xi /2
A/2xi
xi+1
Ecart
1
5
0.5
5.50
~2.3
2
2.750
0.90
3.659 090 909
~0.49
3
1.82954
1.3664
3.196 005 083
~0.033
4
1.59800
1.5644
3.162 455 624
~0.0002
5
1.58122
1.5810
3.162 277 665
~0.5 10-8 
Tableau: 57.2  - Itérations pour l'algorithme d'Héron

Dans le cas de la racine cubique, la démonstration est semblable et nous obtenons:

equation   (57.27)

Signalons encore que le lecteur pourra trouver dans le chapitre de Théorie des Nombres la méthode utilisée pendant l'antiquité (du moins une analogie) et utilisant les fractions continues.

ALGORITHME D'ARCHIMÈDE

Le calcul de la constante universelle "pi" notée equation est très certainement le plus grand intérêt de l'algorithmique puisque l'on retrouve cette constante un peu partout en physique et mathématique (nous pouvons vous conseiller un très bon ouvrage sur le sujet).

Nous rappelons que nous n'en avons pas donné la valeur ni en géométrie, ni dans les autres sections de ce site jusqu'à maintenant. Nous allons donc nous attacher à cette tâche.

Nous définissons définit en géométrie le nombre equation  dit "pi", quelque soit le système métrique utilisé (ce qui fait son universalité), comme le rapport de la moitié du périmètre d'un cercle par son rayon tel que:

equation   (57.28)

Nous devons le premier algorithme du calcul de cette constante à Archimède (287-212 av. J.-C.) dont voici la démonstration.

Démonstration:

Soit un n-polygone inscrit dans un cercle:

equation
  (57.29)

Le principe de l'algorithme d'Archimède est le suivant: Soit equation le périmètre d'un polygone régulier de n côtés inscrit dans un cercle de rayon 1/2. Archimède arrive par induction que:

equation   (57.30)

Nous avons pour périmètre d'un n-polygone:

equation et equation   (57.31)

Avec :

equation   (57.32)

Donc:

equation   (57.33)

Il suffit d'un ordinateur ensuite et de plusieurs itérations pour évaluer avec une bonne précision la valeur de equation.  Evidemment, on utilise l'algorithme d'Héron pour calculer la racine...

equationC.Q.F.D.

Remarque: Il existe un très grand nombre d'algorithmes pour calculer equation. Celle présentée ci-dessus, sans être la plus esthétique, est historiquement la première.

CALCUL DU NOMBRE D'EULER

Parmi la constante equation, il existe d'autres constantes mathématiques importantes qu'il faut pouvoir générer à l'ordinateur (de nos jours les valeurs constantes sont stockées telles quelles et ne sont plus recalculées systématiquement). Parmi celles-ci, se trouve le "nombre d'Euler" noté e (cf. chapitre d'Analyse Fonctionnelle). Voyons comment calculer ce nombre:

Soit la série de Taylor, pour une fonction indéfiniment dérivable f donnée par (cf chapitre sur les Suites Et Séries):

equation   (57.34)

Comme (cf. chapitre de Calcul Différentiel Et Intégral):

equation   (57.35)

nous avons:

equation   (57.36)

Donc en résumé:

equation   (57.37)

Cette relation donne un algorithme pour calculer l'exponentielle equation à un ordre n donnée de précision.

Remarque: Pour diminuer la complexité de cet algorithme, la factorielle peut être calculée avec la formule exposée ci-après.

CALCUL DE LA FACTORIELLE (FORMULE DE STIRLING)

Evidemment, la factorielle pourrait être calculée avec une simple itération. Cependant, ce genre de méthode génère un algorithme à complexité exponentielle ce qui n'est pas le mieux. Il existe alors une autre méthode :

Soit, la définition de la factorielle :

equation   (57.38)

Et d'après les propriétés des logarithmes :

equation   (57.39)

Si n est très grand (mais alors très...) alors:

equation   (57.40)

Lorsque equation, la limite inférieure est négligeable et alors:

equation   (57.41)

Après une petite simplification élémentaire, nous obtenons:

equation   (57.42)

Cette dernière relation est utile si l'on suppose bien évidemment que la constante d'Euler est une valeur stockée dans la machine...

SYSTEMES D'ÉQUATIONS LINÉAIRES

Il existe de nombreuses méthodes de résolution de systèmes d'équations linéaires. La plupart d'entre elles ont été mises au point pour traiter des systèmes particuliers. Nous en étudierons une, appelée la "méthode de réduction de Gauss", qui est bien adaptée à la résolution des petits systèmes d'équations (jusqu'à 50 inconnues).

Remarques:

R1. La validité de certaines des opérations que nous allons effectuer ici pour résoudre les systèmes linéaires se démontrent dans le chapitre traitant de l'Algèbre Linéaire. Au fait, pour être bref, le tout fait appel à des espaces vectoriels dont les vecteurs-colonnes sont linéairement indépendants.

R2. Les systèmes admettent une solution si et seulement si (rappel) le rang de la matrice augmentée est inférieur ou égal au nombre d'équations (cf. chapitre d'Algèbre Linéaire).

UNE ÉQUATION À UNE INCONNUE

Considérons le cas le plus simple: celui d'une équation à une inconnue:

equation   (57.43)

a et b sont les coefficients de l'équation et x en est l'inconnue. Résoudre cette équation, c'est déterminer x en fonction de a et b. Si a est différent de 0 alors:

equation   (57.44)

est la solution de l'équation. Si a est nul et si b est différent de 0 alors l'équation n'admet pas de solutions. Si a et b sont nuls, alors l'équation possède une infinité de solutions.

DEUX ÉQUATIONS À DEUX INCONNUES

Un système (linéaire) de deux équations à deux inconnues s'écrit:

equation   (57.45)

equation sont les coefficients du système d'équations, equation et equation en sont les inconnues.

Remarque: Les notations usitées ci-dessus n'ont rien à voir avec le calcul tensoriel.

Pour résoudre le système, nous procédons comme suit:

A l'aide de manipulations algébriques (addition ou soustraction des différentes égalités entre elles - manipulations autorisées par l'indépendance linéaire des vecteurs-lignes) nous transformons le système en un autre donné par :

equation   (57.46)

Ensuite, nous résolvons l'équation equation, ce qui donne :

equation   (57.47)

Nous en déduisons:

equation   (57.48)

La transformation entre les deux systèmes:

equation   (57.49)

s'effectue simplement en multipliant chaque coefficient de la première égalité par equation et en soustrayant les résultats obtenus des coefficients correspondants de la seconde égalité. Dans ce cas, l'élément equation est appelé "pivot".

TROIS ÉQUATIONS À TROIS INCONNUES

Examinons encore le cas des systèmes de trois équations à trois inconnues:

equation   (57.50)

Nous pouvons par la suite des opérations élémentaires (cf. chapitre d'Algèbre Linéaire) réduire le système linéaire précédent en le système suivant:

equation   (57.51)

et ensuite résoudre l'équation:

equation   (57.52)

puis la deuxième:

equation   (57.53)

et enfin:

equation   (57.54)

Revenons à la transformation des systèmes. Elle s'effectue en deux étapes :

1. Dans la première, nous choisissons equation comme pivot et nous éliminons les coefficients equation et equation de la manière suivante: il faut multiplier chaque coefficient de la première égalité par equation et soustraire les résultats obtenus de la deuxième égalité, ainsi equation devient nul. De même, en multipliant les coefficients de la première équation par equation et en soustrayant les résultats obtenus de la troisième égalité, equation disparaît. Le système d'équation s'écrivant alors:

equation   (57.55)

2. La deuxième étape consiste à traiter le système de deux équations à deux inconnues formé des deuxième et troisième égalités du système précédent, et ce, en choisissant equationcomme pivot. Cette méthode de résolution peut paraître compliquée, mais elle a l'avantage de pouvoir être généralisée et être appliquée à la résolution de systèmes de n équations n inconnues.

N ÉQUATIONS À N INCONNUES

Pour simplifier l'écriture, les coefficients seront toujours notés equation et non pas equation, etc. lors de chaque étape du calcul.

Soit le système linéaire (nous pourrions très bien le représenter sous la forme d'une matrice augmentée afin d'alléger les écritures) :

equation   (57.56)

Il faut choisir equation comme pivot pour éliminer equation. Ensuite, l'élimination de equation s'effectue en prenant equation comme pivot. Le dernier pivot à considérer est bien évidemment equation, il permet d'éliminer equation. Le système prend alors la forme:

equation   (57.57)

En résolvant d'abord la dernière équation, puis l'avant dernière et ainsi de suite jusqu'à la première.

Cette méthode, appelée "méthode de résolution de Gauss" ou encore "méthode du pivot" doit cependant être affinée pour éviter les pivots de valeur 0. L'astuce consiste à permuter l'ordre dans lequel sont écrites les équations pour choisir comme pivot le coefficient dont la valeur absolue est la plus grande. Ainsi, dans la première colonne, le meilleur pivot est l'élément equation tel que:

equation   (57.58)

Il est amené à equation par échange des première et j-ème lignes. L'élimination du reste de la première colonne peut alors être effectuée. Ensuite, on recommence avec les n-1 équations qui restent.

POLYNÔMES

L'ensemble des polynômes et à coefficients réels a été étudié dans le chapitre d'Analyse Fonctionnelle en détails. Nous allons ici traiter de l'aspect numérique de quelques problèmes liés aux polynômes.

Mis à part l'addition et la soustraction de polynômes que nous supposerons comme triviaux (optimisation de la complexité mis à part comme le schéma de Horner), nous allons voir comment multiplier et diviser deux polynômes.

Voyons d'abord comment multiplier deux polynômes :

Soit :

equation   (57.59)

alors :

equation   (57.60)

avec :

equation   (57.61)

C'était simple....

Un tout petit peu plus difficile maintenant : la division euclidienne des polynômes (cf. chapitre de Calcul Algébrique).

Reprenons :

equation   (57.62)

mais en imposant cette fois-ci equation.

La division s'écrira donc nous le savons :

equation   (57.63)

avec equation ou sinon equation.

Il est connu d'avance que nous avons bien évidemment :

equation et deg(r(x))<m.

Nous avons donc par définition q(x) qui est le quotient de la division et r(x) le reste de la division euclidienne de f(x) par g(x).

Rien ne nous interdit donc de poser de la manière la plus générale qui soit :

equation   (57.64)

exempleExemple:

Soit :

equation   (57.65)

donc :

equation   (57.66)

Nous avons donc :

equation   (57.67)

Ensuite :

equation   (57.68)

et enfin :

equation   (57.69)

 

Donc de manière générale :

equation   (57.70)

comme :

equation   (57.71)

le premier reste est donc :

equation   (57.72)

Ensuite :

equation   (57.73)

Le deuxième reste est alors :

equation   (57.74)

etc.

Nous continuons jusqu'à ce que equation.


page suivante : 8. Régressions et interpolations