正数开方运算的牛顿迭代法（用牛顿迭代法求1~n之间所有整数的算术平方根）

之前介绍过一个利用连分式逼近计算根式的方法,但是涉及到指数和对数运算.之后经常收到私信问有没有更直接的方法,不需要指\对数运算,就是简单粗暴的四则运算.答案是当然有,最常用的就是以拿苹果的牛顿大爷的名字所命名的迭代法.

[1] 牛顿迭代法的算法原理

假如函数f是可微的,那么y=f(x)的图形在每一点都有一条切线。如果可以利用图形或其他方法找到图形与x轴交点(r,0)处的第一个近似值,那么下一个更佳的近似值应该位于点(,)处的切线与x轴的交点处。利用作为r的第二个近似值，以此类推可以找到更加接近于(r,0)的近似值。

这一过程非常容易程序化，因为在点(,)处的切线方程为:

令y=0即可解出x,求得其与x轴交点的横坐标为:

更一般的,可以归纳为以下的算法,也叫做牛顿递归公式或牛顿迭代公式:

假定f(x)是可微函数,且假定为方程f(x)=0的根r的初始近似值,用E表示误差的上限,

对i=1,2,...重复计算,直到

[2] 正数开N次方的快速收敛算法

利用牛顿迭代法,可以在实数域内研究一个正数a开n次方(n为不小于2的正整数)的迭代算法:

构造函数:,那么当y=0时,即方程 的解为 .那么迭代其实就是求该方程的近似数值解.下图显示了(n=3,a=5)时的图象示意:

根据迭代公式,有:

上面的迭代公式仍然存在一个问题:首个正数是如何取得的?

先说答案:初值可以取任意正数.

因为正数a开n次方的构造函数 求二阶导数,有:

当 时有 恒成立.说明函数在时是凸函数.即此段函数不存在拐点.而没有拐点的函数图象,对牛顿迭代是友好的,是收敛的.取的任意初值,最终迭代都会收敛.

反之,若函数图象存在拐点,则初值不能任意选择,不合适的初值可能会出现迭代困难或错误的结果。下图是一个典型的迭代困难(陷入死循环)的函数图象示意:

=================

最终,我们得到了正数a开n次方的收敛数列公式(基于牛顿迭代原理):

初值可以取任意正数,当时,数列收敛于

================

该方法有两点问题需要指出:

[1] 该方法每次迭代都需要计算的倒数,当n较大时,计算量并不小.并不适合手工计算.

[2]虽然的值可以取任意正数,但该值取的越接近迭代效率越高,下面是利用Excel计算的两个例子,初值都是取2,第一个例子更接近r,明显迭代次数更少: