数值分析_调和级数收敛问题

ElectronicsEngineeringxxxxx20xx年x月数据与算法实验报告数据与算法实验xxxx20xx/x目录1实验内容描述...............................................................................................................12问题1：理论分析n的值.............................................................................................12.1Float...................................................................................................................12.2Double................................................................................................................23问题2：通用算法........................................................................................................43.1HuffmanAlikeSummation..................................................................................43.1.1理论分析.................................................................................................43.1.2实验结果.................................................................................................53.2Kahan.................................................................................................................63.2.1举例分析.................................................................................................63.2.2理论分析.................................................................................................73.2.3实验结果.................................................................................................74问题3：分析上一问的正确性.....................................................................................85问题4：积分图误差来源.............................................................................................95.1背景...................................................................................................................95.2分析来源..........................................................................................................106问题与体会.................................................................................................................10数据与算法实验xxxx20xx/x11实验内容描述1.用float和double类型分别计算序列求和，试判定是否收敛，收敛的条件是什么，实验给出并从理论上分析收敛时的n=？2.设计通用的求和算法，使得收敛时的n尽量大，所求得的和尽量大（使用float型来计算）。3.设计方案，验证所求结果的正确性（使用float型计算）4.设计方案，验证并解释分析“积分图”快速求解“局部和”误差的来源。返回目录2问题1：理论分析n的值2.1Float对于float的情况，可以先通过实验对累加和与加上1/i之后的值是否相等来判敛。我对每10万次的求和结果打印输出，并且在收敛时停止，结果如图（这里多输出了一些小数点后数字，其实小数点后只有6-7位有效数字）：可见，当n=2097152=221时收敛。而这个n显然不会造成1/n的下溢，因为1/n远远大于float能表示的最小正数（约451.510）；收敛和15.403„„也远远小于最大整数（约383.410）不会造成部分求和的上溢，所以只可能是发生了大数吃小数的情况。下面从理论上分析为什么在n=221处收敛。因为float型浮点数用32bit内存来存储数据，具体bit位分布为数据与算法实验xxxx20xx/x2313023220[符号域][阶数域][尾数域]收敛时sum约为15，阶数域应该是00000011，即十进制的+3。1/n与之相加时，由于1/n很小，要和这个大数阶数域对齐，阶数域应该也是+3。当32432123010.00012222n个时，1/n的尾数域全部是0，这时我们就将看到sum收敛了。可以看出，这时的n=221，实验结果得到了解释。返回目录2.2Double有了分析float型调和级数收敛的基础，我们可以用类似的方法分析double型调和级数。不过有些不同的是，double型有64个bit，而且存储方式和float不相同：636252510[符号域][阶数域][尾数域]所以其收敛原因目前还不能判定是大数吃小数，也有可能是上溢或下溢，需要依次判别哪一种原因下收敛的n更小一些。上溢如果sum在计算过程中上溢，则sum应该超出了double型浮点数的表示范围3081.710。用调和级数近似求和公式()ln0.57721056Snn知，这个时候的3081.710ne，它大致为3081010量级。下溢如果1/n下溢，粗略看1/n应该小于double数的最小正数3245.010，则n为32310量级。显然下溢发生在上溢出现之前，收敛原因不会是上溢。大数吃小数只要分析在下溢发生时，是否已经发生了大数吃小数的情况即可。当n约为32310量级时，sum约为323ln(10)744sum，它小于210，阶数域上应该为00000001001（即数据与算法实验xxxx20xx/x3十进制的9），要发生大数吃小数，1/n的阶数域也应该是9，类似float型的分析方法，有953944010.00012222n52个那么，441321.7610n。这说明，大数吃小数发生在下溢发生之前，下溢也不会是和收敛的原因。至此，已经分析出来double型调和级数的收敛原因是大数吃小数，接下来应该精确计算n的收敛值。可用迭代法：（1）n=244时445453449049ln(2)0.5772156649031.0757210.000122222sumnn52个（2）n=249时496553548048ln(2)0.5772156649034.5414210.000122222sumnn52个（3）n=248时486553548048ln(2)0.5772156649033.8483210.000122222sumnn52个可见收敛的n=248，收敛的和数约为33.8483。为了验证这个结果，在计算机上编程验证。考虑到让计算机从1开始计算1/n的累加和是很漫长的过程（这也是为什么在分析double型的时候没有像前面分析float一样先通过实验找到确切结果），但是这个收敛过程其实是可以从某一个确定的n值来模拟的。在初始化的时候直接将sum初始化为33.8，并且在累加的时候直接让4892210n，之所以选择从这个数开始累加，是因为它已经和理论分析得到的248数据与算法实验xxxx20xx/x4很接近了，只留下来两亿个数让计算机累加，时间是可以忍受的。另外虽然初始化sum=33.8这个值是用欧拉公式估计的并且导致实验最终得到的sum不精确，但是却可以快速找到收敛的n的精确值。下面是实验结果：经比照，它确实是248。综上所述，调和级数和收敛的n值分别为：返回目录3问题2：通用算法3.1HuffmanAlikeSummation3.1.1理论分析类似HuffmanTree的思想，将小数先加起来再加大数，这样有效地避免了小数被大数吃掉的现象，因为很多个小数加起来之后的总值还是比较大的。那么，这个算法的关键就是如何进行分块。为了使收敛的n尽量大，这个分块方法应该是动态的，也就是说，n越大的时候，加的项数应该越多，才能保证每一块加出来的和都是相近的。如下：Forn:1toINFtemp+=1.0f/n;ifna*m//a是一个大于1的实数，a越接近1，精度越高。sum+=temp;coutn=nsum=sumendl;temp=0;m=n;//n作为m的新值这种方法，可以在n很大的时候保证每一块的和值是差不多大的，因为根据欧拉公式，S(n)-S(m)=ln(n/m)=ln(a)。Float型221Double型248数据与算法实验xxxx20xx/x5另外，这种算法的收敛条件也是大数吃小数，不过因为这个大数只是sum的很小一部分（只有ln(a)这么大），所以收敛的n值可以很大。3.1.2实验结果a=3m时虽然sum并没有收敛，但是可以看出，当n=17714700时，sum=17.1793，与用欧拉公式预测的值17.2671已经有一定差距了。所以需要让a小一些。比如下面的例子。n=1.01m时从右图可以看出，当a比较接近于1（比如这里的1.01）的时候，得到的sum可以更加精确。比如右图中的倒数第二个数（n=1011019370约10亿）的误差只有0.008%。当n=231-1时，sum=22.0671，预测值应大约为22.0648，误差为0.01%（跳至问题3）数据与算法实验xxxx20xx/x6需要说明的是，虽然a越小越精确，但是a太小了会降低计算速度，所以需要综合考虑精度和时间两个条件，选择适当的a。返回目录3.2Kahan采用Kahan在1965年提出的Kahansummationalgorithm(alsoknownascompensatedsummation)。为了理解这个算法的原理，可以用下面这个简单的例子i说明。3.2.1举例分析a[]={12345.6,0.123456,12.3456},它们加起来准确值应该是12358.069056。如果有一台计算机，它只能计算到6位有效数字。直接相加a[0]+a[1]=12345.6+0.123456=12345.7