牛顿迭代法(Newton's Method)

牛顿迭代法(Newton's Method)                   

简介

牛顿迭代法(简称牛顿法)由英国著名的数学家牛顿爵士最早提出。但是,这一方法在牛顿生前并未公开发表。

牛顿法的作用是使用迭代的方法来求解函数方程的根。简单地说,牛顿法就是不断求取切线的过程。 对于形如f(x)=0的方程,首先任意估算一个解x0,再把该估计值代入原方程中。由于一般不会正好选择到正确的解,所以有f(x)=a。这时计算函数在x0处的斜率,和这条斜率与x轴的交点x1。 f(x)=0中精确解的意义是,当取得解的时候,函数值为零(即f(x)的精确解是函数的零点)。因此,x1比x0更加接近精确的解。只要不断以此方法更新x,就可以取得无限接近的精确的解。 但是,有可能会遇到牛顿迭代法无法收敛的情况。比如函数有多个零点,或者函数不连续的时候。

牛顿法举例

下面介绍使用牛顿迭代法求方根的例子。牛顿迭代法是已知的实现求方根最快的方法之一,只需要迭代几次后就能得到相当精确的结果。 首先设x的m次方根为a。

下面程序使用牛顿法求解平方根。

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

更快的方法

文献2提到了比上述程序更快的求解平方根的非典型牛顿迭代法。介绍如下。 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?  这句话的注释是“what the fuck?”,翻译过来就是“我靠?” 任何受过程序训练的人看到这句大概都会在想,这句话到底在搞什么鸟? 之所以会出现这种奇怪的注释,要么是此段程序的作者(可能是马克尔)根本不知道该如何解释清楚,或者是维护这段程序的程序员完全看不懂这句话,所以有点儿抓毛。而实际上,它的作用(再加上y = y * ( threehalfs - ( x2 * y * y ) )这句牛顿迭代)就是求平方根。 至于是为什么,本博主也不知道。 以雷神之锤III程序为蓝本可以写出比sqrt()更强大的求平方根函数:

 1 int sqrt(float x) { 
 2     if(x == 0) return 0; 
 3     float result = x; 
 4     float xhalf = 0.5f*result; 
 5     int i = *(int*)&result; 
 6     i = 0x5f375a86- (i>>1); // what the fuck? 
 7     result = *(float*)&i; 
 8     result = result*(1.5f-xhalf*result*result); // Newton step, repeating increases accuracy 
 9     result = result*(1.5f-xhalf*result*result); 
10     return 1.0f/result; 
11 }

参考文献: 1.wikipedia.org 2.http://www.2cto.com/kf/201206/137256.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

从深度学习到机器人控制,2017 人工智能新开发工具盘点

2017 年,在深度学习技术的加持下,CV、NLP、数据分析等领域全面开花,同时大量新开发工具和开源软件的涌现,降低了人工智能开发的门槛,加速了深度学习的普及。...

38760
来自专栏大数据文摘

2016年2季度爆文精选 TOP10

22880
来自专栏新智元

DeepMind 创始人 Cell 评论:通用人工智需要怎样的学习系统?

【新智元导读】谷歌 DeepMind 创始人 Demis Hassabis 等人近日在细胞出版社期刊发表评论,拓展辅助学习系统(CLS)理论,为研究通用人工智能...

38630
来自专栏FD的专栏

从人脸识别到机器翻译:52个有用的机器学习和预测API

人工智能正在成为新一代技术变革的基础技术,但从头开始为自己的应用和业务开发人工智能程序既成本高昂,且往往很难达到自己想要的性能表现,但好在我们有大量现成可用的 ...

11610
来自专栏大数据挖掘DT机器学习

52 个有用的机器学习与预测API

随着基于人工智能与机器学习的应用如雨后春笋般不断涌现,我们也看到有很多提供类似功能的 API 悄悄登上了舞台。 API 是用于构建软件应用的程序、协议以及工具的...

403100
来自专栏ATYUN订阅号

Pinterest推出基于深度学习的PinSage以增强其推荐系统

来自Pinterest的开发人员以及斯坦福大学的研究人员合作推出PinSage,这是一种基于深度学习的高级推荐框架,用于社交网络中的广告和购物推荐。

74540
来自专栏AI科技评论

干货 | 论机器学习的可重复性危机

AI 科技评论按:机器学习研究者、Jetpac 的 CTO、《The Public Data Handbook》和《The Big Data Glossary ...

10410
来自专栏织云平台团队的专栏

T4 级老专家:AIOps 在腾讯的探索和实践

我今天要讲的主题,AIOps,是一个比较新的话题,其实从概念的提出到我们做,只有差不多一年的时间。一个新事物,有其发展的周期,在腾讯里面我们做了比较多的探索,但...

14.1K00
来自专栏大数据挖掘DT机器学习

从采集到建模:某二手主机游戏交易论坛用户行为分析

作者:陈丹奕 宜人贷 数据分析师 https://ask.hellobi.com/blog/datanaystimprovement/4902?utm_sour...

38460
来自专栏新智元

【深度】TensorFlow or TensorSlow,谷歌基准测试为何不给力?(附Google内部员工测试代码下载)

11月9日Google发布了第二代深度学习引擎TensorFlow,引起业内广泛关注。发布后业内人士热议的一个话题是:这个引擎能否成为Google所说的平台级产...

52640

扫码关注云+社区

领取腾讯云代金券