ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

HOÀNG TRUNG THÔNG

PHƯƠNG PHÁP LẶP
GIẢI BÀI TOÁN CHẤP NHẬN TÁCH TỔNG QUÁT
TRONG KHÔNG GIAN HILBERT

Chuyên ngành: Toán ứng dụng
Mã số:

60 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

GS.TS. NGUYỄN BƯỜNG

THÁI NGUYÊN - 2016


i

Mục lục
iii

Bảng ký hiệu
Mở đầu


Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 3
Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . 6

Toán tử đơn điệu . . . . . . . . . . . . . . . . . . . . 10
Toán tử tuyến tính . . . . . . . . . . . . . . . . . . . 12

Điểm bất động của ánh xạ không giãn . . . . . . . . . . . . 13
1.4.1 Ánh xạ không giãn và điểm bất động . . . . . . . . . 13
1.4.2

Phương pháp lặp Mann tìm điểm bất động của ánh
xạ không giãn . . . . . . . . . . . . . . . . . . . . . . 15

Chương 2. Phương pháp lặp giải bài toán chấp nhận tách
tổng quát trong không gian Hilbert
2.1

17

Bài toán chấp nhận tách . . . . . . . . . . . . . . . . . . . . 17
2.1.1
2.1.2

Phát biểu bài toán . . . . . . . . . . . . . . . . . . . 17
Một số bổ đề bổ trợ . . . . . . . . . . . . . . . . . . 18


ii

2.2


tập số thực
không gian Hilbert thực

C
∅

tập con đóng lồi của H
tập rỗng

∀x

mọi x

∃x
x, y

tồn tại x
tích vô hướng của hai véctơ x và y

x
xn → x

chuẩn của véctơ x
xn hội tụ mạnh đến x

xn
T

xn hội tụ yếu x

bài toán nén hình ảnh, chụp hình cộng hưởng từ, mạng nơ ron, khôi phục
ảnh. Một trong những phương pháp đã và đang được nhiều tác giả sử
dụng để giải bài toán chấp nhận tách là phương pháp chiếu trong đó cần
phải thực hiện phép chiếu mêtric lên các tập con lồi đóng của không gian
Hilbert. Tuy nhiên, việc tính ảnh của ánh xạ chiếu mêtric trên một tập lồi
đóng bất kỳ cũng không dễ thực thi. Do vậy, việc xây dựng các phương
pháp xấp xỉ điểm bất động để giải bài toán chấp nhận tách là hướng
nghiên cứu được nhiều nhà toán học quan tâm. Nhiều kết quả công bố
gần đây về phương pháp giải cho lớp bài toán này thường đòi hỏi tính liên
tục Lipschitz và hệ số Lipschitz của ánh xạ. Tuy nhiên trong thực hành
tính toán, việc tính hệ số Lipschitz thường khá phức tạp và tốn kém, dẫn
đến việc cần thiết phải cải tiến và loại bỏ điều kiện này để xây dựng các
phương pháp giải hiệu quả hơn.
Đề tài của luận văn là phương pháp lặp giải bài toán chấp nhận tách
tổng quát trong không gian Hilbert. Đây là một đề tài vừa có ý nghĩa về
mặt lý thuyết, đồng thời vừa có ý nghĩa thực tiễn cao. Nội dung của bản
luận văn được trình bày trong hai chương.
Chương 1: giới thiệu một cách hệ thống lại các định nghĩa, ví dụ và một
số tính chất quan trọng của không gian Hilbert thực.
Chương 2: trình bày phương pháp lặp giải bài toán chấp nhận tách tổng
quát trong không gian Hilbert, trình bày một số định lý hội tụ, các kết
quả cơ bản và áp dụng.
Luận văn này được thực hiện tại Trường Đại học Khoa học – Đại học
Thái Nguyên và hoàn thành dưới sự hướng dẫn của GS.TS. Nguyễn Bường.


2

Tác giả xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy, người đã tận tình
hướng dẫn, giúp đỡ cho tác giả trong quá trình học tập, nghiên cứu và

Không gian Hilbert
Định nghĩa

Định nghĩa 1.1.1 Cho không gian véctơ X trên trường số thực R. Tích
vô hướng xác định trong X là một ánh xạ
., . :X × X → R
(x, y) → x, y
thỏa mãn các điều kiện sau đây:
(i) x, x ≥ 0, với mọi x ∈ X, x, x = 0 ⇔ x = 0;
(ii) y, x = x, y , với mọi x, y ∈ X;
(iii) x + x , y = x, y + x , y với mọi x, x , y ∈ X;
(iv) λx, y = λ x, y với mọi x, y ∈ X, λ ∈ R.
Số x, y được gọi là tích vô hướng của hai véctơ x, y trong X.


4

Nhận xét 1.1.2 Từ định nghĩa suy ra với mọi x, y, z ∈ X, λ ∈ R:
(1) x, y + y = x, y + x, y ;
(2) x, λy = λ x, y ;
(3) x, 0 = 0.
Định nghĩa 1.1.3 Cặp (X, ., . ), trong đó X là một không gian tuyến
tính trên R, ., . là tích vô hướng trên X được gọi là không gian tiền
Hilbert thực.
Định lý 1.1.4 Mọi không gian tiền Hilbert X đều là không gian tuyến
tính định chuẩn, với chuẩn xác định bởi công thức
x =

x, x


ta đều có x ∈ C;

x khi n → ∞,

(c) Tập compact nếu mọi dãy {xn } ⊂ C đều có một dãy con hội tụ về
một phần tử thuộc C;
(d) Tập compact tương đối nếu mọi dãy {xn } ⊂ C đều có một dãy con
hội tụ;
(e) Tập compact yếu nếu mọi dãy {xn } ⊂ C đều có một dãy con hội tụ
yếu về một phần tử thuộc C;
(f) Tập compact tương đối yếu nếu mọi dãy {xn } ⊂ C đều có một dãy
con hội tụ yếu.
Nhận xét 1.1.10
(a) Mọi tập compact đều là tập compact tương đối, nhưng điều ngược lại
không đúng.
(b) Mọi tập đóng yếu đều là tập đóng, nhưng điều ngược lại không đúng.
Mệnh đề 1.1.11 Cho H là không gian Hilbert thực và C là một tập con
của H. Khi đó, ta có các khẳng định sau:
(a) Nếu C là tập lồi, đóng thì C là tập đóng yếu;
(b) Nếu C là tập bị chặn thì C là tập compact tương đối yếu.
Định nghĩa 1.1.12 Cho C là một tập con khác rỗng, lồi, đóng của không
gian Hilbert thực H. Ta biết rằng với mỗi x ∈ H, đều tồn tại duy nhất
một phần tử PC (x) ∈ C thỏa mãn
x − PC (x) = inf x − y
y∈C

Phần tử PC (x) được xác định như trên được gọi là hình chiếu của x lên
C và ánh xạ PC : H → C biến mỗi phần tử x ∈ H thành PC (x) được gọi
là phép chiếu mêtric từ H lên C.



n

= x, x =

|αk |2 .

αk αk =
k=1

k=1

Ví dụ 1.1.16 Không gian
∞
2

l =

x = {xn }n ∈ R :

xn yn
k=1
∞

là không gian Hilbert với tích vô hướng x, y =

xn yn và chuẩn cảm
n=1

sinh

ta được
y, y
x, x −

| x, y |2
≥ 0 ⇔ | x, y |2 ≤ x, x y, y .
y, y

Định lí được chứng minh.
Định lý 1.1.18 Giả sử {xn }n , {yn }n là hai dãy hội tụ đến a, b trong không
gian tiền Hilbert thực X. Khi đó
lim xn , yn = a, b .

n→∞

Chứng minh. Giả sử lim xn = a, lim yn = b trong không gian X. Ta sẽ
n→∞

n→∞

chứng minh lim xn , yn = a, b trong R.
n→∞

Thật vậy, ta có
| xn , yn − a, b | = | xn , yn + xn , b − xn , b − a, b |
≤ | xn , yn − b + xn − a, b |
≤ xn . yn − b + xn − a . b .


8


2

= x + y, x + y = x

2

+ y

2

+ x, y + y, x ,

x−y

2

= x − y, x − y = x

2

+ y

2

− x, y − y, x .

Cộng hai đẳng thức trên ta được đẳng thức (1.3).
Áp dụng đẳng thức hình bình hành cho hai véctơ x − y và x − z ta có
hệ quả sau:

là ∀x, y ∈ C, ∀λ, µ > 0 thì λx + µy ∈ C.
Định nghĩa 1.2.3 Cho C = ∅ là tập lồi trong H và x ∈ C. Nón pháp
tuyến ngoài của C tại x ∈ C, nón đối cực và nón đối ngẫu của C là các
tập hợp lần lượt được kí hiệu và xác định bởi:
NC (x) := {w ∈ H : w, y − x ≤ 0, ∀y ∈ C};
C0 := {w ∈ H : w, x ≤ 0, ∀x ∈ C};
C+ := {w ∈∈ H : w, x ≥ 0, ∀x ∈ C}.
Định nghĩa 1.2.4
(i) Trên đồ thị của hàm f, kí hiệu là epif và được định nghĩa bởi công
thức
epif := {(x, r) ∈ C × R : f (x) ≤ r}.
(ii) Miền hữu hiệu của hàm f , kí hiệu domf và được định nghĩa bởi công
thức
domf := {x ∈ C : f (x) < +∞}.
Định nghĩa 1.2.5 Hàm f được gọi là chính thường nếu domf = ∅ và
f (x) > −∞ với mọi x ∈ C.
Định nghĩa 1.2.6 Hàm f được gọi là
(i) Lồi trên C nếu
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y),

∀x, y ∈ C, ∀λ ∈ [0; 1].

(ii) Lồi ngặt trên C nếu
f (λx+(1−λ)y) < λf (x)+(1−λ)f (y),

∀x, y ∈ C, x = y, ∀λ ∈ (0; 1).

(iii) Lồi mạnh trên C với hệ số α > 0 nếu với ∀x, y ∈ C, ∀λ ∈ (0; 1) ta có
1
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − λ(1 − λ)α x − y 2 .

Định nghĩa 1.3.1 Cho H là một không gian Hilbert. Toán tử đơn trị
T : H → H, được gọi là toán tử đơn điệu nếu
T (x) − T (y), x − y ≥ 0,

∀x, y ∈ H.

Ví dụ 1.3.2 Cho toán tử đơn trị T xác định trên R cho bởi công thức
T (x) = x,

∀x ∈ R.

Khi đó T là toán tử đơn điệu vì với mọi x, y ∈ R, ta có
T (x) − T (y), x − y = x − y, x − y = x − y

2

≥ 0,

∀x, y ∈ R.


11

Định nghĩa 1.3.3 Toán tử đa trị T : H → 2H được gọi là toán tử đơn
điệu nếu
u − v, x − y ≥ 0,

∀x, y ∈ domT,

∀u ∈ T (x),



−x2 nếu x < 0
là toán tử đơn điệu cực đại.
Thật vậy, với mọi điểm M (x, y) ∈
/ Gr(T ) ta luôn tìm được điểm M0 (x0 , y0 ) ∈
−−→ −−→
Gr(T ) sao cho góc giữa hai véctơ OM và OM0 là góc tù, điều này có nghĩa
là
−−→ −−→
(x, y), (x0 , y0 ) = OM .OM0 < 0.
Do vậy T là toán tử đơn điệu cực đại.


12

1.3.2

Toán tử tuyến tính

Định nghĩa 1.3.7 Cho H1 , H2 là các không gian Hilbert. Một ánh xạ
A : H1 → H2 gọi là một ánh xạ tuyến tính hay toán tử tuyến tính nếu:
1) A(x1 + x2 ) = Ax1 + Ax2 với mọi x1 , x2 ∈ H1 ;
2) A(αx) = αAx với mọi x ∈ H1 và với mọi số α.
Định nghĩa 1.3.8 Cho H1 , H2 là các không gian Hilbert. Một toán tử
A : H1 → H2 gọi là liên tục nếu xn → x0 luôn luôn kéo theo Axn → Ax0 .
Định nghĩa 1.3.9 Toán tử tuyến tính A : H1 → H2 gọi là bị chặn (giới
nội) nếu có một hằng số r > 0 để cho
(∀x ∈ H1 )


x
x
Ngược lại, giả sử có hằng số r thỏa mãn công thức (1.5), và xn → x0 .
Ta có
thì lấy xn =

Axn − Ax0 = A(xn − x0 ) ≤ r xn − x0 → 0.
Vậy A liên tục tại x0 .
Số r ≥ 0 nhỏ nhất thỏa mãn điều kiện (1.5) gọi là chuẩn của toán tử A
và được ký hiệu A . Như vậy:


13

1) (∀x ∈ H1 )

Ax ≤ A . x ;

2) Nếu (∀x ∈ H1 )
1.4
1.4.1

Ax ≤ r x thì A ≤ r.

Điểm bất động của ánh xạ không giãn
Ánh xạ không giãn và điểm bất động

Cho C là tập con lồi, đóng, khác rỗng trong không gian Hilbert thực
H, T : C → H là một ánh xạ.
Định nghĩa 1.4.1 Ánh xạ T được gọi là

điểm bất động.


14

Nhận xét 1.4.4 Từ tính lồi chặt của không gian Hilbert H và tính liên
tục của ánh xạ không giãn T , ta thấy nếu tập điểm bất động Fix(T ) khác
rỗng thì nó là tập lồi và đóng.
Vấn đề xấp xỉ điểm bất động của lớp ánh xạ không giãn là đề tài có
tính thời sự và thu hút sự quan tâm nghiên cứu của nhiều nhà toán học
trong và ngoài nước. Dưới đây, ta đề cập đến một số phương pháp xấp xỉ
tìm điểm bất động của ánh xạ không giãn.
Chú ý 1.4.5 Nếu T : C → C là ánh xạ co, thì dãy lặp Picard xác định
bởi x0 ∈ C và xn+1 = T (xn ) hội tụ mạnh về điểm bất động duy nhất của
T . Tuy nhiên điều này không còn đúng đối với lớp ánh xạ không giãn.
Bổ đề 1.4.6 Giả sử T là ánh xạ không giãn trên tập con lồi, đóng, khác
rỗng C của không gian Hilbert H. Khi đó I − T là nửa đóng trên C, nghĩa
là nếu dãy {xn } ⊂ C hội tụ yếu tới x ∈ C và dãy {(I − T )xn } hội tụ mạnh
tới y thì (I − T )x = y.
Định nghĩa 1.4.7 Phép chiếu mêtric của H lên tập C, PC được xác định
bởi
PC x = arg min x − u ,
u∈C

∀x ∈ H,

có nghĩa PC x là điểm trong C với tính chất
x − PC x ≤ x − u ,

∀u ∈ C.


Nếu lim sup( zn+1 − zn − xn+1 n − xn ) ≥ 0, thì lim ||xn − zn || = 0.
n→∞

n→∞

Bổ đề 1.4.11 Cho {an } là dãy số thực không âm thỏa mãn điều kiện
an+1 ≤ (1 − bn )an + bn cn

với mọi n ≥ 1,

trong đó {bn }, {cn } là các dãy số thực dương thỏa mãn
∞

(i) bn ∈ [0, 1],

bn = ∞;
n=1

(ii) lim sup cn ≤ 0.
n→∞

Khi đó lim an = 0.
n→∞

1.4.2

Phương pháp lặp Mann tìm điểm bất động của ánh xạ
không giãn


Chương 2

Phương pháp lặp giải bài toán chấp
nhận tách tổng quát trong không
gian Hilbert
Chương này nghiên cứu bài toán chấp nhận tách tổng quát sinh bởi
ánh xạ lai ghép tổng quát và trình bày các phương pháp lặp để giải các
bài toán này. Cụ thể, một số định lý về sự hội tụ yếu của phương pháp với
việc sử dụng các ánh xạ trung bình và toán tử giải của các toán tử đơn
điệu cực đại. Phần cuối của chương nêu các áp dụng cho phương pháp lặp
Mann tìm điểm bất động của ánh xạ không giãn và cho bài toán điểm cân
bằng. Các kiến thức của chương này được viết trên cơ sở tổng hợp từ các
tài liệu [7]–[13].
2.1
2.1.1

Bài toán chấp nhận tách
Phát biểu bài toán

Cho H là không gian Hilbert và C là một tập đóng lồi trong H. Toán
tử U : C → H được gọi là ngược đơn điệu mạnh (ism) nếu tồn tại hằng
số α > 0 sao cho
x − y, U x − U y ≥ α U x − U y 2 ,

∀x, y ∈ C

và những ánh xạ U như vậy được gọi là α − ism. Cho H1 , H2 là không
gian Hilbert. Cho D và Q tương ứng là hai tập lồi đóng khác rỗng của H1
và H2 . Cho A : H1 → H2 là một toán tử tuyến tính bị chặn. Khi đó bài


−1
ở đây A−1
i 0 và Bj 0 là các tập không điểm của Ai và Bj tương ứng.

Đặt U = A∗ (I − PQ )A trong bài toán chấp nhận tách (2.1), ta có
U : H1 → H1 là toán tử ngược đơn điệu mạnh, ở đây A∗ là toán tử
đối ngẫu của A và PQ là phép chiếu mêtric từ H2 lên Q. Tiếp theo, nếu
D ∩ A−1 Q là khác rỗng, thì z ∈ D ∩ A−1 Q là tương đương với phương
trình sau:
z = PD (I − λA∗ (I − PQ )A)z

(2.3)

ở đây λ > 0 và PD phép chiếu mêtric từ H1 lên D.
2.1.2

Một số bổ đề bổ trợ

Ký hiệu N là tập các số nguyên dương, R là tập các số thực. Cho H là
không gian Hilbert với tích vô hướng ., . và chuẩn . tương ứng.
Bổ đề 2.1.1 Trong không gian Hilbert H ta có:
λx + (1 − λ)y

2

=λ x

2

+ (1 − λ y 2 ) − λ(1 − λ) x − y

mãn điều kiện Opial, nếu
lim inf xn − u < lim inf xn − v
n→∞

với xn

n→∞

u và u = v

Đối với toán tử đơn điệu cực đại B ta có thể xây dựng một toán tử Jr
được xác định như sau
Jr ≡ (I + rB)−1 : H → D(B),
ở đây r > 0. Ta cũng biết rằng nếu B là toán tử đơn điệu cực đại thì toán
tử giải Jr là không giãn chặt và Fix(Jr ) = B −1 0 ≡ {x ∈ H : 0 ∈ Bx} với
mỗi r > 0.
Các bổ đề sau đóng vai trò quan trọng trong việc chứng minh các kết
quả cơ bản ở mục sau.
Bổ đề 2.1.3 ([11]; [12]) Cho H là một không gian Hilbert và B là một
toán tử đơn điệu cực đại trên H. Khi đó các đẳng thức sau đây là đúng
với mọi s, t > 0 và x ∈ H
s−t
Js x − Jt x, Js x − x ≥ Js x − Jt x
s
Js x − Jt x ≤

|s − t|
x − Js x
s



Cho C là một tập lồi đóng khác rỗng của không gian Hilbert H và
f : C × C → R là một song hàm. Xét bài toán cân bằng sau: Tìm z ∈ C
sao cho
f (z, y) ≥ 0,

∀y ∈ C.

(2.7)

Tập tất cả các điểm z ∈ C sao cho (2.7) được thỏa mãn ký hiệu là EP (f ),
có nghĩa là:
EP (f ) = {z ∈ C : f (z, y) ≥ 0,

∀y ∈ C}.

Để giải bài toán cân bằng, ta giả thiết f thỏa mãn các tính chất sau:
(A1) f (x, x) = 0, ∀x ∈ C;
(A2) f đơn điệu, nghĩa là f (x, y) + f (y, x) ≤ 0 với mọi x, y ∈ C;
(A3) Với mọi x, y, z ∈ C, lim sup(tz + (1 − t)x, y) ≤ f (x, y);
t↓0

(A4) f (x, .) là lồi và nửa liên tục dưới với mọi x ∈ C.
Bổ đề 2.1.6 Cho C là một tập lồi đóng khác rỗng của H, f : C × C → R
là một song hàm thỏa mãn (A1)-(A4) , cho r > 0 và x ∈ H. Khi đó
∃z ∈ C sao cho
f (z, y) +

1
y − z, z − x ≥ 0

tập con khác rỗng của H. Một ánh xạ T : C → H được gọi là lai ghép
tổng quát nếu tồn tại α, β ∈ R sao cho
α Tx − Ty

2

+ (1 − α) x − T y

2

≤ β Tx − y

2

2

+ (1 − β) x − y

(2.8)
với mọi x, y ∈ C. Ta gọi ánh xạ này là (α, β)-lai ghép tổng quát.
Lưu ý rằng lớp ánh xạ này chứa một số lớp các ánh xạ đã biết. Ví dụ,
lớp ánh xạ (1, 0)-lai ghép tổng quát là không giãn. Nó là ánh xạ co hẹp
khi α = 2 và β = 1, nghĩa là
2 Tx − Ty

2

≤ Tx − y

Nó cũng là lai ghép với α =


0,

nếu x ∈ D,

PE x, nếu x ∈
/ D,

Ta thấy S là một ánh xạ co hẹp nhưng không liên tục.