怎样迭代求解线性方程组？
怎样迭代求解线性方程组？在科学计算和工程应用领域，经常涉及求解线性方程组问题。迭代法是解决这类问题的有力武器，通过多次迭代逐步逼近精确解，在处理大型稀疏线性方程组时具有重要优势。《返朴》之前已刊发数篇函数迭代的相关文章，本文从基础概念讲起，由浅入深介绍了迭代法求解线性方程组的准备知识和具体过程。
撰文 | 丁玖（美国南密西西比大学数学系教授）
记得有个大科学家曾经说过，这个世界是非线性的。然而非线性方程一般不能直接求解，即解析解虽可证存在却无具体表达式，因而迭代法几乎是唯一可行的办法。比如说，从介值定理可知，方程 x = cos x 在区间 (0, 1) 内定有一解，但没有一步到位的法子找到它，人们只能用基于介值定理的二分法或基于切线逼近的牛顿法，来求得此方程的迭代近似解。这样，从最古老的巴比伦平方根迭代法，到今日非线性方程组数值解的最重要方法——牛顿迭代法，人们一直热衷于迭代法的理论探索和创新实践。
既然有非线性方程，就必然有线性方程，而且后者在科学技术和日常生活中同样随处可见。电话公司的客户安排、航空公司的航班分配、运输公司的运货路线……都可以用线性规划来优化成本。四十年前，当我在南京大学数学系时，读到一篇关于线性规划的综述性文章，其中写道：全世界的计算机大约有百分之六十的时间，都在求解线性规划问题！
另一方面，微分概念告诉我们，非线性函数可以局部地用线性函数来近似，构造牛顿迭代法本质上就基于这个简单的观察。只要非线性函数 f 在一个点 a 存在导数，那么在 a 点的附近，函数值 f(x) 就约等于线性函数值 f(a) + f'(a)(x-a) ，其几何直观则是函数图像的切线在切点附近与曲线相差无几。
计算数学中的一个子学科“数值线性代数”有个基本的职责：怎样有效求解上面的线性方程组？当 n = 2 或 3 ，最多不超过 4 时，我们早已在中学课堂上学会了怎样求解二元一次方程组、三元一次方程组，等等。采用的方法无非是两种，一种叫做代入法，另一种称为加减法。它们都是基于同一个思想：通过消去方程中的一个或几个未知数，设法获得只含有一个未知数的方程，比方说 -2y = 3 ，从而解出这个未知数。
中学生所学的上述方法，实际上是大名鼎鼎的高斯消去法的简单实现，发明者正是德国天才高斯（Carl Friedrich Gauss，1777-1855）。高斯消去法的基本思想还是如上所说：将含有多个未知数的方程化简到只剩下一个未知数，因为只含一个变元的线性方程如 -2y = 3 总是可以一步到位解出 y = -3/2 的。基于这个非常简单的思路，高斯想出了一个点子，将线性方程组的系数方阵程式化系统性地化约成主对角线下方的元素全为零的上三角矩阵，这样新的等价的线性方程组的最后一个方程只含一个未知数，倒数第二个方程含有两个未知数，如此等等。因而，通过所谓的“回代法”，从最后一个方程解出唯一的未知数，然后将它的值代入到倒数第二个方程，结果该方程也只含一个未知数，马上可以解出，再将这两个未知数的值代入到倒数第三个方程，同法解出下一个的未知数。如此这般，就可以依次解出所有的未知数。
高斯消去法在经过有限次代数运算后就可以完全找出给定线性方程组的精确解（如果每步运算的误差为零的话）。所以它属于求解线性方程组的第一类数值方法——直接法，这是解线性方程组优越于解非线性方程组的一个地方。然而，对有巨量（如成千上万个或更大数量级）变元个数或者特别多的系数为零（比如系数矩阵为三对角或其他稀疏类型）的那种方程组，直接法常常没有第二类方法——迭代法有效。对线性偏微分方程直接用差商代替偏导数的差分方法，或将微分方程问题变为数学上等价的变分问题而进行数值优化的有限元方法，所得到的大型线性方程组一般都带有特定结构的稀疏系数矩阵，这时，迭代法几乎是最有效的算法了。
我在以前的科普文章里写过，单变量非线性方程的迭代法收敛的一个充分条件，是迭代函数在不动点的导数绝对值小于 1 。那么，如果被迭代的是有多个变量的线性向量函数，什么样的条件可以充分到保证迭代法收敛呢？所谓序列的收敛，本质上是用距离这个概念来定义的，这个概念我们在以前提到巴拿赫不动点定理或压缩映射定理时已经见到过。我们再来回忆有关内容。在一个抽象的距离空间 (X, d) 里，一个由 X 中的元素所组成的无穷序列 {xk} 被说成是收敛到 X 中的一个元素 x ，指的是由距离函数 d 所确定的非负数列 {d(xk, x)} 当 k 趋向于无穷大时趋向于 0 。对于单变量函数迭代法的收敛性问题，我们实际上选取了一个简单而具体的距离空间，它就是所有实数全体构成的一维欧几里得空间 R ，其任意两个实数之间的距离就是实数轴上两点 x 和 y 之间的通常距离 | x-y | 。
上面两数之间的距离可用线段长度的说法来等价地定义。任意一个实数 a 的绝对值 | a | 在几何上的意义是以数轴上代表 a 的那个点和原点 0 为两端点的线段的长度。不难看出，两个数 x 和 y 之间的距离就是数 x-y 所对应的那条线段的长度。
读者自然会问，怎么选取关键的矩阵 N ？这个矩阵要有逆矩阵，要保证迭代法收敛，并且是收敛得越快越好。这是计算数学家们一直追求的目标。我们现在潜入历史，看看有哪几位数学家在线性迭代法方面贡献卓越，成为先驱。
历史上第一个提出迭代法的数学家又是高斯，所以他不仅是以高斯消去法为代表的直接法的鼻祖，也是迭代法的鼻祖。1823 年 12 月 26 日，高斯在给他昔日博士生戈林（Christian Ludwig Gerling，1788-1864）的一封信中，提出了这个他称之为“非直接消去法”的迭代法，用于求解关于四个城市的一个应用问题。他首先利用也是他发明的最小二乘法得到一组线性方程，然后用自己设计出的迭代法求解对应的法方程。这走出了迭代法求解线性方程组历史进程的第一步。然而，由于高斯的许多数学发现和发明并没有被他正式发表，所以他的发明权不得不常与后人分享，他也不在乎，没有当今“不发表便灭亡”的“科学家烦恼”。半个世纪后，他的同胞数学家冯·赛德尔（Phillip Ludwig von Seidel，1821-1896）于 1874 年发表了包含同样思想的迭代法。
1845 年，另一名德国数学家雅可比（Carl Gustov Jacob Jacobi，1804-1851）也提出了一个以他的名字命名的迭代法。这个方法比较简单，在数值代数的教科书中一般是作为迭代法求解线性方程组的第一个例子被介绍给学生。雅可比的人生轨迹虽然只持续了不到四十七年，他却是一位多产的数学大师，其最伟大的贡献在椭圆函数方面。他被上世纪的美国数学史家贝尔（Eric Temple Bell，1883-1960）写进影响了几代读者的《大数学家》（Men of Mathematics），该书总共只描述了到上世纪初为止留名数学史的三十多个“大数学家”。雅可比的职业生涯中有十三年是在柯尼斯堡大学担任正教授，这所大学的杰出校友有数学家希尔伯特（David Hilbert，1862-1943）和闵可夫斯基（Hermann Minkowski，1864-1909）。
求解线性方程组历史上最有名气也最简单实用的两个迭代法都是德国人的杰作，今日关于它们的基本理论也很漂亮。但是本文已够长了，所以我将再写一文，专门介绍雅可比迭代法和高斯-赛德尔迭代法的基本思想和收敛性。
写于 2023 年 11 月 3 日星期五
美国哈蒂斯堡夏日山庄
原创 丁玖 返朴 2023-11-14 10:26 发表于北京
页:
[1]