s****d 发帖数: 56 | 1 Sqrt(a)可以用牛顿法公式迭代得到:
x=(x+a/x)/2.0 (1)
我用Java实现时,用了另一个“等价”公式:
x=(x*x+a)/(2.0*x) (2)
x我用的时double,leetcode测试表明公式(1)总是能收敛到一个固定的value,而公式(
2)却有时会出现最后在两个value跳跃的情况。
比如sqrt(3),用公式(1)的收敛序列是:
3.0 2.0
2.0 1.75
1.75 1.7321428571428572
1.7321428571428572 1.7320508100147274
1.7320508100147274 1.7320508075688772
1.7320508075688772 1.7320508075688772
sqrt(3),用公式(2)最后在两个值之间跳跃:
3.0 2.0
2.0 1.75
1.75 1.7321428571428572
1.7321428571428572 1.7320508100147274
1.7320508100147274 1.7320508075688772
1.7320508075688772 1.7320508075688774
1.7320508075688774 1.7320508075688772
我感觉应该和浮点运算的近似结果有关,但却不知道怎么准确解释这种现象,尤其为什
么公式(1)就能保证收敛。
哪位大神能解释一下为什么公式(1)能保证收敛,而公式(2)却不能? |
n****e 发帖数: 2401 | 2 x*x然后再除以x导致误差扩大,因为两个数的乘积只能保留前面一部分小数,四舍五入
后最后一位可能在两个数字之间跳动。而且其实乘积的结果只能是用二进制表示,与数
学实际结果有区别。
用(x*x*x+a*x)/(2.0*x*x)看看有什么更有趣的结果。 |
s****d 发帖数: 56 | 3 试了(x*x*x+a*x)/(2.0*x*x),最后也是在两个value跳动:
3.0 2.0
2.0 1.75
1.75 1.7321428571428572
1.7321428571428572 1.7320508100147274
1.7320508100147274 1.7320508075688772
1.7320508075688772 1.7320508075688776
1.7320508075688776 1.7320508075688772
1.7320508075688772 1.7320508075688776
>>x*x然后再除以x导致误差扩大,因为两个数的乘积只能保留前面一部分小数,四舍五入
>>后最后一位可能在两个数字之间跳动。
恩,有道理。
同样是浮点运算,为什么 x=(x+a/x)/2.0 能保证不会出现四舍五入导致的跳动呢 (除
法也有四舍五入啊)? |
n****e 发帖数: 2401 | 4 我觉得因为两个长小数相乘会变成一个非常长的小数,必须要截断,导致了误差。而且
x*x/x这种计算方法导致了结果的循环出现。 |
s****d 发帖数: 56 | 5 >>x*x/x这种计算方法导致了结果的循环出现。
恩,明白了,很有道理! |
h**********c 发帖数: 4120 | 6 跟数值分析的老板混过几年
想起来个东西叫pivoting, |
h**********c 发帖数: 4120 | 7 温习老板的notes
这个东西叫gauss elimination with pivoting, 然后几页是error analysis
北mexico的数值计算水平堪优啊!
长太息!
真是求blah 得blah++
【在 h**********c 的大作中提到】 : 跟数值分析的老板混过几年 : 想起来个东西叫pivoting,
|
h**********c 发帖数: 4120 | 8 mbd,
难怪bank of 北墨西哥老算错帐
给我老算多了,还它就算了
算少了,我一上午argue的误工费谁出
【在 h**********c 的大作中提到】 : 温习老板的notes : 这个东西叫gauss elimination with pivoting, 然后几页是error analysis : 北mexico的数值计算水平堪优啊! : 长太息! : 真是求blah 得blah++
|
s********t 发帖数: 11 | |