Introduction
Les algorithmes de calcul numérique sont des méthodes mathématiques utilisées pour résoudre des problèmes complexes ne pouvant pas être calculés exactement, mais qui peuvent être approximés de manière très précise grâce à des calculs itératifs ou des approximations. Ils sont essentiels dans de nombreux domaines scientifiques et techniques pour effectuer des calculs complexes n'ayant pas de solution analytique simple, comme l'intégration, la dérivation, la résolution d'équations différentielles, et l'optimisation. Ils sont essentiels dans de nombreux domaines scientifiques et techniques pour approcher des valeurs avec une précision élevée, notamment en physique, ingénierie, économie, et informatique.
Les opérations de calcul élémentaire - telles que les valeurs absolues, les racines carrées, et les puissances - servent de fondement pour ces algorithmes. Elles forment les briques de base pour des calculs plus avancés en fournissant des résultats simples et rapides pour des valeurs numériques spécifiques. Ces opérations de base sont couramment intégrées dans des calculs numériques car elles sont nécessaires pour définir des distances, des critères d'arrêt, ou encore des puissances dans des séries d'itérations.
Voici les principales catégories d'algorithmes de calcul numérique :
- Calculs élémentaires : Opérations de base essentielles dans les algorithmes numériques. Exemples : valeur absolue, racine carrée, puissance, logarithme, et fonctions trigonométriques de base.
- Résolution d'équations non linéaires : Ces algorithmes permettent de trouver les solutions d'équations sans solution analytique évidente. Exemples : Méthode de Newton-Raphson, méthode de la bissection, méthode des fausses positions.
- Approximation de fonctions : Ces techniques permettent d'approcher une fonction par une autre plus simple, pour simplifier les calculs ou les rendus graphiques. Exemples : Interpolation polynomiale, interpolation de Lagrange, approximation par spline.
- Intégration numérique : Ces méthodes permettent de calculer des intégrales, surtout lorsqu'il n'est pas possible de les résoudre analytiquement. Exemples : Méthode des rectangles, méthode des trapèzes, méthode de Simpson.
- Différentiation numérique : Approximations de la dérivée d'une fonction en utilisant des valeurs discrètes. Exemples : Méthode des différences finies pour calculer des dérivées premières et secondes.
- Résolution d'équations différentielles : Méthodes pour résoudre des équations différentielles ordinaires ou partielles, souvent utilisées en physique et en ingénierie. Exemples : Méthode d'Euler, méthode de Runge-Kutta, méthode des différences finies pour les équations aux dérivées partielles.
- Algorithmes d'optimisation numérique : Techniques pour trouver le maximum ou le minimum de fonctions, utilisées dans de nombreux domaines comme l'économie, l'intelligence artificielle, et les sciences de la décision. Exemples : Méthode du gradient, algorithme de descente de gradient, programmation linéaire, algorithmes génétiques.
- Calcul des valeurs propres et vecteurs propres : Techniques utilisées pour des applications en algèbre linéaire et en traitement du signal, entre autres. Exemples : Méthode de la puissance, méthode QR.
Méthode de Newton-Raphson pour la résolution d'équations
Un exemple d'algorithme de calcul numérique est la méthode de Newton-Raphson pour trouver les racines d'une équation f(x)=0 :
|
* Entrée : Fonction f(x), sa dérivée f'(x), une estimation initiale x0, une tolérance tol * Sortie : Approximation de la racine MODULE ApproximationDeLaRacine BOUCLE RÉPÉTER JUSQU'À ce que la différence soit inférieure à tol FAIRE x1 ← x0 - f(x0) / f'(x0) SI |x1 - x0| < tol ALORS RETOURNE x1 comme la racine SINON Mettre à jour x0 ← x1 FIN SI FIN BOUCLE RÉPÉTER |
ABS (Valeur absolue)
L'algorithme de valeur absolue est l'un des algorithme les plus simples existant. Il permet de retourner une valeur sans son signe, il est ainsi toujours positif.
|
MODULE ABS(valeur) SI valeur < 0 ALORS RETOURNE - valeur SINON RETOURNE valeur FIN SI |
EXP
L'EXP permet d'indiquer la fonction mathématique d'exponentiel, soit l'inverse d'un logarithme, dont voici l'algorithme :
|
MODULE Exposant(x) inverse ← Faux n ← 0 dl ← 1 i ← 1 SI x < 0 ALORS inverse ← vrai x ← - x FIN SI FAIRE TANT QUE x >= 2 x ← x / 2 n ← n + 1 FIN FAIRE TANT QUE x ← x / 16 n ← n + 4 q ← x FAIRE TANT QUE q > 0,000000000000001 dl ← dl + q i ← i + 1 q ← q * x / i FIN FAIRE TANT QUE BOUCLE POUR i ← 1 JUSQU'A n dl ← dl * dl FIN BOUCLE POUR SI inverse ALORS dl ← 1 / dl FIN SI RETOURNE dl |
LOG
Le LOG permet d'indiquer la fonction logarithmique. Voici son algorithme :
|
MODULE LOG(x) negatif ← faux fois ← 1 ajout ← 0 SI x <= 0.0 ALORS RETOURNE 0 FIN SI SI x < 1.0 ALORS negatif ← vrai x ← 1.0 / x FIN SI BOUCLE FAIRE TANT QUE x >= 10.0 x ← x / 10.0 ajout ← ajout + 2.302585092994046 FIN BOUCLE FAIRE TANT QUE BOUCLE FAIRE TANT QUE x >= 1.1 x ← SQRT(x) fois ← fois x 2 FIN BOUCLE FAIRE TANT QUE x ← x - 1 savx ← x i ← 2 xp ← x x x quotient ← (xp / i) dl ← x - quotient BOUCLE FAIRE TANT QUE 1.0E-15 ← quotient i ← i + 1 xp ← xp x x dl ← dl + (xp / i) i ← i + 1 xp ← xp x x quotient ← (xp / i) dl ← dl - quotient FIN BOUCLE FAIRE TANT QUE dl ← dl x fois dl ← dl + ajout SI negatif ALORS dl ← -dl FIN SI RETOURNE dl |
POW (Puissance)
Ce mot permet d'indiquer la fonction de la puissance. Voici son algorithme :
|
MODULE POW(a,b) p ← 1 BOUCLE POUR i ← 1 JUSQU'A b p ← p x a FIN BOUCLE POUR RETOURNE p |
SQRT (Racine carré)
Cette expression permet d'indiquer la fonction de la racine carré. Voici son algorithme :
|
MODULE SQRT(X) SI X = 0.0 ALORS RETOURNE 0.0 SINON M ← 1.0 XN ← X BOUCLE FAIRE TANT QUE XN >= 2.0 XN ← 0.25 x XN M ← 2.0 x M FIN BOUCLE FAIRE TANT QUE BOUCLE FAIRE TANT QUE XN < 0.5 XN ← 4.0 x XN M ← 0.5 x M FIN BOUCLE FAIRE TANT QUE A ← XN B ← 1.0 - XN BOUCLE REPETER A ← A x (1.0 + 0.5 x B) B ← 0.25 x (3.0 + B) x B x B FIN BOUCLE JUSQU'A B ← 1.0E - 15 RETOURNE A x M FIN SI |