求一个数的开平方

我们假设这个数是 ，如何先快速求出 的值？

我们可以把这个题目转化成一个几何问题。如下图：

image.png

可以转换为，求公式 Y=X2−aY = X^2 - a，（a,0）（\sqrt a,0）的值。

  • 我们现在抛物线上任意取一点 （x0，x02−a）（x_0，x_0^2 - a）, 然后基于这一点画一个切线，切线的方程记为 。
  • 切线的斜率 ，我们可以对抛物线求导，得到
  • 带入到切线的方程可以得
  • 因为切线经过点（x0，x02−a）（x_0，x_0^2 - a），带入切线方程，就有 x02−a=2∗x02+bx_0^2 - a = 2 * x_0^2 + b
  • 转而得到 b=−x02−ab = -x_0^2 - a
  • 然后带入到之前的切线的方程 可得 ，把。
  • 假设 与 轴交点为 （x1,0）（x_1, 0）
  • 把 （x1,0）（x_1, 0）带入上面的切线方程得到
  • 重复上面的步骤，在抛物线上取一点（x1，x12−a）（x_1，x_1^2 - a）, 最终可以得到
  • 随着这样不停的递归迭代。 值会慢慢趋向于（a,0）（\sqrt a,0）

image.png

为什么会逼近 （a,0）（\sqrt a,0） ？

  • 是切线，它与抛物线只有一个点。如果切线与 轴和抛物线一定有交点，这一点一定是（a,0）（\sqrt a,0）
  • 再来看递归公式

如果 xn>ax_n > \sqrt{a}

  • 则 (算术平均大于较小的数，小于较大的数。)
  • 假设
  • 乘以 2 得到：xn+axn>2a.x_n + \frac{a}{x_n} > 2\sqrt{a}.
  • 由于 xn>0x_n>0，我们可以两边乘以 xnx_n（不改变不等式方向）：xn2+a>2a xn.x_n^2 + a > 2\sqrt{a}\, x_n.
  • 将右边移到左边：xn2−2a xn+a>0.x_n^2 - 2\sqrt{a}\, x_n + a > 0.
  • 注意到左侧正好可以写成一个完全平方：(xn−a)2>0.(x_n - \sqrt{a})^2 > 0.
  • 所以假设成立
  • 简写为 a<xn+1<xn\sqrt{a} < x_{n+1} < x_n，可以知道 xn+1x_{n+1} 是在 (a,xn)(\sqrt{a},x_n) 之间逐渐减小逼近 a\sqrt{a}

如果 0<xn<a0 < x_n < \sqrt{a}

  • 则
  • 假设
  • 得到 (xn−a)2>0.(x_n - \sqrt{a})^2 > 0. 这个依然成立，
  • 所以
  • 接下来考虑 xn+1x_{n+1} 已经位于 a\sqrt{a} 的右侧，此时根据之前的证明（当 x>ax > \sqrt{a} 时），迭代公式会使得后续的 xx 值下降，但仍保持在 a\sqrt{a} 上方。也就是说，若从下侧开始，迭代会先“越过” a\sqrt{a}，再从上侧下降。这样就形成了一个交替迭代的过程：
    • 当某个迭代值在 a\sqrt{a} 左侧时，下一个值会在右侧；
    • 当某个迭代值在 a\sqrt{a} 右侧时，下一个值会下降但仍大于 a\sqrt{a}。

总的来说，如果 xn<a⟹xn<xn+1x_n < \sqrt{a} \Longrightarrow x_{n} < x_{n+1} , 说明再向右偏移，xnx_{n} 逐渐变大。如果大于 a\sqrt{a} 以后，又会变成上面的假设 a<xn+1<xn\sqrt{a} < x_{n+1} < x_n 。所以说 xnx_{n} 会逐渐收敛到 a\sqrt{a}

最终用代码实现的牛顿开方法如下：

const det = 1e-5 // 误差多少

func sqrt(a float64) float64 {
	x_0 := a
	for {
		x_1 := (x_0*x_0 + a) / (2 * x_0)
		if math.Abs(x_1-x_0) < det {
			return x_1
		}
		x_0 = x_1
	}
}