线性方程组的迭代法

1、第五章解线性方程组的迭代法 实际问题经过简单的分析可以直接归结 为线性方程组，或者微分方程，后者可以转换为线性方程组。 两种方法： 直接法：中小型稠密矩阵 迭代法：大型稀疏矩阵5.1 Jacobi迭代法和Gauss-Seidel迭代法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111设线性方程组简记 AX=bn其中1112121222n1n2n1212A()X,nnijn nnTTnnaaaaaaaaaaxxxbbbbn将方程组AX=b，改写成便于迭代的形式 建立迭代格式 向量X(0)事先给定，称为初始解向量，用公式逐步迭代求解的方法叫做迭

2、代法. 如果由产生的序列 收敛，则称迭代法是收敛的，否则称为迭代法发散. XBXg(1)( )(0,1,)kkkXBXg( )1kkXn若将方程组改写为), 2 , 1(1nibxanjijij), 2 , 1()(11nixabaxnijjjijiiii0iia 1Jacobi迭代法n建立迭代格式其中(1)( )11()(1,2, ;0,1,2,)nkkiiijjjiij ixba xinka( )( )( )( )12(,)kkkkTnxxxXJacobi迭代法的矩阵表示n将方程组AX=b的系数A分解成 A=D+L+U其中D=diag(a11,a22,ann) ，L和U分别是A的对角线下方

3、元素和上方元素组成的严格下三角阵与严格上三角阵. 即000000000000000000211222112121nnnnnnaaaaaaaaaA()DXLU Xb()DLU Xb()DXLU Xb AXb11()XDLU XD b 迭代格式为：(1)1( )1()kkXDLU XD b (1)1( )1()kkXID A XD b对应的分量表示形式为：(1)( )( )11()(1,2, ;0,1,2,)nkkkiiijjijiixxa xbinka另外一种矩阵形式是：的Jacobi迭代格式（三种）123121322531272xxxxxxx 写出方程组122130207系数矩阵为：02200

4、0000U000100200L 100030007D(1)1()1(1)1()1()X(IDA )XDbkkkkXDLUXDb 迭 代 格 式 为 ：或 者Matlab计算过程如下： A=1 -2 2;-1 3 0;2 0 7A = 1 -2 2 -1 3 0 2 0 7 U=triu(A,1)U = 0 -2 2 0 0 0 0 0 0 L=tril(A,-1)L = 0 0 0 -1 0 0 2 0 0 D=diag(diag(A)D = 1 0 0 0 3 0 0 0 7 -inv(D)*(L+U)ans = 0 2.000000000000000 -2.000000000000000

5、0.333333333333333 0 0 -0.285714285714286 0 0 b=5;-1;2;inv(D)*bans = 5.000000000000000 -0.333333333333333 0.285714285714286 I=eye(3)I = 1 0 0 0 1 0 0 0 1 I-inv(D)*Aans = 0 2.000000000000000 -2.000000000000000 0.333333333333333 0 0 -0.285714285714286 0 0分量形式为:1232133125( 22)1( 1 (0)31(2(20)7xxxxxxxxx

6、(1)( )( )123(1)( )( )213(1)( )( )3125( 22)1( 1 (0)31(2(20)7kkkkkkkkkxxxxxxxxx Gauss-Seidel迭代法方程组改写为：()LD XUXb 11()()XLDUXLDb 即得迭代格式：(1)1( )1()()kkXLDUXLDb Gauss-Seidel迭代法n迭代格式的分量形式：其中 1(1)(1)( )111()(1,2, ;0,1,2,)inkkkiiijjijjjj iiixba xa xinka ( )( )( )( )12(,)kkkkTnxxxX的Gauss-Seidel迭代格式（两种）1231213

7、22531272xxxxxxx 写出方程组例n 分别用Jacobi迭代法与Gauss-Seidel迭代法求解方程组精确到小数点后四位，并要求分别写出其迭代法的分量形式和矩阵形式. 123123123202324812231530 xxxxxxxxx解n（1）用Jacobi迭代法，其迭代法的分量形式为(1)( )( )( )( )12323(1)( )( )( )( )21313(1)( )( )( )( )312121(2423)1.20.10.15201(12)1.50.1250.12581(3023)20.13330.215(0,1,2,)kkkkkkkkkkkkkkkxxxxxxxxxx

8、xxxxxk迭代法的矩阵形式为其中 (1)1( )1()kkXID A XD b1100201 0 0202300.10.1510 1 0001810.12500.12580 0 123 150.13330.2010015ID A 11241.2201121.58130215Db(1)( )11(2)( )22(1)( )3300.10.151.20.12500.1251.50.13330.202.0kkkkkkxxxxxx 取初值X(0) =(0,0,0)，迭代可得(1)(2)(3)(4)(5)(6)(1.200 000,1.500 000,2.000 000) ,(0.750 000,1.

9、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,2TTTTTXXXXXX(7).125356) ,(0.767 355,1.138 410,2.125368) ,TTX迭代7次，得近似值. n（2）用Gauss-Seidel迭代法，其迭代法的分量形式为(0.767 355,1.138 410,2.125368)TX(1)( )( )( )( )12323(1)(1)( )(1

10、)( )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其迭代法的矩阵形式为其中(1)1( )1()()kkXDLUXDLb 1110020200011()1800160823 1519112 4004015DL 11002002311()0001160800019112 400401500.10.1500.01250.106 2500.1583330.00125 DLU 110020241.211()

11、0121.351608302.11191124004015DLb即 取初值X(0) =(0,0,0)，迭代可得(1)( )11(1)( )22(1)( )3300.10.151.200.01250.106251.350 0.1583330.001252.11kkkkkkxxxxxx迭代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 3

12、56,1.138 410,2.125368) .XXXXXTTTTT(0.767 356,1.138 410,2.12537)XT 向量和矩阵的模（范数）n为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，向量和矩阵的范数。向量和矩阵的范数n在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用| x1-x2 |表示。向量和矩阵的范数n而在二维平面上，平面上任意一点P(x,y)到原点的距离用 表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。 推广到n维空间

13、，则称为向量范数。|22OPyx22122121)()(|yyxxPP向量范数,|,:1)|00|0;2)| |,;3),| |nnRkkkRRxxxxxxxxxx yxyxy设任一向量按某一确定的法则对应于一非负实数且满足非负性：，当且仅当时，奇次性：三角不等式：对任意都有，则称为向量 的范数。常见的向量范数121112221111( ,.,)|( ,1)|(| )( ,2)( )|(| )( , )|max|( ,inf)Tnniiniinpppiiii nx xxxnorm xxnorm xornorm xxnorm x pxnorm xxxxxx 设向量对 同 一 向 量 来 说 ，

14、采 用 不 同 的 范 数 ， 值 一 般 是 不 同 的 ，但 下 面 的 性 质 告 诉 我 们 ， 有 限 维 向 量 的 模 是 相 互 等 价 的 ，所 以 在 讨 论 向 量 序 列 收 敛 时 ， 可 采 用 任 意 一 种 范 数 。向量范数性质R| | ,| | ,|nnm MmMRxxx 性质 对中定义的任意两种范数则必存在两正数使得*limlim| 0kkkkx xx x例已知12(1,2, 3, 4),xxxx求 矩阵范数,|,:1):| 00| 0;2)| |;3)| |,;4),|n nn nn nn nARAAAAkAkAkRABABA BRABABA BRAR定

15、义 设任意若按某一确定的法则对应于一非负实数且满足非负性，当且仅当时，奇次性：，三角不等式：相容性：，则称为的一种范数。相容范数|,|,| | |nn nxARRAxAxAx定义设分别为和的一种范数 如果则称该矩阵范数与此向量范数是相容的。算子范数（了解）0| | 1,|,| maxmax |,nn nnxxn nxRARRxAxAAxxR定理设并在上定义向量范数则为上的矩阵范数 且称其为算子范数。算子范数（了解）0|1|1)| max0| 0,| 00,0n nxAAAARRAAAAAxxx xxxxx证明(了解)：由向量范数的连续性知，在有界闭集上一定能达到最大值所以定义了到的一个对应法则

16、。所以下面只要验证范数定义的四个条件。显然成立，若则，因为只有可能。算子范数（了解）|)|(|)(|max|) 3|max|max|)2000 xxxxxxxxxxxxxxxBABABABARAAAAAkAkkAkAnxxx于是，则由算子范数（了解）1|max|,|)(|max|)(|010 xxIxIIRBAABBAxxBABABAxxBAnnx则为单位矩阵中任何矩阵算子范数对推论。同理可证即有所以对常见的矩阵范数1111|maxnijj niAa 范数：2max2|()TAAA范数：11|max|niji njAa 范数：列范数行范数谱范数例题112221,| (1,2,)24:|max2

17、 | 2|,| 1| 45|max2 | 1|,| 2| 46222181014241017810|0101723.466,1.534|23.4664.84pTTAApAAA AIA AA 例设矩阵求解因为由解得，故4。nMatlab计算过程如下：2范数： norm(A)1范数： norm(A,1)无穷范数： norm(A,inf) 矩阵的谱半径11 2,( )max|( ),iii n(i, ,.,n)AAAAAAA 定义设为矩阵 的特征值 则称为矩阵 的谱半径。矩阵 的谱半径不是 的一种范数但可能与 的任何一种范数有某种关系。例题33)(33,3304212|421221AAIA所以。特征

18、值得：解：由的谱半径。求矩阵求特征值命令eig(A)2,(1)( ) |,|;(2),( ) |1,0( )maxn nTARAAAAAAAAAAAAAAAxxxxxxxx定理 设则这里为 的任意一种范数若则。证明 （ ）设为矩阵 的任一特征对，即则由于，故有由 的任意性，有。2max12(2)|( )|( )21, ( )33,|5,|6,24|4.844,( ) |TpAAAAAAAAAAAA因为，故。显然所以。例2120121 ,A011TA 矩阵求（A）（A）,（A A），解：A的特征值为：lm=eig(A)lm = 1.500000000000000 + 1.658312395177

19、701i 1.500000000000000 - 1.658312395177701i 1.000000000000000 ( )A为：norm(lm,inf)ans = 2.236067977499790AA 的特征值为： lm1=eig(A*A)lm1 = 0.936075017171059 2.921124938072438 9.1428000447564982A为 ：sqrt( 9.142800044756498)ans = 3.023706342348162迭代法的收敛性n定理（迭代法的基本收敛定理） 迭代过程 X(k+1) =BX(k) +g对于任意初始向量X(0)及右端向量g均收敛的充要条件是迭代矩阵B的谱半径(B)1, 并且(B) 愈小，收敛速度愈快. n定理（迭代法收敛的充分条件） 若迭代法 X(k+1) =BX(k) +g的迭代矩阵B满足，B=q1,则对于任意的初始向量X(0)与右端向量g迭代法收敛.证明n证 设X*为方程组X=BX+g的精确解,则 X* =BX* +g X* -