动机
将边值问题离散化只是计算的一半:所得方程组仍须求解。网格很大时,明确求逆既浪费存储空间,也忽略了差分模板的稀疏结构。迭代法则反复利用局部数据改善近似。必须区分有限方程组的精确解和微分方程的解:我们可以把一个过粗甚至错误的离散方程组求得非常精确,却仍得不到准确的连续解。
Jacobi 法在一次扫描中只用上一轮的值;Gauss–Seidel 法一算出新值就使用它。逐次超松弛法(SOR)则沿这个修正走一部分或超过一步。我们先从 Poisson 方程组建立算法,再对任意对称正定矩阵以能量证明收敛。
定义
考虑 上的 和已知两端边界值。令 , 近似 。将中央差分式乘以 得
定义 3.6.1
(Gauss–Seidel 与 SOR 扫描)
把已知端点项移到右边,便得 : 的对角元为 ,相邻非对角元为 。更一般地,若矩阵的对角元非零,一次按索引递增顺序的 Gauss–Seidel 扫描设定
SOR 取 ,其中 已使用松弛后的新值。 是 Gauss–Seidel, 是欠松弛, 是超松弛。每个坐标各更新一次称为一轮扫描;改变次序会改变迭代过程,但方程组不变。
定义 3.6.2
(离散能量与残差)
若 对称正定,定义离散能量 和残差 。唯一能量极小值点 满足
因此能量差以 -范数衡量代数误差。同时把 和 乘以相同正数,解与迭代不变,但能量和残差的尺度会改变。
定理/命题
定理 3.6.3
(SOR 的能量下降与收敛)
设 是实对称正定 矩阵,,且 。对任意初始向量,以固定坐标次序循环进行 SOR,均收敛至 的唯一解。若某次更新时的当前残差分量是 ,则该次能量下降量为
命题 3.6.4
(残差与代数误差)
若对称正定矩阵 的最小特征值是 ,则任何近似 满足
这些界限只比较有限线性方程组的解,不包含离散化误差。
证明或证明思路
证明
(能量的逐坐标下降)
固定除第 个以外的坐标,沿 的能量为二次式 。它在 达到最小;SOR 取 。代入即得上述下降量。正定性保证 ,而能量有下界。把所有更新的下降量求和,可知各次更新所见残差分量的平方可加,因此趋于零。
现在要把每次更新时的残差,连到每轮开始时的残差。每次只改变一个坐标,其增量为 ,所以各次增量趋于零。每轮只有固定的 次更新,而 固定,故同一轮开始时与任何更新时的残差之差趋于零。每个坐标都在该轮被访问,因此轮首残差的每个分量均趋于零。由固定矩阵 可知轮首向量收敛至 ;中间向量亦收敛至同一极限。证明并没有假设每个误差分量每次都下降。
证明透视
正定性与参数范围各自的作用
证明三次用到正定性,每次作用不同。它给出 ,所以每次坐标更新都有定义,而沿 的能量是开口向上的抛物线。它使 以 为下界,所以非负下降量之和有限。它也使 可逆,所以残差趋于零便迫使迭代趋于 。条件 只用一次:它使因子 为正,于是有限的下降总和控制 ;在 时下降量为零,论证便得不到任何结论。对称性使 正是 的梯度;对非对称矩阵, 的梯度是 ,下降恒等式不再描述该更新。关键一步是由更新当刻的分量过渡到整个残差。可加性只控制正被更新的坐标在更新当刻的残差分量。由于每次更新只把一个坐标移动 ,而每轮只有 次更新,残差在一轮内几乎不变,这些分量便拼合成轮首的完整残差。
残差命题只需要对称矩阵的谱定理。
证明
(残差的谱界)
令 ,则 。对称矩阵的正交对角化给出 ,以及 ,即得第二个命题。
三种误差必须分开。扫描使有限方程组的能量下降;要由残差界定代数误差,还须考虑矩阵尺度和最小特征值。要把 与连续解的网格取样比较,则另需相容性与稳定性的论证。
例题
例题 3.6.5
(一次顺序扫描)
令 、,由 出发。Gauss–Seidel 先算得 ,再用这个新值算得 。同时更新的 Jacobi 法第一轮则得到 。直接解方程得 ,两者第一轮都不是精确解。
概念视角代数
把一轮扫描看成固定的矩阵分裂
写 ,其中 为对角、 为严格下三角、 为严格上三角。按递增次序的一轮 Gauss–Seidel 恰为 ,所以误差满足 ;SOR 则换成 。对任何初值都收敛,等价于谱半径小于一。在上例中 ,所以第一轮之后每轮误差乘以 ;确实 。
例题 3.6.6
(一次超松弛扫描)
同一方程组和初值,取 。第一个未松弛候选值为 ,故松弛后是 。第二个候选值使用这个新值,为 ;由零松弛后得到 。第一次更新的残差为 ,能量下降量为 。直接计算也有 、。
例题 3.6.7
(残差可能造成错觉)
对未除以 的一维 Poisson 矩阵,,网格细化时趋于零。若 与相应特征向量平行,则 。因此相同绝对残差容许值在较细网格上可能允许较大的代数误差。方程整体缩放会改变残差数值,却不改变迭代;有意义的停止准则须说明尺度和范数。
常见错误与细节
常见错误
(可用参数范围不是速度保证)
此处 保证收敛,是因为 对称正定;它不保证每个参数都比 Gauss–Seidel 快,也不能把证明直接套用到任意非对称对流矩阵。端点 不能包括:标量方程 从零开始会在 与 之间交替。
常见错误
(更新量小不是误差证明)
单凭更新量小也不能普遍保证误差小;选极小的 本来就会使每次更新很小。残差准则应与合适的离散化误差估计比较,实际计算亦须限制迭代次数。
非齐次边界值在扫描前应移入 ,而不是当作内部未知数。这里没有给出一般矩阵的最佳松弛参数。最后,正定性并非证明上的技术细节。
反例模式
Gauss–Seidel 发散的对称矩阵
声称:对每个对角元非零的对称矩阵,Gauss–Seidel 都收敛。取
它对称且可逆,解为 。由 出发,第一轮先设 ,再设 ;下一轮得 。一般而言,第二个坐标每轮乘以 ,迭代发散。失效的假设是正定性: 的特征值为 和 ,而 给出 。此时能量 没有下界,其下降不能推出任何结论。修正后的命题就是定理:对称且正定。
快速检查
快速检查
(Gauss–Seidel 在同一轮更新第二个坐标时,使用第一个坐标的哪个值?)
解答 · 答案
使用刚算出的新值。对 SOR 而言,这是松弛后的新值,不是未松弛的候选值。
练习
快速检查
(从零开始,对 、 进行两轮 Gauss–Seidel,计算第二轮后的残差。)
解答 · 答案
第一轮得 ;第二轮得 、。故 :每轮最后第二个方程恰好成立,但第二坐标改变后第一个方程未必仍成立。
快速检查
(对标量方程 ,推导 SOR 的误差递推式,并确定何时对所有初值收敛。)
解答 · 答案
候选值恒为 ,因此 ,误差满足 。对所有初值收敛当且仅当 ,即 。
快速检查
(设 、。对 计算残差、能量差和命题中的能量上界。该上界对此向量是否取等?)
解答 · 答案
,,而上界为 。界限有效,但对此向量不取等;若残差落在最小特征值 的特征空间,则可取等。