Luận văn Một số thuật toán chiếu giải bài toán chấp nhận lồi

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 Ci là hình cầu . . . . . . . . . . . . . . . . . . 55 3.3.2. Bài toán với Ci 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 A Một số điểm lưu ý khi tính dưới vi phân 65 1.1. Một vài tính chất của dưới vi phân . . . . . . . . . . . . . . . . . 65 1.2. Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 ii Lời cảm ơn Bản luận văn này được hoàn thành dưới sự hướng dẫn tận tâm và nhiệt tình của thầy- GS.TSKH. Phạm Kỳ Anh. Qua đây em xin bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy. Cũng nhân dịp này, em xin gửi lời cảm ơn đến các anh nghiên cứu sinh Cao Văn Chung, Vũ Tiến Dũng cùng tập thể cán bộ, cộng tác viên, nhân viên của Trung tâm tính toán hiệu năng cao trường ĐH Khoa học Tự nhiên vì sự giúp đỡ tận tình và rất hiệu quả trong quá trình thực hiện luận văn. Em cũng xin gửi lời cảm ơn tới các thầy trong Bộ môn Toán học tính toán cùng toàn thể thầy giáo, cô giáo trong Khoa Toán-Cơ-Tin học trường ĐH Khoa học Tự nhiên-ĐH Quốc gia Hà Nội đã nhiệt tình giảng dạy, tạo điều kiện và giúp em thu được nhiều kiến thức bổ ích trong suốt quá trình học tập. Hà Nội, ngày 29 tháng 11 năm 2009 Học viên Vũ Anh Mỹ iii Mở đầu Nhiều vấn đề của khoa học và công nghệ đưa về bài toán tìm một điểm trong giao của một số tập lồi. Bài toán này được gọi là Bài toán chấp nhận lồi: Cho X là một không gian Hilbert và C1, C2, . . . , CN là các tập lồi đóng với giao là một tập C khác rỗng: C = C1 ∩ . . . ∩ CN 6= ∅. 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 Ci là đơn giản theo nghĩa các phép chiếu (trực giao) lên Ci có thể tính toán được tường minh. Ci 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 Ci, 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 Ci. Ci 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 Ci hoặc tập xấp xỉ Ci để xây dựng một dãy các phần tử hội tụ đến nghiệm của bài toán chấp nhận lồi. Một số ứng dụng của bài toán chấp nhận lồi có thể kể ra như sau: • Bài toán xấp xỉ tốt nhất, trong đó mỗi tập Ci là một không gian con đóng. • Khôi phục ảnh (mô hình rời rạc): Mỗi tập Ci là một nửa không gian hoặc một siêu phẳng, X là một không gian Euclid. • Khôi phục ảnh (mô hình liên tục): X là không gian Hilbert vô hạn chiều. • Các thuật toán dưới gradient: Một số tập Ci thuộc loại thứ 2, tức là tập mức dưới của một hàm lồi. 1 Trong luận văn này chúng tôi nghiên cứu thuật toán chiếu tổng quát: x(n+1) = A(n)x(n) = ( N∑ i=1 λ (n) 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 Ai(x) = 0, i = 1, . . . , N dạng:  Aix (n) i + (αn N + γn ) x (n) i = γnx (n), 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 Ci 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 song áp dụng cho bài toán chấp nhận lồi cùng các thử nghiệm số cho các thuật toán trình bày trong Chương 2. 2 Chương 1. Một số kiến thức chuẩn bị 1.1. ánh xạ không giãn Định nghĩa 1. Cho X là một không gian Hilbert, một ánh xạ T : D → D, trong đó D là một tập con lồi, đóng, khác rỗng của X gọi là không giãn nếu ‖Tx− Ty‖ ≤ ‖x− y‖ ∀x, y ∈ D Nếu ‖Tx− Ty‖ = ‖x− y‖ ∀x, y ∈ D, ta nói T là phép đẳng cự. Ngược lại, nếu ‖Tx−Ty‖ < ‖x− y‖ với mọi x, y khác nhau trong D ta nói T là ánh xạ không giãn chặt. Nếu T là ánh xạ không giãn thì tập điểm bất động của T , ký hiệu FixT định nghĩa bởi: FixT = {x ∈ D : x = Tx} là tập lồi đóng. Mệnh đề 1 (Nguyên lý tính nửa đóng). Nếu D là một tập con lồi đóng của X , T : D −→ X là ánh xạ không giãn, (xn) là một dãy trong D và x ∈ D, khi đó nếu xn ⇀ x và xn − Txn → 0 thì x ∈ FixT . Chứng minh: Từ giả thiết xn ⇀ x và ta có lim inf n→∞ ‖xn − x0‖ > lim infn→∞ ‖xn − x‖ với mọi x0 6= x. Thật vậy, từ đẳng thức ‖xn − x0‖2 = ‖xn − x‖2 + ‖x− x0‖2 + 2〈xn − x, x− x0〉 3 và do giả thiết xn ⇀ x, số hạng cuối tiến tới 0. Bây giờ giả sử xn ⇀ x và xn − Txn −→ 0, do T không giãn ta có lim inf n→∞ ‖xn − x‖ ≥ lim infn→∞ ‖Txn − Tx‖ = lim infn→∞ ‖xn − Tx‖, từ bất đẳng thức chứng minh ở trên ta suy ra x = Tx hay x ∈ FixT . Ơ Định nghĩa 2. Nếu N là một ánh xạ không giãn thì ánh xạ trung bình (1−α)I+ αN với α ∈ [0, 1) cũng là ánh xạ không giãn. Một ánh xạ không giãn vững là một ánh xạ trung bình có dạng 1 2I + 1 2N 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 ‖Tx − Ty‖ ≤ ‖x − y‖, ánh xạ còn thỏa mãn bất đẳng thức chặt hơn là ‖Tx− Ty‖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) ‖Tx− Ty‖2 ≤ 〈Tx− Ty, x− y〉 (T là 1−ngượ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 Mệnh đề 3. Giả sử C là một tập con lồi đóng khác rỗng của X với phép chiếu tương ứng là PC . Khi đó: (i) Nếu x ∈ X thì PCx được đặc trưng bởi 2 tính chất: PCx ∈ C và 〈C − PCx, x− PCx〉 ≤ 0 (tiêu chuẩn Kolmogorov). (ii) PC là ánh xạ không giãn vững. Chứng minh: (i): Ta sẽ chứng minh ‖x− PCx‖ = min{‖x− z‖ : z ∈ C} ⇐⇒ 〈x− PCx, PCx− z〉 ≥ 0 ∀z ∈ C. Ta có ‖x− z‖2 = ‖x− PCx+ PCx− z‖2 = ‖x− PCx‖2 + 2〈x− PCx, PCx− z〉+ ‖PCx− z‖2 ≥ ‖x− PCx‖2 + 2〈x− PCx, PCx− z〉 Như vậy, từ 〈x−PCx, PCx−z〉 ≥ 0 ta suy ra ‖x−PCx‖ = min{‖x−z‖ : z ∈ C}. Ngược lại từ ‖x−PCx‖ = min{‖x−z‖ : z ∈ C}. Chọn điểm λz+(1−λ)PCx ∈ C, λ > 0, ta có 0 ≥ ‖x− PCx‖2 − ‖x− (λz + (1− λ)PCx)‖2 = ‖x− PCx‖2 − ‖x− PCx− λ(z − PCx)‖2 = 2〈x− PCx− λ(z − PCx), λ(z − PCx〉 ⇔ 0 ≥ 〈x− PCx− λ(z − PCx), z − PCx〉 Cho λ → 0 0 ≥ 〈x− PCx, z − PCx〉 ⇔ 〈x− PCx, PCx− z〉 ≥ 0 (ii): Để chứng minh PC là ánh xạ không giãn vững, dựa vào mệnh đề 2, ta chỉ cần chỉ ra 〈PCx− PCy, x− y〉 ≥ ‖PCx− PCy‖2. 5 Bất đẳng thức này tương đương với 〈x− y− (PCx− PCy), PCx− PCy〉 ≥ 0. Để chứng minh điều này, từ tiêu chuẩn Kolmogorov áp dụng cho PCy và PCx ta có 〈x− PCx, PCx− PCy〉 ≥ 0, 〈PCy − y, PCx− PCy〉 ≥ 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 7−→ inf c∈C ‖x−c‖ = ‖x−PCx‖ 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 (xn) 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 ‖xn − x‖ ≤ αβn ∀n Mệnh đề 4. Giả sử (xn) 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 (xpn)n hội tụ tuyến tính tới x và (‖xn−x‖)n là dãy giảm thì toàn bộ dãy (xn)n cũng hội tụ tuyến tính tới x. 1.2. ánh xạ hút và dãy đơn điệu Fejer Định nghĩa 6. Giả sử D là một tập lồi đóng khác rỗng, T : D → D là ánh xạ không giãn và F là một tập con lồi đóng khác rỗng của D. Ta nói T là ánh xạ hút đối với tập F nếu với mọi x ∈ D \ F, f ∈ F ‖Tx− f‖ < ‖x− f‖ Ta nói T là hút mạnh đối với với tập F nếu tồn tại một số κ > 0 sao cho với mọi x ∈ D, f ∈ F κ‖x− Tx‖2 ≤ ‖x− f‖2 − ‖Tx− f‖2 6 Khi cần nhấn mạnh ta nói T là κ− hút đối với tập F . Bổ đề 1 (Dạng của một ánh xạ hút mạnh). Giả sử D là tập lồi đóng khác rỗng, T : D → D là ánh xạ không giãn vững có điểm bất động, và α ∈ (0, 2). Đặt R = (1− α)I + αT và cố định x ∈ D, f ∈ FixT . Khi đó: (i) FixR = FixT . (ii) 〈x− f, x− Tx〉 ≥ ‖x− Tx‖2 và 〈x− Tx, Tx− f〉 ≥ 0. (iii) ‖x− f‖2 − ‖Rx− f‖2 = 2α〈x− f, x− Tx〉 − α2‖x− Tx‖2. (iv) R là (2 − α)/α-hút: ‖x − f‖2 − ‖Rx − f‖2 ≥ (2 − α)/α‖x − Rx‖2 = (2− α)α‖x− Tx‖2 Chứng minh: (i) là hiển nhiên. (ii): Do T là ánh xạ không giãn vững, ta có ‖Tx− f‖2 ≤ 〈Tx− f, x− f〉 ⇐⇒‖Tx− x‖2 + ‖x− f‖2 + 2〈Tx− x, x− f〉 ≤ 〈Tx− f, x− f〉 ⇐⇒‖Tx− x‖2 + ‖x− f‖2 + 2〈Tx− x, x− f〉 ≤ 〈Tx− x, x− f〉+ ‖x− f‖2 ⇐⇒‖Tx− x‖2 ≤ 〈x− Tx, x− f〉 = 〈x− Tx, Tx− f〉+ ‖x− Tx‖2 ⇐⇒0 ≤ 〈x− Tx, Tx− f〉. (iii): Bằng tính toán trực tiếp ‖x− f‖2 − ‖Rx− f‖2 =‖x− f‖2 − ‖(1− α)(x− f) + α(Tx− f)‖2 =‖x− f‖2 − [1− α)2‖x− f‖2 + α2‖Tx− f‖2 + 2α(1− α)〈x− f, Tx− f〉] =2α‖x− f‖2 − α2‖x− f‖2 − α2‖Tx− f‖2 + 2α2〈x− f, Tx− f〉 − 2α〈x− f, Tx− f〉 =2α〈x− f, x− f − (Tx− f)〉 − α2[‖x− f‖2 + ‖Tx− f‖2 − 2〈x− f, Tx− f〉] =2α〈x− f, x− Tx〉 − α2‖x− Tx‖2. 7 (iv): Từ (ii), (iii) và định nghĩa R ta có ‖x− f‖2 − ‖Rx− f‖2 = 2α〈x− f, Tx− f〉 − α2‖x− Tx‖2 ≥ 2α‖x− Tx‖2 − α2‖x− Tx‖2 = α(2− α)‖x− Tx‖2 = 2− α α ‖x−Rx‖2. Bổ đề chứng minh xong. Ơ Hệ quả 2. Nếu P là một phép chiếu lên một tập lồi đóng khác rỗng S và α ∈ (0, 2), thì R := (1− α)I + αP là (2− α)/α-hút đối với S và với x ∈ X, s ∈ S ‖x− s‖2 − ‖Rx− x‖2 ≥ (2− α)αd2(x, S). Định nghĩa 7. Giả sử (xn) là một dãy trong X . Ta nói (xn) là chính quy tiệm cận nếu xn − xn+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à (Tn)n≥0 là dãy các tự ánh xạ không giãn của D, trong đó mỗi ánh xạ Tn là κn-hút tương ứng với F và limn κn > 0. Giả sử thêm rằng dãy (xn) được định nghĩa bởi x0 ∈ D tùy ý;xn+1 := Tnxn ∀n ≥ 0. Khi đó dãy (xn) là chính quy tiệm cận. Chứng minh: Cố định f ∈ F và chọn số 0 < κ < lim inf n κn. Khi đó, với mọi n đủ lớn, κ‖xn+1 − xn‖2 ≤ ‖xn+1 − f‖2 − ‖xn − f‖2. Cộng từng vế suy ra chuỗi ∑ n ‖xn+1 − xn‖2 hội tụ, từ đó ‖xn+1 − xn‖ → 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 nx0)n≥0 là chính quy tiệm cận với mọi x0 ∈ D. 8 Về bản chất, toán tử A = A(0)A(1) . . . A(n) chính là hợp thành của các tổ hợp lồi các ánh xạ không giãn vững. Mệnh đề dưới đây chỉ ra rằng tính chất hút(hút mạnh) bảo toàn qua phép hợp thành và lấy tổ hợp lồi. Mệnh đề 5. Giả sử D là một tập lồi đóng, khác rỗng; T1, T2, . . . , TN : D → D là các ánh xạ κi-hút và N⋂ i=1 FixTi là tập khác rỗng, λ1, λ2, . . . , λN > 0 và N∑ i=1 λi = 1 Khi đó: (i) Fix(TNTN−1. . . . .T1) = N⋂ i=1 FixTi và TNTN−1. . . . .T1 làmin{κ1, . . . , κN}/2N−1- hút. (ii) Fix( N∑ i=1 λiTi) = N⋂ i=1 FixTi và N∑ i=1 λiTi là min{κ1, . . . , κN}-hút. Chứng minh: Ta chỉ cần chứng minh cho trường hợp N = 2. (i) Hiển nhiên là FixT1 ∩ FixT2 ⊆ Fix(T2T1). Để chứng minh bao hàm thức ngược lại, chọn f ∈ Fix(T2T1) bất kỳ. Chỉ cần chỉ ra rằng f ∈ FixT1. Giả sử điều này sai, khi đó T1f 6∈ FixT2. Cố định fˆ ∈ FixT1 ∩ FixT2, do T2 là hút ta có ‖f − fˆ‖ = ‖T2(T1f)− fˆ‖ < ‖T1f − fˆ‖ ≤ ‖f − fˆ‖. Điều này vô lý do đó FixT1∩FixT2 = Fix(T2T1). Tiếp theo ta chứng minh T2T1 là ánh xạ hút. Cố định x ∈ D \ Fix(T2T1), f ∈ Fix(T2T1). Nếu x = T1x thì T2x 6= x và do đó ‖T2T1x− f‖ = ‖T2x− f‖ < ‖x− f‖. Ngược lại, nếu T1x 6= x thì ‖T2T1x− f‖ ≤ ‖T1x− f‖ < ‖x− f‖. Trong cả hai trường hợp ta đều có kết luận T2T1 là ánh xạ hút. Để chứng minh phần còn lại, cho x ∈ D, f ∈ Fix(T2T1). Ta có đánh giá sau: ‖x− T2T1x‖2 ≤ (‖x− T1x‖+ ‖T1x− T2T1x‖)2 ≤ 2(‖x− T1x‖2 + ‖T1x− T2T1x‖2) ≤ 2 κ1 (‖x− f‖2 − ‖T1x− f‖2) + 2 κ2 (‖T1x− f‖2 − ‖T2T1x− f‖2) ≤ 2 min{κ1, κ2}(‖x− f‖ 2 − ‖T2T1x− f‖2). 9 (i) chứng minh xong. (ii). Hiển nhiên là FixT1 ∩ FixT2 ⊆ Fix(λ1T1 + λ2T2). Để chứng minh chiều ngược lại, chọn f ∈ Fix(λ1T1 + λ2T2), fˆ ∈ FixT1 ∩ FixT2. Khi đó ta có ‖f − fˆ‖ = ‖λ1T1f + λ2T2f − λ1fˆ − λ2fˆ‖ ≤ λ1‖T1f − fˆ‖+ λ2‖T2f − fˆ‖ ≤ λ1‖f − fˆ‖+ λ2‖f − fˆ‖ = ‖f − fˆ‖. Do đó dấu bằng phải xảy ra ở các bất đẳng thức nói trên; kết hợp với tính lồi chặt của không gian Hilbert X ta suy ra f = T1f = T2f . Vậy f ∈ FixT1 ∩ FixT2. Tiếp theo ta chứng minh λ1T1 + λ2T2 là hút. Giả sử x 6= λ1T1x + λ2T2x và f ∈ Fix(λ1T1 + λ2T2). Khi đó x 6∈ FixT1 ∩ FixT2 và do đó ‖λ1T1x+ λ2T2x− f‖ ≤ λ1‖T1x− f‖+ λ2‖T2x− f‖ < λ1‖x− f‖+ λ2‖x− f‖ = ‖x− f‖. Nếu κ = min{κ1, κ2} và f ∈ Fix(λ− 1T1 + λ2T2) thì ta có κ‖x− (λ1T1x+ λ2T2x)‖2 ≤ κ(λ1‖x− T1x‖+ λ2‖x− T2x‖)2 ≤ κ(λ1‖xT1x‖2 + λ2‖x− T − 2x‖2) ≤ λ1κ1‖x− T1x‖2 + λ2κ2‖x− T2x‖2 ≤ λ1(‖x− f‖2 − ‖T1x− f‖2) + λ2(‖x− f‖2 − ‖T2x− f‖2) ≤ ‖x− f‖2 − ‖(λ1T1x+ λ− 2T2x)− f‖2. Ơ Ví dụ 2. Giả sử S1, S2, . . . , SN là các tập lồi đóng, khác rỗng với các phép chiếu P1, . . . , PN và có giao khác rỗng. Khi đó T := P1 + P2P1 + ã ã ã+ PN . . . P1 N là hút mạnh, FixT = N⋂ i=1 Si và dãy lặp (T nx0) là chính quy tiệm cận với mọi x0. 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à FixT = N⋂ i=1 Si. áp dụng hệ quả 3 dãy (T nx0) 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à (xn) là một dãy trong X . Ta nói dãy (xn)n≥0 là đơn điệu Fejer tương ứng với C nếu ‖xn+1 − c‖ ≤ ‖xn − c‖ ∀c ∈ C;n ≥ 0. Định lý 1 (Tính chất cơ bản của dãy đơn điệu Fejer). Giả sử dãy (xn)n≥0 là đơn điệu Fejer tương ứng với C. Khi đó: (i) (xn) bị chặn và d(xn+1, C) ≤ d(xn, C). (ii) (xn) có nhiều nhất một điểm dính yếu trong C. Hệ quả là (xn) hội tụ yếu đến một điểm trong C khi và chỉ khi tất cả các điểm dính yếu của (xn) nằm trong C. (iii) Nếu phần trong của C khác rỗng thì dãy (xn) hội tụ theo chuẩn. (iv) Dãy (PCxn) hội tụ theo chuẩn. (v) Các tính chất sau tương đương: (1) (xn) hội tụ theo chuẩn đến một điểm thuộc C. (2) (xn) có các điểm dính theo chuẩn và tất cả đều nằm trong C. (3) (xn) có các điểm dính theo chuẩn và một điểm nằm trong C. (4) d(xn, C) → 0. (5) xn − PCxn → 0. Hơn nữa, nếu (xn) hội tụ đến một điểm x ∈ C, thì ‖xn−x‖ ≤ 2d(xn, C) ∀n ≥ 0. 11 (vi) Nếu tồn tại một hằng số α > 0 sao cho αd2(xn, C) ≤ d2(xn, C) − d2(xn+1, C) với mọi n, thì (xn) hội tụ tuyến tính tới một điểm x ∈ C, hơn nữa ‖xn − x‖ ≤ 2(1− α)n/2d(x0, C) ∀n ≥ 0. Chứng minh: (i) là hiển nhiên. (ii): Với mỗi c ∈ C, dãy (‖xn‖2 − 2〈xn, c〉) = (‖xn − c‖2 − ‖c‖2) hội tụ. Do đó nếu c1, c2 là hai điểm dính yếu của dãy (xn) trong C thì ta cũng kết luận được dãy (〈xn, c1 − c2〉) hội tụ và do đó 〈c1, c1 − c2〉 = 〈c2, c1 − c2〉. Do đó c1 = c2. (iii): Cố định một điểm c0 ∈ intC, khi đó tồn tại số dương đủ bé ε sao cho c0 + εBX ⊆ C. Ta sẽ chứng minh 2ε‖xn − xn+1‖ ≤ ‖xn − c0‖2 − ‖xn+1 − c0‖2 ∀n ≥ 0. Thật vậy, ta có thể giả sử xn 6= xn+1. Khi đó c0 + ε xn−xn+1‖xn−xn+1‖ ∈ C, và do tính đơn điệu Fejer ta có∥∥∥(c0 + ε xn − xn+1‖xn − xn+1‖ ) − xn+1 ∥∥∥ ≤ ∥∥∥(c0 + ε xn − xn+1‖xn − xn+1‖ ) − xn ∥∥∥. Bình phương hai vế và giản ước ta được điều cần chứng minh. Khi đó, vì dãy (‖xn− c0‖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 (xn) 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 = 2‖a‖2 + 2‖b‖2 − ‖a + b‖2 cho a := PCxn+k − xn+k và b := PCxn − xn+k với mọi n, k ≥ 0 ta nhận được, ‖PCxn+k − PCxn‖2 = 2‖PCxn+k − xn+k‖2 + 2‖PCxn − xn+k‖2 − 4‖PCxn+k + PCxn 2 − xn+k‖2 ≤ 2‖PCxn+k − xn+k‖2 + 2‖PCxn − xn+k‖2 − 4‖PCxn+k − xn+k‖2 ≤ 2‖PCxn − xn+k − xn+k‖2 − 2‖PCxn+k − xn+k‖2 ≤ 2(‖PCxn − xn‖2 − ‖PCxn+k − xn+k‖2). 12 Ta nhận thấy rằng (PCxn) là dãy Cauchy vì dãy ‖xn − PCxn‖ hội tụ do (i). (v): Sự tương đương giữa các mệnh đề dễ dàng suy ra từ (i), (iv) và định nghĩa đơn điệu Fejer. Ta có : ‖xn+k − xn‖ ≤ ‖xn+k − PCxn‖+ ‖PCxn − xn‖ ≤ ‖xn − PCxn‖+ ‖PCxn − xn‖ = 2d(xn, C). Cho k −→∞ ta được đánh giá ‖xn − x‖ ≤ 2d(xn, C). (vi): Từ bất đẳng thức đã cho, cộng từng vế ta suy ra d2(xn, C) tiến tới 0; do đó (xn) 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 (xn) 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 (xn) cho bởi: x0 ∈ C, xn+1 = (1− tn)xn + tnTxn , n ≥ 0, (tn)n≥0 ⊂ [0, 1]. Khi đó (xn) là đơn điệu Fejer đối với FixT Chứng minh: Kiểm tra trực tiếp, chọn f ∈ FixT bất kỳ. Ta có li ‖xn+1 − f‖2 = ‖xn − f + tn(Txn − xn)‖2 = ‖xn − f‖2 + 2tn〈xn − f, Txn − xn〉+ t2n‖Txn − xn‖2 Nếu tn = 0 thì ‖xn+1−f‖ = ‖xn−f‖, nếu tn = 1 thì ‖xn+1−f‖ = ‖Txn−Tf‖ ≤ ‖xn − f‖. Ta chỉ cần xét tn ∈ (0, 1). Ta có 2〈xn − f, Txn − xn〉+ tn‖txn − xn‖2 < 2〈xn − f, Txn − xn〉+ ‖Txn − xn‖2 = ‖xn − f + Txn − xn‖2 − ‖xn − f‖2 = ‖Txn − f‖2 − ‖xn − f‖2 = ‖Txn − Tf‖2 − ‖xn − f‖2 ≤ 0 do T là ánh xạ không giãn. 13 Từ đẳng thức trên cho ‖xn+1 − f‖2ta suy ra điều cần chứng minh. Ơ Ví dụ 4. Tiếp theo ví dụ 2, dãy (T nx0) hội tụ yếu tới một điểm bất động của T với mọi x0. Chứng minh: Dãy (T nx0) là chính quy tiệm cận theo ví dụ đã xét, và nó là đơn điệu Fejer tương ứng với FixT theo ví dụ 3. Theo nguyên lý tính nửa đóng, mọi điểm giới hạn yếu của (T nx0) nằm trong FixT , á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à C1, . . . , CN 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 Ci 6= ∅. 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à FixTi ⊇ Ci. và α (n) i ∈ [0, 2] là tham số nới lỏng và R (n) i := (1− α(n)i )I + α(n)i T (n)i là nới lỏng tương ứng của T (n) i , (λ (n) i ) N i=1 là các trọng, cuối cùng A(n) := N∑ i=1 λ (n) 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 c