Header Page of 126 ĐẠI HỌC THÁI NGUN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ HUẾ PHƯƠNG PHÁP HIỆU CHỈNH TÌM NGHIỆM CHUNG CHO MỘT HỌ PHƯƠNG TRÌNH TỐN TỬ TUYẾN TÍNH GIỚI NỘI Chun Ngành: TỐN ỨNG DỤNG Mã ngành: 60460112 LUẬN VĂN THẠC SĨ TỐN HỌC Người hướng dẫn : GS.TS NGUYỄN BƯỜNG Thái Ngun - 2013 Footer Page of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 Mục lục Mục lục Mở đầu Chương Giới thiệu phương pháp hiệu chỉnh số khái niệm liên quan 1.1 Một số kiến thức giải tích hàm 1.1.1 Một số khái niệm khơng gian 1.1.2 Tốn tử tuyến tính 1.1.3 Phương trình tốn tử 1.2 Giới thiệu phương pháp hiệu chỉnh 11 1.2.1 Tốn tử hiệu chỉnh 11 1.2.2 Phương pháp hiệu chỉnh 12 1.2.3 Sự tồn tốn tử hiệu chỉnh 12 1.2.4 Hiệu chỉnh hệ phương trình đại số tuyến tính điều kiện xấu 13 1.2.5 Cực tiểu phiếm hàm Tikhonov 17 Chương Phương pháp hiệu chỉnh tìm nghiệm chung cho hệ phương trình với tốn tử tuyến tính giới nội 20 2.1 Bài tốn 20 2.2 Thuật tốn 23 2.3 Một số ví dụ 26 Kết luận 30 Tài liệu tham khảo 31 Footer Page of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 MỞ ĐẦU Xét tốn dạng phương trình tốn tử Ax = f, (1.1) A : X → Y tốn tử từ khơng gian Banach X vào khơng gian Banach Y f phần tử thuộc Y Giả sử A−1 khơng liên tục thay cho f ta biết fδ xấp xỉ f thỏa mãn fδ − f ≤ δ Bài tốn đặt dựa vào thơng tin (A, fδ ) sai số δ, tìm phần tử xấp xỉ nghiệm x0 Rõ ràng khơng thể xây dựng phần tử xấp xỉ xδ theo quy tắc xδ = A−1 fδ A−1 khơng xác định A−1 tồn khơng liên tục, nên A−1 fδ khơng cho ta xấp xỉ nghiệm x0 Tham số δ cho ta mức độ sai số vế phải phương trình (1.1) Vì điều nảy sinh liệu xây dựng phần tử xấp xỉ phụ thuộc vào tham số tham số chọn tương thích với δ cho δ → phần tử xấp xỉ hội tụ đến nghiệm x0 Ta thấy từ f0 ∈ Y ta có phần tử xấp xỉ tương ứng thuộc X Tức tồn tốn tử tác động từ khơng gian Y vào khơng gian X Năm 2011 GS TS Nguyễn Bường nghiên cứu sinh Nguyễn Đình Dũng đưa phương pháp chung để giải hệ phương trình tốn tử tuyến tính giới nội Mục đích luận văn trình bày phương pháp hiệu chỉnh tìm nghiệm chung cho hệ phương trình tốn tử tuyến tính giới nội đưa số ví dụ minh họa cho phương pháp hiệu chỉnh trình bày Footer Page of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 Ngồi phần mở đầu, phần kết luận, luận văn gồm chương Chương Giới thiệu phương pháp hiệu chỉnh số khái niệm liên quan Chương Trình bày phương pháp hiệu chỉnh tìm nghiệm chung cho họ phương trình tốn tử tuyến tính giới nội Luận văn hồn thành với hướng dẫn bảo tận tình GS.TS Nguyễn Bường - Viện Cơng nghệ Thơng tin, Viện Hàn lâm Khoa học Cơng nghệ Việt Nam Từ đáy lòng mình, em xin bày tỏ lòng biết ơn sâu sắc quan tâm, động viên bảo hướng dẫn thầy Em xin trân trọng cảm ơn tới Thầy Cơ trường Đại học Khoa học - Đại học Thái Ngun, phòng đào tạo trường Đại học Khoa học Đồng thời tơi xin gửi lời cảm ơn tới tập thể lớp Cao học Tốn K5 Trường Đại học Khoa học động viên giúp đỡ tơi q trình học tập làm luận văn Tơi xin cảm ơn tới sở giáo dục - đào tạo tỉnh Bắc Ninh, ban Giám hiệu, đồng nghiệp trường THPT Tiên Du số - Tiên Du - Bắc Ninh tạo điều kiện cho tơi học tập hồn thành kế hoạch học tập Tuy nhiên hiểu biết thân khn khổ luận văn thạc sĩ, nên q trình nghiên cứu khơng tránh khỏi thiếu sót, tơi mong dạy đóng góp ý kiến Thầy Cơ độc giả quan tâm tới luận văn Thái Ngun, ngày 10 tháng năm 2013 Tác giả Nguyễn Thị Huế Footer Page of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 Chương Giới thiệu phương pháp hiệu chỉnh số khái niệm liên quan Các kiến thức chương có tham khảo tài liệu [1] 1.1 Một số kiến thức giải tích hàm 1.1.1 Một số khái niệm khơng gian Định nghĩa 1.1 Khơng gian định chuẩn thực khơng gian tuyến tính thực X ứng với phần tử x ∈ X ta có số x gọi chuẩn x, thoả mãn điều kiện: x > 0, ∀x = 0, αx = |α| x+y ≤ x x = ⇔ x = 0; x , ∀x ∈ X, α ∈ R; y , ∀x, y ∈ R + Một khơng gian định chuẩn đầy đủ khơng gian Banach Định nghĩa 1.2 Dãy phần tử xn khơng gian Banach X gọi hội tụ đến phần tử x0 ∈ X n → ∞, xn − x0 → n → ∞, ký hiệu xn → x0 Sự hội tụ theo chuẩn gọi hội tụ mạnh Dãy {xn } ⊂ X gọi hội tụ yếu đến x0 ∈ X, kí hiệu xn x0 , với ∀f ∈ X ∗ - khơng gian liên hợp X, ta có f (xn ) → f (x0 ), n → ∞ Ví dụ 1.1 Khơng gian Lp [a, b] với < p < ∞ khơng gian Banach với chuẩn  b  p1 |ϕ(x)|p d(x) ϕ = a Ví dụ 1.2 Khơng gian Lp [a, b] , p > khơng gian phản xạ Mọi khơng Footer Page of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 gian định chuẩn hữu hạn chiều phản xạ Định nghĩa 1.4 Cho X khơng gian tuyến tính R Một tích vơ hướng X ánh xạ , : X × X → R thoả mãn điều kiện sau: i) x, x > 0, ∀x = 0; x, x = ⇔ x = 0; ii) x, y = y, x , ∀x, y ∈ X; iii) αx, y = α x, y , ∀x, y ∈ X, α ∈ R; iv) x + y, z = x, z + y, z , ∀x, y, z ∈ X Khơng gian tuyến tính X tích vơ hướng , gọi khơng gian tiền Hilbert Khơng gian tiền Hilbert đầy đủ gọi khơng gian Hilbert Ví dụ 1.3 Các khơng gian Rn , L2 [a, b] khơng gian Hilbert với tích vơ hướng xác định tương ứng là: n ξi ηi , x = (ξ1 , ξ2 , , ξn ) , y = (η1 , η2 , , ηn ) ∈ R, x, y = i=1 b ϕ (x)ψ (x) dx, ϕ, ψ ∈ L2 [a, b] ϕ, ψ = a Định nghĩa 1.5 Khơng gian Banach X gọi lồi chặt mặt cầu đơn vị S = S (X) = {x ∈ X : x = 1} X lồi chặt, tức từ x, y ∈ S : x = 1, y = kéo theo x + y < Ví dụ 1.4 Khơng gian Lp [a, b] khơng gian lồi chặt Định nghĩa 1.6 Khơng gian Banach X gọi khơng gian Ephimov Stechkin (hay khơng gian có tính chất E-S) X phản xạ X hội tụ yếu phần tử xn x hội tụ chuẩn ( xn → x ) ln kéo theo hội tụ mạnh ( xn − x → 0) Ví dụ 1.5 Khơng gian Hilbert có tính chất E-S 1.1.2 Tốn tử tuyến tính Định nghĩa 1.7 Cho A : X → Y tốn tử đơn trị X Y hai khơng gian Banach Chúng ta kí hiệu miền xác định A D(A) Footer Page of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 với D(A) = domA = {x ∈ X/Ax = ∅} miền giá trị R(A) = {f ∈ Y /f ∈ Ax, x ∈ D(A)} Tốn tử A gọi tốn tử tuyến tính 1)A(x1 + x2 ) = Ax1 + Ax2 với x1, x2 ∈ X; 2)A (αx) = αAx với x ∈ X, α ∈ R Nếu Y ≡ R ta có phiếm hàm tuyến tính f với miền xác định hàm f domf = {x ∈ X/f (x) = ∅} Định nghĩa 1.8 Tốn tử A gọi tốn tử tuyến tính liên tục tốn tử tuyến tính, đồng thời tốn tử liên tục hai khơng gian X Y Ví dụ 1.6 Cho X = Rk , Y = Rm , tốn tử A xác định A(x1 , x2 , , xk ) = (y1 , y2 , , ym ) với k yi = aij xj , i = 1, , m, j=1 aij số Ma trận (aij )k×m gọi ma trận tốn tử tuyến tính A dạng tổng qt tốn tử tuyến tính từ Rk vào Rm Một tốn tử tuyến tính từ Rk vào Rm liên tục Định nghĩa 1.9 Tốn tử A gọi 1) h-liên tục (hemicontinuous) X A(x + ty) Ax t → với x, y ∈ X; 2) d-liên tục (demicontinuous) X từ xn → x suy Axn Ax n → ∞ Footer Page of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 Định nghĩa 1.10 Tốn tử tuyến tính A : X → Y gọi bị chặn (giới nội) tồn số K > thỏa mãn: Ax Y ≤K x X , ∀x ∈ X Ví dụ 1.7 Cho A : L2 [a, b] → L2 [a, b] tốn tử xác định b (Aϕ)(x) = K(x, s)ϕ(s)ds, a K(x, s) hàm hai biến có bình phương khả tích, nghĩa b b K (x, s)dxds = N < ∞ a a Khi đó, A tốn tử tuyến tính liên tục Tốn tử gọi tốn tử tích phân Fredholm sinh hạch K(x, s) Định nghĩa 1.11 Cho A : X → Y tốn tử tuyến tính liên tục Khi số inf {K, K > : Ax ≤ K x , ∀x ∈ X} gọi chuẩn tốn tử A, kí hiệu A Nhận xét 1.1 1) Ba chuẩn thường dùng Rn n x |xi | = i=1 n x |xi |2 = i=1 x ∞ = max |xi | 1≤i≤n x = (x1 , x2 , , xn ) 2) Trong khơng gian hữu hạn chiều Rn , có sở cố định, tốn tử tuyến tính A cho ma trận (aij )ni,j=1 ba chuẩn tương ứng Footer Page of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page of 126 ma trận A là: n A A |aij | = max 1≤j≤n i=1 = { max λi AT A } 1≤i≤n n A ∞ |aij | , = max 1≤i≤n j=1 λi AT A giá trị riêng ma trận đối xứng AT A Định nghĩa 1.12 Tốn tử A gọi tốn tử (coercive) lim x →+∞ Ax, x = +∞, ∀x ∈ X x Định nghĩa 1.13 Cho X khơng gian Banach thực, A : D(A) → X ∗ tốn tử với miền xác định D(A) = X miền ảnh R(A) nằm X ∗ Tốn tử A gọi 1) đơn điệu (monotone) A(x) − A(y), x − y ≥ 0, ∀x, y ∈ D(A); 2) đơn điệu chặt (strictly monotone) dấu xảy x = y; 3) đơn điệu tồn hàm khơng âm δ(t) khơng giảm với t ≤ 0, δ(t) = A(x) − A(y), x − y ≥ δ ( x − y ) , ∀x, y ∈ D(A) Nếu δ(t) = cA t2 với cA số dương tốn tử A gọi đơn điệu mạnh Ví dụ 1.8 Tốn tử tuyến tính A : RM → RM xác định A = BT B Footer Page of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 10 of 126 với B ma trận vng cấp M , tốn tử đơn điệu Định nghĩa 1.14 Ánh xạ U s : X → X ∗ (nói chung đa trị ) xác định U s (x) = x∗ ∈ X ∗ : x∗ , x = x∗ x ; x∗ = x s−1 ,s ≥ gọi ánh xạ đối ngẫu tổng qt khơng gian X Khi s = U s thường viết U gọi ánh xạ đối ngẫu chuẩn tắc X Nhận xét 1.2 i) Trong khơng gian Hilbert H, ánh xạ đối ngẫu chuẩn tắc tốn tử đơn vị I H ii) Ánh xạ đối ngẫu ví dụ tốn tử đơn điệu, tồn khơng gian Banach Ví dụ 1.9 Với X = Lp (Ω), < p < ∞ Ω tập đo khơng gian Rn ánh xạ đối ngẫu chuẩn tắc có dạng (U x) (t) = x 1.1.3 2−p |x(t)|p−2 x(t), t ∈ Ω Phương trình tốn tử Cho X khơng gian Banach phản xạ thực, X ∗ khơng gian liên hợp X với f ∈ X ∗ cho trước Bổ đề 1.1 Cho X khơng gian Banach thực, f ∈ X ∗ A tốn tử h-liên tục từ X vào X ∗ Khi đó, có A(x) − f, x − x0 ≥ 0, ∀x ∈ X, A(x0 ) = f Chứng minh Footer Page 10 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 19 of 126 18 Như vậy, với α > fδ ∈ Rn : fδ − f0 ≤ δ ta có µ2δ + α x˜α ≤ (µ + δ)2 + α x0 Do µ ≤ µδ + δ, x˜α δ ≤ (µδ + δ) + x0 α Từ điều kiện định lý suy x˜α ≤ β1 (δ) (µδ + δ) + x0 ≤ 4β1 (δ) (µ + 2δ) + x0 , hay x˜α ≤ ϕ (δ) + x0 , ≤ ϕ (δ2 ) + x0 , ϕ (δ) = (µ + 2δ) β1 (δ) → 0, δ → Lấy dãy δk → 0, k → ∞ Với {fδk } : fδk − f0 ≤ δk ta có tương ứng dãy cực tiểu {˜ xαk }, αk = δ (δk ), thỏa mãn: x˜αk ≤ ϕ (δ2 ) + x0 Do đó, chọn dãy {˜ xαks } hội tụ đến phần tử x˜ đó, s → ∞ Dễ dàng kiểm tra ≤ A˜ xαks − f0 − µ ≤ A˜ xαks − fδks + δks − µ ≤ M αks x˜αks , fδks + δks − µ ≤ M αks x0 , fδks + δks − µ ≤ ( Ax0 − f0 + δks )2 + αks x0 ≤ (µ + δks )2 + αks x0 2 + δks − µ + δks − µ Vì αks ≤ β2 (δks ), ≤ A˜ xαks − f0 − µ ≤ Footer Page 19 of 126 Số hóa trung tâm học liệu (µ + δks )2 + β2 (δks ) x0 + δks − µ → 0, http://www.lrc.tnu.edu.vn/ Header Page 20 of 126 19 δks → Từ bất đẳng thức cuối suy A˜ x − f0 = µ Điều chứng tỏ x˜ giả nghiệm phương trình (1.3) giả nghiệm có chuẩn nhỏ tất giả nghiệm Nhưng nghiệm chuẩn tắc nhất, x˜ = x0 Qua dễ dàng nhận thấy dãy hội tụ x˜α(δ) hội tụ đến x0 Cho nên dãy x˜α(δ) hội tụ đến x0 Định lý chứng minh Footer Page 20 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 21 of 126 20 Chương Phương pháp hiệu chỉnh tìm nghiệm chung cho hệ phương trình với tốn tử tuyến tính giới nội Các kết chương sử dụng tài liệu [5] 2.1 Bài tốn Cho X Yj khơng gian Hilbert thực với tích vơ hướng chuẩn X ký hiệu , X X Cho Aj , j = 1, , N, N ánh xạ tuyến tính bị chặn từ X tới Yj Vấn đề đặt là: tìm giá trị x˜ ∈ X cho Aj x˜ = fj , ∀j = 1, , N, (2.1) fj phần tử cho trước Yj Đặt N Sj = {x ∈ X : Aj x = fj }, j = 1, , N, S = Sj j=1 Giả sử S = ∅ Từ tính chất Aj ta dễ dàng suy Sj tập lồi đóng X Do đó, S tập lồi đóng X Xét trường hợp liệu đầu vào fj khơng biết xác, tức δ có giá trị xấp xỉ fj j fj thỏa mãn : δ fj − fj j Yj ≤ δj , δj → 0, j = 1, , N (2.2) Với điều kiện với ánh xạ Aj , phương trình thứ j (2.1) đặt khơng chỉnh, theo nghĩa tập nghiệm Sj khơng phụ thuộc liên Footer Page 21 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 22 of 126 21 tục vào kiện ban đầu fj Vì vậy, để tìm nghiệm cho phương trình j (2.1) ta phải sử dụng phương pháp giải ổn định Một phương pháp phương pháp hiệu chỉnh Tikhonov dựa việc cực tiểu phiếm hàm δ Aj x − fj j Yj + α x − x∗ X, (2.3) x∗ phần tử X \ Sj , α = α(δ1 , · · ·δN ) > tham số hiệu chỉnh Theo kết [10] rằng, tốn αδ (2.3) cho phương trình thứ j hệ (2.1) có nghiệm xj j , αδ δj2 /α, α → {xj j } hội tụ đến x˜j thỏa mãn x˜j − x∗ X = x − x∗ x∈Sj X, j = 1, , N δ δ Trong luận văn này, ta xét tốn tìm xαj cho xαj → x˜ δj , α → 0, đồng thời chọn tham số hiệu chỉnh α = α(δ1 , · · ·δN ) δ j cho xα(δ → x˜ δj → 0, cuối ước lượng tốc độ hội tụ ,···δN ) nghiệm hiệu chỉnh khơng gian vơ hạn chiều, hay ước lượng δ j xα(δ − x˜ với x˜ nghiệm có x∗ - chuẩn nhỏ S ,···δN ) (x∗ −MNS) Burger and Kaltenbacher [4] sử dụng phương pháp lặp NewtonKaczmarz xoay vòng để hiệu chỉnh phương trình hệ (2.1) với điều kiện nguồn đặt lên ánh xạ Aj Phương pháp đường dốc Descent-Kaczmarz sử dụng xoay vòng Haltmeier Kowar, Leit˜ ao, Scherzerfor [8] cho phương trình riêng biệt (2.1) điều kiện nón tiếp tuyến địa phương đặt lên tốn tử Aj Lưu ý hệ phương trình (2.1) viết dạng Ax = f, (2.4) A : X → Y := Y1 × × YN xác định Ax := (A1 x, , AN x), f := (f1 , , fN ) Rất gần đây, Halmeier, Leit˜ ao Scherzer [7] Footer Page 22 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 23 of 126 22 nghiên cứu phương pháp Landweber-Kaczmarz để giải phương trình (2.4) với điều kiện nón tiếp tuyến địa phương ánh xạ tuyến tính Aj Phương trình (2.4) xem trường hợp đặc biệt phương trình (2.1) N = Tuy nhiên, lợi phương trình (2.1) so với (2.4) phản ánh rõ hơn, thơng tin quan trọng (f1 , , fN ) so sánh với phương trình (2.4) chứa thành phần f Trong [6], để tìm khơng điểm chung họ hữu hạn ánh xạ đơn điệu h-liên tục từ khơng gian Banach phản xạ E vào khơng gian đối ngẫu E ∗ , tác giả Nguyễn Bường đề xuất phương pháp hiệu chỉnh thơng qua việc giải phương trình hiệu chỉnh sau N αµj Aj (x) + αU (x) = θ, (2.5) j=0 µ0 = < µj < µj+1 < 1, j = 1, 2, , N − 1, U ánh xạ đối ngẫu chuẩn tắc E ước lượng tốc độ hội tụ nghiệm hiệu chỉnh với điều kiện trơn đặt lên tốn tử A1 , tức là: A1 (˜ x)∗ z = U (x0 ), với z ∈ E Trong chương này, để tìm nghiệm tốn (2.1), ta xét phương pháp hiệu chỉnh dựa sở tìm nghiệm tốn tối ưu hóa khơng ràng buộc sau: N δ Aj x − fj j x∈X Yj + α x − x∗ X (2.6) j=1 Tốc độ hội tụ nghiệm hiệu chỉnh (2.6) với với điều kiện nguồn đặt lên tốn tử A1 mục Trong mục 3, ta xét ví dụ minh hoạ để rằng, tốn (2.4) đặt chỉnh, phương trình (2.1) đặt khơng chỉnh Do đó, phương pháp hiệu chỉnh xoay vòng cho phương trình riêng biệt (2.1) [4] [8] khơng cần thiết Hơn nữa, phương pháp khơng thể tính đặt chỉnh hệ phương trình cho Trong phương pháp (2.6) sử dụng tính chất Footer Page 23 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 24 of 126 23 Các kí hiệu → hội tụ yếu hội tụ mạnh, a ∼ b có nghĩa a = O(b) b = O(a) 2.2 Thuật tốn Với giả thiết đặt lên tốn tử Aj ta dễ dàng tốn (2.6) có nghiệm Ta có hai câu hỏi cần trả lời phần Một là,bài tốn (2.6) có ổn định nghĩa nghiệm phụ thuộc liên tục vào δ kiện ban đầu fj j hay khơng? Hai là, nghiệm (2.6) có hội tụ tới nghiệm (2.1) α, δj → hay khơng? Trong [9], ổn định chứng minh trường hợp N = Để thuận tiện cho người đọc trả lời hai câu hỏi ta chứng minh trường hợp N tùy ý với N ≥ δ δ Định lý 2.1 Cho α > 0, fj jk → fj j với δj ≥ 0, k → ∞, xk δ δ cực tiểu (2.6) với fj j thay fj jk Khi dãy lặp {xk } hội tụ tới cực tiểu (2.6) Chứng minh Rõ ràng, xδα nghiệm (2.6) nghiệm phương trình Bx + α(x − x∗ ) = f˜δ , (2.7) N N A∗j Aj B= δ f˜δ = j=1 A∗j fj j , j=1 δ δ A∗j ánh xạ liên hợp Aj Vì fj jk → fj j nên suy N f˜δk N δ k A∗j fj j = δ → f˜δ = j=1 A∗j fj j j=1 k → ∞ Gọi xδk α nghiệm phương trình N Bx + α(x − x∗ ) = f˜δk , δ k f˜δk = A∗j fj j j=1 Footer Page 24 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ (2.8) Header Page 25 of 126 24 Từ (2.7), (2.8) tính chất đơn điệu B suy δ xδk α − xα X ≤ f˜δk − f˜δ X /α, δ với α > Nên với f˜δk → f˜δ xδk α → xα k → ∞ Định lý chứng minh Hơn nữa, khơng tính tổng qt, giả định δj = δ, δ → Định lý 2.2 Cho α(δ) tham số hiệu chỉnh cho α(δ) → 0, δ/α(δ) → δ → 0, δ → 0, α = α(δ) Khi dãy {xδα }, hội tụ tới nghiệm x˜ có x∗ - chuẩn nhỏ (2.1) xδα nghiệm (2.6), Chứng minh Với y ∈ S, ta có N By = f˜, f˜ = A∗j fj (2.9) j=1 Bởi vậy, từ (2.7) (2.9), ta thu Bxδα − By, xδα − y + α xδα − x∗ , xδα − y = f˜δ − f˜, xδα − y Kết hợp với tính chất đơn điệu B ta suy N xδα −y X ≤ x∗ − y X A∗j + (Yj∗ →X) j=1 δ α ∀y ∈ S (2.10) Vì Aj ánh xạ tuyến tính giới nội δ/α(δ) → 0, suy dãy {xδα(δ) } k giới nội, nên tồn dãy {xk := xδα(δ } dãy {xδα(δ) } hội tụ k) yếu tới phần tử x˜ ∈ X k → ∞ Bây giờ, chứng minh x˜ ∈ S Thật vậy, từ (2.6) ta có bất đẳng thức sau N Al xk − flδk 2Yl Aj xk − fjδk ≤ Yj j=1 N Aj y − fjδk ≤ Yj + α(δk ) y − x∗ X j=1 ≤ N δk2 + α(δk ) y − x∗ Footer Page 25 of 126 Số hóa trung tâm học liệu X, http://www.lrc.tnu.edu.vn/ Header Page 26 of 126 25 với y y ∈ S l = 1, , N Vì phiếm hàm Al x − flδk nửa liên tục yếu x [11], xk x˜ δk , α(δk ) → k → ∞, nên ta suy Al x˜ = fl , l = 1, , N Vì vậy, x˜ ∈ S Bây giờ, từ (2.10), δ/α(δ) → 0, δ → 0, tính chất nửa liên tục yếu chuẩn, tính chất tập lồi đóng H có điểm có x∗ -chuẩn nhỏ nhất, xδα(δ) → x˜ δ → Ta điều phải chứng minh Định lý 2.3 Giả sử tồn ω ∈ Y1 cho x˜ − x∗ = A∗1 ω, với cách chọn tham số hiệu chỉnh α ∼ δ p , < p < 1, ta có xδα(δ) − x˜ X = O(δ p/2 ) Chứng minh Sử dụng (2.6) với x = x˜ δj = δ cho j = 1, , N , ta thu N Aj xδα(δ) − fjδ Yj + α(δ) xδα(δ) − x∗ X j=1 N Aj x˜ − fjδ ≤ Yj + α(δ) x˜ − x∗ X j=1 Vì vậy, ta có N Aj xδα(δ) ) − fjδ Yj + α(δ) xδα(δ) − x˜ X ≤ N δ2 j=1 + α(δ)( x˜ − x∗ X − xδα(δ) − x∗ X X + xδα(δ) − x˜ X + xδα(δ) − x˜ X ) Do x˜ − x∗ − xδα(δ) − x∗ Footer Page 26 of 126 Số hóa trung tâm học liệu X = x˜ − x∗ , x˜ − xδα(δ) , http://www.lrc.tnu.edu.vn/ Header Page 27 of 126 26 suy A1 xδα(δ) − f1δ Y1 + α(δ) xδα(δ) − x˜ X ≤ N δ2 + 2α(δ) ω, A1 (˜ x − xδα(δ) ) (2.11) ≤ N δ + 2α(δ) ω, f1 − f1δ + f1δ − A1 xδα(δ) ≤ N δ + 2α(δ) ω Y1 (δ + A1 xδα(δ) − f1δ Y1 ) Hay A1 xδα(δ) − f1δ Y1 + α(δ) xδα(δ) − x˜ + 2α(δ) ω Y1 δ X + 2α(δ) ω ≤ N δ2 Y1 A1 xδα(δ) − f1δ (2.12) Y1 Áp dụng bất đẳng thức (a, b, c ≥ 0, a2 ≤ ab + c2 ) ⇒ a ≤ b + c ta thu 1/2 A1 xδα(δ) − f1δ Y1 ≤ Nδ + ω Y1 α(δ)δ +2 ω Y1 α(δ) cuối ta có xδα(δ) − x˜ X = O(δ p/2 ), α(δ) ∼ δ p , < p < 2.3 Một số ví dụ Để minh họa, ta xét ví dụ sau việc tìm nghiệm hệ phương trình đại số tuyến tính Aj x = fj , j = 1, 2, (2.13)         −1 −2 −1 −2 A1 = 2  , A2 = −2  , f1 = 3 , f2 = −1 −1 −1 −1 −3 Footer Page 27 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 28 of 126 27 Dễ dàng nhận thấy hệ (2.13) có nghiệm x˜ = (1; 1; 1) Từ det A1 = det A2 = 0, phương trình (2.13) đặt khơng chỉnh dựa kết phần 2, nghiệm chung (2.13) tìm cách tìm nghiệm tốn tối ưu khơng ràng buộc min3 x∈R x = A1 x − f1 + A2 x − f2 + α x − x∗ , (2.14) x2i + x22 + x23 với x = (x1 ; x2 ; x3 ) ∈ R3 Dễ thấy (2.14) tương đương với phương trình sau Bx + α(x − x∗ ) = f˜, (2.15)     20 26 ∗ ∗ ∗ ∗ B = A1 A1 + A2 A2 =  14 1 , f˜ = A1 f1 + A2 f2 = 20 , 1 x∗ véc tơ R3 Từ det B = 996 (2.15) thấy coi (2.15) phương trình hiệu chỉnh cho phương trình tuyến tính Bx = f˜, sử dụng phương pháp lặp Jacoby Gauss-Seidel ta nghiệm xα (2.15) Theo Bảng ta thấy kết tính tốn cho nghiệm xấp xỉ xα = (xα1 ; xα2 ; xα3 ) bước lặp thứ 15 với điểm bắt đầu x0 = (2, 2, 2) • Bảng 15 bước lặp xấp xỉ với điểm bắt đầu x0 = (2; 2; 2) α xα1 xα2 xα3 0.1000 0.9973 0.9955 0.9974 0.0100 0.9997 0.9995 0.9977 0.0010 1.000 1.0000 0.9998 0.0001 1.0000 1.0000 1.0000 x˜ − xα 0.0232 0.0024 0.0002 0.0000 Bây giờ, đưa ví dụ khác với det B = Chúng ta xét Footer Page 28 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 29 of 126 28 trường hợp     0.1 −0.2 0.1 −0.1 0.1 0.2 −0.1 0.1 0.2 −0.1 0.0 0.2     , A2 =  0.2 −0.1 0.0 0.2 , A1 =  0.3 −0.3 0.1 0.1   0.0 0.3 −0.2 0.4 0.1 0.1 −0.1 0.3 −0.1 0.5 −0.3 0.5     −0.1 0.3  0.3  0.3    f1 =   0.2  , f2 = 0.5 0.4 0.6 Khi đó,     0.21 −0.17 0.05 0.09 0.18 −0.17 0.54 −0.29 0.37     , f˜ =  0.45  B=  0.05 −0.29 0.17 −0.27 −0.34 0.09 0.37 −0.27 0.61 0.80 Từ hạng ma trận B = 3, khơng q khó khăn để chứng minh nghiệm (2.13) đường thẳng qua hai điểm x˜ = (1; 1; 1; 1) x = (1; 3; 6; 2) Vì vậy, nghiệm có chuẩn nhỏ x˜ = (1; 7/15; −1/3; 11/15) ≈ (1; 0.466667; −0.333333; 0.733333) Bảng cho ta thấy kết tính tốn với δ = 10−n Để tìm nghiệm phương trình (2.15) với f˜ thay f˜δ cách sử dụng quy tắc lặp [2] x(k+1) = x(k) − αk (Bx(k) + εk (x(k) − x(0) ) − f˜δ ), x(0) ∈ R4 bất kỳ, với quy tắc dừng [3]: Bx(K) − f˜δ ≤ τ δ < Bx(k) − f˜δ , τ > 1, cho k = 1, , K −1 δ Trong ví dụ, có L = B = 1.1847 Ta chọn ε0 = 0.1 εk+1 = εk /(1 + ε3k ) Thì, dãy {εk } thoả mãn điều kiện: εk > 0, εk (εk − εk+1 )/(ε3k εk+1 ) = λ = (ε0 + L2 )/2 = Footer Page 29 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 30 of 126 29 0.7068 Bằng cách đặt αk = cεk với c = 1/(2λ) = 0.7075 có (1 − cλ)cε20 = 0.0035 < Rõ ràng, điều kiện (2.12) [2] tương đương với x˜ − x(0) [(1 + ε30 )(1 + ε20 ) + 2ε0 ] +1 (1 − cλ − 2(ε0 /c))ε0 τ≥ Vì vậy, với x(0) = (0; 0; 0; 0), ta có x˜ − x(0) = x˜ = 1.3663, τ ≥ 94.5933 • Bảng Bảng xấp xỉ nghiệm x(0) = (0; 0; 0; 0), τ = 100 δ = 10−n , n = 1, 2, · · · n K 19 123 17452 694405 24868554 (K) x1 0.01337 0.02337 0.47880 0.70121 0.85935 0.94756 (K) x2 0.03212 0.25683 0.21716 0.29095 0.37766 0.43269 Footer Page 30 of 126 Số hóa trung tâm học liệu (K) x3 -0.02441 -0.22184 -0.25959 -0.28953 -0.31246 -0.32551 (K) x4 0.05780 0.59552 0.86361 0.86577 0.80696 0.76217 B − f˜δ 1.1857 0.94057 0.31553 0.09222 0.03162 0.00999 0.00316 http://www.lrc.tnu.edu.vn/ τδ 10 0.1 0.01 0.001 0.0001 0.00001 Header Page 31 of 126 30 Kết luận Luận văn trình bày đến vấn đề sau : Trình bày số khái niệm giải tích hàm khái niệm khơng gian, tốn tử tuyến tính Cực tiểu phiếm hàm Tikhonov Giới thiệu phương pháp hiệu chỉnh thuật tốn hiệu chỉnh tìm nghiệm chung cho hệ phương trình tốn tử tuyến tính giới nội Ngồi ra, luận văn trình bày số ví dụ cụ thể để minh hoạ cho phương pháp hiệu chỉnh tìm nghiệm cho hệ phương trình tốn tử tuyến tính giới nội đưa Các vấn đề nghiên cứu dựa kết GS-TS Nguyễn Bường nghiên cứu sinh Nguyễn Đình Dũng tháng năm 2011 Footer Page 31 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 32 of 126 31 Tài liệu tham khảo [1] Phạm Kì Anh-Nguyễn Bường, Bài tốn đặt khơng chỉnh Nhà xuất Đại học Quốc gia Hà Nội (2009) [2] A.B Bakushinsky, A Goncharsky, Ill-posed problems: Theory and Applications, Kluwer Academic 1994 [3] A.B Bakushinsky and A Smirnova, A posteriori stopping rule for regularized fixed point iterations, Nonl Anal.64 1255-1261 (2006) [4] M Burger and B Kaltenbacher, Regularization Newton-Kaczmarz methods for nonlinear ill-posed problems, SIAM J Numer Analysis, 44 153-182 (2006) [5] Nguyễn Bường Nguyễn Đình Dũng, Regularization for a common solution of a system of ill - posed equations involving linear bounded mappings, Applied Mathematical Sciences, Vol 76 (5) 3781-3788 (2011) [6] Nguyễn Bường, Regularization for unconstrained vector optimization of convex functionals in Banach spaces, Zh Vychisl Mat i Mat Fiziki, 46(3) 372-378 (2006) [7] A.D Cezaro, M Haltmeier, A Leitao, and O Scherzer, On steepestdescent-Kaczmarz method for regularizing systems of nonlinear illposed equations, Applied Mathematics and Computations, 202 (2) 596-607 (2008) [8] M Haltmeier, R Kowar, A Leitao, and O Scherzer, Kaczmarz methods for nonlinear ill-posed equations I: convergence analysis, Inverse problem and Imaging, (2) 289-298 (2007) II: Applications, (3) 507-523 (2007) Footer Page 32 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ Header Page 33 of 126 32 [9] H.W Engl, K Kunisch, and A Neubauer, Convergence rates for Tikhonov regularization of non-linear ill-posed problems, Inverse Problems 523-540 (1989) [10] A.N Tikhonov and V.Y Arsenin, Solutions of ill-posed problems, Wiley, New York 1977 [11] M.M Vainberg, Variational method and method of monotone mappings, Moscow, Nauka 1972 (in Russian) Footer Page 33 of 126 Số hóa trung tâm học liệu http://www.lrc.tnu.edu.vn/ ... Dũng đưa phương pháp chung để giải hệ phương trình tốn tử tuyến tính giới nội Mục đích luận văn trình bày phương pháp hiệu chỉnh tìm nghiệm chung cho hệ phương trình tốn tử tuyến tính giới nội đưa... tìm nghiệm chung cho hệ phương trình tốn tử tuyến tính giới nội Ngồi ra, luận văn trình bày số ví dụ cụ thể để minh hoạ cho phương pháp hiệu chỉnh tìm nghiệm cho hệ phương trình tốn tử tuyến tính. .. gồm chương Chương Giới thiệu phương pháp hiệu chỉnh số khái niệm liên quan Chương Trình bày phương pháp hiệu chỉnh tìm nghiệm chung cho họ phương trình tốn tử tuyến tính giới nội Luận văn hồn