数值分析实验-病态线性方程组的算法设计.doc

数值分析课程实验报告实验名称 病态线性方程组的算法设计 班级学号姓名序号任课教师评分一、 实验目的1、 初步病态线性方程组的判定。2、 初步了解常规方法在求解病态线性方程组时遇到的困难。3、 针对病态问题设计求解算法并验证算法的有效性。二、用文字或图表记录实验过程和结果1、Hilbert矩阵如下：其中，它是一个对称正定矩阵，并且随着的增加迅速增加，利用Matlab分析如下：可以发现在阶数不断增大Hilbert矩阵的条件数不断增大，这样使得求解Hilbert病态方程变得非常困难，即使A或b有微小扰动时，即使求解过程是精确进行的（即没有舍入误差），所得的解相对于原方程的解也会有很大的相对误差。这就需要提出病态线性方程组的求解方法，对于一般的方程求解常用的有高斯（选主元）消去算法、高斯赛德尔迭代。本试验先使用用列主元高斯消去算法和高斯-赛德尔迭代算法求解线性方程组：其中。2、高斯列主元消去算法(1)设计流程图：开始给定阶数n自动生成Hilbert矩阵和常数向量b将j列主元Ajj存放在top中|Aij|Ajj|交换i=i+1计算并储存结果在上三角矩阵j=j+1j=n回代结束图1 高斯列主元消去算法流程图(2)计算结果：nX（i） i=1，2.n31.0000 1.0000 1.000051.0000 1.0000 1.0000 1.0000 1.0000101.0000 1.0000 1.0000 1.0000 0.9999 1.0002 0.9997 1.0003 0.9998 1.0000201.0000 1.0000 1.0007 0.9845 1.1685 -0.0788 5.3022 -9.9285 18.5579 -16.6214 14.3775 -14.7664 20.8247 -4.8790 -19.0131 29.7824 -15.5740 5.1150 0.7636 0.9842401.0000 1.0003 0.9898 1.1715 -0.5109 8.6090 -21.5428 39.5435 -36.2332 31.7510 -41.5928 13.7476 65.5399 -15.4594 -82.5762 -26.8622 125.4556-13.6811 -9.9732 -7.3397 -115.6481 200.0592 -38.9658 -116.4953 -112.5598 175.2760 184.9966 -54.0737 -164.9719 -228.9714 377.1052 -22.3954 -83.7536-57.8397 11.5290 123.5671 -106.4045 87.1689 -82.9998 32.3404(3)误差分析：从表中明显发现当Hilbert矩阵的阶数较大时（n=40），与精确解X=1完全不一样，而且误差很大，究其原因，在有Hilbert矩阵的病态性，对于算法中的舍入误差，即使不是很大，而且在算法中的步骤也是精确的，会经过相应的算法将误差进行放大，导致矩阵的条件数随着阶数的升高而不断增大，条件数反映了方程组解对原始数据变化的敏感程度，其值越大，这种敏感性就越高，对于微小的扰动，解的相对误差就可能越大。通常认为条件数是初始的相对误差引起解的相对误差的放大倍数。当n=20时，由于计算机的本身的保存问题，带入了微小的扰动误差，因此导致条件数的不断增大和解的不准确。3、高斯-赛德尔迭代算法(1)设计流程图开始生成Hilbert矩阵和常数b向量给定阶数n和迭代精度tol给定初始解y和准确解并赋值x1迭代求解y|y-x1|=epsk=k+1结果(高斯赛德尔迭代的初始解)高斯赛德尔迭代结果图2 高斯赛德尔迭代算法流程图(2)计算结果：（迭代精度tol=0.01、最速下降法精度eps=0.01）nX（i） i=1，2n30.9986 1.0071 0.993450.9999 1.0012 0.9949 1.0077 0.9963101.0001 0.9992 1.0024 1.0006 0.9954 0.9977 1.0026 1.0050 1.0025 0.9946201.0000 0.9995 1.0030 0.9952 0.9994 1.0029 1.0029 1.0010 0.9989 0.99760.9974 0.9981 0.9994 1.0008 1.0019 1.0025 1.0024 1.0013 0.9994 0.9964401.0000 0.9997 1.0019 0.9954 1.0019 1.0033 1.0010 0.9986 0.9976 0.99790.9989 1.0002 1.0012 1.0018 1.0019 1.0017 1.0012 1.0006 0.9999 0.99930.9989 0.9986 0.9984 0.9984 0.9986 0.9989 0.9993 0.9998 1.0003 1.00071.0011 1.0014 1.0016 1.0016 1.0014 1.0011 1.0005 0.9997 0.9986 0.99731.0000 1.0003 0.9990 0.9997 1.0030 1.0007 0.9981 0.9973 0.9982 0.99961.0010 1.0019 1.0023 1.0021 1.0015 1.0008 1.0000 0.9993 0.9987 0.99830.9981 0.9980 0.9982 0.9985 0.9990 0.9995 1.0000 1.0006 1.0011 1.00151.0018 1.0020 1.0020 1.0018 1.0015 1.0009 1.0001 0.9992 0.9979 0.9965(3)误差分析：虽然在采用了最速下降法后的速度有很大的提高，但是结果较高斯赛德尔迭代有不足，这是由于这种方法和共个梯度都是利用二次函数极小问题求解对称正定矩阵的线性方程组，故在求解二元函数的解的舍入误差直接带入高斯赛德尔迭代的迭代过程中，将误差进一步放大，导致解的误差较直接高斯赛德尔迭代所得解有所增大。但就速度来说，它的意义比带来的误差影响大，故对原来计算方法有所改进。三、练习与思考题分析解答 (1)解线性代数方程组Ax=b，若A的条件数（MATLAB中用cond(A)求A的条件数）很大，意味着原始数据A,b变化微小，也有可能引起解的极大变化，此时称方程组是病态的。这样就可以利用系数矩阵的条件数的大小来基本衡量方程的病态与否。(2)实际工作中, 对于不同的情况, 其不仅要考虑到扰动数量级的大小, 还要考虑到系数大小对其的影响. 因此, 行列式 D 的大小如何选取是一个主要问题. 如 (1) (2)行列式D 的大小分别为0.0002、0.2, 但扰动对结果产生较大变化的数量级相当。 D 数值较大的原因在于方程组的系数较大。方程(1)求解得，方程(2)求解得四、本次实验的重点难点分析本次实验是利用高斯列主元消去算法和高斯赛德尔迭代算法来求解线性方程组，从而熟悉求解线性方程组的一般方法，但是本次实验引入Hilbert矩阵来对各种方法的收敛性进行验证，这正是一般的数学公式和理论方法的检验过程，如果对Hilbert矩阵这种严重病态的方程组，如果求解过程是收敛的，可以说明对大多数的方程组也是一样，这样就可以提出相应的算法。其次，在