In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, given a
square grid
In geometry, the square tiling, square tessellation or square grid is a regular tiling of the Euclidean plane. It has Schläfli symbol of meaning it has 4 squares around every vertex.
Conway called it a quadrille.
The internal angle of the s ...
in one or two dimensions, the five-point stencil of a point in the grid is a
stencil
Stencilling produces an image or pattern on a surface, by applying pigment to a surface through an intermediate object, with designed holes in the intermediate object, to create a pattern or image on a surface, by allowing the pigment to reach ...
made up of the point itself together with its four "neighbors". It is used to write
finite difference
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for t ...
approximations to
derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. F ...
s at grid points. It is an example for
numerical differentiation
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.
Finite differences
The simplest ...
.
In one dimension
In one dimension, if the spacing between points in the grid is ''h'', then the five-point stencil of a point ''x'' in the grid is
:
1D first derivative
The first derivative of a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
ƒ of a
real
Real may refer to:
Currencies
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Music Albums
* ''Real'' (L'Arc-en-Ciel album) (2000)
* ''Real'' (Bright album) (2010)
...
variable at a point ''x'' can be approximated using a five-point stencil as:
:
Notice that the center point ƒ(''x'') itself is not involved, only the four neighboring points.
Derivation
This formula can be obtained by writing out the four
Taylor series
In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor serie ...
of ƒ(''x'' ± ''h'') and ƒ(''x'' ± 2''h'') up to terms of ''h''
3 (or up to terms of ''h''
5 to get an error estimation as well) and solving this system of four equations to get ƒ
′(''x''). Actually, we have at points ''x'' + ''h'' and ''x'' − ''h'':
:
Evaluating
gives us
:
Note that the residual term O
1(''h''
4) should be of the order of ''h''
5 instead of ''h''
4 because if the terms of ''h''
4 had been written out in (''E''
1+) and (''E''
1−), it can be seen that they would have canceled each other out by ƒ(''x'' + ''h'') − ƒ(''x'' − ''h''). But for this calculation, it is left like that since the order of error estimation is not treated here (cf below).
Similarly, we have
:
and
gives us
:
In order to eliminate the terms of ƒ
(3)(''x''), calculate 8 × (''E''
1) − (''E''
2)
:
thus giving the formula as above. Note: the coefficients of f in this formula, (8, -8,-1,1), represent a specific example of the more general
Savitzky–Golay filter
A Savitzky–Golay filter is a digital filter that can be applied to a set of digital data points for the purpose of smoothing the data, that is, to increase the precision of the data without distorting the signal tendency. This is achieved, in ...
.
Error estimate
The error in this approximation is of
order ''h''
4. That can be seen from the expansion
:
[Abramowitz & Stegun, Table 25.2]
which can be obtained by expanding the left-hand side in a
Taylor series
In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor serie ...
. Alternatively, apply
Richardson extrapolation
In numerical analysis, Richardson extrapolation is a sequence acceleration method used to improve the rate of convergence of a sequence of estimates of some value A^\ast = \lim_ A(h). In essence, given the value of A(h) for several values of h, we ...
to the
central difference
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for the ...
approximation to
on grids with spacing 2''h'' and ''h''.
1D higher-order derivatives
The centered difference formulas for five-point stencils approximating second, third, and fourth derivatives are
:
:
:
The errors in these approximations are ''O''(''h''
4), ''O''(''h''
2) and ''O''(''h''
2) respectively.
Relationship to Lagrange interpolating polynomials
As an alternative to deriving the finite difference weights from the Taylor series, they may be obtained by differentiating the
Lagrange polynomial
In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree of a polynomial, degree that polynomial interpolation, interpolates a given set of data.
Given a data set of graph of a function, coordinate p ...
s
:
where the interpolation points are
:
Then, the quartic polynomial
interpolating ƒ(''x'') at these five points is
:
and its derivative is
:
So, the finite difference approximation of ƒ
′(''x'') at the middle point ''x'' = ''x''
2 is
:
Evaluating the derivatives of the five Lagrange polynomials at ''x''=''x''
2 gives the same weights as above. This method can be more flexible as the extension to a non-uniform grid is quite straightforward.
In two dimensions
In two dimensions, if for example the size of the squares in the grid is ''h'' by ''h'', the five point stencil of a point (''x'', ''y'') in the grid is
:
forming a pattern that is also called a
quincunx
A quincunx () is a geometric pattern consisting of five points arranged in a cross, with four of them forming a square or rectangle and a fifth at its center. The same pattern has other names, including "in saltire" or "in cross" in heraldry (dep ...
. This stencil is often used to approximate the
Laplacian
In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is the ...
of a function of two variables:
:
The error in this approximation is ''O''(''h''
2),
[Abramowitz & Stegun, 25.3.30] which may be explained as follows:
From the 3 point stencils for the second derivative of a function with respect to x and y:
If we assume
:
See also
*
*
*
References
* {{citation , first1=Milton , last1=Abramowitz , author1-link=Milton Abramowitz , first2=Irene A. , last2=Stegun , author2-link=Irene Stegun , year=1970 , title=
, publisher=Dover . Ninth printing. Table 25.2.
Numerical differential equations