查看原文
其他

牛顿迭代法传奇(上):张冠李戴的命名

曾钟钢、丁玖 返朴 2022-05-18

点击上方蓝字“返朴”进入主页,可关注查阅往期文章

作为解方程的基本通用算法,牛顿法是应用数学和计算数学最重要的算法之一。这个简单神速的算法被冠以牛顿大名,那它真是牛顿发现的吗?


撰文 | 曾钟钢(美国东北伊利诺伊大学数学系讲座教授)、丁玖(美国南密西西比大学数学系教授)


传说三千五百年前,聪明的巴比伦人想出了一个计算平方根简单漂亮的窍门:如果一个正数比  小一点,则A除以它就比  大一点,这样它们的平均值就有希望更靠近  。于是,先取  的一个大致估计记为a, 只需求 a 和的平均,写成公式就是



算出的 b 就是  更精确的近似值 。


神奇的是,如果你的初始估计不是太差,比如猜到作为 a 有两位数字精确,那么 b≈1.414 就有四位数字精确。用同样办法改进 b 得到 c≈1.4142136 的精确数字就有八位。每次计算精确数位翻一番!


猜不出初始近似怎么办呢?没关系,从任何非零正数 a 出发都可以。随意乱猜的结果无非是多算几步,很快就会进入精度加倍状态。这个方法流传至今成为经典传奇,叫做巴比伦方法。为什么说是个传奇?因为没有文字记载。直到公元60年,古希腊数学家Hero of Alexandria (c. 10-c.70) 对这个方法才给出了有案可查的第一个明确的表述,所以巴比伦法也称为赫伦方法 (Heron’s method)。现在我们知道, 本文主题牛顿迭代法最古老的源头来自四大文明之一的巴比伦文明。


什么是牛顿迭代法?


牛顿 (Isaac Newton,1643-1727) 的大名就无需介绍了。他以发现力学三大定律、万有引力定律和微积分跻身从古到今最伟大的科学家行列。牛顿无疑是有史以来最杰出的数学家之一。作为一个重大贡献,他率先发现的微积分可以上升到人类文明瑰宝的高度。所有的理工科大学生都应该知道赫赫有名的“牛顿法”,也称“牛顿迭代”或“牛顿近似”。自然科学家、应用和计算数学家及工程学家们一旦需要求解非线性方程和方程组,脑子里首先应该想到的就会是牛顿法。


什么是牛顿法呢?设想我们要求出一元非线性方程f(x) = 0的解,比如说x – cos x = 0,这里f(x) =x – cos x 。数学史上有个著名的阿贝尔不可能定理,说的是非线性方程一般来说是不可能保证找到精确解的,门都没有。所以我们需要所谓“数值方法”一步一步地逼近解,算到精度够了就行。假如f(x)有导函数f'(x) ,牛顿法就是这样的迭代程式:先取一个初始点x0作为解的近似,然后按下面的简单公式依次迭代:


    (1)


就得到一个序列x0, x1, x2, … 。只要满足三个并不苛刻的条件:(i)函数 f(x) 二次连续可导,(ii)在所求解x*处导数非零,加上(iii)初始近似x0足够接近x*,则这个序列将快速趋近 ,基本上是每一步精确数位加倍。因此,实际计算中大多三五步迭代就可以获得足够精确的近似解。读者可以很容易验证,巴比伦方法其实就是求解平方根方程x2-A=0的牛顿迭代。当然啦,巴比伦人不大可能知道“迭代”这个概念。


你要作科学计算和工程计算吗?几乎所有问题要么本身就是个方程,要么一定会在某个步骤需要解方程。作为解方程的基本通用算法,牛顿法是应用数学和计算数学最重要的算法之一。这个简单神速的算法被冠以牛顿大名,那它真是牛顿发现的吗?这是个历史悠久又颇有争议的传奇故事,其间包含数学史上一个个如雷贯耳的名字。


经久不衰的“谬误”


现在大家用的代数符号和表达式体系,创始人是法国人韦达 (François Viète,1541-1603) 。他的谋生职业是律师,他还做过亨利三世和四世的王室智囊,挣足了钱给自己提供经费研究数学并将结果出版。除了代数上的造诣,他还是方程理论的大师。他计算能力超强,在欧洲首次算出十位精确圆周率值。韦达在十七世纪初提出了一个多项式方程求根的算法,每一次计算精度数位增加一位。用现在的话说叫线性收敛或一阶收敛。韦达的算法解释起来很费功夫,有兴趣的读者可以参考引文[1] 。


据文献[2]考证,牛顿于1664年左右读到韦达的技巧,约1669年写入《分析论》De analysi。但这部书直至1711年才由威尔士数学家琼斯(William Jones,1675-1749)为他编辑出版。牛顿在书中改进了韦达的思路,提出一个近似求解多项式方程的新方法。以三次方程x3 – 2x – 5 = 0为例。他首先注意到在2与3之间有个解(读者可以用介值定理验证),于是他把这个解写成x = 2 + p, 代入原方程化简后得到p的三次方程p3 + 6 P2 + 10p – 1 = 0。当然,解这个新方程看起来跟老方程一样困难。但p的方程可以用上微积分的思路求解:因为p很小,它的平方和立方就更小,于是三次函数p3 + 6 p2 + 10p – 1 可以用线性部分 10p – 1近似。解10p-1=0 得到 p ≈ 0.1。也就是 x  的近似从 2 到 2.1, 精确数位翻倍。


然后,牛顿依法炮制,即令p = 0.1 + q,代入0 = p3 + 6 p2 + 10p – 1:


0= (0.1+q)3+6(0.1+q)2+10(0.1+q)-1=q3+6.3q2+11.23q+0.061≈11.23q+0.061


得到q ≈ -0.0054,也就是x=2.1+q≈2.0956 。再令q = -0.0054 + r,同法得r ≈-0.00004852。这样经过三步以后,牛顿找到原方程的一个8位精确的近似解:


x = 2 + p + q + r ≈ 2 + 0.1 – 0.0054 - 0.00004852 = 2.09455147


每算一步精确数位加倍!


在其1687年首版的辉煌巨著《自然哲学的数学原理》中,牛顿求解了用于天文学的x – e sin x = M这个超越方程。他将其中的正弦函数用级数展开,得到一个近似的多项式方程。然后他就可以用上述数值逼近多项式方程解的法子得到原方程的近似解。正如他在二十年前所做的那样,他没有明确地用到函数的导数概念来推导这个数值方法,也没有明确提出迭代概念和公式。


这就是后人所知牛顿参与创立“牛顿法”的过程。牛顿的贡献是用微积分思路,在韦达方法的基础上把巴比伦方法从平方根方程 x2-A=0 推广到一般的多项式求根


英国科学史专家Nicholas Kollerstrom于1992年发表了一篇关于牛顿法的考证文章[3]。文章的标题很有意思:《托马斯·辛普森和“牛顿近似法”:一个经久不衰的迷思》。意思是说把公式(1)称为“牛顿法”是个迷思(myth),也就是一个广泛流传的谬误,而且这个谬误“经久不衰”。他指出,牛顿法(1)有两个重要的特征:1. 它是一个迭代过程;2. 它采用了微分表达式。而这两个特征中的哪一个,都没有在牛顿的《分析论》里出现。迭代法在理论上是一个无穷极限过程,牛顿只给出了三步计算演示。其实还可以加上一条:由于没有使用微分,牛顿提出的方法只能用于多项式,不是一个通用算法。


第一个真正的迭代法


数值计算求解方程的第一个真正意义上的迭代法是跟牛顿同在英国的约瑟夫·拉夫森(Joseph Raphson,1648-1715)在他于1690年发表的文章《方程分析通论》中给出的近似方法。但它同样没有求导运算,因此不符合“牛顿法”的第二个特征。然而,一些慷慨的后人,包括部分现代数学家,把“牛顿法”的勋章切成一半分给了拉夫森——称之为“牛顿-拉夫森法”。


那么,拉夫森是怎么获得他的数值方法的呢?我们用求解三次方程x3 – ax + b = 0来描述他的求解方案。在每次迭代中,他分两步走。设目前的近似解为u,则将下一个的近似解写成u + d。然后用x=u + d代入方程并按二项式公式展开,这是第一步。在第二步,合并同类项得到d的一次项的系数3u2 – a,然后令 ,这样得到下一个近似解。


拉夫森强调用他的上述办法周而复始地迭代下去,就可以计算出满足任意精确的方程解。然而我们依然看不到求导数运算的影子。此外,他仅仅对多项式方程提出了这个迭代法,用到的二项式公式无法直接推广到像求解超越方程这样的情形。在他最初由伦敦皇家学会发表的那篇文章的前言里,他提到他的方法与牛顿之前的做法有类似之处。然而,七年后的1697年,当他把这个方法著书时没提牛顿的名字,而说韦达是他的方法的始祖。


如果我们比较牛顿和拉夫森的做法,不难发现,牛顿用到一个经过代入步骤而导出的一个似乎更加复杂的多项式,再丢掉高阶项求得近似;拉夫森从头到尾都是用给定的原多项式,运算要简单得多。拉夫森感觉自己的方法跟牛顿是完全不一样的推导,无需归功于牛顿。类似的比较也陆续出现。比如,在1796年发表的文章《关于拉夫森先生的方法的观察》中,作者费伦德(W. Frend)比较了两法的各自优点:“考虑到两种方法的简单性和概念性......我认为总的来说,拉夫森先生求解方程的方法比艾萨克·牛顿爵士的更为方便。”


在1798年,法国大数学家拉格朗日(Joseph-Louis Lagrange,1736-1813)发表了颇具影响力的论文《数值求解方程》。他精细化并推广了牛顿著作《分析论》中的方法,但依然没有用到导数或微分术语。


眼尖的读者很快就发现,在上述拉夫森得到的d的分数表达式中,分子就是函数x3 – ax + b在当前迭代点u的值,而分母恰恰就是这个函数的导数在此迭代点的负值,因而这就给出了“牛顿法”在多项式函数的全部内容。然而,不能因此就说拉夫森发明了今日所称的牛顿法!原因就在于他和牛顿一样,都没有使用导数的记号和运算而得出一般的牛顿法格式,仍然无法直接应用到一般的非线性方程。


被忘却的发明人


那么,谁才是“牛顿法”当之无愧的发明人呢?


此人的全名是托马斯·辛普森(Thomas Simpson,1710-1761),他是比牛顿和拉夫森迟了几十年的英国数学家。他就是近似数值积分著名的“辛普森法则”的那个辛普森。有意思的是,辛普森在牛顿法贡献恐怕最大,却被后人差不多忘得一干二净。他反而在数值积分法获得并非实至名归的荣誉。该得的没得到,不该得的反而拿着了。早他一百年,德国天文学家开普勒(Johannes Kepler,1571-1630)就已经发现了近似计算“曲边矩形”面积的该项法则。因此,德国人把我们叫惯了的辛普森法则自豪地称作为“开普勒的桶法则”,就像我们常常把关于二项展开式各项系数的“帕斯卡三角形”称为“杨辉三角形”那样异曲同工。


辛普森构造出现代意义下的牛顿法是在1740年,此时牛顿已经去世了十三年。那年他出了一本关于数学的论文集,其中一篇描述了“求解方程的一个新方法”,却没有列出任何先驱者的姓名。在前言部分,他断言:“因为它比以往的任何方法都更普遍,它不能不具有相当大的用途。”这听上去口气很大。他是自信而非吹牛:“取给定方程的流数……”此处,流数的英文是fluxion,正是牛顿当年用来表示今天我们所称的“导数”的那个东西——函数的瞬时变化率。接着,他给出了和上面公式(1)式实际一模一样的迭代程序,除了没有采用当今标准的、微积分另一发明人莱布尼茨(Gottfried Leibniz,1646-1716)所引进的导数记号。


辛普森用这个普遍方法做了五个例子,包括求解三次方程、平方根计算、指数方程等。更进一步,他第一个将他的方法用于求解含有两个未知数和两个方程的方程组!既然他是有史以来第一个完整地提出和今日所指的牛顿法有完全相同格式的迭代法,数学史专家Kollerstrom得出结论:辛普森才是牛顿法的发现者。


辛普森版的牛顿法跟现代教科书的差别仅仅是所用的符号。他应当之无愧地被授予创造该法的荣誉。然而,到底是谁写出了现代形式的牛顿法呢?


他就是在近代数学向前迈步的崎岖道路上留下巨大脚印的傅里叶(Joseph Fourier,1768-1830)。这位法国数学家在辛普森提出标准的牛顿法后的第二十八个年头才出生。在十九世纪初,他首次用当今世界通用的导数记号f’重新叙述了迭代法(1),同时把它说成是“牛顿法”。由于拉格朗日的那篇雄文,后来,有些英国数学家将此法称为“牛顿和拉格朗日的方法”,而对拉夫森只字不提。十九世纪的数学史名家、德国人康托尔(Moritz Cantor,1829-1920)考察了牛顿、拉夫森等人的方程近似求解法,把拉夫森描绘为“牛顿的绝对仰慕者和模仿者”,认为他的近似法“与牛顿的方法极其类似”。


瑞士出生的美国数学史家弗洛里安·卡乔里(Florian Cajori,1859-1930)在1911年的《美国数学月刊》上发文提出这个方法理应被称为“牛顿-拉夫森法”。但是,他的命名论据受到Kollerstrom的质疑,依据正是那个“两个特征”,后者认为荣誉只能归于辛普森。然而,著名的数学史家博耶(Carl Boyer,1906-1976)在他1968年出版的大作《数学史》中这样断言:“方程近似求解的牛顿法可在《分析论》中发现。”由于牛顿在科学史包括数学史上的巨大名望,拥有“牛顿法”的真正主人辛普森在数学史上几乎失去了立足之地,拉夫森也只能偶然出现在牛顿名字的后面。


这种张冠李戴的命名在科学和数学史中比比皆是。例如,学过初等微积分的人都知道求不定式极限的“洛必达法则”,实际上是瑞士数学家伯努利(Johann Bernoulli,1667-1748) 的杰作。伯努利的数学功力可不是法国数学家洛必达(Guillaume de l’Hôpital,1661-1704) 所能望其项背的。洛必达于1694年3月17日在给伯努利的信中,提出每年给他三百法郎换取他的最新数学发现,并且不能透露给第三者。当年伯努利告诉了洛必达这个求极限定理,两年后洛必达将它写进了自己的著作《曲线的无穷小分析》,据说这是全世界的第一本微积分教材。尽管洛必达在书中感谢了莱布尼茨和伯努利,尤其感谢伯努利,或许作者有意无意地没有明确承认“洛必达法则”是诞生于别人家的婴儿,不明就里的后人就把这条极其有用的求极限法则冠上了他的名字。当然伯努利在数学史上大名鼎鼎,少了个洛必达法则也不至于沦落成籍籍无名的历史过客。


牛顿法的基本思想和深层含义是什么?哪些激情探索者又续写传奇?且待下篇


后记:作者以此文纪念我们的导师李天岩教授(1945年6月28日-2020年6月25日)逝世一周年。


参考文献

[1] Tjalling J. Ypma, Historical Development of the Newton-Raphson Method, SIAM Review, 37, 531-551, 1995

[2] P. Deuflhard,“A short history of Newton’s method,”Documenta Math.,Extra Volume ISMP,25,25-30,2012.

[3] N. Kollerstrom,“Thomas Simpson and ‘Newton’s method of approximation’:an enduring myth,”BJHS,25, 347-354,1992.


相关阅读

从牛顿、三体到混沌:科学认知如何从简单到复杂

蝴蝶效应和混沌故事

滴水映照大海:一元二次方程里的深刻学问 | 贤说八道

你真的会解方程吗?

中心极限定理:从高尔顿板到麦克斯韦分布


近期推荐

1  失温冻死,不仅仅在严冬,也不仅仅在室外

2  物理学需要形而上

3  高龄产“父”,该喜?该忧?

4  薛定谔方程该写成什么样儿?丨贤说八道

5  谁是中国第一位数学女博士?


特 别 提 示

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

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

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


收不到推送了?快加星标!!




长按下方图片关注「返朴」,查看更多历史文章

微信实行乱序推送,常点“在看”,可防失联

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存