Sciences.ch (méthodes numériques 1/2)

L'informatique théorique est la branche des sciences qui s'occupe du développement d'algorithmes et d'outils théoriques applicables à l'informatique pour la résolution de problèmes formels lié à la simulation de phénomènes physiques ou au traitement et l'échange d'informations. (Larousse)

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).

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.

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):

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!)

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

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.

Nous notons

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.

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.

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é

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.

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(n^k) pour

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.

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

Nous pouvons facilement montrer que cette factorisation maintient le même nombre d'additions

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,

à l'étape 2, et plus générale à

à 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

. Nous en déduisons le nombre maximal d'étapes: c'est le plus petit k tel que

, soit

, soit:

à 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

. 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) :

- 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 à :

En faisant l'hypothèse que l'ordinateur utilisé effectue une opération élémentaire en

secondes (ce qui est déjà une bonne machine). Nous obtenons alors les temps de calculs suivants pour plusieurs valeurs de n :

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(n²), complexité quadratique, O(n³), complexité cubique, O(kⁿ) 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.

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

. 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

, 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

il est trivial de vérifier que

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

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

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?

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:

P7. Si

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

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

Pour P2, 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 à x. Ce nombre est évidemment [x].

Pour la dernière partie, nous observons que, si

sont tous les entiers positifs

qui sont divisibles par a, il suffit de prouver que

. Puisque

, alors:

ALGORITHME D'HÉRON

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

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

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

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

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:

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

Le principe de l'algorithme d'Archimède est le suivant: Soit

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:

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" 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):

Cette relation donne un algorithme pour calculer l'exponentielle

à un ordre n donnée de précision.

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 :

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

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:

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

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 :

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 ÉQUATIONS À TROIS INCONNUES

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:

1. Dans la première, nous choisissons

comme pivot et nous éliminons les coefficients

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:

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

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 n équations n inconnues.

N ÉQUATIONS À 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 linéaire (nous pourrions très bien le représenter sous la forme d'une matrice augmentée afin d'alléger les écritures) :

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, 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

tel que:

Il est amené à

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.

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

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 :

RÉGRESSIONs ET INTERPOLATIONS

Les régressions (ou "interpolations") sont des outils très utiles aux statisticiens, ingénieurs, informaticiens souhaitant établir une 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, polynomiale ou encore logistique.

RÉGRESSION LINÉAIRE À UNE VARIABLE EXPLICATIVE

Nous présentons ici deux algorithmes (méthodes) utiles et connus 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 x et y indépendantes :

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

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

DROITE DE RÉGRESSION

Il existe aussi une autre manière commune de faire une régression linéaire du type :

qui consiste à se baser sur les propriétés de la covariance et de l'espérance (cf. chapitre de Statistiques) et très utilisée entre autres en finance (mais aussi dans n'importe quel domaine où on fait un peu de statistique).

Soit x, y deux variables dont l'une dépend de l'autre (souvent c'est y qui dépend de x) nous avons selon la propriété de linéarité de la covariance qui est rappelons-le :

Il vient donc pour la pente (nous réutiliserons cette relation lors de l'étude du rendement d'un portefeuille selon le modèle de Sharpe dans le chapitre d'Économétrie) :

et pour l'ordonnée à l'origine nous utilisons les propriétés de l'espérance démontrées dans le chapitre de Statistiques:

MÉTHODE DES MOINDRES CARRÉS

Du fait de l'erreur sur y, 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 expérimentale qui passe le plus près possible de ces points.

La "méthode des moindres carrés" consiste à chercher les valeurs des paramètres a, b qui rendent minimale la somme des carrés des écarts e_i résiduels (SS_r: Sum of Squared Residuals) entre les valeurs observées

et les valeurs calculées théoriques de

Cette relation fait apparaître la somme des carrés des écarts comme une fonction des paramètres a,b. Lorsque cette fonction est minimale (extrêmale), les dérivées par rapport à ses paramètres s'annulent:

Remarque: Cette méthode de recherche de minimum (optimisation) est nommée "méthode des multiplicateurs de Lagrange" dans le monde de l'économétrie. Dans notre exemple

est la grandeur scalaire qui fait office de multiplicateur de Lagrange.

C'est un système linéaire de deux équations à deux inconnues. Notons pour simplifier:

Ainsi, l'expression de la pente et de l'ordonnée à l'origine de l'équation recherchée est :

Le terme b, soit l'ordonnée à l'origine peut être obtenu avec la fonction ORDONNEE.ORIGINE( ) de MS Excel et a avec la fonction PENTE( ) et l'ensemble avec la fonction DROITEREG( ).

Maintenant, nous faisons l'hypothèse que chaque valeur mesurée est entachée d'un résidu tel que:

Maintenant, passons par un résultat intermédiaire. Rappelons que nous avons obtenu plus haut:

Multipliant la deuxième relation ci-dessus par

et retranchant de la première, nous obtenons:

Si nous mettons le tout au carré et en sommant pour toutes les observations, nous avons:

Cette dernière relation est appelée "équation d'analyse de la variance". En fait, il s'agit de sommes de carrés. Il faudrait diviser par n pour obtenir des variances.

où SCT est la "somme des carrés totale" (SS_r en anglais), SCE la "somme des carrés expliquée" et SCR la "somme des carrés résiduelle".

Cette dernière relation se trouve également souvent sous la forme suivante dans la littérature:

Notons maintenant les

sans erreurs d'une manière différente et appelons cela le "modèle linéaire à priori":

Il est effectivement important dans la pratique de différencier le modèle à priori qui ne prend pas en compte les erreurs du modèle réel entaché d'erreurs!

et il vient alors immédiatement la relation importante dans la pratique pour calculer les résidus (connaissant les valeurs calculées et les valeurs mesurées):

Rappelons maintenant que dans la chapitre de Statistique nous avions déterminé que le coefficient de corrélation s'exprimait par:

Montrons que ceci est égal à (notation souvent utilisée dans la littérature spécialisée):

Nous admettrons que, pour un individu i prélevé au hasard dans la population,

est connu sans erreur, et que

est une réalisation d'une variable aléatoire que nous noterons dorénavant

et la droite théorique des moindre carrés s'écrira maintenant :

où

est par hypothèse un résidu identiquement distribué et indépendant pour chaque point i selon une loi normale centrée (de moyenne nulle et d'écart-type égal pour tout k) tel que:

où nous avons le résidu qui est donc donné par la différence entre l'ordonnée théorique et l'ordonnée mesurée:

Les hypothèses précédentes concernant les moments des résidus sont appelées "hypothèses de Gauss-Markov" et l'hypothèse particulière d'égalité des variances s'appelle comme nous l'avons vu dans le chapitre de Statistique "l'homoscédasticité".

Nous avons de par la propriété de l'espérance (cf. chapitre de Statistiques):

Alors sous les hypothèses ci-dessus, nous allons montrer que a et b sont des estimateurs sans biais (cf. chapitre de Statistiques) de

et qu'il est possible d'estimer l'écart-type à partir de SCR! Ce qui est un résultat non négligeable et important.

Conformément au modèle adopté, a est à considérer maintenant comme une réalisation de la variable aléatoire donnée par :

Nous devons enfin calculer les variances de A et B en utilisant ses propriétés (cf. chapitre de Statistiques) et les hypothèses sur les résidus, nous avons:

Comme par hypothèse nous avons tous les

qui sont égaux nous pouvons alors écrire:

Le problème réside maintenant dans la détermination de

. Evidemment pour ce faire nous allons être obligés de passer par un estimateur statistique.

Nous savons que nous pouvons écrire selon ce qui a été vu dans le chapitre de Statistique en ce qui concerne les estimateurs:

puisque la loi normale est centrée pour les résidus donc

... et que le résidu est une variable aléatoire implicitement dépendante de la somme de deux variables aléatoires que sont A et B d'où la minoration de deux fois l'erreur-standard.

Indiquons aussi que dans la pratique nous notons fréquemment ce dernier résultat en mélangeant les notations de l'aspect aléatoire et déterministe:

où SEE signifie en anglais "Standard Error of Estimate" (Erreur Standard de l'Estimation).

Ce qui est sympa connaissant ces variances, c'est que nous pouvons aussi estimer la variance de la variable expliquée de notre régression facilement.

Il serait intéressant aussi de faire de l'inférence statistique sur l'espérance des paramètres A et B (donc la pente et l'ordonnée à l'origine) étant donné leur espérance empirique connue. Mais les développements nécessitent une hypothèse forte qui est l'indépendance des variables (

) ce qui est peu acceptable en entreprise.

RÉGRESSION LOGISTIQUE

Bien souvent, les données statistiques disponibles sont relatives à des caractères qualitatifs. Or, comme nous allons le voir, les méthodes d'inférence traditionnelles ne permettent pas de modéliser et d'étudier ce type caractères. Des méthodes spécifiques doivent être utilisées tenant compte par exemple de l'absence de continuité des variables traitées ou de l'absence d'ordre naturel entre les modalités que peut prendre le caractère qualitatif. Ce sont ces méthodes spécifiques les plus usuelles qui seront l'objet du texte qui suit.

Comme nous l'avons vu plus haut, la régression linéaire simple a donc pour but de modéliser la relation entre une variable dépendante quantitative et une variable explicative quantitative.

Lorsque la "variable de classe" Y à expliquer est binaire (oui-non, présence-absence,0-1,etc.) nous approchons dans un premier temps celle-ci par une fonction de probabilité

, qui nous donne à l'opposé la probabilité d'appartenir à la classe

, que nous nommerons "régression logistique" ou encore "régression logit" (très souvent utilisée dans les cadre des réseaux de neurones formels). Ensuite, dans une deuxième étape, nous définissons pour un cas binaire une valeur "cutoff". Par exemple, si nous prenons un cutoff de 0.5 alors les cas pour lesquels

appartiendront à la classe 1 (et inversement dans le cas contraire).

Remarques:

R1. Au fait, la régression logistique n'est qu'une simple loi de distribution de probabilités dans le cas qui nous intéresse (nous verrons une autre régression logistique dans le chapitre d'Économétrie lors de notre étude des séries temporelles).

R2. Il n'est évidemment pas possible d'appliquer systématiquement la régression logistique à n'importe quel type d'échantillon de données! Parfois il faut chercher ailleurs...

R3. Lorsque le nombre de modalités est égal à 2, nous parlons de "variable dichotomique" (oui-non) ou d'un "modèle dichotomique", s'il est supérieur à 2, nous parlons de "variables polytomiques" (satisfait-non satisfait-émerveillé).

Considérons par exemple la variable dichotomique : fin des études. Celle-ci prend deux modalités (en cours, a fini). L'âge est une variable explicative de cette variable et nous cherchons à modéliser la probabilité d'avoir terminé ses études en fonction de l'âge.

Pour construire le graphique suivant, nous avons calculé et représenté en ordonnées, pour des jeunes d'âge différent, le pourcentage de ceux qui ont arrêté leurs études.

Mais comment obtient-t-on pareil graphique avec une variable dichotomique??? Au fait c'est simple. Imaginez un échantillon de 100 individus. Pour ces 100 individus supposez pour un âge donné que 70% "a fini" et 30% "en cours". Eh bien la courbe représente simplement la proportion des deux classes pour l'âge donné. Il est même parfois indiqué les grosseurs des classes avec des cercles sur toute la longueur des asymptotes horizontales pour bien signifier qu'il s'agit d'une variable dichotomique.

Les points sont distribués selon une courbe en S (une sigmoïde) : il y a deux asymptotes horizontales car la proportion est comprise entre 0 et 1. Nous voyons immédiatement qu'un modèle linéaire serait manifestement inadapté.

Cette courbe évoqueront pour certains, à juste titre, une courbe cumulative représentant une fonction de répartition (d'une loi normale par exemple, mais d'autres lois continues ont la même allure). Ainsi, pour ajuster une courbe à cette représentative, nous pourrions nous orienter vers la fonction de répartition d'une loi normale, et au lieu d'estimer les paramètres a et b de la régression linéaire, nous pourrions estimer les paramètres

de la loi Normale (qui est très similaire à la loi logistique comme nous le démontrerons plus loin). Nous parlons alors d'un "modèle Probit".

La loi qui nous intéresse cependant est donc la loi logistique. Contrairement à la loi Normale, nous savons calculer l'expression de sa fonction de répartition dichotomique (probabilité cumulée) qui est du type (c'est son premier avantage!):

pour une variable de prédiction x où P est donc la probabilité d'avoir un 1. Nous voyons immédiatement que cette dernière relation étant la primitive de la fonction de distribution, que prenant x de moins l'infini à plus l'infini que nous avons bien 1. Il s'agit donc bien d'une fonction de répartition!

Lorsque nous optons pour cette fonction de répartition de la loi logistique, nous obtenons le modèle de régression logistique ou "modèle Logit" et c'est là son deuxième avantage le plus important: nous pouvons faire des statistiques sur une régression linéaire multiple!

Ainsi, nous estimerons la probabilité cumulée d'avoir fini ses études pour un individu d'âge x par (il existe plusieurs manières d'écrire cette loi suivant les habitudes et le contexte) :

Nous pouvons calculer aussi l'espérance de la fonction de distribution en appliquant ce qui a déjà été vu au chapitre de Statistiques mais une partie de cette intégrale ne peut être résolue que numériquement par contre... si nous posons:

Nous retombons sur une fonction de répartition ayant parfaitement les mêmes caractéristiques qu'une loi Normale centrée réduite (moyenne nulle et variance unitaire).

Les paramètres a, b sont ajustés selon le principe du maximum de vraisemblance (cf. chapitre de Statistiques). De plus, ces paramètres doivent généralement être ajustés de manière itérative, à l'aide d'un programme auquel nous fournissons des valeurs initiales, et qui optimise ces valeurs de manière récurrente (nous n'entrerons pas dans ces détails qui dépassent le cadre théorique de ce site à ce jour).

Le résultat de cette dernière transformation est appelé "logit". Il est égal au logarithme de "l'odds" P/1-P.

Donc lorsque les coefficients a et b ont été déterminés, l'expression précédente permet de déterminer P connaissant x facilement (il s'agit de résoudre une équation linéaire) et inversement! Par ailleurs, puisque x est une variable dichotomique les coefficients sont très facilement interprétables.

Remarque: L'odds est également appelé "cote" par analogie à la cote des chevaux au tiercé. Par exemple, si un étudiant a 3 chances sur 4 d'être reçu, contre 1 chance sur 4 d'être collé, sa cote est de 3 contre un 1, soit un odds=3.

Revenons un peu sur l'odds car il est possible d'introduire la notion de fonction logistique en faisant la démarche inverse de celle présentée ci-dessus (soit de commencer par la définition de l'odds pour aller jusqu'au logit) et ceci peut parfois même s'avérer plus pédagogique.

Supposons que nous connaissons la taille (hauteur) d'une personne pour prédire si la personne est un homme ou une femme. Nous pouvons donc parler de probabilité d'être un homme ou une femme. Imaginons que la probabilité d'être un homme pour une hauteur donnée est 90%. Alors l'odds d'être un homme est :

Dans notre exemple, l'odds sera de 0.90/0.10 soit 9. Maintenant, la probabilité d'être une femme sera donc de 0.10/0.90 soit 0.11. Cette asymétrie des valeurs est peu parlante parce que l'odds d'être un homme devrait être l'opposé de l'odds d'être une femme idéalement. Nous résolvons justement cette asymétrie à l'aide du logarithme naturel. Ainsi, nous avons :

Ainsi, le logit (logarithme de l'odds) est exactement l'opposé de celui d'être une femme de par la propriété du logarithme:

Imaginons qu'une banque souhaite faire un scoring des ses débiteurs. Comme elle a plusieurs succursales (la banque) elle construit les tables de données (fictives...) suivantes pour chacune (toutes les succursales ne sont donc pas représentées):

Montant crédit	Payé	Non Payé
27200	1	9
27700	7	3
28300	13	0
28400	7	3
29900	10	1

Tableau: 57.3 - Scoring débituers par montant de crédit succursale 1

Montant crédit	Payé	Non Payé
27200	0	8
27700	4	2
28300	6	3
28400	5	3
29900	8	0

Tableau: 57.4 - Scoring débituers par montant de crédit succursale 2

Montant crédit	Payé	Non Payé
27'200	1	8
27'700	6	2
28'300	7	1
28'400	7	2
29'900	9	0

Tableau: 57.5 - Scoring débituers par montant de crédit succursale 3

Nous pouvons voir que la proportion totale des bons débiteurs dans les trois succursales est de

Quand le crédit est inférieur à 27'500, la proportion de bons débiteurs est de

. Quand le montant des crédits est inférieur à 28'000 la proportion de bons débiteurs est de

Quand le montant des crédits est inférieur à 28'500, la proportion de bons débiteurs est de

, et pour des montants inférieurs à 30'000 la proportion est de

Nous poserons pour cette régression logistique que

est un bon risque de crédit et

est un mauvais risque. Ensuite, nous créons le tableau suivant qui est un récapitulatif des données de toutes les succursales:

Montant crédit	Proportion P
27'200	0.0741
27'700	0.7083
28'300	0.8667
28'400	0.7037
29'900	0.9643

Tableau: 57.6 - Proportion des bons débiteurs

Montant crédit KF	Proportion P	Logit
27'200	0.0741	-2.5257
27'700	0.7083	0.8873
28'300	0.8667	1.8718
28'400	0.7037	0.8650
29'900	0.9643	3.2958

Tableau: 57.7 - Proportion des bons débiteurs et Logit

Ainsi, il est possible de dire dans cet exemple, qu'elle est la proportion P de bons ou mauvais payeurs en fonction d'une valeur de crédit X plus petite ou égale à une certaien valeur donnée. Puisque 0 est un mauvais risque de crédit, nous voyons que plus les crédits sont élevés moins le risque est gros (dans ce cas fictif...).

INTERPOLATION POLYNÔMIALE

Il existe de nombreuses techniques d'interpolation de polynômes plus ou moins complexes et élaborées. Nous nous proposons ici de présenter quelques unes dans l'ordre croissant de difficulté et de puissance d'application.

COURBES DE BÉZIER (SPLINE)

L'ingénieur russe Pierre Bézier (Peugeot), aux débuts de la Conception Assistée par Ordinateur (C.A.O), dans les années 60, a donné un moyen de définir des courbes et des surfaces à partir de points. Ceci permet la manipulation directe, géométrique, des courbes sans avoir à donner d'équation à la machine!!

Le thème des Courbes de Bézier est une notion à multiples facettes, vraiment très riche, au croisement de nombreux domaines mathématiques très divers : Analyse, Cinématique, Géométrie Différentielle, Géométrie Affine, Géométrie Projective, Géométrie Fractale, Probabilités, ...

Les Courbes de Bézier sont par ailleurs devenues incontournables dans leurs applications concrètes dans l'industrie, l'infographie, ...

D'abord, nous savons que l'équation d'une droite que nous noterons dans le domaine (par respect de tradition) M joignant deux points

est:

Ce qui est juste puisque lorsque

nous sommes en A et lorsque

nous sommes en B. Donc

et le point M parcoure tout le segment [AB]. Par construction, si A et B étaient des masses physiques égales à l'unité,

représente le barycentre (centre de gravité) du système pour un t donné.

Par définition, le segment [AB] est par définition la "courbe de Bézier de degré 1" avec points de contrôle A et B et les Polynômes 1-t et t sont les "polynômes de Bernstein de degré 1".

Construisons maintenant une courbe paramétrée en rajoutant une 2ème étape à ce qui précède:

- Soit

le barycentre de (A,1-t) et (B, t) et où

décrit [AB].
- Soit

le barycentre de (B,1-t) (C, t) et où

décrit [BC].

Par construction, M(t) se situe donc à la même proportion du segment

que

par rapport au segment [AB] ou

par rapport au segment [BC].

La courbe obtenue est alors l'enveloppe des segments

: en tout point M, la tangente à la courbe est donc le segment

M(t) décrit alors une Courbe de Bézier de degré 2, qui, par construction
commence en A et se finit en C, et a pour tangentes [AB] en A et [BC] en C.

C'est en fait un arc de parabole (que nous pourrions noter très logiquement [ABC] ) :

Par le même schéma, nous pouvons définir une courbe de Bézier de n points

soit

. C'est ce que nous appelons "l'algorithme de Casteljau". Ainsi, soit:

Considérons maintenant M(t) la courbe de Bézier d'ordre 3, nous avons donc les points définis par:

Et là nous pouvons creuser un peu les coefficients en comparant les coefficients de Bézier des courbes d'ordre 2, 3 et 4.

et si on regarde de plus près les coefficients nous remarquons que nous avons aussi:

Il ne s'agit ni plus ni moins que du triangle de Pascal!! Et donc les constantes sont simplement les coefficients binomiaux (cf. chapitre de Calcul Algébrique) donnés par pour l'ordre n dans notre cas par:

Nous aurions alors les polynômes de Bernstein qui seraient donnés (ce qui est plus respectueux des traditions....):

C'est une relation très pratique car elle permet de calculer facilement et rapidement le polynôme correspondant à une courbe de Bézier d'ordre n.

Un exemple très connu des courbes de Bézier d'ordre 3 est l'outil Plume des produits phares Adobe Photoshop ou Adobe Illustrator. Effectivement ces deux outils créent une succession de courbes de Bézier d'ordre 3 dont le point

est défini après coup à la souris en utilisant des poignées ("torseurs" dans le langage de spécialistes Adobe...). Voici un exemple prix d'un de ces logiciels fait avec un tracé à la plume de 5 points (soit 4 splines):

Tant que l'utilisateur ne bouge pas les poignées de points alors tous les points sont alignés sur la droite. Nous avons alors l'impression d'avoir une spline d'ordre 2.

MÉTHODE D'EULER

Il s'agit là de la méthode numérique la plus simple (elle est triviale et dans l'idée assez proche de la méthode de Newton même si leur objectif n'est pas le même). En fait elle ne fournit une approximation (au sens très large du terme) d'une fonction f(x) dont la dérivée est connue.

Ici les points choisis sont équidistants, c'est-à-dire

(h étant le "pas"). Nous notons

la valeur exacte et

, la valeur approchée.

Par construction nous savons (cf. chapitre de Calcul Différentiel Et Intégral) que (nous adoptons une notation un peu particulière dans ce contexte) :

qui correspond donc bien à la pente (non instantané bien sûr!) en equation

de la "courbe intégrale" passant par ce point. D'où :

POLYNÔME DE COLLOCATION

Soit

une fonction connue sous forme explicite ou sous forme tabulée, et supposons qu'un certain nombre de valeurs :

"Interpoler" f signifie estimer les valeurs de f pour des abscisses situées entre equation

, c'est-à-dire dans l'intervalle d'interpolation, par une fonction approximante equation

, qui vérifie les "conditions de collocations" (rien à voir avec votre colocataire !) :

La fonction p s'appelle "fonction de collocation" sur les

. Lorsque p est un polynôme, nous parlons de "polynôme de collocation" ou de "polynôme d'interpolation".

"Extrapoler" f signifie approcher f(x) par p(x) pour des abscisses situées "hors" de l'intervalle d'interpolation.

Quand nous connaissons un polynôme de degré n en n+1 points, nous pouvons donc 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èmes 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 exemple particulier devrait suffire à la compréhension de cette méthode, la généralisation en étant assez simple (voir plus loin).

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

Théorème : Soient

des points d'appui, avec

. Alors il existe un polynôme

de degré inférieur ou égal à n, et un seul, tel que

pour

relation que nous appelons "déterminant de Vandermonde". Nous savons que si le système à une solution, le déterminant du système doit être non nul (cf. chapitre d'Algèbre linéaire).

Montrons par l'exemple (en reprenant un polynôme du même degré que celui que nous avons utilisé plus haut) que le déterminant se calcule selon la relation suivante précédente (le lecteur généralisera par récurrence) :

Calculons ce déterminant suivant la colonne 1 (en faisant usage des cofacteurs comme démontré dans le chapitre d'Algèbre linéaire) :

Comme les

sont l'énoncé de notre problème tous différents tels que

alors le système a une solution unique. Ce qui prouve qu'il existe toujours alors un polynôme d'interpolation.

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.

Evariste 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 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

, nous traçons les courbes représentant g et h. 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 f choisie. Il faut par exemple, que la fonction f 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 [a,b] tel que:

- f est continue sur ou

- unique,

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:

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èmes de Thalès (cf. chapitre de Géométrie Euclidienne):

2. Déterminer

. Si

est assez petit, nous arrêtons le calcul et affichons x et f(x)

MÉTHODE DE LA BISSECTION

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

tel que:

Il faut encore fixer

qui est définit comme la borne supérieure de l'erreur admissible.

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:

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

est le point de coordonnées

, alors les points

sont alignés sur la sécante. La proportion suivante (Thalès) est donc vraie:

MÉTHODE DE NEWTON

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 f qui est dérivable en

, alors nous pouvons la réécrire sous la forme:

où

est la dérivée de f en

est une fonction qui tend vers 0 comme

pour

lorsque x tend vers

(c'est un terme correctif qui sous-tend la suite des termes du développement de Taylor).

La fonction

empêche la résolution de cette équation par rapport à

. En négligeant le terme

, l'équation se réécrit:

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 f satisfait à certaines conditions.

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

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

La condition (2) est évidente, 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

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

par le quotient différentiel:

Si la méthode de résolution est convergente, l'écart entre

diminue à chaque itération. Ceci est assuré, par exemple, si l'intervalle [a,b] contenant

, voit sa longueur diminuer à chaque étape. La méthode de Newton est intéressante car la convergence est quadratique:

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

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 f et f ' au voisinage de

En soustrayant

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

AIRES ET SOMMES DE RIEMANN

Nous désirons calculer l'aire comprise entre l'axe x, la courbe de f et les droites d'équations

. Nous supposons dans ce cas que la fonction f 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 (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

en n sous-intervalles dont les bornes sont

. Les longueurs de ces sous intervalles sont

. Nous construisons les rectangles dont les côtés sont

Si les

sont suffisamment petits,

est une bonne approximation de l'aire cherchée. Nous pouvons recommencer cet exercice en choisissant

comme côtés des rectangles. Nous obtenons alors:

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:

MÉTHODE DES TRAPÈZES

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:

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

PROGRAMMATION LINÉAIRE

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 consiste en un "polygone des contraintes".

Remarques:

R1. La programmation linéaire est beaucoup utilisée (pour ne citer que les cas les plus connus) dans la logistique, la finance d'entreprise ou encore aussi en théorie de la décision lorsque nous devons résoudre un jeu à stratégie mixte (voir le chapitre de Théorie de la décision et des jeux pour voir un exemple pratique).

R2. Dans le cadre de résolution de problèmes où interviennent des produits de deux variables nous parlons alors logiquement "programmation quadratique". C'est typiquement le cas en économétrie dans la modélisation des portefeuilles (cf. chapitre d'Econométrie).

R3. La programmation quadratique et linéaire sont réunies dans l'étude générale de ce que nous appelons la "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 le plus utilisé qui est "l'algorithme du simplexe".

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.

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:

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?

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" :

Remarque: Dans le cas général, pour ceux qui aiment le vocabulaire des mathématiciens..., la donnée d'une contrainte linéaire correspond géométriquement à la donnée d'un demi-espace d'un espace à n dimensions (n étant le nombre de variables). Dans les cas élémentaires, l'ensemble des points de l'espace qui vérifient toutes les contraintes est un convexe limité par des portions d'hyperplan (voir le cas 2 variables, facile à illustrer). Si la fonction de coût est linéaire, l'extrémum est à un sommet (facile à voir). L'algorithme du simplex de base (voir plus loin) part d'un sommet et va au sommet d'à côté qui maximise localement le coût. Et recommence tant que c'est possible.

Pour trouver les coordonnées des sommets, on peut utiliser le graphique si les points sont faciles à déterminer.

Il s'agit donc de chercher à l'intérieur de ce domaine (connexe), le couple

maximisant la fonction économique.

Or, l'équation Z est représentée par une droite de pente constante (-1.2) dont tous les points

fournissent la même valeur Z pour la fonction économique.

En particulier, la droite

passe par l'origine et donne une valeur nulle à la fonction économique. Pour augmenter la valeur de Z et donc la fonction économique, il suffit d'éloigner de l'origine (dans le quart de plan

) la droite de pente -1.2.

Pour respecter les contraintes, cette droite sera déplacée, jusqu'à l'extrême limite où il n'y aura plus qu'un point d'intersection (éventuellement un segment) avec la région des solutions admissibles.

La solution optimale se trouve donc nécessairement sur le pourtour de la région des solutions admissibles et les parallèles formées par la translation de la fonction économique s'appellent les "droites isoquantes" ou "droites isocoûts"...

Voyons maintenant comment résoudre ce problème de manière analytique avant de passer à la partie théorique.

Nous introduisons d'abord la "variable d'écart"

afin de transformer les 3 inégalités par des égalités. Le système d'équations devient alors une "forme standard" :

La situation peut se résumer dans le tableau suivant (nous omettons la représentation de la variable d'écart dans le tableau-matrice qui ne sert qu'à égaliser les équations) :

Nous déterminons maintenant le pivot (voir plus loin la méthode du pivot), pour cela nous choisissons la colonne où le coefficient économique est le plus grand. Ici c'est la colonne 1.

3. On divise les éléments de la colonne du pivot (pivot exclu) par le pivot mais on change leur signe ensuite

4. Pour les autres éléments de la première ligne : élément de la ligne 1 diminué de l'élément correspondant sur la ligne de pivot multiplié par 3/6 (rapport des valeurs dans la colonne de pivot)

Nous n'atteignons la solution optimale que lorsque tous les éléments de la marge sont négatifs ou nuls. Il faut donc continuer (car il reste 400 dans la colonne

) ... ici, on atteint déjà l'optimum au troisième tableau, mais ce n'est pas une généralité (le pivot est 2.5 cette fois). On recommence donc les opérations :

Le processus est terminé car tous les termes de la fonction économique sont négatifs. Le programme optimum est donc de

pour un résultat de :

ALGORITHME DU SIMPLEXE

Pour mettre en oeuvre cet algorithme, nous devons poser le problème sous une 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 donc 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:

où les matrices

correspondent, respectivement, aux coefficients des niveaux d'activité dans la fonction objectif, aux coefficients techniques des activités et aux secondes membres des contraintes.

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

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

impliquant une variable supplémentaire,

, appelée donc "variable d'écart", et soumise à la contrainte de non-négativité,

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 retrouver un système d'équations 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 A 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 A peut, après introduction des variables d'écart se décompenser en deux sous-matrices

, une contenant les variables initiales D et l'autre comportant les variables d'écart B tel que:

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

(57.261)

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

(57.262)

où et sur chaque ligne m, la variable d'écart ajoutée doit être différente 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 B 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 à m éléments (ou dimensions) - le nombre de lignes du système. Nous appelons B la "matrice de la base".

Les variables associées aux composantes colonnes de la matrice B seront dès maintenant appelées les "variables de bases". Dans ce cas, les variables de base sont donc essentiellement les variables d'écart

. Les variables associées aux colonnes de la matrice D seront appelées les "variables hors-base"; il s'agit des variables

- il existe une sous-matrice carrée de la matrice A des coefficients techniques, qui est appelée matrice de base et qui est égale à la matrice carrée unité I de dimension

(effectivement il y autant de variables d'écart que de lignes dans le système d'équations original - au nombre de m - 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 économique.

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

qui sont respectivement les 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:

Si la matrice B 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:

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

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:

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 optimale.

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

de la ligne

La matrice A à m lignes (autant qu'il y a de contraintes) et n colonnes, avec

. Si nous sélectionnons m variables de base et si nous annulons les

variables hors base, la matrice A:

La matrice B 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 j, le coefficient correspondant

de chaque ligne j 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 à z 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.

MÉTHODE 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:

- Résolution de problèmes d'optimisation (recherche opérationnelle, gestion de projets)

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:

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

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éé et testé, nous pouvons voir quelques résultats 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 termes de vitesse de convergence.

CALCUL D'UNE INTÉGRALE

Soit à calculer l'intégrale d'une fonction f définie et positive sur l'intervalle [a,b]:

Nous considérons le rectangle englobant de la fonction sur [a,b] défini par les points

. Nous tirons un grand nombre N de points au hasard dans ce rectangle. Pour chaque point, nous testons s'il est au-dessous de la courbe. Soit F la proportion de points situés au-dessus, nous avons:

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:

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 N/2. 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). C'est-à-dire le point pour laquelle la fonction f s'annule.

Supposons qu'une fonction soit croissante et continue sur un intervalle [a,b] et tel la racine cherchée soit entre a et b. Nous avons donc par le fait que la fonction soit croissante dans l'intervalle:

alors la racine est dans l'intervalle

sinon elle est dans l'intervalle

. Nous avons donc ramené le problème à une taille inférieure. Nous arrêterons l'algorithme quand la précision sera suffisante.

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:

COMPLEXITÉ

NP-COMPLÉTUDE

PARTIE ENTIÈRE

ALGORITHME D'HÉRON

ALGORITHME D'ARCHIMÈDE

CALCUL DU NOMBRE D'EULER

CALCUL DE LA FACTORIELLE (FORMULE DE STIRLING)

SYSTEMES D'ÉQUATIONS LINÉAIRES

UNE ÉQUATION À UNE INCONNUE

DEUX ÉQUATIONS À DEUX INCONNUES

TROIS ÉQUATIONS À TROIS INCONNUES

N ÉQUATIONS À N INCONNUES

POLYNÔMES

RÉGRESSIONs ET INTERPOLATIONS

RÉGRESSION LINÉAIRE À UNE VARIABLE EXPLICATIVE

DROITE DE RÉGRESSION

MÉTHODE DES MOINDRES CARRÉS

ANALYSE DE LA VARIANCE DE LA RÉGRESSION

RÉGRESSION LOGISTIQUE

INTERPOLATION POLYNÔMIALE

COURBES DE BÉZIER (SPLINE)

MÉTHODE D'EULER

POLYNÔME DE COLLOCATION

RECHERCHE DES RACINES

MÉTHODE DES PARTIES PROPORTIONNELLES

MÉTHODE DE LA BISSECTION

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

MÉTHODE DE NEWTON

AIRES ET SOMMES DE RIEMANN

MÉTHODE DES RECTANGLES

MÉTHODE DES TRAPÈZES

PROGRAMMATION LINÉAIRE

ALGORITHME DU SIMPLEXE

MÉTHODE DE MONTE-CARLO

CALCUL D'UNE INTÉGRALE

CALCUL DE PI

DICHOTOMIE