Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ABDELKADER BENHARI ABDELKADER BENHARI ABDELKADER BENHARI ABDELKADER BENHARI MET

ABDELKADER BENHARI ABDELKADER BENHARI ABDELKADER BENHARI ABDELKADER BENHARI METHODES NUMERIQUES METHODES NUMERIQUES METHODES NUMERIQUES METHODES NUMERIQUES D’après les historiens, le calcul numérique remonte au moins au troisième millénaire avant notre ère. Il est ` a l’origine favoris´ e par le besoin d’effectuer des mesures dans déférents domaines de la vie courante, notamment en agriculture, commerce, architecture, géographie et navigation ainsi qu’en astronomie. Il semble que les Babyloniens (qui peuplaient l’actuelle Syrie/Iraq) sont parmi les premiers ` a réaliser des calculs algébriques et géométriques alliant complexité et haute précision. Surtout, ils donnent une importance et un sens au placement relatif des chiffes constituant un nombre, c’est-à - dire ` a introduire la notion de base de dénombrement, en l’occurrence, la base sexagésimale que nous avons ﬁni par adopter dans certains domaines. Ils se distinguent ainsi d’autres civilisations, même bien plus récentes, qui développent des méthodes plus lourdes, en introduisant une pléthore de symboles. Il y a environ 3500 ans, les populations de la vallée de l’Indus (régions de l’Inde et du Pakistan) introduisent les notions de zéro et emploient les nombres négatifs. Il adaptent également le système de comptage Babylonien au système décimal qui est le nôtre aujourd’hui. Ces premiers outils de calcul sont largement développé par la suite par les Grecs, puis transmis en Europe par l’intermédiaire des civilisations musulmanes peuplant le bassin méditerranéen. Tables de matières INTRODUCTION ................................................................................................................................. 6 COMPLEXITÉ ...................................................................................................................................... 9 NP-COMPLÉTUDE .......................................................................................................................... 12 PARTIE ENTIÈRE ............................................................................................................................. 14 ALGORITHME D'HÉRON ............................................................................................................... 17 ALGORITHME D'ARCHIMÈDE .................................................................................................... 18 CALCUL DU NOMBRE D'EULER .................................................................................................. 19 CALCUL DE LA FACTORIELLE (FORMULE DE STIRLING) ................................................ 20 SYSTÈMES D'ÉQUATIONS LINÉAIRES ...................................................................................... 21 UNE ÉQUATION À UNE INCONNUE .......................................................................................... 21 DEUX ÉQUATIONS À DEUX INCONNUES ................................................................................ 21 TROIS ÉQUATIONS À TROIS INCONNUES ............................................................................... 22 N ÉQUATIONS À N INCONNUES ................................................................................................ 23 POLYNÔMES ..................................................................................................................................... 24 RÉGRESSIONS ET INTERPOLATIONS ....................................................................................... 27 RÉGRESSION LINÉAIRE À UNE VARIABLE EXPLICATIVE .................................................. 27 DROITE DE RÉGRESSION ........................................................................................................ 28 MÉTHODE DES MOINDRES CARRÉS ..................................................................................... 29 ANALYSE DE LA VARIANCE DE LA RÉGRESSION BIVARIÉE ........................................ 31 RÉGRESSION LINÉAIRE À UNE VARIABLE EXPLICATIVE FORCÉE PAR L'ORIGINE 39 RÉGRESSION LINÉAIRE MULTIPLE .......................................................................................... 40 RÉGRESSION LOGISTIQUE (LOGIT) .......................................................................................... 46 COEFFICIENT DE CORRÉLATION (DÉTERMINATION) GÉNÉRALISÉ ................................ 53 INTERPOLATION POLYNOMIALE ............................................................................................. 54 COURBES DE BÉZIER (SPLINE) .............................................................................................. 54 MÉTHODE D'EULER .................................................................................................................. 59 POLYNÔME DE COLLOCATION ............................................................................................. 60 RECHERCHE DES RACINES ......................................................................................................... 63 MÉTHODE DES PARTIES PROPORTIONNELLES ..................................................................... 64 A.BENHARI 2 MÉTHODE DE LA BISSECTION ................................................................................................... 65 MÉTHODE DE LA SÉCANTE (REGULA FALSI) ........................................................................ 66 MÉTHODE DE NEWTON ............................................................................................................... 67 AIRES ET SOMMES DE RIEMANN ............................................................................................... 71 MÉTHODE DES RECTANGLES .................................................................................................... 71 MÉTHODE DES TRAPÈZES .......................................................................................................... 73 PROGRAMMATION LINÉAIRE .................................................................................................... 73 ALGORITHME DU SIMPLEXE ..................................................................................................... 80 MÉTHODES DE MONTE-CARLO.................................................................................................. 85 GÉNÉRATION DES VARIABLES ALÉATOIRES ........................................................................ 86 CALCUL D'UNE INTÉGRALE ....................................................................................................... 88 CALCUL DE PI ................................................................................................................................ 89 MODÉLISATION ............................................................................................................................. 90 BOOTSTRAPPING ............................................................................................................................ 93 DICHOTOMIE .................................................................................................................................... 98 BIBLIOGRAPHIE .............................................................................................................................. 99 A.BENHARI 3 MÉTHODES NUMÉRIQUES Complexité NP-Complétude Partie entière Algorithme d'Héron Algorithme d'Archimède Calcul du nombre d'Euler Systèmes 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éthodes des moindres carrés Analyse de la variance de la régression bi variée Régression linéaire à une variable explicative forcée par l'origine Régression linéaire multiple Régression logistique Coefficient de corrélation (détermination) généralisé Interpolation polynômiale Courbes de Bézier Méthodes d'Euler Polynôme de collocation Recherche de racines Méthodes 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éthodes de Monte-Carlo Génération de variables aléatoires Calcul d'une intégrale Calcul de Pi Modélisation Bootstrapping Dichotomie Analyse en composantes principales (A.C.P.) Analyse factorielle des correspondances (A.F.C.) A.BENHARI 4 Khi-2 Méthode des différences finies Réseaux de neurones formels Modèle de neurone Fonctions de transfert Architecture de réseau Algorithmes génétiques Codage et population initiale Les opérateurs Opérateur de sélection Opérateur de croisement Opérateur de mutation A.BENHARI 5 INTRODUCTION 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 polynomial). 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 être parfaitement exacts (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 A.BENHARI 6 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 du 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: • 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. • 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. Axiomes de la programmation (anecdotique): A1. Plus nous écrivons de code, plus nous produirons d'erreurs A.BENHARI 7 A2. Il n'existe pas de programmes sans de possibles erreurs (dû 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): M1. Auditer les besoins présents et anticiper les besoins futurs M2. Définir les objectifs 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!) M5. Optimiser la complexité et contrôler les algorithmes M6. Choix d'une stratégie de développement (modulable ou autre) M7. Traduire les algorithmes dans la technologie choisie (ce choix est un sujet assez sensible...) Remarque: Il faudrait dans l'étape (7) respecter les normes de nommage et de représentation du code ainsi que les conventions (traditions) de fréquence d'insertion des commentaires. M8. Tests (maintenance préventive) Remarque: Le débogage (la gestion des erreurs) d'un programme et les tests de fonctionnement doivent prendre autant, voire plus, de temps que le développement du programme lui-même. 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, uploads/Geographie/ methodes-numeriques.pdf