迭代算法的平方收斂

湯 濤

（南方科技大學數學系 518055）

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

就叫迭代法.

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

1 迭代算法求根

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

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

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

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

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

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

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

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

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

結合上面這兩個結果可以得到：

這種性質稱為二次收斂或平方收斂.具……