Introduction to numerical methods for variational problems

Preface......Page 7
Second Preface......Page 11
Contents......Page 13
List of Exercises and Problems......Page 14
1 Quick Overview of the Finite Element Method......Page 16
2 Function Approximation by Global Functions......Page 22
  2.1.1 Approximation of Planar Vectors......Page 23
  2.1.2 Approximation of General Vectors......Page 27
 2.2 Approximation Principles......Page 30
  2.2.1 The Least Squares Method......Page 31
  2.2.3 Example of Linear Approximation......Page 32
  2.2.4 Implementation of the Least Squares Method......Page 34
  2.2.5 Perfect Approximation......Page 37
  2.2.6 The Regression Method......Page 38
  2.3.1 Ill-Conditioning......Page 43
  2.3.2 Fourier Series......Page 46
  2.3.3 Orthogonal Basis Functions......Page 47
  2.3.4 Numerical Computations......Page 49
  2.4.1 The Interpolation (or Collocation) Principle......Page 51
  2.4.2 Lagrange Polynomials......Page 54
  2.4.3 Bernstein Polynomials......Page 61
 2.5 Approximation Properties and Convergence Rates......Page 63
  2.6.1 2D Basis Functions as Tensor Products of 1D Functions......Page 70
  2.6.2 Example on Polynomial Basis in 2D......Page 72
  2.6.3 Implementation......Page 76
  2.6.4 Extension to 3D......Page 77
  Problem 2.1: Linear Algebra Refresher......Page 78
  Problem 2.3: Approximate a Parabola by a Sine......Page 79
  Problem 2.5: Approximate the Sine Function by Power Functions......Page 80
  Problem 2.7: Approximate a Steep Function by Sines with Boundary Adjustment......Page 81
  Exercise 2.8: Fourier Series as a Least Squares Approximation......Page 82
  Problem 2.10: Approximate a Steep Function by Lagrange Polynomials and Regression......Page 83
 3.1 Finite Element Basis Functions......Page 84
  3.1.1 Elements and Nodes......Page 85
  3.1.2 The Basis Functions......Page 88
  3.1.3 Example on Quadratic Finite Element Functions......Page 89
  3.1.4 Example on Linear Finite Element Functions......Page 91
  3.1.5 Example on Cubic Finite Element Functions......Page 92
  3.1.6 Calculating the Linear System......Page 93
  3.1.7 Assembly of Elementwise Computations......Page 95
  3.1.8 Mapping to a Reference Element......Page 99
  3.1.9 Example on Integration over a Reference Element......Page 101
  3.2.1 Integration......Page 103
  3.2.2 Linear System Assembly and Solution......Page 106
  3.2.4 Using Interpolation Instead of Least Squares......Page 107
  3.2.5 Example on Computing Numerical Approximations......Page 108
  3.2.6 The Structure of the Coefficient Matrix......Page 109
  3.2.7 Applications......Page 111
  3.2.8 Sparse Matrix Storage and Solution......Page 112
  3.3.1 Finite Difference Approximation of Given Functions......Page 114
  3.3.2 Interpretation of a Finite Element Approximation in Terms of Finite Difference Operators......Page 115
  3.3.3 Making Finite Elements Behave as Finite Differences......Page 117
  3.4.2 Extended Finite Element Concept......Page 119
  3.4.3 Implementation......Page 121
  3.4.4 Computing the Error of the Approximation......Page 123
  3.4.5 Example on Cubic Hermite Polynomials......Page 124
 3.5 Numerical Integration......Page 125
  3.5.2 Gauss-Legendre Rules with Optimized Points......Page 126
 3.6 Finite Elements in 2D and 3D......Page 127
  3.6.1 Basis Functions over Triangles in the Physical Domain......Page 128
  3.6.2 Basis Functions over Triangles in the Reference Cell......Page 129
  3.6.4 Isoparametric Mapping of the Reference Cell......Page 132
  3.6.5 Computing Integrals......Page 133
  3.7.1 Example of Approximation in 2D Using FEniCS......Page 134
  3.7.2 Refined Code with Curve Plotting......Page 136
  Problem 3.2: Define Vertices, Cells, and dof Maps......Page 139
  Problem 3.6: Approximate a Steep Function by P3 and P4 Elements......Page 140
  Exercise 3.7: Investigate the Approximation Error in Finite Elements......Page 141
  Exercise 3.9: 2D Approximation with Orthogonal Functions......Page 142
  Exercise 3.11: Compare P1 Elements and Interpolation......Page 143
  Exercise 3.14: Make a 3D Code for Lagrange Elements of Arbitrary Order......Page 144
 4.1 Basic Principles for Approximating Differential Equations......Page 145
  4.1.1 Differential Equation Models......Page 146
  4.1.2 Simple Model Problems and Their Solutions......Page 147
  4.1.3 Forming the Residual......Page 149
  4.1.4 The Least Squares Method......Page 150
  4.1.6 The Method of Weighted Residuals......Page 151
  4.1.7 The Method of Weighted Residual and the Truncation Error......Page 152
  4.1.9 The Collocation Method......Page 153
  4.1.10 Examples on Using the Principles......Page 155
  4.1.11 Integration by Parts......Page 159
  4.1.12 Boundary Function......Page 160
  4.2.1 Computing with Dirichlet and Neumann Conditions......Page 162
  4.2.3 Abstract Notation for Variational Formulations......Page 165
  4.2.4 Variational Problems and Minimization of Functionals......Page 167
  4.3.1 Variable Coefficient......Page 169
  4.3.2 First-Order Derivative in the Equation and Boundary Condition......Page 171
  4.3.3 Nonlinear Coefficient......Page 173
  4.4.1 Extensions of the Code for Approximation......Page 174
  4.4.2 Fallback to Numerical Methods......Page 175
  4.4.3 Example with Constant Right-Hand Side......Page 177
 4.5 Approximations May Fail: Convection-Diffusion......Page 178
  Exercise 4.2: Compute the Deflection of a Cable with Sine Functions......Page 183
  Exercise 4.4: Check Integration by Parts......Page 185
  5.1.1 Finite Element Mesh and Basis Functions......Page 186
  5.1.2 Computation in the Global Physical Domain......Page 188
  5.1.3 Comparison with a Finite Difference Discretization......Page 190
  5.1.4 Cellwise Computations......Page 191
  5.2.1 General Construction of a Boundary Function......Page 194
  5.2.2 Example on Computing with a Finite Element-Based Boundary Function......Page 196
  5.2.3 Modification of the Linear System......Page 198
  5.2.4 Symmetric Modification of the Linear System......Page 201
  5.2.5 Modification of the Element Matrix and Vector......Page 202
  5.3.2 Boundary Term Vanishes Because of the Test Functions......Page 203
  5.3.3 Boundary Term Vanishes Because of Linear System Modifications......Page 204
  5.3.4 Direct Computation of the Global Linear System......Page 205
  5.3.5 Cellwise Computations......Page 206
  5.4.1 Extensions of the Code for Approximation......Page 207
  5.4.3 Application to Our Model Problem......Page 211
 5.5 Variational Formulations in 2D and 3D......Page 213
  5.5.1 Integration by Parts......Page 214
  5.5.2 Example on a Multi-Dimensional Variational Problem......Page 215
  5.5.3 Transformation to a Reference Cell in 2D and 3D......Page 216
  5.5.4 Numerical Integration......Page 218
  5.5.5 Convenient Formulas for P1 Elements in 2D......Page 219
  5.5.6 A Glimpse of the Mathematical Theory of the Finite Element Method......Page 220
 5.6 Implementation in 2D and 3D via FEniCS......Page 224
  5.6.1 Mathematical Problem......Page 225
  5.6.2 Variational Formulation......Page 226
  5.6.3 The FEniCS Solver......Page 227
  5.6.4 Making the Mesh......Page 229
  5.6.5 Solving a Problem......Page 232
 5.7 Convection-Diffusion and Petrov-Galerkin Methods......Page 233
 5.8 Summary......Page 238
  Exercise 5.2: Compute the Deflection of a Cable with 1 P2 Element......Page 239
  Exercise 5.4: Compute with a Non-uniform Mesh......Page 240
  Exercise 5.6: Investigate Exact Finite Element Solutions......Page 241
  Exercise 5.7: Compare Finite Elements and Differences for a Radially Symmetric Poisson Equation......Page 242
  Exercise 5.9: Solve a 2D Poisson Equation Using Polynomials and Sines......Page 243
  Exercise 5.11: Solve a 1D Laplace Problem with FEniCS......Page 244
6 Time-Dependent Variational Forms......Page 245
  6.1.1 Time Discretization......Page 246
  6.1.2 Space Discretization......Page 247
  6.1.3 Variational Forms......Page 248
  6.1.5 Deriving the Linear Systems......Page 249
  6.1.7 Example Using Cosinusoidal Basis Functions......Page 251
  6.1.8 Comparing P1 Elements with the Finite Difference Method......Page 253
  6.2.2 Variational Forms......Page 254
  6.2.3 Linear Systems......Page 255
  6.3.1 Boundary Function......Page 256
  6.3.3 Modification of the Linear System......Page 257
  6.3.4 Example: Oscillating Dirichlet Boundary Condition......Page 258
  6.4.1 Methods of Analysis......Page 260
  6.4.2 Fourier Components and Dispersion Relations......Page 262
  6.4.3 Forward Euler Discretization......Page 263
  6.4.4 Backward Euler Discretization......Page 264
  6.4.5 Comparing Amplification Factors......Page 265
  Exercise 6.1: Analyze a Crank-Nicolson Scheme for the Diffusion Equation......Page 269
  7.1.1 Sequence of Scalar PDEs Formulation......Page 270
  7.1.2 Vector PDE Formulation......Page 271
 7.2 A Worked Example......Page 272
  7.3.1 Variational Form of Each Individual PDE......Page 273
  7.3.2 Compound Scalar Variational Form......Page 274
  7.3.3 Decoupled Linear Systems......Page 275
  7.3.4 Coupled Linear Systems......Page 276
 7.4 Different Function Spaces for the Unknowns......Page 277
 7.5 Computations in 1D......Page 279
  7.5.1 Another Example in 1D......Page 283
  Problem 7.2: Estimate Order of Convergence for the Cooling Law......Page 291
 8.1 Optimization with Constraint......Page 292
  8.1.2 Lagrange Multiplier Method......Page 293
  8.1.3 Penalty Method......Page 294
 8.2 Optimization of Functionals......Page 295
  8.2.1 Classical Calculus of Variations......Page 296
  8.2.2 Penalty and Nitsche's Methods for Optimization with Constraints......Page 298
  8.2.3 Lagrange Multiplier Method for Optimization with Constraints......Page 301
  8.2.4 Example: 1D Problem......Page 302
  8.2.5 Example: Adding a Constraint in a Neumann Problem......Page 305
  9.1.1 Linear Versus Nonlinear Equations......Page 310
  9.1.2 A Simple Model Problem......Page 312
  9.1.4 Exact Solution of Nonlinear Algebraic Equations......Page 313
  9.1.6 Picard Iteration......Page 315
  9.1.7 Linearization by a Geometric Mean......Page 317
  9.1.8 Newton's Method......Page 318
  9.1.10 Implementation and Experiments......Page 320
  9.1.11 Generalization to a General Nonlinear ODE......Page 323
  9.1.12 Systems of ODEs......Page 326
  9.2.1 Picard Iteration......Page 328
  9.2.2 Newton's Method......Page 329
  9.2.3 Stopping Criteria......Page 331
  9.2.4 Example: A Nonlinear ODE Model from Epidemiology......Page 332
 9.3 Linearization at the Differential Equation Level......Page 333
  9.3.2 Backward Euler Scheme and Picard Iteration......Page 334
  9.3.3 Backward Euler Scheme and Newton's Method......Page 336
  9.3.4 Crank-Nicolson Discretization......Page 338
 9.4 1D Stationary Nonlinear Differential Equations......Page 339
  9.4.1 Finite Difference Discretization......Page 340
  9.4.2 Solution of Algebraic Equations......Page 341
  9.4.3 Galerkin-Type Discretization......Page 346
  9.4.5 Newton's Method Defined from the Variational Form......Page 347
  9.5.1 Finite Element Discretization......Page 350
  9.5.2 Finite Difference Discretization......Page 353
  9.5.3 Continuation Methods......Page 355
 9.6 Symbolic Nonlinear Finite Element Equations......Page 356
  9.6.2 The Group Finite Element Method......Page 357
  9.6.3 Numerical Integration of Nonlinear Terms by Hand......Page 359
  9.6.4 Discretization of a Variable Coefficient Laplace Term......Page 361
  Exercise 9.2: Derive and Investigate a Generalized Logistic Model......Page 364
  Problem 9.3: Experience the Behavior of Newton's Method......Page 365
  Problem 9.5: Solve Nonlinear Equations Arising from a Vibration ODE......Page 366
  Exercise 9.6: Find the Truncation Error of Arithmetic Mean of Products......Page 367
  Exercise 9.8: Discretize a 1D Problem with a Nonlinear Coefficient......Page 368
  Problem 9.10: Finite Differences for the 1D Bratu Problem......Page 369
  Problem 9.11: Integrate Functions of Finite Element Expansions......Page 370
  Problem 9.12: Finite Elements for the 1D Bratu Problem......Page 371
  Exercise 9.14: Use Different Symbols for Different Approximations of the Solution......Page 372
  Exercise 9.16: Derive Algebraic Equations for Nonlinear 1D Heat Conduction......Page 373
  Exercise 9.19: Find the Sparsity of the Jacobian......Page 374
  Problem 9.20: Investigate a 1D Problem with a Continuation Method......Page 375
10 Variational Methods for Linear Systems......Page 376
  10.1.2 The Least Squares Method......Page 377
  10.1.4 Computation of the Basis Vectors......Page 378
  10.1.5 Computation of a New Solution Vector......Page 379
  10.1.6 Summary of the Least Squares Method......Page 380
  10.1.8 Summary of the Galerkin Method......Page 381
  10.1.9 A Framework Based on the Error......Page 382
  10.2.1 Motivation and Basic Principles......Page 383
  10.2.2 Use of the Preconditioning Matrix in the Iterative Methods......Page 384
  10.2.4 Incomplete Factorization Preconditioners......Page 385
  10.2.5 Preconditioners Developed for Solving PDE Problems......Page 387
 A.1 Finite Difference Operator Notation......Page 388
 A.2 Truncation Errors of Finite Difference Approximations......Page 389
 A.3 Finite Differences of Exponential Functions......Page 390
  A.4.1 Software......Page 391
References......Page 393
Index......Page 395