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 | |
