为什么逐个更新分量?
模型离散化后常得到大型稀疏方程组 。直接分解可能需要大量存储,定常迭代则反复改进近似解。Jacobi 用旧向量计算所有新分量;Gauss–Seidel 一算出新分量便立即使用。因此方程的排列顺序也是算法的一部分。我们会证明对称正定系统的一个收敛结果,并看清松弛参数的作用。这个结果以精确算术为前提,不能直接预测运行时间或舍入误差。
将 分解为对角、严格下三角与严格上三角部分,假设 。从旧迭代向量 出发,Gauss–Seidel 的一轮满足
这可用前代法计算,无须形成逆矩阵。第 个分量利用目前最新的数值,先算出暂定值
定义 1.7.1
(Gauss–Seidel 与 SOR 的一轮)
Gauss–Seidel 的一轮依次处理 ,并令 。参数为 (各轮固定不变)的逐次超松弛法(SOR)则令 ,其中 用已经松弛过的分量 ()计算。
当 时,它就是 Gauss–Seidel; 称为欠松弛, 称为超松弛。名称并不保证超松弛一定更快。
能量与收敛性
现在假设 是实对称正定矩阵。那么 ,解 唯一,而且
梯度为 。固定其他分量时, 是这个二次函数沿第 个分量的唯一最小点。SOR 朝它走比例 的距离,也可能越过它。
引理 1.7.2
(一次松弛分量更新的能量变化)
对当前向量 ,令 ,则第 个分量的 SOR 更新为 ,并且
证明
(沿一个分量展开二次函数)
对 ,由 对称得 。代入 得 ,即所述之值。
系数 恰在 时为正,并在 (精确的分量最小点)时最大。
定理 1.7.3
(对称正定系统的 SOR 收敛性)
若 实对称正定且 ,则从任意初始向量出发,SOR 都收敛到唯一解。
证明
(每轮严格下降与紧致性)
引理说明每次更新都不会增加能量误差。令 为一整轮把误差 映到新误差的线性映射。每个非零误差在整轮之后能量都严格下降:否则上式中的各平方项都为零,每个分量均不变,故原向量满足 ,与 可逆矛盾。在能量范数 的紧单位球面上,连续函数 因而有小于一的最大值 。于是 。此证明未给出实用的 ,也没有找出最优的 。
证明透视
从单个分量的下降到一致收缩
引理只给出逐个分量的不增;证明分两步把它加强。第一步是整轮严格下降。若一轮没有损失能量,由于 ,这一轮遇到的每个梯度分量都为零,于是没有分量移动,而这些分量正是起始误差的 的分量。可逆性于是迫使 。对称性在前面已经用到,使 成为 的梯度;正定性给出 和范数 。第二步是一致性。仅仅每个 都严格下降,比值 仍可能逐渐逼近一。由于 是线性的,比值只依赖方向,而紧单位球面上的连续函数取得最大值,所以 。在 时第一步失效,这正是排除边界的原因。
完成一轮更新
例题 1.7.4
(比较两种松弛参数)
令 、。首个对角元为正,行列式为 ,故 正定;精确解为 。从 出发,Gauss–Seidel 先得 ,再用新值算出 。
若 ,第一分量变为 ;用此新值计算第二分量的暂定值 ,松弛后得 。两个序列均在定理条件下收敛,但只比较第一步不能断定哪一个先达到指定容差。
常见错误
(在一轮之后才松弛,而不是在一轮之中)
SOR 在计算下一个分量之前就松弛当前分量。把完成的 Gauss–Seidel 向量松弛为 是另一种方法。在上例中取 ,它给出 ,而 SOR 给出 :SOR 的第二分量已经用到了松弛后的第一分量。
例题 1.7.5
(观察一轮中的能量下降)
对同一方程组,。在从 出发的 Gauss–Seidel 一轮中,第一次更新有 、,引理预测下降 ;确实 。第二次更新从 出发,、,预测下降 ,直接计算也得到 。能量误差从 降到 ,一轮内约缩小为原来的 倍。
例题 1.7.6
(边界 保持能量)
取 及相同数据,第一分量变为 。第二分量的暂定值为 ,故 。一轮后迭代为 ,而
每次更新都把分量关于该方向的最小点作反射,因子 为零,能量毫无损失,尽管矩阵是正定的。收敛定理采用开区间,正是为了排除这种情况。
反例模式
正定性不能挽救任意参数
对一维方程 ,SOR 的误差满足 。若 ,非零误差永远交替变号;若 ,误差绝对值增大;若 ,迭代不动。因此正定性本身不能保证任意参数下收敛。
严格对角占优是某些定常迭代常用的充分条件,但不是上述定理的必要前提。例如 的首个对角元及行列式 均为正,所以正定;第一行却不对角占优。另一方面,更新量小并不单独证明误差小。
常见错误
(因为更新量小而停止)
对标量方程 ,取 、,第一次更新的大小是 ,误差却仍是 ; 轮后误差为 。相邻两轮变化很小,可能只反映 很小或收缩很慢,并不代表接近解。应检查适当缩放的残差,并设置迭代次数上限。
练习与解答
快速检查
(计算例子的第二轮 Gauss–Seidel。)
从 出发,每个新分量一算出就立即使用。
解答 · 答案
从 出发,新分量依次为 与 。
快速检查
(对 取 、,求前两步。)
误差每步乘以 。
解答 · 答案
,。误差因子是 ,因此交替而收敛。
快速检查
(对 求 Jacobi 迭代矩阵及谱半径。)
Jacobi 矩阵是 。
解答 · 答案
,其特征值满足 ,故 。它虽不严格对角占优,Jacobi 仍收敛;充分条件不成立不等于发散。
快速检查
(为什么证明不能涵盖 ?)
看看引理中的系数。
解答 · 答案
能量下降系数为零,严格下降与一致收缩的论证都失效。一维反例和上面保持能量的一轮更说明边界处确实可能不收敛。