有限差分法

阐述

有限差分法是将微分方程中的微分转变为差分的近似。例如，给定一维边值问题

$$-u_{xx}=f;\quad u(0)=u(1)=0$$

可以进行差分

$$\frac{\mathrm d^2u}{\mathrm dx^2}=\frac{u(x+h)-2u(x)+u(x-h)}{h^2}+O(h^2)$$

这个近似具有 $O(h^2)$ 精度，并且产生的线性方程是三对角矩阵

$$\begin{pmatrix}-2&1&&&\\1&-2&1&&\\&1&-2&1&\\&&\ddots&\ddots&\ddots\end{pmatrix}u_n=f_n$$

或者也可以采用更高阶的近似，但是带宽也会增加。$m$ 阶近似带来的就是 $m$ 带宽。

实例

周期性边界条件的快速解法

$$-u_{xx}=f;\quad u(0)=u(1),u'(0)=u'(1)$$

如果利用平移不变的特点，就能发展出任意阶有限差分在 $O(n\log n)$ 复杂度内求解的方法，这需要用到 离散 Fourier 变换。定义

$$x_i=i/n;\quad i=0,\cdots,n-1$$

则可以离散化得到：

$$A_n=F\Lambda F^*$$

因此求解只需要 3 步：

1. 计算 $\hat f_n=F^*f_n$
2. 求解 $\Lambda\hat u_n=\hat f_n$
3. 计算 $F^*u_n=\hat u_n$

不过，直接求解会发现 $\Lambda$ 的第一个元素是 0，这是因为周期性边界条件本质上允许增加任意的常数。需要通过指定 $u$ 在 $[0,1]$ 上的平均值来确定 $u$：

$$g=\int_0^1u(x)\mathrm dx\approx \frac1n\sum_{j}u_j=\frac{\hat u_0}{\sqrt n}$$

只需要将这个等式替换掉原来的奇异行就可以了。

Dirichlet 边界条件的快速解法

$$-u_{xx}=f; u(0)=a,u(1)=b$$

性质

$-u_{xx}=f$	$A_n$
smooth solution	order-m approximation
locality	boundedness
translational invariant	Toeplitz
symmeric about x = 1/2	odd/even solution deoupled

相关内容

参考文献