BẤT ĐẲNG THỨC BIẾN PHÂN TỰA ĐƠN ĐIỆU VÀ THUẬT TOÁN XẤP XỈ GIÁ TRỊ
NGUYỄN VĂN THÙY
Trang nhan đề
Mục lục
Phần mở đầu
Chương1: Ký hiệu và định nghĩa.
Chương2: Nguyên lý bài toán bổ trợ.
Chương3: Thuật toán xấp xỉ giá trị .
Kết luận
Tài liệu tham khảo
17 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1841 | Lượt tải: 3
Bạn đang xem nội dung tài liệu Luận văn Bất đẳng thức biến phân tựa đơn điệu và thuật toán xấp xỉ giá trị, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
CHV0NG 2
A '" " ,:?
NGUYENLYBAITOANBOTR0
, .,
2.1 Thu~itoancdso
Trong [2, 3, 4], mQtnh6mcac thu~ttoandtSgiai bai toan (1) dil dtiQc
th6ngnha'ttrongclingmQtkhuonkhBva dtiQcgQiIa nguyen15'bai toanbB
trQ.Y ttidngchinhcuathu~ttoannayd1.,1'aVaGnh~nxetsanday.
Xet hambBtrQM :X ~ 9i Idi m;:tnhvakhavi GateauxtrenX , va Ela
mQtso'dtiongchotrudc.Vdi x E X chotrtidc,xetbaitoanbBtrQ:
(11) mill (M(y) +( EF(x) - M'(x),y) ).
Y EOXad
Gia sa y (x)Ianghi~mcuabaitoan(11).
A.p dl.lllgbB d€ 1.5vdi FI( . ) =M( .) Idi,khavi GateauxtrenX va
F2(-) =< EF(x) - M' (x),.) la hamIdi ( vi tuye'ntinh). Theo(9) , Y (x) thoa
- - -
(M' (y(x», y - y(x» +(E F(x) - M' (x),y) - (EF(x) - M' (x),y(x» 2 0
v Y E Xad,
hoi:icd d;:tngnit gQn
(12) (M'cY(X»+EF(x)-M'(x),y-Y(X»20 VYEXad.
Ne'uy(x)=x thi (12)suyra
(EF(x),y-X)20 VYEXad,
tlicla
(FcY(X»,y-Y(X»20 VYEXad,
lien y (x) Ia nghi~mcuabai toan(1).
D1.,1'atrennh~nxet nay,xay d1.,1'ngthu~toanco sd sanday dtSgiai bai toan
(1).
14
Thu(it tmln 1 ( Thu(it tmln cosO')
Cho tru'deday cae sO'du'ong{8k, k E ~} 0
(i)
(ii)
(13)
(iii)
Chc;mdii!mxucltphat XOEX tily yo
abuack, bierXk, tinh Xk+1 :=y(Xk) b!ing vi?c giai bai loan b5 trq
(11) vai x thaybai Xk, 8bai 8k
mil}cl(M(Y)+(8k P(xk)-M'(xk),y»).
YEX
Neu II Xk+l - Xk II nho hcJn melt giai hC;lncho truac thi dang 0 Nguqc
IC;li,tra v~buac(ii) vai k +- k +1 0
B6d~2.1
T~lim6ibuaccuathu~tloantren,Xk+la nghi?mduynhC[tcuabai loanbien
ph{m:
(14)
vai:
(15)
(pk(Xk+l),X-Xk+l):2: 0 \1XEXad ,
pk(X)=8kp(Xk)+M'(x)-M'(Xk) 0
Chung minh.
Go? ? (14)
/ h
'
hOA k+l, k+l / 1,la su co al ng H~mx va y , We a
(pk(xk+l),yk+l -xk+l):2: 0,
Suy ra
( P k(y k+1), Xk+1- Yk+1) :2: 0 ,
(pk(Xk+l)_pk(yk+l),xk+l - yk+l):::;0,
ho~cvie'td d,;lllgkhac
(16) (M'(xk+l)-M'(yk+l),xk+l_yk+l):::;O,
M~tkhac,doM Iaham16im~nhnentheom~nhd61.3secoh~ngsO'
a>0 saocho
(17) (M'(Xk+l)-M'(yk+l),Xk+l _yk+l):2:a II Xk+l _yk+1112 ,
15
Tli (16)va (17)suyraXk+l=l+l . .
2.2 DjnhIy hQit\1d1!atrenHnht1!adondi~um~nh
Trangphftnnay,chungta se chungminhslj hQiW cuathu~tloan 1
tranghaitnionghQpvoi loantll'F trangbailoan(1)Ia dontr!vadatr!,voi
giii thie'tF Iatl!adcJndi~um~nh.
2.2.1 TruonghQptm!ntll'dontrj
Caegiathie't
1. F Ia tl!adondi~um~nhvoi'hangsO'e lIen xad,
2. F Ia lien WcLipschitzvoi hangsO'A lIen X ,
3. M' Ia dondi~um~nhvoi hangsO'b lIen xad.
B6 d~2.2
V6'igid thilt F la tZ!adondi?um(;mh,nlu bai loan(1)co nghi?m,thl nghi?m
do la duynh{[t.
Chungminh.
* * d
Giii sabailoan(1)cohainghi~mIa Xlva X2E Xa .tucIa
(18)
(19)
* * ad
(F(XI)' X - Xl ) ~ 0 '1/X EX,
* * ad
(F(X2),X-X2)~O 'l/XEX .
Thay X=X; trong(18),taduQc
* * *
(F(XI),X2-Xl) ~0 .
DoF Ia tl!adondi~um~nhnentant~ihangsO'e >0saocho
* * * * * 2
(20) (F(X2)'X2 -Xl) ~ ell X2 -Xl II .
*
M~tkhac,thayX= Xl trong(19)thi thuduQc
(21)
* * *
(F(x2),X2 - Xl)::; 0 .
* *
Tli (20)va (21),suyra xl =X2 . .
16
DjnhIy 2.1
Gidsa riinghili loan(1)conghi~mx* . Ne'uM' la dondi~umqmhvai hiing
sffh trenXld, thi t6ntqziduynhatnghi~mXk+lcila hili loanh8 trei(13).Ne'u
F la tf:Cadondi~umqznhvai hiings6 e tren;:ad( thix*duynhd't) va lien tl;tc
Lipschitzvaihiings6A tren;:adva:
\j k E ~, ex0,~>0,
A +~
thiday{Xk}hQi tl;tmqznhv~x* . Hon mla,ntu M' la lien tl;tCLipschitzvai
hiings6B tren;:ad, thicouaclu(,fngsai s6:
(22)
(23) Ilxk+l-x*II~~(~ +A)lIxk+l-xkll.e c;
Chung minh.
a) Sf:Ct6ntqzivaduynhd'tnghi~m.
Ap dl.mgb6d~1.5va (12),taco Xk+lla nghi<%mcuabai toan(13)ne'u
vachine'u
(24) <M'(Xk+l) - M'(Xk) +c;kF(Xk), x - Xk+l) ~0 \j X E Xad .
Ap dl.mgb6d~1.1vdiA la M', f la M'(Xk),cpla c;kF(Xk)thiA va cpd~
tha'ythoa3giathie'tdftutiencuab6d~.Takit3mtfagiathie'tcu6i.
R5rang0 E domcpvaM' dondi<%um(;lnhvdih~ngso'bnen
< M' (x) - M' (x*), x - x* ) ~b II x - x* 112 ,
thayx*=0 thi tadu<;)c
< M' (x),x ) ~b II X 112 +< M' (0), x ) .
Dodotaduoc
<M'(x),x)+cp(x)~bl!x 11+<c;kp(xk)+M'(O),x)
II x II II x II '
suy fa
17
< M' ex),x) +cp(x)-} +ex) khi IIx II-} +ex).
IIx II
Do v~y,theob6 d~1.1thibai tmln(24)luautant<,tiit nha'tmQtnghi~m,
nghi~mnayduQcgQiIii Xk+l.
Tinh duynha'tcuaXk+lsuyra tub6 d~2.1.
b) Day (XkjhQitl,im~mhv~x*.
*
x langhi~mct'iabaitoan(1)nen
* *
(25) <F(x ), x - x ) ~0
EHit
v X E Xad.
(26)
* *
ct>(x)=M(x ) - M(x) - < M' (x),x - x) .
Vi M' dondi~um<,tnhnentub6d~1.2,taduQc
(27) ct>(Xk)~ b II xk - x* 112 ~0 .
2
X6t s1fbie'nd6i ct'iact>t<,tim6ibuckcuathu~toan1.
6.t+1:=ct>(Xk+l)- ct>(Xk)
=M(Xk) - M(Xk+l) - <M'(Xk) , Xk- Xk+l ) + <M'(Xk) - M'(Xk+l), x*- Xk+l).
Vi M' dondi~um<,tnhnentub6 d~1.2,taduQc
M(Xk+l) - M(Xk) - <M' (Xk), Xk+l- Xk) ~ b II xk+l - xk 112.
2
Dodo
sl:=M(Xk)-M(Xk+l)_<M'(Xk),Xk_Xk+l)::::; - b Ilxk+l-xk 112.
2
Thay x =x*vao(24)thi taduQc
(28) S2 :=< M'(Xk) - M'(Xk+l), x* - Xk+l)
::::;Sk <F(Xk), x* - Xk+l )
::::;Sk <F(Xk) - F(Xk+l) , x* - Xk+l) +Ek <F(Xk+l) , x* - Xk+l).
Do F tl,l'adondi~um<,tnhva
< F(x*) , Xk+l- X* ) ~0 ,
nen
18
(29) (F(Xk+l) ,Xk+l~X*);::: ell xk+l-x* 112.
Do d6
S2:::;- e skllxk+l - x*112+ sk( F(xk) - F(xk+l), x* - xk+l).
V~y
k+l
L'.k
:::;_lll xk+l - xk 112- e Ek II xk+l - x * 112+Ek(F(xk) - F(xk+l), X* - xk+l )2
:::; _lll xk+l - xk 112- e'Ek II xk+l - x * 112+Ek II F(xk) - F(xk+l) IIII x * - xk+l II2
:::;-lll xk+l - xk 112- e Ek II xk+l - x * 112+EkA II xk+l - xk IIII xk+l - x * II2
-
(
vib
II
k+l k
II
EkA
II
k+l *
11)
2
(
A2E2k k
J
II
k+l *
11
2- - - x - x - - x - x + - eE x - x
-Ii J2b 2b
:::;E2k
(A2 - +] II xk+l - x * 112.2b E
2
"1'. k 2eb ~ e A +/3 D d/Y1 a . 0 0
A +/3 E 2b
E2k
(
A 2 - ~
J
<- /3a2.
2b Ek 2b
V~y
(30) L'.~+1:::;- a2/3II xk+l - x* 112.
2b
Tli d6 ta suy ra L'.t+1:::;0 tilc la <D(Xk+l):::;<D(xk).Do v~y,day {<D(Xk)}
giamva bi ch~ndtioibdi 0 lien hQiW. Do d6, L'.t+1-:; 0 va tli (30)suyra
day {Xk}hQiW m(;lnhv6 x* .
c) Changminh(23).
*
Thayx =x vao(24)vado(29),tadtiQc
(M'(xk+l)-M'(xk),X* _Xk+l) +Ek(F(xk)-F(xk+l),x* -xk+l);:::
;:::-Ek(F(xk+l),x* -xk+l)
19
;::::Ek e II Xk+l - X * 112.
M~tkhac,doM' lien WcLipschitzvdi h~ngso'B va F lien WcLipschitzvdi
h~ngso'A nen
:::;B II Xk+l - x * IIII xk+l - xk II,
:::; A II Xk+l - x * IIII Xk+l - x k II .
Dodotaco
Eke!! Xk+l -x* 112:::;II Xk+l -x* IIII Xk+l -xk II (B+EkA),
tlic la
II Xk+l - x' II ,; : (~+A) II Xk+l - Xk II .
.
2.2.2 TruonghQ'ptmintii'datrj
Trongph~nnay,chungtasexettru'onghQpF la loantii'datIt,giatricua
F lucnayla illQtt~pconcuaX. Bai loan(1)lucnaytrdthanh:
* dTIm x EX" SCWcho
* * * * d
::3r E F(x ) : ;::::0'Vx E Xa .
TrongtnronghQpF Ia loantii'da trt,cacdint nghlatti'1.5de'n1.13
tliongling choant X<;ldatri seco dliQcb~ngcachthayF(.) bdi r E F(.).
Chingh<;ln,dint nghlatt,(adondi~uill<;lnhcuaant X<;ldontridliQcthaythe'
bdidintnghlasanday:
::3e > 0, 'V Xl, X2 E xad , 'V rl E F(Xl), 'V r2 E F(X2),
(31)
(32) ;::::0=> ;::::e II Xl - X2 112.
Thu~tloancosdvftnnhlicu,nhlingdoF(Xk)Ia illQtt~phQp,nenla'yba't
ky rk E F(Xk)thayehoF(Xk)trongloan tii'dontIt, va day {Ek}trongtrliong
hQpnaythoa
(33)
-tco . -tco
Ek >0, LEk =+CXJ,L(Ek)2 <+CXJ
k=O k=O
20
Thu~ttmin 2
Bdt dauta dilm xuc{tphatXOE X. Tc;zibuckk, bie'tXk,am Xk+lbangcach
gidi bai loanbdIrq:
(34) mill (M(X)+(ck rk -M'(Xk),X»),
x E Xad
/0 k
F(
k
)VCllrEx.
Caegiathie't
Trangphftnnay,cacgiathie'tv~ngillnguyennhu'trong2.2.1.Riengtint
lient\lCLipschitzcuaF du'Qcd6ithanh
(35) ::3a> 0, ::3~>0 saochoV x E Xad,V r E F(x), II r II ~a II x II +~.
Chti Y 2.1
Ke'tquacuab6 d~2.2v~ndungtrangtru'onghQpF la loantli'da trio
Chungminhdi~unaytu'dngt11nhu'chungminhb6d~2.2,chuy dingluc
* * ~ * *
nayF(x})va F(X2)du'QcthayboiVrEF(x})va VsEF(X2)'
Djnhly 2.2
Gid sa bai loan (31)co nghi?mx*. Ne'uM' la dondi?u mc;znhvdi hangso
b trenxad,thi tbntc;ziduynht/tmiltnghi?m~+1chobai loanb6 trq (34).Ne'u
F la ti!adondi?u mc;znhvdi hangso'e tren)(ld(x*la duynha't) va thoaman
(35),vane'uday{I} thoaman(33),thiday{Xk}hili tl;tmc;znhv~x*.
Chung minh.
a) Si! tbntc;zivaduynha'tnghi?m.
Chung minh hoan loan tu'dngt1fnhu'dinh 1:92.1, ChI thay F(Xk)bdi
k k
)V r E F(x .
b) Day {Xk}hili tl;tmc;znhv~x*.
x* la nghi~mcuabailoan(31)ne'uvaChIne'u
* * * * d
::3r EF(x):(r,x-x ):::::0 VXEXa.
1.5va (12),taco Xk+lla nghi~mcuabai loanb6 trQ(34)
(36)
, ? '
Ap d\lngb6de
ne'uvaChIne'u
21
(37) (M' (Xk+l)- M' (Xk), X - Xk+l) +8k (l, x - Xk+l ) ~0
~. k
F(
k
)VOl rEX.
\j X E xad ,
Xet ham
* *
(x)=M(x ) - M(x)- ( M'(x),x - x) .
VI M' la dondi~um<;lnhnentub6 d~1.2,tadtl-Qc
(Xk)~ b II xk -x* 112~O.
2
llt+l : =(Xk+l)- (Xk)
=M(Xk)- M(Xk+l) - (M'(Xk) , Xk- Xk+l) +(M'(Xk) - M'(Xk+l),x* - Xk+l).
VI M' dondi~um<;lnhentub5d~1.2,taco
M(Xk+l) - M(Xk) - ( M' (Xk), Xk+l- Xk) ~b II xk+l - xk 112.
. 2
Do v~y
Sj :=M(Xk) - M(Xk+l)- (M' (Xk), Xk- Xk+l):::;- b II xk+l - xk 112.
2
Thay x =x* vao(37),taduQc
S2 := (M'(Xk) - M'(Xk+l), x* - Xk+l)
< k (
.k X* - k+l)- 8 I, X
< k (
k * k
)
k k k k+1
-8 r,x-x +8(r,x-x).
Thay x =Xkvao(36)thitaduQc'
* k *
(r ,x -x )~O.
M<.Hkhac, F tl,(adon di~um<;lnhnen
(rk , Xk- x* ) ~ ell Xk - x* 112.
Dodo
S2:::;-e8k Ilxk-x*112+ 8k(rk,xk-xk+l).
V~y
llt+1 :::;- b II Xk+l - xk 112-e 8k II xk - x * 112+8k II rk IIII Xk+l - xk II2
[
k
~
2 k 2
:::;_b Ilxk+l-xkll-~llrkll +lillrkIl2-e8kllxk-x*1I22 b 2b
22
(
k
)2 *
::::;~ IIrk 112-eEk II Xk - X 112.
2b
Tli (35) suy ra
(38) Ilrkll::::;allxkll+~::::;allxk-x*ll+allx*II+~ .
M~t khac ta co
( u +v )2::::;2( U2+V2) '\I u, V E iR .
Do v~y,tli (38) suy ra
IIr~::::; ~2(a211 Xk -x* 112+(a II x* II+~)2)2b 2b
2
a k * 2 l
(
*
)
2
::::;-11x -x II +- a IIx II+~
b b
::::;Yllxk_x*112+8,
trongdo
y =~ 8 =(a IIx*II+~)
b' b
Do do
,0.~+1::::;-eEk IIXk -x* 112+(Ek)2(y II xk -x* 112+8).
Voi bat ky s6 tlf nhien N, ta co
N-l N-l
I,0.~+l::::;I(-eEk IIXk -x* 112+(Ek)2(YII Xk -x* 112+8)),
k=O k=O
ke'thQpvoi (27), ta duQc
b IIxN - x * 112::::;<:D(xN)
2
N-l
[ ](39) ::::;<:D(xo)+ I -eEk IIXk -x* 112+(Ek)2( Y IIXk -x* 112+8)
k=O
N-l
::::;<:D(xo)+I(Ek)2(Yllxk -x* 112+8),
k=O
SHY ra
23
N * 2
II x -X II ~
° o 2 28N-1 N-1 2 *
~ 2cD(x ) + 2(£ ) Y IIxO-X* 112+- L(£k)2 + L ~(£k)211 Xk -X 112
b b b k=0 k=l b
N-I
~l1N + L~Lk Ilxk-x*f,
k=l
ydi
28 N-1
N = 2cD(xO)+ 2y (£°)211XO-X* 112+- L(£k)2,
11 b b b k=O
k - 2y
(
k
)
2
~L - - £ .
b
Ta CO
\i k, II Xk - X * 112~ SUp II Xl - X * 112,
l::;k+1
"k 2y" k 2
LJL =- L./£ ) <+00
kE~ b kE~
bdi vi L(8k)2 <+00.
kE~
Vi I(8k)2 0 saGcho l1N ~11, \iN E ~.
kE~
Luc nay,haiday{II Xk - x* 112}va {l1k}thoagiathi6tcuab6d61.6,suy
ra day {II xk - x* 112}bi ch~nvadododay{Xk}bi ch~n.
D~t f(x) =II X - X* 112,theo dinh 1y gia tri tIling binh
f(x) - fey)=(f(z), x - y)
*
=2(z-x ,x-y),
vdi z =AX +(1- A )y, A E (0, 1) .
Ta co
* *
If(x)-f(y)I~21Iz-x 1IIIx-yll~2supllz-x 1IIIx-yll,
ZEK
vdi K la baa16iciiaday {Xk},va doK bi ch~nnensuyra
(40)
Han Hila,tu (39)taduQc
f lien WcLipschitz.
24
N-l N-l N-l
eL Ek II Xk - X* 112:::;<D(XO)+ L Y(Ek)2 II Xk - X* 112+8L (Ek)2 .
k=O k=O k=O
Vi day {II Xk - x* 112}bi ch<;inen
k * 2
3p >0: II x -x II :::;p \t k,
suyra
N-l N-l
el>k Ilxk -x* 112:::;<D(xO)+(yp+8)L(Ek)2 .
k=O k=O
Vi 2.:(8k)2 <+00nen tli tren suy ra
kE~
(41) 2.:Ek II xk - x* 112 <+00 .
kE~
Thay x =Xkvao (37) ta du<;jc
+Ek 20,
Wcla
-bllxk+l-xk 112+Ek Ilrk 1IIIxk+l-xk 1120.
Ke'th<;jpvoi (35) thi tadu<;jc
II Xk+l - Xk II :::; ~II rk II :::;Ek (exII Xk II +0) (ne'u II Xk+l - xk 11:;t0) .
b b
Vi day {Xk}bi ch<;innend<;it~=exII x:11+0 thi tli trensuyra
(42) II Xk+l -xk II:::; ~Ek .
(42)vftndungtrangtru'ongh<;jpII xk+l - xk II =O.
Tli (40),(41),(42)tasuyra cacgia thie'tcuab5 d@1.7du<;jcthoaman.Do
d6 tadUdc
hm Ilxk_X* 11=0.
k-Hoo
V~y,day {Xk}hQitumanhv@x* . .
25
2.3 DinhIy hQitv dtfatrentlnheMitttfaDunn
Trangph~nnay,chungtasechungmint slfhQit~lcuathu~toan1trang
tnionghQptoan111F trangbai toan(1) Ia dontri va F Ia tlfaDunn.
Caegiathie't
1. F co tint cha't11!aDunnvdi hangso'E trenXad,
2. F lien WcHoldertrenXadngmaIa
:3c>0vaD> 0saGchoV x,y EXad,II F(x) - F(y) II::;D IIx - y Ilc ,
3. M' Ia dondi~umanhvdihangso'b va lient~lCLipschitzvdihangso'B
A
X adtren .
DinhIy 2.3
Oidsabaitoan(1)conghi?mx*.NtuM' la dondi?um{;mhwJi hangsob
tren;:ad, thit5ntqziduynh(Jtnghi?mXk+lchobaitoanb8tre!(13).Hannlla,
ntuF la tf!aDunnvaihangs(/E tren;:advane/u:
(43) \-I k \0..> k+I , I--'> ,
E+~
thi dc7y{ F(Xk) } h()i tl,{v§ F(x*), II Xk+l -Xk II h()itl,{v§ a.va dc7y{ Xk}bi
ch4n.Ntu themgid thilt la M' lien tl,{cLipschitzvaF la lien tl,{CHolder tren
;:ad,thim6iddm tl,{ylu cuadc7y{Xk} la m()tnghi?mcua(1).
Chung minh.
a) Sf!t5ntqzivaduynhatnghi?m.
Slf tan t~iva duynha'tnghi~mciia bai toanb6 trQ(13) da:duQcchung
mint d dint 192.1.
b) Sf! h()i tl,{.
Bat
(44) \P(x, E)=cD(x) +D(x, E),
vdi
(45)
* *
cD(x)=M(x ) - M(x) - ,
* *
D(x, E)=E.
26
Theo (27),taco
cD(xk) ::::b II x k - X * 112.
2
*
Do x Ia nghi~mcuabai roan(1)lien
(\ k k - k
<
* k- *
»~l(X , S ) - S F(x), x x - 0 .
Dodo
(46) '¥(Xk,Sk);::::bllxk-x*112::::0.
2
Ta xet s11'bi€n d6i cuaham'¥ doi vdi m6ibudccuathu~tloan 1.
B~ngcach dungcac ky hi~uva tinh loan tltongt11'nhu trongchungminh
cuadinhIy 2.1,taduc;fC
1:+1:='¥(xk+1,sk+1)- '¥(Xk,sk)
=cD(Xk+1) - cD(xk) +Q(Xk+1, Sk+1) - Q(Xk , Sk)
k+! * k+1 * k * k *
= s] + S2+S < F(x ),x - x ) - S <F(x ), x - x )
=s] +S2 +S3 ,
vdi
S] ~ - b II xk+1 - xk 112,
2
< k<F(
k
)
* k+1
)S2- S x,x - x ,
k+] * k+l * k * k *
S3= S <F(x ), x - x ) - S <F(x ), x - x ).
Ta co
S2~ Sk<F(Xk ), X* - Xk+1 ) =Sk <F(Xk), X* - Xk ) +Sk <F(Xk ), Xk - Xk+l ) .
DoF cotinhcha'tuaDunnva
* k *
<F(x ), x - x );::::0,
lien
<F(Xk),Xk-x*)::::! II F(xk)-F(x*) 112.
E
Dodo
k
S2~-~ II F(Xk) -F(x*) 112+sk<F(Xk),Xk _Xk+1) .
E
27
M ~ kh/ d k+l < k ~';it ac, 0 E - E nen
< k * k+l k )S3- E (F(x ), X - X .
V~y
k
S2+S3 :;;-~IIF(Xk)-F(x*)112 +Ek(F(Xk)-F(x*),Xk_Xk+l).
E
Suy ra
r:+1 :;;-~llxk+l_Xk 112-~ IIF(Xk)-F(x*) 112+
+ Ek II F(Xk) - F(x*) 1111Xk - Xk+l II .
Vi
Ek II F(Xk) - F(x *) 11IIXk - Xk+l II :;; (Ek)2 II F(x k) - F(x *) 112+2~
+~ II Xk - Xk+l 112,
nentadudc
rk+l < ~-b Ilxk -xk+1112-Ek
(
~-~
)
IIF(xk)-F(X*)112.
k - 2 E 2~
V /' '\ b ' k 2~ h' /01I\,< va ex<E <- t 1taco
E+~
rk+l :;;-b-~llxk+l-xk 112- ex~ IIF(xk)-F(x*)112.
k 2 E(E +~)
. Ne'u Xk+l=Xkva F(Xk ) =F(x* ) thi tU(25),suyra Xkla nghi~mcuabai
roan(1).
. NguQc l';ii,ta duQc
r:+1 =\Jf(xk+l,Ek+l)- \Jf(Xk,Ek) <0 ,
do do day {\Jf(Xk, Ek)} giam, bi chi;indudi bdi 0 nen hQi tl,l.Do do, ta co
r:+1 = \Jf(xk+l,Ek+l)- \Jf(Xk, Ek) ~ 0 khi k ~ +00.
Do v~ytaduQc
II xk+1 - X k II ~ 0 khi k ~ +00,
28
IIF(xk)-F(x*)II--+O khik--++oo.
Hon nlia, day {'¥(Xk, 8k)} hQi tl.llien bi ch~nva do do, tU(46) suy fa
'¥(Xk,8k) ~~II Xk -x* 112.
2
V~yday{II xk -x* II} bi ch~nvadododay{Xk}bi ch~n.
Bay giG,gia sii'z la mQtdit5mtl.lyeticila day {Xk},vagia sii'day con {Xkj}
hQi tl.lv~z.
Ta viet l~i (24) la
(M' (Xk+l) - M' (Xk ), X - Xk+l) +8k ( F(xk ), X - Xk+l) ~0 v X E xad .
M' lien WcLipschitzvdi h~ngsO'B lien
II M'(Xk+l)-M'(Xk) II ::=;Bllxk+l-xkII.
M~tkhac,VI 8k>a lien
(F(xk), X - Xk+l) ~- B II xk+l - xk III1 x - xk+l IIa
vX E Xad .
Do do taduoe
(F(xki),x-xki+l)~_Bllxki+l-xki II Ilx-xki+l II VXEXad.
a
VI
F(xki)--+F(x*), xkj --+z, Ilxki+l-xki 11--+0 khi ki --++00,
lien
(47) (F(x*), x - z) ~0 V X E Xad .
Ngoai fa, VI (F(z), x kj - z) --+0, ki --++00lien lieU F(z) =0 thlfa rangz Ia
nghi~mcua(1).
NeuF(z)"*0 , d~t
yki = Xki - (F(z), Xki -z)
II F(z) 112 '
thl
(48) ( F(z) , ykj - z) =(F(z), Xki - Z ) -
29
- 12(F(z),Xki-z).(F(z),F(Z»=0
II F(z) II
D@thfty
Ilykj-xkill::;;llxki-zll~O,
nen
II yki - Xki II ~ 0, ki ~ +00 .
Do F lien tueHoldernen
II F(yki ) - F(xki ) II ::;;D II yki - Xki Ilc (e>O,D>O).
Do d6 tadude
(49) F(yki ) ~ F(x *) .
Mat khae
Ilyki -zll ::;;llyki-Xki 11+llxki-zll,
nen
II yki - z II~ 0 khi ki ~ +00.
Do F tlfaDunnnentil (48)SHYra
(F(yki), yki -z):2:~IIF(yki)-F(z)11 .
E
Cho ki ~ +00thi SHYra
(50)
Til (49) va(50) SHYra
F( yki ) ~ F(z)
*
F(z ) =F(x ) .
Do d6 (47) trdthanh
( F(z), x - z ) :2:0
V~yz langhi~meuabailoan(1).
v X E xad.
.
30