牛顿迭代法求平方根(Java实现) 不念不忘少年蓝@ 2021-11-11 12:26 471阅读 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+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
还没有评论,来说两句吧...