NUMERICAL PARTIAL DIFFERENTIAL EQUATIONS FOR ENVIRONMENTAL SCIENTISTS AND ENGINEERS A First Practical Course Daniel R. Lynch Dartmouth College Dartmouth, New Hampshire USA 4- Springer Library of Congress Cataloging-in-PublicationD ata Lynch, Daniel R. Numerical partial differential equations for environmental scientists and engineers : a first practical course I by Daniel R. Lynch. p. cm. Includes bibliographical references and index. ISBN 0-387-23619-8 (alk. paper) 1. Differential equations, Partial-Numerical solutions. 2. Finite differences. 3. Finite element method. 4. Inverse problems (Differential equations) I. Title. O 2005 Springer Science+BusinessM edia, Inc. All rights resewed. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+BusinessM edia, Inc., 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now know or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks and similar terms, even if the are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed in the United States of America. 9 8 7 6 5 4 3 2 1 SPIN 11055716 Contents Preface xv Synopsis xix I The Finite Difference Method Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 From Algebra to Calculus and Back . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Distributed. Lumped. Discrete Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 PDE Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 IC's. BC's. Classification . . . . . . . . . . . . . . . . . . . . . . . . . . A uniqueness proof: Poisson Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Classification of BC's . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Classification of Equations 2 Finite Difference Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 1-D Differences on a Uniform Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary .U niform Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Use of the Error Term . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 1-D Differences on Nonuniform Meshes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Polynomial Fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Cross-Derivatives 3 Elliptic Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 1-D Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 2-D Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Molecules . . . . . . . . . . . . . . . . . . . . . . . . . . . Matrix Assembly and Direct Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Iterative Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Operation Counts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Advective-Diffusive Equation 4 Elliptic Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Bare Essentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Point Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Block Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Alternating Direction Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Helmholtz Equation CONTENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Gradient Descent Methods 47 5 Parabolic Equations 51 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.2 Examples: Discrete Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Leapfrog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Backward Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2-Level Implicit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.3 Boundary Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.4 Stability, Consistency, Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Convergence .L umped System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Convergence - Discrete System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Accuracy: Fourier Analysis 64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Continuous System 64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lumped System 65 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Discrete System 67 Example: Implicit Leapfrog System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.6 Conservation Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.7 Two-Dimensional Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.8 Nonlinear Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6 Hyperbolic Equations 89 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.2 Lumped Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.3 Harmonic Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.4 More Lumped Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.5 Dispersion Relationship . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Continuous System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Lumped System # 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Lumped System # 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Lumped System # 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 02 Lumped System # 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.6 Discrete Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Discrete System 1 (Telegraph Equation) . . . . . . . . . . . . . . . . . . . . . . . . . 1 06 Discrete Systems 3: Coupled lStO rder Equations . . . . . . . . . . . . . . . . . . . . 1 09 Discrete System 4: Implicit Four-Point Primitive . . . . . . . . . . . . . . . . . . . . 115 6.7 Lumped Systems in Higher Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . 1 16 I1 The Finite Element Method 121 7 General Principles 123 7.1 The Method of Weighted Residuals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 7.2 MWR Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 7.3 Weak Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.4 Discrete Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 29 CONTENTS vii 7.5 Boundary Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.6 Variational Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 7.7 Weak Forms and Conservation Properties . . . . . . . . . . . . . . . . . . . . . . . . 133 8 A 1-D Tutorial 139 8.1 Polynomial Bases the Lagrange Family . . . . . . . . . . . . . . . . . . . . . . . . . 1 39 . 8.2 Global and Local Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 8.3 Local Interpolation on Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 8.4 Continuity Hermite Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 - 8.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 8.6 Boundary Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 8.7 The Element Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 52 8.8 Assembly and the Incidence List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 57 8.9 Matrix Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 8.10 Variable Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 61 8.11 Numerical Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 62 8.12 Assembly with Quadrature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 9 Multi-Dimensional Elements 167 9.1 Linear Triangular Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 Local Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 67 Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 Integration . . . . . . . . . ; . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 70 9.2 Example: Helmholtz Equation on Linear Triangles . . . . . . . . . . . . . . . . . . . 170 9.3 Higher Order Triangular Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 72 Local Coordinate System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 72 Higher-Order Local Interpolation on Triangles . . . . . . . . . . . . . . . . . . . . . . 173 Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 75 Numerical Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 9.4 Isoparametric Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 9.5 Quadrilateral Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 The Bilinear Element . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 81 Higher-Order Quadrilateral Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 83 Isoparametric Quadrilaterals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 83 10 Time-Dependent Problems 189 10.1 General Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 10.2 Lumped and Discrete Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 10.3 Example: Diffusion Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 10.4 Example: Advection-Diffusion Equation . . . . . . . . . . . . . . . . . . . . . . . . . 192 10.5 Example: Wave Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 10.6 Example: Telegraph Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 11 Vector Problems 197 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 97 11.2 Gradient of a Scalar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 97 Galerkin Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 98 Natural Local Coordinate Systems and Neumann Boundaries . . . . . . . . . . . . . 1 99 Dirichlet Boundaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 01 viii CONTENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Elasticity 202 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Weak Form 202 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Constitutive Relations 203 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Galerkin Approximation 204 . . . . . . . . . . . . . . . . . . . . . . . . . . . . Natural Local Coordinate Systems 204 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References Solid Mechanics 205 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4 Electromagnetics 205 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Governing Equations 206 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Potentials and Gauge 206 . . . . . . . . . . . . . . . . . . . . . . . . . . Helmholtz Equations in the Potentials 207 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Weak Form 208 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Boundary Conditions 209 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Reconstructing E and H 209 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References .E &M 209 . . . . . . . . . . . . . . . . . . . . . . . . 11.5 Fluid Mechanics with Mixed Interpolation 210 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Governing equations 210 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bases and Weights 211 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mixed Elements 211 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Weak Form 212 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Galerkin Equations 212 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Numbering Convention 213 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Coordinate Rotation 214 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References: Fluid Mechanics 214 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.6 Oceanic Tides 214 . . . . . . . . . . . . . . . . . . . . . . Weak Form and Galerkin Helmholtz Equation 215 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Velocity Solution 216 References .O ceanic Tides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 12 Numerical Analysis 219 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1 1-D Elliptic Equations 219 Laplace Equation on 1-D Linear Elements . . . . . . . . . . . . . . . . . . . . . . . . 219 Advective-Diffusive Equation on 1-D Linear Elements . . . . . . . . . . . . . . . . . 2 19 . . . . . . . . . . . . . . . . . . . . . . Helmholtz Equation on 1-D Linear Elements 221 . . . . . . . . . . . . . . . . . . . . . . . . Poisson Equation on 1-D Linear Elements 223 Inhomogeneous Helmholtz Equation on 1-D Linear Elements . . . . . . . . . . . . . 2 26 12.2 Fourier Transforms for Difference Expressions . . . . . . . . . . . . . . . . . . . . . . 230 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.3 2-D Elliptic Equations 236 . . . . . . . . . . . . . . . . . . . . . . . . . Laplace Equation on Bilinear Rectangles 236 . . . . . . . . . . . . . . . . . . . . . . . Helmholtz Equation on Bilinear Rectangles 238 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.4 Diffusion Equation 240 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stability 241 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Monotonicity 242 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Accuracy 243 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Leapfrog Time-Stepping 243 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-level Implicit Time-Stepping 245 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.5 Explicit Wave Equation 247 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stability 248 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Accuracy 248 CONTENTS ix 12.6 Implicit Wave Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 50 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 51 12.7 Advection Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 51 Euler Advection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 52 Two-Level Implicit Advection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 Leapfrog Advection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 53 12.8 Advective-Diffusive Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 2-Level Implicit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 Leapfrog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 I11 Inverse MeBhods 263 13 Inverse Noise. SVD. and LLS 265 13.1 Matrix Inversion and Inverse Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 66 Mean and Variability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 66 Covariance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 66 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 Noise Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 68 EigenTheory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 13.2 The Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 72 SVDBasics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 The Square. Nonsingular Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 74 The Square. Singular Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 75 The Square. Nearly-Singular Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 The Over-Determined Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 77 The Under-Determined Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 SVD Covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 SVD References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 79 13.3 Linear Least Squares and the Normal Equations . . . . . . . . . . . . . . . . . . . . 279 Quadratic Forms and Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 79 Ordinary Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 Weighted Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 81 General Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 82 14 Fitting Models to Data 285 14.1 Inverting Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 85 Model-Data Misfit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 85 Direct Solution Strategies and Inverse Noise . . . . . . . . . . . . . . . . . . . . . . .2 87 More on the Model-Data Misfit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 88 14.2 Constrained Minimization and Gradient Descent . . . . . . . . . . . . . . . . . . . . 289 Generalized Least Squares as Constrained Minimization . . . . . . . . . . . . . . . .2 89 The Adjoint Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 90 Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 Summary Adjoint Method with Gradient Descent . . . . . . . . . . . . . . . . . . .2 93 - Monte Carlo Variance Estimation - Inverse Noise . . . . . . . . . . . . . . . . . . . . 2 93 14.3 Inverting Data With Representers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 94 CONTENTS The Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 Inverse Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 14.4 Inverting Data with Unit Responses . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 96 Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 14.5 Summary: GLS Data Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 97 14.6 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 98 GLS Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 . . . . . . . . . . . . . . . . . . . . . . . First-Order Conditions for GLS Extremum 299 The Gradient in Parameter Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 00 An Adjoint Method for Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . 3 02 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.7 Summary Terminology 302 - 15 Dynamic Inversion 305 . . . . . . . . . . . . . . . . . . . . . 15.1 Parabolic Model: Advective-Diffusive Transport 305 Forward Model in Discrete Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 Objective and First-Order Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . 3 07 Adjoint Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 08 Direct Solution An Elliptic Problem in Time . . . . . . . . . . . . . . . . . . . . . 3 09 . Iterative Solution by Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . .3 10 Special Case #1: "Shooting" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 Special Case #2: Agnostic p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 13 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 13 15.2 Hyperbolic Model: Telegraph Equation . . . . . . . . . . . . . . . . . . . . . . . . . . 3 15 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 15 Optimal Fit: GLS Objective and First-Order Conditions . . . . . . . . . . . . . . . . 3 16 Gradient Descent Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 Conjugate Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 19 Solution by Representers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 19 15.3 Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 21 Reduction of the DoF's . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 21 The Weight Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 22 Heuristic Specification of [W] using FEM . . . . . . . . . . . . . . . . . . . . . . . . 3 22 15.4 Example: Nonlinear Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 23 16 Time Conventions for Real-Time Assimilation 329 16.1Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 29 16.2 Observational Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 29 16.3 Simulation Data Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 16.4 Sequential Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 31 16.5 What Time Is It? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 16.6 Example: R-T Operations, Cruise EL 9904 . . . . . . . . . . . . . . . . . . . . . . . 3 32 17 Skill Assessment for Data Assimilative Models 335 17.1 Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 35 Forward and Inverse Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 35 Truth. Data. Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 Skill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 Accuracy/Bias. Precision/Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 36 17.2 Observational System Simulation Experiments: Example . . . . . . . . . . . . . . . . 3 37 CONTENTS xi 18 Statistical Interpolation 341 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18.1 Introduction: Point Estimation 341 . . . . . . . . . . . . . . . . . . . . . . 18.2 Interpolation and the Gauss-Markov Theorem 343 . . . . . . . . . . . . . . . . . . . . . . . . . 18.3 Interpolating and Sampling Finite Fields 345 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18.4 Analytic Covariance Functions 348 . . . . . . . . . . . . . . . . . . . 18.5 Stochastically-Forced Differential Equation (SDE) 350 Example1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 Example2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18.6 OA-GLS Equivalence 356 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18.7 Kriging 358 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18.8 Concluding Remarks 359 Appendices A1 . Vector Identities . . . . . . . . . . . . . . . . . . . . A2 . Coordinate Systems . . . . . . . . . . . . . . . . . . A3 . Stability of Quadratic Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A4 Inversion Notes A5 . Time Conventions . . . . . . . . . . . . . . . . . . . Bibliography 377 Index 385 List of Tables Forward difference representations. O(h). [45]. . . . . . . . . . . . . . . . . . . . . . 14 Backward difference representations. O(h). [45]. . . . . . . . . . . . . . . . . . . . . . 14 Forward difference representations. O(h2). [45]. . . . . . . . . . . . . . . . . . . . . . 14 Backward difference representations. O(h2). [45]. . . . . . . . . . . . . . . . . . . . . 14 Central difference representations. O(h2). [45]. . . . . . . . . . . . . . . . . . . . . . 14 Central difference representations. 0 (h4). [45] . . . . . . . . . . . . . . . . . . . . . 15 Scaling for generic matrix solution strategies. Inversion is the Gold Standard for well-conditioned Elliptic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Scaling in terms of n = llh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 -l/ln(p) for point and line iterations. 2-D Laplace on a square . The number of iterations M required for a given error reduction is proportional to this . . . . . . . . 44 Conservation Analogies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Interpolation data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 40 Interpolated result at x = 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 Sampled values of u = . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 41 Interpolation and extrapolation results . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Nodal values of Hermite cubic bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Integrals of q5 and its derivatives for linear elements. . . . . . . . . . . . . . . . . . . 147 Integrals of 4 and its derivatives for 1-D quadratic elements (mid-element node cen- % tered) . h = is the spacing between nodes; As is the element length; (1) = 2h . . . 1 56 Incidence List for the 1-D mesh in Figure 8.9. . . . . . . . . . . . . . . . . . . . . . . 157 Gauss-Legendre quadrature . The order of polynomial interpolation is 2n - 1. t is the normalized independent variable on the interval [-I, 11 . . . . . . . . . . . . . . . 163 Integration formulas for Linear Triangles. The local indices (i. j. Ic) are numbered in counterclockwise order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 C0 Quadratic Triangular Bases and their Derivatives. . . . . . . . . . . . . . . . . . 1 74 C0 Cubic Triangular Bases and their Derivatives. . . . . . . . . . . . . . . . . . . . . 175 Quadrature points and weights for triangles . The order of exact polynomial inter- polation is indicated as N . Multiplicity M > 1 indicates multiple symmetric points . Adapted from [25]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 2 x 2 Gauss-Legendre quadrature, sufficient to integrate an integrand of order 53773. . 185 3 x 3 Gauss-Legendre quadrature. sufficient to integrate an integrand of order t5775. . 185 C0 Bilinear Quadrilateral Bases and their Derivatives. . . . . . . . . . . . . . . . . . 1 86 C0 Quadratic Quadrilateral Bases and their Derivatives. . . . . . . . . . . . . . . . . 186 C0 Cubic Quadrilateral Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186