MyException - 我的异常网
当前位置:我的异常网» 综合 » 数学札记9——牛顿迭代法

数学札记9——牛顿迭代法

www.MyException.Cn  网友分享于:2013-10-08  浏览:0次
数学笔记9——牛顿迭代法

  牛顿迭代法(Newton's method)又称为牛顿-拉夫逊(拉弗森)方法(Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

示例1:求解平方根

  先来看如何用牛顿迭代法求解5的平方根。在计算器上的结果是2.236067…

  问题可以看作解方程x2=5,下面尝试用牛顿迭代法求解。

  首先令f(x)= x2 – 5 = 0,这是标准步骤,取得一个新函数,令该函数为0。这是一个抛物线:

  抛物线与x轴的交点x就是方程的解,它比2稍大一点。

  现在在x=2处对f(x)做切线:

f(x)的切线

切线与x轴的交点

  x0=2,y0= x02 – 5 = -1,设k是切线斜率:

  在x1处做f(x)的切线,重复上面步骤,

  这就是牛顿迭代法的公式。通过作图可以看出,每一次迭代,x都将更靠近最终解。

 

  f’(x)=2x,将公式代入目标方程f(x)=x2-5:

  已经相当接近计算器的结果。

示例2:2cosx=3x

  解方程2cosx=3x

  由图像可知,方程存在唯一解。

  f(x)=2cosx-3x=0,f’(x)=-2sinx-3,x0=π/6≈0.52

注意事项

  牛顿迭代法几乎可以求解所有方程,但它仍然有一些限制。

  通过前两个例子可以看到,在使用牛顿迭代法时,需要选取一个较为解接近真实解的x0作为迭代基数,x0如何选取呢?一句参考是:“f’不能太小,f’’不能太大,x0要在x附近”,这似乎要凭经验和感觉了,没有什么太好的办法;实际上,如果x0和x的差距过大,可能会得到一个没谱的解。

  设第n次迭代的误差是En=|x-xn|,那么需要满足En+1<En。如果选择和计算都正确,误差缩小的速度将非常快。

  以计算5的平方根为例,如果选择x0=-2,结果将偏向于-2.236067…;如果选择x0=0,则f’(0)=0,没法继续迭代,函数曲线如下图所示:

选择了错误的x0

代码示例:牛顿迭代法开平方

  设x2=a,则f(x)= x2-a,根据牛顿迭代法公式:

 1 const float EPS = 0.00001; 
 2 double sqrt(double x) { 
 3     if(x == 0) 
 4         return 0; 
 5     double result = x; 
 6     double lastValue; 
 7     do{ 
 8         lastValue = result; 
 9         result = result / 2.0f + x / 2.0f / result; 
10     }while(abs(result - lastValue) > EPS);
11     return (double)result;
12

   上面方法开平方会很快,但 https://www.2cto.com/kf/201206/137256.html 中提到了一个更快的方法。

  1999年12月,美国id Software公司发布了名为“雷神之锤III”的电子游戏。它是第一个支持软件加速的游戏,取得了极大成功。(由于影响力过大,文化部于2004年将它列入了非法游戏名单)雷神之锤III并不是id Software公司的第一次成功。早在1993年开始,这家公司就以“毁灭战士”系列游戏名闻天下。1995年,“毁灭战士”的安装数超过了当年微软的windows 95。据传比尔盖茨才曾经考虑买下id software。(id software公司后来被推出过“上古卷轴”系列的Bethesda公司买下)

  id Software所取得的成功很大程度上要归功于它的创始人约翰·卡马克。马克尔也是一个著名的程序员,他是id Software游戏引擎的主要负责人。 回到刚才提到的雷神之锤,马克尔是开源软件的积极推动者,他于2005年公布了雷神之锤III的源代码。至此人们得以通过研究这款游戏引擎的源文件来查看它成功的秘密。

  在其中一个名字为q_math.c的文件中发现了如下代码段:

 1 float Q_rsqrt( float number ) { 
 2     long i; float x2, y; const float threehalfs = 1.5F;
 3     x2 = number * 0.5F; 
 4     y = number; 
 5     i = * ( long * ) &y; // evil floating point bit level hacking 
 6     i = 0x5f3759df - ( i >> 1 ); // what the fuck? 
 7     y = * ( float * ) &i; 
 8     y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration 
 9     // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
10     #ifndef Q3_VM #
11     ifdef __linux__ assert( !isnan(y) ); // bk010122 - FPE?
12     #endif
13     #endif return y; 
14 }

  这段代码的作用就是求number的平方根,并且返回它的倒数。

  经过测试,它的效率比上述牛顿法程序要快几十倍。也比c++标准库的sqrt()函数要快好几倍。此段代码有一个奇怪的句子:

  i = 0x5f3759df - ( i >> 1 ); // what the fuck? 

  没错,一般的求平方根都是这么循环迭代算的但是卡马克(quake3作者)真正牛B的地方是他选择了一个神秘的常数0x5f3759df 来计算那个猜测值,就是我们加注释的那一行,那一行算出的值非常接近1/sqrt(n),这样我们只需要2次牛顿迭代就可以达到我们所需要的精度。好吧如果这个还不算NB,接着看:

  普渡大学的数学家Chris Lomont看了以后觉得有趣,决定要研究一下卡马克弄出来的这个猜测值有什么奥秘。Lomont也是个牛人,在精心研究之后从理论上也推导出一个最佳猜测值,和卡马克的数字非常接近, 0x5f37642f。卡马克真牛,他是外星人吗?

  传奇并没有在这里结束。Lomont计算出结果以后非常满意,于是拿自己计算出的起始值和卡马克的神秘数字做比赛,看看谁的数字能够更快更精确的求得平方根。结果是卡马克赢了... 谁也不知道卡马克是怎么找到这个数字的。

  最后Lomont怒了,采用暴力方法一个数字一个数字试过来,终于找到一个比卡马克数字要好上那么一丁点的数字,虽然实际上这两个数字所产生的结果非常近似,这个暴力得出的数字是0x5f375a86。

  Lomont为此写下一篇论文,"Fast Inverse Square Root"。

  论文下载地址:
  http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf
  http://www.matrix67.com/data/InvSqrt.pdf

向牛顿致敬

  牛顿是近代科学的先驱,智商290,在多个领域都有非凡的成就。

  他在1687年发表的论文《自然定律》里,对万有引力和三大运动定律进行了描述。这些描述奠定了此后三个世纪里物理世界的科学观点,并成为了现代工程学的基础。他通过论证开普勒行星运动定律与他的引力理论间的一致性,展示了地面物体与天体的运动都遵循着相同的自然定律;为太阳中心说提供了强有力的理论支持,并推动了科学革命。

  在力学上,牛顿阐明了动量和角动量守恒的原理,提出牛顿运动定律[1]  。在光学上,他发明了反射望远镜,并基于对三棱镜将白光发散成可见光谱的观察,发展出了颜色理论。他还系统地表述了冷却定律,并研究了音速。

  在数学上,牛顿与戈特弗里德·威廉·莱布尼茨分享了发展出微积分学的荣誉。他也证明了广义二项式定理,提出了“牛顿法”以趋近函数的零点,并为幂级数的研究做出了贡献。

  在经济学上,牛顿提出金本位制度。

  在天文成上,牛顿1672年创制了反射望远镜。他还用万有引力原理说明潮汐的各种现象,指出潮汐的大小不但同月球的位相有关,而且同太阳的方位有关。牛顿预言地球不是正球体。

  在哲学成上,牛顿的哲学思想基本属于自发的唯物主义,他承认时间、空间的客观存在。如同历史上一切伟大人物一样,牛顿虽然对人类作出了巨大的贡献,但他也不能不受时代的限制。例如,他把时间、空间看作是同运动着的物质相脱离的东西,提出了所谓绝对时间和绝对空间的概念;他对那些暂时无法解释的自然现象归结为上帝的安排,提出一切行星都是在某种外来的“第一推动力”作用下才开始运动的说法。《自然哲学的数学原理》牛顿最重要的著作,1687年出版。

  向伟大的牛顿致敬!

总结

  1. 牛顿迭代法的公式:
  2. 注意事项,f’不能太小,f’’不能太大,x0要在x附近

    作者:我是8位的

  出处:http://www.cnblogs.com/bigmonkey

  本文以学习、研究和分享为主,如需转载,请联系本人,标明作者和出处,非商业用途! 

 

文章评论

程序员和编码员之间的区别
程序员和编码员之间的区别
我是如何打败拖延症的
我是如何打败拖延症的
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
Java程序员必看电影
Java程序员必看电影
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
漫画:程序员的工作
漫画:程序员的工作
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
为什么程序员都是夜猫子
为什么程序员都是夜猫子
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
鲜为人知的编程真相
鲜为人知的编程真相
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
10个调试和排错的小建议
10个调试和排错的小建议
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
 程序员的样子
程序员的样子
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员必看的十大电影
程序员必看的十大电影
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
中美印日四国程序员比较
中美印日四国程序员比较
如何成为一名黑客
如何成为一名黑客
旅行,写作,编程
旅行,写作,编程
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员应该关注的一些事儿
程序员应该关注的一些事儿
那些争议最大的编程观点
那些争议最大的编程观点
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
代码女神横空出世
代码女神横空出世
程序员都该阅读的书
程序员都该阅读的书
每天工作4小时的程序员
每天工作4小时的程序员
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员的鄙视链
程序员的鄙视链
一个程序员的时间管理
一个程序员的时间管理
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
编程语言是女人
编程语言是女人
老程序员的下场
老程序员的下场
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有