下面这种方法可以很有效地求出根号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的开方取倒函数。
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
+1
不错不错 学习了
回复10楼,设x0=sqrt(a),则f(x0)=0;
f'(x0)=(f(x)-f(x0))/(x-x0)
=2x,
进一步化简得x-x0=f(x)/(2x),
所以x0=x-f(x)/(2x)
…写错了，f'(x)=(f(x)-f(x0))/(x-x0)=2x
这种迭代的终止条件是什么呢？如果是迭代的次数显然不合适（这样就违背了迭代的本质）
计算上一次和这次值得差，小于一个阈值。
牛顿迭代法本来不就是用来求根的么？
回23楼,我的理解是终止条件可设置为你需要的精确度
可直接设为Xn==Xn+1,浮点数的精度有限,到达最大精度就会停止,输入9,返回3.0
也可以自设定精确值,比如abs((Xn+1)^2-a)<0.01,输入9,就会返回一个很接近3的小数
不错不错 学习了
复习一下。。。
求问楼主，画图的软件是什么，谢谢！
几何画板啊
SICP 上看到的
“Quake III的源码”这个页面404
如果我们有着快乐的思想，我们就会快乐；如果我们有着凄惨的思想，我们就会凄惨。
问下各位，迭代法求不出完全正确的解，只能做到近似，普通计算器用的什么算法对某些可以完全开平方的求出正确解。如求900的开平方得出30，如果用迭代法貌似很难得出。
很棒，谢谢！