Stencil (numerical analysis)

Last updated
The Crank-Nicolson stencil for a 1D problem Crank-Nicolson-stencil.svg
The Crank–Nicolson stencil for a 1D problem

In mathematics, especially the areas of numerical analysis concentrating on the numerical solution of partial differential equations, a stencil is a geometric arrangement of a nodal group that relate to the point of interest by using a numerical approximation routine. Stencils are the basis for many algorithms to numerically solve partial differential equations (PDE). Two examples of stencils are the five-point stencil and the Crank–Nicolson method stencil.

Contents

Stencils are classified into two categories: compact and non-compact, the difference being the layers from the point of interest that are also used for calculation.

In the notation used for one-dimensional stencils n-1, n, n+1 indicate the time steps where timestep n and n-1 have known solutions and time step n+1 is to be calculated. The spatial location of finite volumes used in the calculation are indicated by j-1, j and j+1.

Etymology

Graphical representations of node arrangements and their coefficients arose early in the study of PDEs. Authors continue to use varying terms for these such as "relaxation patterns", "operating instructions", "lozenges", or "point patterns". [1] [2] The term "stencil" was coined for such patterns to reflect the concept of laying out a stencil in the usual sense over a computational grid to reveal just the numbers needed at a particular step. [2]

Calculation of coefficients

The finite difference coefficients for a given stencil are fixed by the choice of node points. The coefficients may be calculated by taking the derivative of the Lagrange polynomial interpolating between the node points, [3] by computing the Taylor expansion around each node point and solving a linear system, [4] or by enforcing that the stencil is exact for monomials up to the degree of the stencil. [3] For equi-spaced nodes, they may be calculated efficiently as the Padé approximant of , where is the order of the stencil and is the ratio of the distance between the leftmost derivative and the left function entries divided by the grid spacing. [5]

See also

Related Research Articles

<span class="mw-page-title-main">Partial differential equation</span> Type of differential equation

In mathematics, a partial differential equation (PDE) is an equation which computes a function between various partial derivatives of a multivariable function.

Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain differential equations. The idea is to write the solution of the differential equation as a sum of certain "basis functions" and then to choose the coefficients in the sum in order to satisfy the differential equation as well as possible.

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.

Pseudo-spectral methods, also known as discrete variable representation (DVR) methods, are a class of numerical methods used in applied mathematics and scientific computing for the solution of partial differential equations. They are closely related to spectral methods, but complement the basis by an additional pseudo-spectral basis, which allows representation of functions on a quadrature grid. This simplifies the evaluation of certain operators, and can considerably speed up the calculation when using fast algorithms such as the fast Fourier transform.

<span class="mw-page-title-main">Level-set method</span> Conceptual framework used in numerical analysis of surfaces and shapes

Level-set methods (LSM) are a conceptual framework for using level sets as a tool for numerical analysis of surfaces and shapes. The advantage of the level-set model is that one can perform numerical computations involving curves and surfaces on a fixed Cartesian grid without having to parameterize these objects. Also, the level-set method makes it very easy to follow shapes that change topology, for example, when a shape splits in two, develops holes, or the reverse of these operations. All these make the level-set method a great tool for modeling time-varying objects, like inflation of an airbag, or a drop of oil floating in water.

<span class="mw-page-title-main">Numerical differentiation</span> Use of numerical analysis to estimate derivatives of functions

In numerical analysis, numerical differentiation algorithms estimate the derivative of a mathematical function or function subroutine using values of the function and perhaps other knowledge about the function.

Numerical methods for partial differential equations is the branch of numerical analysis that studies the numerical solution of partial differential equations (PDEs).

In mathematics a radial basis function (RBF) is a real-valued function whose value depends only on the distance between the input and some fixed point, either the origin, so that , or some other fixed point , called a center, so that . Any function that satisfies the property is a radial function. The distance is usually Euclidean distance, although other metrics are sometimes used. They are often used as a collection which forms a basis for some function space of interest, hence the name.

<span class="mw-page-title-main">Computational electromagnetics</span> Branch of physics

Computational electromagnetics (CEM), computational electrodynamics or electromagnetic modeling is the process of modeling the interaction of electromagnetic fields with physical objects and the environment using computers.

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 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.

A parabolic partial differential equation is a type of partial differential equation (PDE). Parabolic PDEs are used to describe a wide variety of time-dependent phenomena, including heat conduction, particle diffusion, and pricing of derivative investment instruments.

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.

<span class="mw-page-title-main">Finite element method</span> Numerical method for solving physical or engineering problems

The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat transfer, fluid flow, mass transport, and electromagnetic potential.

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.

Finite difference methods for option pricing are numerical methods used in mathematical finance for the valuation of options. Finite difference methods were first applied to option pricing by Eduardo Schwartz in 1977.

The Kansa method is a computer method used to solve partial differential equations. Its main advantage is it is very easy to understand and program on a computer. It is much less complicated than the finite element method. Another advantage is it works well on multi variable problems. The finite element method is complicated when working with more than 3 space variables and time.

The closest point method (CPM) is an embedding method for solving partial differential equations on surfaces. The closest point method uses standard numerical approaches such as finite differences, finite element or spectral methods in order to solve the embedding partial differential equation (PDE) which is equal to the original PDE on the surface. The solution is computed in a band surrounding the surface in order to be computationally efficient. In order to extend the data off the surface, the closest point method uses a closest point representation. This representation extends function values to be constant along directions normal to the surface.

Probabilistic numerics is an active field of study at the intersection of applied mathematics, statistics, and machine learning centering on the concept of uncertainty in computation. In probabilistic numerics, tasks in numerical analysis such as finding numerical solutions for integration, linear algebra, optimization and simulation and differential equations are seen as problems of statistical, probabilistic, or Bayesian inference.

References

  1. Emmons, Howard W. (1 October 1944). "The numerical solution of partial differential equations" (PDF). Quarterly of Applied Mathematics. 2 (3): 173–195. doi: 10.1090/qam/10680 . Retrieved 17 April 2017.
  2. 1 2 Milne, William Edmund (1953). Numerical solution of differential equations (1st ed.). Wiley. pp. 128–131. OCLC   527661 . Retrieved 17 April 2017.
  3. 1 2 Fornberg, Bengt; Flyer, Natasha (2015). "Brief Summary of Finite Difference Methods". A Primer on Radial Basis Functions with Applications to the Geosciences. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611974041.ch1. ISBN   9781611974027 . Retrieved 9 April 2017.
  4. Taylor, Cameron. "Finite Difference Coefficients Calculator". web.media.mit.edu. Retrieved 9 April 2017.
  5. Fornberg, Bengt (January 1998). "Classroom Note: Calculation of Weights in Finite Difference Formulas". SIAM Review. 40 (3): 685–691. Bibcode:1998SIAMR..40..685F. doi:10.1137/S0036144596322507.