牛顿迭代法求sqrt(y)详解
程序员文章站
2022-06-03 12:26:04
...
给出一个数,然后求出这个数的平方根 --> 就是方程 y=x2 ,给y的值,求x。
有两种方法:
- 二分法,设下界l = 0,上界r=y,取中间值mid,
mid = (l+r)/2
if mid*mid == y:
return mid # 找到了
if mid*mid > y: # 说明取值偏大
r = mid # 把上界改成mid
if mid*mid < y: # 说明取值偏小
l = mid # 把下界改成mid
- 牛顿迭代法
理论基础:一条曲线的导函数就是这个曲线上所有点的切线的斜率公式,具体求一个点的切线斜率等于多少要看这个点的横坐标,k = f '(x0)
通过点斜式:
y - y0 = k (x - x0) , k 用k = f '(x0)代入
得出 某一点(x0, y0)在曲线上的切线L公式:
y = f '(x0) (x-x0) + y0 , y0= f(x0)
切线L与X轴的交点(x1, 0)公式:
x1 = x0 - f(x0)/f '(x0)
得出:
xn+1 = xn - f(xn)/f '(xn) 这就是逼近一个数的根的推导式
y = x2
f(x) = x2 - y
f '(x) = 2x
xn+1 = xn - (xn2 - y0)/f '(xn)
上一篇: 微信小程序开发之全局文件