湯 濤
(南方科技大學(xué)數(shù)學(xué)系 518055)
給定一個(gè)函數(shù)f(x)以及一個(gè)初始值x0,然后重復(fù)地計(jì)算
就叫迭代法.
迭代法在人類(lèi)有了計(jì)算機(jī)以后產(chǎn)生了巨大的作用.它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)、讓計(jì)算機(jī)重復(fù)執(zhí)行一組指令(或一定步驟)、在每次執(zhí)行這組指令(或這些步驟)時(shí)、都從變量的原值推出它的一個(gè)新值.雖然迭代法的思想產(chǎn)生在很久以前,包括阿基米德、劉徽都用過(guò),但在計(jì)算機(jī)出現(xiàn)以前,迭代法僅僅具有算法思想,難以付諸實(shí)用,其生命力也就非常有限了.
一個(gè)最典型的迭代法的例子就是開(kāi)根號(hào).假設(shè)我們不知道如何開(kāi)根號(hào),這樣就沒(méi)有辦法求.
換一個(gè)思路.我們問(wèn)如何求x2-2=0的根或其近似根?考慮x2-2=0的一個(gè)等價(jià)形式:
這就可形成一個(gè)迭代算法:大概地給定一個(gè)初始近似值x0,通過(guò)下面的公式逐次形成x1,x2,…:
即不斷令xk+1等于xk和2/xk的算術(shù)平均數(shù),迭代六、七次后得到的值就己經(jīng)相當(dāng)精確了.
例如,假設(shè)首先猜測(cè)根號(hào)2的初始近似值為1,雖然它不是很準(zhǔn)確,但從表1可以看到:使用迭代法(1)后,迭代值很快趨近于.注意到迭代6次有近50位有效數(shù)字,而迭代7次就有近100位的有效數(shù)字!
為什么會(huì)有這么好的精確度呢?
下面我們做一些簡(jiǎn)單分析.由(1),根據(jù)算術(shù)平均數(shù)大于幾何平均數(shù)得出:
表1 迭代算法(1)前7次迭代后的近似值;底下劃線部分是精確值
另一方面,仍由(1)可以得到:
結(jié)合上面這兩個(gè)結(jié)果可以得到:
這種性質(zhì)稱(chēng)為二次收斂或平方收斂.具有這種性質(zhì)的算法收斂非???,每迭代一步就可以加倍小數(shù)點(diǎn)后面的有效數(shù)字.比如一開(kāi)始的誤差是10-1,在迭代6次的過(guò)程中產(chǎn)生的誤差分別是10-2,10-4,10-8,10-16,10-32,10-64的量級(jí)!
那么,是不是每個(gè)迭代公式部可以收斂得這么快呢?笞案是否定的.比如考慮求的近似值、通過(guò)下面這個(gè)恒等式:
可以得到迭代公式
這個(gè)迭代對(duì)任何給定的初始值x0都是收斂的.如取初始值為x0=3就可以得到表2的結(jié)果.這時(shí),區(qū)別就看出來(lái)了:對(duì)于迭代算法(2)、迭代7次以后,僅能得到5位有效數(shù)字,而不是前面例子斷給出的近100位有效數(shù)字.
表2 迭代算法(2)前7次迭代后的近似值
笞案是肯定的.我們還是考慮下面的形式:
其中A,B為待定系數(shù).首先需要(3)和x2=3等價(jià),也就是說(shuō):
另一方面,對(duì)于迭代公式xk+1=A xk+B/xk可以推出
滿(mǎn)足
目前最快的計(jì)算圓周率的迭代算法基于高斯(Karl Gauss,1777—1855)和勒讓德(Adrien-Marie Legendre,1752—1833)的純數(shù)學(xué)理論,它于19 75年被布倫特(Richard Brent)和薩拉明(Eugene Salamin)提煉為適合計(jì)算機(jī)計(jì)算的現(xiàn)代算法.此算法以迅速收斂著稱(chēng),只需25次迭代即可產(chǎn)生π的45 00萬(wàn)位正確數(shù)字.日本筑波大學(xué)于2009年8月17日宣布利用此算法計(jì)算出π小數(shù)點(diǎn)后2500多億(2,576,980,370,000)位數(shù)字.
下面給出高斯-勒讓德算法:選取初值
此算法之所以被稱(chēng)為高斯一勒讓德算法,是因?yàn)檫@兩位大數(shù)學(xué)家貢獻(xiàn)了原始思想;在19世紀(jì),高斯己經(jīng)知道算術(shù)一幾何平均迭代可以導(dǎo)致二次收斂,就象上節(jié)通過(guò)近似求解的例子那樣具有快速的收斂性質(zhì);而勒讓德推導(dǎo)出的一個(gè)關(guān)于橢圓積分的恒等式是算法成功的一個(gè)重要保證.
在上表的算例中,我們先取n=0,算出a1,b1,t1,p1,π1的值,之后再讓n=1,重復(fù)下去,就會(huì)得到一系列的數(shù)據(jù)πn來(lái)近似π.從數(shù)值結(jié)果可以看出,高斯-勒讓德算法是平方收斂的,即如上節(jié)例子所演示的那樣,誤差隨著迭代次數(shù)成平方階遞減.特別地,迭代3次后就可以得到19位有效數(shù)字,迭代5次就可以得到84位,迭代6次后有效數(shù)字171,而迭代7次時(shí),有效數(shù)字就增加為345.
由于篇幅限帶,高斯-勒讓德算法的平方收斂推導(dǎo)將不在此給出.有興趣的讀者可以參考作者近期準(zhǔn)備的一個(gè)小冊(cè)子[1].