Langage C++ et calcul scientifique
16 déc. 2013 Le contenu de ce livre a fait l'objet de cours de troisième année à l'école na- ... par des exercices qui en constituent des développements ...
Le trouble panique avec paniques nocturnes : état des
ÉTAT DES CONNAISSANCES ET EXAMEN DE L'EFFICACITÉ DE DEUX L'AP par définition
Rapport Annuel Annual Report 2014
30 sept. 2016 programme annuel des Cours de l'IHÉS. Ces Cours sont donnés par les professeurs permanents les chercheurs en.
Numéro 71
23 mars 2006 d'un support de cours sur le secteur coopératif comprenant cours et exercices. Il peut être complété par des documents pédagogiques réalisés ...
GROUPE
18 avr. 2016 dants) désignés par le Conseil d'Administration
Interventions psychologiques brèves du trouble panique chez les
12 juil. 2011 Or sans traitement le TP suit généralement un cours ... troubles anxieux les plus courrant (Marchand et Boivin
Etude du trou noir massif central de la Galaxie et de son
15 sept. 2013 devant la commission d'examen composée de : ... AU cours des trois derniers siècles l'idée que le ciel renferme des ... 1966
École doctorale - ED 279 APESA
11 oct. 2021 L'artiste met ici en scène la destruction du Louvre alors en cours d'installation. Cette réflexion sur le passage du temps et la pérennité de ...
Université Bordeaux 2 U.F.R. DES SCIENCES MÉDICALES Année
qui m'ont enseigné l'exercice de la psychiatrie vités en cours et fuient éventuellement la situation dans laquelle ils se trouvent pour chercher.
La valeur référentielle des oeuvres photographiques dAndreas
Gursky Andreas
Langage C++ et calcul scientifique
avec 30 exercices et problèmes corrigés et code C++ en lignePierre Saramito
Copyright (c) 2003-2013 Pierre SaramitoPermission vous est donnée de copier, distribuer et/ou modifier ce documentselon les termes de la licenceGNU Free Documentation License, version 1.3 ou
ultérieure, publiée par la Free Software Foundation, avec le texte de première et quatrième de couverture. Une copie de cette licence figure dans la section Annexes de ce document (texte original en anglais de la licence GNU FDL).À Claire
PréfaceLa simulation numérique est devenue essentielle dans de nombreux domainestels que la mécanique des fluides et des solides, la météo, l"évolution du climat,la biologie ou les semi-conducteurs. Elle permet de comprendre, de prévoir,d"accéder là où les instruments de mesures s"arrêtent.Ce livre présente des méthodes performantes du calcul scientifique : matricescreuses, résolution efficace des grands systèmes linéaires, ainsi que de nom-breuses applications à la résolution par éléments finis et différences finies. Al-ternant algorithmes et applications, les programmes sont directement présentésen langage C++. Ils sont sous forme concise et claire, et utilisent largement lesnotions de classe et de généricité du langage C++.Le contenu de ce livre a fait l"objet de cours de troisième année à l"école na-tionale supérieure d"informatique et de mathématiques appliquées de Grenoble(ENSIMAG) ainsi qu"au mastère de mathématiques appliquées de l"universitéJoseph Fourier. Des connaissances de base d"algèbre matricielle et de program-mation sont recommandées. La maîtrise du contenu de cet ouvrage permet d"ap-préhender les principaux paradigmes de programmation du calcul scientifique.Il est alors possible d"appliquer ces paradigmes pour aborder des problèmesd"intérêt pratique, tels que la résolution des équations aux dérivées partielles,qui est abordée au cours de ce livre. La diversité des sujets abordés, l"efficacitédes algorithmes présentés et leur écriture directe en langage C++ font de cetouvrage un recueil fort utile dans la vie professionnelle d"un ingénieur.Le premier chapitre présente les bases fondamentales pour la suite : présenta-tion du langage C++ à travers la conception d"une classe de quaternions etoutils d"analyse asymptotique du temps de calcul des algorithmes. Le secondchapitre aborde l"algorithme de transformée de Fourier rapide et développedeux applications à la discrétisation d"équations aux dérivées partielles par laméthode des différences finies. Le troisième chapitre est dédié aux matricescreuses et à l"algorithme du gradient conjugué. Ces notions sont appliquées à laméthode des éléments finis. En annexe sont groupés des exemples de générationde maillage et de visualisation graphique.S"il est cependant recommandé de maîtriser les notions du premier chapitrepour aborder le reste du livre, les chapitres deux et trois sont complètementindépendants et peuvent être abordés séparément. Ces chapitres sont complétéspar des exercices qui en constituent des développements, ainsi que des notesbibliographiques retraçant l"historique des travaux et fournissant des référencessur des logiciels et librairies récents implémentant ou étendant les algorithmesprésentés.Les codes C++ présentés au long de ce livre ainsi que dans les exercices sontdisponibles librement à l"adresse
http://www-ljk.imag.fr/membres/Pierre.Saramito/books
sous la licence GNU public licence.RemerciementsJe tiens à remercier chaleureusement plusieurs collègues pour leurs remarquesconstructives qui ont permit d"améliorer le manuscrit. En particulier, mes re-merciements vont vers Christophe Prior (ENSIMAG, Grenoble) et IbrahimCheddadi (Université Pierre et Marie Curie, Paris).
Table des matières
1 Introduction à l"algorithmique numérique en C++1
1.1 Quaternions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Analyse asymptotique des algorithmes. . . . . . . . . . . . . . 12
2 Transformée de Fourier et applications25
2.1 Transformée de Fourier. . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Discrétisation de problèmes aux limites. . . . . . . . . . . . . 32
2.3 Application aux différences finies multi-dimensionnelles. . . . . 47
3 Matrices creuses et méthode des éléments finis61
3.1 Algorithme du gradient conjugué. . . . . . . . . . . . . . . . . 61
3.2 Matrices creuses. . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3 Maillages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.4 Méthode des éléments finis. . . . . . . . . . . . . . . . . . . . 90
A Pré- et post-traitements109
A.1 Ordonnancement et visualisation des matrices creuses. . . . . 109 A.2 Génération et visualisation de maillages. . . . . . . . . . . . . 111 A.3 Visualisation des solutions de type élements finis. . . . . . . . 115B Corrigé des exercices119
C GNU free documentation license137
Bibliographie147
Liste des fichiers d"exemples152
Liste des exercices154
Index155
Chapitre 1Introduction àl"algorithmique numériqueen C++L"objectif de ce premier chapitre est d"introduire, à travers des exemples con-crets, un certain nombre de notions clefs du langage C++ ainsi que de l"analyseasymptotique des algorithmes. Ces notions seront ensuite utilisées tout au longde ce livre.1.1 Quaternions1.1.1 ConceptNous allons présenter, à travers un exemple concret, les notions fondamentalesdu langage C++ qui nous seront utiles par la suite : conception de classe, classeparamétrée par un type, généricité, surcharge d"opérateurs, librairie standard.Nous considérons ici que le lecteur possède déjà quelques rudiments de pro-grammation C++. L"excellent ouvrage de Stroustrup [
55], le concepteur même
de ce langage, pourra être consulté avec profit en ce qui concerne la définition même du langage. Nous nous intéressons à une classe représentant des quater- nions, une extension des nombres complexes. Les quaternions ont été introduits en 1853 par Hamilton. Ils ont plus tard été utilisés en mécanique quantique, et, plus récemment, en animation 3D, pour calculer des rotations d"axes [ 51].Les quaternions sont des nombreshypercomplexesqui forment un groupe non
2Introduction à l"algorithmique numérique en C++Chapitre 1
commutatif. Ils peuvent être représentés à l"aide de matrices complexes2×2: h=?z w -¯w¯z? =?a+ib c+id -c+id a-ib? =aU+bI+cJ+dK avecU=?1 00 1?
,I=?i0 0-i? ,J=?0 1 -1 0? ,K=?0i i0? etI2=J2=K2=-Ugénéralisent les nombres imaginaires purs. Par défini- tion, la norme dehest|h|=? |z|2+|w|2et son conjugué¯h=aU-bI-cJ-dK.1.1.2 Implémentation de la classe
Étudions l"interface de la classecomplexde la librairie standard C++ :template
Section 1.1Quaternions3
affaire auconstructeur par défaut. Lorsque ce même constructeur est appelé avec un seul argument de type flottant, il convertit cette valeur en nombre complexe : nous avons affaire à uneconversion implicite de type. Le deuxième constructeur est leconstructeur de copie: il ne possède qu"un seul argument, de même typecomplexque la classe. L"opérateur d"affectationoperator=prendégalement en argument un nombre complexe.
Passons à l"étude desaccesseurs. Pour chaque accesseurreal()etimag(), le langage C++ permet de spécifier si l"accès est enlecture et écriture, ce qui permet alors de modifier les données de la classe, ou si l"accès est enlecture seule, ce qui ne permet pas de modification des données. L"accès en lecture seule est agrémenté du mot-clefconst, et renvoie une référence constante sur les données :const T&. L"accès en lecture et écriture renvoie une référenceT& sans la restreindre à être constante : ce type d"accès permettra de modifier les donnéesreetimcontenues dans la classe. La classe des nombres complexes de la librairie standard du C++ La classecomplexest complétée par les opérations d"algèbre usuelles+,-,?,/, ainsi queconj(z) qui renvoie le conjuguéabs(z) qui renvoie le module etnorm(z) qui renvoie le carré du module. La librairie fournit également les fonctions mathématiques classiques telles que logarithme, exponentielle, etc. La classe est globalement paramétrée par le typeTqui représente le type à virgule flottante approchant les nombres réels, et utilisé pour les parties réelles et imaginaires. Dans le langage C++, il existe pour cela trois types prédéfi- nis :float,doubleetlong double. Le typefloatest limitée à une préci- sion de six décimales et s"écrit sur quatre octets. Le typedoublepossède une précision de quinze décimales et s"écrit sur huit octets. Le typelong double dépend de la machine et du compilateur : il s"écrit sur douze ou seize octets, et a au moins une précision de quinze décimales. Ainsi, unlong doublepeut représenter une triple ou quadruple précision. Le paramétrage par un typeT nous permet également d"utiliser d"autres classe de nombre à virgule flottante que celles prédéfinies par le langage C++ : de nombreuses librairies C++ pro- posent des nombres à virgule flottante ayant des propriétés très variées. Ainsi, la librairieqdpropose des précisions quadruple et octuple [32] très performantes.
Dans la librairie GNU multi-précisiongmp[
28], la précision des nombres à vir-
gule flottante peut être arbitrairement fixée par l"utilisateur, et un grand nom- bre de décimales deviennent accessibles. Le paramétrage par un type flottant permet de donner un caractèregénériqueà cette classe : il n"est plus nécessaire de la ré-écrire pour chaque nouveau type de nombre à virgule flottante. Abordons à présent l"implémentation de notre classequaternion:4Introduction à l"algorithmique numérique en C++Chapitre 1
quaternion.h#include
template
Section 1.1Quaternions5
Les trois constructeurs présentent une syntaxe très spécifique au langage C++, avec:suivi d"une liste d"initialision des donnéeszcetwcà l"aide des valeurs des arguments. L"opérateur d"affectationoperator=donne également une valeur aux données puis retourne*this, qui est une référence sur le quaternion courant. Écrivons à présent les accesseurs de la classe : quaternion.h(suite)template
template
6Introduction à l"algorithmique numérique en C++Chapitre 1
quaternion.h(suite)template
template
template
Section 1.1Quaternions7
quaternion.h(suite)template
8Introduction à l"algorithmique numérique en C++Chapitre 1
quaternion.h(suite)template
1.1.3 Utilisation de la classe
Écrivons un petit programme qui contrôle les fonctionnalités de notre classe : quaternion_tst.cc#include"quaternion.h"using namespacestd;intmain(intargc,char**argv) {quaternion
Section 1.1Quaternions9
ce qui produit le résultat : h1 = ((1,1), (7,9)) h2 = ((1,-1), (-7,-9)) h1+h2 = ((2,0), (0,0)) h1-h2 = ((0,2), (14,18)) h1*h2 = ((132,0), (0,0)) h1/h2 = ((-0.984848,0.0151515), (0.106061,0.136364)) (h1/h2)*h2 = ((1,1), (7,9)) Par la suite, la compilation sera facilitée par l"utilisation de la commande make, qui utilise le fichier associéMakefilesuivant :Makefile
CXX = c++CXXFLAGS = -O2 -std=c++11
Ceci permet d"entrer une fois pour toute la commande de compilation et ses options. L"option-O2active l"optimisation de code au niveau deux tandis que l"option-std=c++11précise que le langage C++ est celui décrit par la révision de 2011 du standard. Ces options correspondent au compilateur GNU C++ disponible notamment sur le système libre GNU/Linux ainsi que sur la plupart des systèmes propriétaires. Les commandes précédentes deviennent : make quaternion_tst ./quaternion_tst1.1.4 Exercices
Exercice1. (Application aux rotations)
L"objectif de cet exercice est d"utiliser les quaternions pour représenter les rota- tions deR3. Soitpun quaternion décrit parp=a+ib+jc+kd. Introduisons l"applicationCpdes quaternions vers les quaternions, définie pour tout quater- nionrparCp(r) =pr¯p.1) Montrer que, pour deux quaternionspetq, la composition estCp◦Cq=Cpq.
2) L"applicationCps"identifie à une application deR4dansR4. Montrer que
la matrice de cette application est : M p=((((a2+b2+c2+d20 0 0
0a2+b2-c2-d22bc-2ad2bd+ 2ac
0 2bc+ 2ad a2-b2+c2-d22cd-2ab
0 2bd-2ac2cd-2db a2-b2-c2+d2))))
3) Montrer quedet(Mp) =|p|8.
4) On s"intéresse au cas où|p|= 1. La première ligne deMpest(1,0,0,0).
10Introduction à l"algorithmique numérique en C++Chapitre 1
Montrer que la sous-matrice3×3, notée˜Mp, obtenue en enlevant la première ligne et la première colonne est orthogonale et que son déterminant vaut1.5) On s"intéresse à la représentation les rotations par des quaternionspde norme
1via la matriceMp. SoitR=˜Mpla rotation obtenue pour le quaternionp.
Montrer que
˜M-p=Ret que toute rotation a une représentation unique par un quaternion, au signe près.6) Montrer que l"axe de la rotation est le vecteur deR3de coordonnées(b,c,d)
et que l"angle de rotationθautour de cet axe vérifie : cos(θ/2) =aetsin2(θ/2) =b2+c2+d2Exercice2. (Promotion de type)
Nous avons vu que le langage C++ possède trois types à virgule flottante, par ordre de précision croissante :float,doubleetlong double, qui représen- tent respectivement la précision simple, la précision double et une précision supérieure ou égale à la précision double. Ces types peuvent être combinées entre eux dans des expressions lorsqu"il n"y a pas perte de précision : floatx1 = 1.0;doublex2 = 2.0;doublex3 = x1 + x2;1) Considérer l"extrait de code suivant :
quaternion
2) Lapromotion de typedans une expression à virgule flottante est définie par
une relation de la forme : float+double-→double Spécifiez complètement la promotion des types à virgule flottante dans le tableau suivant : +floatdoublelong double float double long doubleSection 1.1Quaternions11
3) La promotion de type entre deux typesT1etT2sera réalisée par
typenamepromoteLa classepromoteest défine par :
structundefined {}; template4) Définir l"opération d"addition généralez1+z2entre deux nombres complexes
z1etz2utilisant des représentations flottantes a priori différentes, de façon à
ce que le code de la question 1 fonctionne.5) De même, définir l"opération d"addition entre deux quaternions utilisant des
type virgule flottante différents.6) Considérons une classe de nombre à virgule flottante définie indépendam-
ment : pour fixer les idées, choisissons la classeqd_real, définie dans la li- brairieqd[32] et qui implémente quatre fois la double précision, soit huit fois
la précision d"unfloat. Citer quelles seraient les modifications supplémentaires à apporter pour que les classescomplexetquaternionpuissent se combiner avec à la fois les types de précisions standards (float,double,long double) et le type défini par qd_real.1.1.5 Notes
Les quaternions ont été introduits en 1853 par Hamilton. Représenter des rota- tions avec des quaternions de norme unité est une astuce ancienne en physique :Shoemake [
51] a été un pionnier pour son utilisation en géométrie algorithmique
12Introduction à l"algorithmique numérique en C++Chapitre 1
pour tracer des courbes en rotation. Ces méthodes sont actuellement massive- ment utilisées, notamment dans la librairieopengl.Il existe une autre application de la rotation
˜Mpintroduite à l"exercice
1: cette
application concerne la transformation de Lorentz en relativité. Pour cela on utilise une extension des quaternions, où le typeTest un nombre complexe : ces quaternions sont appelés quaternions complexes. Le but de cette première section étant de se familiariser au langage C++ et à la généricité par l"exem- ple, nous n"approfondissons pas les applications des quaternions au delà des exercices proposés. Pour aller plus loin avec le langage C++, consillons l"excellent ouvrage deStroustrup [
55], le concepteur même de ce langage. La promotion de type
présentée à l"exercice2est une technique de programmation typique du langage
C++. Elle a été introduite par Veldhuizen [
60] et est actuellement disponible
dans diverses librairies C++ commeblitz++[quotesdbs_dbs18.pdfusesText_24[PDF] : ( dictée : ( 4ème Français
[PDF] : dr Jekyll et mr Hyde 4ème Français
[PDF] : La résistance d’Escherischia coli 1ère SVT
[PDF] :) redaction francais :) 3ème Français
[PDF] :) signification PDF Cours,Exercices ,Examens
[PDF] :/ signification PDF Cours,Exercices ,Examens
[PDF] ==Besoin d'un scan svp !== 3ème Français
[PDF] =Probabilités Terminale Mathématiques
[PDF] ? bicyclette ( second degré ) 1ère Mathématiques
[PDF] ? bientôt en latin PDF Cours,Exercices ,Examens
[PDF] ? Carita 1ère Mathématiques
[PDF] ? celle qui est trop gaie (Les Fleurs du mal , Baudelaire) Terminale Français
[PDF] ? combien x est il est égale 5ème Mathématiques
[PDF] ? completer 6ème Mathématiques