Numerical Analysis and Optimization: An Introduction to...:Numerical Analysis and Optimization: An Introduction to Mathematical Modelling and Numerical Simulation (Numerical Mathematics and Scientific Computation)
By Gregoire Allaire
Publisher: Oxford University Press, USA
Number Of Pages: 472
Publication Date: 2007-07-19
ISBN-10 / ASIN: 0199205213
ISBN-13 / EAN: 9780199205219
Binding: Hardcover
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.
Contents
1 Introduction ix
1 Introduction to mathematical modelling and numerical simulation 1
1.1 General introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 An example of modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Some classical models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.1 The heat flow equation . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 The wave equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.3 The Laplacian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.4 Schr¨odinger’s equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.5 The Lam′e system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.6 The Stokes system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.7 The plate equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Numerical calculation by finite differences . . . . . . . . . . . . . . . . . . . . 14
1.4.1 Principles of the method . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Numerical results for the heat flow equation . . . . . . . . . . . . . . . 17
1.4.3 Numerical results for the advection equation . . . . . . . . . . . . . . 21
1.5 Remarks on mathematical models . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.5.1 The idea of a well-posed problem . . . . . . . . . . . . . . . . . . . . . 25
1.5.2 Classification of PDEs . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2 Finite difference method 31
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 Finite differences for the heat equation . . . . . . . . . . . . . . . . . . . . . . 32
2.2.1 Various examples of schemes . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.2 Consistency and accuracy . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.3 Stability and Fourier analysis . . . . . . . . . . . . . . . . . . . . . . . 36
2.2.4 Convergence of the schemes . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.5 Multilevel schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2.6 The multidimensional case . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3 Other models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.3.1 Advection equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.3.2 Wave equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
v
vi CONTENTS
3 Variational formulation of elliptic problems 65
3.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.1.2 Classical formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.1.3 The case of a space of one dimension . . . . . . . . . . . . . . . . . . . 67
3.2 Variational approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2.1 Green’s formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2.2 Variational formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.3 Lax–Milgram theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.3.1 Abstract framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.3.2 Application to the Laplacian . . . . . . . . . . . . . . . . . . . . . . . 76
4 Sobolev spaces 79
4.1 Introduction and warning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Square integrable functions and weak differentiation . . . . . . . . . . . . . . 80
4.2.1 Some results from integration . . . . . . . . . . . . . . . . . . . . . . . 80
4.2.2 Weak differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.3 Definition and principal properties . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3.1 The space H1(Ω) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3.2 The space H1
0(Ω) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.3.3 Traces and Green’s formulas . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.4 A compactness result . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.3.5 The spaces Hm(Ω) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.4 Some useful extra results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.4.1 Proof of the density theorem 4.3.5 . . . . . . . . . . . . . . . . . . . . 98
4.4.2 The space H(div) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.4.3 The spaces Wm,p(Ω) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4.4 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.5 Link with distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5 Mathematical study of elliptic problems 109
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.2 Study of the Laplacian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.2.1 Dirichlet boundary conditions . . . . . . . . . . . . . . . . . . . . . . . 109
5.2.2 Neumann boundary conditions . . . . . . . . . . . . . . . . . . . . . . 116
5.2.3 Variable coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.2.4 Qualitative properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.3 Solution of other models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.3.1 System of linear elasticity . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.3.2 Stokes equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6 Finite element method 149
6.1 Variational approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.1.2 General internal approximation . . . . . . . . . . . . . . . . . . . . . . 150
6.1.3 Galerkin method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.1.4 Finite element method (general principles) . . . . . . . . . . . . . . . . 153
6.2 Finite elements in N = 1 dimension . . . . . . . . . . . . . . . . . . . . . . . 154
CONTENTS vii
6.2.1 P1 finite elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.2.2 Convergence and error estimation . . . . . . . . . . . . . . . . . . . . . 159
6.2.3 P2 finite elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.2.4 Qualitative properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.2.5 Hermite finite elements . . . . . . . . . . . . . . . . . . . . . . . . . . 168
6.3 Finite elements in N ≥ 2 dimensions . . . . . . . . . . . . . . . . . . . . . . . 171
6.3.1 Triangular finite elements . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.3.2 Convergence and error estimation . . . . . . . . . . . . . . . . . . . . . 184
6.3.3 Rectangular finite elements . . . . . . . . . . . . . . . . . . . . . . . . 191
6.3.4 Finite elements for the Stokes problem . . . . . . . . . . . . . . . . . . 195
6.3.5 Visualization of the numerical results . . . . . . . . . . . . . . . . . . . 201
7 Eigenvalue problems 205
7.1 Motivation and examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
7.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
7.1.2 Solution of nonstationary problems . . . . . . . . . . . . . . . . . . . . 206
7.2 Spectral theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
7.2.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.2.2 Spectral decomposition of a compact operator . . . . . . . . . . . . . . 210
7.3 Eigenvalues of an elliptic problem . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.3.1 Variational problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.3.2 Eigenvalues of the Laplacian . . . . . . . . . . . . . . . . . . . . . . . 218
7.3.3 Other models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
7.4 Numerical methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
7.4.1 Discretization by finite elements . . . . . . . . . . . . . . . . . . . . . 224
7.4.2 Convergence and error estimates . . . . . . . . . . . . . . . . . . . . . 227
8 Evolution problems 231
8.1 Motivation and examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.1.2 Modelling and examples of parabolic equations . . . . . . . . . . . . . 232
8.1.3 Modelling and examples of hyperbolic equations . . . . . . . . . . . . 233
8.2 Existence and uniqueness in the parabolic case . . . . . . . . . . . . . . . . . 234
8.2.1 Variational formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 234
8.2.2 A general result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
8.2.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
8.3 Existence and uniqueness in the hyperbolic case . . . . . . . . . . . . . . . . . 246
8.3.1 Variational formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.3.2 A general result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
8.4 Qualitative properties in the parabolic case . . . . . . . . . . . . . . . . . . . 253
8.4.1 Asymptotic behaviour . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
8.4.2 The maximum principle . . . . . . . . . . . . . . . . . . . . . . . . . . 255
8.4.3 Propagation at infinite velocity . . . . . . . . . . . . . . . . . . . . . . 256
8.4.4 Regularity and regularizing effect . . . . . . . . . . . . . . . . . . . . . 257
8.4.5 Heat equation in the entire space . . . . . . . . . . . . . . . . . . . . . 259
8.5 Qualitative properties in the hyperbolic case . . . . . . . . . . . . . . . . . . . 261
8.5.1 Reversibility in time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
viii CONTENTS
8.5.2 Asymptotic behaviour and equipartition of energy . . . . . . . . . . . 262
8.5.3 Finite velocity of propagation . . . . . . . . . . . . . . . . . . . . . . . 263
8.6 Numerical methods in the parabolic case . . . . . . . . . . . . . . . . . . . . . 264
8.6.1 Semidiscretization in space . . . . . . . . . . . . . . . . . . . . . . . . 264
8.6.2 Total discretization in space-time . . . . . . . . . . . . . . . . . . . . . 266
8.7 Numerical methods in the hyperbolic case . . . . . . . . . . . . . . . . . . . . 269
8.7.1 Semidiscretization in space . . . . . . . . . . . . . . . . . . . . . . . . 270
8.7.2 Total discretization in space-time . . . . . . . . . . . . . . . . . . . . . 271
9 Introduction to optimization 277
9.1 Motivation and examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
9.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
9.1.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
9.1.3 Definitions and notation . . . . . . . . . . . . . . . . . . . . . . . . . . 284
9.1.4 Optimization in finite dimensions . . . . . . . . . . . . . . . . . . . . . 285
9.2 Existence of a minimum in infinite dimensions . . . . . . . . . . . . . . . . . . 287
9.2.1 Examples of nonexistence . . . . . . . . . . . . . . . . . . . . . . . . . 287
9.2.2 Convex analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
9.2.3 Existence results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
10 Optimality conditions and algorithms 297
10.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
10.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
10.1.2 Differentiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
10.2 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
10.2.1 Euler inequalities and convex constraints . . . . . . . . . . . . . . . . 303
10.2.2 Lagrange multipliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
10.3 Saddle point, Kuhn–Tucker theorem, duality . . . . . . . . . . . . . . . . . . 317
10.3.1 Saddle point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
10.3.2 The Kuhn–Tucker theorem . . . . . . . . . . . . . . . . . . . . . . . . 318
10.3.3 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
10.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
10.4.1 Dual or complementary energy . . . . . . . . . . . . . . . . . . . . . . 323
10.4.2 Optimal command . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
10.4.3 Optimization of distributed systems . . . . . . . . . . . . . . . . . . . 330
10.5 Numerical algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
10.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
10.5.2 Gradient algorithms (case without constraints) . . . . . . . . . . . . . 333
10.5.3 Gradient algorithms (case with constraints) . . . . . . . . . . . . . . . 336
10.5.4 Newton’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
11 Methods of operational research
(Written in collaboration with St′ephane Gaubert) 347
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
11.2 Linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
11.2.1 Definitions and properties . . . . . . . . . . . . . . . . . . . . . . . . . 348
11.2.2 The simplex algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
11.2.3 Interior point algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 357
CONTENTS ix
11.2.4 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
11.3 Integer polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
11.3.1 Extreme points of compact convex sets . . . . . . . . . . . . . . . . . . 362
11.3.2 Totally unimodular matrices . . . . . . . . . . . . . . . . . . . . . . . 364
11.3.3 Flow problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
11.4 Dynamic programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
11.4.1 Bellman’s optimality principle . . . . . . . . . . . . . . . . . . . . . . . 372
11.4.2 Finite horizon problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
11.4.3 Minimum cost path, or optimal stopping, problem . . . . . . . . . . . 375
11.5 Greedy algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
11.5.1 General points about greedy methods . . . . . . . . . . . . . . . . . . 380
11.5.2 Kruskal’s algorithm for the minimum
spanning tree problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
11.6 Separation and relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
11.6.1 Separation and evaluation (branch and bound) . . . . . . . . . . . . . 383
11.6.2 Relaxation of combinatorial problems . . . . . . . . . . . . . . . . . . 388
12 Appendix Review of hilbert spaces 399
13 Appendix Matrix Numerical Analysis 405
13.1 Solution of linear systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
13.1.1 Review of matrix norms . . . . . . . . . . . . . . . . . . . . . . . . . . 406
13.1.2 Conditioning and stability . . . . . . . . . . . . . . . . . . . . . . . . . 409
13.1.3 Direct methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
13.1.4 Iterative methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
13.1.5 The conjugate gradient method . . . . . . . . . . . . . . . . . . . . . . 428
13.2 Calculation of eigenvalues and eigenvectors . . . . . . . . . . . . . . . . . . . 435
13.2.1 The power method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
13.2.2 The Givens–Householder method . . . . . . . . . . . . . . . . . . . . . 438
13.2.3 The Lanczos method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
Index 451
Index notations 455
Numerical Analysis and Optimization (Oxford, 2007)Allaire,.part2
ص
发布重复了，呵呵
[ 本帖最后由 drjiachen 于 2008-12-9 15:42 编辑 ]
Numerical Analysis and Optimization (Oxford, 2007)Allaire,.part1
:11bb :11bb :11bb :11bb :11bb
:30bb:30bb:30bb:30bb:30bb:30bb:30bb
haohaohao!haohaohao!haohaohao
楼主的书价格实惠量又足，买着放心，看着舒心@#￥%……&*
厉害啊[m:01] [m:01] [m:01]
本本都是好书,各个都是精品啊,真是高兴
thanks very much!!!!!!!!!!!!!!!!
好书啊好书:11bb :11bb
好书啊 下来看看哦！！！！！！！！！！！
ccccccccccccccccccccccccccccccccccccccccccccccccc
真想看看呢
感謝樓主分享
積極下載學習中..............
haoshu :11bb :27bb :29bb
楼主每天都共享这么多好书，真是感谢！:31bb :29bb
看看~~
学习一下。。。
:30bb :30bb :30bb
[m:03] [m:03] [m:03] [m:03] [m:03] [m:03]
haohaohao!haohaohao!haohaohao
haohaohao!haohaohao!haohaohao
为什么不能用迅雷下载全部链接了？
一本好书,感射楼主提供!!!!!!!!
:11bb :11bb :11bb
:27bb :27bb :27bb :27bb
感谢楼主分享
:11bb :11bb :11bb :11bb
好书！:11bb :27bb :31bb
:30bb :30bb :30bb :30bb :30bb :30bb :30bb ，向所有发布资料的同志致敬！
好书，多谢楼主的分享，多谢！！！
:19bb :19bb :19bb :19bb
think you very much!
:11bb :11bb :11bb
搂主的书真多！！！感谢分享！！:27bb
，仅限学习交流使用，请勿用于商业用途，如果
谢谢，正需要这本书，找了很久都没找到
:11bb :27bb :29bb :30bb :31bb :27bb :27bb
好资料，想看看，呵呵，谢谢分享！
谢谢楼主的分享。:30bb :30bb
顶顶顶顶顶顶顶顶
强烈支持楼主！
:11bb :30bb
谢谢楼主
:11bb :27bb :29bb :30bb
数值方法的书，好东西啊。谢谢楼主。
:30bb 感謝分享:30bb :30bb :30bb
:11bb :11bb :11bb
:11bb :11bb :11bb :11bb
精品好书，好，好，好。。。。好好
好书，谢谢楼主分享。。。。。。。我为人人，人人为我！！
:30bb:30bb:30bb:30bb:30bb3ks3ks
麽多的好东西，眼花缭乱啊
谢谢。。。。。。。。。。。。
好书，谢谢楼主。:31bb :27bb :29bb :30bb :11bb
收藏了。。。。。。。。
:21bb:22bb：cacakiki16de
谢谢楼主。
期待看看~~~~~~~~
好书一本，多谢
学习学习
谢谢
:16bb 感謝樓主分享
谢谢啊，收了。。。。。。。。。。。
thanks a lot for your share!!!
谢谢你啊 ！！！！！！！！！！！
:13bb:31bb:14bb
好书！ 感谢楼主提供分享！！！！！
好书呀，:31bb:16bb
thank you very much
经典啊谢谢
Thank you for your sharing
多谢了。。。。。。。。。。
看看。。。。。
{:4_196:}:16bb
谢谢，学习下！
谢谢楼主分享
学不完啊！
感谢楼主无私奉献
辛苦了，好东西
下来学习，感谢楼主。
Thank LZ very much. It is a very good book.
謝謝分享
{:7_1234:}
发好书，支持支持
{:7_1234:}
{:7_1234:}勤奋学习
{:7_1234:}{:7_1234:}{:7_1234:}
很好，学习学习！
感謝分享！{:soso_e100:}
非常不错的书啊，谢谢楼主分享！！
好书 谢谢啦 ~
关于优化的一本好书。
下来看看！！谢谢楼主！！
我回复了
学习学习
啥也不说了，楼主就是给力！
当做工具书挺不错
厉害啊[m:01] [m:01] [m:01]
感谢楼主，专门来学习了
谢谢楼主
卫夫人花岗岩环境
明天要猫头鹰吗有没有
Numerical Analysis and Optimization (Oxford, 2007)Allaire,.part1.rar
