Luận văn Thuật toán tìm không điểm cho tổng hai toán tử đơn điệu cực đại

Chu'dng3 THU~T TOAN GLOWINSKI - LE TALLEC 3.1 Gi6'ithi~uthu~HtoaD G§n day,Glowinskiva Le T,lllec (trong[13],[14],[15]) duaramQt thu~ttocln mdi rho bai tocln(P) , chungta g9i Ia sd d6 a.Trongd,~mg nguyencuano,sdd6adlt9Cvie'tnhltsau:ZO=Zo(chotrong9ill)vdik >0, Zk bie'tva vdi a E [0,1/2]quailh~giua cac zk,zk+l,zk+l-e,zk+edU9cxac dinhbdih~phltdngtrlnhsau k+8 Z - Z k a~t +A (z k+8 )+B(z k )=0, Z k+I-8 k+8 -z (1- 2a) ~t + A (zk+8 )+B(zk+I-8 )=0, (1) Z k+I k+I-8 -z a~t + A (zk+j )+B(zk+I-8 )=O. Ml;!cdichcuachungtaIa nghiencuusvhQitl;!va t6cdQhQitl;!cua sdd6 a khi A va B Ia toantti'ddndi~ucvcd(;lixacdinhtren9ill.Cl;!theIa chungtamu6nxac dinhdi~uki~ncuaA va B de daysinhra bdi sdd6 a hQitl;!Wi nghi~mcua(P). De co d(;lngtudngtvnhucacsdd6nghiencuutrudc,d§u tienchung taphaivie'tI(;lisdd6a dudid(;lngcuagiai thuc.Khi vie'tI(;li,chungta dU9c ke'tqua: Zk+I =(I+AIAtO - A jB)(1+A 2Bt(1 - A2AXI+AjAt(r - A]B)zkf ddayA]=a~t va A2=(1-2a)~t. Trang31 Dltoi di;tngnaychungtaco th~nh~ntha'ydug sd d6 e duQcphan tichthanh3 bltoCti~nva h)i.d daym6ithutl!cuatmintti'A vaB coth~ thayd6idltQC.ChliY r~ngkhi Al =A2thlsdd6eduQcphantichthanhmQt thu~ttmincuaPeaceman-RachfordvamQthu~ttoanti~n-lui. 3.2 HQi T1.,1Cua Sd D6 e Tronglu~nvan nay,chungta giftsti'r~ngbai toan(P) luauco nghi~m,tucla - -- ::JzE 91,a E Az, b E Bz ma a+b =0 . D~nghienCUDslj hQitl;lcuasdd6e (l), d~t AI=BL\tva A2=(1-2B)L\t, bi6nd6id5ngthucd~utientrongh~(1),chungtaco Zk+8_Zk +e~tA(zk+8)+e~tBzk =0, chuy~nv~taduQc zk+8(I+e~tA)=(I+e~tB)zk , tltdngdudng Zk+8= (1+A I A )-1 (1 +A I B~k = J AlA (1 - A 1B~k . Tltdng tl!, taHnhdltQCcft zk+1-8va zk+l Trang32 Zk+tJ =JA,A(I-AIB~k, k+l-tJ =J (I - A B L k+tJZ A2B 2)£' (2) Zk+1 = JAIA(I-AIB~k+l-tJ. Tie"p thea, b~ng cach loi;ti b6 Zk+8va Zk+1-8trong h<%phu'dngtdnh (2), chungta thudu'9Ccong thuc l~pnhu'sau.La'y zOEiRll.Cho k ~ 0 ,Zkbie"t,ta co Zk+l=JA,JI -AjB)JA2B(1-A2A)JA1A(1-AIB)Zk. Tronglu~nvan naychungtagia sli'r~ngAla da triva B la ddntrio Chungtavie"tcongthuctrendltdidi;lllgkhacb~ngcachdungbiend6iph\! sau(deki~mtrat\tctie"p) (I-vT)=;(yJ~T -IXI+~T), (3) d dayT la toantli'ddndi0,sdd68 trd thanh z'.' =J", [I-,-,B]J"" ~' [aJ"A -I][I-,-,B],2 ') d A l A,d ay a = +T.2 (4) f)~sosanhsdd68vd~thu~toanPeaceman-Rachford,taviet thu~t toanPeaceman-Rachford di;lngkhacla yk+l=J1J3[2J1cA-1][I-AB]yk. (5) VI the"d\tavao(4), chungta d~t k=1 A2 k V =J 1J3 [~][ a J )'IA - I ][1- AIB ]z ,j Trang33 khi Al =Az suyra a =2,tatha'ythu~tmintrengi6ngnh11'thu~tmincua Peaceman-Rachford.Va tad~t l+l =J;. J! -A1B]Vk+1I , Zk+ld<;lt d11'<;5ctU Vk+l t11'dngtv nh11'd thu~ttoantiSn-lui. Tac6th6la'yAl va Az E[O,CX)J,t6nt~ieE[O,+]va ~t>Oma Al=B~t , Az=(1-2B)~t, vdi AlB= va 2A]+A2 ~t=2A]+A2 . Tr11'dckhiquailHimdSnSvhQit\lcuasdd6e chungtaquailtam dSnsvhQit\lcuathu~toantie'n-luivathu~ttoanPeaceman-Rachford. DinhIj 3.1 Giasll'z* lamQtnghi~mcuabaitoan(P)va'A>a.Ne'utoantii'B- 1 la ddndi~um~nhvdi modulo(j >a ,thlday{xk}sinhbdi thu~ttoan tiSn-luiXk+l=J ",JI - AB]Xkthoamanba'td~ngthuc Ilxk+l-z*llz ~llxk-z*1I2-'A(2(j-'A~IBxk-z*112-'A21Iuk-Bz*1I2, d day k I ( k '\ B k k+1) A k+1 U ="i X -I\, X -x EX. Trang34 Ne'uA<2crthl day {Xk}bi ch~nva hQi tl;}Wi nghit%n:tZOOcua (P) .HdnmJa B {xk}~ B ZOOva uk ~-Bzoo. Ne'uA hayB la toantU'ddndit%um~nhvdi moduloyva 8 ,thls\ihQi I tvitnhttla tuy€ntinhvditys6 1- 52A(20"- A) I+A2y2 Dink If 3.2(LionsandMerrier( [21])) Gia sU'z* la mQtnghit%mcuabaitoan(P) va vdi A >O.Day {yk} sinhbdi yk+l=JAB[2JAA -III-AB)yk, ne'uchungtad~t ~k=[I+AB]yk , wk = [I-AB]yk, ~=[1 +AB]z* , w= [1 - AB]z* , . Vk, thlbtt ding thucsailthoaman I II~k+l - ~II ~Ilwk ~ wll ~II~k - ~II. Hdn nlia, (Byk - Bz* ,Yk ...:.z.)~ 0 khi k ~ +00. Trang35 Gia sit B thoaman\;j{xk}c 0(8) va x ED(B) ma {B(xk)}la dang, xk~;Z va (Bxk-Bx,xk -x)~o khi k~+<X),va x=;Z.Thl {yk}hQitl;}duynha'tWinghi~mz* cua(P). Bli' d€ 3.1 Gia sitT la mQttoclntit ddndi~uqtc d~idu'cjcdinhnghlatren91n vagiasLY~lvav lahaisothtfcdu'dng.£)~tr=1+if.Thltoclnttl' J /iT- I la lien tl;}CLipschitzvdi h~ngso L =max~,~}.Khi~ =v thl toclnttl' 2JpT- I lakh6ngdan. Ne'uT-1 la toclnttl'ddndi~um~nhvdi modulo1 > 0, va ~l<V<21 thl JUT - I laLipschitzvdih~ngsoL =if. Chttngminh Gia slYZl'Z2E91nvaxet Zi=~JpT- Ik choi=l,2. Do Zi+Zi - J Z. cho i=1,2,- - pT I r chungtaca ~[z, J ;z}T(; ;z,) , i =1,2. BdiT laadnai~u,chungtaca Trang36 1( ~+z\ ~+Z2 ~+Z\ ~+Z2 ) 0 8- z -Z - + - > ( )] 2 , - , ~ y y y y tu'dngdu'dngvdi (y - 1~Iz\ - z2112-IIZ\ - Z2112+ (y - 2)(z\ - Z2'z\ - Z2)~0. Ne'u y~2 (nghiala ~~v), dungb~td~ngthucCauchy-Schwarz,tasoy ra (y-Qlz] _Zzll2-II~ -z2112+(y-2~lz\-z21111;\+~211~O, nghiala l(y- 1~Iz\ - z211-11~- Z:IIHlz]- z211+II~- Z:IIJ2 0. Do bi€u thlicthli hai la khongam,soyra bi€u thucthunh~tclingkhong amva VIv~y II~- Z:II~(y- 1)Ilz] - z211=~Ilz \ - z211'- Ne'u y < 2 nghiala ~ <v thlb~ngcachdungb~td~ngthucCauchy- Schwarzl§nnii'achungtaco (y-l~lz\ -z2112-II~ -~112+(2-y)lIz\ -z2111111~\-Z-2II~O, nghiala l(Y-l~lz]-z211-11~- IIHlzl -z211-11~- IIJ~O. VI v~ychungtaco Trang37 IIZ:- Z211~Ill} - z211 ' nghlala ljJT - I la lien t\lcLipschitzvdi moduloL =max~,~}. Baygio gia sl( T-1 la toantli'ddndi~um 0va I-l<v<21.Thlb3'tdgngthuc(8)coth~thayb~ng ~>((y-l)(z}-zJ-(~ -~}(z}-Z2)-(~ -~))~ ~.,2>II(y-IXzl-Z2)-(~ -Z2r, tu'dngdu'dngvdi (y-Qlz} -Z2[[2-II~ -~~r +(y-2+ ~1(Y-l)Xz}-Z2'~ -~) ~~(y-lrllzl -z2112+;II~-~~r. Tli ~l<V <21, chungtaco r-2~;(r-l»O. Dungb3'tdgngtucCauchy-Schwarzchungtathudl«;1Ck€t qua (y-l)llz] -z2112-II~ -~112+(y-2+ 2~1(y-l)~lzl-z21111~-z211 ~;(y-lrllz1 -Z2[[2+;II~-~112, vaVIv~y, (y-l~lzl -z2112-II~ -~112+(Y-2+~1(y_1)XZJ-Z2'~ -~)~O. V~ychungminhhoanthanhvdib3'tdgngthuc Trang38 II~- ~IIs (y- qlZI - Z211. D~co du'Qck6tquahQit\lcuachungta,c~nchuysail bk =BZk , (9) (10) (11) (12) (13) b* =Bz* , - k k vk=z -zlb v=zk-Albk , k+l J )..2 r J It-v =).. 2B~ La )..2A - JY k . K6t quahQit\l d~utienc~nquailHimla tru'ongh<;1pAl ?A2.NghIalae E [1/3,1/2]. DinhIf 3.3 Giasaz* la mQtnghi~mcuabaitoc1n(P). Giasar~ngB-1 la ddn di~um~nhvdicr > 0 va 0<A2::;;Al <2a .Thlday{zk}sinhrabdisd d6e (4)chota Ilzk+l-z*II~llzk -z*II,Vk. Hdnll11'aday {zk}hQit\lWi nghi~mcua(P). Chlingminh B~ngcachlamgi6ngnhu'd tren,chungtachiasdd6e thanh2 thu~t toan: thu~toantien- llii va thu~toanPeaceman- Rachford.Chungta quailtamWihai toanti't J AIJI - AlB] va J A2B~:laJ AlA- I J . Trang39 B~ngeachchia,chungtaco Zk+l=JAlAli -AIBJvk+l. Ap d\lllg dinh ly 3.1,cho taba'td~ngthucsail IIZk+l_Z*112~llvk+l_Z*112-Al(2cr-Al~IBvk+l_b*112 -A~lluk-b*112, ddayuk E Az k+l.DoA1 <2cr,ba't'd~ngthti'ctrd thanh Ilzk+l_Z*112~[[Vk+l-z*r -A~[luk-b*112. (14) Va * AI' ]Z =J. B [-][ aJ A A-I V. AZI A 212 Th~tv~y,tuz* lamQtnghi~mcua(P),chungtaco - b* E Az * va v=z* - A lb' E (I+AlA~: VI v~y * J v =z ,AlA Va A2 I L [ * * L * JA2B~laJA1A -Ijv=JA2bLz-A2b JY=z. HdnnuaA vaB la tmlntli'ddndi~uqic d~i,giaithti'cJ A2E la kh6ngclan nentheob6d~3.1thItmlntli'~:lJAlA- Ij lalient\lcLipschitzvdih~ngs6 L =max{f;,l}.Dung(13),chotabatd~ngthuc Trang40 \Iv k+\ - Z* II ~Lllv~ - vii (15) baiainhnghIacuavkvav(nhln(11)va(12»vagiasa r~ngB-1la adnai~um(;lnhvoimodulo0",taco Ilv~-v112= Ilzk-z* -AI(bk -b*f II k * 11 2 2 11( k * ~ 1 2 ( k * k * )= z -z +A'I b -b~ -2AIZ -z,b-b ~ Ilzk-z*112-AI(20"-A\~lbk -b*112. (16) KthQp (14)va (16) chungtasuyra II k+1 * 11 2 2 11 k * 11 2 2 ( ~ I k * 11 2 2 11 k * 11 2 z - z ~L z - z - L A\ 20" - A\ ~b - b - A \ U - b .(17) Do A2~AI<20", chungtacoL=I va (17)choba'td~ngthlic sau: Ilzk+1 - Z*r ~IIz k - Z* II II k * 11 2 I ~ I k * 11 2 II k+\ .* 11 2 ]b - b ~A ,(2-oA1) ~z - z - z - Z Iluk+b*112~A\~~lzk-z*112-llzk+\-z*112]. Tli ba'ta~ngthuc Ill+1- z*112~Ill- z*11' chungtathudl(Qck€t qua {zk}ladongva day ~IZk - z*ll} lahQi~.Hai ba'td~ngthucsaucohamy la bk~ b* va uk~ -b* . Baygiochungtaxet ZOOla mQtgioih(;lncuaday{zk}.Tli A vaB ladongvatlibk=Bzkvauk-lEAzkchungtacob*=Bzoova-bEAzk .Co nghIalaZOOlamQtnghi~mcua(P). Trang41 CuO'icungb~ngcachdungchungminhtrong(Ref [24]trang885) chungtathuduQcke'tquala day {zk}hQitl;!Wizoo, D€ tlmto'cdQhQitl;!cuacuasdd6e , chungtac~ncob6d6 sail EIJ d~3.2. Gia SltT la loan tU'ddn di~uqtc d~im~nhxac dinh tren iRnvdi modulo~>O.ChoA >0 , thlgiaithucJ AT la lienh,lcLipschitzvdih~ng sO' 1 1+ T T Chungminh Gia Slt A>O) X,YEiRn lac{)dinhva- - XEJ;'TX va YEJ;'TY' Do dinhnghlacuagiai th((cloantU',chungtaco x - X E T~va Y - Y ETy. A A tuday,giaSltT la loantltddndi~uvdimodulocJ,chungtaco (x ~~- y ~y. ~- y)~ ~II~- yll' . nghlala (x- y,x - y) ~ (1 + A 1~lx- yl12. Dungba'td~ngth((cCauchy-Schwartz Trang42 VI v~ychung tathuduQcke'tqua Ilx-ylls~llx-yll. Eo?di 3.3 GiasO'Tla loantltddndi~uqtcd~ixacdinhtren91n. GiasO'r~ng T-1 la roanto'ddndi~um~nhvdimodulo0'>0(vdiT la ddntri). Thl T la loanto'ddndi~um~nhneuvachineuT-1 la lientvcLipschitz. Ch((ngminh Trudc lien chungtaquailsatr~ngT-1 la lien t\lCLipschitzapd\lng b6 de tntdc,Gia SltT la loan to'ddndi~um~nhvdi modulo1>0va xet (tl',:\J,(t2,xJ E T-1 . Do Tx]=t] va TX2=t2' chungtaco (t]-t2,x] -xJ;:::rllx] -x2112 Dungba'td~ngth((cCauchy-Schwartz,keo theo Ilx] -x21Is~llt] -t211 V~yT-1 Lipschitzvdih~ngs6 ~ Trang43 Baa l(;li,giasiTr~ngT-1 la lien tvcLipschitzvdi h~ngsf{L, thl, cho ta"tca (XptJ,(X2,t2)ET chungtaco (T:Xj- TX2,XI- X2)=(t]- t2,T-]t]- T-\) ~ allt] - t2112 II 11 2 II 11 2 >..!!-. -] - -] -..!!-. - - L' T t) T t2 - L' XI X2 d c1ay ba"tc1~ngthlic(1) do tinhc1dnc1i~um(;lnhcuaT-1 va ba'tc1~ngthlic (2) doT-1 Lipschitz.V~yT latmintuc1dnc1i~uvdimodulo:, . DinhIf 3.4 Gia Sl(r~ngcacgia thi€t cuab6 c1€3.1c1U9Cthoa.Themgia thi€t la A la toantuc1dnc1i~um~nhvdi modulo11>0 hayT-1 la lien tvcLipschitz vdih~ngs68 >O. Thl z* langhi~mduynha'tcua(P)vaday{zk}hQitvWiz* it nha't la tuy€nHnh,nghIala"v'ktaco . Ilzk+l - z*ll::;c,llzk - z*11 dc1ay I <I c] = I + A 117 n€u A la toantuc1dnc1i~um~nhva JI-,(1(2rr-,(1)< 1CI =. 0" n€u B-1lalientvc. Chlingminh Trang44 Quansattntdclien,dungb6as 3.3,B la tmintti'adnai~um~nhkhi B-1 la lient\lCLipschits.DoA +Bla loantti'adnai~um~nhz* la nghi~m duynh~tcua(P).Chungtaxet J;'IA,[I - PclB]JA2B va ~:[CXJAIA- I]. Tru'dclienloantt(J A ,A la khongdan,hdnnnakhiA la loantti'adnai~u m~nhvdi modulo11>0,dungb6as 2.2,no lien tl;lcLipschitzvdi h~ngs6 ~ I+A I'l . Dung (3) vdi =A1 va f.l =A 2 thlloantti'thilhaicoth~bi~udien la [1-AIBVA2~=~:[ftJA2B-1] d day fi=l+~.I Do B-1 la loan ttt adnai~um~nh , va do b6 as 3.1 vdi T=B,va lfiJ;'zB- I J la lien tl;lclipschitzvdi h~ngs6 ~:. Suyra[I-AIB]JA2Bla khongdan. Cu6icungdungb6as 3.1mQtl~nnnanhu'ngvdiT=A,loantitk€ ti€p : 2[a.lA I A - I] la lien tl;lc Lipschitz vdi h~ng s6I L=max{~:,l}=l do A2~A1. K€t h<jpcabaloanhi, chungtadedangk€t lu~nr~ng Ilzk+1- z*11~ ~llv~- vii (18) d day c = 1+~"111.N€u A la loan tti'adn ai~uvdi ~=1 vdi cac tru'ongh<jp khac. HdnmIa,dungchangminhainh19(3.1)va(16)chungtaco Trang45 Ilvk-vl12~IIZk_Z*W-AI(2cr-AI~lbk-b*1I2 ~llzk_Z*112(19) Ne'uB-1 la lien t~cLipschitz vdi h~ngs6 0> 0 thl Ilzk -z*ll~ollbk - b*11 Ap d~ngvaba'ta~ngthlic(19)taauQc Ilv'k-v112~[I-AI(:G2-AI)]lzk-z*'12 (20) V~y tu (18) va 20) chung ta suyra r~ng Ilzk+l-z*II~CI"Zk -z*11 V~y I <1 CI =I +A /7 n€u Ala roantuadnai~um(;lnhva J I--.<,(20--'< I) <1CI = Ii' ne'uB-1 la lient\lClipschitz Chuy3.1 . Khai ni~ma§u tieDla h~ngs6 c1khongph\l thuQcthallis6 ,,1.2'Tn(dc tieD Al <20-la c6 ainh, ch<;)ll,,1.2 <AI khonganhhuangt6caQhQi t\l tuy€n tinhcuasda68.Tuynhien,chungtalienkiSmtrab~ngHnhroan th~cnghi~m. . LienquailWivaitrocuaAItrongt6caQhQit\ltuye'nHnh,chungtad€ dangnhlnrar~ng,khiA la toaDtuadnai~uvdimodulo11>O,aanhgia chocj trdthanht6thdnkhi AIXa'px12cr,keotheoc I ~ 1+;1]17 .Khi B-1 ]a lient\lclipschitzvdih~ngs60>0, cI=~1- ;: auQcdaubgia t6t,lingvdi AI=0-. Trang46 Khi A la toaDtttddndi 0 va B-1 Ia lien l\1c Lipschitzvoih~ngs60>0,keotheotuchungminhcuadinh193.2,ti s6 hQitl;1la 1-"-1(2"-"-1) 1 c1=,/ 02 .1+"-,11. Bdi b6 d6 3.3 ,Gia sa "B-1 la lien tl;1CLipschitz" thl tu'dngdu'dng vdi "B-1 la toaDtU'ddndi<$um~nh", VI v~ym<$nhd6 cuadinh ly 3.2co th€' d6i cong thucb~ngcachthaythe'gia thie'tnay b~nggia thie'td§u lien. TrongtntonghQpnay,chungtadinhnghjaloanta B ddndi<$um~nh vdi 8modulo,bdib6d63.3,Ii =)i th"ih~ngs6 cI co th€ bi€u di€n du'di d~ngtu'dngdu'dngla - ~l- AJ20"- Al}fcI- . 1+All Tsengchungminhr~ngtacdQhQil\1chothu~tloanTie'n-Luila 1- AJ (20'- A I~2 C = I. 2 ~ l+AI11~ no IOnhdnCI. Va'nd6 nayco trongchungminhdjnhly 3.4,chungta khong quail Him tdi loan tU' IJcIA(I - AIR) nhu'ngchungta tachchungfa .1 va (I - AIB).A,A Djnh ly ke' tie'p noi ke't qua Aj<Az,nghiala 8E[O,+]. hQi l\1 ? cua sd d6 e khi Trang47 Dinhlj 3.5 Gia saz* la mQtnghi~mcuabai tmin(P) va B la tmintll'ddndi~u m~nhvdi 8> Ovalien tl)cLipschitzvdi h~ngs6 8> O.Ne'uA < 28 va Ai E lFA2,A2J (d day C2=1- -<1(2:2--<1)),th'iday {zk}hQit\lWi z*, nghi~m duynhfftcua(P).HdnmJa, '\jk taco Ill+l-~*II~::F lll-zl Chlingminh Ap d\lngb6 de 3.3,B la tminta ddndi~um(;lnh, v'i v~yz* la nghi~mduynhfftcua(P).Giasa Al<A2va Al<20:. Th'i(17) la dungvdi L -<2 , h / /= T,va c ling taco I\Zk+1-lor ~(~:Y~IZk-z*112-Al(2(J-AI~lbk - b*112j (21). Do B-1 la lien t\lc Lipschitz vdi h~ng s6 8 > 0 va tU Bzk=bk va Bz* =b* chung taco bfftd£ngthlic sau Ilzk-z*II~8I1bk- boIl Cho phepchungtake'tlu~ntu(21)r~ng IIl+1-z*11~ ~:F:lll-z*11 d day Trang48 C2=1-A.l(2a-A.l). a 2 . Do AI <20" , Suy fa C2<1.Ben qmh do, bai dinhnghjacuacrva8,chung taco U::;(j va 82 -2UAj +A~~U2-2UAj +A~=(u-Ajl ~O vdi c2~O. Tltdnghi, khi FzAz <Al chungta co r~ng ~:Fz <1 .V~ychungta co day {zk}hQi tv Wi z* vdi t6cdQtuy6n tinh. Chuy3.2 Chu y r~ng di~u ki~n Al E lFAz,AzJ thl tudng dudng vdi f) E ll+1}"~-J. Trang tntongh0 con la mot diu hoima. Nglt<;JCl~ivdi tntongh<;JpAz::;Alt6cdQhQitv cuaday {zk}phv thuQc vaogia tri cua Ivz.T6cdQhQitv t6thdnkhi Ivzgiamva xa'pxi Ivj' Do do chungtachiquailHimWi tntongh<;JpAz::;Al . Trang49