简单实用！3个德国人创造的线性迭代法，超越了一个时代

今年12月26日是德国数学家高斯发明历史上第一个线性迭代法200周年。在前不久发表的《怎样迭代求解线性方程组？》的一文中，我们从基础概念出发，厘清了迭代法求解线性方程组的准备知识和具体过程。这次我们将探讨历史上最有名气、也最简单实用的两种一阶定常迭代法：雅可比迭代法和高斯-赛德尔迭代法的基本思想和收敛性。

撰文 | 丁玖（美国南密西西比大学数学系教授）

我在前一篇《返朴》文章《怎样迭代求解线性方程组？》中，为了能与适用于一般完备距离空间的压缩映射定理挂上钩，只给出了迭代法求解线性方程组的一个简单的收敛性充分

条条大路通罗马

好在我们还有其他的范数可用。作为通常直线段长度概念的直接推广，n维欧几里得空间

特征值与谱半径

然而，有一个收敛的充分必要条件等待着我们去挖掘，这个条件不再用到矩阵的范数，而是矩阵的谱。谱给出了矩阵不依赖于矩阵范数的一个内蕴性质。方阵的谱是它所有特征值全体组成的一个有限的复数集合。给定n阶方阵M，我们称复数λ为M的一个特征值，如果复矩阵M - λI不是可逆的，即存在一个复的非零列向量x使得Mx = λx。这个x被称为M对应于特征值λ的一个特征向量。我们曾经提到，一个矩阵是奇异的当且仅当它的行列式等于零，故λ是M的特征值当且仅当det(M - λI) = 0，其中符号det表示行列式。如果把这个等式左边中的λ看成是变元，根据行列式的定义，det(M - λI)的展开结果是关于λ的一个n阶多项式，所以一个n阶方阵M顶多有n个相异的特征值。我们把M的所有特征值绝对值中的最大值称作 M的谱半径，记为ρ(M)。

研究线性迭代的主要目的是数值求解线性方程组Ax = b，其中的系数矩阵A为非奇异的，

反过来，如果ρ(M) < 1，则存在一个足够小的正数ε 使得ρ(M) + ε < 1。这一看似简单的事实是实数的基本性质。另一方面，对于M的每一个特征值λ和Rn上的任一个范数||•||，设x为λ所对应的一个特征向量，由不等式||M|| ||x|| ≥ ||Mx|| = ||λx|| = |λ| ||x||以及x ≠ 0可知，刚刚获得的不等式两边可以除以正数||x||，而得到不等式||M|| ≥ |λ|，从而可知：矩阵M的谱半径ρ(M)是所有向量范数诱导出的矩阵范数在M的值||M||的一个下界。事实上，这个下界是对应于固定矩阵M的全部范数值||M||构成的实数集合的“下确界”，即这个集合的所有下界中的“最大下界”。“上、下确界”的概念是微积分学的最基础、最重要的概念，真正学通了它，极限理论以及随之而来的连续性、导数、积分、级数等等概念学起来甚至可以

雅可比迭代法和高斯-赛德尔迭代法

现在我们可以集中讨论求解线性方程组Ax = b的雅可比迭代法和高斯-赛德尔迭代法了，其中A为n阶可逆方阵。这两种产自德意志的经典迭代法都是基于在矩阵分解A = N - P中对N和P的特殊选取，其迭代格式都可写为

我们比较一下雅可比方法与高斯-赛德尔方法在迭代点分量计算过程中的显著差别。由雅可比迭代法中n个分量的迭代公式可见，在第k - 1个迭代向量所有的分量都计算完毕后，第k个迭代向量的各个分量才一个接着一个地计算出来；换句话说，第k - 1步迭代获得的全部分量都被用于对第k步迭代所有分量的计算。而对于高斯-赛德尔迭代法，每当需要算出第k个迭代向量的第i个分量时，不仅需要已完成计算的第k - 1个迭代向量从第i + 1到第n个分量帮忙，而且还需要正在进行中的本次迭代已得到的第k个迭代向量的第1到第i - 1个分量相助；或言之，高斯-赛德尔法比雅可比法“更急于求成”，命令当前迭代步骤中刚刚收入囊中的迭代点分量取代上一迭代步骤被“擒获”的同下标分量，“披挂上阵”。这说明，高斯和赛德尔比雅可比更会“用兵”，不肯浪费半点士气。

收敛条件

自然，无论是雅可比迭代法还是高斯-赛德尔迭代法，对矩阵A缺乏某些额外的假设条件，都不能保证其收敛性。那么，当“A的对角线元素个个不能为零”这个先决条件被满足后，什么是保证它们收敛的充分条件呢？

这里，保证雅可比迭代法收敛性的严格对角占优的要求可以被改成不可约弱对角占优，即上面的所有严格不等式换为一般不等式 “≥”，且至少有一个不等式严格成立，但增加了矩阵不可约的附加条件。如果一个方阵的行和列能以同样的方式重新排列（不再排列也算“重新排列”，因为单位矩阵也是排列矩阵），结果变成一个2×2块上三角矩阵，即矩阵的左下角有至少为1×1的0矩阵，那么我们说这个矩阵是可约的，否则就说它是不可约的。

当A为严格对角占优矩阵时，高斯-赛德尔迭代矩阵的∞-范数不大于雅可比迭代矩阵的∞-范数，而这个范数越小，收敛速度通常就越快，因而就收敛快慢而言，前一种方法不亚于后一种方法。

我们把高斯-赛德尔方法另一个独特的收敛性命题端上餐桌，作为本文的最后一道数学菜肴：

如果线性方程组Ax = b的系数矩阵A是对称正定的，那么高斯-赛德尔迭代法收敛。

尾声

德国数学家在两百年前点燃的线性迭代法火炬，百年之后远渡重洋，传递到了科技腾飞、电脑出世的美洲大陆。为了优化迭代效率，从经典的高斯-赛德尔方法出发，在1950年，美国数学家、计算机科学家杨大卫 (David M. Young Jr.，1923-2008，“返朴”将另行介绍他) 和美国物理学家、计算机科学家弗兰克尔 (Stanley Phillips Frankel，1919-1978) 几乎同时引入了一个松弛因子ω进行某种仿射组合，引出了“逐次超松弛迭代法 (method of successive over-relaxation，SOR) ”。前者在哈佛大学数学系的博士学位论文Iterative Methods for Solving Partial Difference Equations of Elliptic Type（《求解椭圆型偏差分方程的迭代方法》）中提出了SOR方法；后者在美国数学会期刊（十年后改名为Mathematics of Computation[《计算数学》]）上发表论文Convergence rates of iterative treatments of partial differential equations（《偏微分方程迭代处理的收敛率》），其中对他设计并称之为“Extrapolated Liebmann method（外推利伯曼法）的SOR方法进行了全面的分析。这两项提出SOR方法的先驱性研究，都与在科学和工程中大量出现的偏微分方程有关，用电子计算机求解这些连续方程离散化后的大型稀疏线性方程组，迭代法是首要之选，这就是SOR方法应运而生的时代背景。

当松弛因子ω取值为1时，SOR方法就还原成高斯-赛德尔方法。我们不细表此法，就此结束本文，因为我们已经通过了解两个古典的迭代法而知悉线性迭代法收敛性准则的基本思想。总而言之，十九世纪三名德国数学家的发明创造，是现代大型、稀疏、结构化线性方程组迭代解研究浪潮的源头。

写于2023年11月19日星期日美国哈蒂斯堡夏日山庄

本文受科普中国·星空计划项目扶持

出品：中国科协科普部

监制：中国科学技术出版社有限公司、北京中科星河文化传媒有限公司

特 别 提 示

1. 进入『返朴』微信公众号底部菜单“精品专栏“，可查阅不同主题系列科普文章。

2. 『返朴』提供按月检索文章功能。关注公众号，回复四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。

版权说明：欢迎个人转发，任何形式的媒体或机构未经授权，不得转载和摘编。转载授权请在「返朴」微信公众号内联系后台。