数值计算方法62

1、华长生制作1fBxxkk)()1(nkknknxfCabI0)()()()()(2)0(0bfafabTbadxxfA)(, 3 ,2 , 1k中南大学数学科学与计算技术学院陈海波第四章 非线性方程的数值解法 4.2 线性方程组的迭代法线性方程组的迭代法华长生制作2 4.2 线性方程组的迭代法线性方程组的迭代法在用直接法解线性方程组时要对系数矩阵不断变换如果方程组的阶数很高,则运算量将会很大并且大量占用计算机资源因此对线性方程组bAx 要求找寻更经济、适用的数值解法nnnnRxRbRA,设-(1)华长生制作3如果能将线性方程组(1)变换为fBxx-(2)nnnnRxRfRB,其中显然,(1)式

2、和(2)式同解, 我们称(1)(2)等价对线性方程组(2),采用以下步骤:可得代入取初始向量),2(,)0(xfBxx)0()1(依此类推华长生制作4fBxx)1()2(fBxxkk)()1(),2 , 1 ,0(k-(3)这种方式就称为迭代法 ,以上过程称为迭代过程迭代法产生一个序列0)(kx如果其极限存在,即*)(limxxkk则称迭代法收敛, 否则称为发散华长生制作5一、简单迭代法(基本迭代法)设线性方程组(1)的一般形式为11212111bxaxaxann22222121bxaxaxannnnnnnnbxaxaxa2211),2 , 1(0niaii设ix则可从上式解出,)(11212

3、1111nnxaxabax华长生制作6)(123231212222nnxaxaxabax)(11111111njjjjxabax依此类推,线性方程组(1)可化为)(12122222njjjjxabax)(11nijjjijiiiixabax)(11nnjjjnjnnnnxabax-(4)(1111111njjjxabax)(1122222njjjxabax)(11njjijiiiixabax)(11njjnjnnnnxabax华长生制作7-(5)(11)()()1(njkjijiiikikixabaxx对(4)作迭代过程),2 , 1 ,0;,2 , 1(kni),(2211nnaaadiag

4、D设则(5)式转化为矩阵形式)()(1)()1(kkkAxbDxxbDAxDxxkkk1)(1)()1(bDxADDxkk1)(1)1()(-(6)华长生制作8令0000002121nnaaaL0000002112nnaaaU的负矩阵的下三角部分A的负矩阵的上三角部分AULDAULAD华长生制作9故迭代过程(6)化为bDxULDxkk1)(1)1()(于是令,),(11bDfULDBJfxBxkJk)()1(),2 , 1 ,0(k等价线性方程组为fxBxJbAx -(7)称(5)式和(7)式为解线性方程组(1)的Jacobi迭代法(J法)迭代法的迭代矩阵为JacobiBJ华长生制作10例1.

5、用Jacobi迭代法求解方程组,误差不超过1e-41233204121114238321xxx解:4121114238A4000110008D000100230U012004000L华长生制作11)(1ULDBJ04121111011441830bDf1335 .2迭代法使用取初值JacobixT,000)0(fxBxkJk)()1(),2 , 1 ,0(nk 华长生制作1204121111011441830fxBxJ)0()1(335 .2000T3,3,5 .2924.4)0()1( xx04121111011441830fxBxJ)1()2(335 .2335 .2T1 ,3636.2,

6、875.21320.2)1()2( xx华长生制作1304121111011441830fxBxJ)2()3(335 .213636.2875.2T9716.0,0455.2,1364.34127.0)2()3( xx依此类推,得方程组满足精度的解为x12迭代次数为12次 x4 = 3.0241 1.9478 0.9205 d = 0.1573 x5 = 3.0003 1.9840 1.0010 d = 0.0914 x6 = 2.9938 2.0000 1.0038 d = 0.0175 x7 = 2.9990 2.0026 1.0031 d = 0.0059 x8 = 3.0002 2.0

7、006 0.9998 d = 0.0040 x9 = 3.0003 1.9999 0.9997 d = 7.3612e-004x10 = 3.0000 1.9999 0.9999 d = 2.8918e-004x11 = 3.0000 2.0000 1.0000 d = 1.7669e-004x12 = 3.0000 2.0000 1.0000 d = 3.0647e-005Jacobi.m0000.10000.20000.3321xxx华长生制作14分析Jacobi迭代法(5)的迭代过程,将(5)式细化)(11)(1111)(1)1(1njkjjkkxabaxx)(11)(2222)(2)1

8、(2njkjjkkxabaxx已经求出之前发现在)1(1)1(2)1(1)1(,kikkkixxxx进行迭代仍用时但当求)(1)(2)(1)1(,kikkkixxxx?,)1(1)1(2)1(1)1(进行迭代呢利用时能否求kikkkixxxx华长生制作15考虑迭代式(7)fxBxkJk)()1(),2 , 1 ,0(kbDxULDxkk1)(1)1()(即bUxLxDxkkk)()()1(),(不含对角线下三角的形式注意到 L将上式改为bUxLxDxkkk)()1()1(-(8)华长生制作16bUxxLDkk)()1()(可逆时当LD 部分包括对角线的下三角即为)(ALD bLDUxLDxkk

9、1)(1)1()()(得设,)(,)(11bLDfULDBGGGkGkfxBx)()1(-(9)上式称为Gauss-Seidel迭代法,简称G-S法利用(8)式展开Gauss-Seidel迭代法也可表示成),2 , 1 ,0(k华长生制作171112)(111)1(111baxaaxnjkjjk2223)(22211)1(222)1(2111baxaaxaaxnjkjjjkjjk3334)(33321)1(333)1(3111baxaaxaaxnjkjjjkjjkiiinijkjijiiijkjijiikibaxaaxaax1111)(11)1()1(nnnnjkjnjnnknbaxaax11

10、11)1()1(华长生制作18例2.用Gauss-Seidel迭代法求解例1.解:迭代法使用取初值SeidelGaussxT,0 , 0 , 0)0(11132)(111)1(111baxaaxjkjjk5 .2)23(81)(3)(2kkxx22233)(22211)1(222)1(2111baxaaxaaxjkjjjkjjk3111114)(3)1(1kkxx3321)1(333)1(311baxaaxjkjjk3)12(41)1(2)1(1kkxx华长生制作19x1 =2.5000 2.0909 1.2273 d =3.4825x2=2.9773 2.0289 1.0041 d =0.5

11、305x3 =3.0098 1.9968 0.9959 d =0.0465x4 =2.9998 1.9997 1.0002 d =0.0112x5 =2.9998 2.0001 1.0001 d =3.9735e-004x6 =3.0000 2.0000 1.0000 d =1.9555e-004x7 =3.0000 2.0000 1.0000 d =1.1576e-005通过迭代,至第7步得到满足精度的解x7Gauss_seidel.m从例1和例2可以看出,Gauss-Seidel迭代法的收敛速度比Jacobi迭代法要高Jacobi迭代法和Gauss-Seidel迭代法统称为简单迭代法华长生

12、制作20二、迭代法的改善称的近似解为线性方程组设,bAxxrAx xAbr为剩余向量,称的解为修正向量,rAzz,表示用zxx令)(zxAAxAzxArrbb是精确解吗z华长生制作21用双精度求解用双精度求解)1(xbAx的近似解为求)1()1()1(Axbrx的剩余向量求)1()1(zrAz的近似解为求)1()1()2(zxxbAx的改进解得)2()2()2(Axbrx的剩余向量求)2()2(zrAz的近似解为解)2()2()3(zxxbAx的改进解得依此类推,直到得到满足精度要求的解修正向量迭代终止时EPSzk|)(华长生制作22三、迭代法的收敛性设解线性方程组的迭代格式fBxxkk)()

13、1(则而方程组的精确解为*,xfBxx*-(10)-(11)将(10)与(11)相减,得*)()1(BxBxxxkk*)()(xxBk*)()(xxkk令,2,1 ,0k华长生制作23则)()1(kkB)1(2kB)0(1kB为非零常数向量注意*)0()0(xx因此迭代法收敛的充要条件*)(limlim)1()1(xxkkkk00lim1kkB可转变为定理1.迭代格式(10)收敛的充要条件为0limkkB-(12)华长生制作24根据矩阵与其Jordan标准形及特征值的关系,可知0limkkB1小于的所有特征值的绝对值B即1)(B因此定理2.迭代格式(10)收敛的充要条件为-(13)1)(B又因

14、为矩阵的谱半径不超过其任一种算子范数,即BB )(于是又可得到华长生制作25定理3.-(14)收敛为迭代矩阵的迭代法则以若)10(, 1BB 且)1()()(1kkkxxBB证明:只证(14)式*)1(xxk*)()()1(xxxxkkk*)(xxk)(*)()1()1(kkkxxxx*)(xxk)()1()1(*kkkxxxx)(*)()1()()(kkkxxBxxB华长生制作26*)(xxk)1()()(*kkkxxBxxB所以*)(xxk)1()(1kkxxBB-(14)即)1()()(1kkkxxBB(14)可以用来估计迭代法的精度,理论上只要epsBBxxkk1)1()(epsk)(

15、华长生制作27在计算时,迭代终止的时间可以用上式判别例3.判别下列方程组用J法和G-S法求解是否收敛111122111221321xxx解:(1) 求Jacobi法的迭代矩阵)(1ULDBJ100010001022101220022101220华长生制作28, 1JJBB 的几种常用算子范数显然因此不能用定理3只能用定理2判断)det(JBI 221122det30所以0|)max(|)(JB01即Jaobi迭代法收敛(2) 求Gauss-Seidel法的迭代矩阵ULDBG1)(1122011001000100220华长生制作29GB200320220同样用定理2判断02|)max(|)(GB

16、21所以Gauss-Seidel迭代法发散在例1和例2中,G-S法收敛速度比J法要高但例3却说明G-S法发散时而J法却收敛因此,不能说G-S法比J法更好华长生制作30另外,给出系数矩阵对角占优线性方程组的一个结论定理4.法均收敛法和则矩阵为严格对角占优的系数矩阵若线性方程组SGJacobiAbAx,证:(1)对于Jacobi迭代法,其迭代矩阵为)(1ULDBJ所以严格对角占优因为系数矩阵,Aniaaijijii, 3 ,2 , 1|niaaijijii, 3 ,2 , 11|1华长生制作310002122222211111112nnnnnnnnJaaaaaaaaaaaaBJBijijiiiaa|1max1根据定理3Jacobi迭代法收敛(2)对于G