Luận văn Thạc sĩ Toán học: Phương pháp lặp xoay vòng và đồng thời giải bài toán chấp nhận tách nhiều tập

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

18
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của luận văn này là trình bày chứng minh chi tiết cho các phương pháp lặp xoay vòng và phương pháp lặp đồng thời để xấp xỉ một nghiệm của bài toán. Để hiểu rõ hơn, mời các bạn tham khảo nội dung luận văn này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Phương pháp lặp xoay vòng và đồng thời giải bài toán chấp nhận tách nhiều tập

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐÀO ĐÌNH THOẢNG PHƯƠNG PHÁP LẶP XOAY VÒNG VÀ ĐỒNG THỜI GIẢI BÀI TOÁN CHẤP NHẬN TÁCH NHIỀU TẬP LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. Nguyễn Bường Thái Nguyên – 2020
ii Lời cảm ơn Luận văn này được hoàn thành dưới sự hướng dẫn của GS.TS. Nguyễn Bường (Viện Công nghệ Thông tin-Viện Hàn lâm Khoa học và Công nghệ Việt Nam). Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy lớp cao học Toán, nhà trường và các phòng chức năng của trường, khoa Toán - Tin, trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Xin chân thành cảm ơn anh chị em trong lớp cao học và bạn bè đồng nghiệp đã trao đổi, động viên và khích lệ tác giả trong quá trình học tập, nghiên cứu và làm luận văn.
iii Mục lục Lời cảm ơn ii Một số ký hiệu và viết tắt iv Mở đầu 1 Chương 1 Một số kiến thức chuẩn bị 3 1.1. Một số đặc trưng của không gian Hilbert . . . . . . . . . . . . . . . 3 1.2. Ánh xạ không giãn trong không gian Hilbert . . . . . . . . . . . . . 12 1.3. Phương pháp CQ giải bài toán chấp nhận tách . . . . . . . . . . . . 14 Chương 2 Phương pháp lặp xoay vòng và lặp liên tiếp giải bài toán (MSSFP) 18 2.1. Phương pháp lặp xoay vòng giải Bài toán (MSSFP) . . . . . . . . . 18 2.2. Phương pháp lặp đồng thời giải Bài toán (MSSFP) . . . . . . . . . 21 2.3. Phương pháp xoay vòng nới lỏng và lặp liên tiếp nới lỏng để giải Bài toán (MSSFP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Kết luận 29 Tài liệu tham khảo 30
iv Một số ký hiệu và viết tắt h., .i tích vô hướng trên không gian Hilbert H k.k chuẩn trên không gian Hilbert H ∪ phép hợp ∩ phép giao R+ tập các số thực không âm A∗ toán tử liên hợp của toán tử A I toán tử đồng nhất ∅ tập rỗng ∀x với mọi x xn −→ x0 dãy {xn } hội tụ mạnh về x0 xn * x0 dãy {xn } hội tụ yếu về x0
1 Mở đầu Cho C và Q là các tập con lồi, đóng và khác rỗng của các không gian Hilbert H1 và H2 , tương ứng. Cho A : H1 −→ H2 là một toán tử tuyến tính bị chặn. Bài toán chấp nhận tách (SFP) có dạng như sau: Tìm một phần tử x∗ ∈ C sao cho Ax∗ ∈ Q. (0.1) Dạng tổng quát của Bài toán (0.1) là bài toán (0.2), bài toán này được phát biểu như sau: Cho Ci , i = 1, 2, ..., N và Qj , j = 1, 2, ..., M là các tập con lồi và đóng của H1 và H2 tương ứng. Tìm một phần tử x∗ ∈ S = ∩N −1 M i=1 Ci ∩ A (∩j=1 Qj ) 6= ∅. (0.2) Mô hình bài toán (SFP) lần đầu tiên được giới thiệu và nghiên cứu bởi Y. Censor và T. Elfving [6] cho mô hình các bài toán ngược. Bài toán này đóng vai trò quan trọng trong khôi phục hình ảnh trong Y học, điều khiển cường độ xạ trị trong điều trị bệnh ung thư, khôi phục tín hiệu (xem [4], [5]) hay có thể áp dụng cho việc giải các bài toán cân bằng trong kinh tế, lý thuyết trò chơi. Thời gian gần đây, lớp các Bài toán (0.2) đã 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. Mục đích của luận văn này là trình bày chứng minh chi tiết cho các phương pháp lặp xoay vòng và phương pháp lặp đồng thời để xấp xỉ một nghiệm của Bài toán (0.2) từ tài liệu [7]. Nội dung của luận văn được chia làm hai chương chính: Chương 1. Một số kiến thức chuẩn bị Trong chương này, luận văn đề cập đến một số đặc trưng cơ bản của không gian Hilbert, phép chiếu mêtric, ánh xạ không giãn và một số phương pháp cải tiến của phương pháp CQ giải Bài toán (0.2).
2 Chương 2. Phương pháp lặp xoay vòng và lặp liên tiếp giải bài toán (MSSFP) Chương này luận văn trình bày chứng minh chi tiết cho các kết quả của Wen và các cộng sự về hai phương pháp lặp xoay vòng và lặp liên tiếp cho việc giải Bài toán (MSSFP) (xem phát biểu trang 15) trong tài liệu [7]. Ngoài ra, luận văn cũng trình bày dạng nới lỏng của các phương pháp khi các tập lồi, đóng Ci và Qj là các tập mức dưới của các hàm lồi.
3 Chương 1 Một số kiến thức chuẩn bị Chương này bao gồm ba mục chính. Mục 1.1 đề cập đến một số đặc trưng cơ bản của không gian Hilbert thực, Mục 1.2 giới thiệu sơ lược một số kết quả về ánh xạ không giãn, bao gồm khải niệm, tính chất của tập điểm bất động và nguyên lý nửa đóng. Mục 1.3 trình bày về phương pháp CQ và một số cải tiến của phương pháp này để giải bài toán chấp nhận tách đa tập. Nội dung của chương này phần lớn được tham khảo từ các tài liệu [1], [2], [8] và [9]. 1.1. Một số đặc trưng của không gian Hilbert Ta luôn giả thiết H là không gian Hilbert thực với tích vô hướng được kí hiệu là h., .i và chuẩn được kí hiệu là k.k. Mệnh đề 1.1. Trong không gian Hilbert thực H ta luôn có đẳng thức sau kx − yk2 + kx − zk2 = ky − zk2 + 2hx − y, x − zi, với mọi x, y, z ∈ H . Chứng minh. Thật vậy, ta có ky − zk2 + 2hx − y, x − zi = hy, yi + hz, zi + 2hx, xi − 2hx, zi − 2hx, yi = [hx, xi − 2hx, yi + hy, yi] + [hx, xi − 2hx, zi + hz, zi] = kx − yk2 + kx − zk2 .
4 Vậy ta được điều phải chứng minh. Mệnh đề 1.2. Với mọi {x1 , . . . , xn } ∈ H, ta có bất đẳng thức sau. n n n X 2 X 21X || λi xi || = λi ||xi || − λi λj ||xi − xi ||2 , n ≥ 2, (1.1) 2 i=1 i=1 i,j=1 n P trong đó λi ∈ [0, 1], i = 1, 2 . . . , n, λi = 1. i=1 Chứng minh. Ta có n X n X n X 2 || λi xi || = h λi x i , λ j xj i i=1 i=1 j=1 n X X n = λi λj hxi , xj i i=1 j=1 n X n 1 X = λi λj (kxi k2 + kxj k2 − kxi − xj k2 ) 2 i=1 j=1 n X n X 2 = λi kxi || − λi λj kxi − xj k2 . i=1 i,j=1 Mệnh đề được chứng minh. Hệ quả 1.1. Cho H là một không gian Hilbert thực. Khi đó, với mọi x, y ∈ H và mọi λ ∈ [0, 1], ta có kλx + (1 − λ)yk2 = λkxk2 + (1 − λ)kyk2 − λ(1 − λ)kx − yk2 . (1.2) Định nghĩa 1.1. Cho C là một tập con khác rỗng, lồi, đóng của không gian Hilbert H . Dãy {xn } ⊂ H được gọi là đơn điệu Fejér tương ứng đối với C nếu với mọi z ∈ C , ta đều có kxn+1 − zk ≤ kxn − zk, ∀n ≥ 1. Nhận xét 1.1. Nếu {xn } ⊂ H là đơn điệu Fejér tương ứng đối với C , thì tồn tại giới hạn hữu hạn limn→∞ kxn − zk với mọi z ∈ C .
5 Mệnh đề 1.3. Cho H là một không gian Hilbert thực. Khi đó, nếu với x, y ∈ H thỏa mãn điều kiện |hx, yi| = kxk.kyk, tức là bất đẳng thức Schwars xảy ra dấu bằng thì hai véc tơ x và y là phụ thuộc tuyến tính. Chứng minh. Giả sử ngược lại rằng x 6= λy với mọi λ ∈ R. Khi đó, từ tính chất của tích vô hướng, ta có 0 < kx − λyk2 = λ2 kyk2 − 2λhx, yi + kxk2 , với mọi λ ∈ R. Ta thấy rằng nếu y = 0, thì hiển nhiên x và y là phụ thuộc tuyến hx, yi tính. Giả sử y 6= 0, khi đó với λ = , thì bất đẳng thức trên trở thành kyk2 |hx, yi| < kxk.kyk, điều này mâu thuẫn với giả thiết. Vậy x và y là phụ thuộc tuyến tính. Mệnh đề được chứng minh. Nhắc lại rằng, dãy {xn } trong không gian Hilbert H được gọi là hội tụ yếu về phần tử x ∈ H , nếu lim hxn , yi = hx, yi, n→∞ với mọi y ∈ H . Từ tính liên tục của tích vô hướng, suy ra nếu xn → x, thì xn * x. Tuy nhiên, điều ngược lại không đúng. Chẳng hạn xét không gian l2 = {xn } ⊂ P∞ 2 2 R: n=1 |xn | < ∞ và {en } ⊂ l , được cho bởi en = (0, ..., 0, 1 , 0, ..., 0, ...), vị trí thứ n với mọi n ≥ 1. Khi đó, en * 0, khi n → ∞. Thật vậy, với mỗi y ∈ H , từ bất đẳng thức Bessel, ta có ∞ X |hen , yi|2 ≤ kyk2 < ∞. n=1
6 Suy ra limn→∞ hen , yi = 0, tức là en * 0. Tuy nhiên, {en } không hội tụ về 0, vì ken k = 1 với mọi n ≥ 1. Ta biết rằng mọi không gian Hilbert H đều thỏa mãn điều kiện của Opial, tính chất này được thể hiện trong mệnh đề dưới đây: Mệnh đề 1.4. Cho H là một không gian Hilbert thực và {xn } ⊂ H là một dãy bất kỳ thỏa mãn điều kiện xn * x, khi n → ∞. Khi đó, với mọi y ∈ H và y 6= x, ta có lim inf kxn − xk < lim inf kxn − yk. (1.3) n→∞ n→∞ Chứng minh. Vì xn * x, nên {xn } bị chặn. Ta có kxn − yk2 = kxn − xk2 + kx − yk2 + 2hxn − x, x − yi. Vì x 6= y , nên lim inf kxn − yk2 > lim inf (kxn − xk2 + 2hxn − x, x − yi) n→∞ n→∞ = lim inf kxn − xk2 . n→∞ Do đó, ta nhận được lim inf kxn − xk < lim inf kxn − yk. n→∞ n→∞ Mệnh đề được chứng minh. Mệnh đề 1.5. ([2]) Cho K là một tập lồi, đóng khác rỗng của không gian Hilbert H . Cho {xn } là một dãy trong H thảo mãn các điều kiện sau. a) lim ||xn − x|| tồn tại với mỗi x ∈ K. n→∞ b) ωw (xn ) ∈ K , trong đó ωw (xn ) là tập các điểm tụ yếu của dãy {xn }. Khi đó dãy {xn } hội tụ yếu tới một điểm thuộc K.
7 Chứng minh. Ta chỉ ra ωw (xn ) chỉ gồm duy nhất một phần tử. Giả sử tồn tại x, y ∈ ωw (xn ) và x 6= y . Khi đó, tồn tại hai dãy con {xnk } và {xnl } sao cho xnk * x và xnl * y . Từ Mệnh đề 1.4, ta nhận được lim inf kxnk − xk < lim inf kxnk − yk k→∞ k→∞ = lim inf kxnl − yk k→∞ < lim inf kxnl − xk k→∞ = lim inf kxnk − xk, k→∞ điều này là vô lý. Do đó, ωw (xn ) chỉ gồm duy nhất một phần tử x (nào đó) và vì vậy xn * x. Mệnh đề 1.6. Mọi không gian Hilbert thực H đều có tính chất Kadec-Klee, tức là nếu {xn } ⊂ H là một dãy bất kỳ trong H thỏa mãn các điều kiện xn * x và kxn k → kxk, thì xn → x, khi n → ∞. Chứng minh. Ta có kxn − xk2 = kxn k2 − 2hxn , xi + kxk2 → 0, n → ∞. Suy ra xn → x, khi n → ∞. Mệnh đề được chứng minh. Mệnh đề 1.7. Cho C là một tập con lồi và đóng của không gian Hilbert thực H . Khi đó, tồn tại duy nhất phần tử x∗ ∈ C sao cho kx∗ k ≤ kxk với mọi x ∈ C. Chứng minh. Thật vậy, đặt d = inf kxk. Khi đó, tồn tại {xn } ⊂ C sao cho kxn k −→ x∈C d, n −→ ∞. Từ đẳng thức hình bình hành, ta có xn + xm 2 kxn − xm k2 = 2(kxn k2 + kxm k2 ) − 4k k 2
8 ≤ (kxn k2 + kxm k2 ) − 4d2 −→ 0, khi n, m −→ ∞. Do đó {xn } là dãy Cauchy trong H . Suy ra tồn tại x∗ = lim xn ∈ C n→∞ (do {xn } ⊂ C và C là tập đóng). Do chuẩn là hàm số liên tục nên ∗ kx k = d. Tiếp theo ta chỉ ra tính duy nhất. Giả sử tồn tại y ∗ ∈ C sao cho ky ∗ k = d. Ta có x∗ + y ∗ 2 kx∗ − y ∗ k2 = 2(kx∗ k2 + ky ∗ k2 ) − 4k k 2 ≤ 2(d2 + d2 ) − 4d2 = 0. Suy ra x∗ = y ∗ . Vậy tồn tại duy nhất một phần tử x∗ ∈ C sao cho kx∗ k = inf x∈C kxk. Từ Mệnh đề 1.7, ta có mệnh đề dưới đây: Mệnh đề 1.8. Cho C là một tập con lồi và đóng của không gian Hilbert thực H . Khi đó, với mỗi x ∈ H , tồn tại duy nhất phần tử PC x ∈ C sao cho kx − PC (x)k ≤ kx − yk với mọi y ∈ C. Chứng minh. Vì C là tập lồi, đóng và khác rỗng nên x − C cũng là tập lồi, đóng và khác rỗng. Do đó, theo Mệnh đề 1.7, tồn tại duy nhất một phần tử PC ∈ C sao cho kx − PC (x)k ≤ kx − yk với mọi y ∈ C. Định nghĩa 1.2. Phép cho tương ứng mỗi phần tử x ∈ H một phần tử PC x ∈ C xác định như trên được gọi là phép chiếu mêtric từ H lên C . Ví dụ 1.1. Cho C = {x ∈ H : hx, ui = y}, với u 6= 0. Khi đó y − hx, ui PC x = x + u. kuk2
9 Ví dụ 1.2. Cho C = {x ∈ H : kx − ak ≤ R}, trong đó a ∈ H là một phần tử cho trước và R là một số dương. Khi đó, ta có:  x nếu kx − ak ≤ R,  PC x = R a +  (x − a) nếu kx − ak > R. kx − ak Mệnh đề dưới đây cho ta một điều kiện cần và đủ để ánh xạ PC : H −→ C là một phép chiếu mêtric. Mệnh đề 1.9. Cho C là tập con lồi, đóng và khác rỗng của không gian Hilbert H . Cho PC : H −→ C là một ánh xạ. Khi đó, các phát biểu sau là tương đương: a) PC là phép chiếu mêtric từ H lên C ; b) hy − PC x, x − PC xi ≤ 0 với mọi x ∈ H và y ∈ C ; Chứng minh. Thật vậy, giả sử PC là phép chiếu mêtric từ H lên C , tức là kx − PC xk = inf u∈C kx − uk. Với mọi x ∈ H , y ∈ C và với mọi α ∈ (0, 1), đặt yα = αy + (1 − α)PC x. Vì C lồi nên yα ∈ C và do đó kx − PC xk ≤ kyα − xk. Điều này tương đương với kx − PC xk2 ≤ kα(y − PC x) − (x − PC x)k2 = α2 ky − PC xk2 + kx − PC xk2 − 2αhy − PC x, x − PC xi. Từ đó, ta nhận được 2hy − PC x, x − PC xi ≤ αky − PC xk2 . Cho α −→ 0+ , ta được hy − PC x, x − PC xi ≤ 0. Ngược lại, giả sử b) đúng. Với mọi x ∈ H và mọi y ∈ C , ta có kx − PC xk2 = kx − y + y − PC xk2 = kx − yk2 + 2hx − y, y − PC xi + ky − PC xk2 = kx − yk2 + 2hx − PC x, y − PC xi − ky − PC xk2 ≤ kx − yk2 .
10 Do đó, kx − PC xk = inf u∈C kx − uk, hay PC là phép chiếu mêtric từ H lên C . Từ mệnh đề trên, ta có hệ quả dưới đây: Hệ quả 1.2. Cho C là một tập con lồi đóng của không gian Hilbert H và PC là phép chiếu mêtric từ H lên C . Khi đó, ta có các khẳng định sau: a) với mọi x, y ∈ H , ta có kPC x − PC yk2 ≤ hx − y, PC x − PC yi; b) với mọi x ∈ H và y ∈ C , ta có kx − yk2 ≥ kx − PC xk2 + ky − PC xk2 . Chứng minh. a) Với mọi x, y ∈ H , từ Mệnh đề 1.9, ta có hx − PC x, PC y − PC xi ≤ 0, hy − PC y, PC x − PC yi ≤ 0. Cộng hai bất đẳng thức trên ta nhận được điều phải chứng minh. b) Với mọi x ∈ H và y ∈ C , từ Mệnh đề 1.9, ta có hx − PC x, y − PC xi ≤ 0. Từ đó, ta có kx − yk2 = k(x − PC x) − (y − PC x)k2 = kx − PC xk2 + ky − PC xk2 − 2hx − PC x, y − PC xi ≥ kx − PC xk2 + ky − PC xk2 . Hệ quả được chứng minh. Mệnh đề 1.10. Cho C là một tập con lồi, đóng của không gian Hilbert H và x∈ / C . Khi đó, tồn tại một phần tử v ∈ H , v 6= 0 sao cho suphv, yi ≤ hv, xi − kvk2 . y∈C
11 Chứng minh. Vì x ∈ / C , nên v = x − PC x 6= 0. Từ Mệnh đề 1.9, ta có hv, y − PC xi ≤ 0, với mọi y ∈ C . Suy ra hv, y − x + x − PC xi ≤ 0, với mọi y ∈ C . Điều này tương đương với hv, yi ≤ hv, xi − kvk2 , với mọi y ∈ C . Do đó suphv, yi ≤ hv, xi − kvk2 . y∈C Mệnh đề được chứng minh. Chú ý 1.1. Mệnh đề 1.10 còn được gọi là định lý tách tập lồi cho trước với một điểm không thuộc nó. Mệnh đề 1.11. Nếu C là một tập con lồi và đóng của không gian Hilbert H , thì C là tập đóng yếu. Chứng minh. Giả sử C không là tập đóng yếu. Khi đó, tồn tại dãy {xn } trong C thỏa mãn xn * x, nhưng x ∈ / C . Vì C là tập lồi và đóng, nên theo định lý tách các tập lồi, tồn tại y ∈ H và ε > 0 (chẳng hạn lấy y = v và ε = kvk2 /2 trong chứng minh của Mệnh đề 1.10) sao cho hy, zi < hy, xi − ε, với mọi z ∈ C . Đặc biệt hy, xn i < hy, xi − ε, với mọi n. Cho n → ∞, ta nhận được hy, xi ≤ hy, xi − ε, điều này là vô lý. Do đó, C là tập đóng yếu.
12 Chú ý 1.2. Nếu C là tập đóng yếu trong H thì hiển nhiên C là tập đóng. Từ định lý Banach-Alaoglu, ta có mệnh đề dưới đây: Mệnh đề 1.12. Mọi tập con bị chặn của H đều là tập compact tương đối yếu. 1.2. Ánh xạ không giãn trong không gian Hilbert Định nghĩa 1.3. Cho C là một tập con lồi, đóng và khác rỗng của không gian Hilbert thực H . Ánh xạ T : C −→ H được gọi là một ánh xạ không giãn, nếu với mọi x, y ∈ C , ta có kT x − T yk ≤ kx − yk. Ta ký hiệu tập điểm bất động của ánh xạ không giãn T là Fix(T ), tức là Fix(T ) = {x ∈ C : T x = x}. Mệnh đề dưới đây cho ta mô tả về tính chất của tập điểm bất động Fix(T ). Mệnh đề 1.13. Cho C là một tập con lồi, đóng và khác rỗng của không gian Hilbert thực H và T : C −→ H là một ánh xạ không giãn. Khi đó, Fix(T ) là một tập lồi và đóng trong H . Chứng minh. Giả sử Fix(T ) 6= ∅. Trước hết, ta chỉ ra Fix(T ) là tập đóng. Thật vậy, vì T là ánh xạ không giãn nên T liên tục trên C . Giả sử {xn } là một dãy bất kỳ trong Fix(T ) thỏa mãn xn → x, khi n → ∞. Vì {xn } ⊂ Fix(T ), nên kT xn − xn k = 0, với mọi n ≥ 1. Từ tính liên tục của chuẩn, cho n → ∞, ta nhận được kT x − xk = 0, tức là x ∈ Fix(T ). Do đó, Fix(T ) là tập đóng. Tiếp theo, ta chỉ ra tính lồi của Fix(T ). Ta có thể chứng minh tính lồi của tập Fix(T ) bằng cách khác như sau: Giả sử Fix(T ) 6= ∅ và x, y ∈ Fix(T ). Với λ ∈ [0, 1], đặt z = λx + (1 − λ)y . Khi đó, từ Mệnh đề 1.1 và tính không giãn của T ta có kT z − zk2 = kλ(T z − x) + (1 − λ)(T z − y)k2
13 = λkT z − xk2 + k(1 − λ)(T z − y)k2 − λ(1 − λ)kx − yk2 = λkT z − T xk2 + (1 − λ)k(T z − T y)k2 − λ(1 − λ)kx − yk2 ≤ λkz − xk2 + (1 − λ)k(z − y)k2 − λ(1 − λ)kx − yk2 = kλ(z − x) + (1 − λ)(z − y)k2 = 0. Suy ra T z = z và do đó z ∈ Fix(T ). Vậy Fix(T ) là một tập lồi. Mệnh đề được chứng minh. Mệnh đề dưới đây cho ta biết về tính nửa đóng của ánh xạ không giãn T . Mệnh đề 1.14 (Nguyên lý nửa đóng, xem [1]). Giả sử T là một ánh xạ không giãn từ tập con lồi, đóng và khác rỗng C của không gian Hilbert thực H vào chính nó. Nếu T có điểm bất động, thì I − T là nửa đóng, tức là nếu {xn } là một dãy trong C hội tụ yếu về phần tử x ∈ C và dãy {(I − T )xn } hội tụ mạnh về phần tử y , thì ta có (I − T )x = y . Chứng minh. Giả sử x − T x 6= y . Vì xn * x, nên xn − y * x − y . Do x − y 6= T x, nên từ Mệnh đề 1.4, ta có lim inf kxn − xk < lim inf kxn − y − T xk n→∞ n→∞ ≤ lim inf (kxn − T xn − yk + kT xn − T xk) n→∞ ≤ lim inf kxn − xk. n→∞ Suy ra mâu thuẫn. Do đó, x − T x = y . Đặc biệt, nếu y = 0 thì x = T x hay x ∈ Fix(T ). Bổ đề được chứng minh. Sự tồn tại điểm bất động đối với lớp ánh xạ không giãn trong không gian Hilbert được phát biểu trong mệnh đề dưới đây: Mệnh đề 1.15. Cho C là một tập con lồi, đóng và bị chặn của không gian Hilbert H . Cho T : C −→ C là một ánh xạ không giãn. Khi đó Fix(T ) 6= ∅.
14 Chứng minh. Lấy x0 ∈ C và dãy {αn } ⊂ (0, 1] sao cho αn → 0. Xác định dãy ánh xạ {Tn } trên C như sau: Tn (x) = αn x0 + (1 − αn )T (x), với mọi n ≥ 1 và mọi x ∈ C . Với mọi x, y ∈ C , ta có kTn (x) − Tn (y)k = (1 − αn )kT (x) − T (y)k ≤ (1 − αn )kx − yk. Suy ra, Tn là ánh xạ co với hệ số co 1 − αn . Theo nguyên lý ánh xạ co Banach1 tồn tại duy nhất xn ∈ C sao cho Tn (xn ) = xn , tức là, xn = αn x0 + (1 − αn )T (xn ). Từ đó suy ra kxn − T (xn )k = αn kx0 − T (xn )k ≤ αn diam(C) → 0. Do đó ta có kxn − T (xn )k → 0. Vì C là tập bị chặn và {xn } ⊂ C nên dãy {xn } cũng bị chặn. Do đó theo Mệnh đề 1.12, tồn tại một dãy con {xnk } ⊆ {xn } sao cho xnk * x∗ khi k → ∞. Do đó, theo Mệnh đề 1.14, ta nhận được x∗ ∈ Fix(T ). Mệnh đề được chứng minh. 1.3. Phương pháp CQ giải bài toán chấp nhận tách Cho C và Q là các tập con lồi, đóng và khác rỗng của các không gian Hilbert H1 và H2 , tương ứng. Cho A : H1 −→ H2 là một toán tử tuyến bị chặn A∗ : H2 → H1 là toán tử liên hợp của A. Bài toán chấp nhận tách (SFP) trong không gian Hilbert được phát biểu như sau: Tìm một phần tử x∗ ∈ S = C ∩ A−1 (Q) 6= ∅. (SFP) 1 Mọi ánh xạ co từ không gian mêtric đầy đủ X vào chính nó đều có duy nhất một điểm bất động.
15 Dạng tổng quát của Bài toán (SFP) là bài toán (MSSFP), bài toán này được phát biểu như sau: Cho Ci , i = 1, 2, ..., t và Qj , j = 1, 2, ..., r là các tập con lồi và đóng của H1 và H2 , tương ứng. Tìm một phần tử x∗ ∈ S = ∩ti=1 Ci ∩ A−1 (∩rj=1 Qj ) 6= ∅. (MSSFP) Một trong những phương pháp cơ bản để giải bài toán (SFP) là phương pháp CQ. Với phương pháp CQ, Bài toán (SFP) được đưa về bài toán tìm một điểm bất động của ánh xạ PC I − γA∗ (I − PQ )A , trong đó γ > 0, PC và PQ lần lượt là các phép chiếu mêtric từE lên Cvà từ F lên Q, tương ứng. 2 ∗ (I − P Ta biết rằng nếu γ ∈ 0, 2 , thì P C I − γA Q A là một ánh xạ không kAk giãn. Do đó, người ta có thể vận dụng các phương pháp tìm điểm bất động của ánh xạ không giãn (phương pháp lặp Mann, phương pháp lặp Halpern, phương pháp xấp xỉ gắn kết) để tìm nghiệm của Bài toán (SFP). Xu [9] đã đưa ra và chứng minh các kết quả dưới đây. Trước hết ông chỉ ra sự hội tụ yếu của phương pháp CQ về một nghiệm của Bài toán (SFP). 2 Định lý 1.1. [9] Nếu γ ∈ 0, 2 thì dãy {xn } xác định bởi x1 ∈ E và kAk xn+1 = PC I − γA∗ (I − PQ )A xn hội tụ yếu về một nghiệm của bài toán (SFP). Sự hội tụ của phương pháp lặp Mann và phương pháp lặp được cho bởi định lý dưới đây: Định lý 1.2. [9] Cho dãy {αn } ⊂ [0, 4/(2 + γkAk2 )] thỏa mãn điều kiện ∞ X 4 αn − αn = ∞. 2 + γkAk2 n=1 2 Nếu γ ∈ 0, thì dãy {xn } xác định bởi x1 ∈ E và kT k2 xn+1 = (1 − αn )xn + αn PC I − γA∗ (I − PQ )A xn , hội tụ yếu về một nghiệm của bài toán (SFP).
16 Năm 2006, Xu [8] đã đưa ra các thuật toán mở rộng của phương pháp CQ dưới đây cho Bài toán (MSSFP). Đặt r 1X p(x) = βj kAx − PQj (Ax)k2 , 2 j=1 trong đó βj > 0 với mọi j = 1, 2, . . . , r. Trước hết, Xu [8] đã chứng minh kết quả dưới đây: Mệnh đề 1.16. Giả sử tập nghiệm của Bài toán (MSSFP) khác rỗng. Khi đó, ta có các khẳng định sau: i) Hàm p(x) là lồi, khả vi với đạo hàm được xác định bởi r X 5p(x) = βj A∗ (I − PQj )Ax, j=1 Pr và 5p(x) là ánh xạ Lipschitz với hằng số L = kAk2 j=1 βj . ii) Phần tử x∗ là một nghiệm của Bài toán (MSSFP) nếu nó là điểm bất động chung của các ánh xạ không giãn trung bình {Ti }ti=1 với Ti = PCi (I − γ 5 p), γ > 0, i = 1, 2, . . . , t. Tiếp đó, ông chứng minh sự hội tụ của phương pháp lặp Picard cho Bài toán (MSSFP). 2 Định lý 1.3. [8] Nếu γ ∈ với βj > 0 với mọi j = 1, 2, . . . , r và L = 0, L Pr kAk2 j=1 βj , thì dãy {xn } xác định bởi x1 ∈ E và r X r X ∗ xn+1 = PCN (I − γ βj A (I − PQj )A . . . PC1 (I − γ βj A∗ (I − PQj )A)xn j=1 j=1 hội tụ yếu về một nghiệm của Bài toán (MSSFP). Xu cũng đã xây dựng và chứng minh sự hội tụ của phương pháp lặp song song và phương pháp lặp xoay vòng cho Bài toán (MSSFP) ở dạng dưới đây: