Tài liệu Thuật toán tách lions mercier và phương pháp luân hướng tìm không điểm của tổng hai toán tử đơn điệu

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGÔ DUY TOẢN THUẬT TOÁN TÁCH LIONS-MERCIER VÀ PHƯƠNG PHÁP LUÂN HƯỚNG TÌM KHÔNG ĐIỂM CỦA TỔNG HAI TOÁN TỬ ĐƠN ĐIỆU LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGÔ DUY TOẢN THUẬT TOÁN TÁCH LIONS-MERCIER VÀ PHƯƠNG PHÁP LUÂN HƯỚNG TÌM KHÔNG ĐIỂM CỦA TỔNG HAI TOÁN TỬ ĐƠN ĐIỆU LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 GIÁO VIÊN HƯỚNG DẪN GS.TS. NGUYỄN BƯỜNG THÁI NGUYÊN - 2016 i Mục lục Bảng ký hiệu ii Mở đầu 1 Chương 1. Không gian Hilbert và toán tử đơn điệu cực đại 3 1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . . 1.2 Toán tử đơn điệu cực đại . . . . . . . . . . . . . . . . . . . . 3 8 Chương 2. Thuật toán tách Lions–Mercier và phương pháp luân hướng tìm không điểm của tổng hai toán tử đơn điệu cực đại 16 2.1 Phương pháp tách . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Mô tả phương pháp . . . . . . . . . . . . . . . . . . . 16 2.1.2 Triển khai phương pháp . . . . . . . . . . . . . . . . 20 2.2 Mối quan hệ của phương pháp ngược từng phần . . . . . . 24 2.2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.2 Mối quan hệ với thuật toán tách Lions–Mercier . . . 26 2.3 Phương pháp luân hướng . . . . . . . . . . . . . . . . . . . . 27 2.3.1 Nguồn gốc của phương pháp luân hướng . . . . . . . 27 2.3.2 Mối liên hệ với phương pháp tách . . . . . . . . . . . 28 Kết luận 32 Tài liệu tham khảo 33 ii Bảng ký hiệu Trong toàn luận văn, ta dùng những ký hiệu với các ý nghĩa xác định trong bảng dưới đây: R tập số thực Rn , Rm H H∗ không gian véc tơ n, m chiều tương ứng không gian Hilbert thực không gian liên hợp của H C[a, b] conv C tập các hàm thực lien tục trên [a, b] bao lồi của tập C conv C A∗ A bao lồi đóng của tập C toán tử liên hợp của toán tử A toán tử mở rộng của toán tử A dom A gra A domf miền xác định của toán tử A đồ thị của toán tử A miền hữu hiệu của hàm f epif zer(A) Jr,T tập trên đồ thị của hàm f tập tất cả không điểm của A, A−1 (0) toán tử giải của toán tử T NC ∅ δC (.) hình nón chuẩn tắc ứng với tập lồi C tập rỗng hàm chỉ trên C V⊥ bù vuông góc của không gian con V 1 Mở đầu Cho A và B là hai toán tử đơn điệu cực đại trong không gian Hilbert H, C := A + B. Nội dung của đề tài luận văn nghiên cứu bài toán tìm không điểm của toán tử C trên cơ sở kết quả của J. Eckstein [4]. Để giải bài toán này, J. Eckstein [4] đưa vào toán tử đơn điệu cực đại Sλ,A,B mà tập không điểm của nó xấp xỉ tập không điểm của A + B. Trong trường hợp B là nón chuẩn tắc của một không gian con tuyến tính thì Sλ,A,B trùng với ngược từng phần của toán tử Spingarn (xem [12], [13]). Ngoài ra, khi r = 1 thì toán tử giải (I + rSλ,A,B )−1 của Sλ,A,B là toán tử G(λ) của Lions–Mercier [6]. Vì vậy, thuật toán Lions–Mercier thực sự là thuật toán điểm gần kề ứng dụng cho toán tử Sλ,A,B . Ngoài ra, J. Eckstein [4] cũng chỉ ra rằng kỹ thuật của Spingarn cho cực tiểu phiếm hàm lồi trên không gian con tuyến tính thực chất là một trường hợp riêng trong cách tiếp cận của Lions–Mercier. Đồng thời thuật toán Lions–Mercier mở rộng thuật toán luân hướng trong qui hoạch lồi đã được chỉ ra bởi Gabay [5] và thuật toán luân hướng cũng là một ví dụ của thuật toán điểm gần kề. Mục đích của đề tài luận văn là trình bày lại kết quả của J. Eckstein [4] về mối quan hệ giữa một số thuật toán tìm không điểm của toán tử đơn điệu cực đại: thuật toán điểm gần kề được đưa ra bởi Martinet [7], sau đó được phát triển bởi Rockafellar [10]; phương pháp Lions–Mercier tìm không điểm của tổng hai toán tử đơn điệu cực đại [6]; phương pháp ngược từng phần của Spingarn cho toán tử đơn điệu cực đại [12], [13]. Nội dung của đề tài luận văn được viết trong hai chương: Chương 1: "Không gian Hilbert và toán tử đơn điệu cực đại". Chương này giới thiệu về không gian Hilbert trên trường số thực và một số kiến 2 thức cơ bản về giải tích lồi. Tiếp theo là giới thiệu về toán tử đơn điệu cực đại và định nghĩa bài toán tìm không điểm của toán tử. Chương 2: "Thuật toán tách Lions–Mercier và phương pháp luân hướng tìm không điểm của tổng hai toán tử đơn điệu cực đại". Chương này nghiên cứu một số phương pháp tìm không điểm của tổng hai toán tử đơn điệu cực đại, chỉ ra phương pháp Lion–Mercier thực chất là trường hợp đặc biệt của thuật toán điểm gần kề, đồng thời nêu nguồn gốc của phương pháp luân hướng và đưa ra mối quan hệ với thuật toán tách. Luận văn này được hoàn thành tại Trường Đại học Khoa học - Đại học Thái Nguyên dưới sự hướng dẫn tận tình của GS. TS. Nguyễn Bường, tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy, người đã người dành nhiều thời gian và tâm huyết để hướng dẫn tận tình, giúp đỡ tôi trong quá trình học tập, nghiên cứu và viết bản luận văn này. Tôi cũng xin chân thành cảm ơn Lãnh đạo Trường Đại học Khoa học – Đại học Thái Nguyên, Ban chủ nhiệm khoa Toán – Tin cùng toàn thể các thầy cô trong và ngoài trường đã giảng dạy giúp tác giả trau dồi thêm rất nhiều kiến thức phục vụ cho việc học tập và nghiên cứu của bản thân. Tác giả xin gửi lời cảm ơn chân thành đến các thầy cô. Cuối cùng tác giả xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện tốt nhất cho tác giả trong quá trình học tập, nghiên cứu và làm luận văn. Xin chân thành cảm ơn! Thái Nguyên, tháng 6 năm 2016 Học viên Ngô Duy Toản 3 Chương 1 Không gian Hilbert và toán tử đơn điệu cực đại Chương này trình bày một số khái niệm và tính chất cơ bản của không gian Hilbert thực H, giới thiệu về toán tử đơn điệu cực đại, định nghĩa không điểm để phục vụ cho chương sau. Các kiến thức của chương được tổng hợp từ tài liệu [7], [10]. 1.1 Không gian Hilbert Định nghĩa 1.1.1 Cho H là không gian tuyến tính xác định trên trường số thực R. Một tích vô hướng trong H là một ánh xạ h·, ·i : H × H → R thỏa mãn các tính chất sau: i. hx, xi ≥ 0, ∀x ∈ H và hx, xi = 0 khi và chỉ khi x = 0, ii. hx, yi = hy, xi , ∀x, y ∈ H, iii. hx + y, zi = hx, zi + hy, zi , ∀x, y, z ∈ H, iv. hαx, yi = α hx, yi , ∀x, y ∈ H, ∀α ∈ R. Số thực hx, yi được gọi là tích vô hướng của hai véctơ x và y. Cặp (H, h·, ·i) gọi là không gian tiền Hilbert. Định lý 1.1.2 (Bất đẳng thức Cauchy–Schwarz) Trong không gian tiền Hilbert H, ∀x, y ∈ H ta luôn có bất đẳng thức sau: |hx, yi|2 ≤ hx, xi.hy, yi. 4 Chứng minh. Với y = 0 bất đẳng thức hiển nhiên đúng. Giả sử y 6= 0 khi đó ∀λ ∈ R ta có: hx + λy, x + λyi > 0, nghĩa là hx, xi + λhy, xi + λhx, yi + |λ|2 hy, yi > 0. |hx, yi|2 hx, yi ta được hx, xi− > 0 hay |hx, yi|2 ≤ hx, xi.hy, yi. Chọn λ = − hy, yi hy, yi Bất đẳng thức được chứng minh.  Dấu bằng trong bất đẳng thức Schwarz xảy ra khi và chỉ khi x và y phụ thuộc tuyến tính. Mối quan hệ giữa khái niệm chuẩn và tích vô hướng được thể hiện qua nhận xét sau: Nhận xét 1.1.3 Mọi không gian tiền Hilbert H là không gian tuyến tính định chuẩn, với chuẩn được xác định: kxk = p hx, xi, x ∈ H. Bất đẳng thức Schwarz được viết lại: |hx, yi| ≤ kxk.kyk. Định nghĩa 1.1.4 Cho X là không gian định chuẩn, dãy {xn } ⊂ X gọi là dãy cơ bản nếu: lim kxn − xm k = 0. m,n→∞ Nếu trong X mọi dãy cơ bản đều hội tụ, tức là kxn − xm k → 0 kéo theo sự tồn tại x0 ∈ X sao cho xn → x0 thì X được gọi là không gian đủ. Định nghĩa 1.1.5 Không gian tiền Hilbert đầy đủ gọi là không gian Hilbert. Ví dụ 1.1.6 Trong Rn , x = (x1, x2 ..., xn) , y = (y1 , y2 ..., yn) ∈ Rn, ta đưa n P xk yk vào tích vô hướng hx, yi = k=1 5 do đó 2 kxk = hx, xi = n X xk xk = |xk |2. k=1 k=1 Khi đó Rn là không gian Hilbert. n X Ví dụ 1.1.7 Trong không gian C[a, b] tập tất cả các hàm thực liên tục trên [a, b]. Xét tích vô hướng: hx, yi = Zb x(t)y(t)dt, x(t), y(t) ∈ C[a, b]. a Khi đó: i. Không gian C[a,b] với chuẩn kxk = max |x(t)| là không gian Banach a6t6b nên C[a, b] là không gian Hilbert; ii. Không gian C[a,b] với chuẩn kxk = Rb !1/2 |x(t)|2 dt a không là không gian Banach do đó C[a, b] không là không gian Hilbert. Định nghĩa 1.1.8 Tập A ⊂ H gọi là tập lồi nếu ∀x1, x2 ∈ A và mọi số thực t ∈ [0, 1] ta đều có tx1 + (1 − t)x2 ∈ A. Nhận xét 1.1.9 Theo định nghĩa, tập ∅ là tập lồi. Ví dụ 1.1.10 Các tập sau đây đều là tập lồi: Rn , ∅, {x} , hình cầu đóng, hình cầu mở, các nửa không gian đóng, nửa không gian mở. Định nghĩa 1.1.11 Cho C ⊂ H. Bao lồi của C là giao của tất cả các tập con lồi của H chứa C, ký hiệu là conv C. Bao lồi đóng của C là tập con lồi đóng nhỏ nhất của H chứa C, ký hiệu là conv C. Định nghĩa 1.1.12 Tập A ⊆ Rn được gọi là nón có đỉnh tại gốc O nếu: ∀x ∈ A, ∀λ > 0 ⇒ λx ∈ A. 6 A ⊆ Rn được gọi là nón có đỉnh tại x0 nếu A − x0 có đỉnh tại O. Nón A gọi là nón lồi nếu tập A là lồi. Định nghĩa 1.1.13 Cho tập lồi S ⊆ Rn , hàm f : S → (−∞, +∞) được gọi là: i. Hàm lồi trên S nếu với mọi số thực 0 ≤ λ ≤ 1, ∀x, y ∈ S, ta có: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y); ii. Hàm lồi chặt trên S nếu với mọi số thực 0 ≤ λ ≤ 1, ∀x, y ∈ S, x 6= y ta có: f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y); iii. Hàm f được gọi là hàm lõm (lõm chặt) trên S nếu −f là lồi (lồi chặt) trên S; iv. Hàm f được gọi là tuyến tính afin trên S nếu f vừa lồi vừa lõm trên S. Một hàm afin trên Rn có dạng f (x) = ha, xi + α với a ∈ Rn , như vậy ∀x, y ∈ Rn , ∀λ ∈ [0, 1] ta có: f (λx + (1 − λ)y) = λf (x) + (1 − λ)f (y). Tuy nhiên, hàm afin không lồi chặt hay lõm chặt. Nếu H là không gian Hilbert thì H cũng là không gian định chuẩn, không gian liên hợp của H là H∗ = L(H, K). Định lý sau đây nêu lên đặc trưng của phiếm hàm tuyến tính liên tục trên không gian Hilbert H. Định lý 1.1.14 Với mỗi véctơ a cố định thuộc không gian Hilbert H, hệ thức: f (x) = hx, ai, ∀x ∈ H (1.1) xác định một phiếm hàm tuyến tính liên tục f (x) trên không gian Hilbert 7 H với kf (x)k = kak. (1.2) Ngược lại với bất kì phiếm hàm tuyến tính liên tục f (x) nào trên không gian Hilbert H cũng đều có thể biểu diễn một cách duy nhất dưới dạng (1.1), trong đó a là một véctơ của H thỏa mãn (1.2). Định lý 1.1.14 cho phép thiết lập tương ứng một - một giữa các phiếm hàm tuyến tính liên tục f trên H và các véctơ a ∈ H. tương ứng đó là phép đẳng cự tuyến tính, cho nên nếu ta đồng nhất phiếm hàm f với véctơ a sinh ra nó thì không gian Hilbert H có thể đồng nhất được với không gian liên hợp H∗ của nó. Cho A là toán tử tuyến tính liên tục trên không gian Hilbert H, với mỗi y ∈ H cố định ta xét phiếm hàm x∗ : H → R xác định như sau: x∗(x) = hAx, yi, ∀x ∈ H. Dễ thấy x∗ là phiếm hàm tuyến tính, liên tục trên H nên theo Định lý 1.1.14 về dạng tổng quát của phiếm hàm tuyến tính liên tục, tồn tại duy nhất y ∗ ∈ H để: hAx, yi = hx, y ∗ i, ∀x ∈ H. Định nghĩa 1.1.15 Cho A là toán tử trong không gian Hilbert H, ánh xạ A∗ : H → H được xác định như sau: A∗ y = y ∗ , ∀y ∈ H trong đó hAx, yi = hx, y ∗ i = hx, A∗ yi. Được gọi là toán tử liên hợp của toán tử A. Nhận xét 1.1.16 Toán tử liên hợp A∗ nếu tồn tại là duy nhất. Định nghĩa 1.1.17 Dãy (xn )n ∈ H được gọi là: 8 i. Hội tụ mạnh đến x0 ∈ H nếu nó hội tụ theo chuẩn, tức là: lim kxn − x0 k = 0, n→∞ kí hiệu xn → x0 hay lim xn = x0 ; n→∞ ii. Hội tụ yếu đến x ∈ H nếu ∀y ∈ H ta có: lim hxn , yi = hx, yi, n→∞ kí hiệu xn ⇀ x khi n → ∞. Định nghĩa 1.1.18 Hàm f xác định trên tập lồi C ⊂ Rn được gọi là lồi mạnh, nếu với ∀x, y ∈ C, ∀λ ∈ [0, 1], tồn tại hệ số t > 0, t ∈ R, ta có: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − λ(1 − λ)tkx − yk2 . Định nghĩa 1.1.19 Cho hàm f : S → (−∞, +∞), S ⊂ Rn, các tập: domf = {x ∈ S : f (x) < +∞} gọi là miền hữu hiệu của hàm f ; epif = {(x, α) ∈ S × R : f (x) ≤ α} gọi là tập trên đồ thị của hàm f. Hàm f là lồi khi và chỉ khi epif là tập lồi. Định nghĩa 1.1.20 Hàm f được gọi là chính thường (proper), nếu domf 6= ∅ và f (x) > −∞, ∀x ∈ S. Cho C ⊂ Rn là tập lồi, C 6= ∅. Ta có một số ví dụ về hàm lồi như sau: p i. Hàm chuẩn Euclid : kxk = hx, xi, x ∈ Rn ; ii. Hàm khoảng cách từ điểm x ∈ Rn tới C : dC (x) = inf kx − yk. y∈C Định nghĩa 1.1.21 Cho H là không gian Hilbert, X là tập con khác rỗng của H. Khi đó X được gọi là tập compact nếu mọi dãy {xn } ⊂ H đều chứa dãy con hội tụ đến một điểm x0 ∈ X nào đó. 1.2 Toán tử đơn điệu cực đại Cho hai tập hợp X, Y ta có một số định nghĩa sau. 9 Định nghĩa 1.2.1 Cho X, Y là hai tập con bất kì của không gian Hilbert H, ánh xạ F từ không gian X vào không gian Y là đơn trị nếu ứng với mỗi phần tử x ∈ X, xác định duy nhất một phần tử F (x) = y ∈ Y và ta kí hiệu là: F : X → Y. Ánh xạ F là đa trị từ không gian X vào không gian Y nếu ứng với mỗi phần tử x ∈ X, thì F (x) là một tập con của không gian Y (có thể là tập rỗng) và ta kí hiệu là: F : X → 2Y . Nhận xét 1.2.2 Ánh xạ đơn trị là một trường hợp riêng của ánh xạ đa trị. Định nghĩa 1.2.3 i. Nếu F là ánh xạ đơn trị thì ánh xạ ngược F −1 : Y → X được định nghĩa như sau: F −1 (y) = {x ∈ X : F (x) = y}, ii. Nếu F là ánh xạ đa trị thì ánh xạ ngược F −1 : 2Y → X được định nghĩa như sau: F −1(y) = {x ∈ X : y ∈ F (x)}, iii. Cho hai ánh xạ T : X → Y và R : Y → Z, hợp của chúng là RT hoặc R ◦ T là RT = {(x, z) | ∃y ∈ Y : (x, y) ∈ T, (y, z) ∈ R}, vì vậy (RT )x = [ Ry. y∈T x Ví dụ 1.2.4 Xét phương trình đa thức: an + an−1 x + · · · + a1 xn−1 + xn = 0, ai ∈ R. 10 Quy tắc cho tương ứng mỗi điểm a ∈ Rn với tập nghiệm của phương trình trên, ký hiệu là F (a) cho ta một ánh xạ đa trị F : Rn → 2C. Định nghĩa 1.2.5 Nếu Y là không gian véctơ thực, ta có một số các khái niệm sau: cA = {(x, cy) | (x, y) ∈ A}, ∀c ∈ R, A : X → Y A + B = {(x, y + z) | (x, y) ∈ A, (x, z) ∈ B}, ∀A, B : X → Y. Định nghĩa 1.2.6 Một không điểm của A là x ∈ X bất kì sao cho 0 ∈ Ax. Tập tất cả các không điểm của A, được kí hiệu là zer(A). Định nghĩa 1.2.7 Toán tử A : H → H được gọi là đơn điệu nếu: hA(x) − A(y), x − yi > 0, ∀x, y ∈ H. Định nghĩa 1.2.8 Cho toán tử đa trị A : H → 2H . Khi đó: dom A = {x ∈ H|Ax 6= ∅} là miền xác định của A, gra A = {(x, u) ∈ H × H|u ∈ Ax} là đồ thị của A. Toán tử A là đơn điệu nếu: hx − y, u − vi > 0, ∀(x, u), (y, v) ∈ gra A. Ví dụ 1.2.9 Cho toán tử đơn trị A xác định trên tập số thực R như sau: A(x) = x, ∀x ∈ R. Khi đó, A là toán tử đơn điệu vì với ∀x, y ∈ R ta có: hA(x) − A(y), x − yi = hx − y, x − yi = (x − y)2 > 0. Định nghĩa 1.2.10 Toán tử đa trị A : H → 2H được gọi là toán tử đơn điệu cực đại nếu toán tử A là đơn điệu và đồ thị gra A của A không chứa trong đồ thị của toán tử đơn điệu khác trong H. 11 Ví dụ 1.2.11 Xét toán tử Ti : R → 2R, i = 1, 2 cho bởi công thức: ( 1 nếu x ≥ 0 T1 (x) = ∅ nếu x < 0 và T2(x) = 1, ∀x ∈ R. Dễ thấy T1, T2 đều là các toán tử đơn điệu. Nhưng T1 không phải là toán tử đơn điệu cực đại vì gra T1 chứa thực sự trong gra T2 . Mệnh đề 1.2.12 Cho toán tử đơn điệu A : H → 2H . Khi đó, A là toán tử đơn điệu cực đại khi và chỉ khi ∀(a, b) ∈ H × H, nếu: hb − u, a − xi > 0, ∀(x, u) ∈ gra A thì b ∈ A(a). Chứng minh. Giả sử A là toán tử đơn điệu cực đại mà b ∈ / A(a). Ta mở rộng toán tử A thành toán tử A bằng cách: A(a) = A(a) ∪ {b}. Suy ra gra A gra A mâu thuẫn với giả thiết. ′ Ngược lại, giả sử b ∈ A(a). Xét toán tử đơn điệu bất kì A có: ′ gra A ⊆ gra A . ′ Nếu (a, b) ∈ gra A thì: hb − u, a − xi > 0, ∀(x, u) ∈ gra A, ′ suy ra b ∈ A(a) ⇒ (a, b) ∈ gra A. Nghĩa là gra A ⊆ gra A. Nghĩa là A là toán tử đơn điệu cực đại. Mệnh đề được chứng minh.  12 Nếu A, B là đơn điệu thì A + B là đơn điệu. Tuy nhiên nếu A, B là đơn điệu cực đại thì A + B không phải lúc nào cũng đơn điệu cực đại. Điều kiện để A + B là đơn điệu cực đại là ri(dom A) ∩ ri(dom B) 6= ∅. Bổ đề 1.2.13 Cho toán tử đơn điệu A trên H, A là đơn điệu cực đại khi và chỉ khi im(I + A)= H. Bổ đề 1.2.14 Cho số thực r > 0, A là toán tử trên H. Khi đó zer(A) = zer(rA), và A là đơn điệu (cực đại) khi và chỉ khi rA là đơn điệu (cực đại). Sau đây là mối tương ứng giữa họ các toán tử đơn điệu cực đại và một lớp toán tử không giãn chặt có miền xác định trên H. Định nghĩa 1.2.15 Toán tử K trên H được gọi là không giãn nếu kx′ − xk >k y ′ − y k ∀(x, y), (x′ , y ′ ) ∈ K. Bổ đề 1.2.16 Mọi toán tử không giãn là đơn trị. Chứng minh. Cho (x, y1 ), (x, y2 ) ∈ K, 0 =k x − x k>k y1 − y2 k, suy ra y1 = y2 .  Định nghĩa 1.2.17 K là không giãn chặt nếu hx′ − x, y ′ − yi > k y ′ − y k 2 ∀(x, y), (x′ , y ′ ) ∈ K. Bổ đề 1.2.18 Mọi toán tử không giãn chặt là đơn điệu và không giãn. Vì vậy chúng là đơn trị. Chứng minh. Cho K là toán tử không giãn chặt. Vì hx′ − x, y ′ − yi > k y ′ − y k nên K là đơn điệu. 2 ∀(x, y), (x′ , y ′ ) ∈ K, 13 Một khái niệm tương đương về toán tử không giãn chặt được đưa ra như sau: 2 2 2 k y ′ − y k 6 k x′ − x k − k (x′ − y ′ ) − (x − y) k ∀(x, y), (x′ , y ′ ) ∈ K. Mối quan hệ tương đương này có thể kiểm tra bằng cách tính toán trực tiếp. Từ dạng này có thể suy ra K là không giãn, và theo Bổ đề 1.2.16 thì K là đơn trị.  Định nghĩa 1.2.19 Bài toán điểm bất động trên K là tìm phần tử x∗ ∈ H sao cho Kx∗ = x∗. Một lược đồ tự nhiên là phép lặp xk+1 = ⋄Kxk , xuất phát từ điểm x0 nào đó thuộc H. Nếu w là điểm bất động bất kì của K, thì từ Bổ đề 1.2.18 ta có 2 2 2 k xk+1 − w k 6 k xk − w k − k xk+1 − xk k ∀k > 0. Suy ra khoảng cách giữa xk và những điểm bất động là không tăng, và k xk+1 − xk k −→ 0. Vì vậy, nếu tồn tại điểm bất động thì dãy xk phải là giới nội. Từ đó, phụ thuộc vào các điều kiện của bài toán đặt ra người ta có thể sử dụng kết luận trên để suy ra tính hội tụ của dãy xk đến điểm bất động của K, thông thường trong tôpô yếu. Trong không gian hữu hạn chiều, sự hội tụ được đảm bảo. Định nghĩa 1.2.20 Cho toán tử đơn điệu cực đại T và số thực r > 0, ta định nghĩa toán tử giải Jr,T của T là (I + rT )−1 . Mệnh đề 1.2.21 Toán tử T trên H là đơn điệu khi và chỉ khi J1,T = (I + T )−1 là không giãn chặt. T là đơn điệu cực đại khi và chỉ khi (I + T )−1 là không giãn chặt và có miền xác định đầy đủ. Chứng minh. Ta có (x, y) ∈ T ⇔ (x + y, x) ∈ (I + T )−1 2 hx′ − x, y ′ − yi > 0 ⇔ hx′ − x + y ′ − y, x′ − xi > k x′ − x k . 14 Suy ra kết luận thứ nhất. Mặt khác, theo Bổ đề 1.2.13, T là cực đại khi và chỉ khi im(I + T ) = H. Điều này đúng khi và chỉ khi toán tử (I + T )−1 có miền xác định đầy đủ. Điều này xác minh cho kết luận thứ 2.  Hệ quả 1.2.22 Toán tử K là không giãn chặt khi và chỉ khi K −1 − I là đơn điệu. K là không giãn chặt với miền xác định đầy đủ khi và chỉ khi K −1 − I là đơn điệu cực đại. Hệ quả 1.2.23 Hàm số từ T 7−→ (I + T )−1 là song ánh giữa họ M (H) các toán tử đơn điệu cực đại trên H và họ F (H) các toán tử không giãn chặt trên H. Hệ quả 1.2.24 Cho T là toán tử đơn điệu cực đại bất kì và số thực r > 0, toán tử giải Jr,T = (I + rT )−1 là không giãn chặt (do đó là đơn trị) và có miền xác định đầy đủ. Chứng minh. Theo Bổ đề 1.2.14, rT là đơn điệu cực đại do đó (I + rT )−1 là không giãn chặt và có miền xác định đầy đủ.  Bổ đề 1.2.25 Cho toán tử đơn điệu cực đại T , số thực r > 0, và x ∈ H, 0 ∈ T x khi và chỉ khi Jr,T (x) = {x}. Chứng minh. Bằng cách tính trực tiếp, Jr,T = {(x + ry, x) | (x, y) ∈ T }. Vì vậy 0 ∈ T x ⇔ (x, 0) ∈ T ⇔ (x, x) ∈ Jr,T vì Jr,T là đơn trị nên phần chứng minh được kết thúc.  Quan sát này đưa ta đến việc xây dựng xấp xỉ không điểm của toán tử T [7]. Xuất phát ∀r > 0 và x0 ∈ H ta tính xk+1 = Jr,T (xk ) = (I + rT )−1 xk . Rockafellar [10] đã chứng minh và phân tích thuật toán này (gọi là thuật toán điểm gần kề): lấy dãy {rk } các số thực dương, bị chặn dưới bởi 0, x0 ∈ H tùy ý, ta thực hiện phép lặp 15 xk+1 = Jrk ,T (xk ) = (I + rk T )−1 xk . Mệnh đề 1.2.26 Cho T là toán tử đơn điệu cực đại. Nếu zer(T ) 6= ∅, thì dãy {xk } sinh ra bởi thuật toán điểm gần kề là giới nội và hội tụ yếu đến không điểm của T . Nếu zer(T ) = ∅ thì {xk } không giới nội. Điều quan trọng cần lưu ý rằng thuật toán bất kì tạo bởi dãy lặp xk+1 = Kxk , ở đây K là toán tử không giãn chặt với miền xác định đầy đủ, có thể xem xét như là một phần ứng dụng của thuật toán điểm gần kề với toán tử đơn điệu cực đại K −1 − I, và {rk } cố định bằng 1. Bài toán cơ bản ta xét trong chương sau là tìm không điểm của toán tử đơn điệu A + B, ở đây A và B là toán tử đơn điệu cực đại. 16 Chương 2 Thuật toán tách Lions–Mercier và phương pháp luân hướng tìm không điểm của tổng hai toán tử đơn điệu cực đại Chương này trình bày thuật toán tách Lions–Mercier và phương pháp luân hướng tìm không điểm của tổng hai toán tử đơn điệu cực đại. Mục 2.1 mô tả phương pháp tách và cách triển khai phương pháp này. Mục 2.2 giới thiệu phương pháp ngược từng phần và mối liên hệ với phương pháp tách Lions–Mercier. Mục 2.3 trình bày về phương pháp luân hướng và nêu mối liên hệ với phương pháp tách. Các kiến thức của chương được tổng hợp từ các tài liệu [2]–[13]. 2.1 2.1.1 Phương pháp tách Mô tả phương pháp Xét bài toán tìm không điểm của tổng hai toán tử đơn điệu cực đại A và B trong không gian Hilbert H. Trong trường hợp đặc biệt A + B là toán tử đơn điệu cực đại, người ta cũng có thể sử dụng thuật toán điểm gần kề cho A + B. Tuy nhiên điểm cần lưu ý trong trường hợp này là Jr,A+B khó tính toán, cho nên cách tiếp cận này là không thực tế. Thay vào đó ta dùng cách tiếp cận tách ra Jλ,A và Jλ,B , trong đó λ > 0 là một số thực