历史上最著名的 3 个数学算法，关于算法的观念，直到今天还在演进

对于“算法”一词给以精确的定义不是一件容易事，有一些意义相近的同义语，就是一些其他的名词，它们（有时）会给出差不多同样的东西，例如 "法则"" 技巧”“程序”还有“方法”等等都是这种同义语。也可以给出一些例子，如长乘法，就是小学生学的把两个正整数相乘的竖式乘法。然而，虽然非形式的解释和恰当的例子对于什么是算法给出了很好的感觉，但算法一词中所深藏的思想却经历了一个很长的演化历程，直得到 20 世纪才得到了令人满意的形式定义，而关于算法的观念，直到如今还在演进。

算盘家和算法家

回到关于乘法的例子，有一点是显然的：怎样把两个数相乘？表示这些数的方法极大地影响了乘法的具体作法。为了弄明白这点，试着把两个罗马数字 CXLVII 和 XXIX 相乘，但不要先把它们译成等价的十进数字 147 和 29。这件事既难弄明白，明白了以后进行计算也极其花时间，而这就可以解释何以留存至今的罗马帝国关于乘法的材料极为零散。记数制可以是 " 累加的 "，如罗马记数法：

C 表示 100。X 表示 10。L 表示 50，但是 X 放在 L 左方表示要从 L 中减去 X，所以就是 40，V 表示 5，I 表示 1，两个 I 放在 V 的右方，表示要把它们加到 V 上，所以是 7。把所有以上的解释“累加”起来，就是罗马数学的 147。

记数制度也可以是进位的，如我们今天所用的那样。如果是进位的，可以使用一个或多个基底。

在很长的时期中，进行计算可以使用一种计算工具 "算盘（abacus）"。这些计算工具可以表示一定基底下的进位制的数。例如，如果以 10 为基底、则一个标记物可以代表 1 个单位、或者 10。或者 100 等等，视它是放在哪一横行或竖列而定。按照精确的规则移动这些标记物，就可以进行算术四则运算。中国的算盘就是 abacus 的一种。

到 12 世纪，阿拉伯数学著作被翻译为拉丁文以后，十进制就在欧洲流行开来了。这种进位制特别适合于算术运算，并且引导到许多新的计算方法。这些方法就通称为算法（algoritmus），而与在算盘上用标记物进行计算相区别。

虽然数字符号，就是数码，来自印度人的实践，而后来才为阿拉伯人所知，现在这些数码却叫做阿拉伯数码．算法（algorithm）的字源却是阿拉伯文，它是阿拉伯数学家阿尔・花拉子米的名字的变体。花拉子米是现在已知的最古老的数学书的作者，这一著作名为 《通过补全和还原做计算的纲要》（al-Kitab al-mukhtasar f hisib al-jabr wod ll-mugi balo），其中的 al-jabr 后来就变成了“代数”（algebra）一词。

有限性

我们已经看到“算法”一词在中世纪是指以整数的十进制表示为基础的计算程序。但是到了 17 世纪，在达朗贝尔主编的《百科全书》中，算法一词被赋予了更广泛的意义，不只用于算术，还用于关于代数方法以及其他的计算程序，诸如 "积分学的算法"" 正弦的算法 " 等等。

算法这个词又逐渐地被用来表示任意的具有精确规则的系统的计算程序。最后，随着计算机的作用越来越大，有限性的重要性被充分认识到了，很本质的要求是，这个过程在有限时间以后就会停止，而给出结果。所以就得到了下面的朴素的定义：

一个算法就是有限多个规则的集合，用以对数量有限的数据进行操作，而在有限多步以后产生结果。

注意，在这里一直强调有限性，在写出算法时的有限性，以及在执行算法时的有限性。

上面的陈述算不上是在经典意义下的数学定义。我们将会看到，把它进一步形式化是重要的。但是我们现在暂时也就满足于这个 "定义" 了，而且来看一下数学中的算法的一些经典例子。

三个历史上的例子

算法具有一种我们尚未提到的特性：迭代，也就是简单程序的反复执行。为了看清迭代的重要性，我们再一次来看一下长乘法这个例子，这是一个对任意大小的正整数都适用的方法。数字变得越大、程序也就越长。但是最关紧要的是，方法是“同样的”，如果会把两个三位数相乘，也就会把两个 137 位的数字相乘，而不必再去学什么新的原理，理由在于长乘法的方法里面包含了大量的仔细构造好的小得多的任务的重复执行，例如把两个一位数相乘的九九表。我们将会看到，迭代在我们所要讨论的算法中起了重要作用。

欧几里得算法：迭代

欧几里得算法是说明算法本质的最好也是最常用的例子。这个算法可以追溯到公元前 3 世纪。欧几里得用它来计算两个正整数的最大公约数（gcd）。

当我们最开始遇到两个正整数 a 和 b 的最大公约数时，它是定义为一个正整数，而且同为 a 和 b 的因数。然而，为了很多目的，定义它为具有以下两个性质的唯一的整数 d 更好。这两个性质就是：

首先，d 是 a 和 b 的一个因数；

其次，如果 c 是 a 和 b 的另一个因数，则 d 可以被 c 所整除。

欧几里得的《几何原本》卷 VII 的前两个命题给出了求 d 的方法，其中第一个命题如下："给定了两个不相等的数、从较大的一数不断地减去较小的一数，如果余下的数位，都不能量度前数，直到余下的数为一单位为止，这时，原来的数为互质。" 换句话说，如果辗转相减得到了数 1，则 gcd 为 1。这时，就说原来的两个数互质（或互为素数）。

辗转相减法

现在我们来一般地描述欧几里得算法，它是基于以下两点观察的：

（1）如果 a=b，则 a 和 b 的 gcd 就是 b（或 a）。

（2）d 是 a 和 b 的公约数，当且仅当它也是 a-b 和 b 的公约数。

现在设要求 a 和 b 的 gcd，而且设 a≥b。如果 a=b，则观察（1）告诉我们，gcd 就是 b。若不然，观察（2）告诉我们，如果求 a-b 和 b 的 gcd 也会得到同样的答案。现在令 a_1 是 a-b 和 b 中较大的一个，而 b_1 则为其中较小的一个，然后再求两数的 gcd。不过，现在两数中较大的一个，即 a_1，小于原来两数中较大的一个，即 a。这样我们就可以把上面的程序再重复一遍：若 a_1=b_1，则 a_1 和 b_1 的 gcd，亦即 a 和 b 的 gcd 是 b_1，若不然，就把 a_1 换成 a_1-b_1，再来组织 a_1-b_1 和 b_1，总之，较大的一个要放在前面，然后再继续下去，这就叫做 " 辗转相减 "。

为了使这个程序能够进行下去，还有一个观察是需要的，这就是下面的关于正整数的一个基本事实，有时称为良序原理：

严格下降的正整数序列 a_0 > a1 > a2 >… 必为有限序列。

因为上面的迭代程序恰好产生了一个严格下降序列，这个迭代最终一定会停止，这就意味着在某一点上必有 a_k=b_k，而这个公共值就是 a 和 b 的 gcd。

欧几里得除法

通常对于欧几里得算法的陈述与此稍有不同。可以应用一种较复杂的程序，称为欧几里得除法（也就是带余除法），它可以大大减少算法的步数，这种算法也称为辗转相除法。这个程序的基本事实是：若 a 和 b 是两个正整数，则必存在唯一的整数 q 和 r，使得

数 q 称为商，而 r 称为余数。上面的两点说明（1）和（2）现在要代以

• 若 r=0，则 a 和 b 的 gcd 就是 b。

• a 和 b 的 gcd 与 b 和 r 的 gcd 是相同的。

这一次，在第一步要用（b，r）代替（a，b）。如果 r≠0，则还要做第二步，并用（r，r_1）来代替（b，r），r1 是用 r 去除 b 所得的余数，所以 r_1<r，并仿此以往。这样，就得到余数的序列是严格下降的（b>r>m>r1>r2≥0）。再用一次良序原理，即知这个程序经过有限步后一定停止，而最后一个非零的余数就是 a 和 b 的 gcd。

不难看到，这两种方法，就求 gcd 而言是等价的，但就算法而言则有很大区别。例如，设 a=103 438，b=37。如果用辗转相减法，就要从 103 438 中累次减去 37，一直到余下的差数小于 37 为止。这个差数与 103438 除以 37 的余数是一样的，而如果用第二种方法，一次就可以得到它。这样，使用第二种方法的理由就在于用累次减法来求除法的余数是非常低效率的。效率上的收益在实践上是很重要的，第二种方法给出的是多项式时间算法，而第一种方法所需的则是指数长的时间。

推广

欧几里得算法可以推广到许多其他背景下，只要有加法、减法和乘法的概念就行。例如它有一个变体，可以用于高斯整数环。就是形如 a＋ bi，而其中 a，b 为整数的复数所成的环，它也可以用于系数为实数的多项式环中（就此而论，系数在任意域中也行）。但有一个要求，就是要能够定义带余除法的类比物，有了这一点以后、算法就与正整数情况的算法基本上相同了。例如下面的命题：设 A 和 B 是两个任意多项式，而且 B 不是零多项式、则必存在两个多项式 Q 和 R。使得或者 R=0，或者 R 的次数小于 B 的次数。

正如欧几里得在《几何原本》中提到的那样，也可以对于一对数（a，b）当 a 和 b 不一定是整数时实行这个程序。容易验证，当且仅当比 a / b 是有理数时，这个程序会停下来。这个观点引导到连分数的概念。在 17 世纪以前，没有特别地研究过它，但是其中的思想根源可以追溯到阿基米德。

阿基米德计算 π 的方法：逼近和有限性

圆周长和圆的直径的比值是一个常数，而自从 18 世纪以来就记作 π。现在我们来看一看阿基米德怎样在公元前 3 世纪就得到了这个比值的经典的近似值 22/7。若在圆内作一个内接的正多边形（其顶点都在圆周上），又作其外切的正多边形（其边都是圆周的切线），再计算这些多边形的周长，就会得到 x 的下界与上界，因为圆的周长必定大于任意内接多边形的周长，而小于任意外切多边形的周长。阿基米德从正六边形开始，然后，每次把多边形的边数加倍，得到了越来越精确的上下界。他做到九十六边形为止，得到了

这个过程中显然涉及迭代。但是称它为一个算法对不对？严格地说，它不是一个算法，不论取多少边的多边形，所得到的仅是 π 的近似值，所以这个过程不是有限的。然而我们确实得到了一个可以近似计算 π 到任意精确度的算法。例如。如果想得到 π 的一个准确到小数十位的近似值，经过有限多步以后，这个算法会给出一个我们想要的近似值。重要的是，这个过程是收敛的。就是说，重要的在于由迭代得出之值可以任意地接近于 π。这个方法的几何来源可以用来证明这个收敛性，而 1609 年德国人作到了 202 边形（基本上用阿基米德的方法），得到 π 的精确到小数 35 位的近似值。

然而，逼近 π 的算法与阿基米德计算两个正整数的 gcd 的算法有一个明显的区别。如欧几里得那样的算法时常称为离散算法，而与用来计算非整数值的数值算法相对立。

牛顿-拉夫森方法：递推公式

1670 年前后、牛顿提出了一个求方程之根的方法，而且就方程 x^3-2x-5=0 解释了他的方法。他的解释从下面的一个观察开始：根 x 近似地等于 2。于是他写出 x=2+p，并用 2＋p 代替原方程的 x，而得到了一个关于 p 的方程。这个新方程算出来是

因为 x 接近于 2，所以 p 很小，而他就略去了 p^3 和 6p^2 来估计 p。这就给了他 p 的方程 10p-1=0，即 p=1/10。这当然不是一个准确解，但是，给了牛顿关于根的新的更好的近似值：x=2.1。然后牛顿就重复这个过程，令 x=2.1＋q，代入原方程以后又给出了一个关于 q 的方程，近似地解这个方程，又把他的近似解精确化了，于是得到 q 的估计为-0.0054，所以 x 的下一个近似值是 2.0946。

尽管如此，我们怎么能确定这个过程会收敛于 x 呢？让我们更仔细地考察这个方法。

切线和收敛性

牛顿的方法可以从几何上用函数 f 的图像来解释，虽然牛顿本人并没有这样做。f（x）=0 的每一个根 x 都对应于函数 y=f（x）的曲线和 x 轴的一个交点。如果从根 x 的一个近似值 a 开始，而且和上面做的一样，设 p=x- a，于是可以用 a+p 代替 x 而得到一个新的函数 g（p），也就是说把原点（0，0）有效地移到了（a，0）处。然后把 p 的所有高次幂都略去，只留下常数项和线性项，这样就得到了函数 g 的最佳的线性逼近 —— 从几何上说，这就是 g 在点（0，g（0））处的切线。

这样，对于 p 所得到的近似值就是函数 y 在点（0，g（0））处的切线与 x 轴的交点。再在横坐标上加一个 a，也就是让原点回到原来的（0，0）处，这样 a＋p 就给出了 f 的根的新近似值。这就是牛顿的方法称为切线法的原因。

从上图可以看到，再作一次切线的逼近，如果曲线 y=f（x）与 x 轴的交点在 a 点以及 f 在点（a，f（a））处的切线与 x 轴的交点（即上图中的横坐标为 a+p 的点，即根的近似值）之间，则第二次的近似值（即 a＋p＋q）肯定比第一次的近似值 a＋p 好（这里称 a 为根的零次近似）。

回到牛顿的例子，可以看到牛顿选取 a=2 并不是上面所说的情况。但是从下一个近似值 2.1 开始，以下所有的近似值就都是这个情况了。从几何上看，如果点（a，f（a））位于 x 轴的上方，而且 y=f（x）的曲线在凸部与 x 轴相交，或者点（a，f（a））在 x 轴的下方，而且 y=f（x）曲线在凹部与 x 轴相交，就会出现这种有利的情况。

初始的逼近（即零次近似）的选择显然是很重要的，而且提出了微妙的未曾想到的问题。如果我们考虑复多项式的复根，这就更加清楚了。牛顿的方法很容易适应这个更广泛的背景。设 z 是一个复多项式的复根，而 z_0 是初始的逼近，于是牛顿方法将给出一个序列 z_0，z_1，z_2…… 它可能收敛于 z，也可能不收敛。我们定义根 z 的吸引区域为这样的初始逼近 z_0 的集合，使得所得到的序列确实收敛于 z，并且记这个区域为 A（z）。怎样来决定 A（z）呢？

第一个问这个问题的人是凯莱，时间是 1879 年。他注意到，对于二次多项式，这个问题是很容易的，但当次数为 3 或者更大时，问题就很困难了。例如多项式 z^2-1 的根 ±1 的吸引区域分别是复平面上以铅直轴为界的两个半平面，但是 z^3-1 的三个根 1，w，w^2 的相应的吸引区域就是极复杂的集合。这些集合是由儒利亚在 1918 年描述的，而现在称为分形集合。

递推公式

牛顿方法的每一阶段都会产生一个新方程。但是拉夫森指出实际上并无必要。他就特殊的例子给出在每一步都可以使用的单一一个公式。但是他的基本的观察可以一般地适用，导出可以用于每一个情况的一般公式，而这个公式用切线的解释就可以容易得出。事实上，曲线 y=f（x）在 x 坐标为 a 处的切线方程是

它与 x 轴的交点的横坐标是 a-f（a）/f'（a）。我们现在所说的牛顿-拉夫森方法就是指的这个公式。我们从一个初始逼近 a_0=a 开始再用这个递推公式得出

这样就得到一个逼近的序列，在复情况下，也就是前面说的 z_0，z_1，z_2，…。

作为一个例子，考虑函数 f（x）=x^2-c。这时，牛顿方法就给出 c 的平方根根号 c 的一串近似值，递推公式现在成了

在上面的一般公式中把 f 换成 x^2-c 即得。这个近似平方根的求法，公元 1 世纪的亚历山大里亚的海伦就已经知道。

本文来自微信公众号：老胡说科学 （ID：LaohuSci），作者：我才是老胡

广告声明：文内含有的对外跳转链接（包括不限于超链接、二维码、口令等形式），用于传递更多信息，节省甄选时间，结果仅供参考，IT之家所有文章均包含本声明。