求解线性方程组的迭代解法ppt课件

1、第四章第四章线性方程组迭代解法第四章目录第四章目录第四章第四章 方程组的迭代解法概述方程组的迭代解法概述), 2 , 1 , 0( )() 1(kgMxxkk迭代解法概述迭代解法概述(续续1 向量序列与矩阵序列的极限向量序列与矩阵序列的极限xxxxxxxRxxxxkkkkkknTknkkk)()()()()()(2)(1)(lim,0lim,),(记为收敛于则称序列有：如果对任何向量范数都对向量序列设向量 向量序列与矩阵序列的极限续向量序列与矩阵序列的极限续 ), 2 , 1( lim)()(nixxxRxRikiknkn当且仅当向量中的收敛于中的向量序列), 2 , 1( lim ), 2

2、, 1( 0limmax010lim, 1 )()()()(1)()()(nixxnixxxxxxxxnixxxxikikikikkjkjnjikikkk亦即由极限存在准则得：，有：而对任意的即：收敛于由定义证明AAAAAAnAnAkkkkkk)()()()(lim,0lim记为收敛于矩阵则称序列任何矩阵范数都有：阶方阵，如果对于为阶方阵序列，为设矩阵序列的收敛概念及定理), 2 , 1, 2 , 1( lim,)(), 2 , 1)()()()()()(njniaaAAnAnaAkaAijkijkkkijkijk，收敛于且矩阵序列阶方阵均为则矩阵序列阶方阵均为设2 雅可比Jacobi迭代法

3、1)-(4 22112222212111212111 nnnnnnnnnnbxaxaxabxaxaxabxaxaxanjijijnibxa1),2 , 1( nnnnnnininnnnnnnabxaxaxaxaxabxaxaxaxabxaxaxax/ ) (/ ) (/ ) (1122112222323121211113132121雅可比Jacobi迭代法续), 2 , 1(/ ), 2 , 1,( / niabgnjijiaabiiiiiiijij，其中4)-(4 ) , 2 , 1 , 0( )()1( kgBxxkk3)-(4 ), 2 , 1( )(11)(11)() 1(nibxax

4、aaxinijkjijijkjijiiki 24/ ) (/ ) (/ ) ()(11)()(22)(11) 1(222)(2)(323)(121) 1(2111)(1)(313)(212) 1(1 nnnknnnkiniknknknknnkkkknnkkkabxaxaxaxaxabxaxaxaxabxaxaxaxJacobi迭代法定义bDgADIB11 ,)1,1,1(),(2211122112211nnnnnnaaadiagDaaaaaadiagD，Jacobi迭代法定义续bxULDxbxULDbAx)()( 则方程组)()( )( )( 5)-4( )( 11111111ULDULDII

5、ULDDIADIBULDAbDgULDBbDxULDx 则则：实实际际上上，若若：即即迭迭代代矩矩阵阵：得得到到等等价价方方程程组组：0000 0000 , 122311312121323121nnnnnnnnaaaaaaUaaaaaaLJacobi迭代法举例 4258321072210321321321xxxxxxxxx6)-(4 )42(51)832(101)722(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1 kkkkkkkkkxxxxxxxxx7)-(4 4 . 83 . 82 . 702 . 02 . 02 . 001 . 02 . 01 . 00 )()1(

6、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(gBxxgBxxTJacobi迭代法举例 :,)(,.,)(1)(2)(1) 1(1) 1(2) 1(1) 1(1) 1(2) 1(1) 1() 1(1) 1(2其迭代格式为迭代法塞德尔称为高斯据此想法构造的迭代法似解向量即可要存贮一个近可能收敛更快并且只需对应的旧分量进行迭代分量便立即用它取代如果每计算出一个新的因此更准确一些好更应比旧值这些新

7、值情况下在收敛的从直观上看被利用这些前面的最新分量未已经算出时计算已经算出时即在计算加充分利用对已经算出来的信息未迭代过程中但在SeidelGaussxxxxxxxxxxxxJacobikikkkikkkikkkikk3 高斯高斯塞德尔塞德尔(Gauss-Seidel)迭代法迭代法 高斯塞德尔(Gauss-Seidel)迭代法续1bUxxLDbUxLxDxbDUxLxDxkkkkkkkk)()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)(2121

8、1)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaaxbLDUxLDxkk1)(1)1()()( :得等价的迭代格式ULDMSeidelGauss1)(法的迭代矩阵为：即：9)-(3 ), 2 , 1( )(1 111)() 1() 1(nibxaxaaxijnijikjijkjijiiki其分量形式为Gauss-Seidel迭代法求解 10)-(4 5/ )42(10/ )832(10/ )722() 1(2) 1(1) 1(3)(3) 1(1) 1(2)(3)(2) 1(1 kkkkkkkkkxxxxxxxxx求例2中的Gauss

9、-Seidel法的迭代阵M的两种方法500/42500/110100/22100/ 1010/210/ 100002002105/ 150/ 1500/1110/ 1100/ 110/ 1)( 5/ 150/ 1500/1110/ 1100/ 110/ 1)(51110110)( 1111ULDMLDLDULDM则：其中：可利用方法求例2中的Gauss-Seidel法的迭代阵M的两种方法续1)2)2(101(101)2(101)(3)(3)(2)(3)1(1)1(2kkkkkkxxxxxx 11)-(4 100221001)(3)(21)(2kkkxxx )(,11)-(4 , )1(2)1(

10、1不不管管常常数数将将右右端端上上标标都都化化为为代代入入分分别别以以第第一一个个式式子子及及将将第第三三个个式式子子中中右右端端的的kxxkk 10/)2(3)(2)1(1kkkxxx 求例2中的Gauss-Seidel法的迭代阵M的两种方法续2)100221001)2(101(51 )(51)(3)(2)(3)(2)1(2)1(1)1(3kkkkkkkxxxxxxx 12)-(4 5004250011 )(3)(2)1(3kkkxxx 5004250011010022100101021010M4 松驰法 ), 2 , 1( )(1)()1(11)()1(nixaxabaxxnijkjijk

11、jijijiiikiki 13)-(4 )(1 )(11)1()( nijkjijijkjijiiikixaxabax记记), 2 , 1( )()()1(nixxxkikiki则：松驰法续迭代格式为：修正量改为松驰法是将得到的一修正量上加看作是在可以将,.)()()()1(kikikikixxxx)144(), 2 , 1()()()1( nixxxkikiki SOR法的迭代矩阵 ), 2 , 1 , 0 , 2 , 1( 15)-(4 )()(1 )(1)(11)1()()(11)1()()1( knixaxabaxxaxabaxxnijkjijijkjijiiikinijkjijijk

12、jijiiikiki bLDxUDLDxbxUDxLDUxLxbxDDxUxLxbDxxkkkkkkkkkkkk1)(1)1()()1()()1()()1()()1(1)()1()()1()( :)1()()1 ()()1 (得到)1()(1UDLDM用SOR法解线性方程组例3 56.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)154()1(3)1(2)1(1)0()1(2)(3)1(3)(3)1(1)(2)1(2)(2)(1)1(1xxxxkxxxxxxxxxxTkkk

13、kkkkkkk代代入入，有有：解解：由由迭迭代代8 . 1202123232121xxxxxxx例 3 续1例 3 续26001. 1,3996. 1,2000. 1)9(3)9(2)9(1xxx误差为比较与精确解,)6 . 1 , 4 . 1 , 2 . 1 ( Tx 3)9(10210004. 0 xx5 迭代法的收敛条件及误差估计的谱。称为矩阵AAnini),(max)(211因此有：的谱是矩阵出由特征值的定义容易得), 2 , 1)(,(,21kAAAAknkkk16)-(4 )()(kkAA 矩阵的谱半径续AxAxx017)-(4 )(AA xAAxxAxx相容性公式 的重要性阐明A

14、A )(18)-(4 )( AA2)(AA 1)(0limAAnAkk充要条件阶方阵，则：为设定理3续0lim 0limlim 12)(1)()184(02)(11)()( kkkkkkkkAAAAAAAAAA所所以以有有于于是是而而存存在在一一种种矩矩阵阵范范数数使使得得由由取取若若充充分分性性 1)( 0)(lim,)()(0)174()164(0lim20lim)( AAAAAAAkkkkkkkkk 所所以以有有于于是是由由极极限限存存在在准准则则有有及及而而利利用用有有由由定定义义若若必必要要性性5.2 迭代法的收敛条件 1)( 30lim0*)(lim*)(lim *)( *)( *

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

16、组维维向向量量于于是是对对任任意意因因而而有有的的特特征征值值不不是是矩矩阵阵则则若若反反之之1940*)(lim*)(lim*)(*)(* 0lim *,)(,01, 1)(,)()()0()()0()0()1()(kkkkkkkkkkxxxMxxxxxMxxMxxMgMxxxgxMIgnMIMM 收敛若条件下在定理)(1,4kxM迭代法的收敛条件续220是松驰法收敛的必要条件20 1)1()det( )1()1(1)( )1()()det( 1)det(4)()det( ,22112211112121 ，即即：因因此此有有：且且而而，又又因因为为：松松弛弛法法收收敛敛必必有有：，由由定定理

17、理因因为为：有有特特征征值值矩矩阵阵证证明明：设设松松弛弛法法的的迭迭代代nnnnnnnnnMaaaUDaaaLDUDLDMMMMM两种迭代法举例 3222122321321321xxxxxxxxx设设线线性性方方程程组组：022101220 3222122)(2)(1) 1(3)(3)(1) 1(2)(3)(2) 1(1Bxxxxxxxxxkkkkkkkkk的迭代式：可由原方程组得到等价例4 Jacobi迭代法续022101220000100220022001000111)(11ULDADIB也可利用迭代法收敛所以所以下面求特征方程：无法判定由于JacobiBBIB10)(00221122)

18、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(1Mxxxxxxxxxxxxxxxxxxxxxkkkkkkk

19、kkkkkkkkkkkkkk）合起来可得迭代阵：）、（）、（由（）的右端得：）代入（）和（将（）的右端得：）代入（将（由迭代式：代入法求迭代矩阵。方法两种迭代法阐明续的特征值。因而可由此式求解等价于因此由于因为：可避开求逆矩阵的特征值法迭代阵求：方法MULDMILDULDLDULDLDLDMILDULDM0)(det(0)det(0)det()(det()det()()()det()det()()( S-G 2111111直接用矩阵A断定敛散性),2, 1( )(1niaaaAnnijjijiiij满足：阶方阵若直接用矩阵A断定敛散性续51121012110A210121012A三种迭代法断定

20、敛散性举例的的收收敛敛性性。讨讨论论用用三三种种迭迭代代法法求求解解，其其中中：组组设设有有线线性性方方程程 12/12/12/112/12/12/11,AbAx均收敛与松驰法迭代法所以为对称正定阵且其各阶主子式为称阵因为这里)20(,0012/12/11, 1,321SGAAAAAA例 5 (续迭代法不收敛。因而，其特征方程：对任何一种范数显然JacobiBBIBULDADIB1)(, 1,210) 1()21(43412/12/12/12/12/12/1)det(1,)(02/12/12/102/12/12/103212311 04/34/34/304/34/34/30B迭代法求解的收敛性

21、。迭代法求解的收敛性。迭代法与迭代法与讨论讨论，其中：其中：组组设有线性方程设有线性方程SGJacobiAbAx 14/34/34/314/34/34/31,迭代法不收敛。迭代法不收敛。所以所以因而因而中有一个根，中有一个根，在在所以所以因为因为所以下面求特征方程：所以下面求特征方程：无法判定无法判定由于由于JacobiBfffBIfBi, 1max)()2, 1(0)(,32121)2(, 03249)1(032271627434343434343)det()(,13 06445649016316904343)det()(1|644564901631690434300004300434301

22、43430143001)(11 MIfMULDM，其特征方程：，其特征方程：显然：显然：迭代法收敛。迭代法收敛。所以所以因此因此）（即即，SGBifi , 1650. 014606330max)(14606330, 0064276481)(223212 两点注释法均收敛。迭代法与，对方程组：为严格主对角占优阵显然，其中：序可得其同解方程组：但若交换两个方程的次这两种方法均不收敛。它们的谱半径分别为迭代法的迭代阵迭代法与分别为与SGJacobibxAAAbxAMBSGJacobiMBMBA10349,215)(,230)(,21503100,04/93/10049103两点注释续无无法法判判定定

23、而而接接近近于于但但收收敛敛法法对对 1649364864916943)11613(1161316941:16/164/904/116/9004/30 04/104/104/304/304101430341MMSGMBA5.3 误差估计 22)-(4 ln)1(ln21)-4 ( 1* 20)-(4 1*, 1)0()1()0()1()()1()()()()()1(MxxMkkxxMMxxxxMMxxxxMgMxxkkkkkkkk ：次次数数，可可以以估估计计需需要要迭迭代代的的并并且且对对预预先先给给的的精精度度及及则则有有误误差差估估计计式式：收收敛敛于于若若，设设有有迭迭代代格格式式：定

24、理5续932.124 .8)4 .0(10ln4 .0ln14 .8, 4 .04 .83 .82 .7 ,000 ,02 .02 .02 .001 .02 .01 .004)0()1()1()0(kxxBxxB迭代改善法 无论是用直接法还是用迭代法求得病态方程组的计算解, 当精度不理想时， 可以运用迭代改善的方法进展处置，即运用迭代改善法 此法常用于解不非常严重病态的方程组。 迭代改善法：迭代改善法： 2也可与直接法结合进展直接求解。 1可用于改善已求得的近似争的精度， 1. 对Ax=b 用列主元消元法，分解法均可，分解法选主元最好。 即：即： )1(xyUxbLyLUA详细步骤为：详细步骤

25、为：迭代改善法续1 2. 求x(1)的修正量z(1) ：先求 )1()1(Axbr然后由)1()1(zzyUzrLy LUA 利利用用即可即可的解。 而)1()1()2(zxx就是近似解x(1)的改良解. 这是由于有：这是由于有： bAzrbAzAxzxAAx )1()1()1()1()1()1()2()( 3. 可继续下去：再求;)3()2()2(xzr)1()1(rAz 求求出出迭代改善法续2例例1：002755853. 0006324242. 00068525. 2446949. 1446949. 1012671. 121xx14 .11508)(01.94341.134741.1347

26、23.19261ACondA与准确解)1()9786. 6,9773. 9(xxTTx)9059. 5,4448. 8(*假设用Gauss消元法求解取五位有效数字比较，相差太远。迭代改善法续3假设用迭代改善法：假设用迭代改善法： K )(kx)(kr 0 0 0 0 0 1 9.9773 6.9786 0.0063242 0.0027559 2 8.1665 5.7110 0.00028017 0.0015411 3 8.4954 5.94130.000127740.0038975 4 8.4356 5.89940.000240940.000072077 0012000. 02500. 033

27、33. 02500. 03333. 05000. 03333. 05000. 00000. 13213xxxH迭代改善法续4例例2 Hilbert 阵阵 较准确的解为Tx)30.30,32.36,062. 9(*Tx)00.31,04.37,190. 9()1(假设用列主元法求得近似解：对x(1)用迭代改善法进展改良：先求30.3032.36062. 92000. 02500. 03333. 02500. 03333. 05000. 03333. 05000. 00000. 1001)1 ()1 (Axbr迭代改善法续5003027. 0000432. 0002300. 0003027. 00

28、00432. 0002300. 1001)1 ()1 (Axbr用Doolittle分解法求解 )1()1(rAzTz)7122. 0,7320. 0 ,1309. 0()1(x(3)显然已具有四位有效数字显然已具有四位有效数字Tzxx)29.30,31.36,059. 9()1()1()2(TAxbr)0001353. 0 ,0001230. 0 ,0003430. 0()2()2()2()2(rAz Tz)01289. 0 ,01349. 0,0027792. 0()2(Tzxx)30.30,32.36,062. 9()2()2()3(可计算可继续求： 并由Dolittle分解法解 可得6

29、 非线性方程组的解法 0),(0),(0),(21212211nnnnxxxfxxxfxxxf非线性方程组的解法续nixxxgxnii,2,1 ),(21, 2 , 1 . 0 ;, 2 , 1 ),( )()(2)(1) 1(knixxxgxknkkiki并建立迭代格式6.1 Newton法 )()()()(2)(1)()(2)(1)(0)(),()(0)(),(kiikiTknkkTknkkxxxxFTaylorxxxxFxFxxx：线性化的近似的线性方程组可得分展式展开后取其线性部处用多元函数在将的一组近似解是非线性方程组设 njkjjnknkknnjkjjknkknjkjjknkkxx

30、fxxxfxxfxxxfxxfxxxf1)()()(211)(2)()(2)(121)(1)()(2)(110),(0),(0),()()()()(:)(! 2)()()()()(0)(12kkkkkkkkkkkkkxfxfxxxxxxfxfxxxfxxxfxfxfxxfNewtonxf 取线性部分展开：在将法：的可对照求),(),(),()()(2)(1)()(22)(11)()(2)(12)(2)(222)(112)()(2)(11)(1)(221)(111knkknknnnknknknkkknnkkknkkknnkkxxxfxxfxxfxxfxxxfxxfxxfxxfxxxfxxfxxf

31、xxfTknkkkkknnnnnnkkxxxxxxxxxfxfxfxfxfxfxfxfxfxFJacobixFxF),()()()()()(2)(1)()()(212221212111)()(矩阵（系数矩阵）：的称为向量函数其中次近似解。的第为非线性方程而以中并从求中再由方程组解出即可由方程组有唯一解非奇异则不为对给定的构成的行列式方程组。当系数矩阵所上述线性方程组称为10)(,)(0)1()()()1()()()()()1()()()()()()(kxFxxxxxxxxxxxxxxxxNewtonxNewtonxFxNewtonkkkkkkkikikiikiikikkkk)()( )()()

32、(kkkxFxxF可写作向量形式样Newton法的详细做法小控制。相对误差充分也可用前后两次迭代的较大时当，则可停止迭代。若若,max . 2),(max)( . 1)()() 1(1)() 1() 1() 1(2) 1(11) 1(kkikinikkknkkinikxxxxxxxxfxF两个方程情况下的Newton法 )()()(0)( )(),(),(0)()(),(0)()(),(, 0),(0),()0()0()0()0(2)0(1)0(2)0(1)0()0(22122111)0()0(2)0(12)0(222)0(112)0(2)0(11)0(221)0(111)0(2222)0(1112)0(2)0(12)0(2221)0(1111)0(2)0(11)0(2)0(1)0(2)0(1212211)0(xFxxFffxxxFxFxfxfxfxfxFxxfxxfxxfxxfxxfxxfxxxfxxxfxxfxxxfxxxfxxfTaylorxxxxxxfxxfxxT若取线性部分可得：展式展开附近用二元在初值可将非线性方程组给定对，可继续迭代作为，以再由：也可直接求解出：的逆矩阵的方法求解，可用求)1(2)1(121)0(2)0(22)0(1)0(11)0(22)0(2)0(