Five-point stencil

Five-point stencil 在一维和二维中的形式:

在数值分析中,给定一个一维或二维的网格,某一点的 Five-point stencil(FPS)即为该点加上它邻近的四个点。FPS主要用于求解导数在格点上的有限差分近似。

One dimension

在一维情况下,如果格点宽度为 $h$ ,对于点 $x$ 的FPS为:
$$
{x-2h,x-h,x,x+h,x+2h}
$$

一阶导数

$$
f’(x)\approx\frac{-f(x+2h)+8f(x+h)-8f(x-h)+f(x-2h)}{12h}
$$

推导过程

将$f(x)$在点$x\pm h,x\pm 2h$处进行Taylor展开:

$$
f(x\pm h)=f(x)\pm hf’(x)+\frac{h^2}{2!}f’’(x)\pm\frac{h^3}{3!}f^{(3)}(x)+O_{1\pm}(h^4)
$$

$$
f(x\pm2h)=f(x)\pm2hf’(x)+\frac{4h^2}{2!}f’’(x)\pm\frac{8h^3}{3!}f^{(3)}(x)+O_{2\pm}(h^4)
$$

分别相消有:

$$
f(x+h)-f(x-h)=2hf’(x)+\frac{h^3}{3}f^{(3)}(x)+O_1(h^4)
$$

$$
f(x+2h)-f(x-2h)=4hf’(x)+\frac{8h^3}{3}f^{(3)}(x)+O_2(h^4)
$$

消去3阶项有:

$$
8f(x+h)-8f(x-h)-f(x+2h)+f(x-2h)=12hf’(x)+O(h^4)
$$

误差

$$
\frac{-f(x+2h)+8f(x+h)-8f(x-h)+f(x-2h)}{12h}=f’(x)-\frac{1}{30}f^{(5)}(x)h^4+O(h^5)
$$

所以误差为$h^4$量级。

高阶导数

同样的方法可以推导出更高阶的导数:

$$
f’’(x)\approx\frac{-f(x+2h)+16f(x+h)-30f(x)+16f(x-h)-f(x-2h)}{12h^2}
$$

$$
f^{(3)}(x)\approx\frac{f(x+2h)-2f(x+h)+2f(x-h)-f(x-2h)}{2h^3}
$$

$$
f^{(4)}(x)\approx\frac{f(x+2h)-4f(x+h)+6f(x)-4f(x-h)+f(x-2h)}{h^4}
$$

误差分别为$O(h^4),O(h2),O(h^2)$量级。


更多内容参照维基百科:

  转载请注明: 石锅拌饭 Five-point stencil

 上一篇
一个有关二分法的面试题 一个有关二分法的面试题
问题:给定一个有序数组,再给定一个数c,判断数组中是否存在两个数a,b,满足a + b = c。要求时间复杂度$O(n)$,空间复杂度$O(1)$。 解决方法:利用首尾两个指针,计算首尾的和,如果小于c,就移动首指针+1,否则就移动尾指针-
2018-12-04
下一篇 
黄金分割搜索 黄金分割搜索
适用于,一维单峰函数搜索最小值或者最大值。 核心思想:基于函数是一维单峰的特性,通过三个点来判断函数的大致走向,并且可以知道最小值一定落在已知最小点的相邻两点所界定的区间内。所以可以通过在区间内插入新的点,来逐步缩小最小值的所在的区间。 例
2018-12-04
  目录