ECP 2e Ann´ee 2004-2005 Math´ematiques 2 ´ MATHEMATIQUES 2 Organisation du cours Responsables Daniel Verwaerde et Pascal Laurent ´ Equipe enseignante : Boussad Mammeri (ECP), Victorita Dolean (CMAPX),Olivier Dubois (EDF), Patrick Erhard (EDF), Pascal Joly (Paris VI), Damien Lucas (Computing Objects), Arnaud Picard (EDF), Fabrice Roucayrol (EDF), Jacques-Herv´e Saiac(CNAM), Thu-Sanh Tran (EDF). Contacts Web : www.etudes.ecp.fr/ Bur : Bat. Ens., S 115 Tel : 01 41 13 11 55, Email : [email protected] , [email protected] Secr´etariat : bur. E 106, Tel. 01 41 13 12 61. R´eception des ´etudiants : envoyer un mail. Divisions du cours Le cours est en trois parties, dont le programme est d´etaill´e `a la fin du document : − Optimisation des fonctions continues (5 s´eances). − Analyse et simulation des ´equations aux d´eriv´ees partielles (9 s´eances). − Th´eorie des graphes et optimisation discr`ete (5 s´eances). Organisation des s´ eances Les s´eances peuvent ˆetre compos´ees soit d’un cours en amphith´eatre et de travaux dirig´es en petites classes, soit d’un cours et de travaux dirig´es tous deux en petites classes. Voir l’emploi du temps ci-dessous pour les d´etails. Il faudra s’inscrire en petites classes. Pour les ´el`eves qui le souhaitent quelques s´eances suppl´ementaires seront organis´ees, hors emploi du temps, pour pr´eciser certaines d´efinition ou faire quelques rappels. 2 Math´ematiques 2 Documents Le cours est enti`erement couvert par les documents distribu´es. Les supports de cours sont : − Le polycopi´e “Calcul diff´erentiel et convexit´e : cours et exercices” qui couvre le cours d’optimisation. − Le polycopi´e du cours “Analyse des ´equations aux d´eriv´ees partielles”, qui couvre l’essentiel du cours d’Analyse . − Un polycopi´e “Analyse 2 : Compl´ements de cours et exercices” couvre les autres s´eances. − Un polycopi´e “Graphes et Optimisation discr`ete : Cours et exercices”. − Les corrig´es des exercices, distribu´es apr`es chaque s´eance, sauf pour quelques s´eances dont le contenu est d´ej`a dans les polycopi´es. Contrˆ oles Il y a deux contrˆoles facultatifs (“bureaux d’´etudes”), un travail obligatoire et le contrˆole final. • Les deux bureaux d’´etudes auront une dur´ee de 1 h 30, sans document, la note finale de contrˆole facultatif aura un coefficient 0, 4. Ils sont situ´es `a la fin du cours d’optimisation et `a la fin du cours d’analyse. • Le travail obligatoire (T.O.) est une ´etude `a r´ealiser au CTI sur un logiciel de simulation de ph´enom`enes r´egis par des ´equations aux d´eriv´ees partielles, FEMLAB. Les modalit´es de cette ´etude seront pr´ecis´ees dans un document ult´erieur (inscription fin septembre, travail `a faire entre octobre et janvier). Si ce travail n’est pas rendu cela fera -2 (vous avez bien lu : moins deux !) sur la note finale. • Un contrˆole ´ecrit, une heure sans document, deux heures avec tous documents, avec un coefficient de 0, 6. Objectifs du cours Les objectifs directs du cours Le cours pr´esente quelques principes math´ematiques pour simuler et optimiser des syst`emes complexes. Le domaine d’application du cours d’Analyse 2 est l’ensemble des ph´enom`enes r´egis par des ´equations aux d´eriv´ees partielles (m´ecanique des milieux continus, ´electromagn´etisme, math´ematiques financi`eres...). La deuxi`eme partie du cours d’optimisation est une introduction aux math´ematiques de la gestion (gestion de production, logistique, repr´esentation des connaissances...). Bien sˆ ur, la simulation et l’optimisation de syst`emes complexes se fait aujourd’hui `a l’aide de logiciels. Les principes math´ematiques et les m´ethodes num´eriques que nous ´etudierons ne servent pas seulement `a la conception des logiciels de simulation utilis´es quotidiennement en entreprise, ils sont aussi et surtout n´ecessaires pour mod´eliser correctement les probl`emes `a simuler et pour utiliser ces logiciels. Pr´esentation 3 Le contexte La simulation est un des grands enjeux industriels d’aujourd’hui car elle raccourcit la dur´ee de conception et diminue les coˆ uts d’´etude. Vous avez certainement vu des simulations sur ordinateur du comportement m´ecanique d’une voiture, d’un avion ou d’un ´ecoulement de fluides... Ces simulations sont r´ealis´ees avec des logiciels qui ne sont vraiment pas des jouets `a mettre entre toutes les mains, leur utilisation demande des connaissances approfondies des mod`eles physiques, des m´ethodes de simulation et des comp´etences sur la mod´elisation d’un probl`eme pour permettre sa simulation. La puissance des ordinateurs fait des mod`eles math´ematiques un outil quotidien de l’ing´enieur tandis que les capacit´es de repr´esentations graphiques rendent intuitive l’exploitation de ces mod`eles. Mais il ne faut jamais oublier que cette “r´ealit´e virtuelle” n’est qu’une r´ealisation informatique d’un mod`ele math´ematique qu’il faut maˆıtriser et qui a des limites. Les objectifs indirects du cours La simulation, comme l’optimisation, montre le lien entre les outils formels des math´ematiques ou les principes g´en´eraux de la physique et les applications. Le cours est `a la charni`ere entre la physique ou la gestion, l’informatique et les math´ematiques ; son int´erˆet p´edagogique est d’unifier des connaissances ´eparses. La simulation met en ´evidence l’unit´e profonde de diff´erents domaines scientifiques : souvent le mˆeme mod`ele math´ematique sert dans des probl`emes de gestion, d’´electronique, de calcul de structures ou de dynamique multicorps ; seul change le langage. Ce qui fait ensuite mieux comprendre les sp´ecificit´es de chaque probl`eme et montre comment passer rapidement d’un domaine `a un autre. Emploi du temps Optimisation Les num´eros des s´eances sont ceux figurant dans les polycopi´es. S´eq Jour Date Heure Lieu 1 Mercredi 15 Septembre 8h Cours en AMPHI, exercices en PC. 2 Vendredi 17 Septembre 14 h Cours et exercices en PC. 3 Mardi 21 Septembre 8h Cours et exercices en PC. 4 Vendredi 24 Septembre 8h Cours en AMPHI, exercices en PC. 5 Mercredi 29 Septembre 14 h Cours en AMPHI et B.E. en PC. 4 Math´ematiques 2 Analyse et approximation des ´ equations aux d´ eriv´ ees partielles S´eq Jour Date Heure Lieu 1 Vendredi 1 Octobre 14 h Cours en AMPHI, exercices en PC. 2 Mercredi 6 Octobre 14 h Cours et exercices en PC. 3 Vendredi 8 Octobre 8h Cours en AMPHI, exercices en PC. 4 Mercredi 13 Octobre 14 h Cours et exercices en PC. 5 Vendredi 15 Octobre 8h Cours en AMPHI et exercices en PC. 6 Mercredi 20 Octobre 14 h Cours et exercices en PC. 6² Lundi 8 Novembre 11 h 30 Cours en AMPHI. 7 Mercredi 10 Novembre 14 h Cours et exercices en PC. 9 Lundi 15 Novembre 11 h 30 Cours en AMPHI. 8 Vendredi 19 Novembre 14 h Cours en PC et B.E. en PC. Graphes et optimisation discr` ete S´eq Jour Date Heure Lieu 1 Lundi 22 Novembre 11 h 30 Cours en AMPHI. 1 Mercredi 24 Novembre 11 h 30 Exercices en PC. 2 Mercredi 24 Novembre 14 h Cours et exercices en PC. 3 Mercredi 1 D´ecembre 14 h Cours en AMPHI, exercices en PC. 4 Vendredi 3 D´ecembre 14 h Cours et exercices en AMPHI. 5 Mercredi 8 D´ecembre 14 h Cours et exercices en PC. Pr´esentation 5 Le contrˆole est le mercredi 15 D´ecembre 2004 Programme des s´ eances Les num´eros des s´eances sont ceux figurant dans les polycopi´es. Optimisation 1. Rappel de calcul diff´erentiel. (Amphi + PC) Cours : Diff´erentielle d’une application (dans le contexte des espaces vectoriels norm´es) Diff´erentielle au sens de Gˆateaux d’une fonction, dimension finie et infinie ; gradient, conditions d’optimalit´e. TD : Calcul de diff´erentielles, cas non quadratique, application `a l’´etude de syst`emes non lin´eaires. 2. Convexit´e. (2 PC) Cours : Fonctions convexes, crit`eres de convexit´e, quelques th´eor`emes classiques, exemples. TD : Exemples, application `a l’´etude de syst`eme non lin´eaires, exemples en dimension infinie. 3. L’optimisation locale. (2 PC) Cours : L’optimisation des fonctions convexes. M´ethodes de descente, optimisation 1D, algorithme de gradient et de relaxation.M´ethode de Newton. TD : La m´ethode du gradient, pr´econditionnement. 4. L’optimisation sous contraintes. (Amphi + PC) Cours : Cas C 1 et contraintes d’´egalit´e : multiplicateurs et th´eor`eme de Lagrange ; cas convexe, contrainte lin´eaires. Interpr´etation des multiplicateurs, dualit´e. TD : Exemples “`a la main” en dimension finie et infinie. M´ethodes de dualit´e. M´ethodes de p´enalisation. 5. L’optimisation sous contraintes. (Amphi + PC) Cours : Cas convexe et contraintes d’in´egalit´e : th´eor`eme de Kuhn et Tucker. M´ethodes de d´ecomposition. TD : Bureau d’´etudes (1 h 30). Analyse et approximation des ´ equations aux d´ eriv´ ees partielles 1. Pr´esentation (Amphi + PC) Cours : Pr´esentation du contexte de la simulation. TD : Introduction aux ´el´ements finis sur l’exemple d’un treillis de barres. 2. Probl`emes elliptiques. Premi`ere pr´esentation de la m´ethode des ´el´ements finis. (2 PC) Cours : Le probl`eme de Poisson pour une membrane. Formulations variationnelles. Approximation. TD : Etude du mod`ele num´erique, introduction `a la m´ethode des ´el´ements finis. 3. Programme d’´el´ements finis et logiciel. (Amphi + PC) Cours : Pr´esentation de FEMLAB et de CATIA. TD : Ecriture et ´etude d’un programme d’´el´ements finis. 4. Les formulations variationnelles des probl`emes elliptiques. (2 PC) Cours : Calcul des variations, les probl`emes non lin´eaires, l’´elasticit´e. TD : Exemples classiques. Probl`emes non lin´eaires. 6 Math´ematiques 2 5. Le cadre fonctionnel et les distributions (Amphi + PC) Cours : D´erivation faible, convergence faible, espace de distributions, espace de Sobolev. TD : Application : noyau de Green, s´eries de Fourier, Lax-Milgram. 6. Les probl`emes dynamiques : cas parabolique. (2 PC) Cours : introduction aux probl`emes dynamiques `a partir d’un probl`eme de finance. TD : Approximation de l’´equation de la diffusion, stabilit´e et consistance. 7. Les probl`emes dynamiques hyperboliques. (2 PC) Cours : Equation d’advection, notion de caract´eristique, syst`eme hyperbolique lin´eaire `a coefficients constants. TD : Approximation num´erique, utilisation des caract´eristiques, condition CFL. 8. Les probl`emes de la m´ecanique des fluides. (PC + BE) Cours : Cas hyperbolique non lin´eaire. Les chocs, exemple de l’´equation de Burgers. TD : Bureau d’´etude (1 h 30 ). 9. La mod´elisation de probl`emes complexes. (Amphi) Cours : Les difficult´es et les pi`eges de la mod´elisation math´ematique d’un probl`eme, exemples. Graphes et optimisation discr` ete 1. Introduction `a la th´eorie des graphes et `a l’optimisation discr`ete. (Amphi + PC) Cours : Notions ´el´ementaires sur la th´eorie des graphes, quelques probl`emes classiques. TD : Probl`emes classiques sur les circuits, le coloriage. Num´erotation optimale, graphe planaire. 2. Probl`eme de flot, du voyageur de commerce et d’ordonnancement ( 2 PC) Cours : Les probl`emes de flots et d’affectation, lien avec la programmation lin´eaire, probl`emes classiques d’ordonnancement. TD : Ford Fulkerson, PERT 3. Notion de complexit´e et de probl`emes NP-complets (Amphi + PC) Cours : Th´eorie de la complexit´e des algorithmes, probl`emes polynomiaux, probl`emes NP ; th´eor`eme de Cook. Probl`emes NP-complets. Notion d’heuristiques. TD : Complexit´e de quelques algorithmes, exemples de probl`emes NP-complets. 4. L’optimisation des probl`emes discrets. ( 2 Amphi) Cours : Le contexte de l’optimisation en nombres entiers. TD : Les algorithmes g´en´etiques. 5. La programmation lin´eaire. (2 PC) Cours : Probl`emes se ramenant au probl`eme canonique ; probl`eme dual, algorithme de Dantzig. TD : Exemples, cas particuliers.