Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG NGỌC PHƯƠNG PHƯƠNG PHÁP HALPERN
TÌM ĐIỂM BẤT ĐỘNG CỦA ÁNH XẠ KHÔNG GIÃN
TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên – 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Công trình được hoàn thành tại :

1.4. Phương pháp lặp Solodov - Svaiter giải phương trình 0 ∈ Tx 16
Chương 2. Phương pháp Halpern và cải biên 28
2.1. Phương pháp Halpern tìm điểm bất động của ánh xạ không giãn 28
2.2. Phương pháp xấp xỉ mềm . . . . . . . . . . . . . . . . . . . . 34
2.3. Phương pháp Halpern cải biên . . . . . . . . . . . . . . . . . . 42
Tài liệu tham khảo 46
1
Lời cảm ơn
Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của GS.TS
Nguyễn Bường. Thầy đã dành nhiều thời gian hướng dẫn và giải đáp các thắc
mắc của tôi trong suốt quá trình làm luận văn. Tôi xin được bày tỏ lòng biết
ơn sâu sắc đến Thầy.
Tôi xin bày tỏ lòng biết ơn các thầy cô khoa Toán - Tin, phòng đào tạo
sau đại học Trường Đại Học Khoa Học, Đại Học Thái Nguyên cũng như các
Thầy cô đã tham gia giảng dạy khóa cao học 2009 - 2011, lời cảm ơn sâu sắc
nhất về công lao dạy dỗ trong suốt quá trình giáo dục và đào tạo của Nhà
trường.
Tôi cũng xin bày tỏ lòng biết ơn với các thầy, các cô trong Ban giám hiệu
và Tổ Toán - Tin Trường Trung học phổ thông Trại Cau đã tạo điều kiện
giúp đỡ tôi trong quá trình học tập, nghiên cứu và hoàn thiện luận văn cao
học.
Cuối cùng, tôi xin chân thành cảm ơn gia đình, các anh chị em học viên
cao học toán K3 và bạn bè đồng nghiệp đã động viên, khích lệ và cổ vũ để
tôi có thể hoàn thành nhiệm vụ của mình.
Thái Nguyên, ngày 6 tháng 5 năm 2011
Tác giả
Dương Ngọc Phương
2
Mở đầu
Bài toán tìm điểm bất động của ánh xạ không giãn trong không gian

A ∪ B A hợp với B
A ∩ B A giao với B
A × B tích Đề-các của hai tập A và B
convD bao lồi của tập D
x
k
→ x dãy {x
k
} hội tụ mạnh tới x
x
k
 x dãy {x
k
} hội tụ yếu tới x
A
∗
toán tử liên hợp của toán tử A
D(A) miền xác định của toán tử A
R(A) miền giá trị của toán tử A
4
Chương 1
Một số khái niệm cơ bản
Trong chương này, chúng tôi đề cập đến các vấn đề sau. Trong mục 1.1,
chúng tôi giới thiệu một số khái niệm và kiến thức liên quan đến không gian
Hilbert. Trong mục 1.2, chúng tôi trình bày một số tính chất của toán tử. Mục
1.3 được dùng để trình bày bài toán tìm điểm bất động. Mục 1.4 được dùng
để trình bày phương pháp lặp Solodov-Svaiter giải phương trình 0 ∈ T x.
1.1. Một số khái niệm của không gian Hilbert
Các khái niệm và kết quả trong phần này được tham khảo trong tài liệu
[1] và [2].

, ξ
2
, , ξ
n
) ∈ R
n
; y = (η
1
, η
2
, , η
n
) ∈ R
n
;
ϕ, ψ =

b
a
ϕ(x)ψ(x)dx, ϕ, ψ ∈ L
2
[a, b].
1.1.2. Một số khái niệm cơ bản
• Cho X là một không gian Hilbert, một dãy {x
n
} gồm các phần tử x
n
∈ X
gọi là hội tụ mạnh tới phần tử của x ∈ X nếu x
n

+ x
2
) = Ax
1
+ Ax
2
∀x
1
, x
2
∈ X;
(ii)A(αx) = αAx, ∀α ∈ R, x ∈ X.
• Toán tử tuyến tính A được gọi là bị chặn, nếu tồn tại một hằng số M > 0
sao cho Ax ≤ Mx. Giá trị hằng số M nhỏ nhất thỏa mãn bất đẳng thức
đó được gọi là chuẩn của A và ký hiệu là A.
Mệnh đề 1.1. Cho X là một không gian Hilbert và x
0
∈ X là một phần tử
tùy ý. Khi đó tồn tại một hàm tuyến tính ϕ : X → R sao cho ϕ = 1 và
ϕ(x
0
) = x
0
.
• Tập hợp tất cả các phiếm hàm tuyến tính liên tục trên X gọi là không
gian liên hợp (hay không gian đối ngẫu của X) và được ký hiệu là X
∗
.
• Dãy {x
n

} hội tụ
yếu tới x ∈ D(T ) và {T (x
n
)} hội tụ mạnh đến p thì T (x) = p.
Định nghĩa 1.1 Nếu dãy {x
n
} hội tụ yếu tới x ∈ X thì dãy {x
n
} là bị
chặn.
• Cho X là một không gian Hilbert, M là một tập con khác rỗng của X.
(i) M được gọi là lồi nếu với mọi x, y ∈ M, 0 ≤ λ ≤ 1 ta có:
λx + (1 − λ)y ∈ M;
(ii) M được gọi là compact nếu mọi dãy {x
n
} ⊂ M đều chứa dãy con hội
tụ tới một điểm thuộc M.
• Mỗi tập con đóng bị chặn M của một không gian Hilbert là compact
yếu, tức là với mỗi dãy bị chặn trong M có thể trích ra được một dãy con
hội tụ yếu tới một phần tử của không gian này.
• Tập M ⊂ X được gọi là tập đóng yếu, nếu {x
n
}  x, thì x ∈ M.
Định lý 1.1. (Mazur)
Mỗi tập con lồi đóng của một không gian Hilbert là đóng yếu.
Định nghĩa 1.2. Một phiếm hàm ϕ xác định trên X được gọi là lồi, nếu
ϕ(tx + (1 − t)y) ≤ tϕ(x) + (1 − t)ϕ(y)
với mọi x, y ∈ X, t ∈ [0, 1]. Nếu dấu "=" xảy ra chỉ khi x = y, thì ϕ được
gọi là lồi chặt.
• Nếu tồn tại một hàm liên tục tăng γ : [0; +∞) → R, γ(0) = 0 sao cho:

0
) ≤ lim inf
n→∞
ϕ(x
n
),
thì ϕ được gọi là nửa liên tục yếu tại x
0
.
Định lý 1.2. Cho một phiếm hàm ϕ : X → R. Ta nói rằng ϕ khả vi theo
hướng h tại một điểm x ∈ X nếu giới hạn
lim
t→0
ϕ(x + th) − ϕ(x)
t
= V

(x, h). (1.1)
Nếu giới hạn trong (1.1) tuyến tính liên tục theo h, tức là V

(x, h) = A(x)h
thì A(x) được gọi là vi phân Gâteaux của ϕ tại điểm x và được kí hiệu là
ϕ

(x).
Trong định nghĩa (1.1) nếu tồn tại toán tử A : X → X
∗
sao cho:
V



(x) thỏa mãn bất đẳng
8
thức sau:
ϕ

(x), x − y ≥ ϕ(x) − ϕ(y), ∀x, y ∈ X;
(ii) Nếu ϕ(x) là một phiếm hàm lồi đều trên X thì:
ϕ

(x), x − y ≥ ϕ(x) − ϕ(y) + γ(x − y), ∀x, y ∈ X;
(iii) Nếu ϕ(x) là một phiếm hàm lồi mạnh trên X thì:
ϕ

(x), x − y ≥ ϕ(x) − ϕ(y) + cx − y
2
, ∀x, y ∈ X.
1.2. Một số tính chất của toán tử
Định nghĩa 1.4. Toán tử A : X → 2
Y
được gọi là bị chặn nếu nó biến mỗi
tập bị chặn trong X thành một tập bị chặn trong Y . Nếu R(A) ⊂ Y là một
tập bị chặn thì toán tử A được gọi là bị chặn đều.
Định nghĩa 1.5. Toán tử A : X → 2
X
∗
được gọi là bức nếu nó tồn tại một
hàm c(t) xác định với t ≥ 0 sao cho c(t) → +∞ khi t → ∞, thì:
y, x ≥ c(x)x, ∀x ∈ X, ∀y ∈ Ax.
Điều kiện trên tương đương với: A là toán tử bức khi và chỉ khi:

0
khi t
n
→ 0 với mọi véc
tơ h ∈ X ;
9
(iii) d - liên tục tại x
0
∈ X nếu với mỗi dãy con {x
n
} ⊂ X sao cho khi
x
n
→ x
0
thì Ax
n
 Ax
0
;
(iv) liên tục Lipschitz nếu ∃L > 0 sao cho:
Ax − Ay ≤ Lx − y, ∀x, y ∈ X.
Định nghĩa 1.8. Toán tử A : X → 2
X
∗
được gọi là d - đơn điệu trên X nếu
tồn tại một hàm không âm d(t), không giảm với t ≥ 0, và d(0) = 0 thỏa mãn
tính chất:
Ax − Ay, x − y ≥ (d(x) − d(y))(x − y), ∀x, y ∈ X.
Định nghĩa 1.9.

). Những định lý điểm bất động
nổi tiếng đã xuất hiện từ đầu thế kỷ 20, trong đó phải kể đến "Nguyên lý
điểm bất động Brower (1912) và Nguyên lý ánh xạ co Banach (1922)". Các
kết quả kinh điển này đã được mở rộng ra cho lớp các ánh xạ và không gian
10
khác nhau, đã được ứng dụng trong toán học nói riêng và trong khoa học kỹ
thuật nói chung.
1.3.1. Nguyên lý ánh xạ co
Trước khi phát biểu nguyên lý ánh xạ co ta sẽ định nghĩa ánh xạ co:
Định nghĩa 1.10. Cho X, Y là các không gian Metric, ánh xạ T : X →
Y được gọi là ánh xạ co nếu tồn tại k ∈ [0, 1) sao cho d(T x, T y) ≤
kd(x, y), ∀x, y ∈ X., trong đó d là các metric của X và Y .
Như vậy, ánh xạ co là trường hợp riêng của ánh xạ Lipschitz và hiển nhiên
là liên tục.
Định lý 1.5. Cho (X, d) là một không gian Metric đầy đủ và T là ánh xạ co
trong X. Khi đó tồn tại duy nhất x
∗
∈ X sao cho: T (x
∗
) = x
∗
. Ngoài ra, với
mọi x
0
∈ X, ta có T
n
x
0
→ x
∗

1
) ≤ kd(x
2
, x
1
) ≤ k
2
d(x
1
, x
0
)

d(x
n+1
, x
n
) ≤ k
n
d(x
1
, x
0
).(∗)
Lấy m ≥ n ta có:
d(x
n
, x
m
) ≤ d(x

)
≤ k
n
(1 + k + + k
m−n−1
)d(x
0
, x
1
)
≤
k
n
1 − k
d(x
0
, x
1
).
Vì k ∈ [0, 1) nên k
n
→ 0 khi n → ∞. Do đó, từ (*) suy ra dãy {x
n
} là dãy
Cauchy. Mà (X, d) là không gian Metric đủ nên {x
n
} hội tụ tới một phần tử
11
x
∗

= x
∗
.
• Giả sử y
∗
∈ X mà T y
∗
= y
∗
thì ta có:
d(x
∗
, y
∗
) = d(T x
∗
, T y
∗
) ≤ kd(x
∗
, y
∗
).
Vì k ∈ [0, 1) nên d(x
∗
, y
∗
) = 0, x
∗
= y

n
} hội tụ
yếu tới điểm bất động của T .
Định nghĩa 1.12. Cho H là không gian Hilbert, C là tập con lồi đóng của
H. Toán tử T : C → H là λ−giả co chặt nếu ∃λ ∈ [0, 1) sao cho:
T x − T y
2
≤ x − y
2
+ λ(I − T )x − (I − T )y
2
, ∀x, y ∈ C,
12
trong đó I là toán tử đồng nhất trong H.
Dễ thấy, khi λ = 0 thì T là ánh xạ không giãn, tức là:
T x − T y ≤ x − y, với mọi x, y ∈ C.
Điều này có nghĩa rằng, lớp các toán tử λ- giả co chặt chứa lớp các ánh
xạ không giãn.
Định lý 1.8. Cho H là không gian Hilbert, C là tập con lồi đóng và giới nội
của H. Toán tử T : C → C là λ− giả co chặt. Khi đó với mỗi x
0
∈ C, 0 <
µ < 1 − λ, dãy lặp {x
n
}
∞
n=0
xác định bởi:
x
n+1

1 − λ
2
, vì λ < 1, nên
˜
λ =
1 − λ
2
> 0.
Do đó suy ra A là toán tử đơn điệu.
Đặt T
t
= (1 − t)I + tT. Khi đó với t > 0 ta có:
T
t
x − T
t
y
2
=(I − tA)x − (I − tA)y
2
=(x − y) − t(Ax − Ay)
2
=(x − y)
2
+ t
2
(Ax − Ay)
2
− 2tAx − Ay, x − y
≤(x − y)

x − T
t
y
2
≤ (x − y)
2
.
Do đó T là ánh xạ không giãn.
Theo Định lý 1.6 thì T
t
có ít nhất một điểm bất động trong C. Mặt khác,
lại theo Định lý 1.7 với mỗi k ∈ [0, 1) dãy lặp x
n
= (T
t
)
n
k
x
0
với x
0
∈ C hội
tụ mạnh tới điểm bất động x
∗
của T trong C.
Mặt khác, toán tử (T
t
)
k

x
0
, k ∈ (0, 1).
Cần chứng minh dãy {x
n
− T
t
(x
n
)}
n∈N
hội tụ mạnh tới 0.
Thật vậy:
x
n+1
− x
∗
= (1 − k)x
n
+ kT
t
(x
n
) − x
∗
= (1 − k)(x
n
− x
∗
) + k(T

2
= (1 − k)
2
x
n
− x
∗

2
+ k
2
T
t
x
n
− x
∗

2
+ 2k(1 − k)T
t
x
n
− x
∗
, x
n
− x
∗
,

− 2a
2
T
t
x
n
− x
∗
, x
n
− x
∗
.
(1.4)
14
Cộng vế tương ứng của hai đẳng thức (1.3) và (1.4) và sử dụng tính chất
không giãn của toán tử T
t
cùng với T
t
x
∗
= x
∗
ta thu được:
x
n+1
− x
∗


∗
, x
n
− x
∗
.
(1.5)
Theo bất đẳng thức Cauchy-Schwarz ta có:
T
t
x
n
− x
∗
, x
n
− x
∗
 ≤ T
t
x
n
− T
t
x
∗
.x
n
− x
∗

2
+ k
2
+ (1 − k)
2
+ 2k(1 − k) − 2a
2
].x
n
− x
∗

2
= x
n
− x
∗

2
.
Chọn a
2
= k(1 − k) ta thu được:
a
2
x
n
− T
t
x


n=0

x
n
− x
∗

2
− x
n+1
− x
∗

2

= x
0
− x
∗

2
− x
N+1
− x
∗

2
≤ x
0

t
là ánh xạ không giãn nên:
T
t
x
n
i
→ T
t
x
∗
, và T
t
x
∗
= x
∗
.
Từ đó suy toàn bộ dãy {x
n
}
∞
n=0
hội tụ tới x
∗
.
15
1.4. Phương pháp lặp Solodov - Svaiter giải phương trình 0 ∈ T x
Bài toán được phát biểu như sau :
Tìm x ∈ H sao cho

Phép chiếu trực giao của x lên A là argmin{y − x, y ∈ A}, được ký hiệu
là P
A
(x).
Bổ đề [7] Cho A là tập đóng trong H,A = ∅, bất kỳ x, y ∈ H và z ∈ A ta
có các kết quả sau :
(i) x − P
A
(x), z − P
A
(x) ≤ 0 ,
(ii) P
A
(x) − P
A
(y)
2
≤ x − y
2
− P
A
(x) − x + y − P
A
(y)
2
.
1.4.1.Phương pháp lặp không chính xác
Việc giải bài toán phụ (1.8) chính xác có thể tính toán khó như việc giải
16
bài toán (1.7). Trong trường hợp bài toán phụ được giải với nghiệm xấp xỉ

bảo tính hội tụ của dãy lặp là :
ε
k
 ≤ σ
k
µ
k
và
∞

k=0
σ
k
< ∞,
hoặc ε
k
 ≤ σ
k
µ
k
y
k
− x
k
 và
∞

k=0
σ
k

k
∈ H và v
k
∈ T (y
k
) như là nghiệm xấp xỉ của bài
toán (1.9). Khi đó một trong hai điều kiện sau được thỏa mãn :
ε
k

µ
k
y
k
− x
k

≤ σ,
ε
k

v
k

≤ σ
trong đó σ ∈ [0; 1] và chú ý rằng σ không phụ thuộc vào số lần lặp k
Đặt
H
k
:= {x ∈ H, v

trên.
Mệnh đề 1.2: Cho x ∈ H , µ > 0 và σ ∈ [0; 1) và giả sử rằng (y, v) là
nghiệm không chính xác của phương trình 0 ∈ T (.) + µ(. − x) với tham số σ.
Từ đó ta có kết quả:
x − y, v ≥ (1 − σ).Max{µy − x
2
, v
2
/µ} ≥ (1 − σ).vy − x. (1.10)
Đặt
H := {z ∈ H|z − y, v ≤ 0}.
Khi đó 4 điều kiện sau tương đương
x ∈ H;
y = x;
v = 0;
x là nghiệm của phương trình (1.7).
hơn nữa
P
H
(x) − x ≥ (1 − σ).Max{y − x, v/µ}. (1.11)
18
Chứng minh
Từ (1.9) ta xét hai trường hợp có thể xảy ra sau : µx − y ≤ v và
µx − y ≥ v.
Trường hợp 1
µx − y ≤ v ta có ε ≤ σv nên
x − y, v =
1
µ
.v − ε, v ≥

.v
2
.
(1.15)
kết hợp (1.14) và (1.15) ta có (1.10) đúng trong trường hợp thứ 2. Tiếp theo
ta chứng minh sự tương đương của 4 điều kiện.
Giả sử x ∈ H thì x − y, v ≤ 0 và do (1.10) ta có x = y.
Nếu x = y thì x − y, v = 0 và do (1.10) nên v = 0.
Tương tự nếu ta có v = 0 thì x = y và x là một nghiệm của (1.7).
Nếu x là nghiệm của (1.7) thì theo tính chất của ánh xạ T ta có :
0 ≤ y − x, v − 0 = y − x, v.
19
Vì vậy, x ∈ H. Cuối cùng để chứng minh (1.11) ta thấy rằng
Nếu x ∈ H thì x = y và v = 0 thì (1.11) đúng.
Nếu x ∈ H (nên v = 0) ta có P
H
(x) = x −
v, x − y
v
2
.v.
Do đó, P
H
(x) − x =
v, y − x
v
.
Nếu v/µ ≥ x − y thì v
2
/µ ≥ µx − y

và
W
k
= {z ∈ H|z − x
k
, x
0
− x
k
 ≤ 0}.
Ta có x
k+1
= P
H
k
∩W
k
(x
0
). Chọn x
0
là điểm ban đầu, tại mỗi lần lặp thì có
2 bài toán phụ được giải và ta luôn tìm thấy nghiệm không chính xác của
bài toán phụ và ta xác định được phép chiếu x
0
lên giao của hai nửa không
gian H
k
∩ W
k

k

và
v
k
= 0.
20
Giả sử sau k lần lặp và H
k
∩ W
k
= ∅ x
k+1
được xác định là kết quả của bài
toán.
Min
z
z − x
0

2
với ràng buộc z − y
k
, v
k
 ≤ 0,
z − x
k
, x
0

 = 0.
Vì vậy, bài toán trên trở thành
Min
λ
1
,λ
2
,h
h
2
+ λ
1
v
k
+ λ
2
(x
0
− x
k
)
2
với ràng buộc λ
1
v
k
+ λ
2
(x
0

, λ
2
có được do giải
bài toán cực tiểu bậc 2 trong không gian hai chiều với sự ràng buộc của hai
bất đẳng thức tuyến tính.
Hơn thế nữa dễ thấy rằng nếu chiếu x
0
lên H
k
ta có
P
H
k
(x
0
) = x
0
−
v
k
, x
0
− y
k

v
k

2
v

+ λ
1
v
k
+ λ
2
(x
0
− x
k
).
trong đó λ
1
và λ
2
là nghiệm của hệ hai phương trình tuyến tính 2 ẩn
λ
1
v
k

2
+ λ
2
v
k
, x
0
− x
k

.
1.4.3. Phân tích sự hội tụ
Mệnh đề 1.3: Giả sử thuật toán 1 đạt đến k+1 lần lặp, khi đó ta có
x
k+1
− x
0

2
≥ x
k
− x
0

2
+ x
k+1
− x
k

2
(1.16)
và
x
k+1
− x
k
 ≥ (1 − σ).max{y
k
− x

k
(x
0
)
2
≤ x
k+1
− x
0

2
− P
W
k
(x
k+1
) −x
k+1
+ x
0
− P
W
k
(x
0
)
2
vì x
k+1
∈ W

k+1
− x
k

2
.
Từ x
k+1
∈ H
k
, ta có
x
k+1
− x
k
 ≥ x
k
− P
H
k
(x
k
),
vậy (1.17) có được từ mệnh đề 1.2.
Từ mệnh đề 2 ta có những kết luận sau:
Hệ quả 1
Giả sử dãy tham số lặp {µ
k
} bị chặn trên và Thuật toán 1 tạo ra một dãy
vô hạn {x

k
} bị chặn cho k −→ ∞ thì kết quả là:
∞

j=0
x
j+1
− x
j

2
< ∞,
do đó
0 = lim
k→∞
x
k+1
− x
k
.
Từ (1.17) và giả thiết µ
k
bị chặn trên ta có kết quả sau:
lim
k→∞
y
k
− x
k
 = 0,

− x
0
} không giảm khi đó
x
k
− x
0
 −→ ∞ khi k −→ ∞ vì vậy x
k
 −→ ∞
Tiếp theo ta chứng minh sự hội tụ mạnh của dãy {x
k
} tới nghiệm trong
trường hợp S = ∅.
Trường hợp S = ∅
Giả sử (1.7) có nghiệm, khi đó S = ∅, chọn x
0
là điểm lặp ban đầu, ta thiết
lập tập
U(x
0
) = {x ∈ H|∀z ∈ S, z − x, x
0
− x ≤ 0}. (1.18)
Ta thấy rằng tập H
k
∩ W
k
luôn chứa tập nghiệm S do đó nó khác rỗng
và phép chiếu trong Thuật toán 1 là xác định, hơn nữa ta thấy rằng dãy lặp