从上面的分析看出,牛顿法的三个条件极其自然,似乎缺一不可。没有光滑性或局部性,线性近似(3)及迭代收敛就无从说起。没有正则性,那么公式(2)中的逆矩阵就成问题。另一方面,牛顿法的成就又在于,只要这三个条件就足够了。
参考文献[1]提到,傅里叶1818 年和柯西 1929 年发表的文章从理论上证明了单变元单个方程牛顿法(1)在三个条件下的二阶收敛性。而现在的共识是牛顿法(2)的最完整的收敛理论归功于前苏联数学家康托若维奇 (Leonid Kantorovich,1912-1986) 发表于1939 年和 1948 年的两篇文章。目前看来,这些文章的收敛性定理表述都有些过于艰涩,其实就是一句话:在上述三个条件下,牛顿法保证二阶收敛。
由于康托若维奇完善了收敛理论并把牛顿法进一步应用到无穷维巴拿赫空间,某些文献也把牛顿法称为牛顿-康托若维奇方法。于是牛顿法的冠名争议案子又增加了一个。
超定方程组的高斯“救场”
包括很多专家在内都有一个流传广泛的误解,以为一个方程组的方程个数必须跟变量个数一样多。这个误解恐怕来自教科书,因为计算数学教科书基本上只谈这类方程组。只有专家读的专著才会谈到,方程个数大于变量个数的方程组称为超定方程组,反之称为欠定方程组。事实上,正方形的方程组虽然有很多理论和求解的方便,但是很多问题本质上就是超定或欠定方程组,在科学计算中根本不可回避。对于超定或欠定非线性方程组,相应的线性近似方程组(4)也是超定或欠定,雅可比矩阵的逆矩阵别说去计算,连定义都没有。怎么办呢?十分遗憾,通用教科书里基本上是找不到答案的。
高斯(Johann Carl Friedrich Gauß , 1777-1855)也是无需介绍的伟大数学家。数学史上一个里程碑式的定理叫代数基本定理,也就是说多项式方程必有复数解。历史上众多数学巨匠尝试过证明这个定理,后来发现都差得远呢。这些大师包括达朗贝尔、欧拉、拉格朗日和拉普拉斯,可谓“江山如此多娇,引无数英雄竞折腰”。最终是谁证明了代数基本定理也是个众说纷纭的数学传奇。高斯1799年把这个世纪难题当博士论文做了,一般被认为是第一个正确的证明。高斯尽管在数学上的成就辉煌,最让人津津乐道的故事却是在他七岁上学后的第二年,老师显然是热衷题海战术,让全班练习从1加到100,神童高斯哪里有兴趣去死加一百个数,跟老师说,1 100=2 99=3 98=101, 结果不就是 101×50=5050 吗?他老师是如何吃惊就不难想象了。
要知道常规逆矩阵也自动是左逆,因此辛普森的牛顿法公式 (2)变成了是高斯公式(5)的特例。
高斯-牛顿法常常也简称牛顿法。于是牛顿法的适用范围从方形方程组扩展到包括超定方程组。由于超定方程组通常不存在通常意义的解,这种情况下高斯-牛顿法可以求出一个推广意义下的解,称为最小二乘解。这是高斯留给应用数学和计算数学的遗产。可惜它埋没于优化类专业书籍里面,多数计算数学通用教科书上不提。
值得一提的是,牛顿法的二阶收敛并不是最快的求根计算方法。比较著名的三阶收敛迭代法有哈雷(Halley)迭代和拉盖尔(Laguerre)迭代,也就是每步迭代获得的精确数位是前一步的三倍。作为课外练习,数学专业本科生都可以构造任何有限阶收敛的快速迭代法。然而从实际计算的角度来看,超过二阶收敛的迭代法仅仅在解决特定问题上可能有些价值。作为通用算法,简单得不能再简单的牛顿法已经二阶收敛,其实际效率在计算中很难被真正超越。哈雷先生虽然以首次算出哈雷彗星轨道周期名垂科学史,但他的迭代法基本上沦落到被遗忘的角落。在此也希望年轻学者不要在研究通用高阶收敛迭代法的问题上浪费时间。除非找到特定应用,超过二阶的收敛速度一般没有实际意义。
进一步的探讨
一个科学发现常常只能被幸运地发现一次。牛顿法则是一次次被重新推广和修正,每次新发现的结果是,我们原来知道的牛顿法不过是新版的特例而已。
从巴比伦-赫伦求平方根扩展到韦达-牛顿-拉夫森的多项式求根, 扩展到辛普森公式求解超越方程和方形方程组,再扩展到高斯求解超定方程组,再扩展到康托若维奇在巴拿赫空间求解,看似简单的“牛顿法”几千年来一再被赋予新的内涵,扩展到更广泛的应用。这期间还引出众多数学大师如傅里叶、柯西和拉格朗日。牛顿法的发展和演变历史,也是数学学人不断探索新领域解决新问题过程的写照。牛顿法的奇妙还在于,从诞生以来一次次的发展、推广和创新都是实质性的,而不仅仅是修边角式的改善。牛顿之后的每次推广都远远超越牛顿的初等方法。当然所有的推广都被习惯性地称为“牛顿法”。于是,“经久不衰的迷思”成为传统。
随着电子计算机的出现以及随之而来的计算数学这一学科的诞生,牛顿法作为求解非线性代数方程组的基本通用方法在科学计算的大舞台上大显身手,到处都是其用武之地。由于解方程的问题太常见,对各种迭代法的深入探索和进一步推广从来没有停止过。要想从牛顿法有所创新,三个收敛条件(光滑性、正则性和局部性)是显而易见的入口。
光滑性,也就是函数或映射 f 连续二阶可微在绝大多数实际应用中不成问题。对于导数不存在、无法求导或者雅可比矩阵计算成本太高的特定方程,可以使用拟牛顿法和创新不动点迭代。这基本上超出了牛顿法的范畴,在此就不多谈了。无需微分的算法难以利用微积分的线性逼近,因此都未能达到二阶高速收敛而无法成为通用算法。
比如说,巴比伦算法在求平方根这个特定问题上就是全局收敛。在发现全局收敛的通用迭代法之前,牛顿法的局部收敛性在一般问题上不输任何算法,所以很难说局部收敛是牛顿法的弊病和短板。局部收敛更恰当的说法是牛顿法的一个特性。由于一般方程组 f(x) = 0 的解可以不唯一,即使找到全局收敛算法,从常理上说这个潜在算法也应该具有局部收敛性,否则无论如何靠近一个解都会跳到另一个解,这算法真能用吗?
欣然接受牛顿法的局部收敛特性并加以利用,可以构造出各种全局收敛算法解决特定问题。一个成功的项目始于 1976年,第一篇现代同伦延拓法的文章横空出世,作者之一就是笔者的博士导师李天岩(1945-2020)教授。现代同伦法的进步在于结合微分拓扑和代数几何思想对计算数学领域的渗透。将这些思路与牛顿法相结合,构造出的目前效率最高、速度最快的求解方法和软件适用于多项式方程组。
常有人说数学是艺术,意思多半是说数学本身是艺术,看你有没有能力欣赏。读者可能想不到,牛顿法的局部收敛特性还可以用来创作似乎毫不相*艺术作品。无论是什么世界名画,油画在数学上无非是每个点都有一个颜色,而每个颜色都可以换算成三个数字代表红黄蓝三原色的强度,反之亦然。任何数学方法,只要能给每个点赋予一个或三个数字,这个方法就可以用电脑做出一幅油画,只要发挥想象力创造力,创作可能性是无穷的。