从谱空间走到实际计算
谱方法用遍及整个区间的基底函数表示近似解;要真正计算,还须决定怎样取得系数,以及网格无法分辨的频率会发生什么事。考虑实值或复值、周期为 的函数,取等距网格。先取奇数个网格点,避开偶数网格需要另行指定的 Nyquist 频率惯例。
定义 5.6.1
(离散系数、三角插值与谱导数)
设 ,,并取 ,。对样本 ,定义
样本的谱导数是向量 ,其分量为 。
系数的归一化和指数的正负号都不可随便更改。我们先微分插值多项式 ,再取网格值。对选定频率范围内的三角多项式,这给出精确导数;但对产生同一组样本的任意函数,未必如此。
为什么插值公式成立?
定理 5.6.2
(离散正交性与插值)
若整数 都在 ,则 在 个网格点的平均值,在 时为一,否则为零。因此每个样本向量都满足 ,而且其插值函数在 、 张成的空间内唯一。
证明
(用等比和证明)
这个平均值是公比为 的等比和:当 整除 时为一,否则为零。由 ,只有两指数相等才会整除。同理,反向求和得到
因为这 个连续整数恰好代表模 的所有余数。代入系数公式便得 。若两个插值函数有相同样本,用正交性恢复其差的各系数:每个系数都是零样本的离散平均,故全为零,所以两者相同。
证明透视
频率窗口在证明中的作用
论证靠两个事实:除非 整除频率差,等比和为零;而窗口 恰好含 个连续整数。窗口用了两次,方向相反。对正交性,它够小: 排除了 的所有非零倍数。对插值,它够大:它与模 的每个剩余类都相交,所以对 的和是完整的和,给出 。唯一性只用到第一个事实。
如果把窗口放宽,第一个用途就失效。频率 与 相差 ,所以在五点网格上两个指数函数重合,任何一个的系数都无法恢复,这就是混叠。因此唯一性只在选定的有限维空间内成立,而不是在所有三角多项式之中。
用系数求导十分直接:一阶导数把 换成 ,二阶导数则换成 ;再反变换便得网格值。快速 Fourier 变换能加快这些求和,却不会改变插值函数,也不能补回网格没有解析的信息。
反例模式
偶数网格破坏对称窗口
人们很容易以为偶数个网格点也能沿用同一公式,取窗口 。取 ,即 ,以及 的采样值 。由于 ,五个频率共用四个网格点,离散平均给出 ,其余为零。所得 的采样值是 ,为数据的两倍,插值失败;而 在每个节点处都为零,唯一性也不成立。修正方法是 Nyquist 惯例:在偶数网格上,两个频率 各取权重 ,此例便恢复为 。
热方程及其能量
对周期边界的 ,其中 ,空间配点后得到常微分方程 。这里 指套用同一谱导数两次。由于 已属于 、 张成的空间,第二次套用再把系数乘以 。网格函数以 度量。
命题 5.6.3
(半离散能量衰减)
设 满足 ,。则
而且平均系数 不随时间改变。
证明
(由离散 Parseval 等式证明)
第一个等号是离散 Parseval 等式:写 ,把 展开为对 的二重和,对 取平均,再用刚证明的正交性,只保留 的项。各系数满足 ,因此
对 求和得能量恒等式;取 则得 。
概念视角代数
把谱导数看成反对称矩阵
把定义作用于单位采样向量,可把 写成显式的循环矩阵:当 为奇数时,
各元素为实数,交换 与 时变号,所以 ;其特征向量是网格上的指数函数,特征值为 。记 ,反对称性无需系数也能给出能量衰减:。
平均值模式保持不变,其余已表示的模式衰减。这是在精确算术下、只离散空间的结论,不能单凭它推断未解析初值的准确度,也不能推断某个时间积分法必定稳定。若用步长 的向前 Euler,每个系数乘上 。因此所有模式均不放大的充要条件是 。向后 Euler 的因子则是 ,对任何正步长均不放大;但时间误差仍须控制。
常见错误
(把半离散衰减搬到时间步进法上)
不等式 是常微分方程组的性质,而不是积分它的方法的性质。取 、,向前 Euler 步长 ,模式 每步乘以 ,振幅大小每步变为三倍,而半离散能量却在衰减。完全离散的方法需要自己的条件,这里是 ,或改用隐式方法。
例题 5.6.4
(分开空间误差与时间误差)
设 、,初值为 。两个频率都在空间中,半离散问题的精确解为 ;对这组初值,它也等于连续解的样本。若用向前 Euler,,一步后两个振幅变为 和 ;该时刻精确振幅却是 和 。网格虽解析了初始函数,时间步长仍带来明显误差。
混叠不是微小的舍入误差
例题 5.6.5
(两个不同波形,完全相同的样本)
在同一五点网格上,,因此 。由 的样本得到的插值函数是 ,计算导数为 。真实导数却是 。在 ,两者分别是 和 。只使用这些样本的任何算法都无法判断原来是哪个波形。
即使相乘前的函数都已表示,相乘也会产生同样问题:,但在五点网格上 。因此逐点相乘后再插值得到 ,而不是原来含频率四的多项式。针对非线性运算设计的补零和滤波可以处理混叠;仅仅对乘积做快速变换不会自动消除它。
常见错误
(把 当成任何被采样函数的导数)
谱导数微分的是插值函数,所以只有当被采样的函数属于 、 张成的空间时才精确。对五点网格上的 ,在 的计算值是 ,真实导数却是 。快速变换或双精度都不能改变这一点:误差来自网格无法表示的频率,只有加密网格或采用已解析的表示才能消除。
什么条件下加密网格有用?
命题 5.6.6
(由系数尾和控制网格导数误差)
设 ,且 、;令 为 中与 模 同余的唯一整数。则
证明
(把频率折回窗口来证明)
绝对收敛允许采样及逐项微分,所以 。在网格上 ,因此 。用正交性并交换绝对收敛的求和,得 。于是
相减得 。 的项为零,因为此时 ,由此得第一个不等式。当 ,有 ,所以 。
当 ,右边尾和趋向零。系数衰减更快可以带来更快的收敛,但“谱”一字本身不保证指数收敛,尤其当周期延拓不光滑。此估计假设样本精确,并未计入舍入误差。
例题 5.6.7
(等比系数给出等比收敛速度)
取 。令 ,把两个等比级数相加得
假设成立:。尾和为 ,所以界变为
当 (),界为 ,并不比平凡界 好:网格这么粗时,估计没有提供信息。 时界为 , 时为 , 时为 。每多加一对网格点,界大约减半,这就是从系数继承的等比速度。
练习与解答
快速检查
(当 , 样本的谱导数是什么?)
把频率对 取余数。
解答 · 答案
在节点上 ,所以插值函数是 ,导数样本是 。真实导数样本则是 ,一般不同。
快速检查
(当 、,向前 Euler 步长 ,求 模式的因子。)
每个模式乘以 。
解答 · 答案
因子为 ,反复步进时该模式的大小会增长。半离散能量不等式不能照搬到这个不稳定的时间离散法。
快速检查
(谱导数对常数向量做什么?)
找出唯一非零的系数。
解答 · 答案
只有零频率系数非零,而它乘以 ,故结果为零。在热方程中同一模式保持不变,对应离散平均值守恒。
快速检查
(在五点网格上,比较 的样本平方后再插值,与先插值再平方。)
利用 。
解答 · 答案
的插值函数就是 本身,所以先插值再平方得 ;样本平方后再插值则得 。它们在五个节点相同,但一般点不同,所以插值和相乘不可交换次序。