求解线性方程组的迭代解法

第四章第四章线性方程组迭代解法第四章目录第四章目录第四章第四章 方程组的迭代解法概述方程组的迭代解法概述),2,1,0()()1(kgMxxkk迭代解法概述迭代解法概述(续）续）1 向量序列与矩阵序列的极限向量序列与矩阵序列的极限xxxxxxxRxxxxkkkkkknTknkkk)()()()()()(2)(1)(lim,0lim,),(记为收敛于则称序列有：如果对任何向量范数都对向量序列设向量 向量序列与矩阵序列的极限（续）向量序列与矩阵序列的极限（续）),2,1(lim)()(nixxxRxRikiknkn当且仅当向量中的收敛于中的向量序列),2,1(lim ),2,1(0limmax010lim,1 )()()()(1)()()(nixxnixxxxxxxxnixxxxikikikikkjkjnjikikkk亦即由极限存在准则得：，有：而对任意的即：收敛于由定义证明AAAAAAnAnAkkkkkk)()()()(lim,0lim记为收敛于矩阵则称序列任何矩阵范数都有：阶方阵，如果对于为阶方阵序列，为设矩阵序列的收敛概念及定理),2,1,2,1(lim,)(),2,1)()()()()()(njniaaAAnAnaAkaAijkijkkkijkijk，收敛于且矩阵序列阶方阵均为则矩阵序列阶方阵均为设2 雅可比（Jacobi）迭代法 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(nibxaxaaxinijkjijijkjijiiki 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()(11111111ULDULDIIULDDIADIBULDAbDgULDBbDxULDx 则则：实实际际上上，若若：即即迭迭代代矩矩阵阵：得得到到等等价价方方程程组组：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(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其迭代格式为迭代法塞德尔称为高斯据此想法构造的迭代法似解向量即可要存贮一个近可能收敛更快并且只需对应的旧分量进行迭代分量便立即用它取代如果每计算出一个新的因此更准确一些好更应比旧值这些新值情况下在收敛的从直观上看被利用这些前面的最新分量未已经算出时计算已经算出时即在计算加充分利用对已经算出来的信息未迭代过程中但在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)(21211)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-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(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(nixaxabaxxnijkjijkjijijiiikiki 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(knixaxabaxxaxabaxxnijkjijijkjijiiikinijkjijijkjijiiikiki 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(1xxxxkxxxxxxxxxxTkkkkkkkkkk代代入入，有有：解解：由由迭迭代代8.1202123232121xxxxxxx例 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 xx5 迭代法的收敛条件及误差估计的谱。称为矩阵AAnini),(max)(211因此有：的谱是矩阵出由特征值的定义容易得),2,1)(,(,21kAAAAknkkk16)-(4 )()(kkAA 矩阵的谱半径（续）AxAxx017)-(4 )(AA xAAxxAxx相容性公式 的重要性说明AA)(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 *)(*)(*)(*194*lim)0()()0()()0()2(2)1()1()(*)(*MMnxxxxxMxxMxxMxxMgMxgMxxxgMxxxxxxnKkkkkkkkkkkkk有由定理必然有：维向量，因此上式成立为任意因为有于是），有：，由迭代公式（满足：则：，使得：维向量）设存在（19)-(4 ),2,1,0()()1(kgMxxkk1)()(Mxk充分必要条件收敛产生的向量序列迭代法的收敛条件（续1）收收敛敛。）产产生生的的向向量量序序列列这这表表明明：由由迭迭代代式式（，都都有有：所所以以，对对任任意意初初始始向向量量又又因因为为并并且且即即：记记为为有有唯唯一一解解方方程程组组维维向向量量于于是是对对任任意意因因而而有有的的特特征征值值不不是是矩矩阵阵则则若若反反之之1940*)(lim*)(lim*)(*)(*0lim *,)(,01,1)(,)()()0()()0()0()1()(kkkkkkkkkkxxxMxxxxxMxxMxxMgMxxxgxMIgnMIMM 收敛若条件下在定理)(1,4kxM迭代法的收敛条件（续2）20是松驰法收敛的必要条件20 1)1()det()1()1(1)()1()()det(1)det(4)()det(,22112211112121 ，即即：因因此此有有：且且而而，又又因因为为：松松弛弛法法收收敛敛必必有有：，由由定定理理因因为为：有有特特征征值值矩矩阵阵证证明明：设设松松弛弛法法的的迭迭代代nnnnnnnnnMaaaUDaaaLDUDLDMMMMM两种迭代法举例 3222122321321321xxxxxxxxx设设线线性性方方程程组组：022101220 3222122)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1Bxxxxxxxxxkkkkkkkkk的迭代式：可由原方程组得到等价例4（Jacobi迭代法续）022101220000100220022001000111)(11ULDADIB也可利用迭代法收敛所以所以下面求特征方程：无法判定由于JacobiBBIB10)(00221122)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(1Mxxxxxxxxxxxxxxxxxxxxxkkkkkkkkkkkkkkkkkkkkk）合起来可得迭代阵：）、（）、（由（）的右端得：）代入（）和（将（）的右端得：）代入（将（由迭代式：代入法求迭代矩阵。方法两种迭代法说明（续）的特征值。因而可由此式求解等价于因此由于因为：可避开求逆矩阵的特征值法迭代阵求：方法MULDMILDULDLDULDLDLDMILDULDM0)(det(0)det(0)det()(det()det()()()det()det()()(S-G 2111111直接用矩阵A判定敛散性),2,1()(1niaaaAnnijjijiiij满足：阶方阵若直接用矩阵A判定敛散性（续）51121012110A210121012A三种迭代法判定敛散性举例的的收收敛敛性性。讨讨论论用用三三种种迭迭代代法法求求解解，其其中中：组组设设有有线线性性方方程程 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迭迭代代法法求求解解的的收收敛敛性性。迭迭代代法法与与讨讨论论，其其中中：组组设设有有线线性性方方程程SGJacobiAbAx 14/34/34/314/34/34/31,迭代法不收敛。迭代法不收敛。所以所以因而因而中有一个根，中有一个根，在在所以所以因为因为所以下面求特征方程：所以下面求特征方程：无法判定无法判定由于由于JacobiBfffBIfBi,1max)()2,1(0)(,32121)2(,03249)1(032271627434343434343)det()(,13 06445649016316904343)det()(1|64456490163169043430000430043430143430143001)(11 MIfMULDM，其特征方程：，其特征方程：显然：显然：迭代法收敛。迭代法收敛。所以所以因此因此）（即即，SGBifi ,1650.014606330max)(14606330,0064276481)(223212 两点注释法均收敛。迭代法与，对方程组：为严格主对角占优阵显然，其中：序可得其同解方程组：但若交换两个方程的次这两种方法均不收敛。它们的谱半径分别为迭代法的迭代阵迭代法与分别为与SGJacobibxAAAbxAMBSGJacobiMBMBA10349,215)(,230)(,21503100,04/93/10049103两点注释（续）无无法法判判定定而而接接近近于于但但收收敛敛法法对对 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 ：次次数数，可可以以估估计计需需要要迭迭代代的的并并且且对对预预先先给给的的精精度度及及则则有有误误差差估估计计式式：收收敛敛于于若若，设设有有迭迭代代格格式式：定理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具体步骤为：具体步骤为：迭代改善法（续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.134723.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.03333.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迭代改善法（续5）003027.0000432.0002300.0003027.0000432.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 非线性方程组的解法 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：线性化的近似的线性方程组可得分展式展开后取其线性部处用多元函数在将的一组近似解是非线性方程组设 njkjjnknkknnjkjjknkknjkjjknkkxxfxxxfxxfxxxfxxfxxxf1)()()(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)(111knkknknnnknknknkkknnkkknkkknnkkxxxfxxfxxfxxfxxxfxxfxxfxxfxxxfxxfxxfxxfTknkkkkknnnnnnkkxxxxxxxxxfxfxfxfxfxfxfxfxfxFJacobixFxF),()()()()()(2)(1)()()(212221212111)()(矩阵（系数矩阵）：的称为向量函数其中次近似解。的第为非线性方程而以中并从求中再由方程组解出即可由方程组有唯一解非奇异则不为对给定的构成的行列式方程组。当系数矩阵所上述线性方程组称为10)(,)(0)1()()()1()()()()()1()()()()()()(kxFxxxxxxxxxxxxxxxxNewtonxNewtonxFxNewtonkkkkkkkikikiikiikikkkk)()()()()(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(01)0(1)0(2)0(10,)(xxxxxxxxxxxxxxxxxxxF两个方程情况下的Newton法举例5.025.0 18134 )0(32312221xxxxx求方程组例2221213231222124368)(,18134)(xxxxxFxxxxxF解4972512.025409846.000273224.000409836.0015625.0061875.032)0()0()1()0(2)0(1)0()0(2)0(1xxxxxxxx求解出6.2 最速下降法0)(0)()(,),()()()()()(0),(0),(0),(21122221221212211xxfxxxxxxfxfxfxfxxxxfxxxfxxxfiTnmiminmnn所有：的零点。反之也对，即零点即是模函数非线性方程组的显然其中构造模函数：对非线性方程组：最速下降法（续）)(minxnRx最速下降法的二维说明miixxfxx122121),(),(最快下降方向。函数处，就是点则：是负梯度方向记为：的值下降最快的方向此函数由多元函数微分知道：),(),(),(),(),(),(),(),(2121212211212122211121xxxxxxgxxgxxGxxgxxxgxxx),(),(:),(),(,),(1),(,0)0(2)0(1)1(2)1(1)1(2)1(1)0(2)0(1)0(2)0(121xxxxxxxxGxxxxGG使得找到一点一定可以沿出发）从初值这样：的值必定递减方向下降的则沿因此，若最速下降法的二维说明（续）为搜索方向。而称射线方向维搜索问题一维极值问题，称为一即：将上述问题转化为),()(min),(),(min),()(2)(10)(2)(12)(2)(2)(11)(10)1(2)1(1kkkkkkkkkkxxGxxgxxxgxxx即的值下降最多的点是使当然希望近似解如何求出新的点方向沿出发假定从,),(),(?),)(,),(,),(21)1(2)1(1)1(2)1(1)(2)(1)(2)(1xxxxxxxxGxxkkkkkkkk),(),(),(),(:),(),(,),(,2*2*121)1(2)1(1)2(2)2(1)2(2)2(1)1(2)1(1)1(2)1(1xxxxxxxxxxxxGxx的最小值点逼近这样继续下去，可逐步使得方向可找到点沿出发从然后最速下降法的二维说明续),(),()(2)(12)(2)1(2)(2)(11)(1)1(1kkkkkkkkxxgxxxxgxx