Author | Grégoire Allaire | |

Isbn | 199205221 | |

File size | 6.77MB | |

Year | 2007 | |

Pages | 455 | |

Language | English | |

File format | ||

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 ﬁttings with splines
J.H. Wilkinson: The algebraic eigenvalue problem
I. Duﬀ, A. Erisman, and J. Reid: Direct methods for sparse matrices
M.J. Baines: Moving ﬁnite elements
J.D. Pryce: Numerical solution of Sturm–Liouville problems
K. Burrage: Parallel and sequential methods for ordinary diﬀerential 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- ﬁnite element methods: theory and applications to solid and ﬂuid
mechanics
J.W. Jerome: Modelling and computation for applications in mathematics, science, and
engineering
Alﬁo Quarteroni and Alberto Valli: Domain decomposition methods for partial diﬀerential
equations
G.E. Karniadakis and S.J. Sherwin: Spectral/hp element methods for CFD
I. Babuˇska and T. Strouboulis: The ﬁnite element method and its reliability
B. Mohammadi and O. Pironneau: Applied shape optimization for ﬂuids
S. Succi: The Lattice Boltzmann Equation for ﬂuid dynamics and beyond
P. Monk: Finite element methods for Maxwell’s equations
A. Bellen and M. Zennaro: Numerical methods for delay diﬀerential equations
J. Modersitzki: Numerical methods for image registration
M. Feistauer, J. Felcman, and I. Straˇskraba: Mathematical and computational methods for
compressible ﬂow
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 ﬂuid 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 oﬃces 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 ﬂow 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 ﬁnite diﬀerences . . . . . . . . .
1.4.1 Principles of the method . . . . . . . . . . . . . . .
1.4.2 Numerical results for the heat ﬂow 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 Classiﬁcation of PDEs . . . . . . . . . . . . . . . .
simulation
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
2
9
9
9
11
12
12
13
13
14
14
17
21
25
25
28
2 Finite diﬀerence method
2.1 Introduction . . . . . . . . . . . . . . .
2.2 Finite diﬀerences 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 diﬀerentiation
4.2.1 Some results from integration . . . . . . . . .
4.2.2 Weak diﬀerentiation . . . . . . . . . . . . . .
4.3 Deﬁnition 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 coeﬃcients . . . . . . .
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 ﬁnite elements . . . . . . . . . . .
Convergence and error estimation . . .
P2 ﬁnite elements . . . . . . . . . . . .
Qualitative properties . . . . . . . . .
Hermite ﬁnite elements . . . . . . . .
elements in N ≥ 2 dimensions . . . . .
Triangular ﬁnite elements . . . . . . .
Convergence and error estimation . . .
Rectangular ﬁnite 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 inﬁnite velocity . . . . . . . . . .
8.4.4 Regularity and regularizing eﬀect . . . . . . . . .
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 ﬁnite 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 Deﬁnitions and notation . . . . . . . . .
9.1.4 Optimization in ﬁnite dimensions . . . .
9.2 Existence of a minimum in inﬁnite 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 Diﬀerentiability . . . . . . . . . . . . . . . . . .
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 Deﬁnitions 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, ﬁrst of all, what is applied mathematics? To say that it is mathematics turned
towards applications would be a tautology and a false characterization. In eﬀect, 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 ﬁrst computers
shortly after the Second World War. More than for any other discipline the computer has
been a revolution for mathematics: in eﬀect it has opened up a new ﬁeld, 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 scientiﬁc
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 scientiﬁc disciplines: mathematics, computing, physical sciences, chemistry, mechanics,
biology, economics, and engineering sciences (under this last term we usually group the
diﬀerent ﬁelds of industrial applications such as aeronautics, power generation, ﬁnance, 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 aﬀect to despise applied mathematics).
Paraphrasing the title of a famous ﬁlm, 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 ﬁlms 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 diﬀerential 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 ﬁrst criteria which guarantee the validity and the relevance of numerical
simulations.
The plan of this course is the following. After a ﬁrst 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 ﬁnite diﬀerences. These ﬁrst 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 ﬁnite element method, which is presented
in detail in Chapter 6. The ﬁnite 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
ﬁrst 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 suﬃcient)
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 ﬁnish 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 ﬂavour of an artiﬁcial ‘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 diﬃcult 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 deﬁnitions 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
ﬁgures 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 ﬁnite diﬀerence schemes, as well as the ﬁnite
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 ﬁnite 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 ﬁgures and all of the three-dimensional ﬁgures 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 beneﬁt 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 ﬁrst few years of university. We recognize
that it is diﬃcult 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 diﬀerential equations (or PDEs),
that is, diﬀerential 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 conﬁne 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 ﬂow 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 ﬁnite diﬀerence method. Finally, in the Section 1.5 we give the deﬁnition
of a well-posed problem as well as a (brief) classiﬁcation 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
scientiﬁc 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 ﬂow equation, or the
diﬀusion 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 speciﬁc
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 ﬂux vector. If we apply Gauss’s theorem we obtain
q · n ds =
∂V
divq dx.
V
Gathering together the diﬀerent 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 deﬁned by
divq =
N
∂qi
with q = (q1 , . . . , qN )T .
∂x
i
i=1
We must now link the heat ﬂow to the temperature, by what is called a constitutive
law. In this case, we use Fourier’s law which says that the heat ﬂux 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 deﬁned 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