Five-point stencil


Five-point stencil

In numerical analysis, given a square grid in one or two dimensions, the five-point stencil of a point in the grid is made up of the point itself together with its four "neighbors". It is used to write finite difference approximations to derivatives at grid points.

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

: {x-2h, x-h, x, x+h, x+2h}.

First derivative

The first derivative of a function ƒ of a real variable at a point "x" can be approximated using a five-point stencil as

:f'(x) approx frac{-f(x+2 h)+8 f(x+h)-8 f(x-h)+f(x-2h)}{12 h}

Obtaining the formula

This formula can be obtained by writing out the four Taylor series 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) + frac{h^2}{2}f"(x) pm frac{h^3}{6} f^{(3)}(x) + O_{1pm}(h^4). qquad (E_{1pm}).

Evaluating ("E" 1+) − ("E" 1−) gives us

:f(x+h) - f(x-h) = 2hf'(x) + frac{h^3}{3}f^{(3)}(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) + 2h^2 f"(x) pm frac{4h^3}{3} f^{(3)}(x) + O_{2pm}(h^4). qquad (E_{2pm})

: (E_{2+})-(E_{2-})

gives us

:f(x+2h) - f(x-2h) = 4hf'(x) + frac{8h^3}{3}f^{(3)}(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.

Estimated error

The error in this approximation is of order "h" 4. That can be seen from the expansion

: frac{-f(x+2 h)+8 f(x+h)-8 f(x-h)+f(x-2h)}{12 h}=f'(x)-frac{1}{30} f^{(5)}(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. Alternatively, apply Richardson extrapolation to the central difference approximation to f'(x) on grids with spacing 2"h" and "h".

Higher derivatives

The centered difference formulas for five-point stencils approximating second, third, and fourth derivatives are

: egin{align} f"(x) &approx frac{-f(x+2 h)+16 f(x+h)-30 f(x) + 16 f(x-h) - f(x-2h)}{12 h^2}, \ f^{(3)}(x) &approx frac{f(x+2 h)-2 f(x+h) + 2 f(x-h) - f(x-2h)}{2 h^3}, \ f^{(4)}(x) &approx frac{f(x+2 h)-4 f(x+h)+6 f(x) - 4 f(x-h) + f(x-2h)}{h^4}.end{align}

Estimated errors

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 polynomials

:ell_j(xi) = prod_{i=0,, i eq j}^{k} frac{xi-x_i}{x_j-x_i},

where the interpolation points are

: egin{align}x_0=x-2h,quad x_1=x-h,quad x_2=x,quad x_3=x+h,quad x_4=x+2h.end{align}

Then, the quartic polynomial p_4(x) interpolating ƒ("x") at these five points is

: egin{align}p_4(x) = sumlimits_{j=0}^4 f(x_j) ell_j(x)end{align}

and its derivative is

: egin{align} p_4'(x) = sumlimits_{j=0}^4 f(x_j) ell'_j(x).end{align}

So, the finite difference approximation of ƒ ′("x") at the middle point "x" = "x"2 is

: egin{align}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) end{align}

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.

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

:{(x-h, y), (x, y), (x+h, y), (x, y-h), (x, y+h)}. ,

This stencil is often used to approximate the Laplacian of a function of two variables:

: Delta f(x,y) approx frac{f(x-h,y) + f(x+h,y) + f(x,y-h) + f(x,y+h) - 4f(x,y)}{h^2}.

The error in this approximation is "O"("h" 2). [Abramowitz & Stegun, 25.3.30]

ee also

* Stencil jumping

Notes

References

*. Ninth printing. Table 25.2.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Stencil jumping — Stencil jumping, at times called stencil walking, is an algorithm to locate the grid element enclosing a given point for any structured mesh. In simple words, given a point and a structured mesh, this algorithm will help locate the grid element… …   Wikipedia

  • Stencil codes — are computer codes that update array elements according to some fixed pattern, called stencils,Sloot, Peter M.A. et al. (May 28, 2002) [http://books.google.com/books?id=qVcLw1UAFUsC pg=PA843 dq=stencil+array sig=g3gYXncOThX56TUBfHE7hnlSxJg#PPA843 …   Wikipedia

  • Five Points — may be:Census recognized communities in the U.S.: *Five Points, Alabama *Five Points, Florida *Five Points, North Carolina *Five Points, Ohio *Five Points, PennsylvaniaU.S. and Canadian neighborhoods: *Five Points (Athens), in Athens, Georgia… …   Wikipedia

  • Stencil (numerical analysis) — 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… …   Wikipedia

  • Point — Point, n. [F. point, and probably also pointe, L. punctum, puncta, fr. pungere, punctum, to prick. See {Pungent}, and cf. {Puncto}, {Puncture}.] 1. That which pricks or pierces; the sharp end of anything, esp. the sharp end of a piercing… …   The Collaborative International Dictionary of English

  • Point lace — Point Point, n. [F. point, and probably also pointe, L. punctum, puncta, fr. pungere, punctum, to prick. See {Pungent}, and cf. {Puncto}, {Puncture}.] 1. That which pricks or pierces; the sharp end of anything, esp. the sharp end of a piercing… …   The Collaborative International Dictionary of English

  • Point net — Point Point, n. [F. point, and probably also pointe, L. punctum, puncta, fr. pungere, punctum, to prick. See {Pungent}, and cf. {Puncto}, {Puncture}.] 1. That which pricks or pierces; the sharp end of anything, esp. the sharp end of a piercing… …   The Collaborative International Dictionary of English

  • Point of concurrence — Point Point, n. [F. point, and probably also pointe, L. punctum, puncta, fr. pungere, punctum, to prick. See {Pungent}, and cf. {Puncto}, {Puncture}.] 1. That which pricks or pierces; the sharp end of anything, esp. the sharp end of a piercing… …   The Collaborative International Dictionary of English

  • Point of contrary flexure — Point Point, n. [F. point, and probably also pointe, L. punctum, puncta, fr. pungere, punctum, to prick. See {Pungent}, and cf. {Puncto}, {Puncture}.] 1. That which pricks or pierces; the sharp end of anything, esp. the sharp end of a piercing… …   The Collaborative International Dictionary of English

  • Point of order — Point Point, n. [F. point, and probably also pointe, L. punctum, puncta, fr. pungere, punctum, to prick. See {Pungent}, and cf. {Puncto}, {Puncture}.] 1. That which pricks or pierces; the sharp end of anything, esp. the sharp end of a piercing… …   The Collaborative International Dictionary of English