欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛顿迭代法求sqrt(y)详解

程序员文章站 2022-06-03 12:26:04
...

给出一个数,然后求出这个数的平方根 --> 就是方程 y=x2 ,给y的值,求x。
有两种方法:

  1. 二分法,设下界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

  1. 牛顿迭代法
    理论基础:一条曲线的导函数就是这个曲线上所有点的切线的斜率公式,具体求一个点的切线斜率等于多少要看这个点的横坐标,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)