leetcode 69 x的平方根(牛顿迭代)

@Ta 2020-08-12发布,2020-08-12修改 1993点击

数学知识

牛顿-拉夫逊迭代

梯度下降法

说明

69题是一道Easy题,实际上的难点在数学上面,有很多方法可以求平方根,此处是计算机用的比较多的方法。

求a的平方根可以等效成求img的根,有了上述数学知识后:

  • 任意选取一个数img,该点坐标是img)
  • 该点与二次函数img上的切线方程为img
  • 切线与x轴相交的点为:img)
  • 过该点与x轴的垂线与二次函数相交与imgimg的坐标为img),其中img
  • ......
  • 所以img

化简:img

也有人把这种方程叫做状态转移方程,其中img待代开根的值,img为n+1次迭代后的平方根,n越大越趋近于实际值

实现

var mySqrt = function (x) {
  let an = 1 // 任意数a0
  let a = x // 被开方数a
  for (let i = 0; Math.abs(an * an - a) > 0.1/* 收敛条件 */; i++) {
    an = (an + a / an) / 2
  }
  return Math.floor(an)
};

红米K30 Pro 变焦版

回复列表(15)
  • mio
    @Ta / 2020-08-12
    完全看不懂了
  • @Ta / 2020-08-12
    这是高等数学2吗?太恐怖了,我下学期 刚刚要学这个了,
  • @Ta / 2020-08-12

    我已经晕了。
    健健康康
    一加8Pro 青

  • @Ta / 2020-08-12

    请教一下 二元一次方程一般使用程序如何求解
    红米Note4超高配版(银色)

  • @Ta / 2020-08-12
  • @Ta / 2020-08-12

    @水木易安,写成矩阵的方式,用线性代数来做,如果仅限于二元一次,直接换元应该就行? 我数学一般般,现在已经毕业了就更少用到了
    红米K30 Pro 变焦版

  • @Ta / 2020-08-13
    @Curtion,,除了matlab ,如何用自己写的程序实现,求一个 原函数的不定积分?
  • o
    @Ta / 2020-08-13
    不明觉叼
  • @Ta / 2020-08-13

    @胡椒舰长,我只是发了一道easy的题,你们高看我了
    红米K30 Pro 变焦版

  • @Ta / 2020-08-13

    我也看不懂
    健健康康
    一加8Pro 青

  • @Ta / 2020-08-13
    @水木易安,二元一次方程?两块钱才一次?我看别人家都是一元一次方程的
  • @Ta / 2020-08-13

    @love封尘,小哥哥快来玩啊
    红米Note4超高配版(银色)

  • @Ta / 2020-08-15
    求a的平方根可以等效成求 [math]f(x) = x^2 - a[/math] 的根,有了上述数学知识后:
    
    - 任意选取一个数 [math]a_{0}[/math],该点坐标是 [math](a_{0},f(a_{0}))[/math]
    - 该点与二次函数 《公式:f(x) = x^2 - a》 上的切线方程为 《公式:f(x) - f(a_{0}) = f'(a_{0})(x - a_{0})》
    - 切线与x轴相交的点为: 《公式:(a_{0} - \frac{f(a_{0})}{f'(a_{0})}, 0)》
    - 过该点与x轴的垂线与二次函数相交与 《公式:a_{1}》, 《公式:a_{1}》 的坐标为 《公式:(a_{1},f(a_{1}))》,其中 《公式:a_{1} = a_{0} - \frac{f(a_{0})}{f'(a_{0})}》
    - ......
    - 所以 《公式:a_{n+1} = a_{n} - \frac{f(a_{n})}{f'(a_{n})}》
    
    化简: [math]a_{n+1} = a_{n} - \frac{a_{n}^{2}-a}{2a_{n}} = \frac{a_{n}+\frac{a}{a_{n}} }{2}[/math]
    
    也有人把这种方程叫做状态转移方程,其中 a 待代开根的值, 《公式:a_{n+1}》 为n+1次迭代后的平方根,n越大越趋近于实际值
    

    求a的平方根可以等效成求 f(x) = x^2 - a 的根,有了上述数学知识后:

    • 任意选取一个数 a_{0},该点坐标是 (a_{0},f(a_{0}))
    • 该点与二次函数 f(x) = x^2 - a 上的切线方程为 f(x) - f(a_{0}) = f'(a_{0})(x - a_{0})
    • 切线与x轴相交的点为: (a_{0} - \frac{f(a_{0})}{f'(a_{0})}, 0)
    • 过该点与x轴的垂线与二次函数相交与 a_{1}a_{1} 的坐标为 (a_{1},f(a_{1})),其中 a_{1} = a_{0} - \frac{f(a_{0})}{f'(a_{0})}
    • ......
    • 所以 a_{n+1} = a_{n} - \frac{f(a_{n})}{f'(a_{n})}

    化简: a_{n+1} = a_{n} - \frac{a_{n}^{2}-a}{2a_{n}} = \frac{a_{n}+\frac{a}{a_{n}} }{2}

    也有人把这种方程叫做状态转移方程,其中 a 待代开根的值, a_{n+1} 为n+1次迭代后的平方根,n越大越趋近于实际值

  • @Ta / 2020-08-15
    @老虎会游泳,万能虎果然名不虚传
  • @Ta / 2020-08-15

    @echo醉老仙,我只是在做[math]UBB,内容是复制了楼主的。

    http://isoyu.com/q.php/bbs.topic.95320.html

添加新回复
回复需要登录

[聊天-此处没基佬] 方爷:Hello,鸡🐔佬林!小尾巴华为Mate40 Pro鸡佬版