利用最新数据
大型线性系统未必对称或正定,因而不能直接使用 SOR 的能量论证。Gauss–Seidel 在一次扫描中依次使用刚更新的数值;我们可以据此逐行控制误差。
定义 7.3.1
(Gauss–Seidel 扫描)
设 是有限维实方阵,所有 ;固定未知数顺序,假设精确算术。把 写成对角、严格下三角及严格上三角部分 。从任意 出发,每次扫描依次计算
即 ,其中 。
右边下标较小的值已在本次扫描中更新。由于 是对角元素非零的三角矩阵,即使 奇异,每次扫描仍有定义;收敛保证还需要证明解存在且唯一。
逐行构造判据
定义 7.3.2
(Sassenfeld 逐行数)
按照相同的更新顺序定义非负数
较早更新坐标的贡献乘上此前得到的对应界。这是 Sassenfeld 判据,是充分条件,并非收敛的必要条件。
定理 7.3.3
(Gauss–Seidel 逐行收敛判据)
若 ,则 可逆,且从任意初值出发,Gauss–Seidel 收敛到唯一解 。每次扫描满足
对于 ,可计算的相邻迭代差还给出
证明
(沿扫描的收缩)
比较任意 各扫描一次,设 。第一行给出 。假设所有 均已有对应的 界,对第 行取绝对值并代入这些较早坐标的界,得到
归纳证明
这里还没有假设解存在。若 ,则 ,所以 ,从而 。因 ,必有 。方阵的核为零意味着可逆,因此 唯一存在并是 的不动点。取 反复使用收缩界,即得误差界及收敛。
令 。收缩界给出 。迭代收敛,所以 。取范数并求等比级数,便得到相邻差的误差界。该保证基于精确算术;浮点计算另需控制舍入误差。
证明很短,但每个假设都有确定的用处。
证明透视
沿扫描顺序建立界
关键一步是按计算顺序界定各坐标。在第 行,已更新的坐标 以 出现,归纳已把其大小界为 ,而不只是 。利用最新数据的好处正在于此,这也是 依赖顺序的原因。尚未更新的坐标 以 出现,以 为界。对角元素非零只用于除以 ;它使 即使在 奇异时仍有定义。
第二步由收缩性推出解的存在与唯一,而非事先假设。对 ,恒等式 表示 是右端为零时扫描的不动点,所以 迫使 。至此 才可作为比较用的不动点。相邻差界以裂项级数收尾:它用刚证得的收敛,把 写成其后所有步的和,再用 求和 。
严格行对角占优是充分条件
推论 7.3.4
(严格行对角占优给出判据)
假设每行都满足 ,令
则在任何顺序下 ,因此对任意右端及初值,Gauss–Seidel 都收敛。
证明
(对逐行数归纳)
每行严格占优给出 。归纳地,如果此前各 ,它们就都不超过一,代入定义可得
第一行开始归纳,因为 。因此 。方程与未知数同时重排时,严格行对角占优保持不变,所以结论对任何顺序都成立。
严格行对角占优无需对称性,即可保证 Gauss–Seidel 和 Jacobi 均收敛;但 未必是精确收敛速率。严格不等式不能放宽为每行取等号。
反例模式
弱对角占优并不足够
声称:若每行都有 ,Gauss–Seidel 就收敛。取
两行都以等号满足弱不等式,且 、,故 。矩阵奇异,系统也不一致,因为 不能同时等于 和 。扫描为 、,所以 每次扫描增加一,迭代无界。声称不成立;定理需要 ,而严格占优正好提供这一点。
例:行对角占优失败,判据仍成功
例题 7.3.5
(行对角占优失败而判据成立)
考虑
第三行 ,因此不严格行对角占优。Jacobi 的无穷范数检验也因第三行比值 而失败。然而依给定顺序,
定理因此保证唯一解和任意初值的收敛。实际 。从 开始,第一轮得到
第二行已使用第一个新值,第三行使用前两个新值。实际误差无穷范数为 ,小于定理给出的界 。Jacobi 的一个范数检验失败,并不证明 Jacobi 发散,更不能说明 Gauss–Seidel 发散。
例题 7.3.6
(两次扫描后的可计算停止界)
从 继续同一系统。第二次扫描给出
相邻差为 ,无穷范数为 。由于 ,可计算的界为
实际误差为 ,范数 。由第一次扫描得到的收缩界更紧:。两个界都正确。相邻差界不需要知道 ,但因子 使它在步长仍大时偏于保守;当相继迭代已很接近时,它才成为有用的停止检验。
检验失败说明什么?
例题 7.3.7
(判据失败而迭代收敛)
取
此时 、,故 ,判据不适用。然而 ,误差更新满足
由于 且 ,从任何初值出发,两分量都趋于零。第一分量可以在第一轮变大,但迭代仍收敛。
常见错误
(把判据失败当作发散)
判据只是上界。 时这个界不提供任何信息,正如上例: 而迭代收敛。要证明发散需另作论证,例如找出一个每次扫描都增长的误差分量。
常见错误
(以为矩阵可逆就保证扫描有定义)
可逆不能保证给定顺序下的扫描有定义;例如 可逆,但对角元素为零。重排方程可能解决零对角问题,却会改变迭代和判据,不能假设任何顺序都适用。
练习与解答
快速检查
(对 计算判据;它能保证收敛吗?)
解答 · 答案
,,因此 。定理适用于任何右端和初值。
快速检查
(将上述三阶例子的方程和未知数都反序排列,计算新判据。)
解答 · 答案
新矩阵是 ,依次得到 、、。最大值超过一;原顺序通过而这个顺序未通过,但后者本身不能判定收敛与否。
快速检查
(已验证精确算术判据 ,且 。给出误差界。)
解答 · 答案
将相邻差乘 ,得到 。这个界没有自动计入浮点舍入。
快速检查
(给出一个可逆但 Gauss–Seidel 按所列顺序发散的系统。)
解答 · 答案
取 、。行列式为 ,但 、;第二分量初值非零时序列无界。唯一解并不保证此迭代收敛。