Đăng ký Đăng nhập
Trang chủ MỘT SỐ PHƯƠNG PHÁP HIỆU CHỈNH GIẢI HỆ PHƯƠNG TRÌNH TOÁN TỬ...

Tài liệu MỘT SỐ PHƯƠNG PHÁP HIỆU CHỈNH GIẢI HỆ PHƯƠNG TRÌNH TOÁN TỬ

.PDF
53
128
115

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐẶNG VĂN HIẾU MỘT SỐ PHƯƠNG PHÁP HIỆU CHỈNH GIẢI HỆ PHƯƠNG TRÌNH TOÁN TỬ LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐẶNG VĂN HIẾU MỘT SỐ PHƯƠNG PHÁP HIỆU CHỈNH GIẢI HỆ PHƯƠNG TRÌNH TOÁN TỬ Chuyên ngành: Toán học tính toán Mã số: 604630 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: GS.TSKH Phạm Kỳ Anh Hà Nội - 2011 LỜI CẢM ƠN Để hoàn thành bản luận văn này tôi đã nhận được sự giúp đỡ to lớn của các Thầy, Cô giáo, gia đình và bạn bè xung quanh. Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy giáo hướng dẫn GS.TSKH Phạm Kỳ Anh, Khoa Toán - Cơ - Tin học, Trường đại học khoa học tự nhiên, ĐHQG Hà Nội. Trong quá trình giảng dạy cũng như hướng dẫn, thầy đã ân cần, động viên, giúp đỡ chỉ bảo tận tình cho tôi. Tôi cũng gửi lời cảm ơn tới các Thầy, Cô trong Khoa Toán - Cơ - Tin học, Phòng sau đại học, Trường Đại học khoa học tự nhiên, ĐHQG Hà Nội đã dạy dỗ, giúp đỡ tôi trong suốt quá trình học tập, đặc biệt là các Thầy, Cô trong Seminar của Bộ môn Toán học tính toán đã có những ý kiến đóng góp quý báu giúp cho bản luận văn hoàn chỉnh hơn. Ngoài ra tôi cũng xin gửi lời cảm ơn tới các bạn đồng nghiệp đã giúp đỡ, động viên tôi trong quá trình thực hiện luận văn này. Cuối cùng, tôi xin gửi lời cảm ơn tới gia đình đã sinh thành, nuôi dưỡng và động viên tôi rất nhiều trong thời gian qua. Dù đã cố gắng hết sức nhưng luận văn không thể tránh khỏi những thiếu sót. Mọi ý kiến đóng góp tôi xin được đón nhận với lòng biết ơn chân thành. Hà Nội, ngày 23 tháng 11 năm 2011 Học Viên Đặng Văn Hiếu 1 MỞ ĐẦU Nhiều bài toán khoa học kĩ thuật dẫn đến việc giải phương trình F(x) = y, trong đó F : X → Y là toán tử (tuyến tính hoặc phi tuyến), X,Y là các không gian Banach. Bài toán trên được gọi là đặt chỉnh, nếu 1. Phương trình luôn có nghiệm duy nhất với mọi y ∈ Y . 2. Nghiệm phụ thuộc liên tục vào các dữ liệu F, y. Khi đó ta có nhiều phương pháp giải bài toán trên. Tuy nhiên trong thực tế không phải lúc nào bài toán cũng đặt chỉnh, tức là 1. Tồn lại y ∈ Y để phương trình vô nghiệm hoặc có nhiều hơn một nghiệm. 2. Nghiệm không phụ thuộc liên tục vào các dữ liệu F, y. Các bài toán đặt không chỉnh rất khó giải do có sai số của dữ liệu và phải tính toán gần đúng trên máy tính. Khi đó ta cần có chiến lược hiệu chỉnh để giải bài toán trên. Nói nôm na, ta sẽ thay bài toán đặt không chỉnh bằng một họ các bài toán đặt chỉnh phụ thuộc tham số mà nghiệm của chúng hội tụ đến nghiệm của bài toán đặt không chỉnh khi tham số hiệu chỉnh dần tới không. Trong các bài toán nhận dạng đa tham số, ta phải xác định x, khi biết các dữ liệu gần đúng yδi của yi , tức là phải giải hệ phương trình (thông thường là đặt không chỉnh) Fi (x) = yδi , i = 1, ..., l. Nếu xem yδ như là một véc tơ yδ = (yδ1 , yδ2 , ..., yδl ), với yδi ∈ Yi , δ như là một véctơ nhiễu δ = (δ1 , δ2 , ..., δl )T ∈ Rl (mức nhiễu) thì hệ phương trình toán tử trên đưa về một phương trình toán tử trong không gian tích F(x) = yδ . 4 Trong nhiều trường hợp việc xét hệ phương trình thay cho một phương trình trong không gian tích với bộ tham số hiệu chỉnh cho kết quả khả quan. Sau đây là hai ví dụ đưa về hệ phương trình toán tử đặt không chỉnh. Ví dụ 1. (Bài toán khôi phục hệ số của phương trình từ ánh xạ Dirichlet Neumann) Ứơc lượng hệ số q ≥ 0 từ phương trình vi phân riêng −∆u + qu = 0, x ∈ Ω ⊂ Rd , ∂u trên biên ∂ Ω của Ω. Giả sử biết trước p ∂v các giá trị Dirichlet của u trên biên ∂ Ω là f0, f1 , . . . , f p−1 và đo đạc được các ∂ ui trên biên ∂ Ω tương ứng. Khi đó ta viết lại bài toán giá trị Neumann gi = ∂v với điều kiện biên Neumann g = Fi (q) = gi , i = 0, ..., p − 1, trong đó Fi : D(Fi ) ⊂ L2 (Ω) → H −1/2 (∂ Ω) là toán tử phi tuyến ánh xạ q tới ∂ ui , ui ∈ H 1 (Ω) là nghiệm yếu của hệ ∂v  −∆u + qu = 0, x ∈ Ω ⊂ Rd i i ui = fi , x ∈ ∂ Ω. Bài toán ước lượng q ≥ 0 từ hệ trên là đặt không chỉnh (xem [5]). Ví dụ 2. (Bài toán ước lượng mômen phi tuyến). Bài toán ước lượng mômen phi tuyến là tìm hàm u ∈ L2 (Ω) trên miền bị chặn Ω ⊂ Rd thỏa mãn hệ phương trình tích phân phi tuyến gi = Z Ω ki (x, u(x))dx ∈ Rm , i = 1, ..., p, với các nhân trơn ki : Ω × R → Rm và các véctơ gi cho trước (i = 1, ..., p). Ta đưa về bài toán Fi (u) = gi , i = 1, ..., p, trong đó Fi : L2 (Ω) → Rm là toán tử phi tuyến đưa u vào cũng là bài toán đặt không chỉnh (xem [5]). 5 R Ω ki (x, u(x))dx. Đây Đã có nhiều phương pháp giải hệ phương trình toán tử đặt không chỉnh. Ngoài các phương pháp lặp xoay vòng như Landweber - Kaczmarz, Newton Kaczmarz, đường dốc Kaczmarz, một nhóm các nhà khoa học tại Trường Đại học khoa học tự nhiên, ĐHQG Hà Nội đã đề xuất các phương pháp chỉnh lặp song song: Newton hiệu chỉnh song song, Gauss - Newton hiệu chỉnh song song, phương pháp chiếu điểm gần kề song song, phương pháp CQ - song song giải hệ phương trình toán tử. Đăc điểm của các phương pháp này là hai quá trình hiệu chỉnh và phân rã song song được thực hiện đồng thời và tương thích với nhau. Luận văn này sẽ trình bày ba phương pháp giải hệ phương trình toán tử đặt không chỉnh: Phương pháp cực tiểu phiếm hàm ổn định với hạn chế độ lệch trong mức sai số cho phép. Phương pháp cực tiểu phiếm hàm làm trơn Tikhonov và phương pháp Gauss - Newton hiệu chỉnh song song. Nội dung chính của bản luận văn bao gồm các vấn đề sau đây: 1. Thiết lập tính đặt chỉnh của bài toán tối ưu có ràng buộc liên kết với hệ phương trình toán tử đặt không chỉnh. 2. Đánh giá tốc độ hội tụ của phương pháp hiệu chỉnh đa tham số trong trường hợp tổng quát. 3. Thiết lập mối liên hệ giữa phương pháp nhân tử Lagrange và phương pháp hiệu chỉnh đa tham số. 4. Nghiên cứu phương pháp hiệu chỉnh đa tham số Tikhonov và đánh giá tốc độ hội tụ. 5. Trình bày phương pháp chỉnh lặp song song dạng Gauss - Newton. Các vấn đề 1 − 3 được trình bày trong bài báo của Torsten Hein [2]. Phần 5 được nghiên cứu trong công trình của Phạm Kỳ Anh và Vũ Tiến Dũng [1]. Phần 4 là các kết quả do học viên phát triển dựa theo tài liệu của Torsten Hein [2], Nguyễn Bường và Nguyễn Đình Dũng [3]. 6 Chương 1 Hiệu chỉnh đa tham số - sự hội tụ và tốc độ hội tụ Trong chương này, chúng tôi đề cập tới phương pháp hiệu chỉnh đa tham số do Torsten đề xuất dựa trên việc cực tiểu phiếm hàm ổn định với điều kiện độ lệch của các phương trình nằm trong giới hạn sai số cho phép, bao gồm các bổ đề về tính ổn định và định lý về tốc độ hội tụ. Cuối chương, chúng tôi giới thiệu hai thuật toán giải bài toán tối ưu và mối liên hệ giữa phương pháp hiệu chỉnh đa tham số và phương pháp nhân tử Lagrange. Nội dung chính của chương được trình bày theo dựa theo tài liệu [2]. 1.1 Đặt bài toán Cho X,Y j , ( j = 1, ..., l) là các không gian Banach phản xạ. Để đơn giản, chuẩn trong các không gian X,Y j cùng được kí hiệu là k.k. Fj : D(Fj ) ⊂ X → Y j ( j = T 1, ..., l) nói chung là các toán tử phi tuyến. Đặt D = lj=1 D(Fj ), giả sử D 6= ∅. Nếu vế phải cho là chính xác ta có hệ sau Fj (x) = y j ( j = 1, ..., l), x ∈ D. (1.1.1) Tuy nhiên dữ liệu y j thường bị nhiễu bởi yδj : ||yδj − y j || ≤ δ j khi đó ta chỉ có phương trình ( j = 1, ..., l), x ∈ D. (1.1.2) Fj (x) = yδj 7 Trong ứng dụng thì bài toán (1.1.2) thường là bài toán đặt không chỉnh. Ngay cả khi các hệ (1.1.1) và (1.1.2) giải được duy nhất thì nghiệm của (1.1.2) cũng không chắc phụ thuộc liên tục vào dữ liệu. Nghĩa là nếu x† là nghiệm duy nhất của (1.1.1) và xδ là nghiệm duy nhất của (1.1.2) thì ||x† − xδ || có thể lớn tùy ý khi δ j ( j = 1, ..., l) đủ nhỏ. Chiến lược hiệu chỉnh. Xét phiếm hàm ổn định J : D ⊂ X → R mà tính chất của nó được liệt kê trong mục 1.2 và thay (1.1.2) bởi bài toán tối ưu có ràng buộc sau  J(x) → min x∈ D (1.1.3)  F (x) − yδ j j ≤ δ j , j = 1, ..., l. Trong lý thuyết hiệu chỉnh Tikhonov, ta thay (1.1.2) bằng bài toán cực tiểu phiếm hàm 2 l δ (1.1.4) ∑ λ j Fj (x) − y j + J (x) → min, Yj j=1 x∈D trong đó λ j > 0( j = 1, ..., l) là các tham số hiệu chỉnh. Khi dùng phương pháp Lagrange để giải bài toán (1.1.3) ta có thể xem các tham số λ j > 0( j = 1, ..., l) như các nhân tử Lagrange. Các hằng số α j = 1 , ( j = 1, ..., l) đóng vai trò các tham số hiệu chỉnh trong phương pháp hiệu λj chỉnh đa tham số. 1.2 Các kết quả về tính ổn định Ta sẽ chỉ ra tính đặt chỉnh của bài toán (1.1.3). Cụ thể ta sẽ thiết lập một số điều kiện để bài toán (1.1.3) có nghiệm duy nhất xδ phụ thuộc liên tục vào các dữ liệu yδj , j = 1, ..., l. Ta sẽ chỉ ra rằng cách tiếp cận bài toán (1.1.3) cũng gần giống như việc chứng minh sự tồn tại, tính ổn định và hội tụ của điểm cực tiểu xδα của phiếm hàm Tikhonov 2 δ F(x) − y + α J(x), Y 8 (1.2.1) ở đây J(x) = ||x − x∗ | |2 hoặc J(x) = ||D(x − x∗ )| |2 , trong đó D là toán tử tuyến tính đóng. Sau đây là một số giả thiết đối với toán tử Fj , ( j = 1, ..., l) và phiếm hàm ổn định J(x): A1. Với dữ liệu chính xác thì hệ (1.1.1) có nghiệm x† , tức là Fj (x† ) = y j , ( j = 1, ..., l). A2. Fj , ( j = 1, ..., l) là các toán tử liên tục và đóng yếu (xn ∈ D(Fj ), xn ⇀ x, Fj (xn ) ⇀ y j thì x ∈ D(Fj ) và Fj (x) = y j ). A3. Phiếm hàm J : D ⊂ X → R không âm và nửa liên tục dưới yếu (xn ⇀ x thì J(x) ≤ lim (inf J(xn ))). n→∞ A4. Tập A(C) := ( x ∈ X : J(x) + ∑ Fj (x) ≤ C l j=1 ) bị chặn trong X với mọi C ≥ 0. A5. Nếu xn ⇀ x và J(xn ) → J(x) thì xn → x. Nhận xét. Giả thiết A1 là một giả thiết tự nhiên đối với bài toán nhận dạng, tức là nếu có quan sát chính xác y j , ( j = 1, ..., l) thì ta có thể giả thiết có bộ "tham số" x† ∈ D thỏa mãn hệ (1.1.1). Nhưng điều này có thể không còn đúng khi dữ liệu bị nhiễu yδj , ( j = 1, ..., l). Tức là nghiệm của (1.1.2) có thể không tồn tại. Kí hiệu   (1.2.2) Mδ = x ∈ X : Fj (x) − yδj ≤ δ j , ( j = 1, ..., l) Yj là tập các phần tử chấp nhận được. Vì x† ∈ Mδ , ∀δ ≥ 0 nên Mδ 6= Ø. Ngoài ra vì Fj liên tục nên Mδ là tập đóng. Bây giờ ta chứng minh sự tồn tại nghiệm xδ của (1.1.3). Bổ đề 1.2.1. Với các điều kiện (A1) − (A4) thì luôn tồn tại nghiệm xδ của (1.1.3). 9 Chứng minh. Giả sử {xn } ⊂ Mδ là dãy cực tiểu sao cho: J(xn+1 ) ≤ J(xn ) và lim J(xn ) = inf J(x). Ta có: J(xn ) ≤ J(x0 ), ∀n ≥ 0. n→∞ Từ (1.2.2) ta có x∈D δ Fj (xn ) ≤ y y j + 2δ j , j = 1, ..., l. δ ≤ + j j l  Đặt C := J(x0 ) + ∑ y j + 2δ j . j=1 Suy ra xn ∈ A(C). Do đó {(xn , F1 (xn ) , ..., Fl (xn )}n là bị chặn trong không gian Banach phản xạ X ×Y1 × ... ×Yl . Suy ra, tồn tại dãy {xnk } sao cho xnk ⇀ x và Fj (xnk ) ⇀ ybj , (1 ≤ j ≤ l). Theo (A2) thì Fj (x) = ybj và ta có Fj (xnk ) − yδj ⇀ ybj − yδj = Fj (x) − yδj , Theo tính nửa liên tục dưới yếu của chuẩn,suy ra δ δ Fj (x) − y j ≤ lim inf F (xnk ) − y j ≤ δ j , (1 ≤ j ≤ l) , k→∞ chứng tỏ x ∈ Mδ . Theo (A3) và xnk ⇀ x suy ra J (x) ≤ lim inf J (xnk ). Từ đó x là nghiệm của k→∞ (1.1.3).⊠ (n) (n) Bổ đề 1.2.2. Cho các điều kiện (A1)−(A4). Hơn nữa {y j } với y j − yδj ≤ (n) (n) (n) c j , c j → 0 (n → ∞) . Gọi {xδn } là dãy nghiệm của (1.1.3) ứng với yδj = y j (n) và δ j + c j . Khi đó 1. Tồn tại dãy con {xδnk } ⇀ xδ là nghiệm của (1.1.3). 2. Nếu xδ là nghiệm duy nhất thì xδn ⇀ xδ . 10 Chứng minh 1. Với mỗi n ∈ N, đặt (n) (n) Mδ = {x ∈ X : Fj (x) − ynj ≤ δ j + 2c j , ( j = 1, ..., l)}, suy ra xδ ∈ Mδ ∀n và Mδ → Mδ , (Mδ ⊂ Mδ ). Do đó ∀n. (∗) J(xδn ) ≤ J(xδ ) (n) (n) (n) Như lập luận trong Bổ đề 1.2.1.,tồn tại dãy {xδnk } sao cho xδnk ⇀ x ∈ Mδ , suy ra J(xδ ) ≤ J(x) ≤ lim inf J(xδnk ) ≤ J(xδ ), (**) J(x) = J(xδ ). k→∞ Do đó Vậy x là nghiệm của (1.1.3). 2. Nếu bài toán (1.1.3) có nghiệm duy nhất xδ thì x = xδ , từ đó suy ra sự hội tụ yếu của dãy {xδn } về xδ . ⊠ Bổ đề 1.2.3. Giả sử có các giả thiết của Bổ đề 1.2.2. Nếu thêm điều kiện (A5) thì {xδn } hội tụ mạnh về xδ . Chứng minh. Hiển nhiên từ (*) và (**) cùng với xδn ⇀ xδ , suy ra lim J(xδn ) = J(xδ ). Kết hợp với (A5) ta có ngay điều phải chứng minh.⊠ n→∞ Cuối cùng chúng ta muốn chứng minh sự hội tụ của nghiệm của (1.1.3) tới nghiệm x† của (1.1.1) khi δ j → 0, (1 ≤ j ≤ l). Định nghĩa 1.2.1. x† được gọi là nghiệm J − min của (1.1.1) nếu J(x† ) = min{J(x) : Fj (x) = y j , 1 ≤ j ≤ l}. Từ Bổ đề 1.2.1. và 1.2.3. suy ra xδ hội tụ tới nghiệm J − min của hệ (1.1.1) (n) khi δ → 0. Nếu thay δ j + c j bởi δ j và yδj bởi y j và lặp lại chứng minh của Bổ đề 1.2.2., ta thu được kết quả sau. Bổ đề 1.2.4. Cho các điều kiện (A1) − (A4) và δ j → 0, tức là (yδj → y j , 1 ≤ j ≤ l). Nếu xδ là nghiệm của (1.1.3) thì tồn tại dãy con {b xδ } hội tụ yếu tới nghiệm J − min x† của (1.1.1). Hơn nữa, nếu nghiệm J − min x† là duy nhất thì xδ ⇀ x† . Nếu thêm điều kiện (A5) thì xδ → x† . 11 1.3 Tốc độ hội tụ Định nghĩa 1.3.1. Giả sử J là hàm lồi và khả vi Fréchet với J ′ (x) ∈ X ∗ , ∀x ∈ D. Khoảng cách Bregman giữa xb, x ∈ D là D(b x, x) xác định bởi D(b x, x) := J(b x) − J(x)− < J ′ (x), xb− x >X ∗ ,X , trong đó < ., . >X ∗ ,X là tích đối ngẫu trong X. Sau này, để đơn giản, ta sẽ bỏ các kí tự X ∗ , X trong tích đối ngẫu. Nhận xét. Từ tính lồi của hàm J(x) suy ra D(b x, x) ≥ 0. Nếu J(x) lồi chặt thì D(b x, x) > 0, ∀b x 6= x. Trước khi nghiên cứu tốc độ hội tụ của phương pháp hiệu chỉnh đa tham số ta xét thêm điều kiện sau A6. ∃γ : 0 ≤ γ < 1 và β = (β1 , β2, ..., βl )T ∈ Rl với β j ≥ 0, ( j = 1, ..., l) thỏa mãn D E l ′ † † † † J (x ), x − x ≤ γ D(x, x ) + ∑ β j Fj (x) − Fj (x ) (1.3.1) j=1  ∀x ∈ Br (x† ) ∩ D với Br (x† ) = x ∈ X : x − x† < r , r > 0 đủ lớn. Điều kiện A6 rất tổng quát và bao gồm các điều kiện nguồn, điều kiện nón pháp tuyến vv... đó Định lý 1.3.1. Giả sử có các giả thiết (A1) − (A6); δ := (δ1 , ..., δl )T , khi 2 D(x , x ) ≤ β kδ k2, 2 1−γ δ † trong đó k.k2 là chuẩn Euclid trong Rl . Chứng minh. Do x† ∈ Mδ ∀δ ≥ 0 nên J(xδ ) ≤ J(x† ). Ta có D E δ † δ † ′ † δ † D(x , x ) = J(x ) − J(x ) − J (x ), x − x , suy ra D E ′ † δ † D(x , x ) ≤ J (x ), x − x . δ † 12 (1.3.2) Theo (A6), ta suy ra D(xδ , x† ) ≤ γ D(xδ , x† ) + † δ ∑ β j Fj (x ) − Fj (x ) l j=1 o n l δ † δ δ δ ≤ γ D(x , x ) + ∑ β j Fj (x ) − y j + y j − y j j=1 ≤ γ D(xδ , x† ) + 2 l ∑ β jδ j † δ ≤ γ D(x , x ) + 2 β kδ k2 j=1 2 Do đó 2 D(x , x ) ≤ β kδ k2 .⊠ 1−γ 2 δ † Nhận xét. Để thiết lập tốc độ hội tụ trong X ta cần đặt thêm điều kiện lên các toán tử Fj hoặc/và hàm J(x). Chẳng hạn giả sử J(x) là hàm lồi mạnh với hệ số η > 0, tức là η J(tx + (1 − t)y) ≤ tJ(x) + (1 − t)J(y) − t(1 − t) kx − yk2 , ∀t ∈ [0; 1]. 2 Suy ra kx − yk2 ≤ η2 D(x, y) = C.D(x, y) với C = η2 . Từ đây kết hợp với (1.3.2) ta có 2 2C δ † δ + x − x ≤ C.D(x , x ) ≤ β . kδ k2 . 1−γ X 2 Từ đó ta có đánh giá tốc độ hội tụ trong X. Mặt khác nếu J(x) = kx − x∗ k2 thì D(b x, x) = kb x − xk2 . 2 δ 2 † † δ Từ (1.3.2), ta được x − x = D(x , x ) ≤ 1−γ β . kδ k2. 2 Ta xét một số trường hợp đặc biệt của giả thiết (A6). Giả thiết này đạt được nếu ta có điều kiện nguồn sau ′ † J (x ) = l ∑ G∗j w j , w j ∈ Y j∗, (1 ≤ j ≤ l), (1.3.3) j=1 trong đó G j ∈ L(X,Y j ) là xấp xỉ tuyến tính của Fj với phần dư là r j (x, x† ) := Fj (x) − Fj (x† ) − G j (x − x† ). 13 (1.3.4) Sau đây là 3 ví dụ điển hình. Hệ quả 1.3.1. Giả sử (1.3.3) thỏa mãn với l r j (x, x† ) ≤ C j .D(x, x† ) và C := ∑ w j ∗ .C j < 1 Y j j=1 thì điều kiện (A6) nghiệm đúng với γ = C và β j = w j Y ∗ , 1 ≤ j ≤ l. j Chứng minh. Ta có J ′ (x† ), x − x† D E ∗ † = ∑ G j w j, x − x l X ∗ ,X X ∗ ,X j=1 l = ∑ w j , G j (x − x† ) Y ∗ ,Y j j j=1 l ≤ ∑ w j Y ∗ G j (x − x† ) j=1 j Yj l  ≤ ∑ w j Y ∗ Fj (x) − Fj (x† ) + r j (x, x† ) j=1 j ≤ ∑ w j Y ∗ Fj (x) − Fj (x† ) + l j=1 ! ∑ w j Y ∗C j D(x, x† ) l j j=1 Từ đó suy ra điều phải chứng minh. ⊠ j Nhận xét. Nếu J(x) = kx − x∗ k2 và Fj khả vi Fréchet thì các giả thiết của Hệ quả 1.3.1 giống các giả thiết trong phương pháp hiệu chỉnh Tikhonov, trong đó G j = F ′ (x† ) : X → Y j là liên tục Lipschitz. Điều này chứng tỏ (1.3.1) là khái quát hóa của các giả thiết quen biết để chứng minh tốc độ hội tụ. Mặt khác tính liên tục Lipschitz của đạo hàm Fréchet không phải là điều kiện cần để phương pháp hiệu chỉnh hội tụ. Do đó nó có thể được thay bởi các giả thiết khác. Hệ quả 1.3.2. Giả sử (1.3.3) thỏa mãn với † † r j (x, x ) ≤ C j Fj (x) − Fj (x ) , 1 ≤ j ≤ l Yj Yj 14 thì điều kiện (A6) nghiệm đúng với γ = 0 và β j = w j Y ∗ (C j + 1), 1 ≤ j ≤ l. j Chứng minh. Như trên ta có J ′ (x† ), x − x† X ∗ ,X l  ≤ ∑ w j Y ∗ . Fj (x) − Fj (x† ) + r j (x, x† ) j=1 j l  ≤ ∑ w j Y ∗ C j + 1 Fj (x) − Fj (x† ) j=1 j Từ đó suy ra điều phải chứng minh. ⊠ Hệ quả 1.3.3. Giả sử (1.3.3) thỏa mãn với † † r j (x, x ) ≤ C j G j (x − x ) , 1 ≤ j ≤ l Yj Yj với C j < 1 thì điều kiện (A6) nghiệm đúng với γ = 0 và β j = w j Y ∗ (1 − Cj )−1 , 1 ≤ j j ≤ l. Chứng minh. Ta có r j (x, x† ) := Fj (x) − Fj (x† ) − G j (x − x† ). Suy ra † † † † † G(x − x ) − r j (x, x ) ≤ Fj (x) − Fj (x ) ≤ G(x − x ) + r j (x, x ) . Do đó † † † (1 −C j ) G(x − x ) ≤ Fj (x) − Fj (x ) ≤ (1 +C j ) G(x − x ) . Theo cách chứng minh của hệ quả (1.3.1) ta có J ′ (x† ), x − x† X ∗ ,X l ≤ ∑ w j Y ∗ . G j (x − x† ) j=1 j Yj kw j kY ∗ ≤ ∑ 1−C j j Fj (x) − Fj (x† ) l j=1 Từ đó suy ra điều phải chứng minh.⊠ 15 1.4 Hiệu chỉnh đa tham số trong không gian Hilbert Ta xét bài toán (1.1.3) với X,Y j là các không gian Hilbert. Giả sử J(x) := kP(x)k2 trong đó P : X → Z là toán tử phi tuyến. Ta sử dụng phương pháp nhân tử Lagrange giải bài toán (1.1.3). Xét hàm Lagrange 2 δ L(x, λ ) := J(x) + ∑ λ j ( Fj (x) − y j − δ j2), l Yj j=1 (1.4.1) hoặc hàm Tikhonov 2 l δ c Tλ (x) := J(x) + ∑ λ j Fj (x) − y j . j=1 Yj (1.4.2) Ta có thuật toán tìm nghiệm của bài toán (1.1.3) như sau [16] Thuật toán 1 1. Cho xδ0 ∈ X, λ (0) = (λ1 , ..., λl ) ≥ 0; k := 0. (0) (0) 2. Tìm nghiệm xδk+1 của bài toán Td λ (k) (x) → min. 3. Đặt  ν  δ δ  Fj (xk+1 ) − y j  (k+1) (k) , ε  , ( j = 1, ..., l) (0 < ε << 1) , λj := λ j max  δ jν (1.4.3) với ν > 0 cố định bất kì. (k+1) (k) 4. Nếu λ − λ < T OL thì dừng thuật toán, ngược lại đặt k := k + 1 và quay lại bước 2. Định lý 1.4.1. Nếu λ (k) → λ và xδk → xδ ∈ D ⊂ X khi k → ∞ thì (xδ , λ ) ∈ X × Rl là điểm yên ngựa của hàm Lagrange (1.4.1) và do đó xδ là nghiệm của (1.1.3). Trước khi đi vào chứng minh định lý 1.4.1 ta có bổ đề sau 16 Bổ đề 1.4.2. Cặp (xδ , λ ) ∈ D × Rl+ là điểm yên ngựa của hàm Lagrange (1.4.1) ứng với bài toán (1.1.3) nếu x = xδ làm cực tiểu phiếm hàm Tikhonov (1.4.2) ứng với tham số hiệu chỉnh λ = λ và thỏa mãn 2 δ δ λ j ( Fj (x ) − y j − δ j2) = 0 j = 1, ..., l, (1.4.4) và thêm điều kiện 2 δ δ Fj (x ) − y j ≤ δ j2 nếu λ j = 0 j = 1, ..., l. (1.4.5) Chứng minh. Theo định nghĩa điểm yên ngựa ta có L(xδ , λ ) ≤ L(xδ , λ ) ≤ L(x, λ ) ∀x ∈ D, ∀λ ∈ Rl+ . Bất đẳng thức thứ hai tương với     2 2   l l 2 2 J xδ + ∑ λ j Fj (xδ ) − yδj − δ j ≤ J (x)+ ∑ λ j Fj (x) − yδj − δ j , j=1 j=1   δ c c hay Tλ xδ ≤ T λ (x) ∀x ∈ D . Điều này đúng theo giả thiết x làm cực tiểu phiếm hàm Tikhonov (1.4.2). Bất đẳng thức thứ nhất tương đương với   2 l  2 δ δ ∑ λ j − λ j Fj (x ) − y j − δ j ≥ 0 j=1 ∀λ ∈ Rl+ . Do giả thiết (1.4.4) và (1.4.5) nên bất đẳng thức cuối này luôn đúng. Vậy Bổ đề 1.4.2 được chứng minh. ⊠ Bây giờ ta đi chứng minh Định lý 1.4.1. Ta kiểm tra các giả thiết của Bổ đề 1.4.2. Theo cách xây dựng cácdãy{λ k } và {xδk } thì các giới hạn λ và xδ của phép lặp (1.4.3) thỏa mãn Tbλ xδ ≤ Tbλ (x) với mọi x ∈ D, tức là xδ làm cực tiểu phiếm hàm Tikhonov (1.4.2) ứng với λ = λ . Hơn nữa cặp (xδ , λ ) thỏa mãn    ν    Fj xδ − yδj   λ j = λ j max , ε , 1 ≤ j ≤ l. (1.4.6)   δ jν   17   2 δ δ Do 0 < ε ≪ 1, nên từ (1.4.6) suy ra hoặc λ j = 0 hoặc Fj x − y j = δ j2. Điều này suy ra giả thiết (1.4.4) của Bổ đề 1.4.2. Tiếp tục kiểm tra giả thiết (1.4.5). Giả sử có chỉ số j nào đó sao cho 2   δ δ Fj x − y j > δ j2 và λ j = 0,   ν δ δ tức là Fj x − y j > δ jν và λ j = 0. Khi đó tồn tại k0 = k0 ( j) sao cho   ν δ δ Fj xk − y j > δ jν với mọi k ≥ k0 (do Fj liên tục và tính liên tục của chuẩn). Do đó max    ν  δ δ  Fj xk − y j   δ jν ,ε      > 1. Theo (1.4.3), suy ra λ k+1 > λ kj > 0 với mọi k ≥ k0 . Cho k → ∞, suy ra j λ j = lim λ kj > λ kj0 > 0. Điều này vô lý vì λ j = 0. Vậy giả thiết (1.4.5) thỏa k→∞ mãn. Áp dụng Bổ đề 1.4.2, Định lý 1.4.1 được chứng minh. ⊠ Nhược điểm của thuật toán 1 1. Phải giải bài toán tối ưu phi tuyến trên mỗi bước lặp. 2. Do phép lặp (1.4.3) hội tụ chậm nên cần thực hiện nhiều bước lặp. Sau đây ta trình bày thuật toán lặp Gauss - Newton để tìm nghiệm xấp xỉ của bài toán (1.1.3). Xét bài toán  J(x) = kP(x)k2Z → min x∈ D δ  Fj (x) − y j ≤ δ j , j = 1, ..., l. Ta dựng hàm Tikhonov 2 l δ c Tλ (x) := J(x) + ∑ λ j Fj (x) − y j . j=1 Yj ′ Giả thiết Fj (x) và P(x) là các hàm khả vi Fréchet với các đạo hàm Fj (x) ′ và P (x). Giả sử đã biết xδk , ta đi tìm xδk+1 = xδk + ∆x bằng cách tuyến tính hóa 18       ′ δ δ Fj xk + ∆x ≈ Fj xk + Fj xδk ∆x       ′ δ δ P xk + ∆x ≈ P xk + P xδk ∆x. Ta đưa về bài toán tìm cực tiểu của dạng toàn phương Tbλ (k) (xδk + ∆x) ≈ Φ(∆x) → min ∆x trong đó 2   2 l ′ δ (k) ′ δ δ δ δ Φ(∆x) = P (xk )∆x + P(xk ) + ∑ λ j Fj (xk )∆x − y j − Fj (xk ) . Z Yj j=1 Tìm ∆x là nghiệm của phương trình ∂Φ = 0, tức là ∂ ∆x ′ ′ ∂Φ = 2P ∗ (xδk )P′ (xδk )∆x + 2P ∗ (xδk )P(xδk ) ∂ ∆x  i h ′ l ′ ′∗ (k) δ δ δ δ ∗ δ + 2 ∑ λ j Fj (xk )Fj (xk )∆x + Fj (xk ) y j − Fj (xk ) = 0 j=1 điều này tương đương với " l # P ∗ (xδk )P′ (xδk ) + ∑ λ j Fj ∗ (xδk )Fj (xδk ) ∆x ′ (k) ′ ′ j=1 l = ∑ (k) ′ λ j Fj ∗(xδk ) j=1  yδj  − Fj (xδk ) − P ∗(xδk )P(xδk ). (1.4.7) ′ Khi đó ta có thuật toán 2 1. Cho xδ0 ∈ X, λ (0) = (λ1 , ..., λl ) ≥ 0; k := 0 (0) (0) 2. Giải (1.4.4) tìm ∆x. Đặt xδk+1 = xδk + ∆x. (k+1) (k+1) 3. Tìm λ (k+1) = (λ1 ) theo công thức (1.4.3). , ..., λl (k+1) (k) − λ < T OL1 và k∆xkX < T OL2 thì dừng thuật toán, 4. Nếu λ ngược lại, đặt k := k + 1 và quay lại bước 2. 19 Sự hội tụ của phương pháp chỉnh lặp Gauss - Newton được nghiên cứu trong [7, 8, 9, 10]. Trong chương 3, sẽ trình bày kĩ hơn về phương pháp chỉnh lặp song song Gauss - Newton [1]. 1.5 Mối liên hệ giữa phương pháp nhân tử Lagrange và phương pháp hiệu chỉnh đa tham số Ta sẽ chỉ ra rằng Thuật toán 1 liên quan mật thiết với phương pháp nhân tử Lagrange cho bài toán tối ưu với ràng buộc bất đẳng thức. Cho X là không gian Banach, ta xét bài toán   J(x) → min (1.5.1)  g j (x) ≤ 0, j = 1, ..., l, với hàm mục tiêu J : X → R và các hàm ràng buộc g j : X → R, j = 1, ..., l. Với mỗi nhân tử Lagrange λ = (λ1 , ..., λl )T ∈ Rl , (λ j ≥ 0) và hằng số c > 0, đặt  2  1 l  2 M(x, λ , c) := J(x) + (1.5.2) ∑ max 0, λ j + cg j (x) − λ j . 2c j=1 Sau đây là phương pháp nhân tử Lagrange. Cho λ k ≥ 0; ck > 0. Ta tìm nghiệm xk của bài toán M(x, λ k , ck ) → min, x ∈ X. (1.5.3) Và cập nhật nhân tử Lagrange (k) λ jk+1 := max{0; λ j + ck g j (xk )}, j = 1, ..., l. (1.5.4) Với ck được chọn theo một quy tắc nào đó (thông thường ta chọn là dãy tăng: ck+1 ≥ ck ). Ta có một số thay đổi nhỏ so với bài toán trên là thay tham số đơn c ∈ R bằng véctơ tham số c = (c1 , ..., cl )T ∈ Rl với c j > 0 và thay hàm (1.5.2) bởi  l 2  1  2 max 0, λ j + c j g j (x) − λ j . (1.5.5) M(x, λ , c) := J(x) + ∑ 2c j j=1 20
- Xem thêm -

Tài liệu liên quan