Python編程實現(xiàn)二分法和牛頓迭代法求平方根代碼
求一個數(shù)的平方根函數(shù)sqrt(int num) ,在大多數(shù)語言中都提供實現(xiàn)。那么要求一個數(shù)的平方根,是怎么實現(xiàn)的呢?
實際上求平方根的算法方法主要有兩種:二分法(binary search)和牛頓迭代法(Newton iteration)
1:二分法
求根號5
a:折半: 5/2=2.5
b:平方校驗: 2.5*2.5=6.25>5,并且得到當前上限2.5
c:再次向下折半:2.5/2=1.25
d:平方校驗:1.25*1.25=1.5625<5,得到當前下限1.25
e:再次折半:2.5-(2.5-1.25)/2=1.875
f:平方校驗:1.875*1.875=3.515625<5,得到當前下限1.875
每次得到當前值和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))
運行結(jié)果:
1 2.5
2 1.25
3 1.875
4 2.1875
5 2.34375
6 2.265625
7 2.2265625
8 2.24609375
9 2.236328125
10 2.2314453125
11 2.23388671875
12 2.23510742188
13 2.23571777344
14 2.23602294922
15 2.23617553711
16 2.23609924316
17 2.23606109619
18 2.23608016968
19 2.23607063293
20 2.23606586456
21 2.23606824875
22 2.23606705666
23 2.2360676527
24 2.23606795073
25 2.23606809974
26 2.23606802523
27 2.23606798798
2.23606796935
2.2360679775
[Finished in 0.1s]
經(jīng)過27次二分法迭代,得到的值和系統(tǒng)sqrt()差別在0.00000001,精度在億分之一,
0.001需要迭代8次
因此,在對精度要求不高的情況下,二分法也算比較高效的算法。
2:牛頓迭代
仔細思考一下就能發(fā)現(xiàn),我們需要解決的問題可以簡單化理解。
從函數(shù)意義上理解:我們是要求函數(shù)f(x)=x²,使f(x)=num的近似解,即x²-num=0的近似解。
從幾何意義上理解:我們是要求拋物線g(x)=x²-num與x軸交點(g(x)=0)最接近的點。
我們假設g(x0)=0,即x0是正解,那么我們要做的就是讓近似解x不斷逼近x0,這是函數(shù)導數(shù)的定義:

可以由此得到

從幾何圖形上看,因為導數(shù)是切線,通過不斷迭代,導數(shù)與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))
運行結(jié)果:
1 2.5
2 2.25
3 2.23611111111
2.23606797792
2.2360679775
精確到億分之一,牛頓法只迭代了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))
微積分、概率、線代是高級算法的基礎課??墒?,這么多年,已經(jīng)忘得差不多了..............................
總結(jié)
以上就是本文關于Python編程實現(xiàn)二分法和牛頓迭代法求平方根代碼的全部內(nèi)容,希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關專題,如有不足之處,歡迎留言指出。
相關文章
django queryset 去重 .distinct()說明
這篇文章主要介紹了django queryset 去重 .distinct()說明,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-05-05
Python將Excel轉(zhuǎn)換為多種圖片格式的方法(PNG, JPG, BMP, SVG)
有時,你可能希望以圖片形式分享Excel數(shù)據(jù),以防止他人對數(shù)據(jù)進行修改或編輯,將Excel轉(zhuǎn)換為圖片可以將數(shù)據(jù)鎖定為靜態(tài)圖片,確保數(shù)據(jù)的完整性和準確性,這篇文章將探討如何使用Python實現(xiàn)將Excel工作表轉(zhuǎn)換為多種圖片格式,如PNG,JPG,BMP和SVG,需要的朋友可以參考下2025-03-03
python面向?qū)ο髮崿F(xiàn)名片管理系統(tǒng)文件版
這篇文章主要為大家詳細介紹了python面向?qū)ο髮崿F(xiàn)名片管理系統(tǒng)文件版,具有一定的參考價值,感興趣的小伙伴們可以參考一下2019-04-04
django框架自定義模板標簽(template tag)操作示例
這篇文章主要介紹了django框架自定義模板標簽(template tag)操作,結(jié)合實例形式分析了Django框架自定義模板標簽原理、操作步驟與相關實現(xiàn)技巧,需要的朋友可以參考下2019-06-06
Python利用matplotlib實現(xiàn)動態(tài)可視化詳解
Python中的數(shù)據(jù)可視化是指原始數(shù)據(jù)的圖形表示,以更好地可視化、理解和推理,Python提供了各種庫,包含用于可視化數(shù)據(jù)的不同特性,下面我們就來看看如何利用matplotlib實現(xiàn)動態(tài)可視化吧2023-08-08

