Frontiers in Numerical Analysis Durham 2002

The Tenth LMS-EPSRC Numerical Analysis Summer School was held at the University of Durham, UK, from the 7th to the 19th of July 2002. This was the second of these schools to be held in Durham, having previously been hosted by the University of Lancaster and the University of Leicester. The purpose of the summer school was to present high quality instructional courses on topics at the forefront of numerical analysis research to postgraduate students. The speakers were Franco Brezzi, Gerd Dziuk, Nick Gould, Ernst Hairer, Tom Hou and Volker Mehrmann. This volume presents written contributions from all six speakers which are more comprehensive versions of the high quality lecture notes which were distributed to participants during the meeting. At the time of writing it is now more than two years since we first contacted the guest speakers and during that period they have given significant portions of their time to making the summer school, and this volume, a success. We would like to thank all six of them for the care which they took in the preparation and delivery of their material.

Subgrid Phenomena and Numerical Schemes.- 1 Introduction.- 2 The Continuous Problem.- 3 From the Discrete Problem to the Augmented Problem.- 4 An Example of Error Estimates.- 5 Computational Aspects.- 5.1 First Strategy.- 5.2 Alternative Computational Strategies.- 6 Conclusions.- References.- Stability of Saddle-Points in Finite Dimensions.- 1 Introduction.- 2 Notation, and Basic Results in Linear Algebra.- 3 Existence and Uniqueness of Solutions: the Solvability Problem.- 4 The Case of Big Matrices. The Inf-Sup Condition.- 5 The Case of Big Matrices. The Problem of Stability.- 6 Additional Considerations.- References.- Mean Curvature Flow.- 1 Introduction.- 2 Some Geometric Analysis.- 2.1 Tangential Gradients and Curvature.- 2.2 Moving Surfaces.- 2.3 The Concept of Anisotropy.- 3 Parametric Mean Curvature Flow.- 3.1 Curve Shortening Flow.- 3.2 Anisotropic Curve Shortening Flow.- 3.3 Mean Curvature Flow of Hypersurfaces.- 3.4 Finite Elements on Surfaces.- 4 Mean Curvature Flow of Level Sets I.- 4.1 Viscosity Solutions.- 4.2 Regularization.- 5 Mean Curvature Flow of Graphs.- 5.1 The Differential Equation.- 5.2 Analytical Results.- 5.3 Spatial Discretization.- 5.4 Estimate of the Spatial Error.- 5.5 Time Discretization.- 6 Anisotropic Curvature Flow of Graphs.- 6.1 Discretization in Space and Estimate of the Error.- 6.2 Fully Discrete Scheme, Stability and Error Estimate.- 7 Mean Curvature Flow of Level Sets II.- 7.1 The Approximation of Viscosity Solutions.- 7.2 Anisotropic Mean Curvature Flow of Level Sets.- References.- An Introduction to Algorithms for Nonlinear Optimization.- 1 Optimality Conditions and Why They Are Important.- 1.1 Optimization Problems.- 1.2 Notation.- 1.3 Lipschitz Continuity and Taylor’s Theorem.- 1.4 Optimality Conditions.- 1.5 Optimality Conditions for Unconstrained Minimization.- 1.6 Optimality Conditions for Constrained Minimization.- 1.6.1 Optimality Conditions for Equality-Constrained Minimization.- 1.6.2 Optimality Conditions for Inequality-Constrained Minimization.- 2 Linesearch Methods for Unconstrained Optimization.- 2.1 Linesearch Methods.- 2.2 Practical Linesearch Methods.- 2.3 Convergence of Generic Linesearch Methods.- 2.4 Method of Steepest Descent.- 2.5 More General Descent Methods.- 2.5.1 Newton and Newton-Like Methods.- 2.5.2 Modified-Newton Methods.- 2.5.3 Quasi-Newton Methods.- 2.5.4 Conjugate-Gradient and Truncated-Newton Methods.- 3 Trust-Region Methods for Unconstrained Optimization.- 3.1 Linesearch Versus Trust-Region Methods.- 3.2 Trust-Region Models.- 3.3 Basic Trust-Region Method.- 3.4 Basic Convergence of Trust-Region Methods.- 3.5 Solving the Trust-Region Subproblem.- 3.5.1 Solving the ?2-Norm Trust-Region Subproblem.- 3.6 Solving the Large-Scale Problem.- 4 Interior-Point Methods for Inequality Constrained Optimization.- 4.1 Merit Functions for Constrained Minimization.- 4.2 The Logarithmic Barrier Function for Inequality Constraints.- 4.3 A Basic Barrier-Function Algorithm.- 4.4 Potential Difficulties.- 4.4.1 Potential Difficulty I: Ill-Conditioning of the Barrier Hessian.- 4.4.2 Potential Difficulty II: Poor Starting Points.- 4.5 A Different Perspective: Perturbed Optimality Conditions.- 4.5.1 Potential Difficulty II… Revisited.- 4.5.2 Primal-Dual Barrier Methods.- 4.5.3 Potential Difficulty I… Revisited.- 4.6 A Practical Primal-Dual Method.- 5 SQP Methods for Equality Constrained Optimization.- 5.1 Newton’s Method for First-Order Optimality.- 5.2 The Sequential Quadratic Programming Iteration.- 5.3 Linesearch SQP Methods.- 5.4 Trust-Region SQP Methods.- 5.4.1 The S?pQP Method.- 5.4.2 Composite-Step Methods.- 5.4.3 Filter Methods.- 6 Conclusion.- A Seminal Books and Papers.- B Optimization Resources on the World-Wide-Web.- B.1 Answering Questions on the Web.- B.2 Solving Optimization Problems on the Web.- B.2.1 The NEOS Server.- B.2.2 Other Online Solvers.- B.2.3 Useful Sites for Modelling Problems Prior to Online Solution.- B.2.4 Free Optimization Software.- B.3 Optimization Reports on the Web.- C Sketches of Proofs.- GniCodes - Matlab Programs for Geometric Numerical Integration.- 1 Problems to be Solved.- 1.1 Hamiltonian Systems.- 1.2 Reversible Differential Equations.- 1.3 Hamiltonian and Reversible Systems on Manifolds.- 2 Symplectic and Symmetric Integrators.- 2.1 Simple Symplectic Methods.- 2.2 Simple Reversible Methods.- 2.3 Störmer/Verlet Scheme.- 2.4 Splitting Methods.- 2.5 High Order Geometric Integrators.- 2.6 Rattle for Constrained Hamiltonian Systems.- 3 Theoretical Foundation of Geometric Integrators.- 3.1 Backward Error Analysis.- 3.2 Properties of the Modified Equation.- 3.3 Long-Time Behaviour of Geometric Integrators.- 4 Matlab Programs of ‘GniCodes’.- 4.1 Standard Call of Integrators.- 4.2 Problem Description.- 4.3 Event Location.- 4.4 Program gni_irk2.- 4.5 Program gni_limn2.- 4.6 Program gni.comp.- 5 Some Typical Applications.- 5.1 Comparison of Geometric Integrators.- 5.2 Computation of Poincaré Sections.- 5.3 ‘Rattle’ as a Basic Integrator for Composition.- References.- Numerical Approximations to Multiscale Solutions in PDEs.- 1 Introduction.- 2 Review of Homogenization Theory.- 2.1 Homogenization Theory for Elliptic Problems.- 2.2 Homogenization for Hyperbolic Problems.- 2.3 Convection of Microstructure.- 3 Numerical Homogenization Based on Sampling Techniques.- 3.1 Convergence of the Particle Method.- 3.2 Vortex Methods for Incompressible Flows.- 4 Numerical Homogenization Based on Multiscale FEMs.- 4.1 Multiscale Finite Element Methods for Elliptic PDEs.- 4.2 Error Estimates (h?).- 4.4 The Over-Sampling Technique.- 4.5 Performance and Implementation Issues.- 4.6 Applications.- 5 Wavelet-Based Homogenization (WBH).- 5.1 Wavelets.- 5.2 Introduction to Wavelet-Based Homogenization (WBH).- 6 Variational Multiscale Method.- References.- Numerical Methods for Eigenvalue and Control Problems.- 1 Introduction.- 2 Classical Techniques for Eigenvalue Problems.- 2.1 The Schur Form and the QR-Algorithm.- 2.2 The Generahzed Schur Form and the QZ-Algorithm.- 2.3 The Singular Value Decomposition (SVD).- 2.4 The Arnoldi Algorithm.- 3 Basics of Linear Control Theory.- 3.1 Controllability and Stabilizability.- 3.2 System Equivalence.- 3.3 Optimal Control.- 4 Hamiltonian Matrices and Riccati Equations.- 4.1 The Hamiltonian Schur Form.- 4.2 Solution of the Optimal Control Problem via Riccati Equations.- 5 Numerical Solution of Hamiltonian Eigenvalue Problems.- 5.1 Subspace Computation.- 6 Large Scale Problems.- 7 Conclusion.- References.