Luận án TS: Phương pháp song song giải bài toán đặt không chỉnh với toán tử đơn điệu - Cao Văn Chung

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Cao Văn Chung PHƯƠNG PHÁP SONG SONG GIẢI BÀI TOÁN ĐẶT KHÔNG CHỈNH VỚI TOÁN TỬ ĐƠN ĐIỆU LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2012 TIEU LUAN MOI download : skknchat@gmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Cao Văn Chung PHƯƠNG PHÁP SONG SONG GIẢI BÀI TOÁN ĐẶT KHÔNG CHỈNH VỚI TOÁN TỬ ĐƠN ĐIỆU Chuyên ngành: Toán học Tính toán Mã số: 62 46 30 01 LUẬN ÁN TIẾN SĨ TOÁN HỌC Tập thể hướng dẫn khoa học: HD1: GS. PHẠM KỲ ANH HD2: GS. NGUYỄN BƯỜNG Hà Nội - 2012 TIEU LUAN MOI download : skknchat@gmail.com Mục lục Trang Lời cam đoan. 2 Danh mục các ký hiệu và chữ viết tắt.

6 Danh mục các bảng. Kiến thức chuẩn bị. Khái niệm cơ sở. Toán tử đơn điệu và phương trình với toán tử đơn điệu.

Bài toán đặt không chỉnh và phương pháp hiệu chỉnh. Hệ thống máy tính song song và lập trình song song. Các ví dụ minh họa. Phương pháp chỉnh lặp song song.

Phương pháp chỉnh lặp ẩn song song. Trường hợp dữ liệu chính xác. Trường hợp dữ liệu có nhiễu. Phương pháp chỉnh lặp hiện song song.

Ứng dụng và thử nghiệm số. Các phương pháp chiếu - lặp song song. Phương pháp chiếu - điểm gần kề song song. Các phương pháp CQ song song trong không gian Banach.

91 4 TIEU LUAN MOI download : skknchat@gmail. Các phương pháp CQ song song trong không gian Hilbert. Thử nghiệm số. Giải hệ phương trình với toán tử ngược đơn điệu mạnh 108 3.

Tìm điểm bất động chung của họ hữu hạn toán tử không giãn tương đối. Phương pháp song song giải phương trình với toán tử đơn điệu trơn. Phương pháp Newton hiệu chỉnh song song và sự hội tụ. Thử nghiệm số.

Phương trình toán tử đơn điệu khả vi cấp hai. Thử nghiệm với toán tử khả vi. 136 Danh mục công trình khoa học của tác giả liên quan đến luận án. 138 Tài liệu tham khảo.

148 5 TIEU LUAN MOI download : skknchat@gmail.com DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT h·, ·i Tích vô hướng (hoặc tích đối ngẫu) A∗ Toán tử liên hợp của toán tử tuyến tính A argminf (x) (argmaxf (x)) Phần tử cực tiểu (cực đại) hóa phiếm hàm f (x) F (T ) (F̂ (T )) Tập điểm bất động (bất động tiệm cận) của T Gr(F ) Đồ thị của ánh xạ (đa trị) F H Không gian Hilbert JAr := (rA + J)−1 J Giải thức của toán tử (đa trị) đơn điệu A PC Phép chiếu metric lên tập lồi đóng C ⊂ X ΠC Phép chiếu metric suy rộng lên tập lồi đóng C ⊂ X PIIRM (PEIRM) Phương pháp chỉnh lặp ẩn (hiện) song song PEIRMm Phương pháp PEIRM với m bước lặp trong. PRPXPM Phương pháp điểm gần kề hiệu chỉnh song song PPPXPM Phương pháp chiếu - điểm gần kề song song PCQM Phương pháp lai ghép song song CCQM Thuật toán CQ xoay vòng đề xuất trong [54] PRNM Phương pháp song song dạng Newton U s (J := U 2 ) Ánh xạ đối ngẫu (ánh xạ đối ngẫu chuẩn tắc) X, X ∗ Không gian Banach X và không gian đối ngẫu của nó x† Nghiệm chuẩn nhỏ nhất (hoặc x0 -chuẩn nhỏ nhất) x∗n Nghiệm phương trình hiệu chỉnh A(x) + αn x = 0 TOL(RT OL = T OL/kx† k) Sai số (Sai số tương đối tính theo %) RAT Tỷ số giữa sai số tuyệt đối và αn : RAT = T OL/αn !NA Kết quả chạy số không ổn định - sai số ra vô hạn nmax Tổng số bước lặp Tp (Ts ) Thời gian chạy (giây) khi chạy song song (tuần tự) Sp = Ts /Tp (Ep = Sp /N ) Tỷ lệ tăng tốc độ (Hiệu suất trung bình mỗi CPU) 6 TIEU LUAN MOI download : skknchat@gmail.com Danh mục các bảng Chương 2.1 So sánh PIIRM & PEIRM với cùng số lần lặp .2 So sánh PIIRM & PEIRM với cùng sai số .3 So sánh PIIRM khi chạy song song & tuần tự .4 PIIRM với dữ liệu có nhiễu .1 So sánh PRPXPM & PPPXPM với số bước lặp nhỏ .2 So sánh PRPXPM & PPPXPM với số bước lặp lớn .3 So sánh PPPXPM & CQ với cùng số bước lặp .4 So sánh PPPXPM & CQ với cùng độ chính xác .1 αn lớn & dữ liệu chính xác - Toán tử khả vi cấp 2 .2 Số bước lặp n lớn & dữ liệu chính xác - Toán tử khả vi cấp 2 .3 αn lớn & dữ liệu có nhiễu - Toán tử khả vi cấp 2 .4 Số bước lặp n lớn & dữ liệu có nhiễu - Toán tử khả vi cấp 2 .5 αn lớn & dữ liệu chính xác - Toán tử khả vi .6 Số bước lặp n lớn & dữ liệu chính xác - Toán tử khả vi .7 Thử nghiệm với dữ liệu có nhiễu - Toán tử khả vi. 135 7 TIEU LUAN MOI download : skknchat@gmail.com Mở đầu Luận án này nghiên cứu các phương pháp song song giải hệ phương trình toán tử Ai (x) := Fi (x) − fi = 0, i = 1, N (1) hoặc phương trình với toán tử phân rã được thành tổng các toán tử N X N X A(x) := Ai (x) = (Fi (x) − fi ) = 0. (2) i=1 i=1 Ở đây các toán tử Fi : X → Y , phần tử fi ∈ Y đã cho; với X là không gian Banach và Y = X ∗ - không gian đối ngẫu của X, hoặc X là không gian Hilbert và Y = X.

Hơn nữa, trong luận án này ta xét các toán tử Fi có tính đơn điệu, tức là với mọi x, y ∈ X ta có hFi (x) − Fi (y), x − yi ≥ 0. Trường hợp X là không gian Banach, ta ký hiệu hf, xi := f (x) với mọi x ∈ X, f ∈ X ∗. Các vấn đề được nghiên cứu trong luận án liên quan đến phương trình với toán tử đơn điệu, bài toán đặt không chỉnh và tính toán song song. Phương trình với toán tử đơn điệu thường xuất hiện trong nhiều lĩnh vực khoa học kỹ thuật cũng như kinh tế xã hội.

Ví dụ trong xử lý ảnh, người ta cần khôi phục hình ảnh đối tượng ban đầu từ các hình chiếu của nó. Điều này có thể đưa về việc giải một hệ phương trình dạng Fi (x) = fi , trong đó các toán tử Fi là đơn điệu. Bài toán khôi phục ảnh nói trên và một số vấn đề thực tế khác dẫn đến bài toán chấp nhận lồi. Ở đó ta cần tìm hình chiếu của một phần tử lên giao của một số tập lồi (xem [27]).

Đây là một trường hợp của bài toán tìm điểm bất động chung của một họ các toán tử không giãn Fi trong không gian Hilbert, tương đương với việc giải hệ phương trình với các toán tử đơn điệu Ai (x) := x − Fi (x) = 0. 8 TIEU LUAN MOI download : skknchat@gmail.com Một số vấn đề thực tế khác lại dẫn đến việc tìm cực trị không ràng buộc của một họ hữu hạn các phiếm hàm lồi, trơn. Bài toán này cũng sẽ đưa đến hệ phương trình dạng (1) với toán tử đơn điệu. Trong khi đó, một số mô hình kinh tế dẫn đến một dạng bài toán gọi là bài toán bù (xem [2,22]).

Bài toán này, trong một số trường hợp, có thể chuyển về việc giải phương trình với toán tử đơn điệu. Một số mô hình ứng dụng trong cơ học lượng tử, lý thuyết lọc. cũng dẫn tới các bài toán dạng (2), với Fi được xây dựng từ các toán tử vi phân (ví dụ, toán tử Laplace ∆ hoặc div của một hàm theo toán tử ∇) sao cho A là toán tử đơn điệu (xem [4, 77]). Một bài toán khác gọi là nhận dạng tham số đa dữ liệu, xuất hiện nhiều trong các lĩnh vực y dược, sinh học phân tử.

cũng có thể đưa về dạng phương trình (2) với toán tử đơn điệu (xem [26, 69]). Ngoài ra, trong nhiều lĩnh vực khoa học kỹ thuật và toán học tính toán, ta phải giải phương trình dạng F x = f , trong đó F toán tử tuyến tính xác định không âm. Đây cũng là một bài toán dạng (1). Vì khả năng ứng dụng rộng rãi như vậy nên phương trình với toán tử đơn điệu đã được nghiên cứu rất nhiều.

Những kết quả định tính cho lớp toán tử này đã được nhiều nhà toán học như H. Browder đã chỉ ra một số tính chất quan trọng của toán tử đơn điệu cực đại, cũng như tìm ra mối liên hệ giữa phương trình với toán tử đơn điệu và bất đẳng thức biến phân. Tính chất đơn điệu cực đại, bức và một số đặc điểm khác của toán tử dạng cA + J, trong đó J là ánh xạ đối ngẫu chuẩn tắc, còn c > 0, A là toán tử đơn điệu được chỉ ra trong [20, 58, 62]. Lớp toán tử đơn điệu cực đại dạng A+αJ và mối liên hệ với dưới vi phân của các phiếm hàm lồi, cũng như các toán tử đơn điệu dạng thế năng đã được nghiên cứu trong [6, 7, 14–17, 36, 46, 59, 63, 74, 84, 85, 87].

Như đã biết, bài toán F (x) = f (3) với F là toán tử đơn điệu, nếu không có thêm giả thiết gì về toán tử F , thường là đặt không chỉnh (xem [1, 2, 4, 20, 76, 77]). Khái niệm về tính đặt chỉnh được J. Hadamard định nghĩa như sau (xem [86]): Nếu (a) ∀f ∈ Y 9 TIEU LUAN MOI download : skknchat@gmail. Khi ít nhất một trong ba điều kiện trên không thỏa mãn, ta nói bài toán là đặt không chỉnh (ill-posed problem hay incorrectly-posed problem).

Lúc đó việc giải số bài toán sẽ rất khó khăn vì các sai số nhỏ trong dữ liệu hoặc trong quá trình giải số trên máy tính có thể dẫn tới sự sai lệch rất lớn của kết quả. Những nhà khoa học đã có công đặt nền móng cho lý thuyết bài toán đặt không chỉnh phải kể đến A. Cũng vì ý nghĩa quan trọng của lý thuyết bài toán đặt không chỉnh, nhiều nhà khoa học thế giới đã đi sâu nghiên cứu và đề xuất các phương pháp giải lớp bài toán dạng này, như I. Do tính không ổn định của dạng bài toán này mà người ta phải sử dụng các phương pháp ổn định hóa để giải nó, gọi là các phương pháp hiệu chỉnh (còn gọi là chỉnh hóa, hay chính quy hóa - regularization).

Tư tưởng của việc hiệu chỉnh là thay bài toán không chỉnh ban đầu bằng một họ các bài toán đặt chỉnh mà nghiệm của các bài toán đặt chỉnh đó hội tụ về nghiệm bài toán ban đầu, khi tham số hiệu chỉnh dần tới không.