向量和矩阵的范数_病态方程组_解线性方程组的迭代法

1、3.4 向量和矩阵的范数n为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，向量和矩阵的范数。向量和矩阵的范数n在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用| x1-x2 |表示。向量和矩阵的范数n而在二维平面上，平面上任意一点P(x,y)到原点的距离用 表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。 推广到n维空间，则称为向量范数。|22OPyx22122121)()(|yyxxPP向量范数的范数。为向量则称，都有三角不等式：对任意奇次性：时

2、，当且仅当非负性：且满足法则对应于一非负实数按某一确定的设任一向量xxRRkkkRyxyxyxxxxxxxxnn|,)3;|,|)2;0|00|)1:|,|,3.4.1定义常见的向量范数|max|)(),()|(|),.,(12121211221121iniTniiniiTnxxxxxxxxxxxxxx设向量向量范数性质nnnnnRMmMmxxxRRxxxxxxyxyxyx|,| ,|R3,.,|,2121使得则必存在两正数中定义的任意两种范数对性质的一致连续函数。是分量则向量范数设性质。有对任意性质，向量范数性质等价性质：niiininiixxxnnnnnxxxxxxxxxxx1111211

3、1|max|1|1:|)3|)2|1) 1例如向量的收敛性*)(*)(*2*1*)()(2)(1)()(|0|limlim,),.,2 , 1(lim),.,(,.,.),2 , 1(3.4.2xxxxxxxxxxxkkkkkkikiknTnTknkkkknnixxRxxxxxxkR收敛到依范数则称向量序列如果有记作依次收敛到则称向量序列满足如果存在其中中一向量序列设定义),.2 , 1(lim0maxlim0|lim|,.)2 , 1(1 . 4 . 3*)()(1*)(*)(nixxxxkikikikinikkkkkxxxxxx）（事实上由。收敛到数依范的充分必要条件是坐标收敛到依向量序列

4、定理3.4.2 矩阵范数的一种范数。为则称，相容性：三角不等式：，奇次性：时，当且仅当非负性且满足应于一非负实数若按某一确定的法则对设任意定义nnnnnnnnRARBABAABRBABABARkAkkAAAAARA|,)4;,|,|)3;|)2; 0|00|:|) 1:|,|,3 . 4 . 3相容范数是相容的。与此向量范数则称该矩阵范数如果的一种范数和分别为设定义|,|,|4 . 4 . 3xAxAAxRRAxnnn算子范数且称其为算子范数。上的矩阵范数为则定义向量范数上并在设定理,|max|max|,|,2 . 4 . 31|0nnxxnnnnRAxxAxAxRRARx算子范数。只有可能，

5、因为则若显然成立，定义的四个条件。所以下面只要验证范数的一个对应法则。到定义了所以上一定能达到最大值在有界闭集的连续性知，证明：由向量范数0, 00|, 0|0|max|) 1|1|0AAAAARRAAAAxxxxxxxxxnn|)|(|)(|max|) 3|max|max|)2000 xxxxxxxxxxxxxxxBABABABARAAAAAkAkkAkAnxxx于是，则由算子范数1|max|,|)(|max|)(|010 xxIxIIRBAABBAxxBABABAxxBAnnx则为单位矩阵中任何矩阵算子范数对推论。同理可证即有所以对常见的矩阵范数njijniTniijnjpnnnnnija

6、AAAAaApRRaAxx11max2111|max|)(|2|1), 2 , 1(,)(3 . 4 . 3max范数：范数：范数：相容的矩阵范数是则于向量范数，设矩阵定理常见的矩阵范数。则非奇异又若则为对称矩阵设推论里德范数。为矩阵的谱范数或欧几为矩阵的行范数，为矩阵的列范数，一般称范数：|)(|,|,)(|,)(1min21max22121112AAAAAAAAAaAFnjniijF对称矩阵范数|)(|)(|)()(0,)(| )(| )(|)()(|1min1max211 -1max22max2maxmax22AAAAAAAAAAAAAAAATT得由非奇异，则又因为所以有知证明：由例题5

7、4)2() 1(2|844. 4466.23|534. 1,466.2301710108|17101084212412264|2| |,1|2max|54| 1| |,2|2max|:|), 2 , 1(|,42121 . 4 . 32122222211FTTFpAAAAIAAAAApAA。，故解得由因为解及求设矩阵例3.4.3 矩阵的谱半径和矩阵序列收敛性关系。的任何一种范数有某种但可能与的一种范数不是的谱半径矩阵的谱半径。为矩阵则称征值的特为矩阵设定义AAAAAAA,.,n),(iinii,)(|max)(,215 . 4 . 31例题33)(33,3304212|421221AAIA所以

8、。特征值得：解：由的谱半径。求矩阵谱半径和矩阵序列的收敛性。的任意性，有由，故有由于则的任一特征对，即为矩阵）设（证明。则若的任意一种算子范数为这里则设定理AAAAAAAAAAAAAAARAxxxxxxxxTnnmax)(0,1|)(,)2(;|,|)() 1 (,4 . 4 . 32)(,5 . 3 . 3|)(5| ,844. 4|, 6| , 5| , 33)(,4212)(| )(|)2(*22max2AARAAAAAAAAAAAAAAnnpFT，满足则必存在算子范数为任意指定的小正数，设定理。，所以显然。，故因为矩阵序列的收敛性。收敛于依范数则称矩阵序列如果记作收敛到矩阵则称矩阵序列

9、如果及矩阵设矩阵序列定义AAAAAAAAnjiaaaAkaAkkkkkkijkijknnijnnkijk|0|limlim,),.,2 , 1,(lim,)(),.,2 , 1()(6 . 4 . 3)()(。的充分必要条件是则设定理。收敛于矩阵依范数的充分必要条件是收敛到矩阵，矩阵序列与向量序列收敛性类似1)(0lim,6 .3.4),.,2 , 1(AkAkRAAAAnkAnnkk3.5 病态方程组与矩阵的条件数。该方程组的精确解为解什么样的变化解将产生项有微小扰动试分析系数矩阵和右端设线性方程组例Txxx) 1 , 1 (?,97. 199. 198. 099. 099. 011 . 5

10、 . 3213.5.1 病态方程组与扰动方程组的误差分析TxxxxxxxA)5 .48,50(97. 198. 099. 099. 199. 00001. 197. 199. 198. 099. 099. 00001. 10000001. 0)1(212121，解得所以即动设系数矩阵有微小的扰病态方程组与扰动方程组的误差分析Txbxx)99. 0,97. 2(9701. 19899. 198. 099. 099. 010001. 00001. 0)2(21解得则若右端有微小变动病态方程组与扰动方程组的误差分析T)3(21)005.148, 5 .148(0197. 19989 . 198. 0

11、99. 099. 00001. 1,xbxxAbA解得则扰动若同时对病态方程组与扰动方程组的误差分析。）（，）（；）（现计算相对误差：，005.149|3;99. 1|105|25 .49|105|1321)3()2(5)1(5xxxxbxxxxxAAA,i(i)(i)病态方程组与扰动方程组的误差分析样的方程为病态方程。称这解发生很大的变化有微小变化时阵和右端项显然上述方程在系数矩,病态方程组n扰动方程 由于计算机字长限制，在解AX=b时，舍入误差是不可避免的。因此我们只能得出方程的近似解 。 是方程组（A+A）x=b+ b (1) xx 在没有舍入误差的解。称方程（1）为方程Ax=b的扰动方

12、程。其中A， b为由舍入误差所产生的扰动矩阵和扰动向量。当A， b的微小扰动，解得（1）的解与Ax=b的解x的相对误差不大称为良态方程，否则为病态方程。扰动方程组的误差界。所以得又因为从而有由既有一个扰动产生则解有一个小的扰动中设，bbxxxbbxbxbxbbxxxxbbbxAAAAAAAA111|)() 1 (,。所以得从而有由既有一个扰动产生则解有一个小的扰动中设，AAAAAAAAAAAAAAxxxxxxxxbxbxxxxbx111|)()()2(,。时得当从而即有由既有一个扰动产生则解都有一个小扰动时和中设，)(1|1|)()()3(11111111,AAAAAAAAAAAAAAAAAA

13、AAAAAAAAbAAbbxxxbxxxbxxxbxbxbbxxxxbx|)(1)(|0|)(|0|)|(|)(1)(|,|)(, 1|,)(1 . 5 . 311AAAAAcondAcondxxbbbAcondxxAbbAAAAAcondAcondxxAAAcondAAAAxxxbAxxRAbbxnn时当时当则如果的解是扰动方程组精确解。的是方程组且非奇异。设定理3.5.2 矩阵的条件数.)(;AAAACond(A)RA1 . 5 . 32121 -bx的谱条件数关于方程组为矩阵称的条件数关于线性方程组为矩阵为非奇异矩阵，称设定义bAxAAAAKnn为病态方程组。称解的相对误差也大，则大时如

14、果谓良态方程组；的相对误差也小，则称解相对较小时如果与条件数相关解的相对误差直接线性方程组bAxAbAxAbAx,)cond(,)(cond,矩阵的条件数的性质。且为正交矩阵性质。其中则性质为非零常数。性质。性质)()()(, 1)(,4| )(|,)(|,|)(3)(cond)(cond21)(cond1minmax11AKAPKPAKPKPAAAkAAcAcAAnnT相对误差的事后估计n定理3.6.3 误差越小。越小误差越大；则。则残余向量的解，记是扰动方程组精确解，的是方程组且非奇异设,)(|, 1)(|)(|)(|)(|)(1)()1 (,AcondxxAcondbxrAcondxxb

15、xrAcondxAbxrxxxbAxxRAnn例题是病态方程。所以方程由于因为系数矩阵例bAxAkAAn1396010005. 098025. 1|)()(cond98. 099. 099. 011 . 5 . 3123.6 解线性方程组的迭代法fGxx。RRRAbAxxbbxnnnn写成等价方程组将类似非线性方程迭代法有唯一解由线性方程组理论知式且且非奇异其中设线性方程组) 1 . 6 . 3(。) 1 . 6 . 3(0,) 1 . 6 . 3(*3.6.1 解线性方程组迭代法概述），（作任取初始向量.2 , 1 , 0.)()1()1()2()0()1()0(kGGGfxxfxxfxxx

16、kk解线性方程组迭代法概述的解。也是的解，同时为方程组即则或即是收敛的若向量序列bAxGGfxxxfxxxxxxxkkkkk*)(*)()(0|limlim解线性方程组迭代法概述。其中，所以即改写为则方程非奇异其中令唯一解设方程组综上所述bMfNMfGxxNMNMMNMAxxxbxxbxxn11T*2*1*,G)2 . 6 . 3()() 1 . 6 . 3(,),.,() 1 . 6 . 3(:解线性方程组迭代法概述的解。组为方程是收敛的，且则称迭代格式若的右端得代入方程任取初始向量) 1 . 6 . 3() 3 . 6 . 3(lim) 3 . 6 . 3(,.)2 , 1 , 0()2

17、. 6 . 3(),.,(*)()()1(0)0(2)0(1)0(xkGxxxxxfxxxkkkkTn3.6.2 Jacobi迭代法和Gauss-Seidel迭代法nnnnnnnnnnnnnnnnniibbbxxxaaaaaaxxxaaabbbxxxaaaaaaaaaniaA.0.0.0.) 1 . 6 . 3(.),.,2 , 1(02121212211122122112121212222111211将其改写成为非奇异矩阵且设Jacobi迭代法),.,2 , 1(/ )(,210.0.0211222111122222211111112njiijijiiJnnnnnnnnniaxabxGaba

18、babnxxxaaaaaaaaaanxxxfxx其分量形式得则Jacobi迭代法迭代法。称其为为：而迭代序列的分量形式其迭代序列Jacbi,.,2 , 1/ )(,.2 , 1 , 01)(1)()1(nijjiikjiji)(kikJkniaxabxkfxGx例题05251101010210110201015352111021210Jacbi1 . 6 . 3321JGxxx解：因为迭代矩阵为迭代法解线性方程组试用例例题T)11(T)0()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1321321)0000. 3 ,0000. 2 ,0000. 1 (11)0 , 0 , 0(,

19、.1 , 021 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 025 . 13 . 004 . 02 . 01 . 002 . 01 . 02 . 00 xxkxxxxxxxxxxxxxxxkkkkkkkkk次有迭代到第取其迭代格式原方程改写为Jacobi迭代法的矩阵形式bfJocbibxxbxxbxDULDGDULDULDULDULDaaaaaaaaaAJnnnnnnn1111111221212211, )()()(,)(0.0.00.00迭代矩阵为，因此所以即故有Jacobi迭代法的算法慢。算法的缺点：收敛速度。返回、停机；输出、如果、计算、输入初始向量、输入

20、3),.,2 , 1(5),.,2 , 1(|max4);,.,2 , 1(/ )(3);,.,2 , 1(2;),.,2 , 1(),.,2 , 1,(11, 1niyxniyxyniaxabynixnibnjiaiiiiiniiinijjjijiiiiijGauss-Seidel迭代法。得，步由第依此类推；得同理由步第；代入迭代公式得由步第；由迭代公式解得步第设初值迭代法进行修正对)1()0()1(1)1(3)1(2)1(1)1(3)0()0(3)1(2)1(1)1(2)0()0(2)1(1)1(1)0()0(2)0(1,.,.,3,.,21,.,Jacobinnnnnnxxxxxxnxx

21、xxxxxxxxxxxGauss-Seidel迭代法bfbxxbxxbxxxLDULDGLDULDULDULDknixaxabaxsskkkijnijkjijkjijiiiki1111)() 1() 1(111)() 1() 1()()(SeidelGauss)()()(,.)1 , 0(),.,2 , 1()(1，迭代矩阵为因此故有所以矩阵形式：由于故将迭代法改写成例题迭代法收敛速度快。显然，次得，迭代到第取初值由解：法求线性方程组用例SGxxxxxxxxxxxkkkkkkkkkT)6(T)0()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1)000. 3 ,000. 2

22、,000. 1 (6)0 , 0 , 0(24 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 0SeidelGauss1 . 6 . 3Gauss-Seidel迭代法的算法。停机；否则返回输出、如果；做、对、输入初始向量、输入3),.,2 , 1(|max4;) 3;)2/ )() 1,.,2 , 13);,.,2 , 1(2;),.,2 , 1(),.,2 , 1,(11, 1nixeyxxyeaxbyninixnibnjiaiiniiiiiiiinijjiiiiiij3.6.3 线性方程组迭代法收敛条件1)(),.,(,(1 . 6 . 3*)(T)0()0(2

23、)0(1)0(GxxxGAxxxfxxbxkn的充要条件是收敛到方程组的解所产生的解向量序列向量对任意的初始的迭代格式组线性方程迭代法收敛基本定理）定理迭代法的收敛条件不收敛。不能肯定即不是必要条件收敛。但该条件所以这是因为。收敛）所产生的序列则由式（若出一个充分条件。此我们给是一件很困难的事。因由于求1|, 1|)(3 .3.6, 1|)()()()(kkkxGxGGxGG迭代法的收敛条件迭代法收敛。；迭代法收敛迭代法收敛。；迭代法收敛由此得出SGGGSGGGSSJJ1|1)(Jacobi1|1)(Jacobi迭代法的误差估计)14. 6 . 3(|1|)13. 6 . 3(|11|1|,3

24、 .3.6, 1)0()1(*)()1()()1()(*)(*)(xxxxxxxxxxxxGGGGGGkkkkkkkk且有估计到方程组的解必收敛）产生的向量序列则迭代格式（有数如果对于任一种矩阵范推论迭代法的误差估计|1|)1()(*)(*)()()1(*)()()1(*)1(*)1(*)(*)1()(kkkkkkkkkkkkkkxxGGxxxxGxxGxxxxGxxGGxGxxxGGfxxfxx所以两式相减取范数，因为证明迭代法的误差估计)0()1()1()(*)()0()1(1)3()2(2)2()1()1()(|1|1|.|xxxxxxxxxxxxxxGGGGGGGkkkkkkkkkkk所以因为收敛的判别条件理。具有某些特性的判定定常给出系数矩阵很难求，因此，目前由于迭代矩阵的谱半径估计迭代次数。）为事前估计，是预先而式（的停机标准）为事后估计，是计算式（A14.3.6;13.3.6收