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

1、数值分析课程实验报告实验名称病态线性方程组的算法设计班级学号姓名序号任课教师评分、实验目的1、初步病态线性方程组的判定.2、初步了解常规方法在求解病态线性方程组时遇到的困难.3、针对病态问题设计求解算法并验证算法的有效性.、用文字或图表记录实验过程和结果1、Hilbert矩阵如下：11/2L1/nHn (hj)1/21/3L1/ (n 1)MMM1/n1/(n 1)L1/(2 n 1)其中hj % j “,它是一个对称正定矩阵,并且con d(Hj随着n的增加 迅速增加,利用Matlab分析如下：可以发现在阶数不断增大Hilbert矩阵的条件数不断增大,这样 使得求解Hilbert病态方程变得

2、非常困难,即使A或 b有微小扰动时,即 使求解过程是精确进行的(即没有舍入误差),所得的解相对于原方程 的解也会有很大的相对误差.这就需要提出病态线性方程组的求解方 法,对于一般的方程求解常用的有高斯(选主元)消去算法、高斯一 赛德尔迭代.本试验先使用用列主元高斯消去算法和高斯-赛德尔迭代 算法求解线性方程组：HnnX b其中 b Q丄,bn)T,bhij (i 1,2,L , n).2、咼斯列主兀消去算法j 1(1)设计流程图：(2)计算结果:nX (i )i=1, 2.n35102040(3)误差分析：从表中明显发现当Hilbert矩阵的阶数较大时(n=40),与精确解 X=1完全不一样,

3、而且误差很大,究其原因,在有 Hilbert矩阵的病 态性,对于算法中的舍入误差,即使不是很大,而且在算法中的步骤 也是精确的,会经过相应的算法将误差进行放大,导致矩阵的条件数 随着阶数的升高而不断增大,条件数反映了方程组解对原始数据变化 的敏感程度,其值越大,这种敏感性就越高,对于微小的扰动,解的 相对误差就可能越大.通常认为条件数是初始的相对误差引起解的相 对误差的放大倍数.当n=20时,由于计算机的本身的保存问题,带入 了微小的扰动误差,因此导致条件数的不断增大和解的不准确.3、高斯-赛德尔迭代算法(1)设计流程图给定阶数n和迭代精度生成Hilbert矩阵和常数b向给定初始解y和准确解并

4、赋值x1迭代求解y结束图2高斯一赛德尔迭代算法流程图(2)计算结果：(迭代精度tol=(3)误差分析：高斯一赛德尔迭代是对于线性方程组的比拟行之有效的方法,高斯一赛德尔迭代较之雅可比迭代有很大的改良,由于在每次迭代中都 是采用最新的迭代数据,对迭代解的限制有很大的进步,本试验在精 度限制的时候采用步数的自动限制,进一步限制解的准确性.虽然在 计算机存储的时候也有微小的舍入误差,但是当限制精度得到后,由 于迭代的步数没有指定,经过迭代后,其解会到达恨到的精度.但是 对于高斯赛德尔迭代,要到达指定的精度,需要大量的迭代步骤,降低了运算速度.因此在设计新算法的时候, 主要考虑如何降低运算迭代次数,由

5、于在实际的运算中,时间的快慢 直接关系到算法的好坏,因此,在设计新算法的时候,采用最速下降 法进行初始值的估算,然后用高斯一赛德尔迭代进行进一步的求解. 虽然在实际的运算过程中,最速下降法速度很慢,但是由于本实验仅 仅用它来求迭代初始解,应选用最速下降法,而放弃共轭梯度算法.4、设计新算法一一利用最速下降法求得迭代的初始解(1)设计流程图：图2高斯一赛德尔迭代算法流程图(2)计算结果：(迭代精度tol=、最速下降法精度eps=)nX (i )i=1, 2 n35102040(3)误差分析：虽然在采用了最速下降法后的速度有很大的提升,但是结果较高 斯一赛德尔迭代有缺乏,这是由于这种方法和共个梯度

6、都是利用二次 函数极小问题求解对称正定矩阵的线性方程组,故在求解二元函数的 解的舍入误差直接带入高斯一赛德尔迭代的迭代过程中,将误差进一 步放大,导致解的误差较直接高斯一赛德尔迭代所得解有所增大.但 就速度来说,它的意义比带来的误差影响大,故对原来计算方法有所 改良.三、练习与思考题分析解答(1) 解线性代数方程组Ax二b,假设A的条件数(MATLAB用cond(A) 求A的条件数)很大,意味着原始数据 A,b变化微小,也有可能引起 解的极大变化,此时称方程组是病态的.这样就可以利用系数矩阵的条件数的大小来根本衡量方程的病态与否.(2) 实际工作中,对于不同的情况,其不仅要考虑到扰动数量级 的

7、大小,还要考虑到系数大小对其的影响.因此,行列式D的大小 如何选取是一个主要问题.如2x1 3x2 8(1)2x1 3.0001x2 8.0002 2000x1 3x2 82000x1 3.0001x2 8.0002行列式D的大小分别为、,但扰动对结果产生较大变化的数量级 相当.D数值较大的原因在于方程组的系数较大.方程(1)求解得x1 x24.00000.0007方程(2)求解得x1 0.0040x2 0.0007四、本次实验的重点难点分析本次实验是利用高斯列主元消去算法和高斯一赛德尔迭代算法来 求解线性方程组,从而熟悉求解线性方程组的一般方法,但是本次实 验引入Hilbert矩阵来对各种方法的收敛性进行验证,这正是一般的 数学公式和理论方法的检验过程,如果对Hilbert矩阵这种严重病态的方程组,如果求解过程是收敛的,可以说明对大多数的方程组也是 一样,这样就可以提出相应的算法.其次,在设计过程中,由于各种算法都存在一定的缺陷,所以在 提出新算法的时候必须考虑各种算法的优缺点,例如咼斯列主