Tài liệu Nghiên cứu một số phương pháp nội suy và sấp xỉ hàm số

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐÀM VĂN MẠNH NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP NỘI SUY VÀ XẤP XỈ HÀM SỐ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2013 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP NỘI SUY VÀ XẤP XỈ HÀM SỐ LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành : PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số : 60 46 46 NGƯỜI HƯỚNG DẪN KHOA HỌC: TS ĐẶNG THỊ OANH THÁI NGUYÊN - 2013 Soá hoùa bôûi trung taâm hoïc lieäu 1 http://www.lrc.tnu.edu.vn/ Mục lục Bảng ký hiệu 5 Danh mục bảng và hình vẽ 6 1 Kiến thức cơ sở 1.1 Hệ phương trình đại số tuyến tính . . . . . . . . . . . . . . 1.2 Một số phương pháp giải hệ phương trình đại số tuyến tính 1.2.1 Chuẩn của ma trận, chuẩn của vectơ . . . . . . . . 1.2.2 Phương pháp Gauss (Phương pháp khử) . . . . . . . 1.2.3 Phương pháp lặp đơn (phương pháp lặp Jacobi) . . . 1.3 Bài toán nội suy hàm số . . . . . . . . . . . . . . . . . . . 1.3.1 Bài toán nội suy hàm số . . . . . . . . . . . . . . . 1.3.2 Sự tồn tại duy nhất của đa thức nội suy . . . . . . . 1.4 Khái niệm sai phân và tỉ sai phân . . . . . . . . . . . . . . 1.4.1 Sai phân . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Tỉ sai phân . . . . . . . . . . . . . . . . . . . . . . . 1.5 Cơ sở của bài toán nội suy với dữ liệu phân tán . . . . . . . 1.5.1 Nội suy hàm số với dữ liệu phân tán . . . . . . . . . 1.5.2 Ma trận xác định dương . . . . . . . . . . . . . . . . 1.5.3 Hàm xác định dương . . . . . . . . . . . . . . . . . 1.5.4 Hàm cơ sở bán kính . . . . . . . . . . . . . . . . . . 1.5.5 Hàm bán kính xác định dương . . . . . . . . . . . . 9 9 10 10 11 14 16 16 16 16 16 17 19 19 20 20 21 21 2 Một số phương pháp nội suy và xấp xỉ hàm số 2.1 Phương pháp nội suy Lagrange . . . . . . . . . . 2.1.1 Thiết lập đa thức nội suy Lagrange . . . 2.1.2 Đánh giá sai số đa thức nội suy Lagrange 2.2 Chọn mốc nội suy tối ưu . . . . . . . . . . . . . 2.2.1 Đa thức Chebyshev . . . . . . . . . . . . 2.2.2 Chọn các mốc nội suy tối ưu . . . . . . . 2.3 Phương pháp nội suy Newton . . . . . . . . . . . 2.3.1 Nội suy trên lưới không đều . . . . . . . . 22 22 22 23 25 25 26 27 27 Soá hoùa bôûi trung taâm hoïc lieäu 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . http://www.lrc.tnu.edu.vn/ 2.4 2.5 2.6 2.3.2 Nội suy trên lưới cách đều . . . . . . . . . . . . . . Phương pháp bình phương bé nhất . . . . . . . . . . . . . . 2.4.1 Trường hợp y phụ thuộc tuyến tính vào các tham số 2.4.2 Trường hợp y phụ thuộc phi tuyến vào các tham số . Phương pháp nội suy RBF . . . . . . . . . . . . . . . . . . 2.5.1 Nội suy hàm cơ sở bán kính (RBF) . . . . . . . . . . 2.5.2 Vấn đề tham số hình dạng tối ưu đối với nội suy hàm cơ sở bán kinh (RBF) . . . . . . . . . . . . . . . . . 2.5.3 Nội suy với độ chính xác đa thức . . . . . . . . . . . 2.5.4 Sai số, ổn định và hội tụ của hàm nội suy theo bán kính . . . . . . . . . . . . . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Ứng dụng của phương pháp nội suy 3.1 Tính đạo hàm . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Tính tích phân số . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Công thức hình chữ nhật trung tâm . . . . . . . . . 3.2.2 Công thức hình thang . . . . . . . . . . . . . . . . . 3.2.3 Công thức Simson (công thức Parabol) . . . . . . . 3.2.4 Công thức cầu phương Gauss . . . . . . . . . . . . . 3.2.5 Công thức Newton - Cotet . . . . . . . . . . . . . . 3.3 Giải phương trình vi phân thường . . . . . . . . . . . . . . 3.3.1 Bài toán Cauchy . . . . . . . . . . . . . . . . . . . . 3.3.2 Phương pháp Euler . . . . . . . . . . . . . . . . . . 3.3.3 Phương pháp Euler-Cauchy . . . . . . . . . . . . . . 3.3.4 Phương pháp Runge-Kutta . . . . . . . . . . . . . . 3.3.5 Vấn đề xác định nghiệm gần đúng với sai số cho trước 3.4 Ứng dụng nội suy RBF . . . . . . . . . . . . . . . . . . . . 3.4.1 Bài toán Dirichlet với phương trình Poisson trong miền giới nội Ω ⊂ Rd và vectơ trọng số . . . . . . . 3.4.2 Vectơ trọng số từ nội suy hàm cơ sở bán kính . . . . 3.4.3 Lược đồ RBF – FD giải phương trình poisson . . . . 29 30 31 33 34 34 36 36 37 39 40 40 42 42 44 46 48 50 51 51 52 54 55 57 58 58 59 61 Kết luận 62 Tài liệu tham khảo 63 Soá hoùa bôûi trung taâm hoïc lieäu 3 http://www.lrc.tnu.edu.vn/ LỜI CẢM ƠN Trong quá trình hoàn thành luận văn "Nghiên cứu một số phương pháp nội suy và xấp xỉ hàm số" tôi đã nhận được sự hướng dẫn, giúp đỡ, động viên của những cá nhân và tập thể. Tôi xin bày tỏ lòng biết ơn sâu sắc tới tất cả các cá nhân và tập thể đã tạo điều kiện và giúp đỡ tôi trong quá trình học tập và nghiên cứu. Trước hết tôi xin cảm ơn Ban giám hiệu nhà trường, các thầy cô Trường Đại học khoa học – ĐHTN, các thầy cô giáo Viện toán học Việt Nam đã tạo mọi điều kiện giúp đỡ tôi hoàn thành chương trình học tập và nghiên cứu. Có được kết quả này tôi vô cùng biết ơn và tỏ lòng kính trọng sâu sắc đối với TS Đặng Thị Oanh – Giảng viên Trường Đại học công nghệ thông tin và truyền thông – ĐHTN người đã tận tình hướng dẫn, giúp đỡ tôi trong suốt quá trình thực hiện luận văn này. Tôi cũng xin cảm ơn bạn bè, đồng nghiệp và những người thân trong gia đình đã động viên, chia sẻ, giúp tôi vượt qua những khó khăn trong quá trình học tập và nghiên cứu. Thái Nguyên, ngày 20 tháng 08 năm 2013 Người thực hiện Đàm Văn Mạnh Soá hoùa bôûi trung taâm hoïc lieäu 4 http://www.lrc.tnu.edu.vn/ Bảng ký hiệu const RBF Gauss MQ IM Q Mk E ||A|| ∀x ∃x ∈ ∆ ∇ Ln (x) f (xi , xi+1 , ..., xi+n ) Pf Rd Rn (x) max min ICN Iht Isim Ξ Ξint ∂Ξ Σ Q Ω hx, yi NΦ (Ω) Cond(A) Hằng số Radianl Basis Funtion Hàm Gaussian Hàm Multiquadric Hàm Inverse Multiquadric Giá trị lớn nhất của đạo hàm cấp k Sai số tích phân Chuẩn của A Với mọi x Tồn tại x thuộc Sai phân tiến Sai phân lùi Đa thức nội suy bậc không quá n Tỉ sai phân cấp n của hàm f (x) tại các điểm xi , xi+1 , ..., xi+n Hàm xấp xỉ hàm f Không gian thực d chiều Sai số đa thức nội suy bậc không quá n Giá trị lớn nhất Giá trị nhỏ nhất Xấp xỉ tích phân xác định bằng công thức hình chữ nhật trung tâm Xấp xỉ tích phân xác định bằng công thức hình thang Xấp xỉ tích phân xác định bằng công thức sim son Bộ tâm phân tán Tập các tâm nằm trong Tập các tâm nằm trên biên Tổng Tích Bao đóng tập Ω Tích vô hướng của x và y Không gian được sinh bởi Φ Số điều kiện của ma trận A Soá hoùa bôûi trung taâm hoïc lieäu 5 http://www.lrc.tnu.edu.vn/ Danh mục bảng và hình vẽ Bảng 1.1 Bảng tỉ sai phân Bảng 1.2 Bảng một số hàm cơ sở bán kính với tham số hình dạng ε>0 Hình 2.1 Hình biểu diễn các điểm M (ti , log k) trong hệ trục Oxy Hình 2.2 Đồ thị hàm cơ sở bán kính Gauss Hình 2.3 Đồ thị hàm cơ sở bán kính MQ Hình 2.4 Đồ thị hàm cơ sở bán kính IMQ Hình 2.5 Đồ thị hàm cơ sở bán kính Côsi (CauChy) Hình 3.1 Hình biểu diễn xấp xỉ hình thang cong bởi các hình chữ nhật trung tâm trên mỗi đoạn chia Hình 3.2 Biểu diễn xấp xỉ hình thang cong bởi hình thang trên mỗi đoạn chia Soá hoùa bôûi trung taâm hoïc lieäu 6 http://www.lrc.tnu.edu.vn/ Mở đầu Bài toán nội suy và xấp xỉ hàm số có vị trí đặc biệt quan trọng trong toán học không chỉ như là những đối tượng để nghiên cứu mà còn đóng vai trò như là một công cụ đắc lực của các mô hình liên tục cũng như các mô hình rời rạc của giải tích trong lý thuyết phương trình, lý thuyết xấp xỉ, lý thuyết biểu diễn nghiệm [5]. Bài toán nội suy được mô tả như sau [4]: Cho D ⊂ Rn , đối với hàm số f : D → Rm đã xác định được một  N tập dữ liệu xk , y k k=1 trong đó xk ∈ Rn , y k ∈ Rm (k = 1, ..., N ) và f (xk ) = y k (∀k = 1, ..., N ), hàm số f có thể chưa xác định được biểu thức giải tích hoặc biểu thức giải tích quá phức tạp đối với yêu cầu đặt ra cho bài toán. Cần tìm tìm hàm Pf “đủ tốt” có biểu thức giải tích cụ thể thỏa mãn hệ điều kiện P f (xk ) = y k (∀k = 1, ..., N ), và tại những điểm x ∈ D không trùng với xk thì P f (x) ≈ f (x). Từ lâu các nhà toán học đã quan tâm đến việc xây dựng các phương pháp, thuật toán nội suy cũng như tìm kiếm các ứng dụng của nó trong thực tiễn. Một số phương pháp nội suy đã tìm được nhiều ứng dụng phải kể đến như: phương pháp nội suy Lagrange, phương pháp nội suy Newton, phương pháp nội suy hàm cơ sở bán kính (Radial Basis Function – RBF), phương pháp bình phương bé nhất. Sử dụng hàm đa thức làm hàm nội suy cùng với thuật toán đơn giản, hai phương pháp nôi suy Lagrange và phương pháp Newton đã giải quyết khá đầy đủ bài toán nội suy hàm một biến. Đối với bài toán nội suy hàm nhiều biến cả hai phương pháp này đều cho thấy sự phức tạp trong thuật toán và kết quả không tốt. Phương pháp nội suy RBF là một phương pháp nội suy dựa trên các hàm cơ sở bán kính và được đề xuất bởi Powell vào năm 1987. Thuật toán được sử dụng trong phương pháp là phức tạp, khối lượng tính toán lớn nhưng kết quả thu được là tốt, đặc biệt trong các bài toán nội suy hàn nhiều biến. Việc giải quyết các yêu cầu của bài toán trên hàm một biến thường đơn giản hơn rất nhiều khi thực hiện trên hàm nhiều biến, vì thế ưu thế lớn nhất của phương pháp là chuyển bài toán hàm nhiều biến về bài toán của hàm một biến. Các bài toán thực tiễn như: Bài toán dự báo Soá hoùa bôûi trung taâm hoïc lieäu 7 http://www.lrc.tnu.edu.vn/ thời tiết, trí tuệ nhân tạo, trắc địa, giải số phương trình vi phân, khôi phục hình ảnh, mạng nơron nhân tạo, nhận dạng chữ viết tay, . . . là những bài toán trong không gian nhiều chiều. Việc giải quyết những bài toán này cần đến những phương pháp nội suy hàm nhiều biến. Một số công trình nghiên cứu của Đặng Thị Thu Hiền, Trần Đức Thụ, Lê Tiến Mười,. . . cho thấy: Sử dụng nội suy bằng hàm cơ sở bán kính (Radial Basis Function-RBF) khi giải quyết các bài toán trên cho kết quả tốt. Phương pháp cho thấy sự độc lập của nó đối với sự phân bố của các nút nội suy. Vì vậy đây là một phương pháp nội suy phù hợp với các nút nội suy phân tán. Mặc dù khối lượng tính toán lớn, nhưng với sự phát triển mạnh mẽ của máy tính điện tử, hiện nay phương pháp nội suy RBF đã được ứng dụng cho nhiều bài toán trong nhiều lĩnh vực. Trong luận văn này chúng tôi trình bày một số phương pháp nội suy và xấp xỉ hàm số và một số ứng dụng của chúng. Nội dung luận văn bao gồm: Chương 1: Kiến thức cơ sở Nội dung của chương là hệ thống các kiến thức cơ sở cho các phương pháp nội suy và xấp xỉ hàm số như: Hệ phương trình đại số tuyến tính và một số phương pháp giải, khái niệm bài toán nội suy, khái niệm sai phân, tỉ sai phân, cơ sở của bài toán nội suy với dữ liệu phân tán Chương 2: Một số phương pháp nội suy và xấp xỉ hàm số Nội dung của chương bao gồm: phương pháp nội suy Lagrange, phương pháp nội suy Newton, phương pháp nội suy RBF và phương pháp bình phương bé nhất. Chương 3: Ứng dụng phương pháp nội suy Trong chương này chúng tôi trình bày một số ứng dụng của phương pháp nội suy như: tính đạo hàm, tính tích phân số, giải phương trình vi phân thường và giải phương trình poisson trên miền giới nội với biên Dirichlet. Soá hoùa bôûi trung taâm hoïc lieäu 8 http://www.lrc.tnu.edu.vn/ Chương 1 Kiến thức cơ sở Trong chương này chúng tôi trình bày một số kiến thức cơ sở cho bài toán nội suy và xấp xỉ hàm số, khái niệm hệ phương trình đại số tuyến tính và một số phương pháp giải như: phương pháp Gauss, phương pháp lặp đơn. Các khái niệm nội suy như: bài toán nội suy hàm số, sự tồn tại duy nhất của đa thức nội suy hàm một biến, khái niệm nội suy với dữ liệu phân tán, ma trận xác định dương, hàm xác định dương, hàm bán kính, hàm cơ sở bán kính. 1.1 Hệ phương trình đại số tuyến tính Hệ phương trình đại số tuyến tính n ẩn là hệ có dạng Ax = b (1.1) trong đó  a11  a21 A =  ... an1 a12 a22 ... an2 ... ... ... ...   a1n a2n   ; b =   ... ann   b1  b2  ; x =   ... bn  x1 x2  ...  xn Với aij ; bi (i = 1, n, j = 1, n) là những số thực đã biết, xi (i = 1, n) là ẩn số phải tìm, A là ma trận hệ số. Nếu ma trận A không suy biến nghĩa là detA 6= 0 thì hệ (1.1) có nghiệm duy nhất x = A−1 b. Soá hoùa bôûi trung taâm hoïc lieäu 9 http://www.lrc.tnu.edu.vn/ 1.2 Một số phương pháp giải hệ phương trình đại số tuyến tính 1.2.1 Chuẩn của ma trận, chuẩn của vectơ a) Chuẩn của ma trận [1]  a11 a12  a21 a22 Cho ma trận A =  ... ... an1 an2 Chuẩn của ma trận A là một số sau:  ... a1n ... a2n  ... ...  . ... ann thực ký hiệu là ||A|| thỏa mãn điều kiện i) ||A|| ≥ 0; ||A|| = 0 ⇔ A = 0; ii) ||αA|| = |α|.||A|| với α là một số thực và || − A|| = ||A||; iii)||A + B|| ≤ ||A|| + ||B||; 4i) ||A.B|| ≤ ||A||.||B||. trong đó B là ma trận cấp m × n. Ta thường dùng các chuẩn sau: ||A||1 = Max X j |aij | chuẩn cột. (1.2) i   12 X 2  ||A||2 = |aij |  chuẩn Ơclit. (1.3) i,j ||A||∞ = M ax i X |aij | chuẩn hàng. (1.4) j b) Chuẩn vectơ [1] Trong Rn cho vectơ x = (x1 , x2 , ..., xn ) ta có thể biểu diễn x là ma trận chỉ có một cột   x1 x  x =  ...2  xn Ta có ||x||1 = n X |xi | (1.5) i=1 Soá hoùa bôûi trung taâm hoïc lieäu 10 http://www.lrc.tnu.edu.vn/ ||x||2 = n X ! 12 |xi |2 (1.6) i=1 ||x||∞ = max |xi | (1.7) i 1.2.2 Phương pháp Gauss (Phương pháp khử) a) Nội dung phương pháp Xét hệ phương trình đại số tuyến tính   a (0) x + a12 (0) x2 + ... + a1n (0) xn = b1 (0)   11 (0) 1 a21 x1 + a22 (0) x2 + ... + a2n (0) xn = b2 (0) ...........................................    an1 (0) x1 + an2 (0) x2 + ... + ann (0) xn = bn (0) (1.8) Thực hiện khử dần các ẩn số trong hệ phương trình (1.8) để đưa hệ về dạng hệ "tam giác" tương đương  (1) (1) (1) (1)   x1 + a22 x2 + a23 x3 + ... + a2n xn = b1 (2) (2) (2) x2 + a23 x3 + ... + a2n xn = b2   (n) xn = bn • Quá trình khử các ẩn số (quá trình thuận) (0) (0) Khử x1 : Giả sử a11 6= 0 (a11 gọi là trụ thứ nhất. (0) Chia cả hai vế của phương trình thứ nhất trong (1.8) cho a11 ta được phương trình (1) (1) (1) x1 + a12 x2 + ... + a1n xn = b1 (1.9) Với (1) a1j a01j = ; j = 2, 3, ..., n. a11 Dùng phương trình (1.9) khử x1 trong n − 1 phương trình còn lại của (1.8) ta được hệ phương trình  (1) (1) (1)  a22 x2 + a(1) 23 x3 + ... + a2n xn = b2 ....... (1.10)  (1) (1) an2 x2 + an3 x3 + ... + ann (1) xn = bn (1) (1) (0) (0) (1) (1) (0) (0) (1) Với aij = aij −ai1 a1j , i = 2, 3, ..., n; j = 2, 3, ..., n và bi = bi −b1 a1j . (1) (1) Khử x2 : Giả sử a22 6= 0 (a22 gọi là trụ đứng thứ hai). (1) Chia cả hai vế của phương thứ nhất của (1.10) cho a12 ta được (2) (2) (2) x2 + a23 x3 + ... + a2n xn = b2 Soá hoùa bôûi trung taâm hoïc lieäu 11 (1.11) http://www.lrc.tnu.edu.vn/ (1) trong đó (2) a2j = a2j (1) a22 (1) ; (2) b2 = b2 (1) a22 với j = 2, 4, 5, ..., n. Sử dụng (1.11) khử x2 trong n − 2 phương trình còn lại của (1.10) quá (n) trình tiến hành cho đến khi ta được một phương trình xn = bn với các (0) (1) (2) (n−1) trụ a11 ; a22 ; a33 ; ...; ann khác không. Thì hệ (1.8) tương đương với hệ phương trình "tam giác" sau  (1) (1) (1) (1)  x1 + a12 x2 + a13 x3 + ... + a1n xn = b1   (2) (2) (2) x2 + a23 x3 + ... + a2n xn = b2 (1.12) ...    (n) xn = bn • Quá trình tìm ẩn (quá trình ngược) Giải hệ (1.12) từ dưới lên trên ta tìm được  (n)  xn = bn   (n−1) (n−1) xn−1 = bn−2 − an−1n xn ...    (1) (1) (1) (1) x1 = b1 − a12 x2 − a13 x3 − ... − a1n xn Chú ý rằng điều kiện áp dụng phương pháp Gauss là các phần tử trụ là khác không. Phân tích quá trình áp dụng phương pháp Gauss ta thấy để đưa hệ (1.1) (k) về hệ tam giác tương đương ta chỉ cần tính các hệ số aij . b) Khối lượng tính Căn cứ vào những công thức tính của phương pháp Gauss ta đếm được Sn các phép toán cộng, trừ, nhân, chia trong đó có n(n − 1)(2n + 5) phép nhân. 6 n(n + 1) • phép chia. 2 n(n − 1)(2n + 5) • phép cộng hoặc trừ. 6 4n3 + 9n2 − 7n Vậy Sn = phép tính. (1.13) 6 So với phương pháp Cramer thì phương pháp Gauss có khối lượng tính toán ít hơn nhiều nhất là khi n lớn. Nếu ma trận hệ số của hệ phương trình đối xứng thì khối lượng tính giảm đi một nửa. • Soá hoùa bôûi trung taâm hoïc lieäu 12 http://www.lrc.tnu.edu.vn/ c) Sai số của phương pháp Gauss Nếu các phép tính cộng, trừ, nhân, chia là đúng hoàn toàn và không phải làm tròn thì phương pháp Gauss cho nghiệm đúng của hệ phương trình (1.1). Vì vậy phương pháp Gauss là một phương pháp đúng. tuy nhiên trong tính toán không tránh khỏi sai số làm tròn nên trong thực tế khi dùng phương pháp Gauss cũng chỉ cho ta nghiệm gần đúng. d) Phương pháp Gauss có trụ lớn nhất Một trong những hạn chế của phương pháp Gauss là phần tử trụ phải khác không. Khi có các phần tử trụ bằng không thì không thực hiện được bằng phương pháp Gauss. Mặt khác nếu định thức của ma trận hệ số khác không nhưng một vài phần tử trụ có giá trị tuyệt đối rất nhỏ so với các phần tử trong cùng hàng thì khi chia cho phần tử trụ sai số làm tròn ở các hệ số trong hàng là lớn. Vì thế nghiệm tìm được thiếu chính xác. Để khắc phục những hạn chế trên người ta thường dùng phương pháp Gauss có tìm trụ lớn nhất. Nội dung phương pháp như sau: • Khử x1 trong sơ đồ Gauss ta tìm số lớn nhất về giá trị tuyệt đối trong (0) (0) (0) các số a11 ; a21 ; ...; an1 làm trụ thứ nhất và hoán vị hàng chứa trụ lớn nhất thứ nhất với hàng thứ nhất. Trụ thứ nhất là số lớn nhất trong các hệ số của x1 quá trình khử x1 tiến hành như phương pháp Gauss. • Khử x2 trong hệ phương trình n − 1 ẩn thu được sau khi khử x1 , ta (1) (1) (1) tìm hệ số lớn nhất về trị tuyệt đối trong các số a22 ; a32 ; ...; an2 làm (1) trụ thứ hai và hoán vị hàng chứa trụ thứ hai về đúng vị trí a22 và tiến hành khử x2 như trong phương pháp Gauss. • Quá trình tiến hành như trên cho đến ẩn cuối cùng. f) Phương pháp Gauss - Gioocdang Phương pháp Gauss - Gioocdang có thể xem là một biến dạng của phương pháp Gauss. Để đơn giản cho việc trình bày ta xét hệ 3 phương trình 3 ẩn sau:  (0) (0) (0) (0)   a11 x1 + a12 x2 + a13 x3 = b1 (0) (0) (0) (0) (1.14) a21 x1 + a22 x2 + a23 x3 = b2   (0) (0) (0) (0) a31 x1 + a32 x2 + a33 x3 = b3 Soá hoùa bôûi trung taâm hoïc lieäu 13 http://www.lrc.tnu.edu.vn/ Nội dung phương pháp là khử dần các ẩn số đưa về hệ "chéo" tương đương  (3)  = b1  x1 (3) (1.15) x2 = b2   (3) x3 = b3 Phương pháp đưa (1.14) về (1.15) Bước 1: Khử x1 ở phương trình thứ hai và thứ ba ở (1.14) ta được hệ sau.  (1) (1) (1)   x1 + a12 x2 + a13 x3 = b1 (1) (1) (1) (1.16) a22 x2 + a23 x3 = b2   (1) (1) (1) a32 x2 + a33 x3 = b3 Bước 2: Khử x2 trong phương trình nhất và thứ ba của (1.16) ta được hệ phương trình sau.  (2) (2)  a13 x3 = b1  x1 + (2) (2) (1.17) x2 + a23 x3 = b2   (2) (2) a33 x3 = b3 Bước 3: Khử x3 trong phương trình thứ nhất và thứ hai trong (1.17) ta được hệ (1.15) Nhận xét: * Cách khử ẩn trong phương pháp Gauss - Gioocdang giống cách khử ẩn trong phương pháp Gauss. * Điều kiện áp dụng phương pháp Gauss - Gioocdang là các phần tử trụ (0) (1) (2) a11 , a22 , a33 phải khác không. 1.2.3 Phương pháp lặp đơn (phương pháp lặp Jacobi) Là phương pháp tìm nghiệm gần đúng của hệ phương trình đại số tuyến tính với độ chính xác cho trước a) Nội dung phương pháp Xét hệ phương trình: Ta đưa hệ về dạng Ax = b (1.1) x = β + αx. (1.18) trong đó   α11 α12 ... α1n α α ... α2n  α =  ...21 22  αn1 αn2 ... αnn Soá hoùa bôûi trung taâm hoïc lieäu 14 http://www.lrc.tnu.edu.vn/   β1 β  β =  ...2  βn sau đó chọn một vectơ xấp xỉ đầu x(0) (thường chọn x(0) = β ) và tính x(k+1) theo công thức x(k+1) = β + αx(k) , k = 0, 1, 2... (1.19) x(k) gọi là vectơ lặp thứ k. Nếu dãy x(0) , x(1) , ..., x(k) , ... có giới hạn là x∗ = lim x(k) k→+∞ thì giới hạn ấy là nghiệm đúng của hệ (1.18) và cũng là nghiệm đúng của (1.1). Thật vậy lim x(k+1) = lim (β + αx(k) ) = β + α lim x(k) k→+∞ k→+∞ hay x∗ = β + αx∗ . k→+∞ b) Sự hội tụ của phương pháp Người ta chứng minh được quá trình lặp đơn hội tụ đến nghiệm duy nhất của hệ (1.1)không phụ thuộc vào việc chọn x(0) ban đầu nếu ||α||p < 1 (1.20) (||α||p có thể dùng ||α||1 hoặc ||α||2 hoặc ||α||∞ ) c) Đánh giá sai số của nghiệm gần đúng Để đánh giá độ lệch giữa nghiệm gần đúng x(k) , nhận được bằng phương pháp lặp đơn và nghiệm đúng x∗ của hệ (1.1), người ta đã chứng minh được công thức sau: ||x(k) − x∗ ||p ≤ và ||x (k) ||α||p ||x(k) − x(k−1) ||p 1 − ||α||p (||α||p )k − x ||p ≤ ||x(1) − x(0) ||p 1 − ||α||p ∗ (1.21) (1.22) Sự hội tụ của phương pháp lặp đơn càng nhanh nếu ||α||p càng nhỏ. Công thức (1.22) cho phép xác định được số lần lặp cần tiến hành K() để nhận được nghiệm gần đúng x(k) với độ chính xác . 1 Trong trường hợp ||α||p ≤ đánh giá (1.21) có dạng đơn giản sau 2 ||x(k) − x∗ ||p ≤ ||x(k) − x(k−1) ||p . Soá hoùa bôûi trung taâm hoïc lieäu 15 http://www.lrc.tnu.edu.vn/ 1.3 Bài toán nội suy hàm số Trong thực tế, ta thường gặp những hàm số y = f (x) mà không biết biểu thức giải tích cụ thể của chúng. Thông thường ta chỉ biết các giá trị y0 , y1 , ..., yn của hàm số lần lượt tại các điểm khác nhau x0 , x1 , ..., xn của một đoạn [a; b], các giá trị này có thể nhận được trong quá trình thí nghiệm, đo đạc, .... Khi sử dụng hàm số trên nhiều khi ta cần biết giá trị hàm số tại một số điểm x 6= xi (i = 0, n) trên đoạn [a; b]. Vấn đề đưa ta đến bài toán sau: 1.3.1 Bài toán nội suy hàm số Bài toán 1.1 [5] Trên [a; b] cho n giá trị khác nhau x0 , x1 , ..., xn và biết giá trị của hàm số y = f (x) tương ứng tại các điểm xi là yi (i = 0, n) tức là ta có yi = f (xi ) (i = 0, n). Tìm đa thức Ln (x) có bậc không quá n. Thỏa mãn điều kiện Ln (x) = yi (i = 0, n) (1.23) Ln (x) gọi là đa thức nội suy của hàm f (x); các điểm xi (i = 0, n) gọi là các nút nội suy. 1.3.2 Sự tồn tại duy nhất của đa thức nội suy Định lý 1.3.1. Đa thức Ln (x) thỏa mãn điểu kiện của bài toán (1.1) nếu có thì duy nhất. Chứng minh. Giả sử từ những điều kiện (1.23) ta xây dựng được hai đa thức nội suy Ln (x) và Pn (x) với Pn (xi ) = Ln (xi ) = yi , (i = 0, n). Khi đó Q(x) = Ln (x) − Pn (x) là một đa thức có bậc không quá n. Vì Q(xi ) = Ln (xi ) − Pn (xi ) = 0, (i = 0, n) nên Q(x) có n + 1 nghiệm phân biệt. Điều này chỉ xảy ra khi Q(x) ≡ 0 hay Pn (x) ≡ Ln (x). Vậy Ln (x) là duy nhất. 1.4 1.4.1 Khái niệm sai phân và tỉ sai phân Sai phân a) Định nghĩa 1.4.1. [7] Cho hàm số y = f (x) xác định bởi bảng số sau x x0 x1 x2 ... xi xi+1 ... y y0 y1 y2 ... yi yi+1 ... Soá hoùa bôûi trung taâm hoïc lieäu 16 http://www.lrc.tnu.edu.vn/ trong đó yi = f (xi ), (i = 0, 1, 2, ...) Và các nút xi cách đều nhau 1 khoảng bằng h > 0 tức là xi = x0 + ih với i = 0, 1, 2, .... ∆yi = yi+1 − yi gọi là sai phân tiến cấp một của hàm f (x) tại điểm xi . ∆2 yi = ∆yi+1 − ∆yi gọi là sai phân tiến cấp hai của hàm số f (x) tại điểm xi . Tổng quát, ta có sai phân tiến cấp n của hàm số y = f (x) tại điểm xi là ∆n yi = ∆n−1 yi+1 − ∆n−1 yi . Ta định nghĩa sai phân lùi ∇yi = yi − yi−1 gọi là sai phân lùi cấp một của hàm f (x) tại điểm xi . ∇2 yi = ∇(∇yi ) = ∇yi+1 − ∇yi gọi là sai phân lùi cấp hai của hàm số f (x) tại điểm xi . Tổng quát, ta có sai phân lùi cấp n của hàm số y = f (x) tại điểm xi là ∇n yi = ∇(∇n−1 yi ) = ∇n−1 yi − ∇n−1 yi−1 . b) Tính chất: Tính chất 1: ∆(y1i + y2i ) = ∆yi + ∆y2i . Tính chất 2: ∆(αyi ) = α∆yi . Tính chất 3: Sai phân cấp m của đa thức bậc n có tính chất: i) Nếu m = n thì sai phân cấp m là hằng số. ii) Nếu m > n thì sai phân cấp m bằng 0. n Tính chất 4: Giả sử f ∈ C[a;b] và (xi ; xi + nh) ⊂ [a; b]. Khi đó ∆n yi = f (n) (xi + εnh) với ε ∈ (0; 1). n h Tính chất 5: Nếu f ∈ 1.4.2 n C[a;b] và khi h đủ nhỏ thì f (n) ∆n f (xi ) (xi ) ≈ . hn Tỉ sai phân a) Định nghĩa 1.4.2. [7] Cho hàm số y = f (x) xác định bởi bảng số sau x x0 x1 x2 ... xi xi+1 ... y y0 y1 y2 ... yi yi+1 ... trong đó yi = f (xi ), (i = 0, 1, 2, ...) và ∆xi = xi+1 − xi 6= 0, i = 0, 1, 2, ... f (xi+1 ) − f (xi ) yi+1 − yi Ta gọi f (xi , xi+1 ) = = ; (i = 1, 2, ....) là tỉ xi+1 − xi xi+1 − xi sai phân cấp 1 của hàm số y = f (x) tại điểm xi và xi+1 . f (xi , xi+1 , xi+2 ) = Soá hoùa bôûi trung taâm hoïc lieäu f (xi+1 , xi+2 ) − f (xi , xi+1 ) ; (i = 1, 2, ....) xi+2 − xi 17 http://www.lrc.tnu.edu.vn/ là tỉ sai phân cấp hai của hàm số y = f (x) tại điểm xi , xi+1 , xi+2 Tổng quát ta có tỉ sai phân cấp n của hàm số y = f (x) tại điểm xi , xi+1 , ..., xi+n được tính thông qua tỉ sai phân cấp n − 1 bằng công thức truy hồi sau f (xi , xi+1 , ..., xi+n ) = f (xi+1 , xi+2 , ..., xi+n ) − f (xi , xi+1 , ..., xi+n−1 ) xi+n − xi (n = 1, 2, ... và i = 0, 1, 2, ...). Thông thường trong thực hành ta thường dùng bảng sau để tính tỉ sai phân x y f (., .) f (., ., .) f (., ., ., .) f (., ., ., ., .) x0 y0 f (x0 , x1 ) x1 y1 f (x1 , x2 ) f (x0 , x1 , x2 ) x2 y2 f (x2 , x3 ) f (x1 , x2 , x3 ) f (x0 , x1 , x2 , x3 ) x3 y3 f (x3 , x4 ) f (x2 , x3 , x4 ) f (x1 , x2 , x3 , x4 ) f (x0 , x1 , x2 , x3 , x4 ) x4 y4 f (x3 , x4 ) Bảng 1.1: Bảng tỉ sai phân b) Tính chất Tính chất 1: Tỉ sai phân cấp k của tổng hai hàm số bằng tổng hai tỉ sai phân cùng cấp của hai hàm số đó. (f + g)(xi , xi+1 , ..., xi+k ) = f (xi , xi+1 , ..., xi+k ) + g(xi , xi+1 , ..., xi+k ). Tính chất 2: Tính chất đối xứng i) f (xi−1 , xi ) = f (xi , xi−1 ), (i = 1, n). ii) f (xi−2 , xi−1 , xi ) = f (xi , xi−1 , xi−2 ). iii)f (x0 , x1 , ..., xn ) = f (xn , xn−1 , ..., x0 ). Tính chất 3: i) Tỉ sai phân của hằng số bằng 0. ii) Tỉ sai phân cấp m của đa thức bậc n có tính chất Nếu m = n thì tỉ sai phân cấp m là hằng số Nếu m > n thì tỉ sai phân cấp m bằng không. c) Quan hệ giữa sai phân và tỉ sai phân Giả sử x1 , x2 , ..., xi , xi+1 , ... là các nút nội suy cách đều của hàm số Soá hoùa bôûi trung taâm hoïc lieäu 18 http://www.lrc.tnu.edu.vn/ y = f (x) và yi = f (xi )(i = 0, 1, 2, ...) là giá trị hàm số tương ứng tại xi . Khi đó ta có công thức liên hệ giữa sai phân và tỉ sai phân như sau: ∆y0 ∇y1 = . h h ∆2 y0 ∇ 2 y2 f (x0 , x1 , x2 ) = = . 2!h2 2!h2 ∆n y0 ∇n y n f (x0 , x1 , ..., xn ) = = . n!hn n!hn i) f (x0 , x1 ) = ii) iii) 1.5 1.5.1 Cơ sở của bài toán nội suy với dữ liệu phân tán Nội suy hàm số với dữ liệu phân tán Bài toán 1.2. [8] Cho bộ dữ liệu (xi ; yi ), i = 1, 2, ..., n, xi ∈ Rd ; yi ∈ R. Trong đó xi là các vị trí đo; yi là kết quả đo được tại vị trí xi . B1 , B2 , ..., Bn là các hàm cơ sở của không gian tuyến tính của các hàm liên tục d biến. Ký hiệu là: ( n ) X F = span{B1 , B2 , ..., Bn } = ck Bk ; ck ∈ R (1.24) k=1 Tìm hàm Pf ∈ F sao cho Pf (xi ) = yi ; i = 1, 2, ..., n (1.25) vì Pf ∈ F nên ta có Pf (x) = n X ck Bk (x), x ∈ Rd . (1.26) k=1 Từ (1.25) và (1.26) ta có Ac = y, (1.27)  B1 (x1 ) B2 (x1 ) ... Bn (x1 )  B (x ) B2 (x2 ) ... Bn (x2 )  A =  2... 1  Bn (x1 ) Bn (x2 ) ... Bn (xn ) (1.28) trong đó  c = [c1 , c2 , ..., cn ]T ; y = [y0 , y1 , ..., yn ]T . Bài toán 1.2 có nghiệm duy nhất khi và chỉ khi ma trận A không suy biến, tức là detA 6= 0. Trường hợp d = 1 (trong không gian một chiều) ta có thể chọn cơ sở như Soá hoùa bôûi trung taâm hoïc lieäu 19 http://www.lrc.tnu.edu.vn/