Techniques Algorithmiques pour le Calcul Scientifique (LI364) Cours no1 : Introd

Techniques Algorithmiques pour le Calcul Scientifique (LI364) Cours no1 : Introduction à MATLAB Stef Graillat Université Pierre et Marie Curie (Paris 6) S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 1 / 43 Format du cours Équipe pédagogique : Stef Graillat, Guénaël Renault Évaluation des connaissances un partiel (25%), une note de TD/TME (15%) et un examen final (60%) 12 séances de TME (dont certains seront à rendre) Horaire Cours : le lundi de 9h00 à 10h30 (salle F119) TD : le mardi de 17h45 à 19h30 (salle ? ?) TME : le jeudi de 13h45 à 15h30 (salle ? ?) Site web : http://www-pequan.lip6.fr/~graillat/teach/tacs/index.html S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 2 / 43 Objectifs du cours Objectifs : Concept mathématique : définition mathématique de concepts et de quantités Algorithme : comment calculer efficacement ces quantités sur ordinateur (via l’utilisation de MATLAB et Maple) ? Résolution de problème : utiliser les concepts et les algorithmes pour résoudre des problèmes concrets S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 3 / 43 Plan général du cours Première partie : algorithmique numérique 1 Introduction à Matlab et à l’arithmétique à virgule flottante 2 Introduction à l’optimisation (1/2) 3 Introduction à l’optimisation (2/2) 4 Résolution de systèmes nonlinéaires (méthode de Newton, méthode d’homotopie) 5 Méthodes itératives pour la résolution de systèmes linéaires 6 Transformée de Fourier discrète, application en traitement du signal et en calcul formel S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 4 / 43 Plan général du cours (suite) Deuxième partie : cryptologie 1 Cryptographie romantique et sa cryptanalyse (1/2) 2 Cryptographie romantique et sa cryptanalyse (2/2) 3 Cryptographie moderne : la clé publique et ses applications (1/2) 4 Cryptographie moderne : la clé publique et ses applications (2/2) 5 Courbes elliptiques en cryptologie (1/2) 6 Courbes elliptiques en cryptologie (2/2) S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 5 / 43 Références principales Scientific Computing with Case Studies, Dianne P. O’Leary, SIAM, 2009 Numerical Computing with MATLAB, Cleve Moler, SIAM, 2004 MATLAB Guide, Desmond J. Higham, Nicholas J. Higham, 2nd édition, SIAM, 2005 Solving Problems in Scientific Computing Using Maple and MATLAB, Walter Gander, Jiri Hrebicek, 4e édition, Springer, 2004 Numerical Recipes. The Art of Scientific Computing, William Press, Saul Teukolsky, William Vetterling et Brian Flannery, 3rd Edition, Cambridge University Press, 2007 S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 6 / 43 Champs d’application Les notions vues dans ce cours interviennent dans : la robotique le traitement du signal le traitement d’image la finance la biologie etc. S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 7 / 43 1. Arithmétique à virgule flottante S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 8 / 43 Peut-on compter jusqu’à 6 avec un ordinateur ? 2 −1 1.000000000000000  1 cos(100π + π/4) 2 2.000000000000111 3tan(arctan(10000)) 10000 2.999999999997162     · · · rq · · · √ 4 !2 · · ·   2   2 (20 fois) 4.000000000629434 5 × (1 + e−100) −1) (1 + e−100) −1)  NaN log(e6000) 1000 Inf S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 9 / 43 Nombres à virgule flottante Un nombre flottant normalisé x ∈F est un nombre qui s’écrit sous la forme x = ± x0.x1 . . . xp−1 | {z } mantisse ×be, 0 ≤xi ≤b −1, x0 ̸= 0 b : la base, p : précision, e : exposant vérifiant emin ≤e ≤emax Précision machine ϵ = b1−p, |1+ −1| = ϵ Approximation de R par F, arrondi fl: R →F Soit x ∈R alors fl(x) = x(1 + δ), |δ| ≤u. L’unité d’arrondi u vaut u = ϵ/2 pour l’arrondi au plus près. S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 10 / 43 Modèle standard de l’arithmétique à virgule flottante Norme IEEE 754 (1985) Les opérations arithmétique ops (+, −, ×, /, √) sont effectuées comme si elles était calculées en précision infinie puis arrondies ensuite Par défault : arrondi au plus près Type Taille Mantisse Exposant Unité d’arrondi Intervalle Simple 32 bits 23+1 bits 8 bits u = 2−24 ≈5, 96 × 10−8 ≈10±38 Double 64 bits 52+1 bits 11 bits u = 2−53 ≈1, 11 × 10−16 ≈10±308 Soient x, y ∈F, fl(x ◦y) = (x ◦y)(1 + δ), |δ| ≤u, ◦∈{+, −, ·, /} S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 11 / 43 Exceptions L’arithmétique est “fermée” : chaque opération retourne un résultat. Exception Résultats Invalid operation NaN (Not a Number) Overflow ±∞ Divide by zero ±∞ Underflow Nombres dénormalisés Inexact Résultat arrondi correctement NaN est généré par les opérations telles que 0/0, 0 × ∞, ∞/∞, (+∞) + (−∞) et √−1. Les symbôles infinis vérifient ∞+ ∞= ∞, (−1) × ∞= −∞et (fini)/∞= 0. S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 12 / 43 Précision des calculs À chaque arrondi, on perd a priori un peu de précision, on parle d’erreur d’arrondi. Même si une opération isolée retourne le meilleur résultat possible (l’arrondi du résultat exact), une suite de calculs peut conduire à d’importantes erreurs du fait du cumul des erreurs d’arrondi. Les deux sources principales d’erreur d’arrondis au cours des calculs sont l’élimination et l’absorption. S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 13 / 43 Exemple du phénomène d’élimination Soit f (x) = (1 −cos(x))/x2, alors 0 ≤f (x) < 1/2 pour tout x ̸= 0. Avec x = 1.2 × 10−5, le cosinus arrondi à 10 chiffres significatifs vaut c = 0.9999 9999 99, donc 1 −c = 0.0000 0000 01 Par conséquent (1 −c2)/x2 = 10−10/1.44 × 10−10 = 0.6944 ... ! ! ! ! Pourtant la soustraction 1 −c est exacte. Pour éviter l’élimination, réécrire f sous la forme f (x) = 1 2 sin(x/2) x/2  S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 14 / 43 Exemple du phénomène d’absorption On calcule numériquement, pour de grandes valeurs de N, la somme : N X i=1 1 i Résultats d’un programme C (flottant SP) sur un processeur Pentium4 : ordre N 105 106 107 108 exacte 1.209015e+01 1.439273e+01 1.669531e+01 1.899790e+01 1 →N 1.209085e+01 1.435736e+01 1.540368e+01 1.540368e+01 N →1 1.209015e+01 1.439265e+01 1.668603e+01 1.880792e+01 S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 15 / 43 2. Introduction à MATLAB S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 16 / 43 MATLAB MATLAB = MATrix LABoratory un langage de programmation et un environnement de développement MATLAB a été conçu par Cleve Moler à la fin des années 1970 MATLAB est complété par de multiples boites à outils (toolboxes) le langage MATLAB supporte la POO Interaction possible avec les langages C et Fortran pour l’aide sur une commande command, utiliser help command ou doc command pour écrire des commentaires % Référence : MATLAB Guide, Desmond J. Higham, Nicholas J. Higham, 2nd édition, SIAM, 2005 S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 17 / 43 MATLAB (suite) S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 18 / 43 MATLAB (suite) MATLAB a été créé dans les années 70 par Cleve Moler alors professeur de mathématiques à l’Université du Nouveau-Mexique MATLAB a été crée à partir des bibliothèques Fortran, LINPACK et EISPACK MATLAB a ensuite évolué, en intégrant la bibliothèque LAPACK en 2000 Il y a des alternatives libres à MATLAB telles que GNU Octave, FreeMat et Scilab La version actuelle de MATLAB est MATLAB R2010b (version 7.11) S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 19 / 43 Vecteurs et matrices en MATLAB Les variables de MATLAB sont principalement des vecteurs et des matrices Les vecteurs : - vecteur ligne >> format compact >> x = [1.1 10.1 100.1] x = 1.1000 10.1000 100.1000 - vecteur colonne >> x = [1.1; 10.1; 100.1] x = 1.1000 10.1000 100.1000 S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 20 / 43 Vecteurs en MATLAB (suite) Affichage et affectation >> x = [1.1; 10.1; 100.1]; >> x x = 1.1000 10.1000 100.1000 >> x(3) = -1.1 x = 1.1000 10.1000 -1.1000 Les vecteurs sont indicés à partir de 1 (et pas 0 comme en C) S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 21 / 43 Vecteurs en MATLAB (suite) Transposition d’un vecteur >> x = [1.1 10.1 100.1]’ x = 1.1000 10.1000 100.1000 Pour entrer un vecteur ou une commande occupant plus d’une ligne >> x = [0 .05 .10 .15 .20 .25 .30 .35 .40 .45 .50 ... .55 .60 .65 .70 .75 .80 .85 .90 .95 1]; Longueur d’un vecteur >> length(x) ans = 21 S. Graillat (Univ. Paris 6) TACS (cours n ˚ 1) 22 / 43 Vecteurs en MATLAB (suite) Vecteur de taille quelconque (par défaut les vecteurs sont en ligne) n = 20; h = 1/n; for k=1:n x(k) = k*h; end Initialisation d’un uploads/Management/ cours1-pdf.pdf

Documents similaires

Observatoire des thèses en sciences de gestion 2014 Document rédigé par Christo 0 0

Nour El Yazid BOUCETTA App 15, 06 rue Alain Lesage, 66000 Perpignan 0763 32 03 0 0

1 Université de Laghouat Département d’électrotechnique 3eme année Lic/ELT Cour 0 0

MISSION ORIENTATION EMPLOI Université Paris II Panthéon-Assas, Centre Assas, 92 0 0

1 Please make sure to sign the application at the end of the form / Veuillez-vo 0 0

Session 2018 Examen : Baccalauréat technologique Spécialité : STHR SUJET ÉPREUV 0 0

Let’s be inspired PROGRAMME GRANDE ÉCOLE POST-BAC EN 5 ANS GRADE DE MASTER ACCE 0 0

Université Paris 1 RAPPORT D'ACTIVITES RAPPORT D'ACTIVITES EN ENTREPRISE EN ENT 0 0

Management Development International Institute Etablissement Privé de Formation 0 0

1 2 Plan du Cours d’Initiation 3. Qu’est-ce qu’une BD ? Notion de SGBDR. 4. Mod 0 0

• Détails
• Publié le Mar 29, 2022
• Catégorie Management
• Langue French
• Taille du fichier 0.6442MB