线性方程组的迭代解法（6）

1、第六章线性方程组的迭代法线性方程组的精确解法，针对于阶数不太大的方程组是比较有效，而对高阶方程组， 特别系数矩阵为无规律大型的稀疏阵(即矩阵中有许多零元素)，直接法很难克服存贮问 题。相对于直接法，我们可用迭代法求解，迭代法可以不必存储系数矩阵屮的零，且很易 编制程序。本章我们主要介绍解线性方程组的一般迭代，seidel迭代，及逐次松驰迭代法 (sor),它们都属于线性迭代。它们一般的做法是：把原方程组ax二b写成与其同解的方 程组x二bx+g,(其中a、b是nxn矩阵，b、g是n维列向量，x是n元未知列向量)，然后 建立迭代格式：x(k)=bxz)+g(6一1)希望对从任意的初始值x(

2、76;)开始，由(61)得到的向量序列x00是收敛的。定义从任意的初始值x(°)开始，由(61)得到的向量序列x00是收敛的，则称此迭 代法是收敛的，我们称b为迭代矩阵。(62)10% - 2x2 _ x3 =3 例：用迭代法解方程组：-2x,+10x2- x3=15 2xo + 5兀3 =10如果把(62)写成如下的同解方程组：x =0.2x2 +0x3 +0.3< x2 = 0.2x)+ 0.% + l5x3 = 0.2x)+ 0.4x2+ 2rh此建立迭代格式：x；k) =02x$t)+0.1x$t)+03x$)=0.2x,t)+0.1x$-】)+ 1.5x；k)= 0.

3、2x$t)+ o.4x 笄)+ 2取初始值晋)=x；°)=x；°)=0,其中x；°),xy),x)即为初始向量x(°)的第一、二、三个分量，其运算结果如下：kx,)x$)x$)000010.30001.500()2.000020.80001.76002.660030.91801.92602.864040.97161.97002.954050.98941.98972.982360.99631.99612.993870.99861.99862.997780.99951.99952.999290.99981.99982.9997而（6 2 ）的准确解是：xi=

4、l,x2=2,x3=3 ,迭代九次后的迭代值x二(0.999&1.999&2.9997)丁与准确解已很接近，但如果把(62)写成如下的同解方程组:x =5x2 - 0.5x3 - 7.5< x2 = -o.5x+ 2.5x3 一 5x3 = lox, - 2x2- 3按上式建立迭代格式：x,)=5x；k-i) 0.5x$-】)+7.5< x$)= _0.5x：k j)+ 2.5xf-i)_ 5x$)= 10x,t)_2x；k7-3取初始值 x(°)二(0,(),0)t,则 x=(7.5,5,3), x(2)=(-31,-8.75,-68),这样继续下去，x

5、(9)=( 1179069,-102678.219,-5862292),其结果的绝对值越来越大，不能逼近于任何常数，这个迭代格式是发散的。对于一个一般的线性方程组ax=b写成与其同解的方程组x二bx+g其方式有无穷多种，究竟怎样的迭代格式是收敛的呢？下 面我们给予讨论。§1.简单迭代法的收敛条件及误差估计我们把由方程组x二bx+g而建立的迭代格式x(k)=b x(k_,)+g(63)称为简单迭代格式。假设方程组x=bx+g有解对任意的初始向量x(0),设由(6-3)得的向量序列为 x(k),则有：严x'b(xz)x),令：e(k)= x(k)-x 则:e(k)=b e0,，e

6、(k)=bk e(0) o 如果(6-3)收敛，则对任意的初始向量x(°),(从而严也是任意的),有e(k)0：又因对 任意e(0),使e(k)= bke(0)->0(k->oo)的充要条件是b(k)->0(k->oo),这样我们得到下面定理：定理1：简单迭代格式(63)收敛的充要条件是b(k)t0(ktoo)。定义2：设nxn阶矩阵b的n个特征值为入，九称p(b)= max | xj |为矩阵b的 i<i<n谱半径。定理2： nxn阶矩阵a,有aj()(ktoo)的充要条件是p(a)<l证明：设a的特征值屮模最大的为九对应的特征向量为v,则

7、有av二川v从而有akv=九:vp (a) <lo如果有aj0,则肾vt0,即娥to(ktoo),从而必有i九|<1即: 反z,结论也成立。由于a必相似于一个jordan标准型：diag( a】，),其中ai =nixni由于p (a)<1,从而| 入|< 1 (i=l/-r)，故有 a： > 0(k > oo) o从而有:(dhig(a,，a)jo,故 ak->0(k->0)系：简单迭代(6-3)收敛的充要条件是p(b)<1 例2：对线性方程组：x=bx+g判断其用简单迭代法能否收敛，其屮:01-2_r1300g =22.700-1b =

8、九3 =解：由于b的特征根为：纸=0,九219211921故 p(b)=,从21而知简单迭代法收敛。矩阵范数与谱半径有如下关系:定理3：设iiii为上定义的一个范数，如果制<1,则p(a)< 1 o证明：设a的特征值中模最大的为九|,对应的特征向量为v ,则有av=x|v ,从而有avvt = wt o因v为特征向量，所以wt 70 o因此iavvt=2, vvtavvr <t vv因此：冈卜制vl我们从前面的系知道：简单迭代法(6-3)收敛的充要条件p (b) <lo然而求矩阵b 的谱半径并非易事，故我们常常用其它判别条件。下面的定理4给出了儿种判断收敛的方 法。定理

9、4：如果简单迭代法(6-3)的迭代矩阵b满足下列条件之一(1) |b|lmax£|bij|vl(2) |b |x= max£| 切 | < 1ii bia梓¥屮<1则简单迭代法收敛，这里b二(切)叭证明：其实三个条件中的任一个都可推汕矩阵b的谱半径p (b)<1,从而可知：定理 的结论成立。误差估计定理5：设有迭代格式(63),若|b|<1,则对任意初始向量x(°)与g迭代收法收敛, 且有误差估计式：hx(k)_x* 乍"blf |x 一 x(°)|1-iibh这里向量范数ii |和矩阵范数| |是相容的任一范

10、数。1-iibh证明：由于|b|<1,故必有p (b) <|b|<1,从而知x=bx+g有唯一解x*,且(63) 必收敛于x：从而有：|x(k + n) _x(k)旧揺曲“)_x(k+t 11 + 11 x(k + n-l) _ x(k + n-2) 11 + 11 x(')_ x(k) |又因为：x(m+1)-x(m)= b (x(m)-x(m_,)从而| x(m+1)- x(,n)|<|b| ii x(m)- x(m_1)|故有：| x(k,n)- x(k)|<(| bir'+ll b|严+|b|+l川x(k)|j-|b|n |x<-x|

11、(64)当 dtoo时得:|x(k) -x* |<(65)从证明过程我们看到当|b|不太接近于1的情况下，可用|卅）xz）|v£作为控制迭代的 终止条件，并取x（k）作为方程组的近似解。例3：在前面的例1中，采用迭代格式为(k)10.2x；k-】)+0x$t)+().3x；k)= 0.2x$7)+0lxf)+1.5xf) = o.2x；k_l) +0.4x/t)+200.2由于b二0.200.10.30.20.40|b|h=max0.4,0.6,0.4=0.6<l|b|g二max 03,0.5,0.6 =0.6< 1|b|f= a/0.22 +0.12 +0.22

12、+0.32 +0.22 +0.42= v038 < 1故收敛，（上面三个条件中只要有一个成立即可推出此法收敛，特别应注意，如果定理中 的三个条件都没有满足，也不能推出简单迭代不收敛，如前面的例2）。§ 2. seidel 迭代对线性方程组x二bx+g建立如下的迭代格式：x,）= bmxk_1） + b|?x 厂）+ + blnxk_1） + g|x；k）= b21x；k）+ b22x 厂）+ + b2“xt）+ g2（6_6）x（k）=b x（k）+b x（k）+ +b x（ki）+£lanunlal 十 un2a2 十unna n 十 mn称为线性方程组x=bx+g

13、的seidel迭代格式，因为我们在迭代过程始终用的是最新的结果, 期望它有更快的收敛速度。这里b=（bij）nxn, g=（gi,，g）t令：e=0 % 0f =bb2bn“22纭仇2_bnn_则(6-6)也可写成矩阵形式：x(k)=e x(k)+f x(k_1)+g(67)即：x(k)= (i-e) ，fx(k',)+ (i-e) _lg(68)这样：(6-8)也是一个简单迭代格式，故前面性质也相应成立，女口： (6-7)收敛的充要条件是：p (i e)“f) <1下面我们给出使seidel迭代法收敛的较易判定的三个充分条件。 定理1:如果线性方程组x二bx+g的矩阵bnxn满

14、足如下条件之一:(1)|b| 卞<1(2)11 bip抚flbjjli=l l|b|p=为为|bjj |2 <1(j=i i=i丿则seidel迭代法(5 6 )是收敛的。证明：因为seidel迭代法(5 6)收敛的充要条件是p (ie)“f) <1下证：三条件只要有一个满足，必有p (i e)_f) <1如果存在入 o，l 九o 上 1，且使 det九 1。一 (i- e)-*f=o,则有 detz0i-x0e-f = 0从而deti-e-f=0,由于丨九oal，由范数的定义知: 九()1|e+f|q|e+ f|h 入o|e+f|f>|e+f|f由于b=e+f,

15、故|b|h<l, |b|u<1, |b|h<l只要有一个成立,必可推出相应的|e+丄f| 入0小于1,即说明：p (e+ f) <1,这与det(i-e- f)= 0矛盾，从而知丨丨<1： 九o入o即(i e )j f的特征根的模必都小于1,故p ( i e )“f) <1,故seidel迭代(6-6) 是收敛的。一般情况下，seidel迭代比简单迭代有更快的收敛速度。例2 :用seidel迭代法解方程组(62 )解：还是采用：x|=0.2x2+0.1 x3+o.3x2=0.2x|+0x3+i.5x3=0.2xi+0.4 x2 +2同解方程组，建立seide

16、l迭代格式：xf) =0.2xf)+0.1x,7 +0.3x；10 =0.2x$)+0.6x$-i)+1.5xf) = o.2x；k) +0.4x；k)+2取初始值x(0)= ( 0 ,0,0),计算结果如下：kx,)x,)x,)000010.30001.56002.684020.88041.94452.953930.98431.99232.993840.99781.99892.999150.99971.99992.9999迭代5次后，已得到较好的结果。但应注意的是：有这样的例子，简单迭代收敛，但seidel不收敛。. 下面分别是简单迭代和seidel迭代的计算框图。(见下页)§ 3

17、. jacobi 迭代和 gauss-seide i 迭代对于线性方程组ax二b,如果用简单迭代或seidel迭代，一般首先把原方程组写成与x 二 bx+g(69)然后再写迭代格式。然而与原方程组同解的形如(6-9)的方程组有无穷多种。如杲我们 把原方稈组写成如下形式的同解方稈组：x =一一 (ai2x2+ ai3x3+ ainxn b|)anx2 = - (a21x|+a23x3+a2nxn-b2)(610)1xn =(an】xi+an2x2+an3x3+an»ixnjbn)ann简单迭代的计算框图(j=l, m)y(o <= y(z) + 6z(z, j)双丿)y(z)&l

18、t;= xo + <(z)注：k为迭代次数最大很，£是控制粘度，x输入是初始值。seidel迭代框图：而得到的简单迭代格式:x,）一丄（hm严）ai!x（k） “ /kj）x2 一va21xla22+ ai3x3k"r）+ + ainxnk"，）- bl）+ a23x3k'° + + a2nxnk"，）- b2）（611）y（k）an+ an2x2k_，）+an3x3k_，）+ + %-区茫】）-叽）称为jacobi迭代（这里砌工0, i=l,2,n）。jacobi迭代也可看成简单迭代的一种，故 对简单迭代的所有性质也成立。从上可

19、知：如果矩阵a的主对角元不为零，则其jacobi 迭代是唯一的。如用矩阵形式表示：则迭代矩阵：b=i- d'*a其中:g二 db, d=diag(an/-, ann)定理1 : jacobi迭代(611)收敛的充要条件是p ( i - d_1 a) <1 o特别：若系矩阵a有如下特殊的特征，则jacobi迭代法收敛。定理2：若方程组ax二b的系矩阵a满足下面条件中的任何一条，则其jacobi迭代法 收敛。(1)a为行对角占优阵，即：|% |>工|打|(i=l,2,n)jhi(2 ) a为列对角占优阵,即：i a” |>工|曲|(j=l,2,n) wj(3 ) a的元素

20、满足：y ' a" ' < 1, a ho (j=l,2,n)ft i au i证明：如果满足条件(1 ),则式(610)中的b满足：|b|l<1,故jacobi迭代收敛。 如果满足条件(3),则|b|h<l,故jacobi迭代收敛。如果满足条件(2),则willd-'at|u<1, 则 a *x=b 的 jacobi 迭代收敛,这里 d二diag(a【,，ann)o 从而有p ( i d_1 at ) < 1 ,因为d'1 "与a7 d1有相同的非零特征根。而在条件(2)下，det屮 工0,故d1 ar与a1&

21、#39; d'1有相同的特征根。从而i-d-1屮与i 一屮di有相同的特征根，故有p( i -d"1 ) =p ( i -a7 d_1) =p ( i -d"1 a),故 p ( i -d_l a) <1 ,从而知 jacobi 迭代收 敛。如果把(6-10)写成seidel迭代式，即：屮)=+ 如兄+ +气兀,一"_勺)如(612)x2 - - 21 屮+。23才d + + a2nx -b2)°22x(n= -(色1带 + an2x2 + an + +%我们称它为方程组ax=b的gauss-seidel迭代式，如写成矩阵形式为： x(k)

22、= d1 (lx(k)+ux(k_1)+ ddbx(k)= (d-l) *u x(k_1)+ (dl)"b(613)其中：l=-_0 'a2 °,u = -°a20 fzj1 1a（n-l）n。川an2ann-u.0d=diag(an, ann)gauss-seidel迭代法的迭代矩阵为(d-l)_1u,常数项为(d-l)_1b，收敛的充要条件是 p (d-l)'1 u)<1,特别：定理3：若方程组ax=b的系数矩阵a,满足下而条件中的任何一条，则gauss-seidel 迭代收敛。(1) a为行对角占优阵(2) a为列对角占优阵(3 )a的

23、元素满足"i v 1, qho(j=l,2,n)i ah i”证明：如果(1)或(3)成立，则(610)中的|国l<1或制<1，由前面一节的 定理1知：gauss-seidel迭代法收敛。如果a为列对角占优阵，gauss-seidel迭代法的迭代 矩阵特征多项式为：detxi-(d-l)_,u = det (d-l)_l -detd-xl-u由于如果丨x i >1,则矩阵?vd-xl-u是列对角占优，从而detlxd-xl-u>0,这 说明迭代矩阵的特征根的模都小于1 ,即p (d-l)-'u) vl,故收敛。定理4：若方程组系数矩阵a为正定阵，则其g

24、uass-seidel迭代收敛。(证明：放在后一节给出)例：设线性方程组为：xi+2 x2= -13xi+ x2 =2问用jacobi迭代法和guass-seidel迭代法解此方程组是否收敛。'0- 2|l解:jacobi迭代矩阵b=, p(b) = v6 > 1,故发散。-30t o -2如果gauss-seidel 迭代，迭代矩阵 b=(d-l)-,u =, p(b)=6>l,故0 6guass-seidel,迭代法也发散。但如果把方程组的两个方程的顺序对换一下3x+ x2=2x|+ 2x2= -1此时，系数矩阵a是行对角占优阵(也是列对角占优阵)，所以jacobi迭代

25、及guass-seidel 迭代都收敛。对jacobi迭代还有如下结论：定理5：设aernxn具有正对角线元素的对称矩阵，则解线性方程组ax=b的jacobi 迭代法的收敛的充要条件是a和2 d-a都是正定阵。易知a与2 d-a的差别仅是非对 角线元素的符号不同(d=diag(alb, ann)o证明：由假设知：d=diag(ai血)是正定对角阵，由于jacobi迭代法的迭代阵b=i-d_ 1 a = di(i-dad)d这里d，从而知b是实对称阵，其特征值都是实数，不妨记为：九，兀1 1必要性：如果jacobi迭代收敛，贝ijp(b)<lo从而知：p(i - d 2 ad 2 ) &l

26、t; 1 ,因为j_ 丄丄 丄丄 丄d石ad石是实对称阵,故p(i-d_2ad2)= maxfll-x： |,由此可知d石ad的 l<i<n丄 _丄_丄 _l特征值必在(0, 2),即说明d_2ad_2是正定阵，从而a是正定阵，且2id石ad石的ii1111特征值也在(0, 2)中，故21-d 2ad亍也是正定阵，由于d(21 - d_ad_2 )d=2da,故2 d a也是正定阵。丄 _丄_丄 丄充分性：如果a和2d-a都是正定阵，则d_2ad_2也是正定阵。由于d_2ad'2111i=i ( i d彳ad 2 ),从而i d 3 ad 2的特征值都小于1 , b|jb的

27、特征值都小丄 _丄于1,又因2 d-a是正定阵，从而21dad丐也是正定阵。1_ 1_ 1_ 1_ 1_ i由于 21-d_2 ad= 1+(1 -d 2 ad 2 ),故(i d= ad_2 )的特征值都大于一1,即b的特征值都大于一1,从而得：p(b)<l,即jacobi迭代收敛。1aciaaf则用jacobi迭代法解方程组ax = b收敛的充要条件aa1证明：易知a正定的充要条件是：-丄v a v 1 , 2d-a正定的充要条件是：-<a<-o2 2由定理5知：jacobi迭代法收敛的充要条件是：-丄vqv丄。2 2§4.逐次超松驰迭代法(s0r)在很多情况下

28、,guass-seidel迭代法比jacobi迭代法收敛速度快。分析guass-seidel迭代公式(6-12),我们可以发现(6-12)改写成：xf)+丄(bj £吋严-立督汀)0=1/-,n)(6-14)aiij=lj=i记：中)二$>/畀称严为第k步第i个分量的残量。那么 j=】j=igauss-seidel迭代法实际上就是:每一个分量的第k次迭代值由第k-1次迭代值再加上一个 残量的倍数构成。如果迭代收敛，显然：ri(k)to(ktoo),(i=l,n)。定义修正量 ax；k)=丄严)，则gauss-seidel迭代可写成：aiix$)= x$t)+ ax,) g二,2

29、,n)为了获得收敛速度更快的迭代公式，期望通选择合适的参数3,在修正向量前面乘以这个参数3,得到新的迭代公式x,)+3从,)来达到。此时迭代式也即为：x,)= x(k-1)+e(bi _£aijx)_£aijx-d)(口,n)(615)aiij = lj = i当gl时，即为gauss-seidel迭代。我们称(6-15)为逐次超松驰迭代法，简记为sor 法。3>1时，一般称逐次超松驰迭代法为超松驰法，3v1时称为低松驰法。xjk) =(l-co)x!k_1) 4- (bj- £aijxj)，(i=l,n)(616)aiij=lj=i + l写成矩阵形式为：

30、x® =(1_3)x(z)+3d"b + lx(k)4-ux(k_，)也即：x(k) = (d - col)_1l(l - co)d + coujx(k_1) + co(d - col)-1 b(617)其迭代矩阵为b(1) = (d - col)-1 t(1 - co)d + coul o显然，sor方法收敛的充要条件是p (b®) <1关于松驰因子的选取我们有如下的定理：定理1： sor方法收敛的必要条件是：0«o<2证明：设b®的特征值分别是九，入2,，入n，则:det b®二九九2九n又 det bdetttd-c

31、ol)-1 f(1 -o)d+uh=( 1 -o)n 要使 sor 收敛，必有p (bo；) <1, 从而|det (b(o) |<1, b|j| (l-(o) n|<h 故有(xco<2o但是并不是对所有cow (0, 2), sor都收敛的。但如果方程组ax=b中系数矩阵a是 正实矩阵，则有如下结论：定理2：如果a是正定对称阵，且0<co<2,则解方程组ax二b的sor方法收敛。证明：设sor的迭代矩阵的非零特征值为九,x是对应的特征向量,则：b(ox=xx即：(da)l)“ (13)d+(ou x=xx,也即(13)d+o)u x=x(d-o)l)x从

32、而有：xt(l - 3)d + coux = xxt(d - ojl)x，这样我们得到：x 打(1 一 co)d + coux九=二t，xt(d 一(ol)x令 d=xtdx ,由于 l二u设xtux=a+bi 则壬丁 lx二a-bi,故d -+(o(a 4-bi) d 一 co(a 一 bi)12 i_ i (1 - o)d + coa + cobi |/|a|_/i d - coa + cobi |由于 | (1 一 co)d + coa 4- cobi |2= (1 一(o)d + coa2 + (cob)2| cl - coa + cobi |2= (d - coa)2 + (cob)

33、2由于 a 是正定阵，ifextax=xt (d-l-u)x=ck2a>0又因 0<co<2,从而(d - coa)2 - (1 - co)d + coa2 > 0,即：|九vl。从而知p (bw) <1, 故sor收敛。注： xt(d -(ol)x 0 o 否则：xt(d - col)x = 0 ,则 xt(d - cou)x = 0 ,从而xt(2d一col-(ou)x = 0,故：x7(2 co)d+a)(dl (7)x = 0,这是不可能的。由此定理知：前而一节的定理4是正确的. 例：设线性方程组ax=b系数矩阵a为1 0.8 0.8a = 0.810.8

34、0.8 0.8 1判别解此方程组的jacobi迭代法、gauss-seidel迭代法是否收敛，又问sor方法当 0<a）<2迭代法是否收敛？解：易知a是正定阵，故gauss-seidel迭代及sor方法当0sv2都是收敛的，而对-0.81-0.8 =-1.944<0,从而可知2d-a非正1 -0.8jacobi 迭代法，由于 det(2d-a)=det - 0.81-0.8 -0.8定，从而jacobi迭代不收敛。例：求解线性方程组ax二b,其中1- 0.300090-0.308981一 0.300091a=0- 0.46691-0.466910-0.27471-0.3089

35、80-0.27471b=（5.32086,6.07624厂&80455,2.67600/解：易知a为严格对角占优的正定阵，下面是分别用jacobi. gauss-seidel及sor方 法（0=1.16）计算的结果，方程组的精确解为x*=（8.4877,6.4275,-4.7028,4.0066/,（保留 五位有效数字）jacobi迭代：y（i）y（i）y（0y（i）1a1入2入3入40000015.320866.07624-8.804552.6760032338.48717888.48716556.42625436.4262848-4.7034945-4.70351084.00624

36、904.0062714guass-seidel 迭代1xx2x0000015.32085997.6729770-5.22196052.885514788.48321156.4227524-4.70637514.004254398.48549846.4251995-4.70455174.0054622158.48761756.4274669-4.70285754.0065823sor迭代方法(3=16)101y(i)a106.1721973x?09.1970072x0 -5.2320356xa403.649119968.48421196.4253206-4.70048864.004661178.48674396.4288020-4.70312024.0064926108.48762806.4275250-4.70284134.0065956从上可以看出sor有较快的收敛速度(如果3取得合适)。至于3取何值时达到最快的 收敛速度这里不作介绍，感兴趣可参阅相关著作。对于严格对角占优矩阵，sor方法有如下的结论：定理3：若a为严格对角占优阵，则当ovcovl时，sor方法收敛。证明：只要能证：当0<3<1时，sor的迭代矩阵：b®=(d-col)-i d+cou的谱半径小于1