Mục lục
Mở đầu 1
1. Một số kiến thức chuẩn bị 3
1.1. ánh xạ không giãn . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. ánh xạ hút và dãy đơn điệu Fejer . . . . . . . . . . . . . . . . . 6
1.3. Mô tả thuật toán tổng quát . . . . . . . . . . . . . . . . . . . . . . 14
1.4. Một số tính chất cơ bản . . . . . . . . . . . . . . . . . . . . . . . 15
2. Một số thuật toán chiếu 24
2.1. Xây dựng thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2. Một số kết quả hội tụ . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3. Một số điều kiện đảm bảo sự hội tụ theo chuẩn và hội tụ tuyến tính 34
2.4. Một vài ví dụ về tính chính quy tuyến tính (bị chặn) . . . . . . . . 39
3. Thuật toán dưới gradient và phương pháp chỉnh lặp song song 41
3.1. Thuật toán dưới gradient . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.1. Cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.2. Các kết quả hội tụ . . . . . . . . . . . . . . . . . . . . . . 47
3.2. Phương pháp chỉnh lặp song song . . . . . . . . . . . . . . . . . . 50
i
3.2.1. Một số kết quả bổ trợ . . . . . . . . . . . . . . . . . . . . . 50
3.2.2. Một số ví dụ minh hoạ . . . . . . . . . . . . . . . . . . . . 51
3.3. Một vài thử nghiệm số . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.1. Bài toán với C
i
là hình cầu . . . . . . . . . . . . . . . . . . 55
3.3.2. Bài toán với C
i
là tập mức dưới của một hàm lồi . . . . . . 57
3.3.3. Phương pháp chỉnh lặp trong không gian vô hạn chiều . . . 61
Kết luận 62
Tài liệu tham khảo 63
Phụ lục 65

C = C
1
. . . C
N
= .
Tìm một điểm x C.
Chúng ta xét hai trường hợp thường gặp sau:
Các tập C
i
là đơn giản theo nghĩa các phép chiếu (trực giao) lên C
i
có thể
tính toán được tường minh. C
i
trong trường hợp này có thể là siêu phẳng,
nửa không gian, không gian con đóng hay một hình cầu.
Không thể tính được phép chiếu lên C
i
, tuy nhiên có thể thay nó bằng phép
chiếu lên một tập xấp xỉ nào đó của C
i
. C
i
trong trường hợp này có thể là
tập mức dưới của một hàm lồi nào đó.
Hướng tiếp cận thường dùng là sử dụng một thuật toán chiếu. Sử dụng các phép
chiếu lên các tập C
i
hoặc tập xấp xỉ C
i

i
[(1
(n)
i
)I +
(n)
i
P
(n)
i
]

x
(n)
, (1.1)
ở đây P
(n)
i
là phép chiếu lên tập xấp xỉ C
(n)
i
trong bước lặp thứ n,
i
,
i
tương
ứng là các trọng và các tham số nới lỏng,
và thuật toán chỉnh lặp song song giải hệ phương trình đặt không chỉnh
A
i

x
(n+1)
=
1
N
N

i=1
x
(n)
i
.
Trong đó
n
là tham số hiệu chỉnh,
n
là tham số song song hóa.
Ngoài các phần Mở đầu, Kết luận và Tài liệu tham khảo, cấu trúc luận văn gồm
3 chương:
Chương 1 mang tên "Một số kiến thức chuẩn bị", trình bày các khái niệm cơ
bản, một số kết quả phụ trợ và thuật toán dạng tổng quát với các ánh xạ không
giãn vững với các kết quả về tính hội tụ của thuật toán tổng quát.
Chương 2 mang tên "Một số thuật toán chiếu", trình bày các thuật toán chiếu
giải bài toán chấp nhận lồi và các kết quả hội tụ.
Chương 3 mang tên "Thuật toán dưới gradient và phương pháp chỉnh lặp song
song", trình bày bài toán chấp nhận lồi khi các tập lồi C
i
cho dưới dạng tập mức
dưới của một phiếm hàm lồi, và thuật toán dưới gradient. Cuối chương này là một
số ví dụ số minh họa thuật toán dưới gradient và phương pháp hiệu chỉnh song

x
n
x
0
> lim inf
n
x
n
x
với mọi x
0
= x. Thật vậy, từ đẳng thức
x
n
x
0

2
= x
n
x
2
+ x x
0

2
+ 2x
n
x, x x
0

2
I +
1
2
N với N là
một ánh xạ không giãn.
Tính vững có thể hiểu là ngoài tính không giãn T x T y x y, ánh xạ
còn thỏa mãn bất đẳng thức chặt hơn là
T x T y
2
+ (Id T )x (Id T )y
2
x y
2
.
Điều này tương đương với bất đẳng thức (ii) trong mệnh đề dưới đây.
Mệnh đề 2. Nếu D là một tập con lồi đóng của X và T : D X là một ánh
xạ, khi đó các mệnh đề sau tương đương:
(i) T là ánh xạ không giãn vững.
(ii) T x T y
2
T x T y, x y (T là 1ngược đơn điệu mạnh ).
(iii) 2T I là ánh xạ không giãn.
Định nghĩa 3. Một ánh xạ được gọi là không giãn vững nới lỏng nếu nó có thể
biểu diễn được dưới dạng (1 )I + F với F là một ánh xạ không giãn vững
nào đó.
Hệ quả 1. Giả sử D là một tập con đóng của X và T : D X là một ánh xạ,
khi đó T là ánh xạ được trung bình hóa khi và chỉ khi nó là ánh xạ không giãn
vững nới lỏng.
4

x + P
C
x z
2
= x P
C
x
2
+ 2x P
C
x, P
C
x z + P
C
x z
2
x P
C
x
2
+ 2x P
C
x, P
C
x z
Như vậy, từ xP
C
x, P
C
xz 0 ta suy ra xP

x), (z P
C
x
0 x P
C
x (z P
C
x), z P
C
x
Cho 0
0 x P
C
x, z P
C
x
x P
C
x, P
C
x z 0
(ii): Để chứng minh P
C
là ánh xạ không giãn vững, dựa vào mệnh đề 2, ta chỉ
cần chỉ ra P
C
x P
C
y, x y P
C

C
x P
C
y 0.
Cộng từng vế ta có điều cần chứng minh.
Định nghĩa 4. Hàm tương ứng d(ã, C) : X R : x inf
cC
xc = xP
C
x
gọi là hàm khoảng cách tới tập C.
Dễ thấy rằng với tập C lồi đóng thì d(ã, C) là hàm lồi và liên tục (và do đó
là nửa liên tục dưới yếu).
Định nghĩa 5. Một dãy (x
n
) trong X được gọi là hội tụ tuyến tính tới giới hạn x
với cấp nếu [0, 1) và tồn tại số 0 sao cho
x
n
x
n
n
Mệnh đề 4. Giả sử (x
n
) là một dãy trong X, p là một số nguyên dương và x là
một điểm trong X. Nếu (x
pn
)
n
hội tụ tuyến tính tới x và (x

và x T x, T x f 0.
(iii) x f
2
Rx f
2
= 2x f, x T x
2
x T x
2
.
(iv) R là (2 )/-hút: x f
2
Rx f
2
(2 )/x Rx
2
=
(2 )x T x
2
Chứng minh: (i) là hiển nhiên.
(ii): Do T là ánh xạ không giãn vững, ta có
T x f
2
T x f, x f
T x x
2
+ x f
2
+ 2T x x, x f T x f, x f
T x x

=2x f
2

2
x f
2

2
T x f
2
+ 2
2
x f, T x f 2x f, T x f
=2x f, x f (T x f)

2
[x f
2
+ T x f
2
2x f, T x f]
=2x f, x T x
2
x T x
2
.
7
(iv): Từ (ii), (iii) và định nghĩa R ta có
x f
2

Định nghĩa 7. Giả sử (x
n
) là một dãy trong X. Ta nói (x
n
) là chính quy tiệm cận
nếu x
n
x
n+1
0.
Ví dụ 1. Giả sử D là một tập lồi đóng khác rỗng, F là một tập con lồi đóng khác
rỗng của D và (T
n
)
n0
là dãy các tự ánh xạ không giãn của D, trong đó mỗi ánh
xạ T
n
là
n
-hút tương ứng với F và lim
n

n
> 0. Giả sử thêm rằng dãy (x
n
) được
định nghĩa bởi
x
0

.
Cộng từng vế suy ra chuỗi

n
x
n+1
x
n

2
hội tụ, từ đó x
n+1
x
n
0.
Hệ quả 3. Giả sử D là một tập lồi đóng, khác rỗng và ánh xạ T : D D là
ánh xạ hút mạnh và có điểm bất động. Khi đó dãy (T
n
x
0
)
n0
là chính quy tiệm
cận với mọi x
0
D.
8
Về bản chất, toán tử A = A
(0)
A

i=1

i
= 1
Khi đó:
(i) Fix(T
N
T
N1
. . . . .T
1
) =
N

i=1
Fix T
i
và T
N
T
N1
. . . . .T
1
là min{
1
, . . . ,
N
}/2
N1
-

1
Fix T
2
Fix(T
2
T
1
). Để chứng minh bao hàm thức
ngược lại, chọn f Fix(T
2
T
1
) bất kỳ. Chỉ cần chỉ ra rằng f Fix T
1
. Giả sử
điều này sai, khi đó T
1
f Fix T
2
. Cố định

f Fix T
1
Fix T
2
, do T
2
là hút ta
có
f

), f Fix(T
2
T
1
). Nếu x = T
1
x thì
T
2
x = x và do đó T
2
T
1
x f = T
2
x f < x f. Ngược lại, nếu T
1
x = x
thì T
2
T
1
x f T
1
x f < x f. Trong cả hai trường hợp ta đều có kết
luận T
2
T
1
là ánh xạ hút.

1
x
2
)

2

1
(x f
2
T
1
x f
2
)
+
2

2
(T
1
x f
2
T
2
T
1
x f
2
)

). Để chứng minh chiều
ngược lại, chọn f Fix(
1
T
1
+
2
T
2
),

f Fix T
1
Fix T
2
. Khi đó ta có
f

f =
1
T
1
f +
2
T
2
f
1

f

f = T
2
f. Vậy f Fix T
1
Fix T
2
.
Tiếp theo ta chứng minh
1
T
1
+
2
T
2
là hút. Giả sử x =
1
T
1
x +
2
T
2
x và
f Fix(
1
T
1
+
2

1
,
2
} và f Fix( 1T
1
+
2
T
2
) thì ta có
x (
1
T
1
x +
2
T
2
x)
2
(
1
x T
1
x +
2
x T
2
x)
2

2
T
1
x f
2
)
+
2
(x f
2
T
2
x f
2
)
x f
2
(
1
T
1
x + 2T
2
x) f
2
.

Ví dụ 2. Giả sử S
1
, S

0
) là chính quy tiệm cận với mọi x
0
.
10
Chứng minh: Do các phép chiếu là các ánh xạ không giãn vững, áp dụng bổ đề 1
và mệnh đề vừa chứng minh ta suy ra T là hút mạnh và Fix T =
N

i=1
S
i
. áp dụng
hệ quả 3 dãy (T
n
x
0
) là chính quy tiệm cận.
Định nghĩa 8. Giả sử C là một tập lồi đóng khác rỗng và (x
n
) là một dãy trong
X. Ta nói dãy (x
n
)
n0
là đơn điệu Fejer tương ứng với C nếu
x
n+1
c x
n

) hội tụ theo chuẩn.
(v) Các tính chất sau tương đương:
(1) (x
n
) hội tụ theo chuẩn đến một điểm thuộc C.
(2) (x
n
) có các điểm dính theo chuẩn và tất cả đều nằm trong C.
(3) (x
n
) có các điểm dính theo chuẩn và một điểm nằm trong C.
(4) d(x
n
, C) 0.
(5) x
n
P
C
x
n
0.
Hơn nữa, nếu (x
n
) hội tụ đến một điểm x C, thì x
n
x 2d(x
n
, C) n
0.
11

n
, c) = (x
n
c
2
c
2
) hội tụ. Do đó
nếu c
1
, c
2
là hai điểm dính yếu của dãy (x
n
) trong C thì ta cũng kết luận được
dãy (x
n
, c
1
c
2
) hội tụ và do đó c
1
, c
1
c
2
= c
2
, c

0

2
n 0.
Thật vậy, ta có thể giả sử x
n
= x
n+1
. Khi đó c
0
+
x
n
x
n+1
x
n
x
n+1

C, và do tính đơn
điệu Fejer ta có




c
0
+
x



x
n



.
Bình phương hai vế và giản ước ta được điều cần chứng minh.
Khi đó, vì dãy (x
n
c
0

2
) hội tụ nên kết hợp với bất đẳng thức vừa chứng minh
ta suy ra (x
n
) là dãy Cauchy; do đó nó hội tụ theo chuẩn.
(iv): áp dụng đẳng thức hình bình hành a b
2
= 2a
2
+ 2b
2
a + b
2
cho a := P
C
x

x
n
x
n+k

2
4
P
C
x
n+k
+ P
C
x
n
2
x
n+k

2
2P
C
x
n+k
x
n+k

2
+ 2P
C


2
2(P
C
x
n
x
n

2
P
C
x
n+k
x
n+k

2
).
12
Ta nhận thấy rằng (P
C
x
n
) là dãy Cauchy vì dãy x
n
P
C
x
n

n
x
n
= 2d(x
n
, C).
Cho k ta được đánh giá x
n
x 2d(x
n
, C).
(vi): Từ bất đẳng thức đã cho, cộng từng vế ta suy ra d
2
(x
n
, C) tiến tới 0; do đó
(x
n
) hội tụ tới một điểm x C do (v). Đánh giá về tốc độ hội tụ của dãy (x
n
) dễ
dàng suy từ đánh giá trong (v).
Ví dụ 3 (Phép lặp Krasnoselski-Mann). Giả sử C là một tập lồi đóng, T : C C
là ánh xạ không giãn và có điểm bất động, và dãy (x
n
) cho bởi:
x
0
C, x
n+1

2
= x
n
f
2
+ 2t
n
x
n
f, T x
n
x
n
+ t
2
n
T x
n
x
n

2
Nếu t
n
= 0 thì x
n+1
f = x
n
f, nếu t
n

n
+ T x
n
x
n

2
= x
n
f + T x
n
x
n

2
x
n
f
2
= T x
n
f
2
x
n
f
2
= T x
n
T f

) nằm trong Fix T, áp dụng định lý 1(ii) ta có điều
cần chứng minh.
1.3. Mô tả thuật toán tổng quát
Giả sử D là một tập lồi đóng khác rỗng và C
1
, . . . , C
N
là một số hữu hạn
các tập con lồi đóng của D với giao khác rỗng.
C :=
N

i=1
C
i
= .
Với mỗi chỉ số i {1, . . . , N} và mọi số n 0, giả sử rằng T
(n)
i
: D D là
ánh xạ không giãn vững và
Fix T
i
C
i
.
và
(n)
i
[0, 2] là tham số nới lỏng và

i
R
(n)
i
là trung bình có trọng của các nới lỏng tương ứng.
Với các ký hiệu này, ta xác định thuật toán bằng cách xét dãy lặp sau:
x
(0)
D tùy ý, x
(n+1)
:= A
(n)
x
(n)
n 0.
14
với giả thiết rằng dãy (x
(n)
) nằm trong D. Ta cũng định nghĩa tập các chỉ số thiết
thực
I
(n)
:= {i {1, . . . , N} :
(n)
i
> 0}.
Ta nói chỉ số i thiết thực tại bước lặp n, hay bước lặp n là thiết thực cho chỉ số i
nếu i I
(n)
. Ta luôn giả thiết rằng mọi chỉ số i đều được chọn vô hạn lần, tức là

là tập chỉ gồm một phần tử với mọi n. Cuối
cùng, ta nói thuật toán đồng bộ hoặc song song nếu I
(n)
= {1, . . . , N} với mọi n.
1.4. Một số tính chất cơ bản
Bổ đề 2 (Tính chất cơ bản của thuật toán). Cho một thuật toán
(i) Nếu x D; n 0,
x
(n)
x
2
x
(n+1)
x
2
=

i<j

(n)
i

(n)
j

(n)
i

(n)
i

i
x
(n)
x
+

i

(n)
i

(n)
i
[2
N

j=1

(n)
j

(n)
j
]x
(n)
T
(n)
i
x
(n)

2
.
15
(iii) Nếu x

m1
l=n

iI
(n)
C
i
và m n 0 thì x
(n)
x
2
x
(m)
x
2

m1

l=n

i
à
(l)
i
x


2
< +.
(v) Nếu n 0 thì
x
(n+1)
x
(n)


i

(n)
i

(n)
i
x
(n)
T
(n)
i
x
(n)
.
Chứng minh:(i) nhận được bằng tính toán trực tiếp.
Dễ thấy rằng (i) (ii) (iii) (iv). Thật vậy, (i) (ii) do hai số hạng
đầu trong (i) không âm; (ii) (iii) bằng cách lấy tổng từng vế từ l = n đến
l = m 1; (iii) (iv) cũng bằng cách lấy tổng từng vế.
(v): Theo cách xây dựng thuật toán:

(n)
i
[(1
(n)
i
)x
(n)
+
(n)
i
T
(n)
i
x
(n)
x
(n)
]
=

i

(n)
i

(n)
i
(x
(n)
T

(n)
) có chứa một dãy con (x
(n

)
) với d(x
(n

)
, C) 0, thì toàn bộ
dãy (x
(n)
) hội tụ theo chuẩn tới một điểm nằm trong C.
Hệ quả 5. Thuật toán là chính quy tiệm cận nếu một trong hai điều kiện sau thỏa
mãn.
(i) lim inf
n:n thiết thực cho i
à
(n)
i
> 0 với mọi chỉ số i.
(ii) lim inf
n:n thiết thực cho i

(n)
i
< 2 với mọi chỉ số i.
Chứng minh: (i): Tồn tại một số > 0 sao cho với mọi n đủ lớn, à
(n)
i



i:i thiết thực tại n

(n)
i

(n)
i
x
(n)
T
(n)
i
x
(n)
.
Do đó x
(n+1)
x
(n)
0 và dãy (x
(n)
) là chính quy tiệm cận.
(ii): Từ bổ đề 1(iv) và Mệnh đề 5, mọi A
(n)
là
n
-hút tương ứng với C, trong đó


đang xây dựng cần phải ít nhất là hội tụ yếu tới một điểm nào đó, tuy nhiên, theo
ví dụ nêu trên thì ta cần phải có thêm giả thiết để đảm bảo điều này.
Định nghĩa 9. Ta nói thuật toán là tụ ( focusing) nếu với mọi chỉ số i và mọi dãy
17
con (x
n
k
)
k
của thuật toán,
(x
n
k
) x
x
n
k
T
n
k
i
x
n
k
0
i thiết thực tại n
k




) đều nằm trong C. Thật vậy, giả sử rằng ngược lại, tồn tại một dãy con
(x
(n
k
)
)
k
hội tụ tới một điểm x C. Ta đưa vào ký hiệu sau:
I
in
:= {i {1, . . . , N} : x C
i
} I
out
:= {i {1, . . . , N} : x C
i
}
Khi đó I
out
khác rỗng. Ta giả thiết rằng (nếu cần thì chuyển qua dãy con)
I
(n
k
)
I
(n
k
+1)
ã ã ã I
(n

, từ bổ đề 2(iii) ta suy ra
x
(n
k
)
x x
(m
k
)
x, từ đó suy ra x
(m
k
)
x.
Sau khi chuyển qua một dãy con nếu cần thiết, ta có thể giả sử rằng tồn tại một
chỉ số i sao cho
i I
(m
k
)
I
out
k
Từ bổ đề 2(iv), ta suy ra

k
à
(m
k
)

k
)
T
(m
k
)
i
x
(m
k
)
0. Do thuật toán là
18
tụ, nên với dãy con m
k
đã có, ta suy ra x C
i
, điều này mâu thuẫn với giả thiết
i I
out
.
Hệ quả 6. Giả sử X là không gian hữu hạn chiều và thuật toán là tụ.
Nếu lim inf
n:n thiết thực cho i
à
(n)
i
> 0 với mọi chỉ số i thì dãy x
(n)
hội tụ theo chuẩn tới một

i
< 2.
Ví dụ 7. Giả sử X là không gian hữu hạn chiều và thuật toán là suy biến.
Giả sử thêm rằng T
(n)
i
: T
i
; C
i
= Fix T
i
, và tồn tại một số > 0 sao cho

(n)
i
2 với mọi n và mọi chỉ số i. Khi đó, dãy (x
(
n
)
) hội tụ theo chuẩn
tới một điểm trong C.
Định nghĩa sau đây cho ta dấu hiệu nhận biết một thuật toán có tụ hay
không.
Định nghĩa 10. Cho một thuật toán, ta nói dãy T
(n)
i
hội tụ từng điểm tới T
i
với

)
) của (x
(n)
) với x
(n
k
)

x D; x
(n
k
)
T
(n
k
)
i
x
(n
k
)
0 và i là thiết thực tại mọi bước lặp n
k
. Ta phải chỉ
19
ra rằng x C
i
. Cố định u X bất kỳ. Do ánh xạ T
(n
k

Cho k tiến tới vô hạn; do giả thiết về T
(n
k
)
i
và (x
(n
k
)
), ta suy ra rằng
T
i
P
D
u u, x u 0.
Do u được chọn bất kỳ, ta có thể chọn u = x + tv, trong đó v là một vector bất
kỳ và t > 0. Khi đó
T
i
P
D
(x + tv) (x + tv), v 0.
Do đó, khi cho t 0, ta được T
i
P
D
x x, v 0. Chọn v = x T
i
P
D

à
(n)
i
>
0 thì dãy (x
(n)
) là chính quy tiệm cận và hội tụ yếu tới một điểm trong C.
(ii) Giả sử thuật toán là tụ và p- lặp đoạn với p là một số nguyên dương nào đó.
Đặt:

n
:= min{à
(l)
i
: np l (n + 1)p 1; i thiết thực tại l} n 0.
20
Nếu

n

n
= +, thì dãy (x
(n)
) có một điểm dính yếu duy nhất trong C.
Chính xác hơn là tồn tại một dãy con (x
(n
k
p)
) hội tụ yếu tới điểm dính yếu
duy nhất này sao cho:

)
0
với mọi dãy r
k
, s
k
trong {0, . . . , p 1}.
Nói riêng, điều này xảy ra khi lim inf
n:n thiết thực cho i
à
(n)
i
> 0 với mọi chỉ số i.
(iii) Giả sử thuật toán là tụ và dãy (x
(n)
) hội tụ yếu tới một điểm x nào đó.
Nếu

n
à
(n)
i
= + với một chỉ số i nào đó thì x C
i
. Hệ quả là nếu

n
à
(n)
i

)
với mọi
k 0.
Do thuật toán là chính quy tiệm cận, ta có x
(n
k
)
x
(m
k
)
0 và do đó x
(m
k
)
k
hội
tụ yếu tới x. Do thuật toán là tụ, ta suy ra
lim
k
x
(m
k
)
T
(m
k
)
i
x

x
(np)
c
2
x
((n+1)p)
c
2

n
(n+1)p1

l=np

iI
(l)
x
(l)
T
(l)
i
x
(l)

2
21
với mọi n 0. Lấy tổng theo n và xét giả thiết cho
n
, ta nhận được dãy con
x

k
)
x
(n
k
p+s
k
)
0 (**)
với mọi dãy (r
k
), (s
k
) {0, 1, . . . , p 1}. Chuyển qua dãy con nếu cần thiết, ta
có thể giả sử rằng (x
(n
k
p)
)
k
hội tụ yếu tới một điểm x D.
Ta sẽ chứng minh x C. Thật vậy, cố định một chỉ số i. Do thuật toán là lặp
đoạn, tồn tại một dãy (r
k
) trong {0, 1, . . . , p 1} sao cho,
x
(n
k
p+r
k

k
)
0. (3)
Do thuật toán là tụ, từ (1), (2), (3) ta suy ra x C
i
. Khẳng định được chứng minh.
Từ định lý (1), x là điểm dính yếu duy nhất của (x
(n)
) trong C, như vậy (ii) chứng
minh xong.
(iii): Từ bổ đề (2)(iv),

n
à
(n)
i
x
(n)
T
(n)
i
x
(n)

2
< +. Do ta giả thiết là

n
à
(n)