2007-11-24 19:45| 
17 Comments | 本文内容遵从 下面这种方法可以很有效地求出根号a的近似值：首先随便猜一个近似值x，然后不断令x等于x和a/x的平均数，迭代个六七次后x的值就已经相当精确了。
例如，我想求根号2等于多少。假如我猜测的结果为4，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号2了：
( 4 + 2/ 4 ) / 2 = 2.25
( 2.25 + 2/ 2.25 ) / 2 = 1.56944..
( 1.56944..+ 2/1.56944..) / 2 = 1.42189..
( 1.42189..+ 2/1.42189..) / 2 = 1.41423..
....
这种算法的原理很简单，我们仅仅是不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根，这个函数的导数是2x。也就是说，函数上任一点(x,f(x))处的切线斜率是2x。那么，x-f(x)/(2x)就是一个比x更接近的近似值。代入f(x)=x^2-a得到x-(x^2-a)/(2x)，也就是(x+a/x)/2。
同样的方法可以用在其它的近似值计算中。Quake III的源码中有一段非常牛B的开方取倒函数。
17 条回复
您也随便说几句吧：
sofa again~
NOIP前一天晚上，我还专门复习了牛迭。
我们仅仅是不断用(x,f(x))的切线来逼近方程y=x^2-a的根。
总觉得不太对，应该是 x^2-a=0的根吧，一个函数怎么还会有根？
回复：谢谢指正，已改正
可以推广到高次方么？[redface]
回复：可以
对所有多项式，只要适当选取起点，都是可以用的。对一般的形如x=f(x)的方程只要迭代是收缩的（这只需要f的导数在适当的区间内绝对值不大于于某个小于1的正数），都是适用的。
回复：谢谢补充
例如这篇文章取的就是f(x)=(x+a/x)/2
上面漏了点东西……导数值应当保持正号，否则迭代会跳跃。
牛顿切线法求 f(x) = 0
似乎只需要满足一区间 [a,b]
f(x) 在 [a,b] 连续，f(a)*f(b)，f'(x) 定号单调 就可以了。
好人啊
请教如何画出这函数图像?
x-f(x)/(2x)就是一个比x更接近的近似值。代入f(x)=x^2-a得到x-(x^2-a)/(2x)，也就是(x+a/x)/2
能否说明一下,说出推导过程我只是初学者
Q3源码里卡马克写的那个是极其巧妙的利用了电脑对浮点数的位操作，只用了一个常数就实现了极高的效率，太牛了。
回10楼
x-f(x)/(2x)就是一个比x更接近的近似值:
4那个点是Xn 左边那个点是Xn-1
求出f(x)在Xn处的一阶导:
f'(Xn) = f(Xn)/(Xn-Xn-1)
挪动挪动:
Xn-1 = Xn - f(Xn)/f'(Xn)
等式右边就是LZ的x-f(x)/(2x)
图像上可以看出Xn-1比Xn更接近我们f(x)的根
之所以可以用迭代法是因为中值定理, 用泰勒公式也可以推出这样的式子
从卡马克那个帖子Google到LZ的Blog的, 很喜欢LZ的东西, 不过... 为什么不开TeX公式的图像生成哇 >___< 看着好辛苦
我曾经在emath的论坛上发过一个手工开平方的算法，如图
http://ii.a.5d6d.com/userdirs/7/4/emath/attachments/month_0808/20080808_1f61184c54d5a3b10ee36znUnkvPbq0o.jpg
太帅了
fuck nimo
[...] 本文出自matrix67.com [...]
+1