线性方程组的数值解法

1、第二章线性方程组的数值解法n线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111n对于线性方程组Ax=b,其中若系数阵A非奇异，则方程组有唯一解. 1112111212222212,nnnnnnnnaaaxbaaaxbaaaxbAxb计算机上求解线性方程组的有效数值方法n直接法 直接解法是解线性方程组的重要方法. 它是指通过有限步的算术运算求出精确解的方法（若计算过程没有舍入误差）. 其基本思想是通过等价变换将线性方程组化为结构简单、易于求解的形式，从而求解. n迭代法 迭代法的基本思想是用某种极限过程逐次逼近方程组的解的方法，是解线

2、性方程组的重要方法.它具有占有储存单元少、程序设计简单、原始系数矩阵在计算过程中不变的优点，但需考虑收敛性和收敛速度问题.2.1 向量、矩阵的范数向量的范数n设Rn为实n维向量空间, Cn为复n维向量空间,记Kn为Rn或Cn , K为实数域R或复数域C.n定义定义若Kn上任一向量x，对应一个非负实数x ，满足如下条件（）非负性：|x|0 且 |x|=0 x=0 （）齐次性：|x|=|x| (K) （）三角不等式 |x+y|x|+|y| (x,yKn) 则称x为向量x的一种范数. 常用的向量范数n设x=(x1,x2,xn)， 1-范数： 2-范数： -范数： p-范数11()nppipixx11

3、niixx12221niixx1maxii nx x矩阵的范数n记Knn为Rnn或Cnnn定义定义 若Knn上任一矩阵A=(aij)nn ,对应一个非负实数A ，满足以下条件:（）非负性： |A|0 且 |A|=0 A=0 （）齐次性：|A|=|A| (K) （）三角不等式： |A+B|A|+|B| (A,BKnn) （） |AB|A|B| (A,BKnn) 则称 A为矩阵A的一种范数. n例 对于实矩阵A=(aij)nn是一种矩阵范数,称为矩阵的Frobenius范数，简称矩阵的F范数.21211()nnijFijaA 考虑到矩阵范数总是与向量范数联系在一起的. n定义定义 对于给定向量范数

4、 和矩阵范数 ，如果对任何向量xKn和AKnn,都有不等式AxAx 成立，则称所给的矩阵范数与向量范数是相容的.n下面给出一种定义矩阵范数的方法，它是由向量范数诱导出来的相容范数. 定义定义 设xKn和AKnn ，且给定一种向量范数 ，称 或 为矩阵A的由向量范数x产生的从属范数或算子范数. 单位矩阵的任一种从属范数都为1.0maxXAxAx1maxxAAx由向量1-范数,2-范数, -范数产生的从属范数分别为n定理定理 设n阶方阵A ，则1-范数：2-范数： ，AH 是A的共轭转置-范数：111maxnijj niaA 11maxniji njaA 2()HA AA矩阵的谱半径n定义设n阶方

5、阵A的特征值为1,2,n ，则称 为A的谱半径（i为i的模）. 对于任意从属范数 ， (A)|A|但当A是正规矩阵，即A AH = AH A时， (A)=|A|2显然若A为实对称矩阵，则(A)=|A|21( )maxii nA 范数的有关定理n定理2.1(范数连续性定理) 设f(x)=|x|为Rn上任一向量范数, 则f(x)是x的连续函数.n定理2.2(范数等价性定理) 设|x|s , |x|t为Rn上任意两种向量范数, 则存在常数c1 ,c20，使得 c1|x|s|x|t c2|x|s ， xRnn定理2.3 向量序列xk收敛于x*的充分且必要条件是 |xk-x*|0, k 其中 是任一向量

6、范数.矩阵范数也有相应上述三个定理的结论例n x= (3,-1,5,8) ,求n解12,xxx1315817 x222223( 1)58993 11max 3 ,1, 5 , 88 xx例n 计算方阵 的各种常用范数n解 100024024A3131maxmax1,6,66Aijija 31131maxmax1,4,88Aijjia 1,AA21211()41nnijFijAaAHA的特征方程为(-1)(-8)(-32)=0所以(AHA)=32 从而 1001001000220240800440240032HA A2324 2A矩阵的条件数n设A为非奇异矩阵，称数 为矩阵A的条件数. n n条

7、件数与所取范数有关 ,因此有时详细记为1( )cond AAA11( )1condAAAAA1( )vvvcondAAA 解线性方程组的直接法 2.2 消去法Gauss消去法思想：Ax=bBx=d (其中B是上三角阵) 求解Bx=d Gauss消去法包括消元过程和回代过程两个环节（一）消元过程1111112111211111211(1)(1)(1)0222221222211(1)(1)(1)2,3,12()iinnnnannarrainnnnnnnnaaabaaabaabaaabaabaaab第一步A b122(1)2212211121311(1)(1)(1)(1)2223220(2)(2)(

8、2)3333223,4,(2)(2)(2)3()iinnanarrainnnnnaaaabaaabaabaab （ ）（ ）第二步A b211(2),11(21,11112111(1)(1)(1)(1)222221011(1)(1)(1),(1)(1)(1)()kkkki kikkkkknknkakkkkkakkknkrrai knkkknknnnaaaabaaabaabaab（）第步Ab 1(1)(1111211111(1)(1)(1)(1)(1)22221220(1)(1)(1)(1)1( )( )( )11111,( )( )( )1kkkkikikkkkkknkknkakkkkkkkk

9、knkakkkrrkkknkai knkkknknnnaaaaabaaaabaaabaabaab （）第 步()kkA b211(2)11(2111112111(1)(1)(1)0222211(1)(1)()nnnnnnnnnnnnnannnarrnnannnaaabaabab）第步Abn n对 k=1,2,(n-1) ，依次计算 (1)(1)( )(1)(1)( )(1)(1)/( ,1,2, )kkikikkkkkkijijikkjkkkiiikkmaaaam ai jkknbbm biiijijbbaa)0()0(,n（二）回代过程(1)(1)(1)1()/(,1,1)niiiiiijj

10、iij ixbaxain n 选列主元的Gauss消去法nGauss消去法能够进行到底的条件是各步的主元素 . 另外既使主元素 不为零，但如果主元素的绝对值很小，用它作除数，势必造成舍入误差的严重扩散,以致于方程组的解的精度受到严重影响,为此引入选主元的方法，选列主元的具体方法如下：(1)kkka(1)0kkkan对方程组Ax=b仍按x1,x2,的顺序依次消 元，只是在每一步消元前都增加一步按列选主 元的工作，如第k步消元前，就所 有 ，取绝对值最大者， 设 ,将第l个方程与第k个方程互换 位置，这样 成为第k步的主元素，然后进 行第k步消元. 每步消元都如此，最后再进行回 代过程，得出方程组

11、的解. (1)(,1, )kkak kn(1)(1)maxkklkkknaa (1)klka全选主元的Gauss消去法n对方程组Ax=b仍按x1,x2,的顺序依次消元，只是在每 一步消元前都增加一步全选主元的工作，如第k步消 元前，就所有 ，取绝对值最大者， 设 ，将第l个方程与第k个方程互 换位置，变元xs,xj互换位置，这样 成为第k步的主元 素，然后进行第k步消元. 每步消元都如此，最后再进行 回代过程，得出方程组的解. (1)( ,1, )kijai jk kn(1)(1)maxkklsijk i nkj naa (1)klsan选列主元的Gauss消去法能压制计算过程中舍入误差的增长

12、，减少舍入误差对计算结果的影响. 例n 利用Gauss消去法求解方程组Ax=b, 其中1212425327,2235112240Abn解 （1）消元过程用矩阵表示为2131413243(0)(0)2212312124121242532701121223510251712240001641212412124011210112100339003390016400077rrrrrrrrrr 第一步第二步第三步Ab(3)(3)Ab经三步消元后；原方程组化为同解的上三角形方程组A(3)x=b(3) . n（2）回代过程对方程组A(3)x=b(3) 自下而上按未知元xi的下标逆序逐步回代得原方程组的解为

13、x4=-1, x3=2, x2=-1, x1=2, 即x=(2,-1,2,-1) 例n 用选列主元素的Gauss法解下列方程组n解 消元过程用矩阵表示为1234123341518311151111631112xxxxn 2113141231181612334151831115123341518311151111611116311123111218311157100153371717310618186375102662rrrrrrrr 2选主元第一步消元选主元4218311153751026627171731061818671001533rr 324342721()()9252318311151

14、8311153751375100266226625085050850000027279272799114351400000025993rrrrrr 第二步消元第三步消元n得同解上三角方程组n回代求解得x4=0,x3=3,x2=2, x1=1, 即x=(1,2,3,0) 12342343441831537512662508502727991025xxxxxxxxxx 例n设系数矩阵A=(aij)nn的元素a110 . 经过Gauss消去法一步以后A化为其中为n-1维列向量，A2为n-1阶方阵. 证明：(1)若A为对称矩阵，则A2也为对称矩阵；(2)若A为严格对角占优矩阵，则A2也是严格对角占优矩

15、阵；(3)若A为对称的严格对角占优矩阵，则选列主元Gauss消去法就是（顺序）Gauss消去法. 1120TaA n证 (1)经Gauss消元一步后，A2的元素为n由于A对称，故 aij=aji ，从而n因此A2为对称矩阵. (1)1111( ,2,3, )iijijjaaaai jna1(1)(1)1111111jiijjijjiijiaaaaaaaaaan(2)设A是（按行）严格对角占优矩阵（按列严格对角占优可类似考虑） ，即 1(1,2, )niiijjj iaain(1)1111222211111111111221111111111121111(1)1111()(0)(2,3nnnni

16、iijijjijjjjjjj ij ij ij innniiijijiiijjjjj ij ij iniiiijiiiijiiiiiiaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaia, )n因此A2是严格对角占优矩阵. n(3)由于A是对称的严格对角占优矩阵所以因而即第一步消元a11为主元素. 由(1)、(2)知A2是对称的严格对角占优矩阵. 记111112,(2,3, )njiijaaaain1111(2,3, )iiaaain(1)(1)(1)222322(1)(1)(1)23nnnnnaaaaaaAn则第二步消元 为主元素. 依次类推，选列主元Gauss消去法就是（

17、顺序）Gauss消去法. (1)22a 2.3 矩阵三角分解法 nA1=L1-1A, b1=L1-1bnA2=L2-1A1=L2-1L1-1A, b2=L2-1b1=L2-1L1-1b nAn-1=Ln-1-1L2-1L1-1A, bn-1=Ln-1-1L2-1L1-1bn记记U=An-1=Ln-1-1L2-1L1-1A A=L1L2 Ln-1U= LU 12211101010001nmmL111101001001nnmL211131111010001nmmm L2112131321211111nnnnnmmmmmmLL LLn如果A的所有顺序主子式均不为零，则A可唯一分解为 A=LU 其中L

18、为单位下三角阵，U为上三角阵. 以下讨论中都假设上述条件成立.求解Ax=b求解LybUxyDoolittle分解法(直接三角分解法) ni）分解 A=LU, 其中L为单位下三角阵，U为上三角阵.即利用矩阵运算比较两边得其分解公式:对k=1,2,3,n，其中111211112121222212221212100100100nnnnnnnnnnnnaaauuuaaaluuaaalluALU1111(,1, )()(1,2, )kkjkjkrrjrkikikirrkkkrual ujk knlal uuikkn010求解Ax=b求解nii）求解方程组Ly=b，即n其计算公式为n其中11(1,2, )

19、kkkkrrrybl ykn010nnnnbbbyyylll21212121101001LybUxyniii）求解方程组Ux=y，即n其计算公式为n其中 1()(,1,2,1)nkkkrrkkr kxyu xukn n 10nnnnnnnnyyyxxxuuuuuu212122211211000nDoolittle分解法的存储可利用原系数矩阵的存储单元，存储形式111212122212nnnnnnuuuluulluA例用Doolittle分解法求解方程组n解 方程组的系数矩阵和右端项分别为12341234123412342426949615232691822615184047xxxxxxxxxx

20、xxxxxx242649615269186151840A9232247bn（1）分解A=LU，即 n（2）求解Ly=b，即n解得y=(9, 5,3,-1)12426211231213633211A123419212312122332147yyyyn求解Ux=y ，即n由公式解得x=( 0.5 ,2,3,-1)123424269123536311xxxxCrout分解法ni）记D=diag(u11,u22,unn), 其中 是下三角阵，是单位上三角阵.此分解是惟一的.利用矩阵运算比较两边得其分解公式: 对k=1,2,3,n，111112112121222221221212001010 001nn

21、nnnnnnnnnnlaaauuaaaullaaalllALU1111(,1,2, )()/(1,2, )kikikirrkrkkjkjkrrjkkrlal uik kknual uljkkn11 ()(),ALULD D ULU LLD UD UL求解Ax=b求解nii）求解方程组 ，即n其计算公式为n其中11()/(1,2, )kkkkrrkkrybl ylkn010111122212212000nnnnnnlybybllyblllLybLybUxyniii）求解方程组x=y，即n其计算公式为n其中 1(,1,2,1)nkkkrrr kxyu xkn n 10nn1112122210100

22、1nnnnxyuuxyuxynCrout分解法的存储可利用原系数矩阵的存储单元，存储形式111212122212nnnnnnluullulllAn例 用系数矩阵A的Crout分解求解线性方程组Ax=b. 其中 6211624101,1141510135Abn分解 ，即n求解方程组 ，得n求解方程组 ，得 ALU61111366102113015102371931000137191911000131074ALyb9461, 110 37yUx=y(1, 1,1, 1)xCholesky分解法(平方根法)ni）记D=diag(u11,u22,unn), = D-1U A=LU=(LD)(D-1U)

23、=LD (分解惟一)其中L是单位下三角阵，是单位上三角阵.n如果A是对称正定的，则=L,其中 是下三角阵1122()()ALDLLDLDLLL称为矩阵的Cholesky分解.利用矩阵运算比较两边得其分解公式: 对k=1,2,3,n，其中1112111112112122221222221212000000nnnnnnnnnnnnnnaaallllaaallllaaallllALL12 1/2111()()/(1,2, )kkkkkkrrkikikir krkkrlallal llikkn010求解Ax=b求解nii）求解方程组 ，即 其计算公式为其中111122212212000nnnnnnyb

24、lybllyblllLy=b11(1,2, )kkkkrrkkrybl ylkn010rTLybL x=yniii）求解方程组 ，即 其计算公式为其中TL x=y1()(,1,2,1)nkkrkrkkr kxyl xlkn n 10nr n 111121122222000nnnnnnxylllxyllxyln平方根法是用于解系数矩阵为正定矩阵的线性方程组.n例 用平方根法（Cholesky分解）解方程组解 由于系数矩阵A对称正定，故一定有分解形式其中 为下三角阵. （1）对系数矩阵进行Cholesky分解 ，即L1233235220330127xxx TALLTA LL111121312122

25、2232313233333232203012llllllllllll由公式得解方程组 ，即得解方程组 ，即得 Ly=b11213122323323,332,6,33llllll 12335223337363yyy 511(,)363y12325333321636133xxx TL x=y1 1(1, )2 3x改进的Cholesky分解法(改进的平方根法)利用矩阵运算比较两边得其分解公式:对k=1,2,3,n,1112112112122221221212100110011001nnnnnnnnnnnaaadllaaaldlALDLaaalld12111()/(1,2, )kkkkkrrrkik

26、ikirr krkrdal dlal d ldikknnii）求解方程组Ly=b 其中niii）求解方程组L x= D-1y 其中11(1,2, )kkkkrrrybl y kn1(,1,2,1)nkkkrkrr kxydl xkn n 10nr n 010rn 例 用改进的平方根法解方程组n解系数矩阵是对称的，故可分解为LDLT，设有分解n由公式得1233351035916591730 xxx1213121232313233351135911591711dllldllld12131232353,1,322,2,3dlldld解方程组Ly=b ，即得解方程组Lx= D-1y ，即得123110

27、1116530213yyy4(10,6, )3y111122133511103126143xdxdxd(1, 1,2)x解三对角方程组的追赶法n设方程组 Ax=d它的系数方阵A是一个阶数较高的三对角方阵且满足条件：(i) |b1|c1|0 , (ii) |bn|an|0 (iii)|bi| |ai|+|ci| , ai,ci0(i=2,3,n-1) 11222333111nnnnnbcabcabcabcabAni)对A进行Crout分解利用矩阵运算比较两边推得其分解公式：11112222223331111111111nnnnnnnnnnbcabcabcabcab1111111,/,(2, )(

28、2, )/(),(2,1)iiiiiiiiiiibcbainbaincbainni,可由ai, bi ,i-1, 产生，真正需计算的是i. i的递推公式为1111/(),(2,1)iiiiicbcbain求解Ax=d求解nii）求解方程组 ，即其计算公式为 (k=2,3,n) 11111/()/()kkkkkkkydbyda ybaLyd111222211nnnnnnydydydLydUxy niii）求解方程组x=y，即n其计算公式为 (k=n-1,n-2, ,2,1)11122211111nnnxyxyxy1nnkkkkxyxyxn将求系数1 2 n-1及y1 y2 yn的过程称之为追的过

29、程;求xn xn-1 x2 x1的过程称之为赶的过程; 2.4 误差分析 Ax=b (1)Ax =b (2)n(2)是(1)的近似方程组，研究二者解的近似程度n上面问题相当于研究Ax=b的精确解x与(A+ A) (x+ x)=b+ b 的精确解x+ x的差 x与扰动 A和 b的关系方程组Ax=b 的右端b的扰动对解的影响n设 b为b的扰动， 引起解x的扰动为 x，则1cond( )xbbA AAxbb1()A xxbbxAb1xAbAxbxAA方程组Ax=b 的系数阵A的扰动对解的影响设 A为A的扰动， 引起解x的扰动为 x，则11()() xAA xxxAAxx()()()0AA xxbA

30、xA xx11假设足够小，使AAA1111cond( )111 cond( )AAA AAAAxAAAAxAAA AAAAn对于一个确定的线性方程组，系数矩阵的条件数较小（接近1）时，方程组是良态的；反之，条件数较大（1）时，则方程组是病态的. 条件数越大，则病态越严重. 条件数的值刻划了方程组病态的程度. 用一个稳定的方法去解一个良态方程组，必然得到精度很高的解. 同样，用一个稳定的方法去解一个病态方程组，结果就可能很差. 2.5 解线性方程组的迭代法 n将方程组 Ax=b （2.5.1)改写成等价方程组 x=Bx+g （2.5.2) 建立迭代格式 x(k+1)=Bx(k)+g (k=0,1

31、,2,) （2.5.3) 向量x(0)为初始预估解向量,用公式(2.5.3)逐步迭代求解的方法叫做迭代法.B称为迭代矩阵. 如果产生的序列x(k)对于任意初始向量x(0)均收敛于x*，则称迭代法是收敛的. 显然x(k)的极限x*为方程组(2.5.2)的精确解.迭代法的误差n记 (k)=x(k)-x* (k=0,1,2,)称为第k步迭代的误差向量. (k+1)=x(k+1)-x* =B(x(k)-x*)=B (k) (k+1)=Bk+1 (0) (k=0,1,2,)其中 (0)=x(0)-x*为初始误差向量. 考察收敛性，就要研究B在什么条件下 (k)0 (k) ，即就要研究B满足什么条件时有

32、Bk0(k).迭代法的收敛性n定理 设BKnn, 的充分必要条件是(B)1. n定理（迭代法的基本收敛定理）迭代过程 x(k+1) =Bx(k) +g对于任意初始向量x(0)及右端向量g均收敛的充分必要条件是迭代矩阵B的谱半径(B)1, 并且(B) 愈小，收敛速度愈快. 由此可知：迭代法的收敛性与收敛速度与迭代矩阵B有关，而与右端向量g和初始向量x(0)无关. limkkB 0迭代法的误差估计n定理 设x*为方程组Ax=b的精确解. 若迭代法 xk+1) =Bx(k) +g的迭代矩阵B满足B1, 其中.是某种算子范数，则对于任意的初始向量x(0)与右端向量g迭代法收敛， 且有如下两个误差估计式

33、：（1） （2.5.4)（2） （2.5.5) ( )( )(1)*1kkkBxxxxB( )(1)(0)*1kkBxxxxBn证 (B)B1，故对于任意的x(0)与g迭代收敛. x(k+1) - x* =B(x(k) -x*) x(k+1) - x(k) =B(x(k) - x(k-1) ) x(k+1) - x* Bx(k) -x* x(k+1) - x(k) Bx(k) - x(k-1) ， 利用x-yx-y Bx(k)-x(k-1)x(k+1)-x(k)x(k)-x*-x(k+1)- x* (1-B)x(k) -x*(1)成立.再反复利用x(k+1)- x(k)Bx(k)-x(k-1)

34、 得(2)成立.基本迭代公式n将方程组Ax=b的系数A分解成 A=L+D+U其中D=diag(a11,a22,ann) ，L和U分别是A的对角线下方元素和上方元素组成的严格下三角阵与严格上三角阵. 即111212122212000000000000000000nnnnnnaaaaaaaaa AJacobi迭代法n若aii0 (i=1,2,n), 将方程组 建立迭代格式 (k=0,1,2,)称为解方程组Ax=b的Jacobi迭代法.nnnnnnnnnnbxaxaxabxaxaxabxaxaxa2211222221211121211113112112311111111232212213222222

35、22112121nnnnn nnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa (1)( )( )( )13112112311111111(1)( )( )( )232212213222222221(1)( )( )( )12121kkkknnkkkknnn nkkkknnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa nJacobi迭代法的分量形式若aii0，将方程组改写为建立迭代格式), 2 , 1(1nibxanjijij), 2 , 1()(11nixabaxnijjjijiiii(1)(

36、 )11()(1,2, ;0,1,2,)nkkiiijjjiij ixba xinkaJacobi迭代法nJacobi迭代法矩阵形式若aii0 (i=1,2,n), 即D非奇异，将方程组Ax=b改写成 Dx=-(L+U)x+b x=-D-1(L+U)x+D-1b建立迭代格式 x(k+1)=-D-1(L+U)x(k)+D-1b (k=0,1,2,)称为解方程组Ax=b的Jacobi迭代法.n迭代矩阵BJ=-D-1(L+U)=E-D-1A1121111221222212000nnJnnnnnnaaaaaaaaBaaaaGauss-Seidel迭代法n Gauss-Seidel迭代法分量形式nGau

37、ss-Seidel迭代法矩阵形式 将方程组Ax=b，改写成 (D+L)x=-Ux+b x=-(D+L)-1Ux+(D+L)-1b 建立迭代格式 x(k+1)=-(D+L)-1Ux(k)+(D+L)-1b (k=0,1,2,)称为解方程组Ax=b的Gauss-Seidel迭代法.迭代矩阵BG=-(D+L)-1U1(1)(1)( )111() (1,2, ;0,1,2, )inkkkiiijjijjjj iiixba xa xinka 超松弛迭代法(SOR方法)n由Gauss-Seidel迭代法得由此得公式即称为超松弛迭代法(SOR方法),其中为松弛因子. 超松弛法的矩阵表示为当 =1时,就是Ga

38、uss-Seidel迭代法.)()(11)1()()1(nijkjijijkjijiiikikixaxabaxx)()1()1()1 (kikikixxx)(11)(11)1()1(nijkjijijkjijiiikixaxabax(1)1( )1() (1)()kkxDLDU xDLbn定理 超松弛法收敛的必要条件为02n证 设其迭代矩阵B的特征值为1,2, n , 由于迭代收敛,故有(B)1 从而 又 因此|1-| 1 ,即02121det(max)1nnii n B111221122detdet() ) det(1)1(1)(1)nnnnnna aaa aaBDLDU关于解某些特殊方程组

39、迭代法的收敛性n定理定理 若线性方程组Ax=b b的系数矩阵A为 对称正定阵，则Gauss-Seidel迭代法 收敛.定理定理 若线性方程组Ax=b的系数矩阵A为 对称正定阵，则当02时, SOR方 法收敛.n称方阵A=(aij)nn 为严格对角占优的，如果 或n定理 若线性方程组Ax=b的系数方阵A=(aij)nn是按行(或按列)严格对角占优的，则Jacobi迭代法和Gauss-Seidel迭代法都是收敛的.), 2 , 1(1niaaiinijjij), 2 , 1(1njaajjnjiiijnJacobi迭代矩阵由于A是按行严格对角占优,即故从而Jacobi迭代收敛11max1nijJi

40、 njiij iaa B11211112211222212000nnJnnnnnnaaaaaaaaaaaaBED A), 2 , 1(1niaaiinijjijn设方程组的精确解为nGauss-Seidel迭代公式为n两式相减得*12(,)nxx xx 1(1)(1)( )111()(1,2, ;0,1,2,)inkkkiiijjijjjj iiixba xa xinka )(11*11*nijjijijjijiiiixaxabax )()(11)(*11)1(*)1(*nijkjjijijkjjijiikiixxaxxaaxxn令 ,设n则n整理得n由于系数阵A是按行严格对角占优的,故)(*

41、1maxkiinikxx )1(*)1(*11maxkllkiinikxxxxnljkljljkljllkllkaaaxx1111)1(*1)(1kljllljnljllljkaaaa11111 令 ， n从而n所以Gauss-Seidel迭代 法收敛.1111(1)1knljj llllklljjllaarlnaa (1)1100()kkkxxrk maxklrrn定理定理 若线性方程组Ax=b的系数矩阵A为严格对角占优矩阵，则当01时,SOR方法收敛.n定理定理 设A是具有正对角线元素的对称矩阵，则解线性方程组Ax=b的Jacobi迭代法收敛的充分必要条件是A和2D-A都为对称正定阵.nJ

42、acobi迭代法收敛的充要条件:(BJ)1 A和2D-A都为对称正定阵(A是具有正对角线元素的对称矩阵). 充分条件： BJ1 A是严格对角占优的nGauss-Seidel迭代法收敛的充要条件:(BG)1 充分条件： BG1 A是严格对角占优的 A为对称正定阵nSOR方法收敛的充要条件:(B)1 充分条件： B1 A是严格对角占优的，且01 A为对称正定阵， 02 必要条件：02n例1 分别用Jacobi迭代法与Gauss-Seidel迭代法求解方程组取初值x(0)=(0,0,0),123123123202324812231530 xxxxxxxxx解n（1）系数阵严格对角占优，故Jacobi

43、迭代法与Gauss-Seidel迭代均收敛.法用Jacobi迭代法，其迭代法的分量形式为(1)( )( )( )( )12323(1)( )( )( )( )21313(1)( )( )( )( )312121(2423)1.20.10.15201(12)1.50.1250.12581(3023)20.13330.215(0,1,2,)kkkkkkkkkkkkkkkxxxxxxxxxxxxxxxkJacobi迭代法的矩阵形式为 x(k+1)=(E-D-1A)x(k)+D-1b即 (1)( )11(2)( )22(1)( )3300.10.151.20.12500.1251.50.13330.2

44、02.0kkkkkkxxxxxx 取初值x(0) =(0,0,0)，迭代可得迭代7次，得近似值(1)(2)(3)(4)(5)(6)(1.200 000,1.500 000,2.000 000) ,(0.750 000,1.100 000,2.140 000) ,(0.769 000,1.138750,2.120 000) ,(0.768125,1.138875,2.125 217) ,(0.767 330,1.138332,2.125358) ,(0.767 363,1.138 414,2xxxxxx(7).125356) ,(0.767 355,1.138 410,2.125368) ,x(

45、0.767 355,1.138 410,2.125368)x(2)用Gauss-Seidel迭代法,其迭代法的分量形式为(1)( )( )( )( )12323(1)(1)( )(1)( )21313(1)(1)(1)(1)(1)312121(2423)1.20.10.15201(12)1.50.1250.12581(3023)20.13330.215(0,1,2,)kkkkkkkkkkkkkkkxxxxxxxxxxxxxxxk其迭代法的矩阵形式为x(k+1)=-(D+L)-1Ux(k)+(D+L)-1b (k=0,1,2,)即 (1)( )11(1)( )22(1)( )3300.10.15

46、1.200.01250.106251.350 0.1583330.001252.11kkkkkkxxxxxx取初值x(0) =(0,0,0)，迭代可得迭代5次，得近似值(1)(2)(3)(4)(5)(1.200 000,1.350 000,2.110 000) ,(0.748500,1.142 688,2.128738) ,(0.766 421,1.138105,2.125 432) ,(0.767 375,1.138399,2.125363) ,(0.767 356,1.138 410,2.125368) .xxxxx(0.767 356,1.138 410,2.12537)xn例2 对方程

47、组分别讨论用Jacobi迭代法和Gauss-Seidel迭代法求解的收敛性. 1231231232212223xxxxxxxxxn解 系数矩阵则Jacobi迭代法的迭代矩阵为其特征方程为因此有1=2=3=0,即(BJ)=01 ，所以Gauss-Seidel迭代法发散. 11100022022()110001023221000002G BDLU222023(2)0002EBG n例3 设方程组Ax=b中分别讨论用Jacobi迭代法、Gauss-seidel迭代法和逐次超松驰迭代法(02)求解的收敛性. 111221112211122An解 显然A是对称矩阵. 现考虑A的各阶顺序主子式从而A是对称

48、正定阵，故Gauss-Seidel迭代法收敛. 又由已知0f(x*).n 线性方程组Ax=b的求解问题等价于求一簇n维椭球面的公共中心问题.min( )( *)nxffRxx1(*)(*)( *)2CfxxA xxx11( )( *)( (*),*)(*)(*)22ffxxA xxxxxxA xxn思想：构造向量序列xk，使 (1)f(x(k+1) f(x(k) f(x(1) f(x(0) (2)当k时, f(x(k) f(x*)这与要求x(k)x*(k)是一致的.n具体方法：由第k个近似x(k)构造下一个近似x(k+1)，首先选定一个向量pk作为方向，要在直线x= x(k) +tpk (t为

49、参数)上找一个使f(x)为极小的点x(k+1) ，即确定参数t使f(x(k)+tpk )为极小.单变量t的二次函数令(t)=t(Apk, pk)-(r(k), pk)=0得且这时有(t)=(Apk, pk)0, 从而得极小f(x(k+1).其中( )2( )( )1( )()(,)(,)()2kkkkkkktftttfxpAppbAxpx( )(,)(,)kkkkrptApp(1)( )( )(,)(,)kkkkkkkkkxxprpApp考察直线x= x(k) +tpk与椭球面f(x)=C的交点，二次方程(t)= f(x(k) +tpk)=C，当C=f(x(k+1) 时只有一个重根k，因此pk

50、与椭球面f(x)=f(x(k+1)相切于x(k+1). 另外，r(k+1)=b-Ax(k+1)=b-A(x(k)+kpk)=r(k)-kApk(r(k+1), pk)= (r(k), pk)- k(Apk, pk)=0 r(k+1)与 pk正交.最速下降法在n维空间定义的二次函数f(x)在点x(k)的改变率最大的方向是f(x)在点x(k)的梯度 gradf(x)|x= x(k)=-r(k) ，因此沿方向r(k)函数f(x)瞬时下降的最快，所以取这个方向为pk而得到新的近似x(k+1)的方法就叫最速下降法.只要r(k)0,最速下降法就继续下去,这里有(r(k+1), r(k) )=0.(1)(

51、)( )( )( )( )( )0,1,2,(,)(,)kkkkkkkkkkxxrrrArr共轭梯度法n求解Ax=b的最速下降法的最速下降方向,即 r(k)=-gradf(x(k)具有局部性质,在x(k) 附近f(x)沿r(k) 下降最快. 但总体看,这个方向未必是函数下降最理想的方向.下面介绍更合理地选择方向pk的方法,这种方法只要经过有限步( n)就能找到n维椭球面簇的公共中心x*的一种迭代法，即共轭梯度法，它是具有迭代形式的精确解法.定义定义 ARnn为对称正定矩阵, p,lRn，如果 (p, Al)=0,则称p与l为A-正交或A-共轭.n先考察二维情形n共轭梯度法的具体步骤n第1步（采用最速下降法） 对于初始向量x(0)，r(0)=b-Ax(0)0，取p0=r(0), 从x(0)出发沿方向p0寻找新的近似(f(x)的极小点)x(1).n计算r(1)=b-Ax(1)=r(0) - 0Ap0，且有(r(1), p0)=0，若 r(1)0 (1)(0)00(0)0000(,)(,)xxprpAppn第2步 选择方向向量p1,满足条件 ) p1=r(1) +0p0 ； ) p1与p0为A-正交或A-