1

我阅读了计算任意数平方根的方法，算法如下：

double findSquareRoot(int n) {
    double x = n;
    double y = 1;
    double e = 0.00001;
    while(x-y >= e) {
        x = (x+y)/2;
        y = n/x;
    }
    return x;
}

我关于这种方法的问题是

  1. 它如何计算平方根？我不明白这背后的数学原理。如何x=(x+y)/2 and y=n/x收敛到 n 的平方根。解释这个数学。

  2. 这个算法的复杂度是多少？

4

4 回答 4

3

这是牛顿法计算平方根的典型应用n。您正在计算序列的限制：

x_0 = n
x_{i+1} = (x_i + n / x_i) / 2

您的变量x是当前术语x_i，您的变量y是n / x_i.

要了解为什么必须计算此限制，您需要考虑以下函数：

f(x) = x^2 - n

你想找到这个函数的根。它的导数是

f'(x) = 2 * x

和牛顿的方法给你公式：

x_{i+1} = x_i - f(x_i) / f'(x_1) = ... = (x_i + n / x_i) / 2

为了完整起见，我在这里复制了@rodrigo 回答的基本原理，并结合了我对它的评论。如果您想忘记牛顿法并尝试单独理解此算法，这将很有帮助。

诀窍是，如果x不是 的平方根n，那么它是一个近似值，位于实根之上或之下，并且y = n/x总是在另一边。因此，如果您计算 的中点(x+y)/2，它将比这两个近似值（x或y）中最差的一个更接近实根。当x和y足够接近时，你就完成了。

这也将帮助您找到算法的复杂性。假设这d是两个近似值中最差的一个到真实根的距离r。然后中点之间的距离(x+y)/2最多r为d/2（如果你画一条线来可视化它会帮助你）。这意味着，每次迭代，距离减半。因此，最坏情况的复杂度与初始近似的距离和所寻求的精度成对数。对于给定的程序，它是

log(|n-sqrt(n)|/epsilon)
于 2013-09-26T11:24:35.450 回答
3

很容易看出您是否进行了一些运行并打印 x 和 y 的连续值。例如 100：

50.5 1.9801980198019802
26.24009900990099 3.8109612300726345
15.025530119986813 6.655339226067038
10.840434673026925 9.224722348894286
10.032578510960604 9.96752728032478
10.000052895642693 9.999947104637101
10.000000000139897 9.999999999860103

看，诀窍在于，如果x不是的平方根n，那么它在实根之上或之下，并且n/x总是在另一边。所以如果你计算 的中点，x它n/x会更接近真正的根。

而关于复杂性，它实际上是无界的，因为真正的根永远不会到达。这就是为什么你有e参数。

于 2013-09-26T11:23:48.327 回答
1

数学上的解释是，在小范围内，算术平均值是几何平均值的合理近似值，几何平均值用于计算平方根。随着迭代越来越接近真正的平方根，算术平均值和几何平均值之间的差异消失了，近似值变得非常接近。这是我最喜欢的 Heron 算法版本，它首先在 1 ≤ n < 4 的范围内对输入n进行归一化，然后展开循环以保证收敛的固定迭代次数。

def root(n):
    if n < 1: return root(n*4) / 2
    if 4 <= n: return root(n/4) * 2
    x = (n+1) / 2
    x = (x + n/x) / 2
    x = (x + n/x) / 2
    x = (x + n/x) / 2
    x = (x + n/x) / 2
    x = (x + n/x) / 2
    return x

我在博客中讨论了几个计算平方根的程序。

于 2013-09-26T12:52:22.353 回答
1

我认为所有信息都可以在维基百科中找到。

基本思想是，如果 x 高估了非负实数 S 的平方根，那么 S/x 将被低估，因此可以合理地预期这两个数字的平均值可以提供更好的近似值。

每次迭代时，该算法都会将答案中的正确数字加倍，因此复杂度与所需精度的对数成线性关系。

为什么它有效？如此处所述，如果您将进行无限迭代，您将获得一些值，我们将其命名为 L。L 必须满足方程 L = (L + N/L)/2（如算法中），因此 L = sqrt(N ）。如果您担心收敛，您可以计算每次迭代的平方相对误差（Ek 是误差，Ak 是计算值）：

Ek = (Ak/sqrt(N) - 1)²
如果：
Ak = (Ak-1 + N/Ak-1)/2 和 Ak = sqrt(N)(sqrt(Ek) + 1)
你可以推导出递归关系对于 Ek：
Ek = Ek-1²/[4(sqrt(Ek-1) + 1)²]
并且它的极限是 0，所以 A1,A2... 序列的极限是 sqrt(N)。

于 2013-09-26T11:21:47.470 回答