HOME

TheInfoList



OR:

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: :f'(x) \approx \frac 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'': :f(x \pm h) = f(x) \pm h f'(x) + \fracf''(x) \pm \frac f^(x) + O_(h^4). \qquad (E_). Evaluating (E_)-(E_) gives us :f(x+h) - f(x-h) = 2hf'(x) + \fracf^(x) + O_1(h^4). \qquad (E_1). Note that the residual term O1(''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 :f(x \pm 2h) = f(x) \pm 2h f'(x) + \frac f''(x) \pm \frac f^(x) + O_(h^4). \qquad (E_) and (E_)-(E_) gives us :f(x+2h) - f(x-2h) = 4hf'(x) + \fracf^(x) + O_2(h^4). \qquad (E_2). In order to eliminate the terms of ƒ(3)(''x''), calculate 8 × (''E''1) − (''E''2) :8f(x+h) - 8f(x-h) - f(x+2h) + f(x-2h) = 12h f'(x) + O(h^4) \, 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 : \frac=f'(x)-\frac f^(x) h^4+O(h^5) 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 f'(x) 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 : f''(x) \approx \frac : f^(x) \approx \frac : f^(x) \approx \frac 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 :\ell_j(\xi) = \prod_^ \frac, where the interpolation points are : x_0=x-2h,\quad x_1=x-h,\quad x_2=x,\quad x_3=x+h,\quad x_4=x+2h. Then, the quartic polynomial p_4(x) interpolating ƒ(''x'') at these five points is : p_4(x) = \sum\limits_^4 f(x_j) \ell_j(x) and its derivative is : p_4'(x) = \sum\limits_^4 f(x_j) \ell'_j(x). So, the finite difference approximation of ƒ ′(''x'') at the middle point ''x'' = ''x''2 is : f'(x_2) = \ell_0'(x_2) f(x_0) + \ell_1'(x_2) f(x_1) + \ell_2'(x_2) f(x_2) + \ell_3'(x_2) f(x_3) + \ell_4'(x_2) f(x_4) + O(h^4) 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: : \nabla^2 f(x,y) \approx \frac. 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: \begin \frac= \frac - 2\frac\Delta x^2 + \cdots \end \begin \frac= \frac - 2\frac\Delta y^2 + \cdots \end If we assume \Delta x=\Delta y=h: \begin \nabla^2 f &= \frac+\frac\\ &= \frac - 4\frach^2 + \cdots\\ &= \frac + O\left(h^2\right)\\ \end


See also

* * *


References

* {{citation , first1=Milton , last1=Abramowitz , author1-link=Milton Abramowitz , first2=Irene A. , last2=Stegun , author2-link=Irene Stegun , year=1970 , title=
Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables ''Abramowitz and Stegun'' (''AS'') is the informal name of a 1964 mathematical reference work edited by Milton Abramowitz and Irene Stegun of the United States National Bureau of Standards (NBS), now the ''National Institute of Standards and Te ...
, publisher=Dover . Ninth printing. Table 25.2. Numerical differential equations