Analyse numérique

Analyse numérique

Lanalyse numérique est une discipline des mathématiques. Elle sinté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 danalyse mathématique.

Plus formellement, lanalyse 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 quelle soccupe principalement de répondre numériquement à des questions à variable réelle ou complexe comme lalgèbre linéaire numérique sur les champs réels ou complexes, la recherche de solution numérique déquations différentielles et dautres problèmes liés survenant dans les sciences physiques et lingénierie.

Sa mise en œuvre pratique et ses domaines dapplication sont décrits plus complètement dans larticle calcul numérique.
Simulation numérique d'un crash de véhicule

Sommaire

Introduction générale

Certains problèmes de mathématiques peuvent être résolus numériquement (i.e., sur ordinateur) de façon exacte par un algorithme en un nombre fini d'opérations. Ces algorithmes sont parfois appelés méthodes directes ou qualifiés de finis. Des exemples sont lélimination de Gauss-Jordan pour la résolution dun système déquations linéaires et lalgorithme du simplexe en optimisation linéaire.

Cependant, aucune méthode directe nest connue pour certains problèmes (de plus, pour une classe de problèmes dits NP-complets, aucun algorithme de calcul direct en temps polynomial n'est connu à ce jour). Dans de tels cas, il est parfois possible dutiliser 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, 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).

Par ailleurs, certains problèmes continus peuvent parfois être remplacés par un problème discret dont la solution est connue pour approcher celle du problème continu ; ce procédé est appelé discrétisation. Par exemple la solution dune équation différentielle est une fonction. Cette fonction peut être représentée de façon approchée par une quantité finie de données, par exemple par sa valeur en un nombre fini de points de son domaine de définition, même si ce domaine est continu.

Lutilisation de lanalyse numérique est grandement facilitée par les ordinateurs. Laccroissement de la disponibilité et de la puissance des ordinateurs depuis la seconde moitié du XXe siècle a permis lapplication de lanalyse numérique dans de nombreux domaines scientifiques, techniques et économiques, avec souvent des effets révolutionnaires.

La génération et la propagation des erreurs

Létude des erreurs forme une partie importante de lanalyse numérique. Les erreurs introduites dans la solution dun problème ont plusieurs origines. Les erreurs darrondis surviennent car il est impossible de représenter en pratique tous les nombres réels exactement sur une machine à états finis (ce que sont en fin de compte tous les ordinateurs numériques). Les erreurs de troncature sont commises par exemple quand une méthode itérative est terminée et que la solution approchée obtenue diffère de la solution exacte. De façon similaire, la discrétisation (en) dun problème (aussi appelée quantification dans les applications pratiques de calcul numérique) induit une erreur de discrétisation (en) (erreur de quantification dans les applications pratiques) car la solution du problème discret ne coïncide pas exactement avec la solution du problème continu.

Une fois que lerreur est générée, elle se propagera généralement tout au long du calcul. Cela conduit à la notion de stabilité numérique[1] : un algorithme est numériquement stable si une erreur, une fois générée, ne croît pas trop durant le calcul (dans une méthode de calcul itératif, une erreur trop grande peut dans certains cas faire diverger lalgorithme qui ne parviendra pas à approcher la solution). Cela nest possible que si le problème est bien conditionné, ce qui signifie que la solution ne change que d'une faible quantité si les données du problème sont changées d'un montant faible. Ainsi, si un problème est mal conditionné, alors la moindre erreur dans les données provoquera une erreur très importante dans la solution trouvée.

Cependant, un algorithme qui résout un problème bien conditionné peut être ou ne pas être numériquement stable. Tout lart de lanalyse numérique consiste à trouver un algorithme stable pour résoudre un problème mathématique bien posé. Un art apparenté est de trouver des algorithmes stables permettant de résoudre des problèmes mal posés, ce qui requiert généralement la recherche d'un problème bien posé dont la solution est proche du problème mal posé, puis de résoudre à la place ce second problème bien posé.

Domaines détudes

Le champ de lanalyse numérique est divisé en différentes disciplines suivant le type de problème à résoudre, et chaque discipline étudie diverses méthodes de résolution des problèmes correspondants.

Parmi les exemples de méthodes danalyse numérique, en voici quelques-unes utilisées pour discrétiser un système d'équations : la méthode des éléments finis, la méthode des différences finies, la méthode des différences divisées, la méthode des volumes finis

Calcul des valeurs de fonctions

Un des problèmes les plus simples est lévaluation dune fonction à un point donné. Mais même lévaluation dun polynôme approchant nest pas aussi évidente quil y parait : la méthode de Horner est souvent plus efficace que la méthode élémentaire basée sur les coefficients du polynôme développé et la simple somme de ses termes. Généralement, il est important destimer à lavance et de contrôler les erreurs darrondis survenant lors de lutilisation dopérations arithmétiques en virgule flottante.

Interpolation, extrapolation et régression

Linterpolation tente de résoudre ou dapprocher la solution au problème suivant : étant donné la valeur connue d'une certaine fonction en un certain nombre de points, quelle valeur prend cette fonction en un autre point quelconque situé entre deux points donnés ? Une méthode très simple est dutiliser linterpolation linéaire, qui suppose que la fonction inconnue évolue linéairement entre chaque paire de points successifs connus. Cette méthode peut être généralisée en interpolation polynomiale, qui est parfois plus précise (on peut en chiffer la précision si les dérivées de la fonction sont connues jusqu'à l'ordre N pour une interpolation à N points) et nécessite de plus petites tables de valeurs connues, mais elle souffre du phénomène de Runge.

Dautres méthodes dinterpolation utilisent des fonctions localisées telles que les splines ou la compression par ondelettes.

Lextrapolation est très similaire à linterpolation, sauf que cette fois on veut déterminer la valeur dune fonction en un point situé hors de lintervalle des points connus. Dans certains cas (par exemple pour lextrapolation de valeurs de fonctions cycliques, logarithmiques ou exponentielles), il est possible de réduire un problème dextrapolation dans un domaine de définition très étendu voire infini, à un problème dinterpolation dans le sous-espace fini contenant les points connus.

La régression est aussi similaire, mais prend en compte le fait que les données connues sont aussi imprécises. Étant donné certains points, et la mesure de la valeur dune fonction à ces points (avec une erreur maximale estimée), on veut déterminer la fonction inconnue. La méthode des moindres carrés est une façon populaire de procéder.

Résolution déquations et systèmes d'équations

Un autre problème fondamental est le calcul des solutions dune équation donnée. Deux cas sont communément distingués, suivant que léquation est linéaire ou non.

De nombreux efforts ont été consacrés au développement de méthodes de résolution de systèmes déquations linéaires. Les méthodes standards incluent lélimination de Gauss-Jordan, et la décomposition LU. Les méthodes itératives telles que la méthode du gradient conjugué sont généralement préférées sur les larges systèmes déquations.

Les algorithmes de recherche de racines dune fonction sont utilisés pour résoudre les équations non linéaires (elles sont nommées ainsi car la racine dune fonction est un argument pour lequel la fonction retourne zéro). Si la fonction est différentiable et que sa dérivée est connue, alors la méthode de Newton est un choix populaire. La linéarisation est une autre technique pour la résolution déquations non linéaires.

Optimisation

Article détaillé : Optimisation (mathématiques).

Dans les problèmes doptimisation, on recherche un point d'un ensemble auquel une fonction définie sur cet ensemble est minimale (ou maximale). Cet ensemble est souvent défini comme une partie d'un espace vectoriel délimitée par des contraintes, c'est-à-dire par des égalités, des inégalités, des appartenances, définies au moyen d'autres fonctions.

Loptimisation est découpée en sous-disciplines qui se chevauchent, suivant la forme de la fonction objectif et celle des contraintes : l'optimisation en dimension finie ou infinie (on parle ici de la dimension de l'espace vectoriel des variables à optimiser), l'optimisation continue ou combinatoire (les variables à optimiser sont discrètes dans ce dernier cas), l'optimisation différentiable ou non lisse (on qualifie ici la régularité des fonctions définissant le problème), l'optimisation linéaire (fonctions affines), quadratique (objectif quadratique et contraintes affines), semi-définie (en) (la variable à optimiser est une matrice dont on requiert la semi-définie positivité), conique (en) (généralisation du problème précédent), convexe (en) (fonctions convexes), non linéaire, la commande optimale, l'optimisation stochastique (en) et robuste (en) (présence d'aléas), l'optimisation multicritère (un compromis entre plusieurs objectifs contradictoires est recherché), l'optimisation algébrique (fonctions polynomiales), l'optimisation bi-niveaux, l'optimisation sous contraintes de complémentarité, l'optimisation disjonctive (l'ensemble admissible est une réunion d'ensembles), etc. Cette abondance de disciplines provient du fait que pratiquement toute classe de problèmes modélisables peut conduire à un problème d'optimisation, pourvu que l'on y introduise des paramètres à optimiser. Par ailleurs, les conditions d'optimalité de ces problèmes d'optimisation apportent parfois des expressions mathématiques originales qui, par le mécanisme précédent, conduisent à leur tour à de nouveaux problèmes d'optimisation.

L'analyse et la résolution numérique des problèmes d'optimisation différentiable avec contraintes passe souvent par l'écriture de ses conditions d'optimalité. Celles-ci font apparaître des variables cachées (les multiplicateurs ou variables duales) qui ne sont pas présentes dans l'énoncé du problème original, mais qui apportent une information précieuse sur celui-ci (les coûts marginaux). Les multiplicateurs de Lagrange ont fait leur apparition aux XVIIIe siècle pour traiter les problèmes doptimisation avec contraintes d'égalité. Pour les problèmes avec contraintes d'inégalité, ces multiplicateurs ont été mis en évidence au milieu du XXe siècle par de nombreux auteurs, dont Karush, Kuhn et Tucker.

Les problèmes d'optimisation étant très divers par leur nature et leur structure, les méthodes numériques de résolution de ces problèmes sont nombreuses. Beaucoup de problèmes d'optimisation sont NP-difficiles ; c'est déjà le cas pour un problème d'optimisation quadratique non convexe.

Évaluation des intégrales

Article détaillé : Calcul numérique d'une intégrale.

Lintégration numérique, également connue comme quadrature numérique, recherche la valeur dune intégrale définie. Les méthodes populaires sont basées sur les formules de Newton-Cotes (avec par exemple la méthode du point médian ou la méthode des trapèzes) ou utilisent les méthodes de quadrature de Gauss. Cependant si la dimension du domaine dintégration devient large, ces méthodes deviennent aussi prohibitivement onéreuses. Dans cette situation, on peut utiliser une méthode de Monte-Carlo, une méthode de quasi-Monte-Carlo (en) ou, dans des dimensions modestement larges, la méthode des grille incomplète (en).

Équations différentielles

Articles détaillés : Résolution numérique des équations différentielles et Résolution numérique des équations aux dérivées partielles (en)

L'analyse numérique traite également du calcul (de façon approchée) des solutions déquations différentielles, que ce soit des équations différentielles ordinaires, ou des équations aux dérivées partielles.

Les équations aux dérivées partielles sont résolues en discrétisant dabord léquation, en lamenant dans un sous-espace de dimension finie. Ceci peut être réalisé par une méthode des éléments finis, une méthode des différences finies ou, particulièrement dans lingénierie, une méthode des volumes finis. La justification théorique de ces méthodes implique souvent des théorèmes de lanalyse fonctionnelle. Ceci réduit le problème à la résolution dune équation algébrique.

Annexes

Note

  1. (en) N.J. Higham (en), Accuracy and Stability of Numerical Algorithms, Philadelphia, SIAM Publication, 2002 .

Articles connexes

Références

Liens externes



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Analyse numérique de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Analyse Numérique — Simulation numérique d un crash de véhicule 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… …   Wikipédia en Français

  • Analyse numerique — Analyse numérique Simulation numérique d un crash de véhicule 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… …   Wikipédia en Français

  • Analyse numérique — ● Analyse numérique étude des algorithmes utilisés pour la résolution numérique des problèmes mathématiques …   Encyclopédie Universelle

  • analyse numérique — skaitinė analizė statusas T sritis automatika atitikmenys: angl. numerical analysis vok. numerische Analyse, f rus. численный анализ, m pranc. analyse numérique, f …   Automatikos terminų žodynas

  • analyse numérique — skaitinė analizė statusas T sritis fizika atitikmenys: angl. numerical analysis vok. numerische Analyse, f rus. численный анализ, m pranc. analyse numérique, f …   Fizikos terminų žodynas

  • DÉRIVÉES PARTIELLES (ÉQUATIONS AUX) - Analyse numérique — Plus peut être que tout autre domaine des mathématiques, les équations aux dérivés partielles étaient prédisposées à bénéficier de l’utilisation des ordinateurs, pour de nombreuses raisons. La plus importante est leur intervention dans de… …   Encyclopédie Universelle

  • Conditionnement (Analyse Numérique) — Pour les articles homonymes, voir Conditionnement. En général, les données d un problème numérique dépendent de mesures expérimentales et sont donc entachées d erreur. Le conditionnement mesure la dépendance de la solution d un problème numérique …   Wikipédia en Français

  • Conditionnement (analyse numerique) — Conditionnement (analyse numérique) Pour les articles homonymes, voir Conditionnement. En général, les données d un problème numérique dépendent de mesures expérimentales et sont donc entachées d erreur. Le conditionnement mesure la dépendance de …   Wikipédia en Français

  • Conditionnement (analyse numérique) — Pour les articles homonymes, voir Conditionnement. En analyse numérique, une discipline des mathématiques, le conditionnement mesure la dépendance de la solution d un problème numérique par rapport aux données du problème, ceci afin de contrôler… …   Wikipédia en Français

  • Méthode des moments (analyse numérique) — Pour les articles homonymes, voir Méthode des moments. En analyse numérique, la méthode des moments est une méthode de résolution numérique de problèmes linéaires avec conditions aux limites. La méthode consiste à ramener le problème à un… …   Wikipédia en Français

Share the article and excerpts

Direct link
https://fr-academic.com/dic.nsf/frwiki/97107 Do a right-click on the link above
and select “Copy Link”