Numerical Analysis and Optimization by Grégoire Allaire


36599fabd53355e-261x361.jpg Author Grégoire Allaire
Isbn 199205221
File size 6.77MB
Year 2007
Pages 455
Language English
File format PDF
Category mathematics


 

NUMERICAL MATHEMATICS AND SCIENTIFIC COMPUTATION Series Editors G.H. GOLUB, A. GREENBAUM ¨ A.M. STUART, E. SULI NUMERICAL MATHEMATICS AND SCIENTIFIC COMPUTATION Books in the series Monographs marked with an asterix (*) appeared in the series ‘Monographs in Numerical Analysis’ which has been folded into, and is continued by, the current series. * * * * * P. Dierckx: Curve and surface fittings with splines J.H. Wilkinson: The algebraic eigenvalue problem I. Duff, A. Erisman, and J. Reid: Direct methods for sparse matrices M.J. Baines: Moving finite elements J.D. Pryce: Numerical solution of Sturm–Liouville problems K. Burrage: Parallel and sequential methods for ordinary differential equations Y. Censor and S.A. Zenios: Parallel optimization: theory, algorithms and applications M. Ainsworth, J. Levesley, W. Light, and M. Marletta: Wavelets, multilevel methods and elliptic PDEs W. Freeden, T. Gervens, and M. Schreiner: Constructive approximation on the sphere: theory and applications to geomathematics C.H. Schwab: p- and hp- finite element methods: theory and applications to solid and fluid mechanics J.W. Jerome: Modelling and computation for applications in mathematics, science, and engineering Alfio Quarteroni and Alberto Valli: Domain decomposition methods for partial differential equations G.E. Karniadakis and S.J. Sherwin: Spectral/hp element methods for CFD I. Babuˇska and T. Strouboulis: The finite element method and its reliability B. Mohammadi and O. Pironneau: Applied shape optimization for fluids S. Succi: The Lattice Boltzmann Equation for fluid dynamics and beyond P. Monk: Finite element methods for Maxwell’s equations A. Bellen and M. Zennaro: Numerical methods for delay differential equations J. Modersitzki: Numerical methods for image registration M. Feistauer, J. Felcman, and I. Straˇskraba: Mathematical and computational methods for compressible flow W. Gautschi: Orthogonal polynomials: computation and approximation M.K. Ng: Iterative methods for Toeplitz systems Michael Metcalf, John Reid, and Malcolm Cohen: Fortran 95/2003 explained George Em Karniadakis and Spencer Sherwin: Spectral/hp element methods for CFD, second edition Dario A. Bini, Guy Latouche, and Beatrice Meini: Numerical methods for structured Markov chains Howard Elman, David Silvester, and Andy Wathen: Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics Moody Chu and Gene Golub: Inverse eigenvalue problems: theory and applications Jean-Fr´ed´eric Gerbeau, Claude Le Bris, and Tony Leli`evre: Mathematical methods for the magnetohydrodynamics of liquid metals Gr´egoire Allaire: Numerical analysis and optimization Numerical Analysis and Optimization An introduction to mathematical modelling and numerical simulation Gr´egoire Allaire ´ Ecole Polytechnique Translated by Dr Alan Craig University of Durham 1 3 Great Clarendon Street, Oxford OX2 6DP Oxford University Press is a department of the University of Oxford. It furthers the University’s objective of excellence in research, scholarship, and education by publishing worldwide in Oxford New York Auckland Cape Town Dar es Salaam Hong Kong Karachi Kuala Lumpur Madrid Melbourne Mexico City Nairobi New Delhi Shanghai Taipei Toronto With offices in Argentina Austria Brazil Chile Czech Republic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore South Korea Switzerland Thailand Turkey Ukraine Vietnam Oxford is a registered trade mark of Oxford University Press in the UK and in certain other countries Published in the United States by Oxford University Press Inc., New York c Gr´  egoire Allaire 2007 The moral rights of the author have been asserted Database right Oxford University Press (maker) First published 2007 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission in writing of Oxford University Press, or as expressly permitted by law, or under terms agreed with the appropriate reprographics rights organization. Enquiries concerning reproduction outside the scope of the above should be sent to the Rights Department, Oxford University Press, at the address above You must not circulate this book in any other binding or cover and you must impose the same condition on any acquirer British Library Cataloguing in Publication Data Data available Library of Congress Cataloging in Publication Data Data available Typeset by Newgen Imaging Systems (P) Ltd., Chennai, India Printed in Great Britain on acid-free paper by Biddles Ltd., King’s Lynn, Norfolk ISBN 978–0–19–920521–9 (Hbk.) ISBN 978–0–19–920522–6 (Pbk.) 1 3 5 7 9 10 8 6 4 2 Contents 1 Introduction ix 1 Introduction to mathematical modelling and numerical 1.1 General introduction . . . . . . . . . . . . . . . . . . . . . 1.2 An example of modelling . . . . . . . . . . . . . . . . . . . 1.3 Some classical models . . . . . . . . . . . . . . . . . . . . 1.3.1 The heat flow equation . . . . . . . . . . . . . . . 1.3.2 The wave equation . . . . . . . . . . . . . . . . . . 1.3.3 The Laplacian . . . . . . . . . . . . . . . . . . . . 1.3.4 Schr¨ odinger’s equation . . . . . . . . . . . . . . . . 1.3.5 The Lam´e system . . . . . . . . . . . . . . . . . . . 1.3.6 The Stokes system . . . . . . . . . . . . . . . . . . 1.3.7 The plate equations . . . . . . . . . . . . . . . . . 1.4 Numerical calculation by finite differences . . . . . . . . . 1.4.1 Principles of the method . . . . . . . . . . . . . . . 1.4.2 Numerical results for the heat flow equation . . . . 1.4.3 Numerical results for the advection equation . . . 1.5 Remarks on mathematical models . . . . . . . . . . . . . . 1.5.1 The idea of a well-posed problem . . . . . . . . . . 1.5.2 Classification of PDEs . . . . . . . . . . . . . . . . simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 9 9 9 11 12 12 13 13 14 14 17 21 25 25 28 2 Finite difference method 2.1 Introduction . . . . . . . . . . . . . . . 2.2 Finite differences for the heat equation 2.2.1 Various examples of schemes . 2.2.2 Consistency and accuracy . . . 2.2.3 Stability and Fourier analysis . 2.2.4 Convergence of the schemes . . 2.2.5 Multilevel schemes . . . . . . . 2.2.6 The multidimensional case . . . 2.3 Other models . . . . . . . . . . . . . . 2.3.1 Advection equation . . . . . . . 2.3.2 Wave equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 31 32 32 35 36 42 44 46 51 51 59 v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENTS vi 3 Variational formulation of elliptic problems 3.1 Generalities . . . . . . . . . . . . . . . . . . . 3.1.1 Introduction . . . . . . . . . . . . . . 3.1.2 Classical formulation . . . . . . . . . . 3.1.3 The case of a space of one dimension . 3.2 Variational approach . . . . . . . . . . . . . . 3.2.1 Green’s formulas . . . . . . . . . . . . 3.2.2 Variational formulation . . . . . . . . 3.3 Lax–Milgram theory . . . . . . . . . . . . . . 3.3.1 Abstract framework . . . . . . . . . . 3.3.2 Application to the Laplacian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 65 65 66 67 68 68 71 73 73 76 4 Sobolev spaces 4.1 Introduction and warning . . . . . . . . . . . . . . . 4.2 Square integrable functions and weak differentiation 4.2.1 Some results from integration . . . . . . . . . 4.2.2 Weak differentiation . . . . . . . . . . . . . . 4.3 Definition and principal properties . . . . . . . . . . 4.3.1 The space H 1 (Ω) . . . . . . . . . . . . . . . . 4.3.2 The space H01 (Ω) . . . . . . . . . . . . . . . . 4.3.3 Traces and Green’s formulas . . . . . . . . . 4.3.4 A compactness result . . . . . . . . . . . . . . 4.3.5 The spaces H m (Ω) . . . . . . . . . . . . . . . 4.4 Some useful extra results . . . . . . . . . . . . . . . . 4.4.1 Proof of the density theorem 4.3.5 . . . . . . 4.4.2 The space H(div) . . . . . . . . . . . . . . . 4.4.3 The spaces W m,p (Ω) . . . . . . . . . . . . . . 4.4.4 Duality . . . . . . . . . . . . . . . . . . . . . 4.5 Link with distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 79 80 80 81 84 84 88 89 94 96 98 98 101 102 103 105 5 Mathematical study of elliptic problems 5.1 Introduction . . . . . . . . . . . . . . . . 5.2 Study of the Laplacian . . . . . . . . . . 5.2.1 Dirichlet boundary conditions . . 5.2.2 Neumann boundary conditions . 5.2.3 Variable coefficients . . . . . . . 5.2.4 Qualitative properties . . . . . . 5.3 Solution of other models . . . . . . . . . 5.3.1 System of linear elasticity . . . . 5.3.2 Stokes equations . . . . . . . . . 6 Finite element method 6.1 Variational approximation . . . . . . . 6.1.1 Introduction . . . . . . . . . . 6.1.2 General internal approximation 6.1.3 Galerkin method . . . . . . . . 6.1.4 Finite element method (general 6.2 Finite elements in N = 1 dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 109 109 109 116 123 126 136 136 144 . . . . . . . . . . . . . . . . . . . . . . . . . . . . principles) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 149 149 150 153 153 154 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENTS P1 finite elements . . . . . . . . . . . Convergence and error estimation . . . P2 finite elements . . . . . . . . . . . . Qualitative properties . . . . . . . . . Hermite finite elements . . . . . . . . elements in N ≥ 2 dimensions . . . . . Triangular finite elements . . . . . . . Convergence and error estimation . . . Rectangular finite elements . . . . . . Finite elements for the Stokes problem Visualization of the numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 159 163 165 168 171 171 184 191 195 201 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 205 205 206 208 209 210 213 213 218 221 224 224 227 8 Evolution problems 8.1 Motivation and examples . . . . . . . . . . . . . . . . . 8.1.1 Introduction . . . . . . . . . . . . . . . . . . . . 8.1.2 Modelling and examples of parabolic equations . 8.1.3 Modelling and examples of hyperbolic equations 8.2 Existence and uniqueness in the parabolic case . . . . . 8.2.1 Variational formulation . . . . . . . . . . . . . . 8.2.2 A general result . . . . . . . . . . . . . . . . . . . 8.2.3 Applications . . . . . . . . . . . . . . . . . . . . 8.3 Existence and uniqueness in the hyperbolic case . . . . . 8.3.1 Variational formulation . . . . . . . . . . . . . . 8.3.2 A general result . . . . . . . . . . . . . . . . . . . 8.3.3 Applications . . . . . . . . . . . . . . . . . . . . 8.4 Qualitative properties in the parabolic case . . . . . . . 8.4.1 Asymptotic behaviour . . . . . . . . . . . . . . . 8.4.2 The maximum principle . . . . . . . . . . . . . . 8.4.3 Propagation at infinite velocity . . . . . . . . . . 8.4.4 Regularity and regularizing effect . . . . . . . . . 8.4.5 Heat equation in the entire space . . . . . . . . . 8.5 Qualitative properties in the hyperbolic case . . . . . . . 8.5.1 Reversibility in time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 231 231 232 233 234 234 236 241 246 246 247 249 253 253 255 256 257 259 261 261 6.3 6.2.1 6.2.2 6.2.3 6.2.4 6.2.5 Finite 6.3.1 6.3.2 6.3.3 6.3.4 6.3.5 vii 7 Eigenvalue problems 7.1 Motivation and examples . . . . . . . . . . 7.1.1 Introduction . . . . . . . . . . . . . 7.1.2 Solution of nonstationary problems . 7.2 Spectral theory . . . . . . . . . . . . . . . . 7.2.1 Generalities . . . . . . . . . . . . . . 7.2.2 Spectral decomposition of a compact 7.3 Eigenvalues of an elliptic problem . . . . . . 7.3.1 Variational problem . . . . . . . . . 7.3.2 Eigenvalues of the Laplacian . . . . 7.3.3 Other models . . . . . . . . . . . . . 7.4 Numerical methods . . . . . . . . . . . . . . 7.4.1 Discretization by finite elements . . 7.4.2 Convergence and error estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENTS viii 8.6 8.7 8.5.2 Asymptotic behaviour and equipartition 8.5.3 Finite velocity of propagation . . . . . . Numerical methods in the parabolic case . . . . 8.6.1 Semidiscretization in space . . . . . . . 8.6.2 Total discretization in space-time . . . . Numerical methods in the hyperbolic case . . . 8.7.1 Semidiscretization in space . . . . . . . 8.7.2 Total discretization in space-time . . . . 9 Introduction to optimization 9.1 Motivation and examples . . . . . . . . . . . . 9.1.1 Introduction . . . . . . . . . . . . . . . 9.1.2 Examples . . . . . . . . . . . . . . . . . 9.1.3 Definitions and notation . . . . . . . . . 9.1.4 Optimization in finite dimensions . . . . 9.2 Existence of a minimum in infinite dimensions . 9.2.1 Examples of nonexistence . . . . . . . . 9.2.2 Convex analysis . . . . . . . . . . . . . . 9.2.3 Existence results . . . . . . . . . . . . . of energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 263 264 264 266 269 270 271 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 277 277 278 284 285 287 287 289 292 10 Optimality conditions and algorithms 10.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . 10.1.1 Introduction . . . . . . . . . . . . . . . . . . . 10.1.2 Differentiability . . . . . . . . . . . . . . . . . . 10.2 Optimality conditions . . . . . . . . . . . . . . . . . . 10.2.1 Euler inequalities and convex constraints . . . 10.2.2 Lagrange multipliers . . . . . . . . . . . . . . . 10.3 Saddle point, Kuhn–Tucker theorem, duality . . . . . 10.3.1 Saddle point . . . . . . . . . . . . . . . . . . . 10.3.2 The Kuhn–Tucker theorem . . . . . . . . . . . 10.3.3 Duality . . . . . . . . . . . . . . . . . . . . . . 10.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . 10.4.1 Dual or complementary energy . . . . . . . . . 10.4.2 Optimal command . . . . . . . . . . . . . . . . 10.4.3 Optimization of distributed systems . . . . . . 10.5 Numerical algorithms . . . . . . . . . . . . . . . . . . 10.5.1 Introduction . . . . . . . . . . . . . . . . . . . 10.5.2 Gradient algorithms (case without constraints) 10.5.3 Gradient algorithms (case with constraints) . . 10.5.4 Newton’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 297 297 298 303 303 306 317 317 318 320 323 323 326 330 332 332 333 336 342 11 Methods of operational research (Written in collaboration with St´ ephane Gaubert) 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.2 Linear programming . . . . . . . . . . . . . . . . . . 11.2.1 Definitions and properties . . . . . . . . . . . 11.2.2 The simplex algorithm . . . . . . . . . . . . . 11.2.3 Interior point algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 347 348 348 353 357 . . . . . . . . . . . . . . . . . . . . . . . CONTENTS ix 11.2.4 Duality . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Integer polyhedra . . . . . . . . . . . . . . . . . . . . . . . 11.3.1 Extreme points of compact convex sets . . . . . . . 11.3.2 Totally unimodular matrices . . . . . . . . . . . . 11.3.3 Flow problems . . . . . . . . . . . . . . . . . . . . 11.4 Dynamic programming . . . . . . . . . . . . . . . . . . . . 11.4.1 Bellman’s optimality principle . . . . . . . . . . . . 11.4.2 Finite horizon problem . . . . . . . . . . . . . . . . 11.4.3 Minimum cost path, or optimal stopping, problem 11.5 Greedy algorithms . . . . . . . . . . . . . . . . . . . . . . 11.5.1 General points about greedy methods . . . . . . . 11.5.2 Kruskal’s algorithm for the minimum spanning tree problem . . . . . . . . . . . . . . . . 11.6 Separation and relaxation . . . . . . . . . . . . . . . . . . 11.6.1 Separation and evaluation (branch and bound) . . 11.6.2 Relaxation of combinatorial problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 361 362 364 368 371 372 372 375 380 380 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 383 383 388 12 Appendix Review of hilbert spaces 13 Appendix Matrix Numerical Analysis 13.1 Solution of linear systems . . . . . . . . . . 13.1.1 Review of matrix norms . . . . . . . 13.1.2 Conditioning and stability . . . . . . 13.1.3 Direct methods . . . . . . . . . . . . 13.1.4 Iterative methods . . . . . . . . . . . 13.1.5 The conjugate gradient method . . . 13.2 Calculation of eigenvalues and eigenvectors 13.2.1 The power method . . . . . . . . . . 13.2.2 The Givens–Householder method . . 13.2.3 The Lanczos method . . . . . . . . . 399 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 405 406 409 411 424 428 435 436 438 442 Index 451 Index notations 455 This page intentionally left blank To the memory of Jacques-Louis LIONS (1928–2001) ´ Professor at the Ecole Polytechnique from 1966 to 1986 This page intentionally left blank Introduction This course treats two essential subjects, among many others, in applied mathematics: numerical analysis and optimization. Before even presenting these two disciplines, let us immediately say that through their teaching the objective of this course is to introduce the reader to the world of mathematical modelling and numerical simulation which have gained considerable importance in these last decades in all areas of science and industrial applications (or engineering science). Mathematical modelling is the art (or the science, depending on the point of view) of representing (or transforming) a physical reality into abstract models which are accessible to analysis and to calculation. Numerical simulation is, of course, the process which allows us to calculate the solutions of these models on a computer, and thus to simulate physical reality. But, first of all, what is applied mathematics? To say that it is mathematics turned towards applications would be a tautology and a false characterization. In effect, throughout time, mathematicians have been inspired by the practical problems that they have tried to solve, however, the emergence of applied mathematics as an independent discipline is relatively recent. In fact, everything changed with the appearance of the first computers shortly after the Second World War. More than for any other discipline the computer has been a revolution for mathematics: in effect it has opened up a new field, that of modelling and simulation. The computer has made mathematics an experimental science (we make ‘numerical experiments’ as others make physical experiments), and the design, as well as the analysis of methods of calculation on a computer, has become a new branch of mathematics: this is numerical simulation. This progress also made it possible for mathematics to attack much more complex and concrete problems, resulting from immediate industrial or scientific motivations, to which we can bring both qualitative and quantitative responses: this is mathematical modelling. We can thus characterize applied mathematics as the mathematics of modelling and numerical simulation. From this point of view, applied mathematics lies at the intersection of many scientific disciplines: mathematics, computing, physical sciences, chemistry, mechanics, biology, economics, and engineering sciences (under this last term we usually group the different fields of industrial applications such as aeronautics, power generation, finance, etc.). The American mathematician Joseph Keller said as a joke that ‘pure mathematics is a branch of applied mathematics’. He wanted to highlight the multidisciplinary character of applied mathematics (but it is not excluded that he also wanted to pay back some ‘pure’ mathematicians who affect to despise applied mathematics). Paraphrasing the title of a famous film, my colleague Pierre-Louis Lions claims that applied mathematics is characterized by three things: Sex, Lies, and Videotapes. Videocassettes are of course the symbols of digital simulation (and of the films that they produce), lies xiii xiv INTRODUCTION correspond to models (not always faithful to reality), and the sex is obviously mathematical analysis (inextinguishable engine of human passions and source of much pleasure). After this (long) detour we can now return to the title of this course. Numerical analysis is thus the discipline which conceives and analyses the methods or algorithms of numerical calculation. In addition optimization is the theory of methods which allow us to improve the operation, output, or the response of a system by maximizing or minimizing associated functions. It is thus an essential tool for modelling. The objectives of this course are to familiarize the reader with the principal models (which are often partial differential equations), their methods of numerical solution and their optimization. Of course, the ambition of this course is to give a foundation which will allow future engineers either in a design department or in research and development to create new models and new numerical algorithms for more complicated problems not discussed here. However, even those not destined for such a career are interested in understanding the fundamentals of numerical simulation. Indeed, many industrial or political decisions will be taken from now on having faith in calculations or numerical simulations. It is thus essential that the decision-makers are capable of judging the quality and of the reliability of the calculations which are presented to them. This course will allow them to understand the first criteria which guarantee the validity and the relevance of numerical simulations. The plan of this course is the following. After a first chapter of introduction to the principal ‘classical’ models and to their numerical solution, Chapter 2 is dedicated to the study of the numerical method of finite differences. These first two chapters allow us to go very quickly to some essential numerical questions which motivate the theoretical developments that follow. Chapters 3, 4, and 5 are dedicated to the theoretical solution by the variational approach of stationary (independent of time) models. They also give the foundation of a very important numerical method, called the finite element method, which is presented in detail in Chapter 6. The finite element method is the basis of many pieces of industrial or academic software. Chapters 7 and 8 discuss the solution of nonstationary problems (or of evolution in time), from both the theoretical and numerical points of view. If the first eight chapters are dedicated to numerical analysis, the last three treat optimization. Chapter 9 presents a series of concrete examples of optimization problems and gives a theory of existence of solutions to these problems. Chapter 10 derives the (necessary or sufficient) conditions for optimality of the solutions. These conditions are important as much from the theoretical as the numerical point of view. They allow us to characterize the optima, and they are the foundation of the numerical algorithms that we describe. Finally, chapter 11 is an introduction to operational research. After having studied linear programming, we give an outline of combinatorial optimization methods (that is to say optimization in discrete variables) which are essential for the optimal planning of resources and tasks in all large companies. Each chapter starts with an introduction which gives the plan and the principal ideas. The length of this course should not worry the reader: the course contains numerous supplementary developments which allow the curious reader ‘to go a little further’ and to make the link with other works or other disciplines. It is, therefore, more a work of reference than the exact transcription of a lecture course. To finish this introduction we give some practical information. As far as possible, this course is intended to be ‘self-contained’ to avoid frequent references to other works. This INTRODUCTION xv is particularly sensible for many results from analysis which here are only useful, but not essential, technical tools. Statement without proof would amount to using them as ‘black boxes’ which gives them the flavour of an artificial ‘recipe’. As far as possible, we have therefore included their proof, but more as information and to ‘demystify’ than for the theoretical interest of the mathematical arguments. In order to distinguish them we use, for all these difficult passages or those of complementary interest, smaller characters like these. The reader should therefore consider these passages in small characters as ‘outside of the programme’. The statements of results or of definitions are in italic characters like these. The exercises are in sans serif characters like these. The end of a proof is indicated by the character 2, while the end of a remark or of an example is indicated by the character •. An index is available at the end of the work. The answers to exercises will be published in French. Most of the computer programs which implement the numerical methods studied, and which have allowed us to produce the figures in this work, are available on the website http://www.cmap.polytechnique.fr/˜allaire/course X annee2.html where the reader can download them freely. The finite difference schemes, as well as the finite element method in one dimension, have been programmed in the language Scilab developed by INRIA and ENPC, available free on the website http://www.scilab.org while the results of the finite element method in two dimensions have been obtained with the help of the program FreeFem++ developed by F. Hecht and O. Pironneau and also available free on the website http://www.freefem.org In addition, most of the two-dimensional figures and all of the three-dimensional figures have been drawn with the help of graphical program xd3d developed by Fran¸cois Jouve at the ´ Ecole Polytechnique and also available free on the website http://www.cmap.polytechnique.fr/˜jouve/xd3d Let us indicate another web address for the curious reader who wants to know more about the history of mathematics or the life of some mathematicians cited in this course http://www-history.mcs.st-and.ac.uk/history The reader who would like to keep up to date with the progress and advances of applied mathematics would benefit to consult the site of the Soci´et´e de Math´ematiques Appliqu´ees et Industrielles http://smai.emath.fr or that of its American colleague, the Society for Industrial and Applied Mathematics http://www.siam.org The level of this course is introductory and it does not need any other prerequisites other than the level of knowledge gained in the first few years of university. We recognize that it is difficult to show much originality in this subject which is already classical in the literature. In particular, our course owes much to its predecessors and particularly to the course by B. Larrouturou, P.-L. Lions, and P.-A. Raviart from which it sometimes borrows heavily. The author thanks all those who have reread parts of the manuscript, particularly Fr´ed´eric Bonnans, Bruno Despr´es and Bertrand Maury. A special mention is due to St´ephane Gaubert, who has co-written chapter 11, and also to Olivier Pantz, who has reread the entire manuscript with great care and who has checked the exercises and written xvi INTRODUCTION the corrections. The author thanks in advance all those who will point out the inevitable errors or imperfections of this edition, for example, by email to the address [email protected] G. Allaire Paris, July 7, 2005 1 Introduction to mathematical modelling and numerical simulation 1.1 General introduction This chapter is an introduction to two distinct, but closely linked, aspects of applied mathematics: mathematical modelling and numerical simulation. A mathematical model is a representation or an abstract interpretation of physical reality that is amenable to analysis and calculation. Numerical simulation allows us to calculate the solutions of these models on a computer, and therefore to simulate physical reality. In this book, the models we shall study will be partial differential equations (or PDEs), that is, differential equations in several variables (time and space, for example). For the moment we shall put aside a third fundamental aspect of applied mathematics, that is, the mathematical analysis of models to which we shall return in a little more depth in later chapters. We need, in some way, to both motivate and justify this necessary intrusion of mathematical analysis. We shall see that the numerical calculation of the solutions of these physical models sometimes has some unpleasant surprises which can only be explained by a sound understanding of their mathematical properties. Once again we recall the fundamental multidisciplinary character of applied mathematics, and therefore of numerical simulation, which combines mathematics, computer science, and engineering. Although most of the problems and applications which motivate applied mathematics are fundamentally nonlinear (see, for example, [12], [27]), we confine ourselves 1 MODELLING AND SIMULATION 2 in this work to linear problems for simplicity. Likewise, we only consider deterministic problems, that is, with no random or stochastic components. Finally, in order for this chapter to be introductory and easily accessible, we shall often be a little imprecise in our mathematical arguments. The more rigorous reader can be reassured that we shall return to the concepts introduced in this way more carefully in the following chapter. The plan of this chapter is the following. Section 1.2 is devoted to an elementary example of modelling which leads to the heat flow equation. Section 1.3 is a quick review of the principal PDEs that we meet in the usual models in mechanics, physics, or engineering sciences. Section 1.4 is an informal introduction to numerical analysis and the finite difference method. Finally, in the Section 1.5 we give the definition of a well-posed problem as well as a (brief) classification of PDEs. 1.2 An example of modelling Modelling represents a considerable part of the work of an applied mathematician and requires a thorough knowledge, not only of applied mathematics, but also of the scientific discipline to which it is applied. In fact, in many cases the mathematical model may not yet be established, or we must select the pertinent one from among several possibilities, or we must simplify known models which are too complex. However, in an introductory presentation of the discipline it is not possible to do justice to this step of the modelling process: we must begin by learning the basic properties of applied mathematics! This is why we limit ourselves to describing the derivation of a well-known classical physical model, and we refer the reader who wishes to know more to more specialised works. The model which we shall describe is known as the heat flow equation, or the diffusion equation. Let us consider a domain Ω in N space dimensions (denoted by RN , with in general N = 1, 2, or 3) which we assume is occupied by a homogeneous, isotropic material which conducts heat. We denote the space variable by x, that is a point of Ω, and the time variable by t. The heat sources in Ω (possibly nonuniform in time and space) are represented by a given function f (x, t), while the temperature is an unknown function θ(x, t). The quantity of the heat is proportional to the temperature θ and is therefore cθ where c is a physical constant (which depends on the material) called the specific heat. To calculate the temperature θ, we write down the law of conservation of energy or of heat. In an elementary volume V contained in Ω, the variation in time of the amount of heat is the balance of that produced by the sources and that which leaves or returns through the element boundaries. In other words, d dt   cθ dx V   f dx − = V q · n ds, (1.1) ∂V where ∂V is the boundary of V (with surface element ds), n is the outward unit AN EXAMPLE OF MODELLING 3 normal from V , and q is the heat flux vector. If we apply Gauss’s theorem we obtain   q · n ds = ∂V divq dx. V Gathering together the different terms in (1.1) and using the fact that the elementary volume V is independent of time, we deduce the energy conservation equation c ∂θ + divq = f ∂t (1.2) which holds at every point x ∈ Ω and for all time t. We recall that the divergence operator is defined by divq = N  ∂qi with q = (q1 , . . . , qN )T . ∂x i i=1 We must now link the heat flow to the temperature, by what is called a constitutive law. In this case, we use Fourier’s law which says that the heat flux is proportional to the temperature gradient q = −k∇θT (1.3) where k is a positive constant (which depends on the material) called the thermal conductivity. Remember that the gradient operator is defined by T  ∂θ ∂θ , ... , . ∇θ = ∂x1 ∂xN By combining the conservation law (1.2) and the constitutive law (1.3), we obtain an equation for the temperature θ ∂θ − k∆θ = f, ∂t where ∆ = div∇ is the Laplacian operator given by c ∆θ = N  ∂2θ . ∂x2i i=1 This equation is valid in the entire domain Ω and we must add another relation, called a boundary condition, which describes what happens at the boundary ∂Ω of the domain, and another relation which describes the initial state of the temperature. By convention, we choose the instant t = 0 to be the initial time, and we impose an initial condition θ(t = 0, x) = θ0 (x), (1.4) where θ0 is the function giving the initial distribution of the temperature in the domain Ω. The type of boundary condition depends on the physical context. If the domain is

Author Grégoire Allaire Isbn 0199205221 File size 6.77MB Year 2007 Pages 455 Language English File format PDF Category Mathematics Book Description: FacebookTwitterGoogle+TumblrDiggMySpaceShare This text, based on the author’s teaching at Ecole Polytechnique, introduces the reader to the world of mathematical modelling and numerical simulation. Covering the finite difference method; variational formulation of elliptic problems; Sobolev spaces; elliptical problems; the finite element method; Eigenvalue problems; evolution problems; optimality conditions and algorithms and methods of operational research, and including a several exercises throughout, this is an ideal text for advanced undergraduate students and graduates in applied mathematics, engineering, computer science, and the physical sciences.     Download (6.77MB) A First Course in Stochastic Models Programming Projects in C for Students of Engineering, Science, and Mathematics Numerical Methods For Viscosity Solutions And Applications Finite Markov Chains and Algorithmic Applications Practical Augmented Lagrangian Methods for Constrained Optimization Load more posts

Leave a Reply

Your email address will not be published. Required fields are marked *