图 7.9
收敛
于 ${x_n}$ 到 $\sqrt{2}$ .

我们将通过求出 $N$ 的表达式来说明所用方法的类型，这是计算 $\sqrt{2}$ 的一种经典方法。它使用迭代

$$x_{n+1} = \frac{2 + x_n}{1 + x_n} \text{ with } x_0 = 1$$

这产生有理逼近

$$\left{1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \dots\right}$$

最后给出的逼近误差小于 0.0001。假设我们要求一个精确到 $p$ 位小数的逼近；那么我们需要找到一个 $N$ 使得

$$|x_n - \sqrt{2}| < 0.5 \times 10^{-p}$$

对于 $n > N$ 。写作 $\varepsilon_n = x_n - \sqrt{2}$ 使得 $x_0 = \sqrt{2} + \varepsilon_0, x_1 = \sqrt{2} + \varepsilon_1, \dots, x_{n+1} = \sqrt{2} + \varepsilon_{n+1}$ （等等）我们有

$$\sqrt{2} + \varepsilon_{n+1} = \frac{2 + \sqrt{2} + \varepsilon_n}{1 + \sqrt{2} + \varepsilon_n}$$

交叉相乘，我们得到

$$(\sqrt{2} + \varepsilon_{n+1})(1 + \sqrt{2} + \varepsilon_n) = 2 + \sqrt{2} + \varepsilon_n$$

由此可得

$$\sqrt{2} + 2 + \sqrt{2}\varepsilon_n + (1 + \sqrt{2})\varepsilon_{n+1} + \varepsilon_{n+1}\varepsilon_n = 2 + \sqrt{2} + \varepsilon_n$$

进一步化简得

$$(1 + \sqrt{2} + \varepsilon_n)\varepsilon_{n+1} = -\varepsilon_n(\sqrt{2} - 1)$$

因此，由于 $x_n = \sqrt{2} + \varepsilon_n$

$$|\varepsilon_{n+1}| = \frac{(\sqrt{2} - 1)|\varepsilon_n|}{1 + x_n}$$