Godunov's scheme

Last updated

In numerical analysis and computational fluid dynamics, Godunov's scheme is a conservative numerical scheme, suggested by S. K. Godunov in 1959, [1] for solving partial differential equations. One can think of this method as a conservative finite-volume method which solves exact, or approximate Riemann problems at each inter-cell boundary. In its basic form, Godunov's method is first order accurate in both space and time, yet can be used as a base scheme for developing higher-order methods.

Contents

Basic scheme

Following the classical finite-volume method framework, we seek to track a finite set of discrete unknowns,

where the and form a discrete set of points for the hyperbolic problem:

where the indices and indicate the derivatives in time and space, respectively. If we integrate the hyperbolic problem over a control volume we obtain a method of lines (MOL) formulation for the spatial cell averages:

which is a classical description of the first order, upwinded finite volume method. [2]

Exact time integration of the above formula from time to time yields the exact update formula:

Godunov's method replaces the time integral of each

with a forward Euler method which yields a fully discrete update formula for each of the unknowns . That is, we approximate the integrals with

where is an approximation to the exact solution of the Riemann problem. For consistency, one assumes that

and that is increasing in the first argument, and decreasing in the second argument. For scalar problems where , one can use the simple Upwind scheme, which defines .

The full Godunov scheme requires the definition of an approximate, or an exact Riemann solver, but in its most basic form, is given by:

Linear problem

In the case of a linear problem, where , and without loss of generality, we'll assume that , the upwinded Godunov method yields:

which yields the classical first-order, upwinded Finite Volume scheme whose stability requires .

Three-step algorithm

Following Hirsch, [3] the scheme involves three distinct steps to obtain the solution at from the known solution at , as follows:

  1. Define piecewise constant approximation of the solution at . Since the piecewise constant approximation is an average of the solution over the cell of size , the spatial error is of order , and hence the resulting scheme will be first-order accurate in space. Note that this approximation corresponds to a finite volume method representation whereby the discrete values represent averages of the state variables over the cells. Exact relations for the averaged cell values can be obtained from the integral conservation laws.
  2. Obtain the solution for the local Riemann problem at the cell interfaces. This is the only physical step of the whole procedure. The discontinuities at the interfaces are resolved in a superposition of waves satisfying locally the conservation equations. The original Godunov method is based upon the exact solution of the Riemann problems. However, approximate solutions can be applied as an alternative.
  3. Average the state variables after a time interval . The state variables obtained after Step 2 are averaged over each cell defining a new piecewise constant approximation resulting from the wave propagation during the time interval . To be consistent, the time interval should be limited such that the waves emanating from an interface do not interact with waves created at the adjacent interfaces. Otherwise the situation inside a cell would be influenced by interacting Riemann problems. This leads to the CFL condition where is the maximum wave speed obtained from the cell eigenvalue(s) of the local Jacobian matrix.

The first and third steps are solely of a numerical nature and can be considered as a projection stage, independent of the second, physical step, the evolution stage. Therefore, they can be modified without influencing the physical input, for instance by replacing the piecewise constant approximation by a piecewise linear variation inside each cell, leading to the definition of second-order space-accurate schemes, such as the MUSCL scheme.

See also

Related Research Articles

A finite difference is a mathematical expression of the form f (x + b) − f (x + a). If a finite difference is divided by ba, one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for the numerical solution of differential equations, especially boundary value problems.

<span class="mw-page-title-main">Riemann sum</span> Approximation technique in integral calculus

In mathematics, a Riemann sum is a certain kind of approximation of an integral by a finite sum. It is named after nineteenth century German mathematician Bernhard Riemann. One very common application is approximating the area of functions or lines on a graph, but also the length of curves and other approximations.

<span class="mw-page-title-main">Finite volume method</span>

The finite volume method (FVM) is a method for representing and evaluating partial differential equations in the form of algebraic equations. In the finite volume method, volume integrals in a partial differential equation that contain a divergence term are converted to surface integrals, using the divergence theorem. These terms are then evaluated as fluxes at the surfaces of each finite volume. Because the flux entering a given volume is identical to that leaving the adjacent volume, these methods are conservative. Another advantage of the finite volume method is that it is easily formulated to allow for unstructured meshes. The method is used in many computational fluid dynamics packages. "Finite volume" refers to the small volume surrounding each node point on a mesh.

Verlet integration is a numerical method used to integrate Newton's equations of motion. It is frequently used to calculate trajectories of particles in molecular dynamics simulations and computer graphics. The algorithm was first used in 1791 by Jean Baptiste Delambre and has been rediscovered many times since then, most recently by Loup Verlet in the 1960s for use in molecular dynamics. It was also used by P. H. Cowell and A. C. C. Crommelin in 1909 to compute the orbit of Halley's Comet, and by Carl Størmer in 1907 to study the trajectories of electrical particles in a magnetic field . The Verlet integrator provides good numerical stability, as well as other properties that are important in physical systems such as time reversibility and preservation of the symplectic form on phase space, at no significant additional computational cost over the simple Euler method.

In mathematics, the convergence condition by Courant–Friedrichs–Lewy is a necessary condition for convergence while solving certain partial differential equations numerically. It arises in the numerical analysis of explicit time integration schemes, when these are used for the numerical solution. As a consequence, the time step must be less than a certain time in many explicit time-marching computer simulations, otherwise the simulation produces incorrect results. The condition is named after Richard Courant, Kurt Friedrichs, and Hans Lewy who described it in their 1928 paper.

In numerical methods, total variation diminishing (TVD) is a property of certain discretization schemes used to solve hyperbolic partial differential equations. The most notable application of this method is in computational fluid dynamics. The concept of TVD was introduced by Ami Harten.

In numerical analysis and computational fluid dynamics, Godunov's theorem — also known as Godunov's order barrier theorem — is a mathematical theorem important in the development of the theory of high resolution schemes for the numerical solution of partial differential equations.

In the study of partial differential equations, the MUSCL scheme is a finite volume method that can provide highly accurate numerical solutions for a given system, even in cases where the solutions exhibit shocks, discontinuities, or large gradients. MUSCL stands for Monotonic Upstream-centered Scheme for Conservation Laws, and the term was introduced in a seminal paper by Bram van Leer. In this paper he constructed the first high-order, total variation diminishing (TVD) scheme where he obtained second order spatial accuracy.

<span class="mw-page-title-main">Finite difference method</span> Class of numerical techniques

In numerical analysis, finite-difference methods (FDM) are a class of numerical techniques for solving differential equations by approximating derivatives with finite differences. Both the spatial domain and time interval are discretized, or broken into a finite number of steps, and the value of the solution at these discrete points is approximated by solving algebraic equations containing finite differences and values from nearby points.

In applied mathematics, discontinuous Galerkin methods (DG methods) form a class of numerical methods for solving differential equations. They combine features of the finite element and the finite volume framework and have been successfully applied to hyperbolic, elliptic, parabolic and mixed form problems arising from a wide range of applications. DG methods have in particular received considerable interest for problems with a dominant first-order part, e.g. in electrodynamics, fluid mechanics and plasma physics.

In computational physics, the term upwind scheme typically refers to a class of numerical discretization methods for solving hyperbolic partial differential equations, in which so-called upstream variables are used to calculate the derivatives in a flow field. That is, derivatives are estimated using a set of data points biased to be more "upwind" of the query point, with respect to the direction of the flow. Historically, the origin of upwind methods can be traced back to the work of Courant, Isaacson, and Rees who proposed the CIR method.

Nonstandard finite difference schemes is a general set of methods in numerical analysis that gives numerical solutions to differential equations by constructing a discrete model. The general rules for such schemes are not precisely known.

The Lax–Friedrichs method, named after Peter Lax and Kurt O. Friedrichs, is a numerical method for the solution of hyperbolic partial differential equations based on finite differences. The method can be described as the FTCS scheme with a numerical dissipation term of 1/2. One can view the Lax–Friedrichs method as an alternative to Godunov's scheme, where one avoids solving a Riemann problem at each cell interface, at the expense of adding artificial viscosity.

In numerical analysis, von Neumann stability analysis is a procedure used to check the stability of finite difference schemes as applied to linear partial differential equations. The analysis is based on the Fourier decomposition of numerical error and was developed at Los Alamos National Laboratory after having been briefly described in a 1947 article by British researchers Crank and Nicolson. This method is an example of explicit time integration where the function that defines governing equation is evaluated at the current time. Later, the method was given a more rigorous treatment in an article co-authored by John von Neumann.

False diffusion is a type of error observed when the upwind scheme is used to approximate the convection term in convection–diffusion equations. The more accurate central difference scheme can be used for the convection term, but for grids with cell Peclet number more than 2, the central difference scheme is unstable and the simpler upwind scheme is often used. The resulting error from the upwind differencing scheme has a diffusion-like appearance in two- or three-dimensional co-ordinate systems and is referred as "false diffusion". False-diffusion errors in numerical solutions of convection-diffusion problems, in two- and three-dimensions, arise from the numerical approximations of the convection term in the conservation equations. Over the past 20 years many numerical techniques have been developed to solve convection-diffusion equations and none are problem-free, but false diffusion is one of the most serious problems and a major topic of controversy and confusion among numerical analysts.

<span class="mw-page-title-main">Central differencing scheme</span>

In applied mathematics, the central differencing scheme is a finite difference method that optimizes the approximation for the differential operator in the central node of the considered patch and provides numerical solutions to differential equations. It is one of the schemes used to solve the integrated convection–diffusion equation and to calculate the transported property Φ at the e and w faces, where e and w are short for east and west. The method's advantages are that it is easy to understand and implement, at least for simple material relations; and that its convergence rate is faster than some other finite differencing methods, such as forward and backward differencing. The right side of the convection-diffusion equation, which basically highlights the diffusion terms, can be represented using central difference approximation. To simplify the solution and analysis, linear interpolation can be used logically to compute the cell face values for the left side of this equation, which is nothing but the convective terms. Therefore, cell face values of property for a uniform grid can be written as:

Fluid motion is governed by the Navier–Stokes equations, a set of coupled and nonlinear partial differential equations derived from the basic laws of conservation of mass, momentum and energy. The unknowns are usually the flow velocity, the pressure and density and temperature. The analytical solution of this equation is impossible hence scientists resort to laboratory experiments in such situations. The answers delivered are, however, usually qualitatively different since dynamical and geometric similitude are difficult to enforce simultaneously between the lab experiment and the prototype. Furthermore, the design and construction of these experiments can be difficult, particularly for stratified rotating flows. Computational fluid dynamics (CFD) is an additional tool in the arsenal of scientists. In its early days CFD was often controversial, as it involved additional approximation to the governing equations and raised additional (legitimate) issues. Nowadays CFD is an established discipline alongside theoretical and experimental methods. This position is in large part due to the exponential growth of computer power which has allowed us to tackle ever larger and more complex problems.

The convection–diffusion equation describes the flow of heat, particles, or other physical quantities in situations where there is both diffusion and convection or advection. For information about the equation, its derivation, and its conceptual importance and consequences, see the main article convection–diffusion equation. This article describes how to use a computer to calculate an approximate numerical solution of the discretized equation, in a time-dependent situation.

The compact finite difference formulation, or Hermitian formulation, is a numerical method to compute finite difference approximations. Such approximations tend to be more accurate for their stencil size and, for hyperbolic problems, have favorable dispersive error and dissipative error properties when compared to explicit schemes. A disadvantage is that compact schemes are implicit and require to solve a diagonal matrix system for the evaluation of interpolations or derivatives at all grid points. Due to their excellent stability properties, compact schemes are a popular choice for use in higher-order numerical solvers for the Navier-Stokes Equations.

<span class="mw-page-title-main">Gradient discretisation method</span>

In numerical mathematics, the gradient discretisation method (GDM) is a framework which contains classical and recent numerical schemes for diffusion problems of various kinds: linear or non-linear, steady-state or time-dependent. The schemes may be conforming or non-conforming, and may rely on very general polygonal or polyhedral meshes.

References

  1. Godunov, S. K. (1959). "Разностный метод численного расчета разрывных решений уравнений гидродинамики" [A Difference Scheme for Numerical Solution of Discontinuous Solution of Hydrodynamic Equations]. Mat. Sbornik . 47: 271–306. MR   0119433. Zbl   0171.46204. Translated US Joint Publ. Res. Service, JPRS 7226, 1969.
  2. Leveque, Randy J. (2002). Finite Volume Methods for Hyperbolic Problems. Cambridge University Press. ISBN   0-521-81087-6.
  3. Hirsch, C. (1990). Numerical Computation of Internal and External Flows. Vol. 2. Wiley. ISBN   0-471-92452-0.

Further reading