数值分析 线性方程组迭代解法

1、第四章线性方程组迭代解法返回前进第四章目录返回前进第四章 方程组的迭代解法概述), 2 , 1 , 0( )() 1(kgMxxkk返回前进1 向量与矩阵的范数返回前进6.1 向量与矩阵的范数 具有如下三个性质：为模的长度平面上任一向量,)(),(222121aaaaaaT时成立等号成立仅当0, 0 ) 1 (aaaa, )2(对任意实数)( ) 3(三角不等式baba且满足：若对应非负实数维向量对于任意,xRxnn;0, 0 ) 1 (时成立等号仅当xxxx )2(：对任意实数yxyx)3(的范数或模为向量则称xx返回前进常用的向量范数ininnTnxxxxxxxxxxxxxx1211222

2、21221max:,),(；常用的向量范数有设yxyxyxyxyxiniiniiiniiini1111maxmaxmax max返回前进对2范数2212/112/11yxyxyxniniiniiii22222222211212112222 2yxyyxxyyxxyxyxniniiniiiniii.:0,的则称这两种范数是等价使存在实数中任意两种向量范数如果对xMxxmMmxxRan返回前进Rn中范数的等价性 2222211maxxxxxxxnini xnxxnxnxxxxxxxxnjinij22222211 max即有：则：设xnxx1返回前进矩阵范数 （相容性），有：、阶方阵对于任意两个对任

3、意实数时成立等号仅当BAABBABABAnAAAA)4(;) 3(;,)2(;0, 0) 1 (返回前进常用的矩阵范数)( max) 1 (11称为最大行和njijniaA)( max)2(111称为最大列和niijnjaA的最大特征值为，AAAT112)3(ninjijFaA112)4(返回前进BAbabababaBAnjijninjijninjjinjjinjjijinjijijnioooo111111111maxmax max3 ）：（BAbabababaABnjkjnknkikninknjkjikninknjkjikninjnkkjikni1111111111111maxmax max

4、 maxmax4）：（常用的矩阵范数（续）返回前进最大行和矩阵范数的证明：即要证满足范数的四条的范数为矩阵下证,max111AaAniijnj0010, 2 , 1, 0max00: ) 1 ( 11111AanianjaAAijniijniijnj有：到从，亦即对任意有：当且仅当对所有的即显然：若证1111212222111211 maxmaxmax)(.;. : ) 2(AaaaAaaaaaaaaaaAniijijjijnjijnnnnnn那么：证返回前进1111111maxmax maxmax)(),() 3(BAbababaBAbBaAniijniijniijijniijijijij于

5、等于绝对值之和：，注意到和的绝对值小：对证11111111111)max)(max( max max)4(BAbababaABnikjnjniiknkniijijnkninkkjik）（：证最大行和矩阵范数的证明返回前进范数的相容性 XAAX22222111xAAxxAAxxAAxxAAxF，APpPAAAAA与AAAA返回前进求范数举例，求相应各范数，则：设TTAxAx)11, 7(4321,) 5, 3(1111118 6 8 xAAxAx解：342x043014)20)(10(2014141022AAIT令22115 ,22115 :21的特征值得AAT222222170)11() 7(

6、 ,22115 xAAxA故2014141043214231 :AAT因为xAAxAx11 7 5返回前进 向量序列与矩阵序列的极限xxxxxxxRxxxxkkkkkknTknkkk)()()()()()(2)(1)(lim,0lim,),(记为收敛于则称序列有：如果对任何向量范数都对向量序列设向量返回前进 向量序列与矩阵序列的极限（续） ), 2 , 1( lim)()(nixxxRxRikiknkn当且仅当向量中的收敛于中的向量序列), 2 , 1( lim ), 2 , 1( 0limmax010lim, 1 )()()()(1)()()(nixxnixxxxxxxxnixxxxikik

7、ikikkjkjnjikikkk亦即由极限存在准则得：，有：而对任意的即：收敛于由定义证明返回前进矩阵序列的收敛概念及定理AAAAAAnAnAkkkkkk)()()()(lim,0lim记为收敛于矩阵则称序列任何矩阵范数都有：阶方阵，如果对于为阶方阵序列，为设), 2 , 1, 2 , 1( lim,)(), 2 , 1)()()()()()(njniaaAAnAnaAkaAijkijkkkijkijk，收敛于且矩阵序列阶方阵均为则矩阵序列阶方阵均为设返回前进的谱。称为矩阵AAnini),(max)(211因此有：的谱是矩阵出由特征值的定义容易得), 2 , 1)(,(,21kAAAAknkk

8、k16)-(3 )()(kkAA返回前进矩阵的谱半径（续）AxAxx017)-(3 )(AAxAAxxAxx相容性返回前进公式 的重要性说明AA )(18)-(3 )(AA2)(AA 1)(0limAAnAkk充要条件阶方阵，则：为设返回前进定理3（续）0lim 0limlim 12)(1)()183(02)(11)()(kkkkkkkkAAAAAAAAAA所以有于是而存在一种矩阵范数使得由取若充分性1)( 0)(lim,)()(0)173()163(0lim20lim)(AAAAAAAkkkkkkkkk所以有于是由极限存在准则有及而利用有由定义若必要性返回前进19)-(3 ), 2 , 1

9、, 0( )()1(kgMxxkk1)()(Mxk充分必要条件收敛产生的向量序列1)( 30lim0*)(lim*)(lim *)( *)( *)( *194*lim)0()()0()()0()2(2)1()1()(*)(*MMnxxxxxMxxMxxMxxMgMxgMxxxgMxxxxxxnKkkkkkkkkkkkk有由定理必然有：维向量，因此上式成立为任意因为有于是），有：，由迭代公式（满足：则：，使得：维向量）设存在（返回前进收敛若条件下在定理)(1,4kxM收敛。）产生的向量序列这表明：由迭代式（，都有：所以，对任意初始向量又因为并且即：记为有唯一解方程组维向量于是对任意因而有的特征值

10、不是矩阵则若反之1930*)(lim*)(lim*)(*)(* 0lim *,)(, 01, 1)(,)()()0()()0()0()1()(kkkkkkkkkkxxxMxxxxxMxxMxxMgMxxxgxMIgnMIMM返回前进4.2 方程组的误差分析 0, 220001. 12212121xxxxxx1, 10001. 20001. 12212121xxxxxx2 . 0, 8 . 10001. 20005. 12212121xxxxxx返回前进491. 1488. 0090. 1783. 008. 183. 1200. 0250. 0333. 0250. 0333. 0500. 033

11、3. 0500. 000. 1321xxxx11160/4712/136/115/14/13/14/13/12/13/12/11321xxxx方程组：返回前进 006. 0843. 0683. 0001. 1999. 0001. 1111 xb解解改改变变为为若若右右端端项项01111166131413111241011321xxxx解返回前进方程组的性态讨论 病态、良态返回前进bbxxA)( bAbAxxAAxbbAxAxbbxAbAxbAx111 由bbAAxxbAxAxb111AA返回前进方程组的性态讨论（续2）xAAxAAxxAAxxAAxxxAAxxxAxAbxxAA-bAX1111

12、1 )()(0)()(xAAxAAxAAxAAx1111)1(移项返回前进AAAAAAAAAAAAxxAAAAA1111111101, 1,，则可推得：即假定很小时当AAAAxxAAAAA11 ) 1(,也即分母为上式右端实际上为充分小时当返回前进方程组的性态讨论续（3）摄动方程 )( bxAAxxAbbxxAAbAxbAxAAxAAxbAxAAAxAxA1111111:,两边取范数得左乘移项xbAAAxxAAx1111,移项后有：同除bAxxAAxb1有bbAAAAbbAAAA111上式返回前进bbAAAAAAxxAAA1111)( 1很小若bbAAAAkkAAk11 记bbAAkbbAAA

13、Axx1亦即：方程组的性态讨论续（4）返回前进矩阵的条件数 bbAAAAxx1AAAAxx1 bbAAxx11)(AAAcond1000100010001001,40000200010001. 2)(0001. 1111111AAcondA其中可见病态十分严重：对于例返回前进判断病态矩阵的几点参考1)det(112 ninjijaA返回前进利用条件数判断矩阵的性态举例748408611)( 1801803018019236303691211AAAcondA因为：中的：例121.11/1:11.3/12/11.2/1112nnnnnHHilbetA阵：是中的例使用主元素法求解也难以保证数值稳定性

14、。使用主元素法求解也难以保证数值稳定性。cond返回前进3 雅可比（Jacobi）迭代法 1)-(3 22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxanjijijnibxa1),2 , 1( nnnnnnininnnnnnnabxaxaxaxaxabxaxaxaxabxaxaxax/ ) (/ ) (/ ) (1122112222323121211113132121返回前进雅可比（Jacobi）迭代法（续）), 2 , 1(/ ), 2 , 1,( / niabgnjijiaabiiiiiiijij，其中4)-(3 ) , 2 , 1 ,

15、0( )() 1(kgBxxkk3)-(3 ), 2 , 1( )(11)(11)() 1(nibxaxaaxinijkjijijkjijiiki23/ ) (/ ) (/ ) ()(11)()(22)(11) 1(222)(2)(323)(121) 1(2111)(1)(313)(212) 1(1nnnknnnkiniknknknknnkkkknnkkkabxaxaxaxaxabxaxaxaxabxaxaxax返回前进Jacobi迭代法定义bDgADIB11 ,)1,1,1(),(2211122112211nnnnnnaaadiagDaaaaaadiagD，返回前进Jacobi迭代法定义（续

16、）bxULDxbxULDbAx)()( 则方程组)()( )( )( 5)-3( )( 11111111ULDULDIIULDDIADIBULDAbDgULDBbDxULDx则：实际上，若：即迭代矩阵：得到等价方程组：0000 0000 , 122311312121323121nnnnnnnnaaaaaaUaaaaaaL返回前进Jacobi迭代法举例4258321072210321321321xxxxxxxxx6)-(3 )42(51)832(101)722(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx7)-(3 4 . 83 . 82

17、 . 702 . 02 . 02 . 001 . 02 . 01 . 00 )() 1(kkxx其矩阵形式为：50.1170.1071. 94 . 83 . 82 . 78.43 . 82 . 702 . 02 . 02 . 001 . 02 . 01 . 00)8.4 , 3 . 8 , 2 . 7()1()2()0()1(gBxxgBxxT返回前进Jacobi迭代法举例 返回前进 收敛条件收敛条件 迭代格式收敛的充要条件是G的谱半径1。对于Jacobi迭代，我们有一些保证收敛的充分条件定理：若A满足下列条件之一，则Jacobi迭代收敛。 A为行对角占优阵 A为列对角占优阵 A满足ijiji

18、iaajiijjjaa1 jiiiijaa返回前进证明：)(1ULDGiiijijijiiijiaaaaG1max1max1 jiiiijiaaG证毕返回前进3222122321321321xxxxxxxxx设线性方程组：022101220 3222122)(2)(1) 1(3)(3)(1) 1(2)(3)(2) 1(1Bxxxxxxxxxkkkkkkkkk的迭代式：可由原方程组得到等价返回前进022101220000100220022001000111)(11ULDADIB也可利用迭代法收敛所以所以下面求特征方程：无法判定由于JacobiBBIB10)(00221122)det(,13213

19、返回前进3 高斯塞德尔(Gauss-Seidel)迭代法 :,)(,.,)(1)(2)(1) 1(1) 1(2) 1(1) 1(1) 1(2) 1(1) 1() 1(1) 1(2其迭代格式为迭代法塞德尔称为高斯据此想法构造的迭代法似解向量即可要存贮一个近可能收敛更快并且只需对应的旧分量进行迭代分量便立即用它取代如果每计算出一个新的因此更准确一些好更应比旧值这些新值情况下在收敛的从直观上看被利用这些前面的最新分量未已经算出时计算已经算出时即在计算加充分利用对已经算出来的信息未迭代过程中但在SeidelGaussxxxxxxxxxxxxJacobikikkkikkkikkkikk返回前进bUxxL

20、DbUxLxDxbDUxLxDxkkkkkkkk)()1()()1()1(1)()1(1)1()()( 其矩阵形式为：) (1)83() (1) (1)1(11)1(22)1(11)1(2)(2)(323)1(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaaxbLDUxLDxkk1)(1)1()()( :得等价的迭代格式ULDMSeidelGauss1)(法的迭代矩阵为：即：9)-(3 ), 2 , 1( )(1 111)() 1() 1(nibxaxaaxijnijikjijkji

21、jiiki其分量形式为返回前进Gauss-Seidel迭代法求解 10)-(3 5/ )42(10/ )832(10/ )722() 1(2) 1(1) 1(3)(3) 1(1) 1(2)(3)(2) 1(1kkkkkkkkkxxxxxxxxx返回前进求例2中的Gauss-Seidel法的迭代阵M的两种方法500/42500/110100/22100/ 1010/210/ 100002002105/ 150/ 1500/1110/ 1100/ 110/ 1)( 5/ 150/ 1500/1110/ 1100/ 110/ 1)(51110110)( 1111ULDMLDLDULDM则：其中：可利

22、用方法返回前进求例2中的Gauss-Seidel法的迭代阵M的两种方法续1)2)2(101(101)2(101)(3)(3)(2)(3)1(1)1(2kkkkkkxxxxxx11)-(3 100221001)(3)(21)(2kkkxxx)(,11)-(3 , )1(2)1(1不管常数将右端上标都化为代入分别以第一个式子及将第三个式子中右端的kxxkk 10722(3)(2)1(1）kkkxxx返回前进求例2中的Gauss-Seidel法的迭代阵M的两种方法续2)100221001)2(101(51 )(51)(3)(2)(2)(2)1(2)1(1)1(3kkkkkkkxxxxxxx12)-(

23、3 5004250011 )(3)(2)1(3kkkxxx5004250011010022100101021010M返回前进 收敛条件收敛条件 迭代格式收敛的充要条件是G的谱半径1。我们看一些充分条件定理：若A满足下列条件之一，则Gauss-Seidel 迭代收敛。 A为行或列对角占优阵 A对称正定阵返回前进证明：设G的特征多项式为)(sP，则ULDLDULDIGIPs)()()()(11ULDA为对角占优阵，则1时ULD )(为对角占优阵0)( ULD即0)(sP1 即1)(G证毕二种方法都存在二种方法都存在收敛性问题收敛性问题。 有例子表明：有例子表明：Gauss-Seidel法收敛时，法

24、收敛时，Jacobi法可能法可能不收敛；而不收敛；而Jacobi法收敛时，法收敛时， Gauss-Seidel法也可能法也可能不收敛。不收敛。返回前进两种迭代法举例3222122321321321xxxxxxxxx设线性方程组：022101220 3222122)(2)(1) 1(3)(3)(1) 1(2)(3)(2) 1(1Bxxxxxxxxxkkkkkkkkk的迭代式：可由原方程组得到等价返回前进例4（ Jacobi迭代法续）022101220000100220022001000111)(11ULDADIB也可利用迭代法收敛所以所以下面求特征方程：无法判定由于JacobiBBIB10)(0

25、0221122)det(,13213返回前进例4（ G-S迭代法续）法发散故，其特征方程：显然：由：SGMMIMULDMLDLD12)(, 2, 00)2(20032022)det(1|200320220000100220120011001)(120011001)(122011001)(321211返回前进两种迭代法说明200320220541(5) 2)32(2222341(4) 322221(3) 22(2) ) 1 ( 221)(3)(3)(2)(3)(2)1(3)(3)(2)(3)(3)(2)1(2)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1Mxxxxxxxxxx

26、xxxxxxxxxxxkkkkkkkkkkkkkkkkkkkkk）合起来可得迭代阵：）、（）、（由（）的右端得：）代入（）和（将（）的右端得：）代入（将（由迭代式：代入法求迭代矩阵。方法返回前进两种迭代法说明（续）的特征值。因而可由此式求解等价于因此由于因为：可避开求逆矩阵的特征值法迭代阵求：方法MULDMILDULDLDULDLDLDMILDULDM0)(det(0)det(0)det()(det()det()()()det()det()()( S-G 2111111返回前进4 松驰法 ), 2 , 1( )(1)() 1(11)() 1(nixaxabaxxnijkjijkjijijiii

27、kiki13)-(3 )(1 )(11)1()(nijkjijijkjijiiikixaxabax记), 2 , 1( )()()1(nixxxkikiki则：返回前进松驰法（续）迭代格式为：修正量改为松驰法是将得到的一修正量上加看作是在可以将,.)()()()1(kikikikixxxx)143(), 2 , 1()()()1(nixxxkikiki返回前进), 2 , 1 , 0 , 2 , 1( 15)-(3 )()(1 )(1)(11)1()()(11)1()()1(knixaxabaxxaxabaxxnijkjijijkjijiiikinijkjijijkjijiiikikibLDx

28、UDLDxbxUDxLDUxLxbxDDxUxLxbDxxkkkkkkkkkkkk1)(1)1()()1()()1()()1()()1(1)()1()()1()( :)1()()1 ()()1 (得到)1()(1UDLDM返回前进用SOR法解线性方程组（例3） 8 . 1202123232121xxxxxxx56.1)18.1(7.04.01)11(7.04.01)11(7.04.0)1 , 1 , 1( ),2, 1 ,0( )8.1(7.04.0)(7.04.0)1(7.04.0)153()1(3)1(2)1(1)0()1(2)(3)1(3)(3)1(1)(2)1(2)(2)(1)1(1xxxxkxxxxxxxxxxTkkkkkkkkkk代入，有：解：由迭代返回前进例 3 （续1）返回前进例 3 （续2）6001. 1,3996. 1,2000. 1)9(3)9(2)9(1xxx误差为比较与精确解,)6 . 1 , 4 . 1 , 2 . 1 ( Tx 3)9(10210004. 0 xx返回前进迭代法的收敛条件（续2）20是松驰法收敛的必要条件20 1)1 ()det( )1 ()1 (1)( )1 ()()det( 1)det(4)()det( ,22112211112121，即：因此有：且，而又因为：，松弛法收敛必有：，由定理因为：有特征值矩阵证明：设松弛法的迭代n