求根号m(巴比伦算法)

巴比伦算法是针对求根号m的*似值情况的,它的思想是这样的:

  设根号m=X0,则如果枚举有答案X(X<X0),则m/X>X0,当精度要求不高的时候,我们可以看成X=m/X=X0,而如果精度要求比较高,我们只需取X和m/X的*均值作为新的枚举答案X再进行操作,可以证明这样会一直逼*答案,至于做几次完全取决于精度要求。而实践证明这样求根号的速度极快

% 计算数字m的*方根的巴比伦算法: 

% (1)先猜一个答案guess(可以将m/2作为第一个答案);

% (2)计算r=m/guess; 

% (3)令guess=(guess+r)/2; 

% (4)如有必要返回第2步重复多次。步骤2和步骤3的重复次数越多, guess就越接*m的*方根。

—————————————————————————————————————————————————————————————————————————

然后本渣又想到能不能推广到n次方根,和HZH大神讨论无果后又问大神,大神给出了……一个解答……:

算法的正确性依赖于x=sqrt(N)为差分方程a(n+1)=(an+N/an)/2的吸引不动点吧,如果推广到高次根可能会使耗散力增加而导致周期倍分叉而不可做吧

(PS:本渣真是数学弱爆了完全读不懂,这里mark一下希望以后能看懂……(众:你这渣渣一辈子都不懂……))

额用人话解释一下:由于2次根号太特殊所以高次根号不能推广(BY YJT大神)

但不久后,vfk大神有说:

如果我没有脑残的话……


真相是,那家伙就是牛顿迭代


f(x) = x^2 - a
f'(x) = 2x
所以式子为
x' = x - (x^2 - a) / (2x) = (x + a / x) / 2


所以说,要想拓展到m次……
f(x) = x^m - a
f'(x) = m * x^(m - 1)
所以式子为
x' = x - (x^m - a) / (m * x^(m - 1)) = x * (1 - 1 / m) + a / (m * x^(m - 1))
只要初始估计充分接*根就可以获得很好的效果……看起来abs(f''(r) / (2 * f'(r)))不是很大的样子


大家好我是不会证其无论取何初始值一定收敛的sb

(PS:虽然本渣看不懂但是Vfk说的大概是取适当的初始貌似可以……)

原文地址:https://www.cnblogs.com/wmrv587/p/3531792.html