迭代算法的平方收斂

湯 濤

（南方科技大學(xué)數(shù)學(xué)系 518055）

給定一個函數(shù)f（x）以及一個初始值x0，然后重復(fù)地計算

就叫迭代法.

迭代法在人類有了計算機以后產(chǎn)生了巨大的作用.它利用計算機運算速度快、適合做重復(fù)性操作的特點、讓計算機重復(fù)執(zhí)行一組指令（或一定步驟）、在每次執(zhí)行這組指令（或這些步驟）時、都從變量的原值推出它的一個新值.雖然迭代法的思想產(chǎn)生在很久以前，包括阿基米德、劉徽都用過，但在計算機出現(xiàn)以前，迭代法僅僅具有算法思想，難以付諸實用，其生命力也就非常有限了.

1 迭代算法求根

一個最典型的迭代法的例子就是開根號.假設(shè)我們不知道如何開根號，這樣就沒有辦法求.

換一個思路.我們問如何求x2-2=0的根或其近似根？考慮x2-2=0的一個等價形式：

這就可形成一個迭代算法：大概地給定一個初始近似值x0，通過下面的公式逐次形成x1，x2，…：

即不斷令xk+1等于xk和2/xk的算術(shù)平均數(shù)，迭代六、七次后得到的值就己經(jīng)相當(dāng)精確了.

例如，假設(shè)首先猜測根號2的初始近似值為1，雖然它不是很準(zhǔn)確，但從表1可以看到：使用迭代法（1）后，迭代值很快趨近于.注意到迭代6次有近50位有效數(shù)字，而迭代7次就有近100位的有效數(shù)字！

為什么會有這么好的精確度呢？

下面我們做一些簡單分析.由（1），根據(jù)算術(shù)平均數(shù)大于幾何平均數(shù)得出：

表1 迭代算法（1）前7次迭代后的近似值；底下劃線部分是精確值

另一方面，仍由（1）可以得到：

結(jié)合上面這兩個結(jié)果可以得到：

這種性質(zhì)稱為二次收斂或平方收斂.具有這種性質(zhì)的算法收斂非?？?，每迭代一步就可以加倍小數(shù)點后面的有效數(shù)字.比如一開始的誤差是10-1，在迭代6次的過程中產(chǎn)生的誤差分別是10-2，10-4，10-8，10-16，10-32，10-64的量級！

那么，是不是每個迭代公式部可以收斂得這么快呢？笞案是否定的.比如考慮求的近似值、通過下面這個恒等式：

可以得到迭代公式

這個迭代對任何給定的初始值x0都是收斂的.如取初始值為x0=3就可以得到表2的結(jié)果.這時，區(qū)別就看出來了：對于迭代算法（2）、迭代7次以后，僅能得到5位有效數(shù)字，而不是前面例子斷給出的近100位有效數(shù)字.

表2 迭代算法（2）前7次迭代后的近似值

笞案是肯定的.我們還是考慮下面的形式：

其中A，B為待定系數(shù).首先需要（3）和x2=3等價，也就是說：

另一方面，對于迭代公式xk+1=A xk+B/xk可以推出

滿足

2 求圓周率的平方收斂算法

目前最快的計算圓周率的迭代算法基于高斯（Karl Gauss，1777—1855）和勒讓德（Adrien-Marie Legendre，1752—1833）的純數(shù)學(xué)理論，它于19 75年被布倫特（Richard Brent）和薩拉明（Eugene Salamin）提煉為適合計算機計算的現(xiàn)代算法.此算法以迅速收斂著稱，只需25次迭代即可產(chǎn)生π的45 00萬位正確數(shù)字.日本筑波大學(xué)于2009年8月17日宣布利用此算法計算出π小數(shù)點后2500多億（2，576，980，370，000）位數(shù)字.

下面給出高斯-勒讓德算法：選取初值

此算法之所以被稱為高斯一勒讓德算法，是因為這兩位大數(shù)學(xué)家貢獻(xiàn)了原始思想；在19世紀(jì)，高斯己經(jīng)知道算術(shù)一幾何平均迭代可以導(dǎo)致二次收斂，就象上節(jié)通過近似求解的例子那樣具有快速的收斂性質(zhì)；而勒讓德推導(dǎo)出的一個關(guān)于橢圓積分的恒等式是算法成功的一個重要保證.

在上表的算例中，我們先取n=0，算出a1，b1，t1，p1，π1的值，之后再讓n=1，重復(fù)下去，就會得到一系列的數(shù)據(jù)πn來近似π.從數(shù)值結(jié)果可以看出，高斯-勒讓德算法是平方收斂的，即如上節(jié)例子所演示的那樣，誤差隨著迭代次數(shù)成平方階遞減.特別地，迭代3次后就可以得到19位有效數(shù)字，迭代5次就可以得到84位，迭代6次后有效數(shù)字171，而迭代7次時，有效數(shù)字就增加為345.

由于篇幅限帶，高斯-勒讓德算法的平方收斂推導(dǎo)將不在此給出.有興趣的讀者可以參考作者近期準(zhǔn)備的一個小冊子[1].