recevoir les news :: signaler une erreur :: statistiques visiteurs :: imprimer

ALGORITHMES | FRACTALS | ALGEBRE DE BOOLE | CRYPTOGRAPHIE |

L'analyse numériques est la branche des sciences qui s'occupe du développement d'algorithmes mathématiques applicables à l'informatique pour la résolution de problèmes formels lié à la simulation de phénomènes physiques. (Larousse)

Lors de ma scolarité, j'ai été frustré de la façon avec laquelle mes professeurs nous avaient introduit à l'analyse numérique. J'étais attristé de les entendre dire que la physique ne pouvait formellement (dans le sens du calcul symbolique) résoudre certains problèmes à corps.

Or, cela n'est pas tout à fait vrai (ni tout à fait faux..)! Certes, on ne peut directement résoudre certains problèmes de façon symbolique (formelle) et directe, mais les méthodes numériques sont des procédures de calcul (algorithmes) intégrées dans des machines de calculs (les ordinateurs) qui ont toutes été à la base, élaborées sur des méthodes symboliques (théorie des structures, algèbre de boole). Le cercle est ainsi fermé ! Voyons cela un peu plus dans les détails:

Si nous prenons ce cercle et que nous le déplions (expérience imaginaire), nous nous retrouvons avec un trait de longueur finie. Si nous choisissons arbitrairement le début de l'anlyse numérique comme l'extrémité gauche de ce trait, nous nous trouvons avec la mécanique quantique (physique-mathématique) qui permet de décrire la physique des semi-conducteurs. Ensuite, un peu plus loin, nous nous retrouvons avec la physique mécoscopique (physique-mathématique), qui permettra d'élaborer des transistors. Ces derniers, sont des composants électroniques ayant à effectuer des calculs à partir de valeurs binaires et selon les régles de l'algèbre de Boole (mathématique). Enfin, on utilisera la théorie des circuits (physique-mathématique) pour construire des machines capables d'effectuer de grandes quantitués itératives de calculs.

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 qu'on ne puisse les connaîtres avec exactitude fait que les résultats des calculs ne peuvent jamais êtres parfaitement exactes (on le sait très bien pour la météo qui en est l'exemple connu le plus flagrant). Cette 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).

Définition: On définit la notion d’algorithme par 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édaire 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.

Axiome de la programmation:

- 1er Axiome: plus nous écrivons de code, plus nous produirons d'erreurs

- 2ème Axiome: la programmation sans erreur est un mythe

Principe de base de la programmation:

Le déboguage (la gestion des erreurs) d'un programme doit prendre autant, voir plus, de temps que le développement du programme lui-même (rappellons que cette partie du site n'a pas pour but de vous donner les algorithmes dans un language de programmation donné mais de vous fournier les méthodes numérique de calcul).

Lors du développement d'un programme scientifique, il peut 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 'sagit:

COMPLEXITE

La complexité d'un algorithme est la mesure du nombre d'opération fondamentales qu'il effectue sur une jeu de données (le nombre de fois qu'est exécuté une ligne de code). La complexité est donc exprimée comme une fonction de la taille du jeu de données (du nombre de lignes de code).

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

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

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

- La "complexité au pire":

C'est le plus grand nombre d'opération qu'aura à exécuter l'algorithme sur un jeu de données de taille fixée, ici à . Il s'agit donc d'un maximum, et l'algorithme finira toujours avant d'avoir effectué  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":

Il s'agit de la moyenne des complexités de l'algorithme sur des jeux de données de taille  (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 "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  varie d'une certain manière.

- les algorithmes sub-linéaires dont la complexité est en général de l'ordre

- les algorithmes linéaires en complexité  et ceux en complexité en  sont considérés comme rapides.

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

PARTIE ENTIERE

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

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

On écrit aussi  pour désigner la partie fraction de ; on a ainsi:

Soit . Alors:

1) , ,  où

2) , lorsque

3) , si

4)

5)  si ,  si

6)  si

7) Si , alors  représente le nombre d'entiers positifs inférieurs ou égaux à  qui sont divisibles par .

Démonstrations:

La première partie de (1) est simplement la définition de  sous forme algébrique. Les deux autres parties sont des réarrangements de la première partie. Dans ce cas, on peut écrire  où .

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

La démonstration de (3) est évidente.

Pour prouver (4), on écrit , , où et sont des entiers et où  et . Alors:

En écrivant , où , on a , où .

Il s'ensuit que:

0 si -1 si

et on obtient la démonstration (5).

Pour démontrer (6), on écrit , où , et , où . On obtient ainsi:

puisque . Par ailleurs:

et on a ainsi le résultat.

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

, c'est-à-dire

soit le résultat attendu.

ALGORITHME D'HERON

Soit à calculer la racine carrée:

Il existe un algorithme dit "algorithme d'Héron" qui permet de calculer la valeur de cette racine carrée. Démonstration et méthode:

On obtient la formule:

Exemple avec :

On prend

Dans le cas de la racine cubique, la démonstration est semblable et l'on obtient:

ALGORITHME D'ARCHIMEDE

Le calcul de la constante universelle "pi" notée  est très certainement le plus grand intérêt de l'algorithmique puisque l'on retrouve cette constante partout en physique et mathématiques (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.

On définit en géométrie le nombre  , 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:

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

Soit un -polygone inscrit dans un cercle:

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

On a pour périmètre d'un -polygone:

 et

Avec

Donc:

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

CALCUL DU NOMBRE D'EULER

Parmi la constante , 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. Voyons commentcalculer cette dernière :

Soit la série de Taylor, pour une fonction indéfiniment dérivable  donnée par (voir le chapitre traitant des suites et séreis dans la section d'algèbre) :

Comme (voir le chapitre de calcul intégral et différentiel dans la section d'algèbre):

nous avons:

Donc en résumé:

Cette relation donne un algorithme pour calculer l'exponentielle  à un ordre  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

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 :

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

Si  est très grand (mais alors très…) alors:

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

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

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'EQUATIONS LINEAIRES

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, qui est bien adaptée à la résolution des petits systèmes d'équations (jusqu'à 50 inconnues).

UNE EQUATION A UNE INCONNUE

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

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

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

DEUX EQUATIONS A DEUX INCONNUES

Un système de deux équations à deux inconnues s'écrit:

 sont les coefficients du système d'équations,  et  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: à l'aide de manipulations algébriques (addition ou soustraction des différentes égalités entre elles) nous transformons le système en un autre donné par:

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

Nous en déduisons:

La transformation entre les deux systèmes:

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

TROIS EQUATIONS A TROIS INCONNUES

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

Nous pouvons par un suite d'opérations élémentaire transformer le système précédente en le système suivant:

en ensuite résoudre l'équation:

puis la deuxième:

et enfin:

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

La deuxième étape consiste à traiter le système de deux équations à deux inconnues formé des deuxième et troisième égalités, et ce, en choisissant  comme 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  équations  inconnues.

N EQUATIONS A N INCONNUES

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

Soit le système:

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

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 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  tel que:

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

REGRESSION ET INTERPOLATIONS

Les régressions (ou "interpolations") sont des outils très utiles aux statisticiens, ingénieurs, informaticiens souhaitant établir un loi de corrélation entre deux (ou plus) variables dans un contexte d'études et d'analyse ou d'extrapolation.

Il existe un grand nombre de méthodes d'interpolation : de la simple résolution d'équations du premier degré (lorsque uniquement deux points d'un mesure sont connus) aux équations permettant d'obtenir à partir d'un grand nombre de points des informations essentielles à l'établissement d'une loi (ou fonction) de régression linéaire ou polynomiale.

REGRESSION LINEAIRE

Voici donc un d'algorithme très utile dans les sciences expérimentales (nous en avons déjà parlé lors de notre étude des statistiques). L'objectif ici est de chercher à exprimer la relation linéaire entre deux variables et indépendantes :

- est la variable indépendante ou "explicative". Les valeurs de sont fixées par l'expérimentateur et sont supposées connues sans erreur

- est la variable dépendante ou "expliquée" (exemple : réponse de l'analyseur). Les valeurs de sont entachées d'une erreur de mesure. L'un des buts de la régression sera précisément d'estimer cette erreur.

Nous cherchons une relation de la forme:

C'est l'équation d'une droite, d'où le terme de "régression linéaire".

Du fait de l'erreur sur , les points expérimentaux, de coordonnées , ne se situent pas exactement sur la droite théorique. Il faut donc trouver l'équation de la droite expirementale qui passe le plus près possible de ces points.

La "méthode des moindres carrés" consiste à chercher les valeurs des paramètres  qui rendent minimale la somme des carrés des écarts résiduelle (: Sum of Squared Residuals ) entre les valeurs observées  et les valeurs calculées théoriques de :

où est le nombre de points et:

d'où:

Cette relation fait apparaître la somme des carrés des écarts comme une fonction des paramètres . Lorsque cette fonction est minimale, les dérivées par rapport à ces paramètres s'annulent:

soit :

Le système ci-dessus est dit appelé "système des équations normales". Il admet pour solutions (après quelques substitutions et simplifications triviales) l'expression de la pente et de l'ordonnée à l'origine de l'équation recherchée :

INTERPOLATION POLYNOMIALE

Quand nous connaissons un polynôme de degré  en  points, nous pouvons connaître par une méthode simple (mais pas très rapide – mais il existe plusieurs méthodes) complètement ce polynôme.

Pour déterminer le polynôme, nous allons utiliser les résultats exposés précédemment lors de notre étude des système d'équations linéaires. Le désavantage de la méthode présentée ici est qu'il faut deviner à quel type de polynôme nous avons affaire et savoir quels sont les bons points qu'il faut choisir…

Un simple exemple particulier devrait suffire à la compréhension de cette méthode la généralisation en étant assez simple.

Soit un polynôme du second degré :

et nous avons connaissances des points suivants (dont vous remarquerez l'ingéniosité des points choisis par les auteurs de ces lignes…) :

Nous en déduisons donc le système d'équations :

Système qui une fois résolu dans les règles de l'art nous donne :

RECHERCHE DES RACINES

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.

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

Il existe un grand nombre d'algorithmes permettant de calculer les racines de l'équation  avec une précision théorique arbitraire. Nous n'en verrons que les principaux. Attention, la mise en œuvre 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 , nous traçons les courbes représentant  et . Les racines de l'équation  étant données par les abscisses des points d'intersection des deux courbes.

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

-  est continue sur  ou

-

-  unique,

METHODE DES PARTIES PROPORTIONNELLES

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

-  est continue

-  est monotones dans un voisinage de la racine

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:

Sur cette figure nous tirons à l'aide des théorème de Thalès:

d'où:

Si , nous pouvons négliger  au dénominateur et il vient:

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

1. choisir  et , calculer  et

2. Déterminer . Si  est assez petit, nous arrêtons le calcul et affichons  et

3. Sinon nous procédons comme suit:

- nous remplaçons  par  et  par

- nous remplaçons  par  et  par

- nous retournons au point (2)

METHODE DE LA BISSECTION

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

  est continue sur

2.

Il faut encore fixer  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

2. Evaluation de

3. Si  alors le travail est terminé, il faut afficher  et

4. Sinon on procède comme suit:

- on remplace  par  si

- on remplace  par  si  ou

- on retourne en (1)

L'étape (3) impose la condition  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  contenant . Ce test s'énonce comme suit:

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

METHODE DE LA SECANTE (REGULA FALSI)

Les conditions préalables sont les suivantes:

Il faut déterminer un intervalle  tel que:

1.  est continue sur

2.

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

nous en déduisons:

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

1. Calcul de

2. Evaluation de

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

4. Sinon on procède comme suit:

- on remplace  par  si

- on remplace  par  si  ou

- on retourne en (1)

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

3'. Si , alors le travail est terminé et on affiche

Remarque: si l'intervalle  contient plusieurs racines, cette méthode converge vers l'une d'entre elles; toutes les autres sont perdues.

METHODE DE NEWTON

Considérons la figure suivante:

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

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  qui est dérivable en , alors nous pouvons la réécrire sous la forme:

où  est la dérivée de  en  et  est une fonction qui tend vers 0 comme  pour  lorsque  tend vers  (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 , nous obtenons:

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

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

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

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

par:

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

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

Dans un intervalle  comprenant  et  il faut que:

1. la fonction soit deux fois dérivable

2. la dérivée  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 évident, en effet si  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  et .

Si la fonction  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  par le quotient différentiel:

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

soit elle aussi suffisamment petite.

L'itération s'écrit alors:

Convergence de la méthode:

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

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

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

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 :

Mais:

donc:

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

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

ce qui montre bien que la convergence est quadratique.

AIRES ET SOMMES DE RIEMANN

Considérons la figure suivante:

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

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.

METHODE DES RECTANGLES

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

L'aire de ces rectangles vaut:

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

La figure correspondante est la suivante:

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:

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

METHODE DES TRAPEZES

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

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

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  n'est pas à valeurs positives, nous ne parlons plus d'aire mais de "somme de Riemann". Les sommes à calculer sont alors:

et:

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

PROGRAMMATION LINEAIRE

L'objectif de la programmation linéaire est de trouver la valeur optimale d'une fonction linéaire sous un système d'équations d'inégalités de contraintes linéaires. La fonction à optimiser est baptisée "fonction économique" (utilisée en économie dans le cadre d'optimisations) et on la résout en utilisant une méthode dite "méthode simplexe" (voir plus loin) dont la représentation graphique consisten en un "polygone des contraintes". 

Remarque: la programmation linéaire est aussi connue sous le nom de "recherche opérationnelle"

La recherche opérationnelle à pour domaine l'étude de l'optimisation de processus quels qu'ils soient. Il existe de nombreux algorithmes s'inspirant des problèmes du type exposés lors de notre étude de la programmation linéaire. Nous nous attarderons en particulier sur l'algorithme plus utilisé qui est "l'algorithme du simplexe" (d'après ce que j'ai cru comprendre).

Lorsqu'on peut modéliser un problème sous forme d'une fonction économique à maximiser dans le respect de certaines contraintes, alors on est typiquement dans le cadre de la programmation linéaire.

Soit une fonction économique Z telle que:

où les  sont des variables qui influent sur la valeur de Z, et les  les poids respectifs de ces variables modélisant l'importance relative de chacune de ces variables sur la valeur de la fonction économique.

Les contraintes relatives aux variables s'expriment par le système linéaire suivant:

Sous forme générale et matricielle ce genre de problème s'écrit:

Voyons un exemple qui consiste à résoudre le problème simple suivant:

Une usine fabrique 2 pièces P1 et P2 usinées dans deux ateliers A1 et A2. Les temps d'usinage sont pour P1 de 3 heures dans l'atelier A1 et de 6 heures dans l'atelier A2 et pour P2 de 4 heures dans l'atelier A1 et de 3 heures dans l'atelier A2.

Le temps de disponibilité hebdomadaire de l'atelier A1 est de 160 heures et celui de l'atelier A2 de 180 heures.

La marge bénéficiaire est de 1'200.- pour une pièce P1 et 1'000.- pour une pièce P2.

Quelle production de chaque type doit-on fabriquer pour maximiser la marge hebdomadaire?

Le problème peut se formaliser de la façon suivante:

La fonction économique étant:

à maximiser.

Résolution graphique du problème (ou méthode du "polygone des contraintes"): les contraintes économiques et de signe sont représentées graphiquement par des demi-plans. Les solutions, si elles existent appartiennent donc à cet ensemble appelé "région des solutions admissibles"

Sinon, on peut bien évidemment résoudre ce problème analytiquement en traitant le problème à l'aide de l'algorithme du simplexe

ALGORITHME DU SIMPLEXE

Pour mettre en œuvre cet algorithme, on doit poser le problème sous un forme "standard" et introduire la notion de "programme de base" qui est l'expression algébrique correspondant à la notion de "point extrême du polyèdre des programmes admissibles" étudiée lors de la programmation linéaire (noté ci-après P.L.). En effet, nous verrons que la solution d'un problème de type P.L. si elle existe, peut toujours être obtenue en un programme de base. La méthode du simplexe va donc consister à trouver un premier programme de base puis à construire une suite de programmes de base améliorant constamment la fonction économique et donc conduisant à l'optimum.

Un problème de P.L. est mis sous sa "forme standard" s'il implique la recherche du minimum de la fonction objectif sous des contraintes ayant la forme d'équation linéaires et de conditions de non négativité des variables, c'est-à-dire s'il se pose sous la forme que nous avons vu lors de notre étude de la programmation linéaire:

C'est-à-dire aussi, en utilisant des notation matricielles:

où les matrices  correspondent, respectivement, aux coefficients des niveaux d'activité dans la fonction objectif, aux coefficients techniques des activités et aux seconde membres des contraintes.

Nous allons voir maintenant comme un problème général de P.L. peut toujours être ramené à une forme dite "standard". La notion de "variable d'écart" est essentielle pour effectuer cette "réduction".

Remarque: chercher le maximum d'une fonction  revient à chercher le minimum de la fonction de signe opposé . D'autre part une contrainte qui se présente comme une inéquation:

peut être remplacée par l'équation:

impliquant une variable supplémentaire, , appelée "variable d'écart", et soumise à la contrainte de non-négativité, .

Bien évidemment, dans un cas contraire tel où le système est du type:

Nous écrirons:

impliquant donc également une variable supplémentaire et soumise à la contrainte de non-négativité, .

Ce travail de mise en forme standard nous permet donc de nous retrouver un système d'équation linéaires à résoudre (nous avons vu précédemment sur le site comme résoudre ce genre de système avec l'algorithme du pivot).

La matrice qui représente les composantes du système d'équations peut s'exprimer dans différentes variantes en fonction de la base vectorielle choisie (voir le chapitre d'analyse vectorielle dans la section d'algèbre). Nous allons introduire la notion de "forme canonique utilisable" associée au choix d'une base et nous montrerons que cette reformulation du système de contraintes va nous permettre de progresser vers l'optimum.

La matrice  peut, après introduction des variables d'écart se décompenser en deux sous-matrices , une contenant les variables initiales  et l'autre comportant les variables d'écart  tel que:

Remarque importante: les variables d'écart sont des variables et non des constantes !! Il convient dans un système où les variables sont au nombre de tel que une équation du système s'écrirait:

d'ajouter une variable d'écart tel que:

 où

et sur chaque ligne , la variable d'écart ajoutée doit être différentes de celles déjà insérées dans le système. C'est la raisons pour laquelle nous pouvons décomposer la matrice en deux-sous matrices.

Les colonnes de la matrice  sont bien évidemment, par définition de la méthode, des colonnes unités, linéairement indépendantes. Ces colonnes forment une base de l'espace vectoriel des colonnes à  éléments (ou dimensions) – le nombre de lignes du système. Nous appelons la "matrice de la base".

Les variables associées aux composantes colonnes de la matrice  seront dès maintenant appelées les "variables de base". Dans ce cas, les variables de base sont donc essentiellement les variables d'écart . Les variables associées aux colonnes de la matrice  seront appelées les "variables hors-base"; il s'agit des variables .

Remarque: rappelons que dans l'expression de la fonction économique, seule les variables hors-base apparaissent.

En résumé, tout P.L. une fois mis sous forme standard est tel que:

- il existe une sous-matrice carrée de la matrice  des coefficients techniques, qui est appelée matrice de base et qui est égale à la matrice carrée unité  de dimension  (effectivement il y autant de variables d'écart que de lignes dans le système d'équations original – au nombre de  - et autant de colonnes puisque chaque variable d'écart à un indice différent).

- les variables de base associées n'apparaissent pas dans l'expression de la fonction économiques

- le second membre des contraintes est constitué d'élément non négatifs

Nous disons que le problème est mis sous "forme canonique utilisable associée à la base , correspondant aux variables de base ".

Remarque: Nous pouvons intervertir les matrices (et donc changer de base canonique) et  (ce qui revient à dire que la matrice des variables de base devient la matrices des variables hors-base et inversement).

Il est maintenant commode d'introduire les notations suivantes:

qui sont respectivement le vecteurs des variables de base et le vecteur des variables hors-base.

Ainsi, le système d'équations décrivant les contraintes peut s'écrire indifféremment:

ou bien aussi:

Si la matrice  est une matrice de base, elle est non singulière et admet donc une matrice inverse . En multipliant cette équation, à gauche et à droite, par  nous obtenons:

Le système d'équations aura alors été mis sous une forme résolue en .

Pour obtenir une forme canonique utilisable associée à la base , correspondant aux variables de base, il ne reste plus qu'à éliminer les variables de base de l'expression de la fonction économique.

Ecrivons cette fonction en séparant les vecteurs  et , nous obtenons:

Nous pouvons alors facilement exprimer  en fonction de . En utilisant le système d'équations mis sous forme résolue en , nous avons dans un premier temps:

que nous substituons dans la fonction économique, pour obtenir:

Nous regroupons les termes en  et nous avons:

Nous avons alors toujours système d'équations mais ne comportant plus d'inégalités mais au contraire des égalités !!! Reste plus qu'à démontrer que la solution de ce système dit "programme base" par la méthode du pivot est optimal.

Définition: nous appelons coût réduit de l'activité hors base , le coefficient correspondant  de la ligne .

Soit un problème de programmation linéaire sous forme standard:

La matrice  à  lignes (autant qu'il y a de contraintes) et  colonnes, avec . Si nous sélectionnons  variables de base et si nous annulons les  variables hors base, la matrice :

et le système se réduit à:

La matrice  est de dimension . Si elle définit une base, elle admet une matrice inverse . Une solution du système est donc:

Si l'expression  est non négative , nous avons une solution admissible qui vérifie les contraintes et que nous appellerons un programme de base:

Le problème de programmation linéaire, s'écrit aussi sous la forme suivante, que nous appelons "forme canonique utilisable associée au programme de base":

Définition: nous appelons "coût réduit" de l'activité hors base , le coefficient correspondant  de chaque ligne  de l'expression

A partir des développements effectués précédemment nous pouvons énoncer le résultat suivant:

Proposition 1: si dans la forme canonique utilisable associée à un programme de base, tous les coûts réduits sont  alors le programme de base est optimal.

Proposition 2: La solution d'un problème de P.L., si elle existe, peut toujours être trouvée en un programme de base.

La démonstration précise de ce résultat est assez délicate. Nous pouvons cependant en avoir une intuition en considérant, une fois de plus, la notion de coût réduit.

En effet, pour un programme de base donné, considérons la forme canonique utilisable associée à la base. Sur cette forme nous pouvons vérifier que, ou bien le programme de base est optimal (tous les coûts réduits sont ), ou bien que le programme de base peut être amélioré et remplacé par un nouveau programme de base donnant à  une valeur plus petite (un coût réduit est négatif et la variable hors-base associée peut être augmentée jusqu'à ce qu'une ancienne variable de base s'annule). Comme il y a un nombre fini de programmes de base (au plus égal au nombre ), la solution de P.L. se trouve nécessairement en un programme de base.

METHODE DE MONTE-CARLO

La méthode de Monte-Carlo est un moyen très efficace de contourner les problèmes mathématiques et physiques les plus complexes. Elle trouve ses applications dans des domaines variés dont voici quelques exemples:

  - Aiguille de Buffon

  - Problèmes de neutronique liés à la bombe atomique

  - Calcul d'intégrale ou d'espérance de variables aléatoires

  - Résolution d'équations elliptiques ou paraboliques

  - Résolution de systèmes linéaires

  - Résolution de problèmes d'optimisatio

  - Finance

Il existe 2 types de problèmes qui peuvent être traités par la méthode de Monte-Carlo: les problèmes probabilistes, qui ont un comportement aléatoire, et les problèmes déterministes, qui n'en ont pas.

Pour ce qui est du cas probabiliste, il consiste à observer le comportement d'une série de nombres aléatoires qui simule le fonctionnement du problème réel et à en tirer les solutions.

Pour le cas déterministe, le système étudié est complètement défini et on peut en principe prévoir son évolution, mais certains paramètres du problème peuvent être traités comme s'il s'agissait de variables aléatoires. Le problème déterministe devient alors probabiliste et ré solvable de façon numérique. On parle alors d'estimation de "Monte-Carlo" ou d'une approche de "MC élaborée".

La dénomination de méthode de "Monte-Carlo" date des alentours de 1944. Des chercheurs isolés ont cependant utilisé bien avant des méthodes statistiques du même genre: par exemple, Hall pour la détermination expérimentale de la vitesse de la lumière (1873), ou Kelvin dans une discussion de l'équation de Boltzmann (1901), mais la véritable utilisation des méthodes de Monte-Carlo commença avec les recherches sur la bombe atomique.

Au cours de l'immédiat après-guerre, Von Neumann, Fermi et Ulam avertirent le public scientifique des possibilités d'application de la méthode de Monte-Carlo (par exemple, pour l'approximation des valeurs propres de l'équation de Schrödinger). L'étude systématique en fut faite par Harris et Hermann Khan en 1948. Après une éclipse due à une utilisation trop intensive pendant les années 1950, la méthode de Monte-Carlo est revenue en faveur pour de nombreux problèmes: en sciences physiques, en sciences économiques, pour des prévisions électorales, etc., bref, partout où il est fructueux d'employer des procédés de simulation.

Le mieux pour comprendre la méthode de Monte-Carlo c'est d'abord d'avoir un très bon générateur de nombres aléatoire (ce qui est très difficile). Prenons comme exemple le générateur de Maple:

rand();

restart;rand();

Nous voyons donc que la fonction par défaut de générateur de nombres aléatoires de Maple est à utiliser avec la plus grand prudence puisque un ré-initialisation du système suffit à retrouver des valeurs aléatoires… égales. Cependant il existe des libraires spécialisées dans Maple tel que:

restart;readlib(randomize):randomize():rand();

> restart;readlib(randomize):randomize():rand();

Epreuve à priori réussie (au fait, il nous faudrait faire un beaucoup plus grand nombre d'essais afin de bien vérifier que le générateur ne suive pas une loi de distribution connue… ce qui n'est malheureusement jamais le cas).

Une fois le générateur crée et testé, nous pouvons voir quelques résultat de la méthode de Monte-Carlo. Ainsi, dans le calcul des intégrales, celle-ci s'avère très utile et très rapide en terme de vitesse de convergence.

CALCUL D'UNE INTEGRALE

Soit à calculer l'intégrale d'une fonction  définie et positive sur l'intervalle :

Soit . Nous considérons le rectangle englobant de la fonction sur défini par les points  . Nous tirons un grand nombre  de points aux hasard dans ce rectangle. Pour chaque point, nous testons s'il est au-dessous de la courbe. Soit  la proportion de points situés au-dessous, nous avons:

L'algorithme Maple est donné par:

intmonte:=proc(f,a,b,N)
local i,al,bl,m,F,aleaabs,aleaord,estaudessous;
m:=round(max(a,b)*10^4);
al:=round(a*10^4);
bl:=round(b*10^4);
aleaabs:=rand(al..bl);
aleaord:=rand(0..m);
F:=0;
for i from 1 to N do
     estaudessous:=(f(aleaabs()/10^4)-aleaord()/10^4)>=0;
     if estaudessous then
          F:=F+1;
     fi
od:
RETURN((b-a)*max(a,b)*F/N)
end:

Remarque: pour appeler cette procédure il suffit d'écrire >intmonte(f,a,b,N) mais en remplaçant le premier argument passé en paramètre par l'expression d'une fonction et les autres arguments par des valeurs numériques bien évidemment.

CALCUL DE PI

Pour le calcul de  le principe est le même et constitue donc à utiliser la proportion du nombre de points dans un quartier de cercle (cela permet de simplifier l'algorithme en se restreignant aux coordonnées strictement positives) inscrit dans un carré relativement au nombre de points total (pour tester si un point est à l'extérieur du cercle, nous utilisons bien évidemment le théorème de Pythagore) tel que:

L'algorithme Maple est donné par:

estalinterieur:=proc(x,y) x^2+y^2<1 end:
calculepi:=proc(N)
local i,F,abs,ord,alea,erreur,result;
alea:=rand(-10^4..10^4);
F:=0;
for i from 1 to N do
     abs:=alea()/10^4;ord:=alea()/10^4;
       if estalinterieur(abs,ord) then
            F:=F+1;
       fi
od;
RETURN(4*F/N)
end:

DICHOTOMIE

La dichotomie consiste pour un objet de taille N à exécuter un algorithme de façon à réduire la recherche à un objet de taille . On répète l'algorithme de réduction sur ce dernier objet. Ce type d'algorithme est souvent implémenté de manière récursive. Lorsque cette technique est utilisable, elle conduit à un algorithme très efficace et très lisible.

Un exemple simple est la recherche de la racine d'une fonction continue (nous avons déjà étudié différentes méthodes plus haut pour résoudre ce genre de problèmes).

Supposons qu'une fonction soit croissante et continue sur un intervalle . Nous avons donc . Nous  calculons . Si  alors la racine est dans l'intervalle  sinon elle est dans l'intervalle . Nous a donc ramené le problème à une taille inférieure. Nous arrêterons l'algorithme quand la précision sera suffisante.

L'algorithme Maple est donné par:

zero:=proc(f,a,b,pre)
local M;
M:=f((a+b)/2);
if abs(M)<pre then 
     RETURN((a+b)/2)
elif M>0 then
     zero(f,a,(a+b)/2,pre)
else zero(f,(a+b)/2,b,pre)
     fi
end:

et ce ne sont que quelques exemples auxquelles la méthode est applicable!!