Python编程实现二分法和牛顿迭代法求平方根代码
求一个数的平方根函数sqrt(int num),在大多数语言中都提供实现。那么要求一个数的平方根,是怎么实现的呢? 1:二分法 求根号5 a:折半: 5/2=2.5 每次得到当前值和5进行比较,并且记下下下限和上限,依次迭代,逐渐逼近平方根: import math from math import sqrt def sqrt_binary(num): x=sqrt(num) y=num/2.0 low=0.0 up=num*1.0 count=1 while abs(y-x)>0.00000001: print count,y count+=1 if (y*y>num): up=y y=low+(y-low)/2 else: low=y y=up-(up-y)/2 return y print(sqrt_binary(5)) print(sqrt(5)) 运行结果: 经过27次二分法迭代,得到的值和系统sqrt()差别在0.00000001,精度在亿分之一, 0.001需要迭代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代入: def sqrt_newton(num): x=sqrt(num) y=num/2.0 count=1 while abs(y-x)>0.00000001: print count,y count+=1 y=((y*1.0)+(1.0*num)/y)/2.0000 return y print(sqrt_newton(5)) print(sqrt(5)) 运行结果: 精确到亿分之一,牛顿法只迭代了3次,是二分法的十倍 3:利用牛顿法求开立方 def cube_newton(num): x=num/3.0 y=0 count=1 while abs(x-y)>0.00000001: print count,x count+=1 y=x x=(2.0/3.0)*x+(num*1.0)/(x*x*3.0) return x print(cube_newton(27)) 微积分、概率、线代是高级算法的基础课。可是,这么多年,已经忘得差不多了.............................. 总结 以上就是本文关于Python编程实现二分法和牛顿迭代法求平方根代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |