I took these notes in spring 2017 for CME 306, taught by Professor Lexing Ying.
If is -differentiable, then is the usual derivative. If is weakly differentiable, then satisfies If is differentiable in the distributional sense, then satisfies is the space of -differentiable functions on , equipped with the norm and the seminorm is the space of square-integrable functions on , equipped with the inner product and induced norm is the Sobolev space equipped with the inner product Poincare inequality: . Note for
In finite-difference methods, derivatives are approximated with forward/backwards/central difference operators:
They may be combined to yield, for example, approximations to the second derivative:
Error estimates (truncation error) are obtained using Taylor’s theorem:
To solve Poisson’s equation with finite differences, replace assuming that all neighbors of every point are contained in . This yields a system of linear equations in the , which we may solve. Consistency is given by the error estimate by the following argument. Discrete maximum principle: If for all , then attains its maximum on . (Proof: assume it attains an interior maximum; then its neighbors are also maxima.) Bound on growth: . (Proof: Recalling for a paraboloid , , construct a paraboloid for which and . Then apply the discrete maximum principle to the mesh function .) This implies uniqueness (and hence existence), applying the bound to . This implies the error estimate, applying the bound to and using the truncation error on :
Suppose we are solving an initial value problem of the form where is some polynomial. With finite differences, we construct an evolution operator that describes the approximate solution at the next time step : and compute iterates upon an initial condition . A necessary condition for convergence to the correct solution is both consistency and stability. For analysis, view as a convolution operator acting on a function : so that the Fourier transform of both sides is with For an operator to be consistent, we require as and , where is the true time evolution operator (that evolves by time ). Generally, a scheme created via finite differences will be consistent. However, if we need to constrct an operator by hand as a linear combination of lattice points, there is a nice characterization in the Fourier domain. By Taylor expansion in and using the PDE, the true evolution operator is Under the Fourier transform, , so this equation becomes Therefore, is accurate to order , i.e. if and only if or, rescaling: For an operator to be stable w.r.t. some norm, we require for all , where now we think of as the error. If an operator is unstable, the error’s magnitude may increase exponentially. (Note that the PDE itself must be stable, which is true for the heat equation and transport equation.) Von Neumann stability analysis uses the -norm, which especially nice because the Plancherel theorem says that . Thus, the stability condition can be written , which holds if and only if . A necessary condition for stability is the CFL condition (Courant-Friedrichs-Lewy), which says that a necessary condition for stability is that the domain of contains the domain of . If is both consistent and stable, we may show convergence via the following error estimate. Similar to above,
For the heat equation, the condition for th-order accuracy becomes where . (We may increase the order by 1 in error term because the only has even powers.) The -method uses the evolution operator given by The explicit forward Euler scheme uses , is a second-order scheme, and is -stable for . The implicit forward Euler scheme uses and is so-named because we need to solve a linear system to determine . It is stable for all . The mesh sizes and need not be related anymore, and the max-norm error estimate can be written The Crank-Nicolson scheme uses . It is stable for all . The max-norm error estimate can be written
For the scalar transport equation , the condition for th-order accuracy becomes where . The von Neumann stability condition for the following three schemes is . The forward Euler scheme uses the evolution operator given by where the dependence on the sign of is called upwinding (necessary to satisfy the CFL condition). The Friedrichs scheme is a first-order method based on the central difference where the artificial diffusion stabilizes it. The Lax-Wendroff scheme is a method constructed explicitly to be second-order accurate: where The Wendroff box scheme is a second-order method suitable for mixed initial-boundary value problems: where averages of surrounding grid points (up to four) are used if the grid point doesn’t exist.
The Galerkin method is the following. We relax the strong formulation of the PDE into the weak formulation for some bilinear form and space of test functions . Define a bilinear form as often symmetric. If we relax to some subspace with basis , we may express so that this becomes In matrix form, this is the linear system , with the matrices The matrix is called the stiffness matrix and is called the load vector. Let’s consider Poisson’s equation with Dirichlet boundary conditions, with (a coercivity condition). Here, the space of test functions is the Sobolev space with the bilinear forms For the finite-element method, the subspace is the space of piecewise linear functions on meshpoints , with basis of the “pyramid functions” interpolated from Error analysis is most natural in the energy norm . Since and for all by construction, we have so choosing , so We assumed that is symmetric to apply Cauchy-Schwarz. We may be interested in bounding with the norm. For this, first convert norms from above using the relation where the first follows is a coercivity condition (which follows from and Poincaré’s inequality) and the second is a boundedness condition (???). Then set to be the linear interpolation of and use the interpolation bound to arrive at where the last inequality is true when is convex. We may be also interested in bounding with the seminorm . For this, first convert norms from above using the relation which the first follows from our condition and the second is Poincaré’s inequality. Then set to be the linear interpolation of and use the interpolation bound to arrive at where the last inequality is true when is convex.
Conservative schemes discretize the spatial domain into cells and locally solve the integral equation Approximate to arrive at the conservative scheme with numerical flux . A conservative scheme is consistent if locally satisfies a Lipschitz condition If a consistent conservative scheme converges, then it converges to a weak solution (Lax and Wendroff). If additionally the scheme is monotone, i.e. the scheme is written and is monotonically increasing in its three arguments, then the scheme converges to an entropy solution (Crandell and Majda). This condition may be expanded to read Monotone schemes are at best first-order. Define and , where we can think of as the maximum velocity of flow. The following schemes are monotone with a CFL condition. The Godunov scheme uses the numerical flux derived from solving the Riemann problem at each mesh point (requires casework). The Lax-Friedrichs scheme uses the numerical flux