文档介绍：求数值近似开平方算法 200721101008 陈林摘要:本文分别用牛顿迭代法、蒙特卡洛实验法和样条插值方法求数值的近似开方值,并用数值 3开平方为算例,简单比较了三种方法的优劣。一. 牛顿迭代法 :牛顿迭代法实际上是由不动点迭代法的原理结合泰勒展开式构造迭代公式,所以迭代初值必须满足迭代收敛条件'( ) 1 x??,设 y x C ? ?,则 1'2 yx ?,由初值条件解得 1/ 4 x?,不妨设 01x?,3C?,则牛顿迭代公式为: 1 1 3 ( ) 2 n n n x x x ?? ?。 : x0=input('input x0='); %设定迭代初值,本例为 1 er=1; n=0; %定义一个计数器记录循环次数 while er> x=*(x0+3/x0); %牛顿迭代公式 er=abs(x-x0); x0=x; %数值解 n=n+1; end x sqrt3=sqrt(3) %真实数值 n er clear %清除内存变量 : x0x sqrt3 n er 4 -005 因为计算机的截断误差和 matlab 数值显示格式的原因,显示出来的数值解和真实数值是一样的,但从误差变量 er 的值我们可以看到其计算的误差。误差在小数点后的第 5 位,保证了 5 位的有效数字,即的迭代结果是准确的。迭代4次就达到了要求的精度,说明了牛顿迭代法的收敛速度很快,可以证明它的平方收敛的。 4. 注释及花絮(参考文献 Chris Lomont, fast inverse square root, 2000, Mathematics Subject Classification ) 牛顿迭代法初值的选取影响收敛的速度,而且有初值条件,不满足初值条件,迭代公式可能发散,这也是牛顿迭代法的缺陷之一;其次迭代公式中要求解方程的一阶导数,而很多函数无法求导或是求其解析导函数很困难,无法用初等函数表示。所以虽然牛顿迭代法能达到平方收敛,但应用却不是想象那么好。关于迭代初值的研究,很多数学家对此很感兴趣。如卡马克就用 0x5f3759df 作为初值(前两位 0x表示 16进制,后面才是数据,换算成十进制为 1597463007 ), 达到了很好的收敛效果。但我用这个数作为迭代初值却没有看出可以减少迭代次数,感觉还是取解附近的值作为迭代初值好些,也可能是我所选的数值太小了吧。而对于这个神奇的初值,大家都不知道卡马克当时是怎么算出来的,因为效果很好又具有神秘色彩,被大家誉为 Magic Number 。普渡大学的数学家 Chris Lomont 看了以后觉得有趣,决定要研究一下卡马克弄出来的这个猜测值有什么奥秘。 Lomont 也是个牛人,在精心研究之后从理论上也推导出一个最佳猜测值,和卡马克的数字非常接近,0x5f37642f 。卡马克真牛, 他是外星人吗? 传奇并没有在这里结束。 Lomont 计算出结果以后非常满意,于是拿自己计算出的起始值和卡马克的神秘数字做比赛,看看谁的数字能够更快更精确的求得平方根。结果是卡马克赢了... 谁也不知道卡马克是怎么找到这个数字的。