《2022年2022年解线性方程组的预条件AOR迭代法 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年解线性方程组的预条件AOR迭代法 .pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Improving AOR method for consistent linear systems?Yan-lei CHANG?Guo-feng ZHANG?Jing-yu ZHAOSchool of Mathematicsand statistics,Lanzhou University,Lanzhou 730000, P.R.ChinaAbstractFor solving the linear system AX= b, di?erent preconditionedGauss-Seidel methods havebeen proposedby many authors.In thi
2、s paper,we considerpreconditionedAOR iterativemethods with preconditioners(I + R) , (I + S) and (I + S + R ). In addition,the convergenceand comparisontheorems of two preconditionedAOR methods withpreconditioners(I + R)and (I + S + R ), respectively,are established.Numericalexample is also given to
3、illustrateour results.Keywords: Preconditioner;L-matrix;M-matrix;AOR method;SOR method;MathematicsSubjectClassi?cation(2000): 65F10,65F501IntroductionConsider the followinglinear system:Ax = b,(1.1)where A Rn n, b Rnare given and x Rnis unknown.For any splitting,A = M -N withdet(M ) = 0, the basic i
4、terativemethodfor solving (1.1) isx(i +1)= M- 1Nxi+ M- 1b,i = 0, 1,.For simplicity,withoutloss of generality,we assume throughoutthis paper thatA = I -L -U,(1.2)where I is the identitymatrix,L and U are strictlylower and upper triangularmatrices obtainedfrom A, respectively.Then the iterationmatrice
5、sof the classical AORiterativemethodin 4 isde?ned:Lrw= (I -rL )- 1(1 -w)I + (w -r )L + wU ,(1.3)where w and r are real parameters withw = 0.The spectral radiusof the iterativematrixis decisive for the convergence and stabilityof themethod,and the smaller it is, the faster the method converges when t
6、he spectral radius is smallerthan 1. In order to accelerate the convergence of iterativemethodsolving the linear system (1.1),preconditionedmethodsare often used. Thatis,P Ax = P b,?Theproject-sponsoredby SRFfor ROCS,SEMand ChunhuiProgramme.?E-mailaddress:?Correspondingauthor.E-mail:gf E-mailaddress
7、:1http:/1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 2where P, called the preconditioner,is an non-singularmatrix.DenotePA = D?-L?-U?.Applyingthe AOR method, we get the correspondingpreconditionedAOR iterativemethods whoseiterativematr
8、ices areL?rw= (D?-rL?)- 1(1 -w)D?+ (w -r)L?+ wU?,where w and r are real parameterswithw = 0, D?, L?and U?are the diagonal,strictlylowertriangularand strictlyupper triangularparts of PA, respectively.In 8, Morimotopresented a modi?edJacobi and a modi?ed GaussSeideliterativemethodbyusing the precondit
9、ionerP = I + R, whereR =000 00000 00.0000 00- an 1- an 20 - ann - 10.In 3, Gunawardenapresented a modi?ed Jacobi and a modi?edGaussSeideliterativemethodwithpreconditionerP = I + S, whereS =0- a120 000- a23 0.000 - an- 1n000 0.In 9, Nikiet al. considered a GaussSeideliterativemethodwith preconditione
10、rP = I + S +R = I +R, whereR =0- a120 0000- a23 00.0000 0- an - 1n- an 1- an20 - ann - 10.In5, Y.Liet al.considereda preconditionedAORiterativemethodwithpreconditionerP = I + S,?Ax =?b,(1.4)where?A = (I + S)A and?b = (I + S)b withS =0- a120 000- a23 0.000 - an- 1n000 0.Now, let us consider the ?rst
11、preconditionedlinear system,http:/2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 3?Ax =?b,(1.5)where?A = (I + R )A and?b= (I + R)b withR =000 00000 00.0000 00- an 1- an 20 - ann - 10.and the second preconditionedlinear systemAx =b,(1.6)w
12、hereA = (I + S + R )A = (I +R)A andb = (I + S + R)b = (I +R )b withR =0- a120 0000- a23 00.0000 0- an - 1n- an 1- an20 - ann - 10.We express the coe?cientmatrixof (1.5) as?A =?D -?L -?U,(1.7)where?D = diag (?A),?L and?U are strictlylower and upper triangularmatricesobtainedfrom?A ,respectively.By ca
13、lculation,we obtainthat?D = I -E,?L = L -R + RL + F,?U = U,where E and F are diagonal and strictlylower triangularmatrices obtainedfrom RU .The coe?cientmatrixof (1.4) can be expressed as?A =?D -?L -?U,(1.8)where?D = diag (?A),?L and?U are strictlylower and upper triangularmatricesobtainedfrom?A ,re
14、spectively.By calculation,we also obtainthat?D = I -E1,?L = L + F1,?U = U -S + SU,where E1and F1are diagonal and strictlylower triangularmatrices obtainedfrom SL .The coe?cientmatrixof (1.6) can be expressed asA =D -L -U,(1.9)whereD = diag (A),L andU are strictlylower and upper triangularmatricesobt
15、ainedfromA ,respectively.By calculation,we also obtainthatD = I -E1-E2,L = L -R + RL + F1+ F2,U = U -S + SU.Where E1and F1are diagonaland strictlylower triangularmatricesobtainedfrom SL , E2andF2are diagonal and strictlylower triangularmatrices obtainedfrom RU .http:/3名师资料总结 - - -精品资料欢迎下载 - - - - -
16、- - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 4Applyingthe AORmethodto the preconditionedlinearsystems (1.4)(1.5)(1.6),respectively,we have the correspondingpreconditionedAOR iterativemethodwhose iterativematricesare?Lrw= (?D -r?L)- 1(1 -w)?D + (w -r)?L + w?U,(1.10)an
17、dLrw= (D -rL)- 1(1 -w)D + (w -r)L + wU,(1.11)and?Lrw= (?D -r?L)- 1(1 -w)?D + (w -r)?L + w?U.(1.12)This paper is organizedas follows.In 2, some preliminariesare given.In 3, we prove theconvergence theorems.In 4, we discuss comparedtheorembetween (I + S) and (I + S + R)correspondingAOR method.Numerica
18、ltests are in 5.2PreliminariesFor convenience,we shall now brie?yexplainsome of the terminologyand lemmas used in thenext sections.Let C = (cij) Rn nbe an n n real matrix.By diag(C),we denote the n ndiagonal matrixcoincidingin its diagonal with cii. For A = (aij), B = (bij) Rn n, we writeA B if aijb
19、ijholds for all i, j = 1, 2,., n. CallingA non-negativeif A 0, (aij 0; i, j = 1,., n),we say thatA -B 0 if and only if A B . These de?nitionscarry immediatelyover to vectorsby identifyingthem withn 1 matrices. ( ) denotes the spectral radius of a matrix.De?nition1 (10)A matrixA is a L-matrixif aii 0
20、; i =1,., n and aij 0, for all i, j =1, 2,., n; i = j .De?nition2 (10)A matrixA is an M-matrixif A = sI -B, B 0 and s (B ), where (B)denotes the spectral radius of B.De?nition3 (10)A matrixA is irreducibleif the directed graph associated to A is stronglyconnected.De?nition4 Let A be a real matrix.Th
21、e representationA = M -N is called(1) regular if M- 10 and N 0;(2) weak regular if M- 10 and M- 1N 0;(3) M-splittingif M is an M-matrixand M- 1N 0;(4) H-splittingif -| N | is an M-matrix;(5) H-compatiblesplittingif = -| N |.Lemma2.1(10)Let A 0 be an n n irreduciblematrix.Then,(1) A has a positive re
22、al eigenvalue equal to its spectrix radius.(2) To (A ), there corresponds an non-zero eigenvector x 0.(3) (A) increases when any entry of A is increased.(4) (A) is a simple eigenvalue of A .Lemma2.2(1)Let A be an non-negativematrix.Then,(1) if x Ax for some nonnegativevector x, x = 0, then (A).(2) i
23、f Ax xfor some positive vector x, then (A) . Moreover,if A is irreducibleandif0 = x Ax = x,x = Ax, Ax = xfor some non-negativevector x, then (A ) and x is a positive vector.http:/4名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 5Lemma2.3(1
24、1)A is monotoneif and only if A is non-singularwith A- 1 0. Here a realmatrixA is called monotoneif Ax 0 impliesx 0.Lemma2.4(10)Let A = M -N be a regular splittingof matrixA. Then, A is non-singularwith A- 1 0, if and only if (M- 1N ) 1, where (M- 1N ) = (A- 1N )1 + (A- 1N ) 0 and A is an irreducibl
25、eL-matrix.Then the iterativematricesLrwand?Lrwassociated to the AORmethod applied to the linearsystems (1.1)and (1.5),respectively, are non-negativeand Lrwis irreducible.Proof.From that A is an L-matrix,we have L 0 is a strictlylower triangularmatrixand U 0is a strictlyupper triangularmatrix.So (I -
26、rL )- 1= I + rL + r2L2+ + rn- 1Ln - 1 0.By (1.3),we haveLrw= (I -rL )- 1(1 -w)I + (w -r)L + wU = I + rL + r2L2+ + rn- 1Ln - 1(1 -w)I + (w -r)L + wU = (1 -w)I + (w -r )L + wU + rL (1 -w)I + rL (w -r )L + wU + (r2L2+ + rn - 1Ln- 1) (1 -w)I + (w -r)L + wU = (1 -w)I + w(1 -r )L + wU + T.whereT = rL (w -
27、r )L + wU + (r2L2+ + rn - 1Ln - 1) (1 -w)I + (w -r)L + wU 0.So Lrwis non-negative.We can also get that (1 -w)I + w(1 -r )L + wU is irreduciblefor A isirreducible,hence Lrwis irreducible.By (1.10),we have?Lrw= (?D -r?L )- 1(1 -w)?D + (w -r )?L + w?U = (I -r?D- 1?L )- 1(1 -w)I + (w -r)?D- 1?L + w?D- 1
28、?U= (1 -w)I + w(1 -r)?D- 1?L + w?D- 1?U +?T.where?T = r?D- 1?L (w -r )?D- 1?L + w?D- 1?U + r2(?D- 1?L )2+ + rn - 1(?D- 1?L)n- 1(1 -w)I + (w -r )?D- 1?L + w?D- 1?U 0.So we have?T 0 and?Lrw 0 from?D 0,?L 0 and?U 0.As?Lrw, we have?Lrwisnon-negative.http:/5名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -
29、- - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 6Similarly,we have the followinglemma.Lemma3.4Let A andA are the coe?cientmatricesof the linearsystems (1.1)and (1.6).respectively.If 0 r w 1(w =0)( r=1), Ais an irreducibleL-matrixand 1 -n0, 1 -aii +1ai+1 i 0, (i = 1, 2,., n -1). Then th
30、e iterativematricesLrwandLrwassociated tothe AORmethod applied to the linearsystems (1.1)and (3.3),respectively,are non-negativeandLrwis irreducible.Theorem3.5Let Lrwand?Lrwbe the iterativematricesof the AORmethod given (1.3)and(1.10),respectively.If0 r w 1(w =0)( r=1), Ais an irreducibleL-matrixand
31、 if1 -n 0. Then(1) (?Lrw) (Lrw) if (Lrw) 1.Proof.From Lemma 3.3, it is clear that Lrwis non-negativeand irreduciblematrices.Thus, fromLemma 2.1 there exists a positive vector x , such thatLrwx = x,where (Lrw) or, equivalently,(1 -w)I + (w -r )L + wUx = (I -rL )x.(3.1)Therefore,for this x 0,?Lrwx -x
32、= (?D -r?L )- 1(1 -w)?D + (w -r )?L + w?U x -x= (?D -r?L )- 1(1 -w)?D + (w -r )?L + w?U - (?D -r?L )x= (?D -r?L )- 1(1 -w)I -(1 -w)E + (w -r)L + (w -r )(- R + RL + F ) + wU - (I - E ) + r (L -R + RL + F )x= (?D -r?L )- 1(w -1 + )E + (w -r )(- RA -E) + r (- RA -E)x= (?D -r?L )- 1(-1)(1 -r )E + (-1)w
33、- r + rwR (I -rL )x= (-1)(?D - r?L )- 1(1 -r )Ex +w- r + rwR(I -rL )x = (-1)(?D - r?L )- 1C.Where C = (1 -r )Ex +w - r + rwR(I -rL )x 0.(1)If0 1, then?Lrwx -x 0. Therefore,?Lrwx x . By Lemma 2.2, we get (?Lrw) = (Lrw).Theorem3.6Let LrwandLrwbe the iterativematricesof the AORmethod given (1.3)and(1.1
34、1),respectively.If0 r w 1(w =0)( r=1), Ais an irreducibleL-matrixand1 -n 0, 1 -aii +1ai+1 i 0, (i = 1, 2,., n -1) . Then(1) (Lrw) (Lrw) if (Lrw) 1.http:/6名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 7Proof.From Lemma 3.4, it is clear th
35、at Lrwis non-negativeand irreduciblematrices.Thus, fromLemma 2.1 there exists a positive vector x , such thatLrwx = x,where (Lrw) or, equivalently,(1 -w)I + (w -r )L + wUx = (I -rL )x.(3.2)Denote (D -rL )- 1B , E3= E1+ E2,L = L + D. We know B 0, E3 0 andL 0.Therefore,for this x 0,Lrwx -x = (D -rL )-
36、 1(1 - w )D + (w -r )L + wU x -x= B (1 -w)D + (w -r)L + wU - (D -rL)x= B (1 -w)(I -E3) + (w -r)( L + D ) + w(U -S + SU) - (I -E3) + r (L + D )x= B (w -1)E3+ (w -r )D + w(- S + SU ) + E3+ rDx.Denote D = H -E3, H = - R + RL + RU + SL = - RA + SL. By using of (3.2),we getLrwx -x = B (-1)(1 -r)E3+ (w -r
37、)H + w(- S + SU ) + rHx= B (-1)(1 -r)E3+ (-1)( S + R )(I -rL ) + r(1 - )RA + r(-1)SL x= (-1)B (1 -r)E3+ S +w -r + rwR (I -rL )x.Where N = (1 - r )E3+ S +w- r + rwR(I -rL )x 0. Hence we obtain that(1) If0 1, thenLrwx -x 0. Therefore,Lrwx x . By Lemma 2.2, we get (Lrw) = (Lrw).RemarkIt is well known t
38、hat,when w = r , AOR iterationis reduced to SOR iteration.So wecan easily get the followingcorollaries.Corollary1.Let Lwand?Lwbe the iterativematricesof the Successive Overrelaxation(SOR)iterativemethodassociated to (1.1) and (1.10), respectively.Under the hypothesis of Lemma3.3.We get(1) (?Lw) (Lw)
39、 if (Lw) 1.Corollary2.Let LwandLwbe the iterativematricesof the Successive Overrelaxation(SOR)iterativemethodassociated to (1.1) and (1.11), respectively.Under the hypothesis of Lemma3.4.We get(1) (Lw) (Lw) if (Lw) 1.For obtainingstrictlyinequality,we suppose some conditionand obtainthe followingthe
40、oremand lemma.http:/7名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - 8Lemma3.7Let A Rnn(n 3) andA are the coe?cientmatricesof the linearsystems(1.1)and (1.6),respectively.If A is irreduciblewith aii +1ai+1 i 0(i = 1,2,., n -1) and thereexi
41、sts an i, i n -2 such that ani= 0. ThenA is irreducible.SoLwris irreducible.Proof.Firstwe show thatA is irreducible.The assertionfor n = 3 is obvious.Now we onlyconsider the case when n 4. LetA = ( aij). Thenaij=aij-aii +1ai +1 j 11 i n,-n- 1(j = ) k=1ankakji = n.(3.3)By (3.3)and the assumptionof th
42、e theoremwe have ann - 2 - ann - 1an - 1n- 2 0 and ai +1 i0, i = 1,., n - 2 and aii +2= aii +2- aii +1ai +1 i+2 0, i = 1,., n - 2. This implies that the directedgraph (A) ofA has some paths such as (n - 1,., 3, 2,1) ,(n, n - 2), (1, 3,., n) and (2, 4,., n -1)when n is odd, and (n -1,., 3, 2, 1), (n,
43、 n -2),(1, 3,., n -1) and (2, 4,., n) when n is even,and hence there is a closed path (1, 3,., n, n - 2,n - 3, n - 1, n - 3,., 4, 2, 1) when n is odd, and(1, 3,., n -1,n -2, n, n -2, n -4,., 4, 2, 1) when n is even. HenceA is irreducible.SoLwrisirreducible.Underthe hypothesisof Lemma3.6 and Lemma3.7
44、, we obtainthe followingtheoremandcorollary.Theorem3.8Let LrwandLrwbe the iterativematricesof the AORmethod given (1.3)and(1.11),respectively.If 0 r w 1(w = 0)( r = 1). We get(1) (Lrw) (Lrw) if (Lrw) (Lrw) if (Lrw) 1.Corollary3.Let LwandLwbe the iterativematricesof the Successive Overrelaxation(SOR)
45、iterativemethodassociated to (1.1) and (1.6), respectively.We get(1) (Lw) (Lw) if (Lw) (Lw) if (Lw) 1.Theorem3.9Let LrwandLrwbe the iterativematricesof the AORmethod given (1.3)and(1.11),respectively.If0 r w 1(w = 0)( r = 1), A is an non-singularirreducibleM-matrixand aii +1ai +1 i 0, i = 2, 3,., n
46、-1, n 0. Then (Lrw) (Lrw) if (Lrw) (1 - (Lrw)x,Lrwx (Lrw)x.Form theorem 2.1.11(1),we obtain (Lrw) (Lrw) 1.Corollary4. Let LwandLwbe the iterativematrices of the SOR methodgiven (1.3) and (1.11),respectively.If 0 w 0, i =2, 3,., n -1, n 0 Then (Lw) (Lw) if (Lw) 1.4Comparedtheoremof (I + S) and (I + S
47、 + R)In this section, we establish compared theorem between (I + S) and (I + S + R) correspondingAOR method.http:/9名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 10Theorem4.1Let A be an non-singularM-matrix,?LrwandLrwbe the iterativematri
48、ces of theAORmethods given (1.12)and (1.11),respectively.Ifn - 1k =1- ankakj 0, j = 1, 2,., n -1, 0 n- 1k=1ankakn 1, and 0 r w 1(w = 0)( r = 1). Then (Lrw) (?Lrw) if (?Lrw) 1.Proof.From (1.4)(1.6),we haveA -?A = (I + S + R )A -(I + S)A = RA 0.Then?A- 1A- 10.Denote?A = (I + S)A =1w(?D -r?L ) -1w(1 -w
49、)?D + (w -r)?L + w?U = ES-FS,ES=1w(?D -r?L),FS=1w(1 -w)?D + (w -r)?L + w?U.By calculation,we obtainE- 1R 0, E- 1S 0,FR 0, FS 0.So,?A = ES-FS, andA = ER-FRare regularsplitting.Moreover,FS-FR=1w(1 -w)?D + (w - r )?L + w?U -1w(1 -w)D + (w -r)L + wU =1w(1 -w)E2+ (w -r )(R -RL -F2) 0.Then FS FR 0, and?A-
50、 1FSA- 1FR 0.by the monotone of functionf (x) =x1+ x, we have (Lrw) (?Lrw).Corollary5.Let A be an non-singularM-matrix,?LwandLwbe the iterativematricesof theSOR methodgiven (1.12) and (1.11),respectively.Ifn- 1k =1- ankakj 0,j = 1, 2,., n -1, 0 n- 1k=1ankakn 1, and 0 r w 1(w = 0)( r = 1). Then (Lw)