'.
-

•

4^'

BO GIAO DUG VA DAO TAO
DAI HOC QUOC GIA HA N O I
n^l/CJNG DAI HOC KHOA HOC Tl/NHIEN
&

NGUYEN VAN HUNG

M O T S O PHUONG P H A P H I E U CHJNR

GIAI BAI TO AN DAT KHONG CIliMH
Chuy^n nganh
Ma so

: Toan hoc linh (can
: 1.01.07

^\
LUAN AN PHO^ TIEN
SI KHOA HOC TOAN - LY

NGUdl HUdNG DAN KHOA HOC: TIEN SI - PIIAM KY AN13

i^u-^rz-?.>^:(ss.-:-

i^ir,

^:T:

*

Ha nOi - 1996


MUC LUC
L51 noi dau

1
CHUONG I
PHUONG PHAP COMPACT THU HEP CAI BIEN


CHUONG III
M O T S O PHUONG PHAP LAP - HIEU CHINH
§1. Phirang phap Gauss - Newton hi6u chinh (RGN)
§2. Ki^m tra di^u kien B] cua Bakushinski
§3. Phuang phap hieu chinh Gasse - Newton g'an dung
§4. Phirang phap Seidel - Newton hieu chinh va bai toan phi tuyS'n cong huang
I - Phuomg phap Seidel - Newton (SN) vd phuomg phap
Seidel - Newton hieu chinh ( RSN)
II - Syc hdi tu dia phuomg cua phuomg phap RSN
III - Bdi todn Men tudn hodn cho phuomg trinh Duffing - Van derpol
nil - Bdi todn bien tudn hodn doi v&iphuomg trinh Van derpol

40
41
46
52

Phan ket luan
Phu luc
1- Bai toan - Lcfi giai
2- Thuat giai va chuong trinh

66
67
67
72

Tai lieu tham khao

gg

B.A , Laverientiev

M.M ,Vasin J.M, Ivanov V.K,

Bakushinski A.B, Gaponenko Yu .L, Bertero M.P, Nashed M.Z, Groetsch C M . , ...
Khai niem dat chinh theo Hadamard la:
Xet phirang trinh
Ax = y
Trong do A la toan tu dua khong gian T5p6 X vao khong gian Topo Y
1 - Vai m6i y e Ytbn tai x e X
2 - Nghiem x la duy nhat.
3 - Nghiem phu thu5c lien liic vao cac du kien cua bai loan.

(0,1)


Ne'u vi pham it nhSit m6t trong ba dieu kien tren, ihi bai toan dugc goi la bai toan dat
kh6ng chinh,
•

M6t VI du didn hinh khi A la toan tu* tuye'n Ifnh hoan toan lien tuc, con X, Y
la cac khdng gian Banach v6 ban chieu, khi do:
00

i-ImA ^ YvalmA = u {Ax:||x||< n)latap pham tru thirnha't.(dieu nay CO nghia
n=l

la bai toan (0,1) giai dugc khOng phai vdi moi y e Y).
ii - Ne'u A ' : Y-> X c6 ton tai thi cung khong lien tuc. Di^eu nay chung to nghiem
cua bai toan (0,1) khong phu thuoc lien tuc cac du" kien ban dau
min
x e Xo

chf cap truong, B5, qu6'c gia, qu6'c te' va dugc bao cao tai Xeminar toan hoe tfnh toan
cua Dai Hoc Tong Hgp Ha Noi (Tien sy Pham Ky Anh chu tri). Hoi nghi khoa hoe 35
nam thanh lap khoa Toan - Co - Tin DHTHHN hoc nam 1991, Hoi nghi khoa hoc khoa
toan DHSPHN 2 1992, H5i nghi khoa hoc khoa Toan - Co - Tin hoc DHTHHN 1994,
Hoi nghi quoc te' vt bai toan ngugc 1995 ( Tai thanh pho Ho Chf Minh).


CHUONGI
PHUONG PHAP COMPACT THU HEP CAI B I C N

$1 - Ma dau:
Xet phuang trinh
Ax = y

•

(LI)

6 day A la toan tir phi tuye'n, X,, Y la cac khong gian vector t6p6. Gaponenko
Yu.L [24,25] nam 1982 da de xua't phuang phap c6 ten la "compact thu hep". Ong da
xay dung dugc cac tap Vg gbm huu han phan tir sao cho:
V xg e Vg => II X5 - Xd II < diam V5 + 5 -> 0 ( 5 -> 0)
Arsenin V.Ia , ([5], nam 1989 ), xet bai toan (1.1), trong do A : H ^ C[a,b], H la
kh6ng gian Hilbert. Thay vi biet ys e C[a,b] chi bie't m thi hien {y'sl "'1, trong do han
mOt nua y'5 thoa man dieu kien.
II / 5 - y d ||c x* (5 -> 0 )
Cung nhu phuang phap Tikhonov AN, phuang phap Robust kh6ng cho phep danh gia
sai s6' cua nghiem g'an dung.
Y tuang cua Gaponenko va ky thuat cua Arsenin da dugc chung toi sir dung de xay
dung thuat toan giai bai toan (LI) va da danh gia dugc tO'c dO hoi tu cua nghiem g^an
dung.
52 - Cac gia thiet cua bai toan.
Xet phuang trinh (1.1), trong do A : X -> C[a,b], A la toan tir lien tuc, X la
khdng gian Banach. Goi Xi la mfen xac dinh cua phie'm ham on dinh D.[x].


-6

Xi c: X va ta c6

OO

Xi ==uK(n)

1) la (p(h) luai huu ban cua tap compact K(n), c6
nghia la:
Vxe K(n), 3 Xh e S (n,h) : ||xh - x|| < (p(h)
Trong do 0 < (p(h), la ham dan dieu tang tren ( 0,1 ]

va lim (p(h) - 0
h->0

Xet phie'm ham Ibi

:

llyc-ysllc ^ V.5

iii/ 3 G > 0 :

I(|)8(yi)- yd(t) +Q6

5T

iiiii/

T =To I < 1 khi to < yd (t) - Q5

aR8(t,x)

0

5x
S3 - Thuat toan Compact thu hep dang Robust.
Gia sir ta c6 he thiic.
b

De dang chiing minh dugc cac danh gia sau:
(l)5(yd) 1 : l/qj+ 1/pj = 1, Tir he thue (2.2 ) va (3.2). suy ra he thii-c (3.1).
Gia su 5 > 0 la m6t sC c6 dinh tuy y ta chon day hn > 0 va so N = N (5) sao cho.
(p(hN-0 >5>(p(hN)
So db tinh toan theo phuang phap Compact thu hep cai bien dang Robust gbm cac
buac sau day:
Budfc 1, Chon ri = 1 va dat
V, {VE S(r,,hi) : (|)5(Av) < GT((p(h,),ri) + co(5)l
Ne'u V] = (j)

la'y

r2 = ri +1
0 )
thi
va

I (t)8(Av) - Uyd 1 ^ 0 (5 -> 0 )
V = Xd

Chung minh day dii bd de nay xem trong [5 ].
0 sao cho
n[vn] VQ. Khong ma't tinh tong quat ta c6 the coi
n

11

Vn —> Vo ( n -^ 00 ), va do do:
Q [ V o ] < Q[Xd] - £ ^


Suyra: Xh e

VN=V5

Bd d'e dugc chi^ng minh [].
Nhan xet 3,2: VN ^ i?, doi vdi moi N > No ta luOn c6 rw < rNo ^ No va
VN 0
Chvcng minh: Gia sir ngugc lai di^eu do kh6ng xay ra, khi do tbn tai hai day{Vk")va
so 8 >0 dd:
||vk"-Vk-||>s>0

(3.4)

Vai Vk* e VNk c: Ko, k = 1,2 .... Do Ko la tap Compact nen khCng giam tdng quat
chung ta c6 the coi rang

Vk" -^ v"

khi k -> o)

Khi do ta cung c6 Avk" -^ Av"*". Mat khac
(|)5 (Avk") < GT((p(hNk ),rNk) + co(5).
Tir do suy ra.
0 < (1)5 (Av*) < co(5) -> 0 ( 5 -> 0)
Theo bd de (3.1) ta c6:

v* = Xd e X . Dieu nay mau thuan vox (3.4 ).


nhat thie't phai thue hien dung N but^c nhu da trinh bay a tren.
BireJc 1: Lay r, = 1 va thanh lap tap hgp:
Vi-{v:veS(hn,ri):(|)8(Av) < G^F(5,ri ) + co(5))
Ne'u Vi ^ (|), ta la'y tuy y xs e Vi
Khi do: || X5 - Xd || < diam Vi + cp ( hN) ^ diam Vi + 8
Thuat loan dimg a day
Ne'u Vi ^ (|), ta la'y r2 = ri + 1 va thue hien buac 2 ....
Budc ( n < N) dugc thirc hien ne'u

Vi,... V„-1 = ([>

Khi do rn = n, ta thanh lap tap Vn
Vn-{v:veS(hn,rn):(l)6(Av) < GT(5,rn ) + co(5))
Ne'u Vn ^ (t>, ta la'y xs e V, tuy y, thi
II xg - Xd II < diam Vn + 5 va thuat toan dung lai.
Ngugc lai Vn = (j), dat rn = n +1 va quay lai h\x6c n cho de'n khi n < N thi dung
Nhan xet 3.5: Ne'u rn > n[Xd ], thi V„ ?^ cj) khi do thuat toan a nhan xet (3.4) dimg lai.
Dfeu nay chung to: Ne'u Qxd la mot so nguyen thi so bubc cua thuat loan la fifxd ].
Ne'u il[Xd ] khong phai la so nguyen thi so' bu6e cua thuat toan la [Q[Xd ]]+ 1. Vay so
bu(5fc ciia thuat toan khOng phu thu()c vao 5 khi 5 du be.
Nhan xet 3.6: Ne'u tien nghiem bie't rang Q[Xd] < R thi ta thanh lap tap
V5={v:veS(hN,R):(|)5(Av) < G4^(6,R)+co(5)}
va thuat toan chi c6 mot bu6e.


12

Nhdn xet 3.7: Ta c6 thd thay gia thie't (3.1) bang gia thie't i^^{y^) < (3(5), trong do
P(5) > 0 la ham lien tuc, p(8) ^ 0 khi 5 ^ 0. Khi do c6 ihi la'y tap V„ nhu sau:
•
1) lim diam V„ + „i-1 - 0
N

Chvcng minh : Gia sir ke't luan ciia bd rfe (4.3) kh5ng dung, khi do tbn tai
Vk" e Vn ^ + n^ -1 va sb e > 0

Sao cho llvk"*"-Vk'll > e > 0

vai k =: 1,2,...

Vi Vn e K (nk) - la compact, k - 1,2,... nen khong giam tdng quat ta gia sir rang:
Vk* ~ > Vo" k h i k - > 00

Tac6(i)5(Avk*) < G^((p(hnj^+ . i y i ) , r n ^ +n,^ i) + co(8)
K

K

Cho k - ^ 00, ta dugc: (j)6(AVo'^) < (x»(8)
T&bdd^e (3.1) suyra:
AVo"^ = yd = Ax*

(4.1)


m

Theo each xay dimg thi 0

1-

Ns

+
Ns

1
—
Ns

Cho s -> OO thi dugc he thiJc
1 - a < Q [ x * ] - [Q[x*]] < 1 - a

(4.2)

Theo each xay dung day ( Vk" } ta c6
mk

"N - ^ T -^f^^'' k

Suyra

Nk

mk

n
\


Til (4.1) . (4.3) va tinh duy nha't cua x* nen Vo" = x*. Difeu nay mau thuan vai gia
thie't phan chung.
Bd de dugc chung minh []
Djnh ly 4.1: Dugc suy ra true tie'p tu: bd de nay.

§5 - Truomg hgp ve phai va toan tur khong biet chinh xac
Trong muc nay chung ta gia thie't rang: Trong phuang trinh (1.1) ta khong bie't A ma
chi bie't A ^
A^ : X -> C[a,b] La toan tur lien tuc thoa man.
a - II A^v - Av|| < u(|a,Q[v]) V v e Xi, u(ja,s) la ham lien luc khOng am, kh5ng
giam theo JJ, va s, vbi mdi s cb dinh u(]a,s) —> 0 khi p ^ 0 va u(o,s) = OV s > 0
b - V v i , V 2 E X i : llA^Vi. A^V2|| < T ( | | v i - V 2 | | , r ) ;

Trong do r = max(n[vi ],Q[v2]), ham T(t,r) thoa man gia thie't trong S2
c - Ta van gia thie't (|)5( yj) = (t)5(AxT) < co(8).
Cac gia thie't khac giiJ nguyen nhu trong 52.
Chon day (hn) kh6ng tang; 0 < h„ < 1, hn —> 0 khi n —> oo, 8 va p ed dinh,
N = N(8,ii) chon tijr he thitc (p(hN. 0 > ji + 8 x p (hN ).
Budc 1 : Dat ri = 1 va xay dung tap hgp
V, = (v: V G S(h,,ri) : U^^'v) < G[T((p (hi),ri) + u(vi,ri) ]+ co(8))
Ne'u W\^^ia. la'y r2 = ri


16-

Ne'u Vi = (|) ta la'y r2 = ri + 1
Sau do thue hien budc tie'p theo
Bir6c n ( n < N )
Vn = {v: V e S(hn,rn) : UA^'v)


Dieu nay chihig to xi, e VN hay VN ^ (j).
Bd dfe dugc chung minh.[]


17

Bd de 5.3 : Day tap compact (Vg^} co ve didm Xdkhi p, 8 -> 0
Chicng minh: Gia sir 6\tw do kh6ng xay ra, khi do tbn tai hai day{ Vk" 1 0 dd.
(5.1)

||vk*-Vk-||>e>0,k=l,2....

Do V c= Ko nen {Vk* ) c= Ko, kh6ng m&i tinh tdng quat chiing ta cb ihi coi rang:
Nk

Vk* ~> v"^ khi K - ^ 00

Taco:
U^x^-)

^ G[^((p( h ) , r ) + u(P, r ) ] + «(5)
k

k

k

Tur day suy ra:
lim
0

Theo bd d'e 3.1 ta co v = Xd
Dfeu nay mau thuSn vcfi (5.1). Nhu vay ta cb diam Vg -> 0 ( 8,|i -> 0 ).
Bd de dugc chiing minh [].
Do

Vg chiia Xh : ||xh - Xd||< q)(hN) nen ta co.
||x^5 - Xdll < 11x^^8 - Xh|| + II Xh - Xdll < diam V^g + cp(hN)

Hay

||x^g - Xdll < T(8,p) = diam V^g + 8 + u

(5.2)

Ta phat bidu ke't qua vua nhan dugc dudi dang dinh ly sau:

Dinh ly 5.1: Phuang phap compact thu hep dang robust v6i ve' phai la toan tir A bie't
g"an dung hOi tu va co danh gia (5.2) .
Nhdn xet 5.1: Ne'u chi bie't g"an dung A' va phuang trinh khong cb nghiem duy nhat,
ta cb thd ke't hgp cac phuang phap nghien cun trinh bay trong §4, §5.

§6- Ap dung cho phuang trinhvi phan thuong .
@ - Xet bai toan Cauchy dbi vai phuang trinh vi phan tuye'n tinh bac 2.
0^! HC:C QUDC GIA HA NOI
KT

Gia sit bai toan (6.1) eo nghiem duy nha't. Trong thue tb ta chi bie't cac thd hien cua
ve' phai y'(x)v.., y"'(x) va ditu kien bien (pi^ ,(p2^ thoa man.
a-||y^^J-f||

< 6 :V6i 1< Kj < m,

m/2

dugc goi la tuang tu rbi rac cua ham u (x) e W [0,1]
Bd de 6.1 [20]: Ne'u u(x) e W ^ [0,1], eon Uhx(x) la tuang tu rai rac ctia u(x), thi tbn
tai hang sb ho = ho(u) > 0 d^ ta co danh gia.
II Uhx -u||2^ V~h~ +x

khiO N o : ||u"|| 1 < rw
2

Chitng minh:
Gia sur ngugc lai: Vn, 3 N > n : rw < ||u" || 1
w

2

Dat m = [ II u" II 1 ] + 1 ta tim dugc Nj > ni va mi < Ni sao cho W ^ ^. That vay, ne'u
0 sao cho.

II^'IIV -ll""llw' -^ = '•'',11=1,2,...
Vi hinh cau dong trong W2'[ 0,1] la tap hgp compact trong C[0,1] nen tir day
{v"n} = (an) CZ C[0,1], tbn tai day {ak } e {an)sao cho
n

2

Bat dang thiJe cubi cung mau thuan vai gia thie't phan chung.
Bo de dugc chiing minh.[]
Bo de 6.2: Vbi sb tu nhien N > No tap VN khong rOng va chiia trong tap compact Ko
nao db.
Chieng minh: Tu bd de (6.1) suy ra:
l|u"L ^ II"11 1 ^rN va||u",,|l
< rN
Lfo.i]
"w
Lro.i]
2

2

2

Theo each xay dung, tren mOi doan [Xi,Xi +1] u"ht(x)
CO dang ajX + bi, tiif da'y suy ra
u"'hx(x) = ai
Ta cb danh gia:
||u"hx|| 1 ^ rN+ Co
^2
XN

Vi I ai I = I tga I = I u"h,(x) I =

^ Co vai x e [xi, Xi+i],
hN
No

.

-


22

X t

u V = J J u"hx(r|) dridt + cpi^x + (p2^ = Uhx (x) +((pi^ -(pi )x + ((p2^ - (p2)
0 0

d day Uh t(x) la tuang tu rbi rac ciia u(x)
Ta cb danh gia:
II u \ , - U II 2 ^ II Uh X - U II 2 + I (p 1 ^ - CPI I + I Cp2^ -(P2 I
< Vhn +Xn + 5 + 6 < 35
va

(6.2)

(|)6(Du\0 < U 8 ( D u \ , ) - (|)5(Du)| + U^u) < G | | D u \ , - Du||c+ co(5)