Một số khái niệm
Cho H là không gian Hilbert thực, E là không gian Banach và E ∗ là đối ngẫu của E.
1 Tập lồi: Tập C ⊂ H (hoặc E) được gọi là lồi nếu C chứa mọi đoạn thẳng nối hai điểm bất kỳ của nó Tức là C lồi khi và chỉ khi
2 Toán tử đơn điệu: Ánh xạ T : E → E ∗ được gọi là đơn điệu nếu
(Tx − Ty, x − y) ≥ 0 ∀x, y ∈ E, trong đó ký hiệu (f, x) chỉ tích đối ngẫu Trường hợp E = E ∗ = H ta có tích vô hướng trong H.
Bổ đề 1.1.1 Giả sử S là tập các không điểm của T , tức là
Nếu T là toán tử đơn điệu và S ƒ= ∅ thì S là tập lồi.
Chứng minh Với mọi x 1 , x 2 ∈ S và t ∈ (0, 1) đặt x = tx 1 + (1 − t)x 2 Vì
T là toán tử đơn điệu nên ta có
Từ điều này suy ra (Tx, x 1 − x 2) = 0 Vậy Tx = θ nghĩa là x ∈ S □
3 Toán tử ngược-đơn điệu mạnh: T được gọi là đồng bức với hằng số c > 0 hay c-ngược đơn điệu mạnh trên H nếu
Toán tử T được coi là đơn điệu cực đại khi nó vừa đơn điệu vừa có đồ thị không phải là tập con thực sự của đồ thị của một toán tử đơn điệu khác.
Toán tử J : E → E ∗ xác định bởi
Ánh xạ đối ngẫu chuẩn tắc J(x) được định nghĩa bởi J(x) = {f ∈ E∗ | (f, x) = ǁxǁ 2 = ǁf ǁ 2 ∗} Hàm số φ : E × E → R được xác định bởi φ(y, x) = ǁyǁ 2 − 2(y, Jx) + ǁxǁ 2 cho mọi x, y ∈ E, với J là ánh xạ đối ngẫu chuẩn tắc từ không gian E vào không gian đối ngẫu của nó.
E ∗ Đại lượng φ(x, y) gọi là khoảng cách suy rộng trên E.
Ánh xạ không giãn và ánh xạ không giãn tương đối là hai khái niệm quan trọng trong toán học Cho C là một tập con lồi đóng của E và T là ánh xạ từ C vào chính nó, tập hợp các điểm bất động của T được ký hiệu là F(T) Một điểm p trong C được gọi là điểm bất động tiệm cận của T nếu tồn tại một dãy x_n hội tụ yếu tới p sao cho giới hạn lim (x_n Tx_n) = 0 T được coi là không giãn nếu ǁTx - Tyǁ ≤ ǁx - yǁ với mọi x, y ∈ C Hơn nữa, T là ánh xạ không giãn tương đối khi F(T) = F(T) và φ(p, Tx) ≤ φ(p, x) với mọi x ∈ C và p ∈ F(T).
Nếu T là toán tử không giãn trên không gian Hilbert, thì A = I − T sẽ là một toán tử đơn điệu, với I là toán tử đồng nhất Đối với mọi x, y thuộc H, ta có ǁTx − Tyǁ ≤ ǁx − yǁ.
Chương 1 Kiến thức 9 chuẩn bị
0 ≤ ǁAx − Ayǁ = ǁx − yǁ − 2(x − y, Tx − Ty) + ǁTx − Tyǁ
6 Không gian Banach lồi đều: Không gian Banach E được gọi là lồi đều nếu với mọi ε > 0 tồn tại δ(ε) > 0 sao cho với mọi x, y ∈ E, ǁxǁ ≤
1, ǁyǁ ≤ 1 và ǁx − yǁ ≥ ε ta luôn có ǁx + yǁ < 2(1 − δ(ε)).
Chú ý 1 Có thể thay đổi như sau: với mọi x, y ∈ E, d > 0 tồn tại δ( ε ), ǁxǁ ≤ d, ǁyǁ ≤ d, ǁx − yǁ ≥ ε ta có ǁx + yǁ ≤ 2d(1 − δ( ε )).
Mọi không gian Hilbert đều là không gian lồi đều Cụ thể, nếu ε > 0 và ǁxǁ ≤ 1, ǁyǁ ≤ 1 với điều kiện ǁx − yǁ ≥ ε, thì từ bất đẳng thức hình bình hành có thể suy ra các tính chất quan trọng của không gian này.
Do đó ǁx + yǁ 2 = 2 ǁxǁ 2 + ǁyǁ 2 Σ
Chú ý 3 Mọi không gian Banach lồi đều là không gian phản xạ, tức là E ∗∗
7 Không gian Banach lồi chặt: Không gian Banach E được gọi là lồi chặt nếu với mọi x, y ∈ E, x ƒ= y, ǁxǁ ≤ 1, ǁyǁ ≤ 1 ta có ǁx + yǁ < 2.
Không gian Banach được phân loại thành hai loại: trơn và trơn đều Đặt U = {x ∈ E | ǁxǁ = 1} là hình cầu đơn vị của E Không gian Banach E được gọi là trơn nếu giới hạn lim ǁ x + ty ǁ − ǁ x ǁ t→0 t tồn tại với mỗi x, y ∈ U Nếu giới hạn này tồn tại cho mọi x, y ∈ U, thì E được gọi là trơn đều Đặc biệt, nếu E là trơn đều, thì J liên tục chuẩn-chuẩn đều trên mỗi tập con bị chặn của E.
9 Tính chất Kadec-Klee: Không gian Banach E có tính chất Kadec-Klee nếu x n ⇀ x và ǁx n ǁ → ǁxǁ thì x n → x khi n → ∞.
Bổ đề 1.1.2 Mọi không gian Banach lồi đều đều có tính chất Kadec-
Chứng minh Giả sử x n ⇀ x và ǁx n ǁ → ǁxǁ khi n → ∞.
Nếu x = θ thì ǁx n ǁ → 0 suy ra x n → θ.
Nếu x ƒ= θ, không giảm tổng quát coi ǁxǁ = 1 và với mọi n, x n ƒ= θ. Đặt x n y n ǁx n ǁ ta có ǁy n ǁ = 1 và với mọi f ∈ E ∗ ta có f (y n f ( x n ) f ( x )
) = → = f (x) ǁx n ǁ 1 suy ra y n ⇀ x Do E lồi đều nên tồn tại δ > 0 sao cho với mọi ξ > 0, δ(ξ)
Mặt khác, với mọi f ∈ E ∗ và ǁf ǁ = 1 ta có ǁy n + xǁ ≥ f (y n + x) = f (y n ) + f (x).
Do đó lim2(1 − δ(ǁy n − xǁ)) ≥ 2f (x).
Theo định lý Hahn-Banach: tồn tại f ∈ E ∗ , ǁf ǁ = 1, f (x) = ǁxǁ sao cho lim2(1 − δ(ǁy n − xǁ)) ≥ 2ǁxǁ = 2 suy ra y n → x khi n → ∞ và x n = ǁx n ǁy n → ǁxǁx = x Vậy x n → x □
Phép chiếu trong không gian Hilbert
Định nghĩa 1.2.1 Cho A là một tập khác rỗng (không nhất thiết lồi) của H và điểm x ∈ H Đặt d A (x) = inf y x y∈A
Ta nói d A (x) là khoảng cách từ x đến A Nếu tồn tại π ∈ A sao cho d A (x) ǁπ − xǁ thì ta nói π là hình chiếu vuông góc của x lên A Ký hiệu là π P A (x).
Sau đây là một số tính chất quan trọng của phép chiếu trực giao mà chúng ta sẽ sử dụng trong Chương 2, 3 và 4. ǁ − ǁ
Bổ đề 1.2.1 Cho A là một tập lồi, đóng, khác rỗng của H Khi đó với mọi x, y ∈ H và z ∈ A, các tính chất sau đúng:
Bổ đề 1.2.2 Cho A là một tập con lồi, đóng, khác rỗng của H Khi đó với mọi x ∈ H hình chiếu P A (x) của x trên A luôn tồn tại và duy nhất.
Chứng minh Do d A (x) = inf y x nên theo định nghĩa của cận dưới đúng, y∈A tồn tại dãy {y k } ∈ A sao cho lim ǁy k − xǁ = d A (x) < +∞.
Vậy dãy {y k } bị chặn, do đó nó có một dãy con {y k j } hội tụ đến một điểm π nào đó Do A đóng nên π ∈ A Vậy ǁπ − xǁ = lim ǁy k j − zǁ = lim ǁy k − xǁ = d A (x). j k
Chứng tỏ π là hình chiếu của x trên A.
Bây giờ ta chỉ ra tính duy nhất của hình chiếu Thật vậy, nếu tồn tại hai điểm π và π 1 đều là hai hình chiếu của y trên A thì
Cộng hai bất đẳng thức này ta suy ra ǁπ − π 1ǁ ≤ 0 và do đó π = π 1.
□ Cho siêu phẳng H = {z ∈ H | (a, z) = b} của H Khi đó hình chiếu của điểm x ∈ H bất kỳ lên H là
Phương pháp chiếu-điểm gần kề
Chương này trình bày một cải tiến của phương pháp điểm gần kề cổ điển trong việc giải bài toán tìm không điểm của toán tử đơn điệu cực đại trong không gian Hilbert vô hạn chiều Thuật toán mới được phát triển bằng cách kết hợp phương pháp điểm gần kề và phương pháp chiếu, giữ lại những ưu điểm của phương pháp điểm gần kề mà không tốn nhiều chi phí tính toán trong bước chiếu Đặc biệt, nhờ vào tính chất của toán tử đơn điệu cực đại và phép chiếu, thuật toán này đảm bảo hội tụ mạnh mẽ đến một nghiệm của bài toán.
Giới thiệu
Trong bài toán tìm x ∈ H sao cho 0 ∈ T(x), với H là không gian Hilbert và T(x) là một toán tử đơn điệu cực đại, chúng ta ký hiệu tập nghiệm của bài toán này.
Phương pháp điểm gần kề là một kỹ thuật trong giải bài toán, trong đó giả sử rằng đã có một xấp xỉ x k ∈ H gần với nghiệm của bài toán (2.1) Điểm lặp tiếp theo được xác định thông qua việc giải một bài toán phụ gần kề.
0 ∈ T (x) + à k (x − x k ), (2.2) trong đú à k > 0 là tham số hiệu chỉnh.
Nếu tham số hiệu chỉnh {à k } bị chặn, thì dãy lặp {x k } của phương pháp điểm gần kề sẽ hội tụ yếu tới một nghiệm của bài toán (2.1), giả sử bài toán này có nghiệm O Güler đã đưa ra một ví dụ về một hàm f -lồi thực sự trong không gian Hilbert vô hạn chiều l 2, cho thấy rằng thuật toán điểm gần kề cho T = ∂f hội tụ yếu nhưng không hội tụ mạnh.
2 Việc giải chính xác bài toán phụ gần kề (2.2) nói chung khó thực hiện.
Trong thực tế, bài toán (2.2) chỉ cần được giải gần đúng bằng cách tìm một cặp y k ∈ H và v k ∈ T (y k) sao cho sai số ε k = v k + à k (y k − x k).
Trong phương pháp điểm gần kề gần đúng thuần túy, điểm lặp tiếp theo được xác định từ công thức x k+1 := y k
Các điều kiện đảm bảo các phép lặp (2.3) hội tụ là
Điều kiện đầu tiên đảm bảo sự hội tụ toàn cục, trong khi điều kiện thứ hai, cùng với một giả thiết nào đó, sẽ dẫn đến tốc độ hội tụ tuyến tính địa phương Cần lưu ý rằng dãy khả tổng {σ k} thường được chọn trước Trong điều kiện thứ hai, sai số cho phép σ k phải thỏa mãn ε k Σ.
Khi σ k tiến gần đến 0, các điều kiện về sai số ε k trở nên quá nghiêm ngặt Nếu {σ k} là một dãy hằng không bằng 0, sự hội tụ của dãy lặp gần kề sẽ không được đảm bảo, ngay cả trong trường hợp có số chiều hữu hạn.
Để giải quyết các vấn đề liên quan đến việc đánh giá sai số của thuật toán điểm gần kề gần đúng thuần túy, cần thiết phải cải tiến phương pháp này theo hướng k Σ.
Chương 2 Phương pháp chiếu-điểm 4 gần kề k k k Σ ǁ ǁ ∞ k k=
0 à ǁy k − x k ǁ k k hướng cố định sai số cho phép σ Nói cách khác là chúng ta chấp nhận y k
∈ H và v k ∈ T (y k ) là một nghiệm của (2.3) nếu một trong hai điều kiện sau đúng: k k ǁε ǁ
≤ σ hoặc ǁε ǁ à k ǁy k − x k ǁ ǁv k ǁ≤ σ, trong đó σ ∈ [0, 1) Dưới điều kiện này, siêu phẳng
H k := {x ∈ H | (v k , x − y k ) = 0} tách chặt điểm lặp x k khỏi tập nghiệm S (giả thiết S khác rỗng) Chúng ta thu được một thuật toán lai ghép chiếu-điểm gần kề sau đây:
Thuật toán 2.1.1 ([10]) Chọn giá trị ban đầu tùy ý x 0 ∈ H và σ ∈ [0, 1).
Giả sử đó cú x k , chọn à k > 0 và tỡm y k ∈ H sao cho ε k = v k + à k (y k − x k ), v k ∈ T (y k ), trong đú ǁε ǁ ≤ σ max{ǁv ǁ, à k ǁy − x ǁ}.
Dừng nếu v k = 0 hoặc y k = x k Nếu không, xây dựng siêu phẳng
Trong phương án cải tiến này, chúng ta giữ lại các ưu điểm của phương pháp điểm gần kề, đồng thời cố định sai số cho phép σ Phép chiếu x k lên siêu phẳng H k được thể hiện bằng công thức tường minh, giúp giảm thiểu chi phí tính toán Tuy nhiên, phương pháp lai ghép này chỉ tạo ra dãy {x k } hội tụ yếu đến nghiệm của bài toán (2.1) Định nghĩa 2.1.1 nêu rõ rằng cặp (y, v) ∈ H × H được xem là nghiệm gần đúng với sai số cho phép σ của 0 ∈ T (ã) + à(ã − x) nếu thỏa mãn các điều kiện v ∈ T (y), v + à(y − x) = ε, và ǁεǁ ≤ σ max{ǁvǁ, àǁy − xǁ}.
Mệnh đề 2.1.1 Cho x ∈ H, à > 0, σ ∈ [0, 1) và giả sử rằng (y, v) là một nghiệm gần đỳng của 0 ∈ T (ã) + à(ã − x) với sai số cho phộp σ Khi đó
(x − y, v) ≥ (1 − σ) max{àǁx − yǁ 2 , ǁvǁ 2 /à} ≥ (1 − σ)ǁvǁǁx − yǁ.
Bốn khẳng định sau là tương đương x ∈
= x; v 0; x là một nghiệm của bài toán (2.1).
Hơn nữa, ǁP H (x) − xǁ ≥ (1 − σ) max{ǁx − yǁ, ǁvǁ/à} (2.5)
Chứng minh Để chứng minh (2.4) ta xét hai trường hợp àǁx − yǁ ≤ ǁvǁ và àǁx − yǁ ≥ ǁvǁ.
Trong trường hợp thứ nhất, kết hợp với Định nghĩa 2.1.1 ta có ǁεǁ ≤ σǁvǁ và (x − y, v) à (v − ε, v).
Như vậy ta chứng minh được (2.4) đúng trong trường hợp thứ nhất.
Xét trường hợp thứ hai Tương tự, ta có ǁεǁ ≤ σàǁy − xǁ.
≥ à(1 − σ)ǁx − yǁ Hơn nữa, trong trường hợp này ta có
Vậy (2.4) đúng trong cả hai trường hợp.
Chúng ta sẽ chỉ ra sự tương đương của bốn khẳng định Giả sử x ∈ H, ta có (x−y, v) ≤ 0, từ đó suy ra x = y Nếu x = y thì (x−y, v) = 0, dẫn đến v = 0 theo (2.4) Tương tự, nếu v = 0 thì x = y và x là nghiệm của bài toán (2.1) Cuối cùng, nếu x là nghiệm của bài toán (2.1), tức là 0 ∈ T(x), thì từ tính đơn điệu của T có thể được khẳng định.
Cuối cùng, để chứng minh (2.5) chú ý rằng nếu x ∈ H thì x = y, v = 0 và (2.5) đúng Ta xét trường hợp x ∈/ H Ta có
Nếu ǁvǁ/à ≥ ǁx − yǁ, thì ǁvǁ²/à ≥ àǁx − yǁ², và (2.5) được suy ra từ bất đẳng thức đầu tiên của (2.4) Ngược lại, nếu ǁvǁ/à ≤ ǁx − yǁ, thì (2.5) được suy ra từ bất đẳng thức thứ hai của (2.4).
Chứng minh được hoàn thành □
Sự hội tụ mạnh của phương pháp chiếu-điểm gần kề
Thuật toán chiếu-điểm gần kề
Thuật toán 2.2.1 ([11]) Cho x 0 ∈ H là xấp xỉ ban đầu bất kỳ và σ
∈ [0, 1) Giả sử tại bước lặp thứ k chúng ta đã có x k
Chương 2 Phương pháp chiếu-điểm 10 gần kề
Bước 1: Chọn à k > 0, tỡm (y k , v k ) là một nghiệm gần đỳng của bài toán
0 ∈ T (x) + à k (x − x k ) với sai số cho phép σ.
Bước 2 (Bước chiếu): Xác định
Nhận xét 1 Trong mỗi bước lặp chúng ta cần giải hai bài toán:
Bài toán phụ điểm gần kề luôn có một nghiệm chính xác và duy nhất, do đó việc tìm nghiệm gần đúng trở nên đơn giản hơn so với việc tìm nghiệm chính xác Ở bước 1 của Thuật toán 2.2.1, nghiệm gần đúng được xác định rõ ràng, tuy nhiên, cặp nghiệm (y k , v k ) tại bước này không phải là duy nhất, dẫn đến dãy lặp {x k } cũng không có tính duy nhất.
Bài toán 2: Tìm hình chiếu của x 0 lên giao của hai nửa không gian H k ∩
Trong phần tiếp theo của chương này, chúng ta sẽ chứng minh được tập H k
∩W k luôn luôn khác rỗng ngay cả khi bài toán (2.1) vô nghiệm Vì vậy,
Bước chiếu của Thuật toán 2.2.1 được xác định và do đó nó xác định theo nghĩa sinh ra một dãy vô hạn {x k }.
2 Việc tìm hình chiếu của x 0 lên H k ∩ W k tương đương với việc giải một hệ gồm hai phương trình tuyến tính hai ẩn số (kể cả trong không gian vô hạn chiều) Thật vậy, giả sử tại lần lặp thứ k có H k ∩ W k khác rỗng Khi đó x k+1 là nghiệm của min z ǁz − x 0 ǁ 2 sao cho (z − y k , v k ) ≤ 0,
Chương 2 Phương pháp chiếu-điểm 9 gần kề k k k
Biểu diễn z − x 0 như là tổ hợp tuyến tính của v k và x 0 − x k cộng với một vectơ trực giao với v k và x 0 − x k : z − x 0 = λ 1 v k + λ 2(x 0 − x k ) + h, trong đó (h, v k ) = 0, (h, x 0 − x k ) 0.
Bài toán trên trở thành min λ ,λ ,h ǁhǁ 2 + ǁλ 1 v k + λ 2(x 0 − x k )ǁ 2 sao cho (λ 1 v k + λ 2(x 0 − x k ) + x 0 − y k , v k ) ≤ 0,
Tại nghiệm của bài toán, h = 0, dẫn đến việc tìm λ 1 và λ 2 thông qua việc giải bài toán bình phương tối thiểu hai chiều với hai ràng buộc bất đẳng thức tuyến tính.
Hơn nữa, nếu hình chiếu của x 0 lên H k nằm trong W k thì
Bởi vậy trong trường hợp này chúng ta thu được x k mà không cần thêm bất cứ tính toán nào Ngược lại, nếu P H (x 0 ) không nằm trong W k ta có
P H ∩W (x 0 ) = x 0 + λ 1 v k + λ 2(x 0 − x k ), trong đó λ 1 , λ 2 là nghiệm của hệ phương trình tuyến tính hai phương trình với hai ẩn số
Như vậy chúng ta có thể viết tường minh công thức của x k+1 , điều này có nghĩa là chi phí tính toán ở bước chiếu trong Thuật toán 2.2.1 không đáng kể.
Định lý hội tụ
Thuật toán 2.2.1 có một số tính chất quan trọng mà không cần giả định bài toán có nghiệm Các đại lượng x k, y k, v k được sinh ra từ thuật toán này, với k = 0, 1,
Mệnh đề 2.2.1 Giả sử Thuật toán 2.2.1 đúng đến k + 1 Khi đó các bất đẳng thức sau đúng ǁx k+1 − x 0 ǁ 2 ≥ ǁx k − x 0 ǁ 2 + ǁx k+1 − x k ǁ 2 , (2.6) và ǁx k+1 − x k ǁ ≥ (1 − σ) max{ǁy k − x k ǁ, ǁv k ǁ/à k } (2.7)
Chứng minh Từ định nghĩa của W k ta có
⇒ ǁx − x ǁ ≤ ǁz − x ǁ. Điều này có nghĩa x k là hình chiếu của x 0 lên W k Áp dụng Bổ đề 1.2.1 với
A = W k , x = x k+1 và y = x 0 , ta thu được ǁP W k (x k+1 ) − P W 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 nên P W k (x k+1 ) = x k+1 Hơn nữa, P W k (x 0 ) = x k Vì vậy, ǁx k+1 − x k ǁ 2 ≤ ǁx k+1 − x 0 ǁ 2 − ǁx k+1 − x k+1 + x 0 − x k ǁ 2
Vì x k+1 ∈ H k nên ǁx k+1 − x k ǁ ≥ ǁP H k (x k ) − x k ǁ ≥ (1 − σ) max{ǁy k − x k ǁ, ǁv k ǁ/à k }.
Bất đẳng thức cuối cùng được suy từ Mệnh đề 2.1.1 □ k
Hệ quả 2.2.1 Giả sử dóy tham số hiệu chỉnh {à k } bị chặn và Thuật toán
2.2.1 sinh ra dãy vô hạn {x k } Khi đó một trong hai khẳng định sau đúng
(i) Dãy {x k } bị chặn và các điểm tụ yếu của nó nằm trong S ƒ= ∅; (ii) S = và lim k→∞ ǁx k ǁ = ∞.
Chứng minh Áp dụng liên tiếp (2.6), ta được k−1 ǁx k − x 0 ǁ 2 ≥ ǁx j+1 − x j ǁ 2 j=0
(i) Giả sử {x k } bị chặn Cho k → ∞ ta có ǁx j+1 − x j ǁ 2 < ∞, j=0 và vì vậy lim x k+1 x k = 0. k→∞
Kết hợp với (2.7) và tớnh bị chặn trờn của {à k } k ta thu được k→∞limǁy k − x k ǁ = 0, (2.8) k→∞limǁv k ǁ = 0 (2.9)
Dãy {x k } trong không gian Hilbert bị chặn, dẫn đến việc tồn tại các điểm tụ yếu Gọi x¯ là một điểm tụ yếu bất kỳ của dãy {x k }, và dãy con {x k j } hội tụ yếu về x¯ Theo công thức (2.8), dãy {y k j } tương ứng cũng sẽ hội tụ về x¯, trong khi v k thuộc tập T.
(y k ) với v k hội tụ mạnh về 0 và do tính đơn điệu cực đại của T suy ra 0 ∈ T (x¯) Nghĩa là x¯ ∈ S.
Giả sử S = ∅, từ chứng minh trước đó, ta thấy rằng dãy {x k } không bị chặn Theo (2.6), dãy {ǁx k − x 0 ǁ} không giảm, dẫn đến ǁx k − x 0 ǁ → ∞ khi k → ∞ Do đó, ta kết luận rằng ǁx k ǁ cũng tiến tới vô cùng khi k tăng.
Chúng ta sẽ chứng minh sự hội tụ mạnh của dãy {x k} đến nghiệm của phương trình khi S ƒ= ∅ Tiếp theo, chúng ta sẽ phân tích tính chất của dãy {x k} trong trường hợp phương trình không có nghiệm.
Trường hợp 1 S ƒ= ∅ Cho x 0 là giá trị ban đầu bất kỳ Đặt
Chúng ta sẽ chỉ ra tập H k ∩ W k luôn chứa tập nghiệm S và vì thế nó khác rỗng Hơn nữa, chúng ta cũng sẽ chứng tỏ dãy {x k } nằm trong U (x 0 ).
Mệnh đề 2.2.2 Giả sử Thuật toán 2.2.1 thực hiện được đến bước k và x k ∈
U (x 0 ) Khi đó những khẳng định sau đây đúng:
(ii)x k+1 hoàn toàn xác định và x k+1 ∈ U (x 0 ).
Chứng minh.(i) Từ tính đơn điệu của T ta có
Từ giả thiết x k ∈ U (x 0 ) suy ra
Từ định nghĩa của W k ta có S ⊆ W k Từ đó suy ra S ⊆ H k ∩ W k
(ii) Từ (i) suy ra H k ∩ W k ƒ= ∅, do đó x k+1 hoàn toàn xác định Vì x k+1 là hình chiếu của x 0 lên H k ∩ W k nên theo Bổ đề 1.2.1 ta có
Vì S ⊆ H k ∩ W k nên bất đẳng thức trên đúng với mọi z ∈ S Từ định nghĩa của U (x 0 ) suy ra x k+1 ∈ U (x 0 ) □
Hệ quả 2.2.2 Thuật toán 2.2.1 hoàn toàn xác định và sinh ra các dãy lặp
{x k }, {y k } và {v k } sao cho x k ∈ U (x 0 ), S ⊆ H k ∩ W k với mọi k Hơn nữa, nếu dóy à k bị chặn trờn thỡ {x k } bị chặn và cỏc điểm tụ yếu của nó nằm trong S.
Chứng minh Dễ thấy x 0 ∈ U (x 0 ) Áp dụng Mệnh đề 2.2.2 và quy nạp theo k ta chứng minh được phần đầu của Hệ quả 2.2.2 Từ Hệ quả 2.2.1 suy ra dãy
Dãy {x k } bị chặn với các điểm tụ yếu nằm trong S Theo Định lý 2.2.1, nếu dãy {x k } được sinh ra từ Thuật toán 2.2.1 và dãy tham số hiệu chỉnh {à k } cũng bị chặn, thì dãy {x k } sẽ hội tụ mạnh tới x ∗ = P S (x 0 ).
Chứng minh rằng vì tập nghiệm S lồi và đóng, cùng với giả thiết khác rỗng, nên phép chiếu x₀ lên S tồn tại, dẫn đến x∗ = P_S(x₀) được xác định hoàn toàn Từ cách xác định xₖ₊₁, ta có ǁxₖ₊₁ − x₀ǁ ≤ ǁz − x₀ǁ với mọi z thuộc Hₖ ∩ Wₖ.
Vì x ∗ ∈ S ⊆ H k ∩ W k nên với mọi k ta có ǁx k − x 0 ǁ ≤ ǁx ∗ − x 0 ǁ (2.10) Theo Hệ quả 2.2.2, dãy {x k } bị chặn và có các điểm tụ yếu nằm trong
S Giả sử {x k j là một dãy con hội tụ yếu của {x k } và x¯ ràng là giới hạn yếu của nó Rõ ǁx − x ǁ = ǁx − x − (x − x )ǁ
≤ 2ǁx − x ǁ − 2(x − x , x − x ), bất đẳng thức cuối suy ra từ (2.10) Từ tính hội tụ yếu của {x k j } tới x¯ ta thu được lim sup ǁx k j − x ∗ ǁ 2 ≤ 2 ǁx ∗ − x 0 ǁ 2 − (x¯ − x 0 , x ∗ − x 0 )Σ
(2.11) Áp dụng Bổ đề 1.2.1 với A = S, x = x 0 , z = x¯ ∈ S và chú ý rằng x ∗ là hình chiếu của x 0 lên S ta có
Kết hợp bất đẳng thức cuối cùng với (2.11) ta có lim sup j→∞ ǁx k j − x ∗ ǁ 2 = 0.
Từ đó suy ra dãy {x k j } hội tụ mạnh về x ∗ và rõ ràng x¯ = x ∗ vì x¯ là một giới hạn yếu của {x k j }.
Vì x¯ là điểm tụ yếu duy nhất của dãy {x k }, nên dãy này hội tụ yếu đến x ∗ Do {x k } bị chặn, toàn bộ dãy {x k } cũng hội tụ yếu về x ∗ Hơn nữa, mọi dãy con hội tụ yếu của {x k } đều hội tụ mạnh về x ∗.
Trường hợp S = ∅ Trong trường hợp này dãy {x k } vẫn xác định với mọi k và phân kỳ. k j
0 Định lý 2.2.2 Nếu S = ∅ thì Thuật toán 2.2.1 sinh ra một dãy vô hạn {x k }.
Nếu thờm điều kiện dóy tham số hiệu chỉnh à k bị chặn thì lim k→∞ ǁx k ǁ = ∞.
Chứng minh Trước hết, chúng ta chỉ ra Thuật toán 2.2.1 xác định bằng phương pháp quy nạp.
Với k = 0: Bài toỏn 0 ∈ T (x) + à 0(x − x 0 ) luụn cú nghiệm chớnh xác và vì vậy nó có nghiệm gần đúng (y 0 , v 0 ) Chú ý rằng W 0 = H và
H 0 luôn khác rỗng (vì y 0 ∈ H 0) Bởi vậy phép chiếu x 0 lên H 0 ∩ W 0 hoàn toàn xác định, hay tồn tại x 1 = P H 0 ∩W 0 (x 0 ).
Giả sử x k , (y k , v k ) đã được xác định với k = 0, , ^k Chúng ta cần phải
Gọi z 0 ∈ ri(D(T )), trong đó D(T ) là miền xác định của T Đặt ρ = max{ǁy k − z 0 ǁ, k = 0, , ^k} và h(x) 0 nếu ǁx − z 0 ǁ ≤ ρ + 1,
+∞ trong các trường hợp còn lại.
Gọi h : H → R ∪ {+∞} là một hàm số nửa liên tục dưới và lồi thực sự, do đó
∂h đơn điệu cực đại và
T ′ = T + ∂h cũng đơn điệu cực đại Hơn nữa,
Do đó, v k ∈ T ′ (y k ) với k = 0, , k Như vậy, x k , (y k , v k ) thỏa mãn các điều kiện của Thuật toán 2.2.1 áp dụng cho bài toán
Vì T ′ có miền xác định bị chặn nên bài toán trên có nghiệm Sử dụng
2.2.2 ta suy ra ^ k+1 được xác định Vậy Thuật toán 2.2.1 hoàn toàn xác định. Theo Hệ quả 2.2.1 ta suy ra lim k→∞ ǁx k ǁ = ∞ □
{} chứng minh x cũng được xác định.
Phương pháp chiếu-điểm gần kề song song
Xét hệ phương trình toán tử
A i (x) = 0, i = 1, , N, (2.12) trong đó H là không gian Hilbert và A i : H → H là các toán tử đơn điệu cực đại.
Thuật toán 2.3.1 ([3]) Chọn giá trị ban đầu bất kỳ x 0 ∈
H, ௠σ ∈ [0, 1) Giả sử tại lần lặp thứ k, đã có x k :
Bước 1: Tìm nghiệm (đồng thời) y i ∈ H của phương trình
+ ε i = 0, i = 1, , N, (2.13) trong đú à i ∈ (0, à¯), ǁε i ǁ ≤ σ max{ǁA i (y i )ǁ, à i ǁx k − y i ǁ}.
Bước 2: Xác định (đồng thời) các hình chiếu của x k lên các nửa không gian
H i = {z ∈ H | (z − y i , A i (y i )) ≤ 0} và tìm chỉ số tối ưu j k (1 ≤ j k ≤ N ) sao cho ǁx k − P H jk (x k )ǁ = max {ǁx k − P H i (x k )ǁ}.
Nếu x k+1 = x k thì dừng quá trình lặp.
Ngược lại, ta có thì P i (x k ) = x k , do đó k ǁx k − P H i (x k )ǁ = 0. i i
Tính toán chỉ số tối ưu j k trong mỗi lần lặp không yêu cầu thêm chi phí tính toán nào, ngoại trừ việc xác định giá trị lớn nhất trong N số không âm ở Bước 2.
2 Việc giải các phương trình (2.13) cũng như xác định khoảng cách ǁx k −
P H i (x k )ǁ là hoàn toàn độc lập theo từng chỉ số i = 1, 2, , N , do đó có thể được thực hiện đồng thời trên N bộ xử lý song song của một bó máy tính.
3 Tương tự như khi giải một phương trình, trên mỗi bước lặp ta chỉ cần tính một lần hình chiếu của x 0 lên giao của hai nửa không gian.
Bổ đề 2.3.1 Nếu Thuật toán 2.3.1 kết thúc tại bước lặp hữu hạn k + 1 thì x k là một nghiệm của hệ (2.12).
Giả sử Thuật toán 2.3.1 kết thúc tại bước lặp k + 1, với x k+1 = P H jk ∩W (x 0) ≡ x k, điều này cho thấy x k thuộc H j k và ǁx k − P j ǁ = 0 Theo định nghĩa của j k, ta có ǁx k − P H i (x k )ǁ = 0 cho mọi i = 1, , N Áp dụng Mệnh đề 2.1.1 cho các phương trình A i (y i ) + à i (y i − x k ) + ε i = 0, ta nhận được ǁP H i (x k ) − x k ǁ ≥ (1 − σ) max{ǁx k − y k ǁ, ǁA i (y k )ǁ/à k }.
Vì vậy, ǁx k − y i ǁ = 0 và ǁA i (y i )ǁ = 0, dẫn đến A i (y i ) = 0 và y i ≡ x k cho mọi i = 1, , N, điều này có nghĩa là x k là một nghiệm của hệ (2.12) Trong phần tiếp theo, chúng ta giả sử rằng Thuật toán 2.3.1 tạo ra dãy lặp vô hạn {x k }.
Bổ đề 2.3.2 Giả sử tại bước lặp thứ k ta có x k ∈ U (x 0) Khi đó,
(ii) x k+1 được xác định và x k+1 ∈ U (x 0);
(iii) ǁx k+1 − x 0ǁ ≤ ǁP S (x 0) − x 0ǁ với mọi k ∈ N và do đó {x k } bị chặn. k k k k H k k k k k k k k k k k k
Chứng minh (i) Vì A i đơn điệu nên với mọi z ∈ S ta có i i i i
Theo định nghĩa của W k suy ra z ∈ W k với mọi z ∈ S hay S ⊂ W k
(ii) Giả sử S ƒ= ∅ suy ra H j k ∩ W k ƒ= ∅ Vì vậy x k+1 = P j (x 0) xác định.
Vì x k+1 là hình chiếu của x 0 lên H j k ∩ W k nên từ Bổ đề 1.2.1 suy ra
Vì S ⊂ H j k ∩ W k nên bất đẳng thức trên đúng với mọi z ∈ S và do đó ta có x k+1 ∈ U (x 0).
(iii) Từ (2.14) ta có ǁx k+1 − x 0ǁ ≤ ǁz − x 0ǁ với mọi z ∈ H j k ∩ W k
Vì S ⊂ H j k ∩ W k nên bất đẳng thức trên suy ra ǁx k+1 − x 0ǁ ≤ ǁP S (x 0) − x 0ǁ, từ đó suy ra dãy {x k } bị chặn □
Bổ đề 2.3.3 Giả sử Thuật toán 2.3.1 đúng đến k + 1 Khi đó ta có ǁx k+1 − x 0ǁ 2 ≥ ǁx k − x 0ǁ 2 + ǁx k+1 − x k ǁ 2 , (2.16) ǁx k+1 − x k ǁ ≥ (1 − σ) max {ǁy i − x k ǁ, ǁA i (y i )ǁ/à i } (2.17)
Chứng minh Tương tự như chứng minh của Mệnh đề 2.2.1 Từ định nghĩa của
W k suy ra x k = P W k (x 0) Áp dụng Bổ đề 1.2.1 ta có
Chương 2 Phương pháp chiếu-điểm 20 gần kề
Chương 2 Phương pháp chiếu-điểm 20 gần kề
Vì x k+1 ∈ W k nên P W k (x k+1) = x k+1, ta thu được ǁx k+1 − x k ǁ ≤ ǁx k+1 − x 0ǁ − ǁx k − x 0ǁ
H j k nên ǁx k − x k+1ǁ ≥ ǁx k − P H jk (x k )ǁ ≥ max ǁx k − P H i (x k )ǁ. k i=1, ,N k
Với mỗi i = 1, , N , áp dụng (2.5) ta được i i i
Vì vậy ǁx k − P H i (x k )ǁ ≥ (1 − σ) max{ǁy k − x k ǁ, ǁA i (y k )ǁ/à k }. i i i x k+1 x k (1 σ) max i=1, ,N
Bổ đề được chứng minh □ Định lý 2.3.1 Giả sử {x k } là dãy vô hạn sinh bởi Thuật toán 2.3.1 Khi đó k→∞limx k = P S (x 0) (2.18)
Chứng minh Sử dụng (2.16) liên tiếp ta thu được k−1 ǁx k+1 − x 0ǁ 2 ≥ ǁx k − x 0ǁ 2 + ǁx k+1 − x k ǁ 2 ≥ ǁx l+1 − x l ǁ 2 (2.19) l=0
Theo phần (iii) của Bổ đề 2.3.2 ta có ǁx k+1 − x 0ǁ ≤ ǁP S (x 0) − x 0ǁ với mọi k, do đó
Cho k → ∞ ta được lim sup ǁx k − x 0ǁ ≤ ǁP S (x 0) − x 0ǁ.
Chương 2 Phương pháp chiếu-điểm 0 gần kề k k ǁ − ǁ ≥
Chương 2 Phương pháp chiếu-điểm 1 gần kề ǁ − ǁ
Sử dụng (2.17) và với giả thiết à i k→∞lim
≤ à ta thu được ǁy i − x k ǁ = 0, (2.20) lim ǁA i (y i )ǁ = 0 (2.21)
Giả sử {x k m} là một dãy con hội tụ yếu của dãy bị chặn {x k} và x k m hội tụ yếu về x¯ khi m → ∞ Từ (2.20), ta suy ra rằng y i hội tụ yếu về x¯ khi m → ∞ Với tính đơn điệu của A i cho mỗi i = 1, , N và z ∈ H, ta có những kết luận quan trọng về sự hội tụ trong không gian này.
Từ tính đơn điệu cực đại của A i suy ra A i (x¯) = 0, i = 1, , N , nghĩa là x¯ ∈ S Vì ǁx k − x 0ǁ ≤ ǁP S (x 0) − x 0ǁ với mọi k nên ta có ǁx k m − P S (x 0)ǁ = ǁx k m − x 0 − (P S (x 0) − x 0)ǁ
(2.22) Áp dụng Bổ đề 1.2.1 ta được
(x 0 − P S (x 0), x¯ − P S (x 0)) = ǁx 0 − P S (x 0)ǁ − (x¯ − x 0 , P S (x 0) − x 0) ≤ 0. Kết hợp bất đẳng thức trên với (2.22) ta thu được k lim m →∞ǁx k m − P S (x 0)ǁ = 0 hay x k m → P S (x 0) khi m → ∞.
Hơn nữa, ta cũng có x¯ ≡ P S (x 0) Vì vậy nên P S (x 0) là một điểm tụ yếu của dãy {x k } Rõ ràng mọi dãy con hội tụ yếu của {x k } đều hội tụ mạnh đến
P S (x 0), do đó x k → P S (x 0) khi k → ∞. Định lý được chứng minh □ k k k→∞ k k m k m k m k m k m k m k m k m
Trong bài viết này, chúng ta sẽ khám phá mối liên hệ giữa ánh xạ không giãn và toán tử đơn điệu, cụ thể là việc tìm điểm bất động của ánh xạ không giãn tương đương với việc tìm không điểm của toán tử đơn điệu Bằng cách áp dụng phương pháp lai ghép, chúng ta sẽ chứng minh các định lý hội tụ mạnh cho ánh xạ không giãn trong không gian Banach và cải biên cho không gian Hilbert Chương này sẽ trình bày chi tiết thuật toán hội tụ mạnh cho ánh xạ không gian tương đối và các ánh xạ không giãn trong không gian.
Các bổ đề quan trọng
Cho không gian Banach E với chuẩn ǁ ã ǁ và không gian đối ngẫu E ∗ Ký hiệu (ã, ã) là tích đối ngẫu, với mọi f ∈ E ∗ và x ∈ E, ta có (x, f) = f(x) Gọi J là ánh xạ đối ngẫu chuẩn tắc từ E đến E ∗.
E đến E ∗ được định nghĩa bởi
Hàm số φ : E × E → R được định nghĩa bởi φ(y, x) = ǁyǁ 2 − 2(y, Jx) + ǁxǁ 2 với mọi x, y ∈ E Từ định nghĩa dễ dàng suy ra(ǁyǁ − ǁxǁ) 2 ≤ φ(y, x) ≤ (ǁyǁ + ǁxǁ) 2 (3.1)
Sau đây là các kết quả bổ trợ phục vụ cho việc chứng minh sự hội tụ của các thuật toán CQ.
Bổ đề 3.1.1 Cho E là không gian Banach trơn và lồi đều, {y n }, {z n } là hai dãy của E Nếu φ(y n , z n ) → 0 và nếu {y n } hoặc {z n } bị chặn thì y n − z n → 0.
Gọi C là tập con lồi, đóng và khác rỗng của không gian Banach E, nơi E là không gian lồi chặt và trơn Với mọi điểm x thuộc E, tồn tại một điểm x* trong C sao cho φ(x*, x) đạt giá trị tối thiểu so với mọi y trong C Phép chiếu tổng quát P_C: E → C được định nghĩa bởi P_C(x) = x* là ánh xạ tương ứng.
Bổ đề 3.1.2 Cho C là tập con lồi đóng khác rỗng của không gian
E và x ∈ E Khi đó x ∗ = P C (x) nếu và chỉ nếu
Bổ đề 3.1.3 Cho C là tập con lồi đóng khác rỗng của không gian
Banach phản xạ, lồi chặt và trơn E và cho x ∈ E Khi đó φ(y, P C (x)) + φ(P C (x), x) ≤ φ(y, x) với mọi y ∈ C.
Bổ đề 3.1.4 khẳng định rằng, trong không gian Banach lồi chặt và trơn E, nếu C là tập con lồi đóng của E và T là ánh xạ không giãn tương đối từ C vào chính nó, thì tập hợp F(T) sẽ có tính chất lồi và đóng.
Chứng minh Trước hết ta chứng minh F (T ) đóng Giả sử {x n } là dãy của
F (T ) sao cho x n → x^ ∈ C Vì T là ánh xạ không giãn tương đối nên với mọi n ∈ N Từ đó suy ra ^ φ(x, Tx) lim φ(x n , Tx) ≤ lim φ(x , x) = φ(x, x) = 0.
Do đó ta thu được x = Tx hay x ∈ F (T ).
Tiếp theo, ta chứng minh F (T ) lồi Với mọi x, y ∈ F (T ) và t ∈ (0,
1), đặt z = tx + (1 − t)y Ta sẽ chỉ ra Tz = z Ta có φ(z, Tz) = ǁzǁ 2 − 2(z, JTz) + ǁTzǁ 2
= ǁzǁ 2 + tφ(x, Tz) + (1 − t)φ(y, Tz) − tǁxǁ 2 − (1 − t)ǁyǁ 2
Từ đó suy ra z = Tz □
Một số thuật toán CQ trong không gian Banach
Cho E là một không gian Banach trơn đều và lồi đều, trong khi C là một tập con lồi đóng khác rỗng của E T là ánh xạ không giãn tương đối từ C vào chính nó, và giả sử rằng tập hợp các điểm bất động F(T) của T là khác rỗng.
Sử dụng phương pháp lai ghép, chúng ta có thể thu được định lý hội tụ mạnh của ánh xạ không giãn tương đối trong không gian Banach Định lý 3.2.1 nêu rằng cho dãy số thực {α k } với điều kiện 0 ≤ α k < 1 cho mọi k và lim k→∞ α k < 1, nếu {x k } là dãy được sinh ra từ thuật toán (CQ) với x 0 ∈ C, thì y được xác định bởi công thức y = J −1 (α Jx + (1 - α)JTx ).
x k+1 = P C k ∩Q k (x 0), k = 0, 1, 2, trong đó J là ánh xạ đối ngẫu trên E Khi đó {x k } hội tụ mạnh tới P F (T )
(x 0), trong đó P F (T ) là phép chiếu tổng quát từ C lên F (T ).
Chứng minh Bước 1 Các tập con C k , Q k lồi, đóng với mỗi k = 0, 1,
2, Từ định nghĩa của C k và Q k dễ thấy C k là tập đóng và Q k là tập lồi đóng Cần chứng minh C k là tập lồi Thật vậy, ta có φ(z, y k ) ≤ φ(z, x k ) tương đương với
Với mọi z 1 , z 2 ∈ C k và t ∈ (0, 1), đặt z = tz 1 + (1 − t)z 2 và xét
2(z, Jx k − Jy k ) + ǁy k ǁ 2 − ǁx k ǁ 2 = t 2(z 1 , Jx k − Jy k ) + ǁy k ǁ 2 − ǁx k ǁ 2
≤ 0, điều này suy ra z ∈ C k Vậy C k là tập lồi.
Vì J và J −1 là các ánh xạ 1 − 1 nên với mọi u ∈ F (T ) ta có φ(u, y k ) = φ(u, J −1 (α k Jx k + (1 − α k )JTx k ))
= ǁuǁ 2 − 2(u, α k Jx k + (1 − α k )JTx k ) + ǁα k Jx k + (1 − α k )JTx k ǁ 2
= α k (ǁuǁ 2 − 2(u, Jx k ) + ǁx k ǁ 2 ) + (1 − α k )(ǁuǁ 2 − 2(u, JTx k ) + ǁTx k ǁ 2 )
Rõ ràng F (T ) ⊂ C 0 ∩ Q 0 Giả sử F (T ) ⊂ C k ∩ Q k với một k ∈ N cố định Vì F (T ) ƒ= ∅ nên C k ∩ Q k ƒ= ∅ suy ra tồn tại x k+1 = P C k ∩Q k (x)
∈ C k ∩ Q k Theo Bổ đề 3.1.2 ta có
(x k+1 − u, Jx − Jx k+1) ≤ 0 với mọi u ∈ F (T ) suy ra F (T ) ⊂ Q k+1 và do đó F (T ) ⊂ C k+1 ∩ Q k+1 Theo quy nạp ta có
F (T ) ⊂ C k ∩ Q k với mọi k Vậy dãy {x k } hoàn toàn xác định.
Bước 3 Mọi dãy con hội tụ yếu {x k j } của {x k } đều hội tụ về một điểm bất động của T
Từ định nghĩa của Q k và Bổ đề 3.1.2 suy ra x k = P Q (x 0) Theo Bổ đề 3.1.3 ta có φ(x k , x 0) = φ(P Q k (x 0), x 0) ≤ φ(u, x 0) − φ(u, x k ) ≤ φ(u, x 0) ∀u ∈ F (T ) ⊂
Do đó φ(x k , x 0) bị chặn Hơn nữa, từ (3.1) suy ra {x k } bị chặn.
Vì x k+1 ∈ Q k , nên theo Bổ đề 3.1.3 (y = x k+1 , C = Q k , x k = P Q k (x 0)) ta có φ(x k , x 0) ≤ φ(x k+1 , x k ) + φ(x k , x 0) ≤ φ(x k+1 , x 0) suy ra dãy {φ(x k , x 0)} không giảm và bị chặn trên do đó tồn tại giới hạn hữu hạn lim φ(x k , x 0) Vì k→∞ nên φ(x k+1 , x k ) ≤ φ(x k+1 , x 0) − φ(x k , x 0) k→∞limφ(x k+1 , x k ) = 0 (3.2)
Ta có x k+1 = P C k ∩Q k (x 0) ∈ C k nên từ định nghĩa của C k suy ra φ(x k+1 , y k )
≤ φ(x k+1 , x k ) Cho k → ∞ ta thu được k→∞limφ(x k+1 , y k ) = 0 (3.3)
Từ (3.2), (3.3), dãy {x k } bị chặn và Bổ đề 3.1.1 suy ra lim ǁx k+1 − y k ǁ = lim ǁx k+1 − x k ǁ = 0. k→∞
Vì J là ánh xạ 1 − 1 nên k→∞ k→∞limǁJx k+1 − Jy k ǁ = lim ǁJx k+1 − Jx k ǁ = 0 (3.4) k k→∞
Mặt khác ǁJx k+1 − Jy k ǁ = ǁJx k+1 − (α k Jx k + (1 − α k )JTx k )ǁ
≥ (1 − α k )ǁJx k+1 − JTx k ǁ − α k ǁJx k − Jx k+1ǁ suy ra 1 ǁJx k+1 − JTx k ǁ ≤ α 1 −
Từ (3.4) và lim sup α k < 1 suy ra k→∞
(ǁJx k+1 − Jy k ǁ + ǁJx k − Jx k+1ǁ) k→∞limǁJx k+1 − JTx k ǁ = 0.
Vì J −1 cũng là ánh xạ 1 − 1 nên k→∞lim x k+1 Tx k lim k→∞ ǁJ (Jx k+1) − J (JTx k )ǁ = 0.
Từ ǁx k − Tx k ǁ ≤ ǁx k − x k+1ǁ + ǁx k+1 − Tx k ǁ ta có k→∞limǁx k − Tx k ǁ = 0.
Vậy nên nếu {x k j } là một dãy con bất kỳ của dãy {x k } sao cho x k j hội tụ yếu đến x ∈ C thì x ∈ F (T ) = F (T ).
Bước 4 x k → P F (T )(x 0). Đặt w = P F (T )(x 0) Với mọi k ∈ N, từ định nghĩa của x k+1 và w ∈
C k ∩ Q k ta có φ(x k+1 , x 0) ≤ φ(w, x 0) Mặt khác, theo tính nửa liên tục dưới yếu của chuẩn ta có φ(x, x 0) = ǁx^ǁ 2 − 2(x^, Jx 0) + ǁx 0ǁ 2
≤ lim inf(ǁx k ǁ − 2(x k , Jx 0) + ǁx 0ǁ )
Từ định nghĩa của phép chiếu tổng quát suy ra x = w và vì vậy lim φ(x
Sử dụng tính chất Kadec-Klee của E ta thu được {x k j } hội tụ mạnh đến
Dãy {x k j } là một dãy hội tụ yếu tùy ý của {x k }, do đó, có thể kết luận rằng x k hội tụ mạnh đến P F (T )(x 0) Dựa trên ý tưởng của phương pháp lai ghép, Qin và cộng sự đã đưa ra những nghiên cứu mới vào năm 2007.
Trong không gian Banach, một thuật toán ánh xạ không giãn tương đối được đề xuất, theo Định lý 3.2.2 Cụ thể, cho dãy α k (0, 1) với lim k→∞ α k = 0, ta có dãy {x k } được sinh ra từ thuật toán với x 0 ∈ C, và y được tính bằng công thức y = J −1 (α Jx + (1 - α)JTx).
Dãy {x k} hội tụ về điểm P F (T)(x 0) Định lý 3.2.2 được coi là trường hợp đặc biệt của Định lý 3.2.3, liên quan đến sự hội tụ của thuật toán CQ xoay vòng nhằm tìm điểm bất động của các ánh xạ không giãn tương đối, điều này sẽ được chứng minh trong phần dưới đây.
Cho T 1 , T 2 , , T N là họ các ánh xạ không giãn tương đối từ C vào chính nó và F
(T i ) là tập các điểm bất động của
F (T i ). Giả sử F ƒ= ∅, ta có định lý sau đây j→∞
T Định lý 3.2.3 ([6]) Giả sử T i liên tục đều với mọi i = 1, 2, , N Cho
{x k } là dãy sinh bởi x 0 ∈ C, y = J −1 (α Jx + (1 α )JT x ), T := T ,
Giả sử α k là dãy trong (0, 1) sao cho lim k→∞ α k = 0 Khi đó dãy {x k } hội tụ mạnh đến P F (x 0).
Chứng minh Bước 1 C k , Q k là các tập lồi đóng với mọi k ≥ 0.
Từ định nghĩa của C k và Q k dễ dàng suy ra C k là tập đóng và Q k là tập lồi đóng Ta chỉ cần chứng minh C k là tập lồi Vì φ(z, y k ) ≤ α k φ(z, x 0) + (1 − α k )φ(z, x k ) tương đương với
2α k (z, Jx 0) + 2(1 − α k )(z, Jx k ) − 2(z, Jy k ) ≤ α k ǁx 0ǁ 2 + (1 − α k )ǁx k ǁ 2 − ǁy k ǁ 2
Từ đó suy ra C k lồi.
Với mọi u ∈ F ta có φ(u, y k ) = φ(u, J −1 (α k Jx 0 + (1 − α k )JT [k] x k ))
= ǁuǁ 2 − 2(u, α k Jx 0 + (1 − α k )JT [k] x k ) + ǁα k Jx 0 + (1 − α k )JT [k] x k ǁ 2
Do đó u ∈ C k với mọi k ≥ 0 suy ra F ⊂ C k
Rõ ràng F ⊂ C = Q 0 Giả sử F ⊂ Q k với mọi k ≥ 0 Vì x k+1 là hình chiếu của x 0 lên C k ∩ Q k nên theo Bổ đề 3.1.2 ta có
Theo giả thiết quy nạp F ⊂ C k ∩ Q k ta có
Từ định nghĩa của Q k+1 suy ra F ⊂ Q k+1 Vậy F ⊂ Q k với mọi k ≥ 0 Vì
F ƒ= ∅ nên C k ∩ Q k ƒ= ∅, do đó {x k } hoàn toàn xác định.
Từ định nghĩa của Q k suy ra x k = P Q k (x 0) và x k+1 = P C k ∩Q k (x 0) ∈ Q k ta có φ(x k , x 0) ≤ φ(x k+1 , x 0).
Do đó {φ(x k , x 0)} là dãy không giảm Hơn nữa, từ x k = P Q k (x 0) và Bổ đề 3.1.3 suy ra φ(x k , x 0) ≤ φ(u, x 0) − φ(u, x k ) ≤ φ(u, x 0)∀u ∈ F ⊂ Q k
Dãy {φ(x k , x 0)} là dãy bị chặn trên, từ đó suy ra rằng dãy {x k} cũng bị chặn Do {φ(x k , x 0)} không giảm và bị chặn trên, nên tồn tại giới hạn k→∞limφ(x k , x 0) Theo Bổ đề 3.1.3, ta có φ(x k+1 , x k ) = φ(x k+1 , P Q k (x 0)) ≤ φ(x k+1 , x 0) − φ(P Q k (x 0), x 0).
Cho k → ∞ ta thu được lim k→∞ φ(x k+1 , x k ) = 0 (3.5)
Vì x k+1 = P C k ∩Q k (x 0) ∈ C k nên theo định nghĩa C k ta có φ(x k+1 , y k ) ≤ α k φ(x k+1 , x 0) + (1 − α k )φ(x k+1 , x k ).
Kết hợp với lim k→∞ α k = 0 và (3.5) ta thu được k→∞limφ(x k+1 , y k ) = 0 (3.6)
Từ (3.5), (3.6) và Bổ đề 3.1.1 suy ra lim ǁx k+1 − y k ǁ = lim ǁx k+1 − x k ǁ = 0,
Ta có suy ra k→∞lim ǁx k+l − x k ǁ = 0 với mọi l ∈ {1, 2, , N } (3.7) ǁx k − y k ǁ ≤ ǁx k − x k+1ǁ + ǁx k+1 − y k ǁ k→∞limǁx k − y k ǁ = 0 (3.8)
Vì J là ánh xạ 1 − 1 trên tập bị chặn nên
Chú ý rằng k→∞limǁJx k+1 − Jy k ǁ = lim ǁJx k+1 − Jx k ǁ = 0. ǁJT [k] x k − Jy k ǁ = ǁJT [k] x k − (α k Jx 0 + (1 − α k )JT [k] x k )ǁ
Kết hợp với lim k→∞ α k ta thu được lim JT [k] x k Jy k = 0. k→∞
Vì J −1 là ánh xạ 1 − 1 trên tập bị chặn nên
Ta có k→∞limǁT [k] x k − y k ǁ = 0 (3.9) ǁx k − T [k] x k ǁ ≤ ǁx k − y k ǁ + ǁy k − T [k] x k ǁ và theo (3.8) và (3.9) ta thu được
Ta có k→∞limǁT [k] x k − x k ǁ = 0 (3.10) ǁx k − T k+l x k ǁ ≤ ǁx k − x k+l ǁ + ǁx k+l − T k+l x k+l ǁ + ǁT k+l x k+l − T k+l x k ǁ với mọi l ∈ {1, 2, , N } Từ giả thiết T l liên tục đều kết hợp với (3.8) và (3.10) suy ra k→∞limǁx k − T k+l x k ǁ = 0 ∀l ∈ {1, 2, , N }. k→∞ ǁ − ǁ
Vậy nên lim k→∞ ǁx k − T l x k ǁ = 0 với mọi l ∈ {1, 2, , N }.
Giả sử {x_k^j} là một dãy con của {x_k} hội tụ yếu đến x ∈ C, khi đó x thuộc F = F Chúng ta sẽ chứng minh rằng x = P_F(x_0) Đặt w = P_F(x_0) Từ x_{k+1} = P_{C_k} ∩ Q_k(x_0) và w ∈ F ⊂ C_k ∩ Q_k, ta có φ(x_{k+1}, x_0) ≤ φ(w, x_0) Hơn nữa, nhờ tính liên tục yếu của chuẩn, ta có φ(w, x_0) = ||w||^2 - 2(w, Jx_0) + ||x_0||^2.
≤ lim inf(ǁx k j ǁ − 2(x k j , Jx 0) + ǁx 0ǁ ) lim inf φ(x k , x 0) j→∞ lim sup φ(x k j , x 0) j→∞
Từ định nghĩa của P (x ) ta có x = w và vì vậy lim φ(x , w) = φ(x, x ) Bởi
F 0 ^ j→∞ k j ^ 0 vậy nên lim ǁx k j ǁ = ǁwǁ Sử dụng tính chất Kadec-Klee của E ta thu được
{x k j } hội tụ mạnh đến P F (x 0) Vì {x k j } là dãy con hội tụ yếu bất kỳ của {x k } nên ta có thể kết luận rằng {x k } hội tụ mạnh đến P F (x 0) □
Chú ý Trường hợp N = 1, thuật toán lặp xoay vòng của Liu trùng với thuật toán của Qin-Su.
Thuật toán CQ xoay vòng thực hiện tuần tự, dẫn đến chi phí tính toán cao khi N lớn Điều này khiến thuật toán trở nên không hiệu quả trên bó máy tính Đối với trường hợp N lớn, có thể áp dụng phương pháp CQ song song để tối ưu hóa hiệu suất.
≤ j→∞ Định lý 3.2.4 ([2]) Giả sử {x k } là dãy sinh bởi thuật y i = J −1 (α k Jx 0 + (1 − α k )JT i x k ) ∀i = 1, 2, N,
Giả sử {α k } là dãy trong khoảng (0, 1) và lim α k = 0 Khi đó dãy {x k } hoàn toàn xác định và x k hội tụ mạnh đến P F (x 0) ∈ F khi k → ∞.
Nhận xét Trong thuật toán của Liu, tập C k phải xây dựng cho mọi y k
Trong thuật toán song song ta chỉ cần tìm tập C k cho y i cách xa x k nhất
Hơn nữa, việc tính y i có thể thực hiện đồng thời trên N bộ xử lý.
Chứng minh Định lý này cũng chứng minh theo các bước như trong các Định lý 3.2.1 và 3.2.3.
Bước 1 Dãy {x k } hoàn toàn xác định.
Rõ ràng Q k là tập đóng và bị chặn với mọi k ≥ 0 Hơn nữa φ(z, y i k ) ≤ α k φ(z, x 0) + (1 − α k )φ(z, x k ) tương đương với i k 1 2
{α k ǁx 0ǁ 2 điều này chỉ ra rằng C k là tập lồi đóng.
Vì hàm φ : C → R với φ(x) = ǁxǁ 2 lồi nên với mọi p ∈ F ta có φ(p, y i k ) = φ(p,
= ǁpǁ 2 − 2(p, α k Jx 0 + (1 − α k )JT i x k ) + ǁα k Jx 0 + (1 − α k )JT i
≤ α k φ(p, x 0) + (1 − α k )φ(p, x k ) (do T i k là ánh xạ không giãn).
Vì vậy p ∈ C k và F ⊂ C k với mọi k ≥ 0.
Rõ ràng F ⊂ Q 0 = C Giả sử F ⊂ Q k−1 với mọi k ≥ 1, chúng ta sẽ chỉ ra rằng F ⊂ Q k Thật vậy, vì x k = P C k−1 ∩Q k−1 (x 0) nên theo Bổ đề 3.1.2 suy ra rằng (x k − z, Jx 0 − Jx k ) ≥ 0 với mọi z ∈ C k−1 ∩ Q k−1 Lại vì F ⊂
C k−1 ∩ Q k−1 nên ta có (x k − z, Jx 0 − Jx k ) ≥ 0 với mọi z ∈ F Vì vậy theo định nghĩa của Q k ta suy ra F ⊂ Q k Bởi vậy nên F ⊂ C k ∩ Q k với mọi k ≥ 0 Vì F ƒ= ∅ theo giả thiết nên tồn tại x k+1 = P C ∩Q (x 0).
Bước 2 Dãy {x k } bị chặn và mọi điểm tụ yếu của nó thuộc F
Vì T i là ánh xạ không giãn tương đối nên F (T i ) lồi đóng (i = 1, 2,
Do đó F là tập lồi đóng và vì vậy tồn tại duy nhất w = P F (x 0).
Sử dụng Bổ đề 3.1.2 và định nghĩa của Q k ta có x k = P Q (x 0), hơn nữa x k+1 = P C k ∩Q k (x 0) ∈ Q k Bởi vậy nên φ(x k , x 0) ≤ φ(x k+1 , x 0) Do đó dãy {φ(x k , x 0)} không giảm Vì w ∈ F ⊂ Q k và x k = P Q k (x 0) nên sử dụng Bổ đề
Bất đẳng thức cuối cùng đảm bảo tính bị chặn của dãy {x k } và {φ(x k , x 0)} Vì vậy tồn tại giới hạn lim φ(x k , x 0).Từ x k+1 = P C k ∩Q k (x 0) ∈ Q k và x k
= P Q k (x 0) ta có Điều này suy ra lim k→∞ φ(x k+1 , x k ) ≤ φ(x k+1 , x 0) − φ(x k , x 0). φ(x k+1 , x k ) = 0 và vì vậy theo Bổ đề 3.1.1 ta có lim x k+1 k→∞ x k ǁ = 0 Sử dụng x k+1 ∈ C k và định nghĩa của C k ta cũng có φ(x k+1 , y i k ) ≤ α k φ(x k+1 , x 0) + (1 − α k )φ(x k+1 , x k ).
Từ tính bị chặn củaφ(x k , x 0) và giả thiết lim k→∞ α k = 0 nên khi cho k → ∞ ta thu được lim φ(x k+1 , y i k ) = 0 Một lần nữa, theo Bổ đề 3.1.1 ta thu được k→∞lim k→∞ k ǁx k+1 − y i k ǁ = 0.
Vì ǁx k − y i k ǁ ≤ ǁx k − x k+1ǁ + ǁx k+1 − y i k ǁ nên cho k → ∞ ta có lim ǁx k
{} k k k k→∞ y i k ǁ = 0 Từ cách xác định i k ta suy ra lim ǁx k − y i ǁ = 0 với mọi i k k→∞ k
1, 2, , N Vì vậy dãy {y i } cũng bị chặn với mọi i = 1, 2, , N
Từ cách xác định y i suy ra ǁJT i x k − Jy k ǁ = ǁJT i x k − (α k Jx 0 + (1 − α k )JT i x k )ǁ
Đối với mọi i = 1, 2, , N, từ tính không giãn tương đối của T i và tính bị chặn của {x k } dẫn đến tính bị chặn của {T i x k } Vì E trơn đều và J liên tục trên mọi tập con bị chặn, nên Jx 0 JT i x k cũng bị chặn Hơn nữa, do lim k→∞ α k = 0, ta có k→∞limǁJT i x k − Jy k ǁ = 0, với i = 1, 2, , N.
Vì E phản xạ, lồi đều nên J −1 là ánh xạ 1 − 1 trên mọi tập con bị chặn.
Vì ǁx k − T i x k ǁ ≤ ǁx k − y i ǁ + ǁT i x k − y i ǁ nên cho k → ∞ ta thu được k→∞limǁx k − T i x k ǁ = 0, i = 1, 2, , N.
Từ tính bị chặn của {x k } ta suy ra tồn tại dãy con {x k j } sao cho x k j hội tụ yếu về x Vì T i là ánh xạ không giãn tương đối nên x ∈ F (T i ) = F
Vì x k+1 = P C k ∩Q k (x 0) và w ∈ F ⊂ C k ∩ Q k nên ta có φ(x k+1 , x 0) ≤ φ(w, x 0).
Mặt khác từ tính nửa liên tục dưới yếu của chuẩn ta thu được φ(x, x 0) = ǁx^ǁ 2 − 2(x^, Jx 0) + ǁx 0ǁ 2
Với w = P F (x 0), ta có x = w Vì vậy lim φ(x^ k j , x 0) = φ(w, x 0) và lim ǁx k j ǁ j→∞ j→∞ k k i ǁ − ǁ i k→∞ k k k
≤ lim inf{ǁx k ǁ − 2(x k , Jx 0) + ǁx 0ǁ } ǁwǁ Sử dụng tính chất Kadec-Klee của E ta thu được {x k j } hội tụ mạnh đến
P F (x 0) Vì dãy {x k j } là dãy hội tụ yếu bất kỳ của {x k } ta có lim x k = P F (x 0).
Một số thuật toán CQ trong không gian Hilbert
Trong phần này chúng ta sẽ trình bày một số kết quả của phương pháp
CQ khi áp dụng trong không gian Hilbert.
Cho C là một tập con lồi đóng và khác rỗng của không gian
Trong không gian Hilbert, với φ(x, y) = ǁx − yǁ² và ánh xạ J = I (ánh xạ đồng nhất), phép chiếu tổng quát được xác định là phép chiếu trực giao Đặc biệt, ta có ǁP_C(x) − P_C(y)ǁ² ≤ ǁx − yǁ² − ǁ(P_C(x) − x) − (P_C(y) − y)ǁ² ≤ ǁx − yǁ² Áp dụng Định lý 3.2.1 cho ánh xạ không giãn trong không gian Hilbert, chúng ta nhận được kết quả hội tụ mạnh của ánh xạ này Theo Định lý 3.3.1, nếu T là một ánh xạ không giãn từ C vào chính nó và F(T) khác rỗng, thì dãy {x_n} được sinh ra từ T sẽ có tính chất đặc biệt.
x k+1 = P C k ∩Q k (x 0), k = 0, 1, 2, , trong đó dãy {α k } ⊂ [0, a) với a ∈ [0, 1) Khi đó {x k } hội tụ mạnh đến
Chứng minh Cần chứng minh rằng T là ánh xạ không giãn có F (T
Nếu ƒ= ∅, thì T là ánh xạ không giãn tương đối, dẫn đến F(T) ⊂ F^(T) Với u ∈ F(T), tồn tại một dãy {u_n} ⊂ C sao cho u_n hội tụ yếu về u và u_n - Tu_n → 0 Do T không giãn, T bán đóng, từ đó suy ra u T u, và kết luận F(T) = F^(T).
Vì T không giãn nên với mọi x, y ∈ H ta có ǁTx − Tyǁ ≤ ǁx − yǁ tương đương với φ(Tx, Ty) ≤ φ(x, y).
Do đó T là ánh xạ không giãn tương đôi và theo Định lý 3.2.1 ta thu x n →
Cho T i (i = 1, 2, , N ) là họ các ánh xạ không giãn từ C và chính nó và giả sử
(T i ) khác rỗng Chúng ta xét một cải tiến của thuật toán
CQ song song trong không gian Hilbert H mà trong đó các tập con C n và Q n là các nửa không gian của H Khi đó x n+1 = P C n ∩Q n (x 0) có thể tính được tường minh.
Thuật toán 3.3.1 ([2]) Cho x 0 ∈ C là giá trị ban đầu bất kỳ và dãy {α n } ⊂
Trong Thuật toán này chúng ta đã cải tiến để C k và Q k là các nửa không gian hoặc trùng với H vì vậy nên x k+1 = P C k ∩Q k (x 0) có thể không thuộc C.
Do đó để bước tính y i có nghĩa thì bước đặt z k = P C (x k ) là cần thiết Trong trường hợp C = H thì z k = x k
Vì C k và Q k là các nửa không gian, nên nếu C k ∩ Q k khác rỗng, chúng ta có thể áp dụng công thức hiển tính P C ∩Q (x 0) tương tự như trong Thuật toán 2.2.1 Định lý 3.3.2 cung cấp kết quả hội tụ cho dãy {x k } được sinh ra từ Thuật toán 3.3.1, với T i (i = 1, 2, ).
, N ) liên tục và lim α k = 0 Khi đó x k hội tụ mạnh đến P F (x 0) khi k k→∞
Chứng minh.1 Chứng minh tương tự Định lý 3.2.4 với chú ý là z k ∈ C ta có
F ⊂ C k ∩ Q k với mọi k ≥ 0 Và vì F ƒ= ∅ nên dãy {x k } hoàn toàn xác định.
2 Sử dụng x k = P C k (x 0), x k+1 = P C k ∩Q k (x 0) ∈ C k và F ⊂ C k ∩ Q k với mọi k ≥ 0, tương tự Định lý 3.2.4 ta thu được các kết quả sau ǁx 0 − x k ǁ ≤ ǁx 0 − P F (x 0)ǁ ∀k; (3.11) ǁx k − x k+1ǁ → 0 khi k → ∞; ǁx k − y i ǁ → 0 khi k → ∞ với i = 1, 2, , N (3.12)
Từ (3.11) suy ra dãy {x k } và {y i } bị chặn với mọi i = 1, 2, , N Hơn nữa ta có i i i ǁz k − y k ǁ = ǁP C (x k ) − P C (y k )ǁ ≤ ǁx k − y k ǁ.
Nên sử dụng (3.12) ta có k→∞limǁz k − y i ǁ = 0 và lim ǁz k − x k ǁ = 0 (vì ǁz k − x k ǁ ≤ ǁz k − y i ǁ + ǁx k − y i ǁ) (3.13) k→∞ k k
Từ đó suy ra {z k } bị chặn Từ Thuật toán suy ra ǁT i z k − y k ǁ = ǁT i i z k − (α k x 0 + (1 − α k )T i (z k ))ǁ
Với mỗi p ∈ F cố định, ta có ǁx 0 − T i z k ǁ ≤ ǁx 0 − pǁ + ǁp − T i z k ǁ ≤ ǁx 0
− pǁ + ǁp − z k ǁ với i = 1, 2, , N Bất đẳng thức cuối cùng suy ra {ǁx 0 −
→ ∞ k k k chặn Và do đó vì lim k→∞ α k = 0 nên ta có k→∞limǁT i z k − y i k ǁ = 0.
Vậy ta có lim ǁz k − T i z k ǁ = 0 (vì ǁz k − T i z k ǁ ≤ ǁz k − y i ǁ + ǁT i z k − y i ǁ).
Từ tính bị chặn của z k nên tồn tại dãy con z k sao cho z k ⇀ z và limz k
T i z k j ǁ = 0 Từ tính không giãn tương đối của T i suy ra z ∈ F (T i ) = F (T j→∞ i ) với i = 1, 2, , N Vì vậy z ∈ F Sử dụng (3.11) ta có ǁz k j − P F (x 0)ǁ = ǁP C ^(x k ) − P C (P F (x 0))ǁ
Vì vậy từ (3.13) và z k j → z^ ta suy ra (3.14) lim sup z k j→∞ j − P F (x 0)ǁ ≤ 2(ǁx 0 − P F (x 0)ǁ − (z^ − x 0 , P F (x 0) − x 0).
Vì z ∈ F và F lồi nên ta có ǁx 0 − P F (x 0)ǁ 2 − (z − x 0 , P F (x 0) − x 0) = (x 0 − P F (x 0), z − P F (x 0)) ≤ 0. Kết hợp với (3.14) suy ra lim ǁz k j − P F (x 0)ǁ = 0 hoặc z k j → P F (x 0) khi j → ∞.
Vì vậy nên P F (x 0) là điểm tụ yếu duy nhất của {z k } Rõ ràng mọi dãy con hội tụ yếu của {z k } đều hội tụ mạnh về P F (x 0) do đó z k → P F
Từ lim k→∞ z k x k = 0 ta có lim k→∞ x k = P F (x 0) □
Trong nghiên cứu, các tác giả đã áp dụng Thuật toán CQ xoay vòng của Liu và Thuật toán CQ song song để xác định điểm bất động của hai toán tử tích phân phi tuyến trong không gian Hilbert H = L 2 [0, 1].
Tính toán cho thấy, khi sử dụng một bộ xử lý, thuật toán CQ song song mang lại hiệu quả cao hơn so với thuật toán CQ xoay vòng Trong chế độ chạy song song với hai bộ xử lý, thuật toán CQ song song cũng tiết kiệm thời gian hơn đáng kể để đạt được độ chính xác tương tự so với thuật toán CQ xoay vòng.
Bài toán khôi phục ảnh
Phương pháp chiếu-điểm gần kề song song
Bài toán khôi phục ảnh phát biểu lại thành bài toán giải hệ phương trình với toán tử đơn điệu
(4.1) Áp dụng Thuật toán chiếu - điểm gần kề song song để giải hệ phương trình
Bước 1 Giả sử tại bước lặp thứ k ≥ 0 ta đã có x k Tìm y i ∈
− x ) = 0 i = 1, 2, , n. ǁv i ǁ 2 i k k k Nhân vô hướng cả hai vế của phương trình trên với v i ta được i i i i
Bước 2 Tìm chỉ số tối ưu i k :
⇒ ǁx k − y i k ǁ ≤ ǁx k − zǁ, suy ra P H i (x k ) = y i và k k i ( x k , v i ) − à i x k − P H i (x k ) = x k − y k (1 + à k i )ǁv ǁ i 2 v i
|(x k , v i ) − à i | suy ra ǁx k − P H i (x k )ǁ (1 + à i )ǁv ǁ và vỡ vậy ta cú i = argmax
Nếu không thì x k+1 được xác định như sau x k+1 = P H ik ∩W (x 0) = x 0 + λ 1 A i (y i k ) + λ 2(x 0 − x k ), trong đó λ 1 , λ 2 thỏa mãn hệ phương trình
Thử nghiệm số
Xột hệ phương trỡnh (x, v i ) = à i , trong đú
H = L [0, 1], v i = t , à i i + 2 i = 1, 2, 3, 4, và nghiệm chính xác của bài toán này là x ∗ (t) = t.
Tính toán thực hiện ở chế độ tuần tự với x 0 = 10 4 × t và à i = 1 với mọi i, k, sai số ε k được tính theo công thức ε 2 = ǁx k − x ∗ ǁ 2
Bảng 4.1: Thuật toán chiếu-điểm gần kề song song
Giải hệ phương trình đại số tuyến tính
Phương pháp chiếu-điểm gần kề song song
Đây là bài toán khôi phục ảnh với H = R^n, v_i = a_i và à_i = b_i Bằng cách áp dụng thuật toán chiếu - điểm gần kề song song, chúng ta có thể phát triển thuật toán giải hệ phương trình (4.2) như sau.
Cho trước x 0 ∈ R n và à i > 0 và tại lần lặp thứ k ≥ 0 ta đó cú x k
Nếu không thì tìm λ 1 và λ 2 thỏa mãn hệ phương trình
(y i k )), k và tính Ý nghĩa hình học
Do à i > 0 nờn phương trỡnh (4.4) cho thấy rằng y i nằm trong đoạn thẳng
[x k , P i (y i )] Hơn nữa, từ (4.4) và (4.3) ta thu được
•Xét các siêu phẳng nằm trong đoạn thẳng [x k , P i (x k )].
. n (1 + à i )ǁa i ǁ 2 i i Σ Điều này cho thấy H′ i song song với H k i
= {z ∈ R n | (z, x 0 − x k ) = (x k , x 0 − x k )}. là siêu phẳng đi qua điểm x k và vuông góc với vector x 0 − x k k
Trong trường hợp n = 2, m = 3 và à i = 1, giả sử hệ phương trình có nghiệm, các đường thẳng H i được minh họa Với à i = 1, y i được xác định là trung điểm của đoạn thẳng [x k , P i (x k )] cho mọi k và i.
Hình 4.1: Minh họa hình học thuật toán chiếu-điểm gần kề song song
4.2.2 Phương pháp CQ song song
Giải hệ phương trình (4.2) tương đương với bài toán tìm điểm bất động của họ toán tử không giãn P i (x) từ R n vào chính nó.
Với mọi k ≥ 0, hình chiếu của x k lên C = R n là chính nó, tức là z k P R n (x k ) = x k Hơn nữa, ta có k = α k x 0 + (1 − α k )P i (x k ) = α k x 0 + (1 − α k ) x k − a T x k − b i ǁa i ǁ 2 a i Σ
Nếu P C k ∩Q k (x 0) ƒ∈ Q k thì hình chiếu của x 0 lên C k ∩ Q k viết dưới dạng
P C k ∩Q k (x 0) = x 0 + λ 1(x k − P i k (x k )) + λ 2(x 0 − x k ), trong đó λ 1, λ 2 thỏa mãn hệ phương trình
Tóm lại, áp dụng Thuật toán CQ song song giải hệ phương trình (4.2) như sau Cho x 0 ∈ R n và dãy {α k } ⊂ (0, 1) Giả sử tại lần lặp thứ k ≥ 0 ta đã có x k
x k nếu x k ∈ C k , x k+1 = P C k (x 0) nếu P C k (x 0) ∈ Q k , x 0 + λ 1(x k − P i k (x k )) + λ 2(x 0 − x k ) các trường hợp còn lại, trong đó λ 1 , λ 2 là nghiệm của hệ phương trình (4.3) và
Bài viết đã hệ thống hóa các thuật toán hội tụ mạnh để giải các phương trình và hệ phương trình toán tử đơn điệu, cũng như tìm điểm bất động của một tập hợp hữu hạn các ánh xạ không giãn trong không gian Hilbert Phương pháp được áp dụng là sự kết hợp giữa thuật toán điểm gần kề và phép chiếu lên giao của các tập lồi hoặc nửa không gian.
Luận văn đã đề cập đến các vấn đề sau:
1 Hệ thống lại một số phương pháp điểm gần kề và các cải biên của nó trong không gian Hilbert Khái niệm nghiệm gần đúng với sai số cho phép và một số tính chất quan trọng;
2 Trình bày thuật toán chiếu-điểm gần kề để tìm không điểm của toán tử đơn điệu cực đại và định lý hội tụ mạnh đến một điểm trong tập các không điểm;
3 Trình bày các thuật toán song song chiếu-điểm gần kề và CQ tương ứng để giải hệ phương trình với toán tử đơn điệu và tìm điểm bất động của họ các ánh xạ không giãn tương đối trong không gian Hilbert và Banach;
4 Trình bày các định lý hội tụ mạnh cho các toán tử không gian tương đối trong không gian Banach và định lý hội tụ mạnh của phương pháp CQ xoay vòng và CQ song song cho họ hữu hạn các ánh xạ không giãn tương đối trong không gian Banach;
5 Áp dụng thuật toán chiếu-điểm gần kề song song cho bài toán khôi phục ảnh trong không gian Hilbert và một ví dụ số minh họa cho sự hội tụ của thuật toán này;
6 Áp dụng thuật toán chiếu-điểm gần kề song song và phương pháp
CQ song song là phương pháp hiệu quả để giải hệ phương trình khi số ẩn và số phương trình không nhất thiết phải bằng nhau Thuật toán chiếu-điểm gần kề song song trong không gian R² được minh họa một cách rõ ràng qua các ví dụ hình học, giúp người đọc dễ dàng hiểu và áp dụng.
[1]Lê Dũng Mưu và Nguyễn Văn Hiền (2009), Nhập môn giải tích lồi ứng dụng, Nhà xuất bản Khoa học tự nhiên và Công nghệ,
[2] P K Anh and C V Chung (2011), A parallel CQ method for a finite family of relatively nonexpansive mappings (Submitted for publication).
[3]P K Anh and C V Chung (2011), On strongly convergent parallel prox- imal point algorithms, Journal of Science, VNU, 27(2).
[4]O Guler (1991), On the convergence of the proximal point algorithm for convex minimization, SIAM J Optim., 2, 649-664.
[5]S Kamimura and W Takahashi (2002), Strong convergence of a proximal- type algorithm in a Banach space, SIAM J Optim., 13, 938-945.
[6]X F Liu (2011), Strong convergence theorems for a finite family of rela- tively nonexpansive mappings, Vietnam J Math., 39, 63-69.
[7]S Matsushita and W Takahashi (2005), A strong convergence theorem for relatively nonexpansive mappings in a Banach space, J. Approx Theory, 134, 257-266.
[8]R T Rockafellar (1976), Monotone operators and proximal point algo- rithm, SIAM J Contr Optim., 14, 877-897.
[9]X L Qin and Y F Su (2007), Strong convergence theorems for relatively nonexpansive mappings in a Banach space, Nonlinear Anal., 67, 1958-1965.
[10] M V Solodov and B F Svaiter (1999), A hybrid projection- proximal point algorithm, J Conv Anal., 6, 59-70.