牛顿迭代法求平方根（Java实现）

不念不忘少年蓝@ 2021-11-11 12:26 463阅读 0赞

我们如果要求 c 的平方根，那么首先想到利用方程求解，即![f(x)=x^\{2\}-c][f_x_x_2_-c] ，![f(x)][f_x]与 ![x][] 轴正方向的交点即为我们要求的值，即![\\sqrt\{c\}][sqrt_c]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l6eV9jc2Ru_size_16_color_FFFFFF_t_70][]

接着问题来了，牛顿迭代法是怎么求![\\sqrt\{c\}][sqrt_c] 的？

我们可以先取一个![\\sqrt\{c\}][sqrt_c] 的近似值，假设初始值![\{\\color\{Blue\}x=c\}][color_Blue_x_c] ，然后求函数在![(x,f(x))][x_f_x]处的切线![AT][]与 ![x][] 轴的交点，设为 ![t][] 点,

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l6eV9jc2Ru_size_16_color_FFFFFF_t_70 1][]

那么![AC=f(x)][AC_f_x]，由于函数导数为![2x][]，即![AT][]斜率为![2x][]，那么![TC=f(x)/2x][TC_f_x_2x]

即可得出![OT=OC-TC][OT_OC-TC]，即为![\{\\color\{Blue\} x-f(x)/2x\}][color_Blue_ x-f_x_2x] ，为了消除掉![f(x)][f_x]，把![\{\\color\{Blue\}f(x)=x^\{2\}-c\}][color_Blue_f_x_x_2_-c] 带入 ![\{\\color\{Blue\} x-f(x)/2x\}][color_Blue_ x-f_x_2x] ，得出![OT][]等于![x-(x^\{2\}-c)/2][x-_x_2_-c_2]，最终等于![\{\\color\{Red\} (c/x+x)/2\}][color_Red_ _c_x_x_2]

当然，这个值比 ![x][] 更接近 ![\\sqrt\{c\}][sqrt_c]

接下来就是迭代，一步步的逼近![\\sqrt\{c\}][sqrt_c] 直到满足误差范围，如图所示，应该都能看明白：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l6eV9jc2Ru_size_16_color_FFFFFF_t_70 2][]

接下来上代码：

public static double sqrt(double c) {
    	if (c < 0) return Double.NaN;
    	double err = 1e-15; //设置误差不超过1*10^-15
    	double t = c; //设置初始等于c
    	while (Math.abs(t-c/t) > err*t) //1-c/t^2的绝对值小于err时停止
    		t = (c/t+t)/2;
    	return t;
    }

OK,完成！

参考文献及资料：

算法（第4版）Algorithms 4th edition

[http://www.matrix67.com/blog/archives/361][http_www.matrix67.com_blog_archives_361]

[f_x_x_2_-c]: https://private.codecogs.com/gif.latex?f%28x%29%3Dx%5E%7B2%7D-c
[f_x]: https://private.codecogs.com/gif.latex?f%28x%29
[x]: https://private.codecogs.com/gif.latex?x
[sqrt_c]: https://private.codecogs.com/gif.latex?%5Csqrt%7Bc%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l6eV9jc2Ru_size_16_color_FFFFFF_t_70]: /images/20211109/d1fb0e45b9124f39a13513e942f2c31e.png
[color_Blue_x_c]: https://private.codecogs.com/gif.latex?%7B%5Ccolor%7BBlue%7Dx%3Dc%7D
[x_f_x]: https://private.codecogs.com/gif.latex?%28x%2Cf%28x%29%29
[AT]: https://private.codecogs.com/gif.latex?AT
[t]: https://private.codecogs.com/gif.latex?t
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l6eV9jc2Ru_size_16_color_FFFFFF_t_70 1]: /images/20211109/ec2827921f5d4b3396ab1c38c94dbc25.png
[AC_f_x]: https://private.codecogs.com/gif.latex?AC%3Df%28x%29
[2x]: https://private.codecogs.com/gif.latex?2x
[TC_f_x_2x]: https://private.codecogs.com/gif.latex?TC%3Df%28x%29/2x
[OT_OC-TC]: https://private.codecogs.com/gif.latex?OT%3DOC-TC
[color_Blue_ x-f_x_2x]: https://private.codecogs.com/gif.latex?%7B%5Ccolor%7BBlue%7D%20x-f%28x%29/2x%7D
[color_Blue_f_x_x_2_-c]: https://private.codecogs.com/gif.latex?%7B%5Ccolor%7BBlue%7Df%28x%29%3Dx%5E%7B2%7D-c%7D
[OT]: https://private.codecogs.com/gif.latex?OT
[x-_x_2_-c_2]: https://private.codecogs.com/gif.latex?x-%28x%5E%7B2%7D-c%29/2
[color_Red_ _c_x_x_2]: https://private.codecogs.com/gif.latex?%7B%5Ccolor%7BRed%7D%20%28c/x&plus;x%29/2%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l6eV9jc2Ru_size_16_color_FFFFFF_t_70 2]: /images/20211109/db9a89393798499da00c2b8c9e17ac0d.png
[http_www.matrix67.com_blog_archives_361]: http://www.matrix67.com/blog/archives/361