引言
有限差分把微分方程化为代数方程,但我们仍须求解所得的线性系统。本节以正方形上的 Dirichlet Poisson 问题为例,分清三个对象:连续问题的精确函数、网格方程的精确解,以及迭代所得的近似解。前两者之差是离散误差;后两者之差则是线性求解器误差。
动机
假设薄板的边界温度已知,板内有稳定热源,适当规范化后可用 建模。五点差分格式比较每个内部节点与四个邻点的数值。即使某邻点紧接内部未知量,边界值仍是已知数据。我们会证明离散系统解的存在唯一性,估计网格误差,并解释简单迭代为何在细网格上可能很慢。
定义与设定
定义 3.5.1
(五点 Dirichlet 问题)
令 ,,,网格点为 。当 或 等于 或 时,指定边界值 。对 ,定义
离散方程为 ,其中 。上式直接保留边界节点;若矩阵只作用于内部未知量,必须把已知边界项移至右边。下文最大范数包括边界节点。对零边界向量,内部欧氏范数为 。
定义 3.5.2
(Jacobi 迭代)
由任意内部初值 出发,保持边界值固定,并同时更新所有内部点;右边只使用第 步的值:
这是把内部方程 对中心值解出,而邻值取自上一次迭代。
定理/命题
定理 3.5.3
(最大值原理与二阶误差)
若每个内部节点均满足 ,而边界上 ,则整个网格上 。因此离散 Dirichlet 问题恰有一解。设 满足 及边界条件 ,并有 、。若边界值及 的取样均精确,则
定理 3.5.4
(正方形上 Jacobi 迭代的收敛性)
固定 时,从任何内部初值开始的 Jacobi 迭代都收敛至离散解。若 是第 次迭代值减去精确离散解,则
此因子依赖网格,当 时趋近一;因此此估计不能保证与网格无关的迭代次数。
证明或证明思路
证明
(邻点传播与单向障碍函数)
先证最大值原理。假设正的最大值出现在内部节点。网格节点经由邻点步可以连通,所以每个内部节点都有一条邻点路径通往边界。四个邻值均不大于它,故 减去四邻值之和非负;假设又使该差非正。因此四个邻点都取相同的最大值。沿通往边界的路重复此推理,便与边界非正矛盾。将此原理用于两个解之差及其相反数,得到唯一性。内部系统是方阵,核空间只有零向量亦保证对每个右端项都有解。
沿两个坐标方向分别作中心 Taylor 展开,对精确解的取样得到
设 ,。虽然 在水平两边不必为零,但在整个边界非负。它只依赖 ,所以 方向的差分为零,而 方向的差分对二次式 精确;因此恰有 。因此 且边界上 ; 亦然。最大值原理给出 ,即得定理常数。同一论证也表明:零边界网格向量若满足 ,则 。
证明透视
边界上不必为零的障碍函数
比较论证只需要单边的边界信息。由于边界上 而 ,不论 是否为零, 与 在边界上都非正。正因有此自由,障碍函数可以只依赖 :五点算子作用其上时化为一维二阶差分,而它对二次式精确,所以不会产生新的误差项。
假设在三处起作用。 的光滑性提供相容性界 。精确边界数据使 在边界为零。网格经邻点步连通,使最大值形成的平台能一直传播到边界。由于残差界是双边的,最大值原理要用两次,分别作用于 与 。常数 是 Taylor 定理的 乘以 。
Jacobi 估计依赖另一种工具:以正交特征向量基底代替比较论证。
证明
(正弦模式把 Jacobi 误差对角化)
离散解是 Jacobi 更新的不动点,把它减去。边界误差为零,内部误差满足 。正弦阵列 ,,构成内部向量空间的正交基底。Jacobi 误差矩阵作用于各阵列时,只会乘上
其最大绝对值为 ,在 与 均达到。由于 ,而正弦在 、 为零,边界零值得以保持。把 按正交基底展开,每一步各系数都乘上 ,再用 Parseval 恒等式便得范数估计。高频模式可以一边衰减一边交替变号;收敛并不表示每点都单调变化。
概念视角算法
Jacobi 即显式伪时间推进
对辅助热问题 (边界数据相同)使用显式前向时间格式,以五点 Laplace 算子及比例 :
取 ,即五个权重全部非负的最大比例,中心权重 为零,且 ;这一步正好就是 Jacobi 更新。换言之,用 Jacobi 解 Poisson 系统,就是以保持权重非负的最大步长,把热方程推进至稳态。伪时间步长为 ,而最慢的光滑模式衰减所需时间与 无关,所以迭代次数按 增长。事实上 。
例题
例题 3.5.5
(只有一个内点的完整计算)
取 、零边界值及 ,则 。唯一内点处 ,格式给出 ,故 ,恰为精确取样值。这里两个纯四阶偏导数皆为零;此多项式的精确性不能推广到所有光滑解。
例题 3.5.6
(代数残差控制什么误差)
设 具有正确边界值,且内点上 。若 是精确网格解,则 的边界为零,故 。这是求解器误差,不能单独当作 的误差;应加上离散误差界。若求解器回报的是未缩放矩阵 的残差,应先除以 才能使用此估计。
例题 3.5.7
(收敛为何仍可能缓慢)
当 ,最慢 Jacobi 因子为 ;当 ,它约为 。因此在较细网格上,一百次迭代只能把最差误差分量减少约 。对每个固定网格说“Jacobi 收敛”是正确的,却不能单凭这句话判断网格加密的计算成本。更快方法需要另行分析。
常见错误
常见错误
(把边界值从右端项漏掉)
当矩阵只作用于内部未知量时,内部节点的每个边界邻点都会在右端贡献已知项 。漏掉这些项等于解零边界数据的问题,那是另一个边值问题,而不是同一问题精度稍差的版本。
常见错误
(在 Jacobi 扫描中混用新旧值)
Jacobi 右边只使用第 次迭代的值。若就地覆写数组,使部分邻点已是第 次的值,得到的是 Gauss–Seidel 扫描。那是另一种方法,上面的因子 不再描述它。
反例模式
更新量小不代表误差小
常见的停止准则声称:一旦 低于容许值,迭代值与离散解的距离也同样小。取 ,并设误差在最慢模式上:,故 。由于更新量等于 ,
更新量通过 的容许值,误差却约为更新量的两千倍。修正要用到谱:误差矩阵 对称,特征值的绝对值不超过 ,所以 的每个特征值至少为 ,从而
在此例中这个界给出 ,是精确的。
此外,上述误差定理不能不经额外论证便套用于不光滑解、不精确数据、不规则区域或非正方网格。
总结
五点算子满足离散最大值原理;配合二次障碍函数,可在明确的光滑条件下证明唯一性与二阶节点误差界。Jacobi 在每个固定正方形网格上收敛,但其最差收敛因子随加密趋近一。离散误差与求解器误差必须分开计算。
练习
快速检查
(在单位正方形取 、 和边界值 。求内点值并解释为何它是精确值。)
记得使用四个边界邻点。
解答 · 答案
四个邻点值为 、、、,平均数为 。调和函数 满足给定边界,其取样也满足差分格式;由唯一性,数值即精确值。
快速检查
(设 、、。求定理给出的离散误差界。若具正确边界值的近似解 在内点满足 ,求总节点误差界。)
以三角不等式合并两种不同的误差界。
解答 · 答案
离散误差至多为 ;代数误差至多为 。因此在定理所列光滑和精确数据条件下,总节点误差至多为 。
快速检查
( 时求模式 的 Jacobi 因子。经两次迭代后,该误差模式有何变化?)
因子的符号和绝对值都重要。
解答 · 答案
。每次迭代使该模式变号并将振幅减半;两次之后成为初始值的 。只要绝对值小于一,负因子并不妨碍收敛。