Worldlex Wiki L'analyse numérique est l'étude des algorithmes pour les problèmes des mathématiques continues . Ces algorithmes impliquent des variables réelles ou complexes (contrairement aux mathématiques discrètes ) et utilisent généralement l'approximation numérique en plus de la manipulation symbolique . L'analyse numérique trouve des applications dans tous les domaines de l'ingénierie et des sciences physiques, et, au XXIe siècle, également dans les sciences de la vie et les sciences sociales telles que l'économie, la médecine, le commerce et même les arts. L'augmentation actuelle de la puissance de calcul a permis le recours à des analyses numériques plus complexes, fournissant des modèles mathématiques détaillés et réalistes en sciences et en ingénierie. Parmi les exemples d'analyse numérique, on peut citer : les équations différentielles ordinaires utilisées en mécanique céleste (prédiction des mouvements des planètes, des étoiles et des galaxies), l'algèbre linéaire numérique en analyse de données , ainsi que les équations différentielles stochastiques et les chaînes de Markov pour la simulation des cellules vivantes en médecine et en biologie. Avant l’avènement des ordinateurs modernes, les méthodes numériques s’appuyaient souvent sur des formules d’interpolation manuelles , utilisant des données issues de grandes tables imprimées. Depuis le milieu du XXe siècle, les ordinateurs calculent les fonctions requises, mais bon nombre de ces mêmes formules continuent d’être utilisées dans les algorithmes logiciels. Le point de vue numérique remonte aux premiers écrits mathématiques. Une tablette de la collection babylonienne de Yale ( YBC 7289 ) donne une approximation numérique sexagésimale de la racine carrée de 2 , la longueur de la diagonale dans un carré unitaire . L'analyse numérique s'inscrit dans cette longue tradition : plutôt que de donner des réponses symboliques exactes traduites en chiffres et applicables uniquement aux mesures du monde réel, on utilise des solutions approximatives dans des limites d'erreur spécifiées.
Histoire
Le domaine de l'analyse numérique est antérieur de plusieurs siècles à l'invention des ordinateurs modernes. L'interpolation linéaire était déjà utilisée il y a plus de 2000 ans. De nombreux mathématiciens de renom du passé se sont intéressés à l'analyse numérique , comme en témoignent les noms d'algorithmes importants tels que la méthode de Newton , le polynôme d'interpolation de Lagrange , l'élimination de Gauss ou la méthode d'Euler . Les origines de l'analyse numérique moderne sont souvent associées à un article de 1947 de John von Neumann et Herman Goldstine [ mais d'autres font remonter ses origines aux travaux d' E.T. Whittaker en 1912
Pour faciliter les calculs manuels, de volumineux ouvrages ont été produits, contenant des formules et des tables de données telles que les points d'interpolation et les coefficients des fonctions. Grâce à ces tables, souvent calculées avec une précision de 16 décimales, voire plus pour certaines fonctions, on pouvait trouver des valeurs à insérer dans les formules et obtenir ainsi d'excellentes estimations numériques de certaines fonctions. L'ouvrage de référence dans ce domaine est la publication du NIST éditée par Abramowitz et Stegun , un livre de plus de 1 000 pages recensant un très grand nombre de formules et de fonctions couramment utilisées, ainsi que leurs valeurs en de nombreux points. Si les valeurs des fonctions sont aujourd'hui moins utiles avec l'avènement des ordinateurs, la liste exhaustive des formules reste très précieuse.
La calculatrice mécanique a également été développée comme outil de calcul manuel. Ces calculatrices ont évolué vers les ordinateurs électroniques dans les années 1940, et l'on a alors constaté que ces derniers étaient également utiles à des fins administratives. L'invention de l'ordinateur a aussi influencé le domaine de l'analyse numérique , car elle a permis d'effectuer des calculs plus longs et plus complexes.
Le prix Leslie Fox d'analyse numérique a été créé en 1985 par l' Institut de mathématiques et de ses applications .
Concepts clés
Méthodes directes et itératives
Les méthodes directes calculent la solution d'un problème en un nombre fini d'étapes. Ces méthodes donneraient la solution exacte si elles étaient appliquées avec une précision infinie . On peut citer comme exemples l'élimination de Gauss , la factorisation QR pour la résolution de systèmes d'équations linéaires et la méthode du simplexe en programmation linéaire . En pratique, on utilise une précision finie et le résultat est une approximation de la solution exacte (sous l'hypothèse de stabilité ).
Contrairement aux méthodes directes, les méthodes itératives ne sont pas censées se terminer en un nombre fini d'étapes, même si une précision infinie était possible. À partir d'une estimation initiale, les méthodes itératives forment des approximations successives qui convergent vers la solution exacte seulement à la limite. Un test de convergence, souvent basé sur le résidu , est spécifié afin de déterminer quand une solution suffisamment précise a (idéalement) été trouvée. Même en utilisant une arithmétique de précision infinie, ces méthodes n'atteindraient pas la solution en un nombre fini d'étapes (en général). On peut citer comme exemples la méthode de Newton, la méthode de dichotomie et l'itération de Jacobi . En algèbre matricielle numérique, les méthodes itératives sont généralement nécessaires pour les problèmes de grande taille.
En analyse numérique, les méthodes itératives sont plus courantes que les méthodes directes. Certaines méthodes sont directes en principe, mais sont généralement utilisées comme si elles ne l'étaient pas, par exemple la méthode GMRES et la méthode du gradient conjugué . Pour ces méthodes, le nombre d'itérations nécessaires pour obtenir la solution exacte est si important qu'une approximation est acceptée, de la même manière que pour une méthode itérative.
Prenons comme exemple le problème de la résolution
- 3 x 3 + 4 = 28
pour la quantité inconnue x .
| 3 x 3 + 4 = 28. | |
| Soustraire 4 | 3 x 3 = 24. |
| Diviser par 3 | x 3 = 8. |
| Prenez les racines cubiques | x = 2. |
Pour la méthode itérative, appliquez la méthode de bissection à f ( x ) = 3 x 3 − 24. Les valeurs initiales sont a = 0, b = 3, f ( a ) = − 24, f ( b ) = 57.
| un | b | milieu | f (milieu) |
|---|---|---|---|
| 0 | 3 | 1.5 | − 13,875 |
| 1.5 | 3 | 2,25 | 10.17... |
| 1.5 | 2,25 | 1,875 | − 4,22... |
| 1,875 | 2,25 | 2,0625 | 2,32... |
Ce tableau permet de conclure que la solution se situe entre 1,875 et 2,0625. L'algorithme peut renvoyer n'importe quel nombre dans cet intervalle avec une erreur inférieure à 0,2.
Conditionnement
Problème mal conditionné : Soit la fonction discrétisation ». Par exemple, la solution d’une équation différentielle est une fonction . Cette fonction doit être représentée par un nombre fini de données, par exemple par sa valeur en un nombre fini de points de son domaine, même si ce domaine est un milieu continu .
Génération et propagation des erreurs
Erreur de troncature et de discrétisation
Des erreurs de troncature surviennent lorsqu'une méthode itérative est interrompue ou qu'une procédure mathématique est approchée et que la solution approchée diffère de la solution exacte. De même, la discrétisation induit une erreur de discrétisation car la solution du problème discret ne coïncide pas avec celle du problème continu. Dans l'exemple ci-dessus, pour calculer la solution de l'équation , après dix itérations, la racine calculée est d'environ 1,99. Par conséquent, l'erreur de troncature est d'environ 0,01.
Une fois qu'une erreur est générée, elle se propage tout au long du calcul. Par exemple, l'opération + sur un ordinateur est imprécise. Un calcul du type l'est encore plus.
Une erreur de troncature se produit lorsqu'une procédure mathématique est approchée. Pour intégrer une fonction exactement, il faudrait déterminer une infinité de régions, mais numériquement, seule une somme finie de régions est accessible, d'où l'approximation de la solution exacte. De même, pour dériver une fonction, l'élément différentiel tend vers zéro, mais numériquement, seule une valeur non nulle de cet élément peut être choisie.
Stabilité numérique et problèmes bien posés
Un algorithme est dit numériquement stable si une erreur, quelle qu'en soit la cause, ne s'amplifie pas significativement au cours du calcul. Cela se produit lorsque le problème est bien conditionné , c'est-à-dire lorsque la solution ne varie que légèrement si les données du problème sont légèrement modifiées. À l'inverse, si un problème est mal conditionné, la moindre erreur dans les données se transformera en une erreur importante. Le problème initial et l'algorithme utilisé pour le résoudre peuvent être bien ou mal conditionnés, et toute combinaison est possible. Ainsi, un algorithme qui résout un problème bien conditionné peut être numériquement stable ou instable. L'un des aspects fondamentaux de l'analyse numérique est de trouver un algorithme stable pour résoudre un problème mathématique bien posé.
Domaines d'études
Le domaine de l'analyse numérique comprend de nombreuses sous-disciplines. Voici quelques-unes des principales :
Calcul des valeurs des fonctions
Interpolation : Constatant que la température varie de 20 degrés Celsius à 13h00 à 14 degrés à 15h00, une interpolation linéaire de ces données permettrait de conclure qu'elle était de 17 degrés à 14h00 et de 18,5 degrés à 13h30. Extrapolation : Si le produit intérieur brut d’un pays a progressé en moyenne de 5 % par an et s’élevait à 100 milliards l’an dernier, on peut extrapoler qu’il atteindra 105 milliards cette année.  Régression : En régression linéaire, étant donné n points, on calcule une droite qui passe au plus près de ces n points.  Optimisation : Supposons qu’un stand de limonade vende 1,00 $ le verre, que 197 verres de limonade puissent être vendus par jour et que chaque augmentation de 0,01 $ entraîne la vente d’un verre de moins par jour. Si le prix pouvait être fixé à 1,485 $, le profit serait maximal. Cependant, la contrainte d’un prix au centime près fait que les prix de 1,48 $ et 1,49 $ par verre permettent tous deux d’obtenir le revenu maximal de 220,52 $ par jour.  Équation différentielle : Si 100 ventilateurs sont installés pour souffler de l’air d’un bout à l’autre d’une pièce, et qu’une plume est lâchée dans le vent, que se passe-t-il ? La plume suivra les courants d’air, dont la trajectoire peut être très complexe. Une approximation consiste à mesurer la vitesse du vent à proximité de la plume chaque seconde, puis à faire avancer la plume simulée comme si elle se déplaçait en ligne droite à cette même vitesse pendant une seconde, avant de mesurer à nouveau la vitesse du vent. C’est ce qu’on appelle la méthode d’Euler pour résoudre une équation différentielle ordinaire. |
L'un des problèmes les plus simples est l'évaluation d'une fonction en un point donné. L'approche la plus directe, qui consiste à insérer directement le nombre dans la formule, est parfois peu efficace. Pour les polynômes, il est préférable d'utiliser le schéma de Horner , car il réduit le nombre de multiplications et d'additions nécessaires. De manière générale, il est important d'estimer et de contrôler les erreurs d'arrondi dues à l'utilisation de l'arithmétique à virgule flottante .
Interpolation, extrapolation et régression
L'interpolation résout le problème suivant : étant donné la valeur d'une fonction inconnue en un certain nombre de points, quelle est la valeur de cette fonction en un autre point situé entre les points donnés ?
L'extrapolation est très similaire à l'interpolation, sauf que dans ce cas, il faut trouver la valeur de la fonction inconnue en un point situé en dehors des points donnés.
La régression est similaire, mais elle tient compte de l'imprécision des données. À partir de points et de mesures de la valeur d'une fonction en ces points (avec une marge d'erreur), on peut déterminer la fonction inconnue. La méthode des moindres carrés est une méthode permettant d'y parvenir.
Résolution d'équations et de systèmes d'équations
Un autre problème fondamental consiste à calculer la solution d'une équation donnée. On distingue généralement deux cas, selon que l'équation est linéaire ou non. Par exemple, l'équation est linéaire tandis que ne l'est pas.
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 directes classiques, c'est-à-dire celles qui utilisent une décomposition matricielle , comprennent l'élimination de Gauss , la décomposition LU , la décomposition de Cholesky pour les matrices symétriques (ou hermitiennes ) et définies positives , et la décomposition QR pour les matrices non carrées. Les méthodes itératives telles que la méthode de Jacobi , la méthode de Gauss-Seidel , la surrelaxation successive et la méthode du gradient conjugué sont généralement privilégiées pour les grands systèmes. Des méthodes itératives générales peuvent être développées à l'aide d'une décomposition matricielle .
Les algorithmes de recherche de racines servent à résoudre les équations non linéaires (ils sont ainsi nommés car une racine d'une fonction est un argument pour lequel la fonction s'annule). Si la fonction est dérivable et que sa dérivée est connue, la méthode de Newton est couramment utilisée. La linéarisation est une autre technique de résolution des équations non linéaires.
Résolution de problèmes de valeurs propres ou de valeurs singulières
Plusieurs problèmes importants peuvent être formulés en termes de décomposition en valeurs propres ou de décomposition en valeurs singulières . Par exemple, l' algorithme de compression spectrale d'images repose sur la décomposition en valeurs singulières. L'outil statistique correspondant est l'analyse en composantes principales .
Optimisation
Le domaine de l'optimisation se subdivise en plusieurs sous-domaines, selon la forme de la fonction objectif et des contraintes. Par exemple, la programmation linéaire traite le cas où la fonction objectif et les contraintes sont linéaires. Une méthode célèbre en programmation linéaire est la méthode du simplexe .
La méthode des multiplicateurs de Lagrange peut être utilisée pour réduire les problèmes d'optimisation avec contraintes à des problèmes d'optimisation sans contraintes.
Évaluation des intégrales
Équations différentielles
La résolution des équations aux dérivées partielles commence par leur discrétisation, les ramenant à un sous-espace de dimension finie. Cette discrétisation peut être réalisée par la méthode des éléments finis , par la méthode des différences finies , ou (particulièrement en ingénierie) par la méthode des volumes finis . La justification théorique de ces méthodes repose souvent sur des théorèmes d' analyse fonctionnelle . Le problème se ramène ainsi à la résolution d'une équation algébrique.
Logiciel
Au fil des ans, la Royal Statistical Society a publié de nombreux algorithmes dans sa revue Applied Statistics (le code de ces fonctions « AS » est disponible ici ) ; l’ACM a fait de même dans sa revue Transactions on Mathematical Software (le code de « TOMS » est disponible ici ). Le Naval Surface Warfare Center a publié à plusieurs reprises sa bibliothèque de sous-programmes mathématiques (le code est disponible ici ).
Il existe plusieurs applications de calcul numérique populaires telles que MATLAB [ TK Solver , S-PLUS et IDL , ainsi que des alternatives libres et open source comme FreeMat , Scilab [ GNU Octave (similaire à MATLAB) et IT++ (une bibliothèque C++). On trouve également des langages de programmation comme R (similaire à S-PLUS), Julia [ et Python avec des bibliothèques telles que NumPy , SciPy et SymPy . Les performances varient considérablement : si les opérations vectorielles et matricielles sont généralement rapides, la vitesse des boucles scalaires peut varier de plus d’un ordre de grandeur
De nombreux systèmes de calcul formel, tels que Mathematica, bénéficient également de la disponibilité de l'arithmétique à précision arbitraire, qui peut fournir des résultats plus précis.
De plus, tout tableur peut être utilisé pour résoudre des problèmes simples d'analyse numérique. Excel , par exemple, propose des centaines de fonctions , notamment pour les matrices, qui peuvent être utilisées avec son solveur intégré .