院 系： 计算机学院 专 业： 计算机科学与技术年 级： 2010级 课程名称： 数值分析 学 号： 201006020034 姓 名： 徐叶茂 _2013年 1 月 20 日 一、实验目的数值分析是计算机科学和应用数学的重要交叉部分，对计算机的发展与应用起着十分重要的作用，实验的目的是通过实验评价各种算法的优劣，用高级语言描述学过的算法并上机调试通过，对结果进行分析，加深对各种典型数值问题计算机求解的数值分析基本概念和原理的理解和掌握，进一步熟练掌握高级程序设计语言的使用以及熟悉相关算法在计算机上的实现过程二、主要内容与基本要求本科目在学习的过程中共设置了四道实验题目，分别是关于拉格朗日插值问题、数值积分问题、常微分方程初值问题和非线性方程求根问题要求我们通过实验体会算法的实现过程并对实验的结果进行误差分析以下是四个实验的名称以及相关的顺序：实验1 拉格朗日插值算法实验实验2 组合型求积或龙贝格积分实验实验3 龙格-库塔算法与阿达姆斯算法实验实验4 弦截法和牛顿迭代法求根实验 要求我们通过上机编程实现相关的算法，并对运行的结果进行保存和分析，将调试分析的结果与理论结果进行比较，从而得出算法的优劣性，将分析所得形成分析报告，最终提交实验报告。
三、实验软件对于算法的实现过程利用Dev C++软件进行代码的编写并将得到的结果输出到txt记事本中从而保存实验结果和方便分析四、实验过程实验1 拉格朗日插值算法实验对于本实验我选择的是第二章实验题中的第21题，需要实现的内容是第一问中先利用解析式得出的函数表，然后第二问是利用拉格朗日的一次和二次插值公式分别对进行插值，但是二者对应的值是不同的，第一问中所得的函数表正好为第二问的插值过程提供初值，第三问是对被插值的节点利用解析式计算出对应每个节点的解析解，第四问中要求对一次和二次拉格朗日插值算法求得的数值解和第三问求得的解析解作差，分别获得两次插值各自对应的误差在实验过程中我将两次插值的误差取绝对值，之后对二者进行作差，从而比较二者误差的大小，这样可以体现出一次与二次插值的精确度，最后参照课本对实验结果进行分析并将分析所得的结果记录实验2 组合型求积或龙贝格积分实验对于本实验我选择的是实验题中的第15题，要求写出组合型梯形公式和辛普生公式的标准过程，选择适当的步长计算积分并满足误差限在本实验过程中，因为步长起初是不确定的，我们必须设计出步长变化的算法，并且结果满足所给定的误差限值得一提的是我利用了两种算法来确定步长，一种方法是受龙贝格积分的影响，每次把步长缩小一半，直到满足题给误差限；另外一种方法是利用二分法，设最初把整个区间分为10000份，然后通过二分法逐渐减小所划分的份数，这样也就逐渐增大了步长，使步长的值逐渐接近刚好满足题给条件的情况。
单从数据结果分析，第二种方法的实际效果好于第一种方法，两种方法所进行的计算次数在不同情况下是不一定的，而所用到的存储空间相差不大实验3 龙格-库塔算法与阿达姆斯算法实验对于本实验我选取的是实验题中的第20题，对题17中的微分方程进行求解，先利用n=4的龙格-库塔公式求解了微分方程的区间内所有节点函数值，并用这些值中的前四个点作为阿达姆斯方法的初值，之后我用开型阿达姆斯公式、闭型阿达姆斯公式以及阿达姆斯预报-校正公式对微分方程分别进行了求解，需要指出的是，通常情况下闭型的阿达姆斯方程利用计算机是无法解的，但是第17题刚好是一个特殊情况，它的与项是可以分离的，即在求解的公式中项可以通过移项直接移到左边的式中，从而求解过程相当于一个开型的阿达姆斯方程，但实际应用的是闭型阿达姆斯公式原理然后再利用题给的解析解求解了区间内节点的精确值，并与阿达姆斯方法求解的数值解依次作差，从而比较三种阿达姆斯方法的精度最后是比较阿达姆斯方法与n=4的龙格-库塔方法在求解过程中的精度实验4 弦截法和牛顿迭代法求根实验 对于本实验选择的是实验题第12题中的（2）、（4）两个小题，分别运用到了弦截法和牛顿迭代法两种算法求解非线性方程的根。
第（2）问中要求利用弦截法求解非线性的一个根并且该根在4.0附近，根的近似值是3.73307903，这样就可以确定选择进行求解的区间，选定好自变量的区间之后利用公式进行迭代即可，但是区间的上下界如果选取不恰当的话也可能会导致最终的结果因为发散而溢出，求根失败，在进行试验过程中我将这两种情况都进行了体现，并且我将误差限设置为第（4）问中要求设计一个不用除法操作计算，取a=0.1，0.2，0.5，0.8，2.5和10，并且所提供误差限为，这个算法的实现是通过牛顿迭代法实现的，并且对于初值的选取不同需要进行的迭代次数也不一样，选取的初值离所提供的值越远，所需进行迭代的次数就越多，但是误差的大小情况是不一定的，有可能迭代的次数多，但是精度会比较高，也有可能迭代的次数少且精度高，但是同样存在选取某些节点的值时迭代的结果发散而导致计算在计算机中一直进行而无法输出结果，比如在计算a=10时，如果去初值为时,就会导致计算持续进行而无结果输出五、实验结果分析实验1 拉格朗日插值算法实验 本实验的前三问都是为第四问做准备的，因为之前的三问都只是利用公式进行求解而已，并不涉及任何的分析过程，在第四问中获得解析解与数值解之间的误差，进而对算法进行分析。
对于本道实验题，观察数据可以发现，在最后得到的误差结果中，一次拉格朗日插值的结果相对于真值是总是偏大的，而二次拉格朗日插值的结果总是偏小的，所以可以看出在区间上，一次拉格朗日获得的线性多项式曲线是在函数中曲线上方的，并且随着值的增大，误差逐渐增大，可以看出随着自变量的增大，线性多项式与原函数的偏离程度逐渐增大，同样对于在相同的区间上，二次拉格朗日插值的线性多项式的曲线总是位于原函数的下方，而正好相反，随着自变量值的增加，误差逐渐减小，所以二次插值的线性多项式与原函数的接近程度增大误差关系图（图1）实验所得的结果中，二次拉格朗日插值的误差为负数，所以我取绝对值来作图，以便于比较，并把二者的误差作差进行了比较，如上图通过对上图二者的误差进行比较可以得出，一次拉格朗日插值的准确度不及二次拉格朗日插值的准确度高个人分析产生此种结果的原因如下：一次拉格朗日插值的余项公式为，而二次拉格朗日插值余项为，并且在二次插值所选取的三个节点中有两个节点与一次插值的节点是相同的，并且与选取的节点与所选取节点的距离都小于1，所以二次插值截断的余项的值小于一次插值截断的余项，这是造成二次插值准确度稍高的主要原因，虽然在一些特殊的情况下也有可能大于，但一般情况下节点的选取都满足二次插值余项值小于一次插值余项，这也是为什么在通常情况下，随着拉格朗日插值多项式次数的提高，所得的结果越准确。
特殊情况下比如龙格提出的在区间[-1,1]对函数进行等距节点插值，结果就是一个例外，结果如下： 当|x|<0.726… 当0.726…<|x|<1所以从最终所得数据分析来看，该实验的结果是可靠的，与理论分析的结果是相符的实验2 组合型求积或龙贝格积分实验 因为本实验题中是要求我们选择合适的步长以符合给定的误差限，并且输出结果的数据也不多，可直接参考记事本提供的数据，所以对误差的作图没有太大的意义通过观察得到的数据结果可以发现，虽然两种方法所得到的误差都满足题给的误差限，但是用二分法获得的误差更接近于，而每次步长减半的算法有些甚至已经接近的级别了，这也说明每次步长减半的算法在计算过程中有部分可能满足条件的点被跳过了，而我估计当再用二分法进行处理步长时，最终所得的步长很可能会大于第一种方法所得的步长，但是又小于它的两倍，最后的实验结果与我的猜想是相符的这样证明了在组合型积分过程中，二分法处理步长的实际效果好于直接将步长直接减半 因为在求解的过程中组合型梯形公式和组合型辛普生公式最后在区间上划分的份数是不同的，所以对于最终得到的误差的大小并不能体现出二者的准确度高低按书中所给的局部误差公式分析，组合型梯形公式的局部误差为：而组合型辛普生公式的局部误差为：对应于同一区间时，与值是相等的，若要进行比较，二者应取相同的步长，则此时组合梯形公式所划分的份数是辛普生公式的两倍，假设将按辛普生公式处理将区间划分为n份，则此时梯形公式中应划分为2n份，最后得到的误差结果是在绝大多数情况下，步长的选取不可能会大到选择超过1的值，所以从理论分析的结果是辛普生公式的计算准确度要高于梯形公式。
而本实验中二分法的实验结果似乎符合这个分析结果，但是由于步长的不同，所以是不具有说服力的实验3 龙格-库塔算法与阿达姆斯算法实验以下图中是四种方法计算所得到的误差比较：误差关系图（图2）备注：其中误差1是n=4的龙格-库塔方法；误差2是开型阿达姆斯方法；误差3是闭型阿达姆斯方法；误差4是阿达姆斯预报-校正方法通过观察实验得到的数据可以得出n=4的龙格-库塔公式求解的结果的精度要高于开型和闭型的阿达姆斯方法所求解的结果，而闭型阿达姆斯的精准度要高于开型阿达姆斯的精准度后者的实验结果与理论结果是相符的，而对于前者，书中并没有给出理论方面的结论，只是提到m=3的阿达姆斯公式与n=4的龙格-库塔公式的误差都是，并且多步法比单步法节省运算量我个人分析的原因如下：n=4的龙格-库塔公式属于单步法，利用的是相邻的一个节点，通过计算K1，K2，K3，K4的值来最终刻画出点的函数值虽然计算量较之多步法略显复杂，但是这样对点的描述显然更细致而多步法选择之前的四个点作为启动节点来估算本节点，对该点的描述情况会略显粗糙一些，尤其当步长h的取值比较大时，阿达姆斯的误差应该还会有所增加，相反若步长h值减小的话，误差应该会相应地减小，但是准确度好坏的排序并不会因此而改变，在之后进行的取若干步长的实验中也证实了这个分析过程，步长增大或者减少，误差也会相应增大或者减少，但准确度依然是n=4的龙格-库塔公式最好，然后是闭型和开型的阿达姆斯公式。
实验中我还利用阿达姆斯预报-校正算法对微分方程进行了计算，计算的结果很令人满意，误差的增大速度缓慢并且准确度高于n=4的龙格-库塔公式，阿达姆斯预报-校正算法运用到了开型和闭型的阿达姆斯公式，通过李查逊外推技术，最终获得更高精度的计算公式，当然二者的比较都是在步长h=0.02的情况下进行的因为只输出小数点后八位时误差之间的区分不是很明显，所以我选择输出小数点后的十二位以用来明显区分所得误差，否则很多误差的结果通过四舍五入之后是相同的实验4 弦截法和牛顿迭代法求根实验弦截法图（牛顿迭代没有提供图）：误差关系图（图3）备注：误差（2）指的是第二问中的误差；这个图刻画的是弦截法误差的递变速率，在最初几次呈线性递减，后面则是递减速率是逐级放大的，观察图中斜率和结合所提供的数据可以明显发现这一点在第二问中，分析实验所得的数据可以发现，当初值选择可以保证收敛时，随着迭代的次数的增加，误差的递减速度也逐渐加快，在开始时每迭代一次，误差的次数缩减为原来的1/10左右，到后面速度加快到1/100和1/10000，比如当我选取的区间上下界分别为3.5和4.5时，经过6次迭代后得到满足误差限的结果，并且分析误差数据可以发现，误差的递减速度是逐渐加快的。
当选取的区间上下界分别为1.5和4.0时，在迭代的过程中结果是发散的，最终数据异常而跳出计算的过程在第四问中，我对三种情况都进行了测试，对于因为一直运行而无法跳出计算过程的情况没有提供参考。