拟谱法

拟谱法（Pseudo-spectral methods）也称为离散变数表示（discrete variable representation、DVR）法，是在应用数学及计算科学中求解偏微分方程用的数值分析方法。拟谱法和谱方法有密切关系，但在谱方法中基底函数中使用了拟谱的基底函数，也就是可以在分割网格上表示的函数。此作法简化一些运算子的计算，在使用快速算法（例如快速傅里叶变换）时可以加速计算速度。

## 说明

考虑以下的初值问题

$$i \frac{\partial}{\partial t} \psi(x, t) = \Bigl[-\frac{\partial^2}{\partial x^2} + V(x) \Bigr] \psi(x,t), \qquad\qquad \psi(t_0) = \psi_0$$

有周期性条件$\psi(x+1, t) = \psi(x, t)$。这个例子是势能为$V(x)$之粒子的薛定谔方程，不过其结构可适用到其他应用。在许多实务上的偏微分方程中，其中有一项是和导数（例如是动能相关的量）有关，另一项则是和另一个函数（此处为势能）的乘积。

在谱方法中，其解$\psi$会展开为一组适合基底函数的组合，例如平面波。

$$\psi(x,t) = \frac{1}{\sqrt{2\pi}} \sum_n c_n(t) e^{2\pi i n x} .$$

将解代入，并且计算系数的方程，可以得到系数的常微分方程

$$i\frac{d}{dt} c_n(t) = (2\pi n)^2 c_n + \sum_k V_{n-k} c_k,$$

而其元素$V_{nk}$可以透过显式的傅立叶转换求得

$$V_{n-k} = \int_0^{1} V(x) \ e^{2\pi i (k-n) x} dx .$$

若将$N$基底函数的展开到一定项次后截断，并且找$c_n(t)$的解，就可以得到偏微分方程的解。一般而言会用数值方法进行，例如龙格－库塔法。为了数值解，常微分方程的右侧需重复计算在许多不同时间间隔下的值。此时，谱方法有个和势能项$V(x)$有关的主要问题。

在谱方法下，和势能函数$V(x)$的相乘会转换为向量和矩阵的乘法，其复杂度是$N^2$，而且在求解系数的微分方程时，需要另外去计算矩阵元素$V_{nk}$，这也需要时间。

在拟谱法中，会用不同的方式来计算。给定系数$c_n(t)$，会用反离散傅立叶转换来计算函数$\psi$在离散格点$x_j = 2\pi j/N$下的值。在格点上，计算函数的乘积 $\psi'(x_i, t) = V(x_i) \psi(x_i, t)$，再用傅立叶转换转换回来，可以得到一组新的系数$c'_n(t)$，来代替矩阵乘积运算$\sum_k V_{n-k} c_k(t)$。

可以证明二个方法有类似的精准度，而且拟谱法可以使用快速傅立叶转换，其时间复杂度为$O(N\ln N)$，理论上比矩阵乘法要快很多。而且，可以直接计算函数$V(x)$，不用再经过额外的积分运算。

## 技术讨论

若用比较抽象的方式来描述，拟谱法是处理在偏微分方程中二个函数$V(x)$和$f(x)$的乘积。为了简化表示式，省略掉函数中时间的自变数。在概念上，拟谱法包括三个步骤：

- 将$f(x)$以及$\tilde{f}(x) = V(x)f(x)$扩展为由有限多个基底函数形成的组合（此为谱方法）。
- 针对一组给定的基底函数，找到一组分割方式可以将基底函数的纯量积转换为在格点上的加权和。
- 在每一个格点将$V$和$f$相乘，来计算函数的乘积。

### 基底的展开

函数$f$和$\tilde f$可以用一组有限基底的函数来扩展$\{\phi_n\}_{n = 0,\ldots,N}$：

$$f(x) = \sum_{n=0}^N c_n \phi_n(x)$$

$$\tilde f(x) = \sum_{n=0}^N \tilde c_n \phi_n(x)$$

为了简化起见，令基底是正交且正规化的，$\langle \phi_n, \phi_m \rangle = \delta_{nm}$，利用内积$\langle f, g \rangle = \int_a^b f(x) \overline{g(x)} dx$配合适当的边界$a,b$，其系数为

$$c_n = \langle f, \phi_n \rangle$$

$$\tilde c_n = \langle \tilde f, \phi_n \rangle$$

配合一些计算可得

$$\tilde c_n = \sum_{m=0}^N V_{n-m} c_m$$

而$V_{n-m} = \langle V\phi_m, \phi_n \rangle$。这是谱方法的基础。为了区分$\phi_n$的基底以及正交的基底，有时会将上述扩展称为有限基底表示（Finite Basis Representation、FBR）。

### 分割

针对给定基底$\{\phi_n\}$以及$N+1$个基底函数，可以设法找到分割方式，也就是$N+1$个点以及加权，使得

$$\langle \phi_n, \phi_m \rangle = \sum_{i=0}^N w_i \phi_n(x_i) \overline{\phi_m(x_i)} \qquad\qquad n,m = 0,\ldots,N$$

特别的例子包括多项式的高斯求积以及平面波的离散傅里叶变换，特别需注意的是格点及加权$x_i,w_i$都是基底及数量$N$的函数。

利用分割方式，可以透过格点上的值，以另一种方式来表示函数$f(x), \tilde f(x)$的数值。此表示法有时称为离散变数表示法（Discrete Variable Representation、DVR），完全等效于基底的展开。

$$f(x_i) = \sum_{n=0}^N c_n \phi_n(x_i)$$

$$c_n = \langle f, \phi_n \rangle = \sum_{n=0}^{N} w_i f(x_i) \overline{\phi_n(x_i)}$$

### 相乘

和函数$V(x)$的相乘会在格点上进行

$$\tilde f(x_i) = V(x_i) f(x_i).$$

一般来说这里会有一些近似，可以计算其中一个系数$\tilde c_n$:

$$\tilde c_n = \langle \tilde f, \phi_n \rangle = \sum_i w_i \tilde f(x_i) \overline{\phi_n(x_i)} = \sum_i w_i V(x_i) f(x_i) \overline{\phi_n(x_i)}$$

利用谱方法，对应的系数会是$\tilde c_n = \langle Vf, \phi_n \rangle$。拟谱法则会用以下皂的近似来处理

$$\langle Vf, \phi_n \rangle \approx \sum_i w_i V(x_i) f(x_i) \overline{\phi_n(x_i)}.$$

若乘积可以用$Vf$给定的有限基底函数组合来表现，则上式在给定分割方式上会完全正确。

## 特殊的拟谱架构

### 傅立叶法

若问题中有周期性的边界条件，其周期为$[0,L]$，基底函数可以用平面波来产生。

$$\phi_n(x) = \frac{1}{\sqrt{L}} e^{-\imath k_n x}$$

其中$k_n = (-1)^n \lceil n/2 \rceil 2\pi/L$，而$\lceil\cdot\rceil$是取整函数。

在$n_{\text{max}} = N$处截断的分割为离散傅立叶转换，格点会平均分布$x_i = i \Delta x$，间隔为$\Delta x = L / (N+1)$，各点的加权会是相同旳定值$w_i = \Delta x$。

在讨论误差时，需注意到平面波的乘积也是平面波，$\phi_{a} + \phi_b = \phi_c$，$c \leq a+b$。因此，定量来说，若函数$f(x), V(x)$可以用$N_f, N_V$基底函数足够准确的呈现，只要用$N_f + N_V$个基底函数，即可用拟谱法得到足够准确的结果。

平面波的扩展一般效果较差，需要许多的基底函数才能收敛。不过。基底展开和格点表示的转换可以用快速傅立叶转换进行，其时间复杂度较低，为$N \ln N$。因此，平面波是拟谱法中常用的一种基底函数。

### 多项式

另一种常见的展开方式是多项式，此处会使用高斯求积（Gaussian quadrature），其中提到可以找到加权系数$w_i$及格点$x_i$使得

$$\int_a^b w(x) p(x) dx = \sum_{i=0}^N w_i p(x_i)$$

对任意的$2N+1$次或是更低次的多项式$p(x)$都成立。一般而言，加权函数$w(x)$及范围$a,b$都是根据特定问题所选定的，因此会选择几种分割方式中的一种。若要用在拟谱法，需选择基底函数为$\phi_n(x) = \sqrt{w(x)} P_n(x)$，其中$P_n$为$n$阶多项式，有以下特性

$$\int_a^b w(x) P_n(x) P_m(x) dx = \delta_{mn}.$$

在上述条件下，the $\phi_n$会是正交基底，其内积为$\langle f, g \rangle = \int_a^b f(x) \overline{g(x)} dx$。此基底以及分割点可以用在拟谱法中。

有关其误差，若$f$可以用$N_f$个基底函数很好的呈现，而$V$可以用$N_V$阶多项式很好的呈现，则其积可以用前$N_f+N_V$个基底函数很好的呈现。且拟谱法用该数量的基底函数，会有足够准确的结果。

在一些标准问题中，会出现这些多项式。例如量子简谐振动子可以扩展为埃尔米特多项式，而在转动问题中，会用雅可比多项式来定义相关的勒壤得多项式。