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

Curtion

@Ta 2020-08-12发布，2020-08-12修改 7858点击

数学知识

牛顿-拉夫逊迭代

梯度下降法

说明

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

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

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

化简：

也有人把这种方程叫做状态转移方程，其中待代开根的值,为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|隐藏机器人聊天)

1

mio

@Ta / 2020-08-12 / 样 / 源

完全看不懂了
2

胡椒舰长

@Ta / 2020-08-12 / 样 / 源

这是高等数学2吗？太恐怖了，我下学期刚刚要学这个了，
3

罐子

@Ta / 2020-08-12 / 样 / 源

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

水木易安

@Ta / 2020-08-12 / 样 / 源

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

大尨

@Ta / 2020-08-12 / 样 / 源
6

Curtion

@Ta / 2020-08-12 / 样 / 源

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

胡椒舰长

@Ta / 2020-08-13 / 样 / 源

@Curtion，，除了matlab ，如何用自己写的程序实现，求一个原函数的不定积分？
9

Curtion

@Ta / 2020-08-13 / 样 / 源

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

罐子

@Ta / 2020-08-13 / 样 / 源

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

love封尘

@Ta / 2020-08-13 / 样 / 源

@水木易安，二元一次方程?两块钱才一次?我看别人家都是一元一次方程的
12

水木易安

@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越大越趋近于实际值

14

echo醉老仙

@Ta / 2020-08-15 / 样 / 源

@老虎会游泳，万能虎果然名不虚传
15

老虎会游泳

@Ta / 2020-08-15 / 样 / 源

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

https://hu60.cn/q.php/bbs.topic.95320.html
16

嚻

@Ta / 2022-01-06 / 样 / 源

f(x_{2})=\frac{x^5}{a_{n}^{2}-a}-x^6

添加新回复

回复需要登录。