Luận văn Thạc sĩ Toán học: Phương pháp lặp ẩn và phương pháp lặp hiện giải bài toán chấp nhận tách

Chia sẻ: Tri Lễ | Ngày: | Loại File: PDF | Số trang:42

Thêm vào BST

Báo xấu

23
lượt xem 2
download

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

Đề tài luận văn nghiên cứu bài toán chấp nhận tách và một số phương pháp giải: Cho C và Q là các tập con lồi đóng khác rỗng của không gian Hilbert tương ứng H1 và H2. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Phương pháp lặp ẩn và phương pháp lặp hiện giải bài toán chấp nhận tách

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN HỒNG NHÂN PHƯƠNG PHÁP LẶP ẨN VÀ PHƯƠNG PHÁP LẶP HIỆN GIẢI BÀI TOÁN CHẤP NHẬN TÁCH LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN HỒNG NHÂN PHƯƠNG PHÁP LẶP ẨN VÀ PHƯƠNG PHÁP LẶP HIỆN GIẢI BÀI TOÁN CHẤP NHẬN TÁCH Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
i Mục lục Danh sách ký hiệu ii Mở đầu 1 1 Một số kiến thức cơ bản 4 1.1 Bài toán chấp nhận tách trong không gian Hilbert . . . . . 4 1.1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . 4 1.1.2 Bài toán chấp nhận tách trong không gian Hilbert . 16 1.2 Một số bổ đề cần thiết . . . . . . . . . . . . . . . . . . . . 17 2 Phương pháp lặp ẩn và phương pháp lặp hiện giải bài toán chấp nhận tách 21 2.1 Phương pháp lặp ẩn . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 Mô tả phương pháp . . . . . . . . . . . . . . . . . 21 2.1.2 Sự hội tụ của phương pháp . . . . . . . . . . . . . 22 2.2 Phương pháp lặp hiện . . . . . . . . . . . . . . . . . . . . 26 2.2.1 Mô tả phương pháp . . . . . . . . . . . . . . . . . 26 2.2.2 Sự hội tụ của phương pháp . . . . . . . . . . . . . 26 Tài liệu tham khảo 38
ii Danh sách 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 H không gian Hilbert thực X không gian tuyến tính C tập con đóng lồi của H A toán tử tuyến tính giới nội T toán tử phi tuyến hx, yi tích vô hướng của hai vectơ x và y kxk chuẩn của vectơ x xn → x xn hội tụ mạnh đến x xn * x xn hội tụ yếu x F ix(T ) tập điểm bất động của T I ánh xạ đơn vị PC phép chiếu từ H lên C KM Krasnosel’skii-Mann
1 Mở đầu Đề tài luận văn nghiên cứu bài toán chấp nhận tách và một số phương pháp giải: Cho C và Q là các tập con lồi đóng khác rỗng của không gian Hilbert tương ứng H1 và H2 . Bài toán chấp nhận tách được phát biểu: Tìm điểm x∗ với tính chất x∗ ∈ C và Ax∗ ∈ Q, (1) ở đây A : H1 → H2 là toán tử tuyến tính giới nội. Bài toán chấp nhận tách trong không gian Hilbert hữu hạn chiều đã được đề xuất bởi Censor và Flfving để mô hình hóa bài toán ngược xuất hiện trong khôi phục ảnh và trong y học. Mới đây, người ta tìm thấy bài toán này cũng có thể dùng để mô hình hóa sự bức xạ. Lưu ý rằng bài toán chấp nhận tách (1) có thể phát biểu dưới dạng phương trình bất động PC I − γAT (I − PQ ) A x∗ = x∗ . (2) ở đây, AT là ánh xạ đối ngẫu của A, PC và PQ là các phép chiếu mêtric tương ứng lên C và Q. Ta thấy, x∗ là nghiệm của bài toán chấp nhận tách (1) khi và chỉ khi x∗ là điểm bất động của PC I − γAT (I − PQ ) A . Từ đó suy ra rằng ta có thể sử dụng các phương pháp tìm điểm bất động giải bài toán chấp nhận tách. Một thuật toán cơ bản giải bài toán (1) là thuật toán CQ của Byrne. Thuật toán này sử dụng một phương pháp chiếu gradient (GPM) trong bài toán cực tiểu lồi. Tiếp đó, Byrne áp dụng bước lặp cho
2 thuật toán CQ và Zhao sử dụng bước lặp cho thuật toán CQ nhiễu giải bài toán chấp nhận tách. Chúng ta biết rằng thuật toán CQ và thuật toán KM cho bài toán chấp nhận tách không nhất thiết hội tụ mạnh trong không gian Hilbert vô hạn chiều. Mới đây, Wang và Xu đề xuất thuật toán CQ cải biên với sự hội tụ mạnh bằng cách đưa vào đường cong xấp xỉ cho bài toán chấp nhận tách trong không gian Hilbert vô hạn chiều và nhận được nghiệm có chuẩn cực tiểu của bài toán chấp nhận tách là giới hạn mạnh của đường cong xấp xỉ. Luận văn này được thực hiện tại Trường Đại học Khoa học – Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của GS. TS. Nguyễn Bường. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các Thầy giáo, Cô giáo đã tham gia giảng dạy lớp Cao học Toán K9Y (khóa 2015–2017); Nhà trường và các phòng chức năng của Trường; Khoa Toán – Tin, trường Đại học Khoa học – Đại học Thái Nguyên, lãnh đạo đơn vị công tác đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập. Tác giả cũng xin gửi lời cảm ơn tới tập thể lớp Cao học Toán K9Y (khóa 2015–2017), các đồng nghiệp đã luôn động viên và giúp đỡ tác giả rất nhiều trong quá trình học tập, nghiên cứu. Cuối cùng, tôi xin gửi lời cảm ơn chân thành tới gia đình, bạn bè đã động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi khi học tập và nghiên cứu.
3 Thái Nguyên, ngày 10 tháng 11 năm 2017 Tác giả luận văn Trần Hồng Nhân
4 Chương 1 Một số kiến thức cơ bản Chương này gồm 2 mục: Mục 1.1 giới thiệu về không gian Hilbert thực và một số tính chất của không gian Hilbert; trình bày định nghĩa toán tử đơn điệu và bài toán chấp nhận tách trong không gian Hilbert thực. Mục 1.2 trình bày một số bổ đề bổ trợ cho chương tiếp theo. Các kiến thức của chương này được viết trên cơ sở tổng hợp các tài liệu [1], [2]. 1.1 Bài toán chấp nhận tách trong không gian Hilbert 1.1.1 Không gian Hilbert a) Định nghĩa và tính chất Định nghĩa 1.1.1. Một tập X được gọi là không gian tuyến tính trên R nếu với mỗi cặp (x, y) ∈ X × X, một phần tử của X, ta gọi là tổng của x và y, ký hiệu là x + y; với mỗi α ∈ R và x ∈ X, một phần tử của X, gọi là tích của α và x, ký hiệu là αx thỏa mãn các điều kiện sau: (1) x + y = y + x với mọi x, y ∈ X (tính chất giao hoán); (2) (x + y) + z = x + (y + z), ∀x, y, z ∈ X (tính chất kết hợp); (3) tồn tại phần tử không của X, ký hiệu 0, sao cho: x + 0 = 0 + x với mọi x ∈ X;
5 (4) với mọi x ∈ X, tồn tại phần tử đối của x, ký hiệu là −x, sao cho x + (−x) = 0 với mọi x ∈ X; (5) 1 · x = x · 1 = x, với mọi x ∈ X (1 là phần tử đơn vị); (6) α(βx) = (αβ)x, với mọi α, β ∈ R, với mọi x ∈ X; (7) (α + β)x = αx + βx, với mọi α, β ∈ R, với mọi x ∈ X; (8) α(x + y) = αx + αy, với mọi α ∈ R, với mọi x, y ∈ X. Định nghĩa 1.1.2. Cho H là một không gian tuyến tính trên trường số thực R. Tích vô hướng trên không gian H là một ánh xạ đi từ tích Descartes H × H vào R, ký hiệu là h., .i, thỏa mãn các điều kiện sau: (1) hx, yi = hy, xi với mọi x, y ∈ H. (2) hx + y, zi = hx, zi + hy, zi với mọi x, y, z ∈ H. (3) hαx, yi = αhx, yi với mọi x, y ∈ H và mọi α ∈ R. (4) hx, xi > 0 khi và chỉ khi x 6= 0 và hx, xi = 0 khi và chỉ khi x = 0. Nhận xét 1.1.3. Từ Định nghĩa 1.1.2 ta suy ra (1) hx, αyi = αhy, xi với mọi x, y ∈ H và mọi α ∈ R; (2) hx, y + zi = hx, yi + hx, zi với mọi x, y, z ∈ H. Định nghĩa 1.1.4. Không gian tuyến tính H cùng với một tích vô hướng trên nó được gọi là một không gian tiền Hilbert. Định lí 1.1.5. (bất đẳng thức Schwarz) Trong không gian tiền Hilbert H, với mọi x, y ∈ H ta luôn có bất đẳng thức sau: |hx, yi|2 ≤ hx, xihy, yi. (1.1)
6 Chứng minh. Với mọi số thực α và với mọi x, y ∈ H ta có 0 ≤ hx − αy, x − αyi = hx, xi − 2αhx, yi + α2 hy, yi. Từ đây suy ra ∆ = |hx, yi|2 − hx, xihy, yi ≤ 0 với mọi x, y ∈ H. Hay |hx, yi|2 ≤ hx, xihy, yi với mọi x, y ∈ H. Định lý được chứng minh. Dấu đẳng thức trong bất đẳng thức (1.1) xảy ra khi và chỉ khi x và y phụ thuộc tuyến tính. Định lí 1.1.6. Không gian tiền Hilbert H là một không gian tuyến tính định chuẩn với chuẩn được xác định bởi p kxk = hx, xi với mọi x ∈ H. (1.2) Chuẩn này được gọi là chuẩn cảm sinh từ tích vô hướng. Hàm số kxk = hx, xi với mọi x ∈ H là một chuẩn trên H. p Chứng minh. Thật vậy, từ điều kiện (4) của Định nghĩa 1.1.2 ta có kxk > 0 nếu x 6= 0 và kxk = 0 nếu x = 0 với x ∈ H. Từ điều kiện (1) và (3) của Định nghĩa 1.1.2 ta suy ra kαxk = |α|.kxk với mọi α ∈ R và mọi x ∈ H. Từ bất đẳng thức Schwarz và cách định nghĩa chuẩn ta có |hx, yi| ≤ kxk.kyk với mọi x, y ∈ H. (1.3) Từ đó với mọi x, y ∈ H ta có: hx + y, x + yi = hx, xi + 2hx, yi + hy, yi 2 ≤ kxk2 + 2kxk.kyk + kyk2 = kxk + kyk . Suy ra kx + yk ≤ kxk + kyk với mọi x, y ∈ H.
7 Định nghĩa 1.1.7. Nếu H là một không gian tiền Hilbert thực và đầy đủ đối với chuẩn cảm sinh từ tích vô hướng xác định bởi (1.2) thì H được gọi là không gian Hilbert thực. Ví dụ 1. Không gian n ∞ X o 2 2 l = x = {xn }n ∈ R : |xn | < +∞ n=1 là không gian Hilbert với tích vô hướng ∞ X hx, yi = x n yn , x = {xn }n∈N , y = {yn }n∈N ∈ l2 n=1 và chuẩn v u∞ ∞ X 1 p uX 2 2 kxk = hx, xi = t 2 |xn | = |xn | . n=1 n=1 Ví dụ 2. Không gian L2 [a, b] là không gian Hilbert với tích vô hướng: Zb hx, yi = x(t)y(t)dt, ∀x, y ∈ L2 [a, b] a và chuẩn Zb ! 21 kxk = |x(t)|2 dt . a Ví dụ 3. Gọi C[a, b] là tập tất cả các hàm giá trị thực liên tục trên khoảng đóng hữu hạn [a, b] ⊂ R. Trong C[a, b] xét tích vô hướng Z b hx, yi = x(t)y(t).dt, x(t), y(t) ∈ C[a, b]. a Không gian C[a, b] với chuẩn Z b 21 2 kxk = |x(t)| .dt a là không gian tiền Hilbert, nhưng không phải là không gian Hilbert.
8 Định lí 1.1.8. Giả sử {xn }n∈N , {yn }n∈N là hai dãy lần lượt hội tụ mạnh đến x0 , y0 trong không gian tiền Hilbert thực H. Khi đó, lim hxn , yn i = hx0 , y0 i. n→∞ Chứng minh. Giả sử lim xn = x0 , lim yn = y0 trong không gian Hilbert n→∞ n→∞ H. Ta sẽ chứng minh lim hxn , yn i = hx0 , y0 i trong R. n→∞ Thật vậy, |hxn , yn i − hx0 , y0 i| = |hxn , yn i + hxn , y0 i − hxn , y0 i − hx0 , y0 i| ≤ |hxn , yn − y0 i| + |hxn − x0 , y0 i| ≤ kxn k.kyn − y0 k + kxn − x0 k.ky0 k. Vì dãy {xn }n∈N hội tụ trong H nên tồn tại một số M > 0 sao cho kxn k ≤ M với mọi n ∈ N. Do đó, lim hxn , yn i = hx0 , y0 i. n→∞ Định lý được chứng minh. Nhận xét 1.1.9. Tích vô hướng là một phiếm hàm song tuyến tính liên tục trên H × H. Định lí 1.1.10. Với mọi x, y thuộc không gian tiền Hilbert H, ta luôn có đẳng thức hình bình hành sau: 2 22 2 kx + yk + kx − yk = 2 kxk + kyk .
9 Chứng minh. Với mọi x, y ∈ H, ta có kx + yk2 = hx + y, x + yi = kxk2 + kyk2 + 2hx, yi và kx − yk2 = hx − y, x − yi = kxk2 + kyk2 − 2hx, yi. Cộng hai đẳng thức trên ta được đẳng thức cần chứng minh. Áp dụng đẳng thức hình bình hành cho x − y và x − z ta có hệ quả sau. Hệ quả 1.1.11. Cho H là một không gian tiền Hilbert và x, y, z ∈ H. Khi đó, ta có đẳng thức Apollonius: 2 2 2 y + z + ky − zk2 . 2 kx − yk + kx − zk = 4 x − 2 Nhận xét 1.1.12. (ý nghĩa của đẳng thức hình bình hành) (1) Đẳng thức trên nói lên một tính chất hình học: Tổng bình phương các cạnh của hình bình hành bằng tổng bình phương hai đường chéo. (2) Từ định lý trên ta thấy, muốn đưa được tích vô hướng vào một không gian định chuẩn thì không gian này phải thỏa mãn điều kiện hình bình hành. Ngược lại nếu H là một không gian định chuẩn trong đó đẳng thức hình bình hành được thỏa mãn với mọi phần tử thuộc H thì trên H sẽ tồn tại một tích vô hướng h., .i sao cho chuẩn được xác định nhờ tích vô hướng. Điều này được thể hiện qua định lý sau. Định lí 1.1.13. Giả sử (H, ||.||) là một không gian định chuẩn trên R trong đó đẳng thức hình bình hành nghiệm đúng với mọi x, y ∈ H. Nếu đặt 1 2 2 hx, yi = kx + yk − kx − yk , (1.4) 4 thì h., .i là một tích vô hướng trên H và ta có hx, xi = kxk2 .
10 Chứng minh. Ta chứng minh h., .i xác định như trên thỏa mãn các điều kiện trong định nghĩa về tích vô hướng. Thật vậy, các điều kiện (1) và (4) trong Định nghĩa 1.1.2 hiển nhiên được thỏa mãn. Đặt 1 2 2 p(x, y) = kx + yk − kx − yk , 4 Để ý rằng, h., .i : H × H −→ R là một hàm liên tục và p(x, 0) = 0, p(−x, y) = −p(x, y) ∀x, y ∈ H. Với mọi x, y, z ∈ H ta có 4 (p(x, z) + p(y, z)) = kx + zk2 − kx − zk2 + ky + zk2 − ky − zk2 x+y ⇔ p(x, z) + p(y, z) = 2p ,z . (1.5) 2 Trong đẳng thức (1.5) lấy y = 0 được x p(x, z) = 2p ,z . (1.6) 2 Như vậy ta có x+y 2p ,z = p(x + y, z). 2 Nghĩa là p(x, z) + p(y, z) = p(x + y, z). Vậy điều kiện (2) trong Định nghĩa 1.1.2 được chứng minh. Thay thế x bằng 2x trong (1.6) ta được 2p(x, z) = p(2x, z), ∀x, y, z ∈ H. Bằng quy nạp ta kiểm tra được p(nx, z) = np(x, z), ∀n ∈ N và bằng lập luận như trên ta có p(rx, z) = rp(x, z), ∀r ∈ Qvàx, z ∈ H.
11 Nhờ tính liên tục của chuẩn ||.|| suy ra hàm p(., z) liên tục, qua giới hạn ta có p(ax, z) = ap(x, z) ∀x, z ∈ H và a ∈ R. Vậy p(x, y) là một tích vô hướng trên H và hiển nhiên hx, xi = p(x, x) = kxk2 . Định lý được chứng minh. Định nghĩa 1.1.14. Trong không gian Hilbert H (i) Dãy {xn }∞ n=1 được gọi là hội tụ yếu đến phần tử x ∈ H nếu lim hxn , yi = hx, yi ∀y ∈ H. n→∞ (ii) Dãy {xn }∞ n=1 được gọi là hội tụ mạnh đến x ∈ H nếu lim kxn − xk = 0. n→∞ Ký hiệu xn * x chỉ sự hội tụ yếu, xn → x chỉ sự hội tụ mạnh của dãy {xn } đến phần tử x ∈ H. Chú ý 1.1.15. (1) Trong không gian Hilbert H, hội tụ mạnh kéo theo hội tụ yếu, nhưng điều ngược lại không đúng. (2) Mọi không gian Hilbert đều có tính chất Kadec–Klee, tức là nếu dãy {xn } trong không gian Hilbert H thỏa mãn các điều kiện kxn k → kxk và xn * x, thì xn → x khi n → ∞. Chứng minh. Thật vậy, trong không gian Hilbert nếu xn * x0 và kxn k → kx0 k thì xn → x0 . Với mọi x, ta có kxn − x0 k2 = hxn − x0 , xn − x0 i
12 = kxn k2 − hx0 , xn i − hxn , x0 i + kx0 k2 . Từ giả thiết suy ra lim kxn k2 = kx0 k2 , lim hxn , x0 i = kx0 k2 , lim hx0 , xn i = kx0 k2 . x→∞ x→∞ x→∞ Do đó lim kxn − x0 k2 = kx0 k2 . x→∞ Đó là điều phải chứng minh. b) Toán tử đơn điệu trong không gian Hilbert Định nghĩa 1.1.16. Cho hai không gian tuyến tính X và Y . Một ánh xạ A : X → Y được gọi là ánh xạ tuyến tính hay toán tử tuyến tính nếu: (i) A(x1 + x2 ) = Ax1 + Ax2 với mọi x1 , x2 ∈ X; (ii) A(αx) = αAx với mọi x ∈ X và mọi α ∈ R. Chú ý 1.1.17. (1) Điều kiện (i) và (ii) trong Định nghĩa 1.1.16 tương đương với: A(α1 x1 + α2 x2 + ... + αk xk ) = α1 Ax1 + α2 Ax2 + ... + αk Axk với mọi xi ∈ X với mọi αi ∈ R, i = 1, . . . , k. (2) Nếu Y ≡ X thì ta cũng nói A là toán tử trong X. Ký hiệu R(A) là miền giá trị của toán tử A, tức là tập hợp các phần tử y ∈ Y sao cho y = Ax với một x ∈ X nào đó. Nếu y1 , y2 ∈ R(A) thì α1 y1 + α2 y2 ∈ R(A) với mọi α1 , α2 ∈ R nên R(A) là một không gian con của Y .
13 Định nghĩa 1.1.18. Một toán tử A từ X vào Y là liên tục khi và chỉ khi nó bị chặn (giới nội), nghĩa là tồn tại một hằng số dương K sao cho: kAxk ≤ K kxk ∀x ∈ X. Định nghĩa 1.1.19. Một toán tử A từ X vào Y được gọi là bị chặn (giới nội) nếu có một hằng số K > 0 sao cho: kAxk kAk = sup = sup kAxk ≤ K. x6=0 kxk x6=0 Ký hiệu mặt cầu tâm a bán kính r > 0 trong không gian X là S(a, r), nghĩa là S(a, r) = {x ∈ X : kx − ak = r}. Hệ quả 1.1.20. Toán tử tuyến tính A bị chặn (liên tục) nếu tập các trị của nó trên một mặt cầu (tùy ý) bị chặn. Chứng minh. Thật vậy, giả sử kAxk ≤ N với mọi x ∈ S(x0 , α). Khi đó, với mọi x mà kxk = 1 thì αx + x0 ∈ S, cho nên A(αx + x0 ) ≤ N , và do đó kAαx + Ax0 k ≤ N hay α kAxk ≤ N + kAx0 k . Từ đó suy ra kAxk ≤ (N + kAx0 k)/α. Vậy theo Định nghĩa 1.1.19 ta có: kAxk sup = sup kAxk ≤ K, x6=0 kxk x6=0 với K = (N + kAx0 k)/α. Ví dụ 4. Toán tử A : L2 [0, 1] → L2 [0, 1] xác định bởi Z 1 (Ax)(t) = x(s)ds, t ∈ [0, 1] 0
14 là toán tử tuyến tính liên tục. Thật vậy, áp dụng bất đẳng thức Bunhiacopxki ta có t 2  0 2 Z Z Z1 x(s)ds ≤  |x(s)| ds ≤ |x(s)|2 ds = kxk2 , 0 0 0 với mọi t ∈ [0, 1]. Suy ra, A bị chặn. Do đó
2 Z1