Luận văn Một số phương pháp hiệu chỉnh giải hệ phương trình toán tử

j ∥∥∥G j(x− x†)∥∥∥ Yj ,1≤ j ≤ l với C j < 1 thì điều kiện (A6) nghiệm đúng với γ = 0 và β j = ∥∥w j∥∥Y ∗j (1− C j)−1,1≤ 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∑j=1∥∥w j∥∥Y ∗j .∥∥G j(x− x†)∥∥Yj ≤ l ∑ j=1 ‖w j‖Y∗j 1−C j ∥∥Fj(x)−Fj(x†)∥∥ 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 ,Yj là các không gian Hilbert. Giả sử J(x) := ‖P(x)‖2 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 L(x,λ ) := J(x)+ l ∑ j=1 λ j( ∥∥∥Fj(x)− yδj ∥∥∥2Yj −δ 2j ), (1.4.1) hoặc hàm Tikhonov T̂λ (x) := J(x)+ l ∑ j=1 λ j ∥∥∥Fj(x)− yδj ∥∥∥2Yj . (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) = (λ (0)1 , ...,λ (0)l )≥ 0;k := 0. 2. Tìm nghiệm xδk+1 của bài toán T̂λ (k)(x)→ min. 3. Đặt λ (k+1)j := λ (k) j max  ∥∥∥Fj(xδk+1)− yδj∥∥∥ν δ νj ,ε  ,( j = 1, ..., l)(0 < ε << 1) , (1.4.3) với ν > 0 cố định bất kì. 4. Nếu ∥∥∥λ (k+1)−λ (k)∥∥∥< TOL 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 λ j( ∥∥∥Fj(xδ )− yδj ∥∥∥2−δ 2j ) = 0 j = 1, ..., l, (1.4.4) và thêm điều kiện∥∥∥Fj(xδ )− yδj ∥∥∥2 ≤ δ 2j 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 J ( xδ ) + l ∑ j=1 λ j (∥∥∥Fj(xδ )− yδj ∥∥∥2−δ 2j)≤ J (x)+ l∑ j=1 λ j (∥∥∥Fj(x)− yδj ∥∥∥2−δ 2j), 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 l ∑ j=1 ( λ j−λ j )(∥∥∥Fj(xδ )− yδj ∥∥∥2−δ 2j)≥ 0 ∀λ ∈ 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ác dã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 T̂λ ( xδ ) ≤ T̂λ (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 λ j = λ jmax  ∥∥∥Fj(xδ)− yδj∥∥∥ν δ νj ,ε  ,1≤ j ≤ l. (1.4.6) 17 Do 0< ε ≪ 1, nên từ (1.4.6) suy ra hoặc λ j = 0 hoặc ∥∥∥Fj(xδ)− yδj ∥∥∥2 = δ 2j . Đ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∥∥∥Fj(xδ)− yδj ∥∥∥2 > δ 2j 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(xδk)− 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(xδk)− yδj∥∥∥ν δ νj ,ε > 1. Theo (1.4.3), suy ra λ k+1j > λ kj > 0 với mọi k ≥ k0. Cho k → ∞, suy ra λ j = limk→∞ λ k j > λ k0j > 0. Điều này vô lý vì λ j = 0. Vậy giả thiết (1.4.5) thỏa 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) = ‖P(x)‖ 2 Z →min x∈D∥∥∥Fj(x)− yδj ∥∥∥≤ δ j, j = 1, ..., l. Ta dựng hàm Tikhonov T̂λ (x) := J(x)+ l ∑ j=1 λ j ∥∥∥Fj(x)− yδj ∥∥∥2Yj . Giả thiết Fj(x) và P(x) là các hàm khả vi Fréchet với các đạo hàm F ′ j(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 ( xδk +∆x ) ≈ Fj ( xδk ) +F ′ j ( xδk ) ∆x P ( xδk +∆x ) ≈ P ( xδk ) +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 T̂λ (k)(x δ k +∆x)≈Φ(∆x)→ min∆x trong đó Φ(∆x) = ∥∥∥P′(xδk )∆x+P(xδk )∥∥∥2Z + l∑j=1λ (k)j ∥∥∥F ′j(xδk )∆x−(yδj −Fj(xδk ))∥∥∥2Yj . Tìm ∆x là nghiệm của phương trình ∂Φ∂∆x = 0, tức là ∂Φ ∂∆x = 2P ′∗(xδk )P ′(xδk )∆x+2P ′∗(xδk )P(x δ k ) +2 l ∑ j=1 λ (k)j [ F ′∗ j (x δ k )F ′ j(x δ k )∆x+F ′∗ j (x δ k ) ( yδj −Fj(xδk ) )] = 0 điều này tương đương với[ P ′∗(xδk )P ′(xδk )+ l ∑ j=1 λ (k)j F ′∗ j (x δ k )F ′ j(x δ k ) ] ∆x = l ∑ j=1 λ (k)j F ′∗ j (x δ k ) ( 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) = (λ (0)1 , ...,λ (0) l )≥ 0;k := 0 2. Giải (1.4.4) tìm ∆x. Đặt xδk+1 = x δ k +∆x. 3. Tìm λ (k+1) = (λ (k+1)1 , ...,λ (k+1) l ) theo công thức (1.4.3). 4. Nếu ∥∥∥λ (k+1)−λ (k)∥∥∥ < TOL1 và ‖∆x‖X < TOL2 thì dừng thuật toán, 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ử La- grange 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)→ ming j(x)≤ 0, j = 1, ..., l, (1.5.1) 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 M(x,λ ,c) := J(x)+ 1 2c l ∑ j=1 ( max { 0,λ j + cg j(x) }2−λ 2j ). (1.5.2) 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+1j := max{0;λ (k)j + ckg 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 M(x,λ ,c) := J(x)+ l ∑ j=1 1 2c j ( max { 0,λ j + c jg j(x) }2−λ 2j ). (1.5.5) 20 Cho ν > 0, đặt g j(x) := 2δ νj (∥∥∥Fj(x)− yδj ∥∥∥νYj −δ νj ) ; c j := λ j 2δ 2νj . Do đó M(x,λ ,c) := J(x)+ l ∑ j=1 1 2c j max{0,λ j + λ jδ νj (∥∥∥Fj(x)− yδj ∥∥∥νYj −δ νj )}2 −λ 2j  = J(x)+ l ∑ j=1 δ 2νj λ j max{0,λ j + λ jδ νj (∥∥∥Fj(x)− yδj ∥∥∥νYj −δ νj )}2 −λ 2j  = J(x)+ l ∑ j=1 δ 2νj λ j max{0,1+ 1δ νj (∥∥∥Fj(x)− yδj ∥∥∥νYj −δ νj )}2 −1  = J(x)+ l ∑ j=1 δ 2νj λ j max 0, ∥∥∥Fj(x)− yδj ∥∥∥νYj δ νj  2 −1  = J(x)+ l ∑ j=1 λ j (∥∥∥Fj(x)− yδj ∥∥∥2νYj −δ 2νj ) Kết quả này trùng với hàm Lagrange trong (1.4.1) với ν = 1. Hơn nữa ta cập nhật (1.5.4) và đi đến λ (k+1)j := max { 0,λ (k)j +2c (k) j δ νj (∥∥∥Fj(x)− yδj ∥∥∥νYj −δ νj )} = max 0,λ (k)j + λ (k) j δ νj (∥∥∥Fj(x)− yδj ∥∥∥νYj −δ νj ) = λ (k)j max 0, ∥∥∥Fj(x)− yδj ∥∥∥νYj δ νj . Kết quả này trùng với (1.4.3) khi ε = 0. 21 Chương 2 Phương pháp hiệu chỉnh đa tham số Tikhonov Trong chương này, chúng tôi đề cập tới phương pháp hiệu chỉnh đa tham số Tikhonov dựa trên việc cực tiểu phiếm hàm làm trơn Tikhonov, trong đó phiếm hàm có chứa tham số α và các tham số - λ j, ( j = 1, ..., l). Phần này tôi phát triển dựa theo cách tiếp cận tổng quát của Torsten [2] để mở rộng các kết quả đã biết của Nguyễn Bường và Nguyễn Đình Dũng [3], bao gồm các định lý: Định lý 2.2.1, Định lý 2.2.2, Định lý 2.2.3, Mệnh đề 2.2.4 về sự tồn tại và tính ổn định của nghiệm. Cuối chương là hai định lý: Định lý 2.2.5, Định lý 2.2.6 về tốc độ hội tụ của nghiệm. 2.1 Nhắc lại bài toán Cho X ,Yj,( j = 1,2, . . . , l) là các không gian Banach phản xạ, Fj : D(Fj) ⊂ X → Yj là các toán tử (phi tuyến), D := l⋂ j=1 D(Fj) 6=∅. Ta cần giải hệ sau Fj(x) = y j,x ∈ D,( j = 1,2, . . . , l). (2.1.1) Trong trường hợp dữ liệu có nhiễu, yδj : ∥∥∥yδj − y j∥∥∥≤ δ j,( j = 1,2, . . . , l) ta có hệ mới Fj(x) = yδj ,x ∈ D,( j = 1,2, . . . , l). (2.1.2) 22 Phương pháp hiệu chỉnh đa tham số Tikhonov Xét bài toán cực tiểu hóa phiếm hàm làm trơn Tikhonov Tα(x) = l ∑ j=1 λ j ∥∥∥Fj(x)− yδj ∥∥∥2Yj +αJ(x)→minx∈D , (2.1.3) trong đó α > 0;λ = (λ1, ...,λl)T ,λ j > 0,‖λ‖∞ = 1, phiếm hàm ổn định J : D⊂ X → R và véctơ hiệu chỉnh α = (α1, ...,αl)T ;α j = αλ j , j = 1,2, . . . , l. Định nghĩa. x† được gọi là nghiệm J−min của bài toán (2.1.1) nếu x† thỏa mãn (2.1.1) và J(x†) = min{J(x) : x ∈ S} trong đó S := {x ∈ D : Fj(x) = y j, j = 1,2, . . . , l}. Mục tiêu của chương này là thiết lập tính đặt chỉnh của bài toán (2.1.3) với các điều kiện (A1)-(A5), tức là chứng minh bài toán (2.1.3) luôn có duy nhất nghiệm xδα phụ thuộc liên tục vào dữ liệu đã cho. Ngoài ra thêm một vài điều kiện bổ sung về hàm Fj(x) và J(x) ta sẽ có đánh giá tốc độ hội tụ của phương pháp theo khoảng cách Bregman. 2.2 Một số kết quả Sau đây là một số kết quả chính thu được cho phương pháp hiệu chỉnh Tikhonov. Định lý 2.2.1. Với các điều kiện (A1)− (A4) thì bài toán (2.1.3) luôn có ít nhất một nghiệm xδα . Chứng minh. Đặt d = inf x∈D Tα(x). Khi đó tồn tại dãy cực tiểu {xn} ⊂D, sao cho d = lim n→∞ Tα(xn). Nói riêng dãy {Tα(xn)} là dãy bị chặn, nghĩa là, tồn tại R > 0 sao cho 0≤ Tα(xn)≤ R ∀n ∈ N. Điều này tương đương với l ∑ j=1 λ j ∥∥∥Fj(xn)− yδj ∥∥∥2+αJ(xn)≤ R ∀n ∈ N. 23 Do đó {Fj(xn)}n,{J(xn)}n là bị chặn. Suy ra tồn tại C ≥ 0 sao cho J(xn)+ l ∑ j=1 ∥∥Fj(xn)∥∥≤C, ∀n. Mà theo (A4) tập A(C) = { x : J(x)+ l ∑ j=1 ∥∥Fj(x)∥∥≤C} là bị chặn. Từ đó suy ra dãy {xn,F1(xn), ...,Fl(xn)} là bị chặn trong không gian Ba- nach phản xạ X ×Y1× ...×Yl. Do vậy nó là tập compac tương đối yếu, hay tồn tại dãy con {xnk} ⊂ {xn} sao cho xnk ⇀ x0Fj(xnk)⇀ y j( j = 1,2, . . . , l). Theo giả thiết (A2) thì x0 ∈D và Fj(x0) = y j,( j = 1,2, . . . , l). Do tính nửa liên tục dưới yếu của chuẩn và của J(x), ta có ∥∥∥Fj(x0)− yδj ∥∥∥= ∥∥∥y j− yδj ∥∥∥≤ limk→∞ inf∥∥∥Fj(xnk)− yδj ∥∥∥ , j = 1,2, . . . , l J(x0)≤ limk→∞ infJ(xnk). Từ đây suy ra d ≤ Tα(x0)≤ limk→∞ infTα(xnk)≤ limk→∞ supTα(xnk) = limk→∞ Tα(xnk) = d, do đó d = Tα(x0), hay x0 là nghiệm của bài toán (2.1.3).⊠ Định lý 2.2.2. Cho các giả thiết (A1)− (A5), α > 0, và yδnj → yδj (n → ∞), j = 1,2, . . . , l. Gọi xn là nghiệm của bài toán (2.1.3) ứng với yδj thay bằng yδnj Khi đó 1. Tồn tại một dãy con hội tụ của dãy xn. 2. Mỗi giới hạn của dãy con là nghiệm của bài toán (2.1.3). 24 Chứng minh. Lập luận tương tự như trong định lý 2.2.1 ta có xnk ⇀ x0 ∈ DFj(xnk)⇀ y j và Fj(x0) = y j,( j = 1, . . . , l). Vì xnk là nghiệm của (2.1.3) và y δnk j → yδj nên ta có Tα(x0)≤ limk inf l ∑ j=1 λ j ∥∥∥Fj(xnk)− yδnkj ∥∥∥2+αlimk infJ(xnk) ≤ lim k { sup l ∑ j=1 λ j ∥∥∥Fj(xnk)− yδnkj ∥∥∥2 +α supJ(xnk) } ≤ lim k { l ∑ j=1 λ j ∥∥∥Fj(x)− yδnkj ∥∥∥2+αJ(x) } = l ∑ j=1 λ j ∥∥∥Fj(x)− yδj ∥∥∥2 +αJ(x) = Tα(x) ∀x ∈ D. (2.2.1) Vậy Tα(x0)≤ Tα(x) ∀x ∈ D từ đây suy ra x0 ∈ Argmin x∈D Tα(x). (2.2.2) Bây giờ ta chứng minh xnk → x0. Từ (2.2.1) ta có lim k→∞ { l ∑ j=1 λ j ∥∥∥Fj(xnk)− yδnkj ∥∥∥2+αJ(xnk) } = l ∑ j=1 λ j ∥∥∥Fj(x0)− yδj ∥∥∥2+αJ(x0) (2.2.3) Ta kết luận J(xnk) → J(x0). Thật vậy giả sử ngược lại J(xnk)9 J(x0). Vì J(x0)≤ limk infJ(xnk) nên nếu đặt C := limk supJ(xnk) thì C > J(x0). Ngoài ra, tồn tại dãy con {xm}m ⊂ {xnk}k sao cho lim m→∞ J(xm) =C. Chú ý rằng xm ⇀ x0,Fj(xm)⇀ y j = Fj(x0) nên từ (2.2.3) ta có lim m l ∑ j=1 λ j ∥∥∥Fj(xm)− yδmj ∥∥∥2 = l∑j=1λ j ∥∥∥Fj(x0)− yδj ∥∥∥2 +α [J(x0)−C] 25 < l ∑ j=1 λ j ∥∥∥Fj(x0)− yδj ∥∥∥2. Điều này là vô lý vì theo tính nửa liên tục dưới yếu của chuẩn thì∥∥∥Fj(x0)− yδj ∥∥∥≤ lim m inf ∥∥∥Fj(xm)− yδmj ∥∥∥ ,( j = 1,2, . . . , l) . Vậy J(xnk)→ J(x0). Kết hợp với xnk ⇀ x0 và giả thiết (A5) ta có điều phải chứng minh.⊠ Định lý 2.2.3. Cho các giả thiết (A1)− (A5), α(δ )→ 0 và ‖δ‖ 2 α(δ ) → 0 khi δ → 0. Giả sử {δ k}k mà δ k → 0. Gọi {xδkαk} là dãy nghiệm của bài toán (2.1.3) ứng với δ k và αk = α(δ k). Khi đó 1. {xδkαk} chứa dãy con hội tụ. 2. Mỗi giới hạn của dãy con là một nghiệm J−min của (2.1.1). 3. Nếu nghiệm J−min x† của (2.1.1) là duy nhất thì lim δ→0 xδα(δ ) = x †. Chứng minh. 1. Đặt S := { x ∈ D : Fj(x) = y j, j = 1, . . . , l } (2.2.4) Vì S⊂ D và xδα là nghiệm cực tiểu của (2.1.3) nên với mọi x ∈ S, ta có l ∑ j=1 λ j ∥∥∥Fj(xδα)− yδj ∥∥∥2+αJ(xδα)≤ l∑ j=1 λ j ∥∥∥Fj(x)− yδj ∥∥∥2+αJ(x) = l ∑ j=1 λ j ∥∥∥y j− yδj ∥∥∥2+αJ(x)≤ l∑ j=1 λ jδ 2j +αJ(x) ≤ ‖λ‖ ∞ ‖δ‖2+αJ(x) = ‖δ‖2 +αJ(x). (2.2.5) 26 Từ (2.2.5) ta suy ra J(xδα)≤ ‖δ‖2 α + J(x), (2.2.6) λ j ∥∥∥Fj(xδα)− yδj∥∥∥2 ≤ ‖δ‖2+αJ(x), (2.2.7)∥∥∥Fj(xδα)∥∥∥ - bị chặn. (2.2.8) Từ (2.2.6),(2.2.8) và giả thiết (A4) ta có { xδα ,F1(xδα), ...,Fl(xδα) } là dãy bị chặn trong không gian Banach phản xạ X ×Y1× ...×Yl. Do đó dãy { x δk αk,F1(x δk αk), ...,Fl(x δk αk) } cũng bị chặn. Vậy nó là tập compắc tương đối yếu. Suy ra tồn tại dãy con { x δm αm } ⊂ { x δk αk } hội tụ yếu, tức là xδmαm ⇀ x0,Fj(x δm αm)⇀ y 0 j . (2.2.9) Theo giả thiết (A2) suy ra x0 ∈ D và y0j = Fj(x0). Từ (2.2.7) và chú ý tính nửa liên tục dưới yếu của chuẩn, ta có ∥∥Fj(x0)− y j∥∥≤ lim m inf ∥∥∥Fj(xδmαm)− y j∥∥∥ ≤ lim m inf {∥∥∥Fj(xδmαm)− yδmj ∥∥∥+∥∥∥yδmj − y j∥∥∥} ≤ lim m [ 1√ λ j ( ‖δ m‖2+αmJ(x) )1/2 +δ jm ] = 0. Từ đó suy ra Fj(x0) = y j, ∀ j = 1, ..., l. Chứng tỏ x0 ∈ S. Mặt khác, theo (2.2.6), giả thiết và tính nửa liên tục dưới yếu của J(x) thì với mọi x ∈ S, ta có J(x0)≤ lim m infJ(xδmαm)≤ limm supJ(x δm αm)≤ J(x). (2.2.10) Đặc biệt cho x = x0 ta suy ra lim m→∞ J(x δm αm) = J(x0). (2.2.11) Từ (2.2.11), xδmαm ⇀ x0 và giả thiết (A5) ta suy ra x δm αm → x0. 2. Theo (2.2.10) ta có x0 ∈ S , J(x0)≤ J(x), ∀x ∈ S, suy ra x0 là một nghiệm 27 J−min của (2.1.3). Tất nhiên nếu có một giới hạn x′0 của một dãy con thì nó cũng là nghiệm J−min của bài toán (2.1.1). 3. Nếu nghiệm J−min x† của (2.1.1) là duy nhất thì theo phần 1.,2., mọi dãy con đều hội tụ về x†. Do đó lim δ→0 xδα(δ ) = x †. Định lý được chứng minh. ⊠ Trước khi đi vào đánh giá tốc độ hội tụ của nghiệm xδα tới nghiệm x† của (2.1.1), ta xét trường hợp giả tối ưu, tức là có xδ ,ηα sao cho Tα(xδ ,ηα )≤ Tα(xδα)+η (2.2.12) với η ≥ 0 cho trước. Mệnh đề 2.2.4. Giả sử (A1)− (A5) thỏa mãn, và yδj ∈ Yj,( ∥∥∥y j− yδj ∥∥∥ ≤ δ j),δ := (δ1, ...,δl)T ,α := α(δ ,η) thỏa mãn α(δ ,η)→ 0; ‖δ‖ 2 2 α(δ ,η) → 0; η α(δ ,η) → 0 khi δ → 0;η → 0. Khi đó 1. Mọi dãy { x δk,ηk αk } k với δ k → 0;ηk → 0,αk =α(δ k,ηk) thỏa mãn (2.2.12) có một dãy con hội tụ. 2. Mỗi giới hạn x̂ của dãy con là nghiệm J−min của (2.1.1). Hơn nữa nếu thêm điều kiện nghiệm x† của (2.1.1) là duy nhất thì lim k→∞ x δk,ηk αk = x †. Chứng minh. Đặt xk = x δk,ηk αk . Khi đó ta có 28 l ∑ j=1 λ j ∥∥∥Fj(xk)− yδ j,kj ∥∥∥2Yj +αkJ(xk)≤ ≤ l ∑ j=1 λ j ∥∥∥Fj(x†)− yδ j,kj ∥∥∥2Yj +αkJ(x†)+ηk ≤ ‖δ k‖22+αkJ(x†)+ηk. Cho k → ∞ ta suy ra Fj(xk)→ y j (k → ∞) và J(xk)≤ ‖δ k‖22 αk + ηk αk + J(x†). (2.2.13) Do đó theo giả thiết {J(xk),F1(xk), ...,Fl(xk)} bị chặn, suy ra tồn tại một dãy con hội tụ yếu xki ⇀ x̂ ∈ D. Ngoài ra x̂ là nghiệm của (2.1.1). Hơn nữa trong (2.2.13) thay x† bằng x̂ ta thu được J(x̂)≤ lim i→∞ infJ(xki)≤ limi→∞ supJ(xki)≤ limi→∞ { ‖δ k‖22 αk + ηk αk + J(x̂) } = J(x̂) Từ đây suy ra lim i→∞ J(xki) = J(x̂), và do đó xki → x̂ (theo giả thiết A5). Lại theo (2.2.13) ta có J(x̂)≤ lim i→∞ supJ(xki)≤ J(x†)≤ J(x̂). Suy ra x̂ là nghiệm J−min của (2.1.1). Nếu nghiệm J−min x† là duy nhất, tức là x̂ = x† thì xki → x†. Mệnh đề 2.2.4 được chứng minh. ⊠ Định lý 2.2.5. (Tốc độ hội tụ của xδα(δ )→ x† khi δ → 0) Cho các giả thiết (A1)− (A5) và các điều kiện sau 1. F1(x),J(x) khả vi Fréchet trong lân cận x†. 2. ∃L > 0 sao cho ∥∥r1(x,x†)∥∥ ≤ L.D(x,x†) với mọi x trong lân cận của x†, trong đó r1(x,x †) := F1(x)−F1(x†)−F ′ 1(x †)(x− x†). 29 3. ∃w ∈ Y ∗1 : J ′ (x†) = F ′1(x †)∗w. 4. L.‖w‖Y ∗1 < 1 . Khi đó. Nếu chọn α ∼ ‖δ‖p,(0 < p < 2) thì D(xδα(δ ),x †) = O (‖δ‖µ) trong đó µ = min{p,2− p} Chứng minh. Quy ước ‖.‖ là chuẩn trong không gian tương ứng. Từ (2.2.5) cho x = x† ta có l ∑ j=1 λ j ∥∥∥Fj(xδα)− yδj ∥∥∥2+αJ(xδα)≤ ‖δ‖2+αJ(x†). Vì D(xδα ,x†) = J(xδα)− J(x†)− 〈 J′(x†),xδα − x† 〉 cùng với các giả thiết 2., 3. nên ta có l ∑ j=1 λ j ∥∥∥Fj(xδα)− yδj ∥∥∥2+αD(xδα ,x†)≤ ‖δ‖2+α 〈J′(x†),x†− xδα〉 = ‖δ‖2+α 〈 w,F ′ 1(x †)(x†− xδα) 〉 = ‖δ‖2+α 〈 w,r1(xδα ,x †)+F1(x†)−F1(xδα) 〉 ≤ ‖δ‖2+α ‖w‖ [∥∥∥r1(xδα ,x†)∥∥∥+∥∥∥y1− yδ1∥∥∥+∥∥∥yδ1 −F1(xδα)∥∥∥] ≤ ‖δ‖2+α ‖w‖LD(xδα ,x†)+α ‖w‖δ1+α ‖w‖ ∥∥∥yδ1 −F1(xδα)∥∥∥ . (2.2.14) Do đó l ∑ j=1 λ j ∥∥∥Fj(xδα)− yδj ∥∥∥2+α(1−L‖w‖)D(xδα ,x†)≤ ‖δ‖2+α ‖w‖‖δ‖ +α ‖w‖ ∥∥∥yδ1 −F1(xδα)∥∥∥ . (2.2.15) Từ (2.2.15) suy ra∥∥∥F1(xδα)− yδ1∥∥∥2︸ ︷︷ ︸ a2 ≤ 1λ1 ( ‖δ‖2+α ‖w‖‖δ‖ ) ︸ ︷︷ ︸ c2 + α ‖w‖ λ1︸ ︷︷ ︸ b ∥∥∥yδ1 −F1(xδα)∥∥∥︸ ︷︷ ︸ a . (2.2.16) 30 Chú ý rằng ( a,b,c > 0;a2 ≤ c2+ab)⇒ (a≤ b+ c), suy ra ∥∥∥F1(xδα)− yδ1∥∥∥≤ ( ‖δ‖2+α ‖w‖‖δ‖ )1/2√ λ1 + α ‖w‖ λ1 . (2.2.17) Từ (2.2.15) suy ra D(xδα ,x †)≤ ‖δ‖2 +α ‖w‖‖δ‖+α ‖w‖ ∥∥∥yδ1 −F1(xδα)∥∥∥ α(1−L‖w‖) . (2.2.18) Chọn α ∼ ‖δ‖p. Nếu 0 < p < 1 thì từ (2.2.17) ta có∥∥∥F1(xδα)− yδ1∥∥∥= O(‖δ‖p) . Kết hợp với (2.2.18) ta có D(xδα ,x †) = O(‖δ‖p) . Nếu 1≤ p < 2 thì từ (2.2.17) ta có∥∥∥F1(xδα)− yδ1∥∥∥= O(‖δ‖) . Kết hợp với (2.2.18) ta có D(xδα ,x †) = O ( ‖δ‖2−p ) . Từ đó nếu đặt µ = min{p,2− p} thì Định lý 2.2.5 được chứng minh. ⊠ Nhận xét. Khi chọn J(x) = ‖x− x∗‖2, ta có 1. D(x˜,x) = ‖x˜− x‖2, do đó theo định lý 2.2.5. ta có∥∥∥xδα − x†∥∥∥= O(‖δ‖ µ2) (2.2.19) 31 2. Điều kiện 2. trong định lý 2.2.5. là∥∥∥F1(x)−F1(x†)−F ′1(x†)(x− x†)∥∥∥≤ L∥∥∥x− x†∥∥∥2. Điều này có thể đạt được nếu ta giả thiết tính Lipschitz của F ′1, tức là∥∥∥F ′1(x)−F ′1(x†)∥∥∥≤ 2L∥∥∥x− x†∥∥∥ , ∀x ∈U(x†). Thật vậy theo công thức giá trị trung bình ∥∥∥F1(x)−F1(x†)−F ′1(x†)(x− x†)∥∥∥= = ∥∥∥∥ 1∫ 0 ( F ′1(x † + t(x− x†))−F ′1(x†) ) (x− x†)dt ∥∥∥∥ ≤ 1∫ 0 2Lt ∥∥x− x†∥∥2dt = L∥∥x− x†∥∥2 . Bây giờ ta tổng quát hóa định lý 2.2.5 bằng cách sử dụng điều kiện A6. Định lý 2.2.6. (Tốc độ hội tụ của xδα(δ )→ x† khi δ → 0) Cho các giả thiết (A1)− (A6). Khi đó ta có đánh giá D ( xδα ,x † ) ≤ 1 1− γ [ ‖δ‖2 α + ∥∥∥β∥∥∥‖δ‖+α l∑ j=1 β 2j 4λ j ] (2.2.20) Hơn nữa nếu chọn α ∼ ‖δ‖p,(0 < p < 2) thì D(xδα(δ ),x †) = O (‖δ‖µ) (2.2.21) trong đó µ = min{p,2− p} Chứng minh. Ta có Tα(xδα)≤ Tα(x†) và D(xδα ,x†) = J(xδα)−J(x†)− 〈 J′(x†),xδα − x† 〉 , nên suy ra l ∑ j=1 λ j ∥∥∥Fj(xδα)− yδj ∥∥∥2 +αD(xδα ,x†)≤ 32 ≤ l ∑ j=1 λ j ∥∥∥Fj(x†)− yδj ∥∥∥2+α〈J′(x†),xδα − x†〉X∗,X ≤ l ∑ j=1 λ jδ 2j +αγD(xδα ,x†)+α l ∑ j=1 β j ∥∥∥Fj(xδα)−Fj(x†)∥∥∥ ≤ l ∑ j=1 λ jδ 2j +αγD(xδα ,x†)+α l ∑ j=1 β j {∥∥∥Fj(xδα)− yδj ∥∥∥+∥∥∥yδj − y j∥∥∥} ≤ l ∑ j=1 λ jδ 2j +αγD(xδα ,x†)+α l ∑ j=1 β j {∥∥∥Fj(xδα)− yδj ∥∥∥+δ j} ≤ αγD(xδα ,x†)+ l ∑ j=1 { λ jδ 2j +αβ jδ j + α 2β 2j 4λ j +λ j ∥∥∥Fj(xδα)− yδj ∥∥∥2} (theo bất đẳng thức Cauchy). Do đó D ( xδα ,x † ) ≤ 1 1− γ  l ∑ j=1 λ jδ 2j α + l ∑ j=1 β jδ j +α l ∑ j=1 β 2j 4λ j  . (2.2.22) Mặt khác l ∑ j=1 λ jδ 2j ≤ ‖λ‖∞ l ∑ j=1 δ 2j = l ∑ j=1 δ 2j ; l ∑ j=1 β jδ j ≤ ∥∥∥β∥∥∥ 2 .‖δ‖2 Kết hợp điều này với bất đẳng thức (2.2.22) ta thu được đánh giá (2.2.20). Nếu chọn α := C‖δ‖p và đặt µ = min{p.2− p} thì từ (2.2.20) ta thu được (2.2.21).Định lý 2.2.6 được chứng minh. ⊠ Nhận xét. Từ (2.2.22) ta có đánh giá D(xδα ,x †)≤ 1 1− γ l ∑ j=1 ( λ jδ 2j α +β jδ j + αβ 2j 4λ j ) = 1 1− γ l ∑ j=1 (√ λ jδ j√ α + √ α β j 2 √ λ j )2 Vế phải của bất đẳng thức trên nhỏ nhất khi hai số bằng nhau, khi đó đặt α−1j = λ j α := β j 2δ j ,( j = 1, ..., l) , 33 và bất đẳng thức trên trở thành D(xδα ,x†)≤ 2 1− γ ∥∥∥β∥∥∥ 2 ‖δ‖2. Đánh giá này trùng với đánh giá trong định lý (1.3.1) của chương 1. Do đó giải (1.1.3) bằng phương pháp Lagrange ta thu được các nhân tử Lagrange λ1, ...,λl , với sai số tối ưu cho D(xδα ,x†) dưới các giả thiết đã cho. Mặt khác tham số hiệu chỉnh "tối ưu" α j = α λ j không chỉ phụ thuộc vào mức độ nhiễu δ j mà còn phụ thuộc vào tỷ lệ δ j β j . Do đó rất khó để tìm λ tối ưu tiên nghiệm cho (2.1.3) với λ và α cố định. Do vậy mà thuật toán 1 (chương 1) được minh họa như phương pháp hiệu chỉnh đa tham số Tikhonov kết hợp với chiến lược chọn tham số tiên nghiệm. Chiến lược chọn tham số được nghiên cứu một cách tổng quát bởi Morozov. Trong chương 3, tham số hiệu chỉnh n = n(δ ) được chọn theo nguyên lý Morozov cải biên. 2.3 Ví dụ minh họa Giải hệ phương trình Fi(x1, . . . ,xm) = yi, i = 1,2, . . . ,N. (2.3.1) với m ẩn số x1, . . . ,xm và N phương trình m >> N. Giả sử các phiếm hàm Fi : Rm → R khả vi Fréchet trong lân cận nghiệm x† của hệ (2.3.1). Ta viết lại dưới dạng véctơ F(x) = y. (2.3.2) trong đó F : Rm → RN , F = (F1, . . . ,FN), x = (x1, . . . ,xm)T , y = (y1, . . . ,yN)T . Cụ thể với N = 4 và Fj(x) có dạng F1 (x) = k2x1+ x22+ ...+ x2m = xT A1x+ k2xT b F2 (x) = x1x2+ x2x3 + ...+ xm−1xm = xT A2x F3 (x) = x1x3+ x2x4 + ...+ xm−2xm = xT A3x F4 (x) = x1x4+ x2x5 + ...+ xm−3xm = xT A4x 34 trong đó k 6= 0 cho trước, b = (1,0,0, ...,0)T và Al = (ali j)m×m, l = 1,2,3,4 với a1i j = 0 nếu i = j = 1 hoặc i 6= j1 nếu i = j 6= 1, và ali j =  1 2 nếu |i− j|= l−1 0 nếu |i− j| 6= l−1, l = 2,3,4. Bây giờ ta đi kiểm tra các giả thiết A1− A5. Rõ ràng các không gian X = Rm,Yj = R, j = 1,2,3,4 là các không gian Hilbert và J(x) = ‖x‖2. A1. Với dữ liệu chính xác y = (k2,0,0,0)T thì hệ có nghiệm chính xác là x† = (1,0, . . . ,0)T . A2. Dễ thấy các hàm Fi(x), j = 1, ...,4 liên tục. Vì trong không gian hữu hạn chiều hội tụ mạnh và hội tụ yếu trùng nhau, nên nếu xn ⇀ x;Fi(xn)⇀ yi thì xn → x;Fi(xn)→ yi, từ tính liên tục của Fi(x) suy ra Fi(x) = yi và x∈D j = Rm. A3. J(x) = ‖x‖2 là hàm không âm và nửa liên tục dưới yếu (do tính nửa liên tục dưới yếu của chuẩn). A4. Hiển nhiên với mọi C ≥ 0 thì tập A(C) = {x ∈ Rm : ‖x‖2+ 4 ∑ j=1 ∥∥Fj(x)∥∥≤C} là tập bị chặn (do ‖x‖ ≤ √C). A5. Nếu xn ⇀ x và ‖xn‖→ ‖x‖ thì ‖xn− x‖2 = ‖xn‖2−2+‖x‖2 → ‖x‖2−2 +‖x‖2 = 0. Do đó xn → x. Để thu được đánh giá tốc độ hội tụ của nghiệm xδα(δ ) về nghiệm x †, ta cần kiểm tra các giả thiết của định lý 2.2.5. Theo định lý thì chỉ cần kiểm tra giả thiết đó với một hàm, chẳng hạn với F1(x). 1. Dễ thấy F1(x) và J(x) là các hàm đa thức nên chúng đều khả vi Fréchet trong lân cận x†. 2. D(x,x†) = ∥∥x− x†∥∥2 và F ′1(x†) = 2A1x† + k2b,F”1 (x) = 2A1. Do đó ∥∥F”1 (x)∥∥= ‖2A1‖= 2. Ta có 35 ∥∥r1(x,x†)∥∥= ∥∥∥F1(x)−F1(x†)−F ′1(x†)(x− x†)∥∥∥= = ∥∥∥∥ 1∫ 0 ( F ′1(x † + t(x− x†))−F ′1(x†) ) (x− x†)dt ∥∥∥∥ ≤ 1∫ 0 2t ∥∥x− x†∥∥2dt = ∥∥x− x†∥∥2 = D(x,x†). Vậy giả thiết 2. của định lý 2.2.5 thỏa mãn với L = 1. 3. Ta có F ′1(x †) = 2A1x†+ k2b = k2b và J ′ (x†) = 2x†. Do vậy chọn w = 2k2 , khi đó w ∈ Y ∗2 và J ′ (x†) = F ′1(x†)∗w. 4. Cuối cùng L.‖w‖Y ∗2 = 2 k2 . Để có L.‖w‖Y ∗2 √ 2. Vậy ta có thể sử dụng phương pháp hiệu chỉnh đa tham số Tikhonov để giải bài toán trên. 36 Chương 3 Phương pháp chỉnh lặp song song dạng Gauss - Newton Trong chương này, chúng tôi đề cập tới phương pháp chỉnh lặp song song dạng Gauss - Newton giải hệ phương trình toán tử. Nội dung chính của chương này dựa trên công trình của Phạm Kỳ Anh và Vũ Tiến Dũng [1]. 3.1 Giới thiệu Nhiều bài toán nhận dạng dẫn đến việc giải hệ phương trình toán tử sau Fi(x) = yi, 1≤ i≤ N, (3.1.1) trong đó Fi : X → Yi (toán tử phi tuyến), X ,Yi là các không gian Hilbert. Trong trường hợp dữ liệu có nhiễu, tức là chỉ biết yδi sao cho ∥∥∥yδi − yi∥∥∥≤ δ , ta có hệ Fi(x) = yδi 1≤ i≤ N, (3.1.2) Viết lại hệ (3.1.1) và (3.1.2) dưới dạng sau F(x) = y, (3.1.3) và F(x) = yδ , (3.1.4) 37 trong đó F : X →Y :=Y1×Y2× ...×YN , F(x) = (F1(x),F2(x), ...,FN(x)),y = (y1, ...,yN) ∈ Y và yδ = (yδ1 , ...,yδN) ∈ Y . TrongY ta xét tính vô hướng và chuẩn tương ứng như sau: ∀u=(u1, ...,uN)∈ Y và v = (v1, ...,vN) ∈ Y Y= N ∑ i=1 Yi, ‖u‖Y = ( N ∑ i=1 ‖ui‖2Yi)1/2. Một trong những phương pháp hiệu chỉnh hiệu quả cho bài toán đặt không chỉnh phi tuyến là phương pháp chỉnh lặp Gauss-Newton IRGNM (Iteratively regularized Gauss - Newton mehtod), do Bakushinskii đề xuất vào năm 1992 [6]. Sự hội tụ của phương pháp IRGNM được nghiên cứu bởi Blaschke [7], Hohage [9], Deuflhard [8], Jin Qin nia [10] và một số tác giả khác [11, 12