为什么改变 Gauss–Seidel 的步长?
设 太大,不宜直接分解,而 是实对称正定矩阵。Gauss–Seidel 每次改变一个坐标,并立即使用刚算出的新坐标。逐次超松弛法(successive over-relaxation,SOR)把每次坐标修正乘上一个倍数。倍数大于一可能使迭代更快,也可能走过头。我们将证明,哪些正倍数能保证对每个对称正定系统收敛;这并不说明对某个特定矩阵哪一个最快。
以下假设 对称正定、,并使用精确算术。因此 ,且解 唯一。写 ,其中 为对角部分, 分别为严格下、上三角部分;对称性给出 。
定义 7.2.1
(参数为 的 SOR 扫描)
在第 次扫描开始时,向量为 。依次更新坐标 :
残差 是在已部分更新的向量处计算的。 称为欠松弛; 称为超松弛。
当 ,这就是 Gauss–Seidel:新坐标使当时该行残差为零,但之后更新其他坐标可能再次改变它。
把各坐标方程合起来,得到
左边的矩阵是对角元为正的下三角矩阵,所以每次扫描都有定义。改变坐标顺序会改变 ,因此也会改变方法。
最小化一个二次函数
定义 7.2.2
(系统的能量)
方程组 的能量为
由 和对称性,
等号只在 成立。因此解方程组等同于最小化这个二次函数。若当前部分更新的向量是 ,只把第 个坐标改变 ,展开得到
设 ,沿该坐标使函数最小的改变为 。SOR 则取 。
引理 7.2.3
(一次松弛坐标步的能量变化)
设 、、 及 ,则
证明
(代入松弛步)
上面的展开即 。代入 ,
由于 ,;代入即得第二个形式。
当 ,每一步都使 下降,除非当前残差已为零。超松弛会越过该坐标的最小点,但不会走得太远而失去能量的下降。仅有下降仍不足以证明收敛到解;还须排除在离解很远处停滞。
定理 7.2.4
(正定系统的 SOR 收敛)
若 是实对称正定矩阵,且 ,则 SOR 从任意起点收敛到 。这个区间是对所有正定矩阵的统一保证:若 ,即使在一维正定系统中,也存在使迭代不收敛的起点。
证明
(由能量下降到完整残差趋零)
令 表示第 次扫描更新前 个坐标后的向量;故 ,。令 为第 次坐标改变。把能量恒等式对所有坐标及扫描求和,再用 ,得到
因此每个 。固定 ,更新前该坐标的残差等于 ,也趋于零。部分更新的向量与 只相差之前有限个坐标改变,而这些改变都趋于零。由线性映射 的连续性, 的每个分量都趋于零。因 是固定的有限矩阵,
此论证使用固定的有限 和固定的 ;它没有给出适用于所有正定矩阵的统一收敛速度。必要性部分就是下文端点一节的一维计算。
证明从未说明一次扫描把误差缩小固定倍数,而是从有限的能量预算中得到收敛,详见下文。
证明透视
能量预算从何而来
关键一步是把能量恒等式对每个坐标步求和。仅有单调下降,能量仍可停在 之上;裂项求和则显示各步平方的总和有限,因此步长本身趋于零。两个假设使这个和有限:正定性使 以 为下界,而 使系数 为正。在 ,系数为零,能量预算不提供任何信息。
其余步骤把小步长化为小误差。除以 ,每一步就变成更新前的残差。每个这样的残差都是 的分量,在部分更新的向量而非 处计算; 有限,才能吸收中间有限个各自趋于零的步。最后一步用固定的逆矩阵 由残差过渡到误差。
算例:追踪最新坐标
例题 7.2.5
(一次 Gauss–Seidel 扫描及其能量)
取
矩阵正定,因为对非零 ,。当 ,坐标方程为
第一次扫描得 ,第二次得 。若在第二个方程使用旧的第一坐标,就是 Jacobi 步,而不是这里的扫描。事实上,,其不动点为 ,误差每次扫描乘以 。故 、,与精确解一致。
能量印证了引理。这里 。第一次扫描的两个残差为 与 ,系数 ,故两次下降为 与 。确实 ,。最小值为 ,所以一次扫描后仍有能量差 。
例题 7.2.6
(取 的超松弛)
同一系统及起点下,第一坐标改变 。第二残差要使用这个新值,故为 ,第二坐标改变 。第一次扫描得到 ,不是 。
引理中的系数现为 ,所以两次能量下降为 与 ,合计 。直接代入得 ,与此一致。扫描结束时的残差为
定理保证收敛,但只看第一次扫描不能判定这个选择长期是否更快。
端点及假设为何重要
例题 7.2.7
(一维情形的端点)
对一维方程 ,即 、,SOR 为 ,故 。若 且 ,迭代值永远交替变号,而能量 不变,与引理中的零下降一致;若 ,迭代值不动;若 或 ,则 ,其绝对值增长。这证明了上述统一保证的必要性。
正定性也重要:没有它,二次函数未必有下界,能量证明便不适用。对角元为正并不能代替正定。
反例模式
对称且对角元为正并不足够
声称:对每个对角元为正的对称矩阵, 的 SOR 都收敛。取
矩阵对称且对角元为正,但 ,所以并非正定, 沿 无下界。扫描为 、。从 开始,第二坐标为 ,迭代无界,尽管唯一解是 。定理需要的是正定性,而不只是对角元为正。
定理也不保证有限精度的实现能达到任意小的误差;舍入及停止准则需另行分析。
常见错误
(用旧坐标计算残差)
第 个坐标的残差必须在部分更新的向量处计算。若用扫描开始时的值,便成了 Jacobi 式的步,其能量变化不受引理描述;在算例中,第一次扫描后会得到 ,而不是 。
常见错误
(把区间当作最佳参数的建议)
定理只说 中每个 都收敛,并没有说较大的 较快,也没有说对某个矩阵哪个 最快。接近任一端点的参数可能很慢,坐标顺序也影响表现。
练习与解答
快速检查
(对 ,从 出发,取 。求前两个迭代值及第 步的精确误差。)
解答 · 答案
更新式为 。故 、,不动点为 。减去不动点得 。
快速检查
(在上述二维例子中,求第一次 Gauss–Seidel 扫描后的残差。为何第二分量为零,第一分量却不是?)
解答 · 答案
在 ,,故 。第二步使用新的第一坐标,使第二行成立;但这一步也改变了已修正过的第一行。
快速检查
(设 对称正定,。若一次完整 SOR 扫描不改变 ,证明起始向量满足 。)
解答 · 答案
每次坐标更新的能量变化都非正;由能量恒等式中严格为正的系数,总和为零表示每次坐标改变都为零。每个更新前残差也为零。因为坐标完全没有改变,这些残差正是起始向量处 的各分量,故起始向量为解。