牛顿迭代

函数y = f(x)在点(a, f(a))处的切线方程为：y - f(a) = f'(a)(x - a)
令y = 0得，x = a - f(a) / f'(a)
从而得到递推公式：x' = x - f(x) / f'(x)

例1：求N的算术平方根

x ^ 2 = N
构造：f(x) = x ^ 2 - N
那么：f'(x) = 2x
x' = x - (x ^ 2 - N) / (2 * x)
= (x + N / x) / 2
从而递推公式为：x' = (x + N / x) / 2

以下是迭代计算45的算术平方根过程，初始值取1：

x = 1.000000    x' = 23.000000
x = 23.000000   x' = 12.478261
x = 12.478261   x' = 8.042266
x = 8.042266    x' = 6.818852
x = 6.818852    x' = 6.709102
x = 6.709102    x' = 6.708204
x = 6.708204    x' = 6.708204

例2：求N的倒数

1 / N = x
1 / x = N
构造：f(x) = 1 / x - N
那么：f'(x) = -1 / x ^ 2
x' = x - (1 / x - N) / (-1 / x ^ 2)
= x * (2 - N * x)
从而递推公式为：x' = x * (2 - N * x)

取初值为0.01，迭代计算45的倒数过程如下：

x = 0.010000    x' = 0.015500
x = 0.015500    x' = 0.020189
x = 0.020189    x' = 0.022036
x = 0.022036    x' = 0.022221
x = 0.022221    x' = 0.022222
x = 0.022222    x' = 0.022222

牛顿迭代至少是二阶收敛的，速度快，迭代10多次就能得到相当高的精度，但前提是：

• 构造出合适的f(x)函数；
• 选择恰当的迭代初值；

根据牛顿迭代的几何意义，更容易理解上述两点。