Python编程实现二分法和牛顿迭代法求平方根代码(python erf)

编辑：rootadmin

推荐整理分享Python编程实现二分法和牛顿迭代法求平方根代码(python erf)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:python2//4,python2ide,python 2to3,python2ide,python2怎么用,python 2,python 2to3,python 2to3,内容如对您有帮助，希望把文章链接给更多的朋友！

求一个数的平方根函数sqrt(int num) ,在大多数语言中都提供实现。那么要求一个数的平方根，是怎么实现的呢？实际上求平方根的算法方法主要有两种：二分法(binary search)和牛顿迭代法(Newton iteration)

1：二分法

求根号5

a:折半： 5/2=2.5b:平方校验: 2.5*2.5=6.>5，并且得到当前上限2.5c:再次向下折半:2.5/2=1.d:平方校验：1.*1.=1.<5,得到当前下限1.e:再次折半:2.5-(2.5-1.)/2=1.f:平方校验：1.*1.=3.<5,得到当前下限1.

每次得到当前值和5进行比较，并且记下下下限和上限，依次迭代，逐渐逼近平方根：

运行结果：1 2. 1. 1. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2. 2...[Finished in 0.1s]

经过次二分法迭代，得到的值和系统sqrt()差别在0.，精度在亿分之一，

0.需要迭代8次

因此，在对精度要求不高的情况下，二分法也算比较高效的算法。

2：牛顿迭代

仔细思考一下就能发现，我们需要解决的问题可以简单化理解。

从函数意义上理解：我们是要求函数f(x)=x²，使f(x)=num的近似解，即x²-num=0的近似解。

从几何意义上理解：我们是要求抛物线g(x)=x²-num与x轴交点（g(x)=0）最接近的点。

我们假设g(x0)=0，即x0是正解，那么我们要做的就是让近似解x不断逼近x0，这是函数导数的定义：

可以由此得到

从几何图形上看，因为导数是切线，通过不断迭代，导数与x轴的交点会不断逼近x0。

对于一般情况：

将m=2代入：

运行结果：1 2. 2. 2...

精确到亿分之一，牛顿法只迭代了3次，是二分法的十倍

3：利用牛顿法求开立方

微积分、概率、线代是高级算法的基础课。可是，这么多年，已经忘得差不多了..............................

总结

本文链接地址:https://www.jiuchutong.com/biancheng/377056.html 转载请保留说明！