清华大学数值分析实验报告

数值分析实验报告一、实验3.1题目：考虑线性方程组bAx，nnRA，nRb，编制一个能自动选取主元，又能手动选取主元的求解线性代数方程组的Gauss消去过程。（1）取矩阵6816816816A，1415157b，则方程有解Tx1,,1,1*。取10n计算矩阵的条件数。分别用顺序Gauss消元、列主元Gauss消元和完全选主元Gauss消元方法求解，结果如何？（2）现选择程序中手动选取主元的功能，每步消去过程都选取模最小或按模尽可能小的元素作为主元进行消元，观察并记录计算结果，若每步消去过程总选取按模最大的元素作为主元，结果又如何？分析实验的结果。（3）取矩阵阶数n=20或者更大，重复上述实验过程，观察记录并分析不同的问题及消去过程中选择不同的主元时计算结果的差异，说明主元素的选取在消去过程中的作用。（4）选取其他你感兴趣的问题或者随机生成的矩阵，计算其条件数，重复上述实验，观察记录并分析实验的结果。1.算法介绍首先，分析各种算法消去过程的计算公式，顺序高斯消去法：第k步消去中，设增广矩阵B中的元素0kkka（若等于零则可以判定系数矩阵为奇异矩阵，停止计算），则对k行以下各行计算,1,2,,kikikkkkalikkna，分别用ikl乘以增广矩阵B的第k行并加到第1,2,,kkn行，则可将增广矩阵B中第k列中kkka以下的元素消为零；重复此方法，从第1步进行到第n-1步，则可以得到最终的增广矩阵，即,nnnBAb；列主元高斯消去法：第k步消去中，在增广矩阵B中的子方阵kkkkknkknknnaaaa中，选取kkika使得(k)maxkkikikkinaa，当kik时，对B中第k行与第ki行交换，然后按照和顺序消去法相同的步骤进行。重复此方法，从第1步进行第n-1步，就可以得到最终的增广矩阵，即111,nnnBAb；完全主元高斯消去法：第k步消去中，在增广矩阵B中对应的子方阵kkkkknkknknnaaaa中，选取kkkija使得(k)maxkkkijijkinkjnaa，若kik或kjk，则对B中第k行与第ki行、第k列与第kj列交换，然后按照和顺序消去法相同的步骤进行即可。重复此方法，从第1步进行到第n-1步，就可以得到最终的增广矩阵，即222,nnnBAb；接下来，分析回代过程求解的公式，容易看出，对上述任一种消元法，均有以下计算公式：1;;1,2,,1nnnnnnnnnkkjjjkknkkbxabaxxknna2.实验程序的设计一、输入实验要求及初始条件；二、计算系数矩阵A的条件数及方程组的理论解；三、对各不同方法编程计算，并输出最终计算结果。3.计算结果及分析（1）先计算系数矩阵的条件数，结果如下，12()2557.500000,()1727.556025,()2557.50000condAcondAcondA可知系数矩阵的条件数较大，故此问题属于病态问题，b或A的扰动都可能引起解的较大误差；采用顺序高斯消去法，计算结果为：最终解为x=(1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000001,0.999999999999998,1.000000000000004,0.999999999999993,1.000000000000012,0.999999999999979,1.000000000000028)T使用无穷范数衡量误差，得到*XX=2.842170943040401e-14，可以发现，采用顺序高斯消元法求得的解与精确解之间误差较小。通过进一步观察，可以发现，按照顺序高斯消去法计算时，其选取的主元值和矩阵中其他元素大小相近，因此顺序高斯消去法方式并没有对结果造成特别大的影响。若采用列主元高斯消元法，则结果为：最终解为x=(1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000)T同样使用无穷范数衡量误差，有*XX=0；若使用完全主元高斯消元法，则结果为最终解x=(1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000,1.000000000000000)T同样使用无穷范数衡量误差，有*XX=0；（2）若每步都选取模最小或尽可能小的元素为主元，则计算结果为最终解x=(1.0000000000000001.0000000000000001.0000000000000001.0000000000000010.9999999999999981.0000000000000040.9999999999999931.0000000000000120.9999999999999791.000000000000028)T使用无穷范数衡量误差，有*XX为2.842170943040401e-14；而完全主元消去法的误差为*XX=0。从（1）和（2）的实验结果可以发现，列主元消去法和完全主元消去法都得到了精确解，而顺序高斯消去法和以模尽量小的元素为主元的消去法没有得到精确解。在后两种消去法中，由于程序计算时的舍入误差，对最终结果产生了一定的影响，但由于方程组的维度较低，并且元素之间相差不大，所以误差仍比较小。为进一步分析，计算上述4种方法每步选取的主元数值，并列表进行比较，结果如下：第n次消元顺序列主元完全主元模最小16.000000000000000886.00000000000000024.666666666666667884.66666666666666734.285714285714286884.28571428571428644.133333333333333884.13333333333333354.064516129032258884.06451612903225864.031746031746032884.03174603174603274.015748031496063884.01574803149606384.007843137254902884.00784313725490294.003913894324853884.003913894324853104.0019550342130990.0156173706054690.0156173706054694.001955034213099从上表可以发现，对这个方程组而言，顺序高斯消去选取的主元恰好事模尽量小的元素，而由于列主元和完全主元选取的元素为8，与4在数量级上差别小，所以计算过程中的累积误差也较小，最终4种方法的输出结果均较为精确。在这里，具体解释一下顺序法与模最小法的计算结果完全一致的原因。该矩阵在消元过程中，每次选取主元的一列只有两个非零元素，对角线上的元素为4左右，而其正下方的元素为8，该列其余位置的元素均为0。在这样的情况下，默认的主元也就是该列最小的主元，因此两种方法所得到的计算结果是一致的。理论上说，完全高斯消去法的误差最小，其次是列主元高斯消去法，而选取模最小的元素作为主元时的误差最大，但是由于方程组的特殊性（元素相差不大并且维度不高），这个理论现象在这里并没有充分体现出来。（3）20n时，重复上述实验过程，各种方法的计算结果如下所示，在这里，仍采用无穷范数衡量绝对误差。顺序高斯消去法列主元高斯消去完全主元高斯消去选取模最小或尽可能小元素作为主元消去X1.0000000000000001.0000000000000001.0000000000000001.0000000000000010.9999999999999981.0000000000000040.9999999999999931.0000000000000140.9999999999999721.0000000000000570.9999999999998861.0000000000002270.9999999999995471.0000000000009020.9999999999982091.000000000003524111111111111111111111111111111111.0000000000000001.0000000000000001.0000000000000001.0000000000000010.9999999999999981.0000000000000040.9999999999999931.0000000000000140.9999999999999721.0000000000000570.9999999999998861.0000000000002270.9999999999995471.0000000000009020.9999999999982091.0000000000035240.9999999999931791.0000000000127320.9999999999781731.000000000029102111111110.9999999999931791.0000000000127320.9999999999781731.0000000000291022.910205409989430e-11002.910205409989430e-11可以看出，此时列主元和完全主元的计算结果仍为精确值，而顺序高斯消去和模尽可能小方法仍然产生了一定的误差，并且两者的误差一致。与n=10时候的误差比相比，n=20时的误差增长了大约1000倍，这是由于计算过程中舍入误差的不断累积所致。所以，如果进一步增加矩阵的维数，应该可以看出更明显的现象。（4）不同矩阵维度下的误差如下，在这里，为方便起见，选取2-条件数对不同维度的系数矩阵进行比较。维度条件数顺序消去列主元完全主元模尽量小10n1.7e+32.84e-14002.84e-1420n1.8e+62.91e-11002.91e-1125n5.7e+79.31e-10009.31e-1030n1.8e+92.98e-08002.98e-0840n1.9e+123.05e-05003.05e-0570n3.8e+163.28e+043.88e-123.88e-123.28e+04100n8.5e+163.52e+134.2e-34.2e-33.52e+13从上表可以看出，随着维度的增加，不同方法对计算误差的影响逐渐体现，并且增长较快，这是由于舍入误差逐步累计而造成的。不过，方法二与方法三在维度小于40的情况下都得到了精确解，这两种方法的累计误差远比方法一和方法四慢；同样地，出于与前面相同的原因，方法一与方法四的计算结果保持一致，方法二与方法三的计算结果保持一致。4.结论本文矩阵中的元素差别不大，模最大和模最小的元素并没有数量级上的差异，因此，不同的主元选取方式对计算结果的影响在维度较低的情况下并不明显，四种方法都足够精确。对比四种方法，可以发现采用列主元高斯消去或者完全主元高斯消去法，可以尽量抑制误差，算法最为精确。不过，对于低阶的矩阵来说，四种