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

luyuanhong

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

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

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



条条大路通罗马



特征值与谱半径



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



收敛条件



尾声

德国数学家在两百年前点燃的线性迭代法火炬，百年之后远渡重洋，传递到了科技腾飞、电脑出世的美洲大陆。为了优化迭代效率，从经典的高斯-赛德尔方法出发，在 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 日星期日

美国哈蒂斯堡夏日山庄

原创 丁玖 返朴 2023-11-30 08:40 发表于北京