Tài liệu Nghiên cứu một số hàm cơ sở bán kính và ứng dụng để tính đạo hàm

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ NHÂM NGHIÊN CỨU MỘT SỐ HÀM CƠ SỞ BÁN KÍNH VÀ ỨNG DỤNG ĐỂ TÍNH ĐẠO HÀM LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2014 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGHIÊN CỨU MỘT SỐ HÀM CƠ SỞ BÁN KÍNH VÀ ỨNG DỤNG ĐỂ TÍNH ĐẠO HÀM LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành : TOÁN ỨNG DỤNG Mã số : 60 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC: TS ĐẶNG THỊ OANH THÁI NGUYÊN - 2014 1 Mục lục Bảng ký hiệu 6 Danh mục bảng và hình vẽ 7 1 Hàm cơ sở bán kính 1.1 Cơ sở của bài toán nội suy hàm số với dữ liệu phân tán . 1.1.1 Bài toán nội suy . . . . . . . . . . . . . . . . . . . 1.1.2 Một số phương pháp nội suy đa thức . . . . . . . . 1.1.3 Nhận xét . . . . . . . . . . . . . . . . . . . . . . . 1.2 Nội suy hàm số với dữ liệu phân tán . . . . . . . . . . . 1.2.1 Ma trận xác định dương . . . . . . . . . . . . . . . 1.2.2 Hàm xác định dương . . . . . . . . . . . . . . . . 1.2.3 Hàm bán kính . . . . . . . . . . . . . . . . . . . . 1.2.4 Hàm cơ sở bán kính( Radial Basis Function-RBF ) 1.2.5 Hàm bán kính xác định dương . . . . . . . . . . . 1.2.6 Hàm bán kính xác định dương có điều kiện . . . . 1.3 Một số hàm cơ sở bán kính và vấn đề tham số hình dạng 1.4 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Nội suy hàm cơ sở bán kính và ứng dụng tính đạo hàm 2.1 Nội suy hàm cơ sở bán kính . . . . . . . . . . . . . . . . . 2.1.1 Nội suy với độ chính xác đa thức . . . . . . . . . . . 2.1.2 Sai số, ổn định và hội tụ của nội suy hàm cơ sở theo bán kính . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Xây dựng công thức tính gần đúng đạo hàm dựa vào nội suy hàm cơ sở theo bán kính . . . . . . . . . . . . . . . . . 2.2.1 Nội suy hàm cơ sở bán kính không thành phần đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Nội suy hàm cơ sở bán kính với độ chính xác đa thức 2.3 Phương pháp tính đạo hàm nhờ nội suy RBF . . . . . . . . 2.3.1 Đạo hàm của hàm cơ sở bán kính . . . . . . . . . . 2.3.2 Tính đạo hàm nhờ nội suy RBF . . . . . . . . . . . 2 9 9 9 9 10 10 12 12 13 13 13 13 14 15 16 16 17 18 20 20 22 24 24 25 2.4 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Thử nghiệm số 3.1 Bài toán . . . . . . . . . . . . . . . . . . . . 3.2 Một số kết quả thử nghiệm . . . . . . . . . . 3.2.1 Thử nghiệm trên bộ tâm thứ nhất . . 3.2.2 Thử nghiệm trên bộ tâm thứ hai . . . 3.2.3 Thử nghiệm trên bộ tâm thứ ba . . . 3.2.4 Thử nghiệm trên bộ tâm thứ tư . . . 3.2.5 Thử nghiệm trên bộ tâm thứ năm . . 3.3 Tổng hợp kết quả thử nghiệm . . . . . . . . . 3.3.1 Tổng hợp kết quả thử nghiệm với hàm 3.3.2 Tổng hợp kết quả thử nghiệm với hàm 3.3.3 Tổng hợp kết quả thử nghiệm với hàm 3.4 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gaus MQ IMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 26 26 27 30 33 36 39 42 42 42 43 43 Kết luận 44 Tài liệu tham khảo 45 3 LỜI CẢM ƠN Trong quá trình hoàn thành luận văn "Nghiên cứu một số hàm cơ sở bán kính và ứng dụng để tính đạo hàm" 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 – Đại học Thái Nguyên, 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 – Đại học Thái Nguyên 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 05 tháng 05 năm 2014 Người thực hiện Nguyễn Thị Nhâm 4 Mở đầu Bài toán nội suy hàm số đã được rất nhiều các nhà toán học quan tâm nghiên cứu và đưa ra nhiều ứng dụng trong thực tiễn. Trong đó phải kể đến một số phương pháp nội suy truyền thống như: Phương pháp nội suy Lagrange; Phương pháp nội suy Newton; Phương pháp bình phương bé nhất. Những phương pháp này giải quyết khá đầy đủ bài toán nội suy hàm một biến với công thức đơn giản, dễ tính. Tuy nhiên đối với bài toán nội suy hàm nhiều biến, đặc biệt là trên tập điểm phân bố không đều thì những phương pháp trên gặp khó khăn trong tính toán vì công thức tính toán phức tạp. Hàm cơ sở bán kính là một công cụ hữu hiệu để nội suy hàm số trên tập điểm phân tán trong không gian nhiều chiều. Phương pháp nội suy hàm cơ sở bán kính đã được đề xuất bởi Powell vào năm 1987. Các vấn đề cơ bản về lí thuyết của hàm cơ sở bán kính và ứng dụng của nó đã được nghiên cứu rộng rãi bởi nhiều tác giả như: Buhman,Wendland, Gregory E. Fasshauer,... Một trong các ứng dụng quan trọng của phương pháp nội suy hàm cơ sở bán kính là tính gần đúng đạo hàm của hàm số dựa trên tập điểm lân cận, mà tại đó cần tính đạo hàm. Ưu thế lớn nhất của phương pháp là để giải bài toán nhiều chiều thì thay vì phải làm việc với hàm nhiều biến, ta chỉ cần làm việc với hàm một biến. 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 và phù hợp cho nhiều bài toán trong thực tiễn. Luận văn được trình bày trong 3 chương với những nội dung chính như sau: • Chương 1: Trình bày cơ sở của bài toán nội suy hàm số với dữ liệu phân tán; Nội suy hàm số với dữ liệu phân tán; Một số hàm cơ sở bán kính và vấn đề tham số hình dạng; Kết luận. • Chương 2: Nội suy hàm cơ sở bán kính; Xây dựng công thức tính gần đúng đạo hàm dựa vào nội suy hàm cơ sở bán kính và phương pháp 5 tính đạo hàm nhờ nội suy hàm cơ sở bán kính; Kết luận. • Chương 3: Thử nghiệm số. 6 Bảng ký hiệu const RBF Gaus MQ IM Q ||A|| ∀x ∃x ∈ Ln (x) Pf Rd max min Ξ Σ Q Hằng số Radial Basis Function Hàm Gaussian Hàm Multiquadric Hàm Inverse Multiquadric Chuẩn của A Với mọi x Tồn tại x thuộc Đa thức nội suy bậc không quá n Nội suy với độ chính xác đa thức Không gian thực d chiều Giá trị lớn nhất Giá trị nhỏ nhất Bộ tâm phân tán Tổng Tích Ω Bao đóng tập Ω NΦ (Ω) Không gian được sinh bởi Φ Cond(A) Số điều kiện của ma trận A φ0 Đạo hàm của hàm φ 00 φ Đạo hàm cấp hai của hàm φ 7 Danh mục bảng và hình vẽ Bảng 1.1 Bảng 1.2 Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng Bảng 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22 3.23 3.24 3.25 3.26 3.27 3.28 3.29 3.30 3.31 3.32 Bảng một số hàm cơ sở bán kính. Bảng một số hàm cơ sở bán kính với tham số hình dạng ε > 0. Bảng giá trị (x; y) trong bộ tâm thứ nhất. Bảng giá trị hàm số sin(2xy) với bộ tâm thứ nhất. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.2. 2 2 Bảng giá trị hàm số e−x −y với bộ tâm thứ nhất. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.4. Bảng giá trị hàm số sin(πx) sin(πy) với bộ tâm thứ nhất. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.6. Bảng giá trị hàm số sin(3πx) sin(3πy) với bộ tâm thứ nhất. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.8. Bảng giá trị (x; y) trong bộ tâm thứ hai. Bảng giá trị hàm số sin(2xy) với bộ tâm thứ hai. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.11. 2 2 Bảng giá trị hàm số e−x −y với bộ tâm thứ hai. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.13. Bảng giá trị hàm số sin(πx) sin(πy) với bộ tâm thứ hai. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.15. Bảng giá trị hàm số sin(3πx) sin(3πy) với bộ tâm thứ hai. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.17. Bảng giá trị (x; y) trong bộ tâm thứ ba. Bảng giá trị hàm số sin(2xy) với bộ tâm thứ ba. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.20. 2 2 Bảng giá trị hàm số e−x −y với bộ tâm thứ ba. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.22. Bảng giá trị hàm số sin(πx) sin(πy) với bộ tâm thứ ba. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.24. Bảng giá trị hàm số sin(3πx) sin(3πy) với bộ tâm thứ ba. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.26. Bảng giá trị (x; y) trong bộ tâm thứ tư. Bảng giá trị hàm số sin(2xy) với bộ tâm thứ tư. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.29. 2 2 Bảng giá trị hàm số e−x −y với bộ tâm thứ ba. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.31. 8 Bảng 3.33 Bảng 3.34 Bảng 3.35 Bảng 3.36 Bảng 3.37 Bảng 3.38 Bảng 3.39 Bảng 3.40 Bảng 3.41 Bảng 3.42 Bảng 3.43 Bảng 3.44 Bảng 3.45 Bảng 3.46 Bảng 3.47 Bảng 3.48 Hình 3.1 Hình 3.2 Hình 3.3 Hình 3.4 Hình 3.5 Bảng giá trị hàm số sin(πx) sin(πy) với bộ tâm thứ tư. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.33. Bảng giá trị hàm số sin(3πx) sin(3πy) với bộ tâm thứ tư. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.35. Bảng giá trị (x; y) trong bộ tâm thứ năm. Bảng giá trị hàm số sin(2xy) với bộ tâm thứ năm. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.38. 2 2 Bảng giá trị hàm số e−x −y với bộ tâm thứ năm. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.40. Bảng giá trị hàm số sin(πx) sin(πy) với bộ tâm thứ năm. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.42. Bảng giá trị hàm số sin(3πx) sin(3πy) với bộ tâm thứ năm. Kết quả thử nghiệm với dữ liệu cho trong Bảng 3.44. Tổng hợp kết quả thử nghiệm với hàm Gaus. Tổng hợp kết quả thử nghiệm với hàm MQ. Tổng hợp kết quả thử nghiệm với hàm IMQ. Mô phỏng vị trí các điểm trong Bảng 3.1 Mô phỏng vị trí các điểm trong Bảng 3.10 Mô phỏng vị trí các điểm trong Bảng 3.19 Mô phỏng vị trí các điểm trong Bảng 3.28 Mô phỏng vị trí các điểm trong Bảng 3.37 9 Chương 1 Hàm cơ sở bán kính Trong chương này chúng tôi trình bày một số kiến thức cơ bản về hàm cơ sở bán kính; hàm xác định dương; hàm bán kính xác định dương, hàm bán kính xác định dương có điều kiện; cơ sở của bài toán nội suy hàm số với dữ liệu phân tán. 1.1 1.1.1 Cơ sở của bài toán nội suy hàm số với dữ liệu phân tán Bài toán nội suy Trong thực tế nhiều khi phải phục hồi một hàm số f (x) tại mọi giá trị của x trên đoạn [a; b] mà chỉ biết một số hữu hạn giá trị của hàm số tại một số hữu hạn các điểm rời rạc của đoạn đó. Các giá trị đó được cung cấp qua thực nghiệm hay tính toán. Vậy nảy sinh một vấn đề toán học như sau: Trên đoạn [a; b] cho một lưới các điểm chia (điểm nút) xi , i = 0, 1, 2, · · · , n và tại các nút xi cho giá trị của hàm số y = f (x) là yi = f (xi ), i = 0, 1, 2, · · · , n. Cần xây dựng đa thức nội suy Pn (x) sao cho Pn (x) trùng với f (x) tại các nút xi , nghĩa là: Pn (xi ) = yi ; 1.1.2 i = 0, 1, 2, · · · , n. Một số phương pháp nội suy đa thức Một số phương pháp nội suy đa thức được đưa ra và giải quyết rất tốt bài toán trên, điển hình là phương pháp nội suy Lagrange và phương pháp nội suy Newton. Đa thức nội suy Lagrange: n X (x − x0 )(x − x1 )...(x − xi−1 )(x − xi+1 )...(x − xn ) Ln (x) = .yi . (x − x )(x − x )...(x − x )(x − x )...(x − x ) i 0 i 1 i i−1 i i+1 i n i=0 10 Đa thức nội suy Newton tiến xuất phát từ nút nội suy x0 : Pn (x) = y0 + (x − x0 )f (x0 ; x1 ) + ... + (x − x0 )...(x − xn−1 )f (x0 ; x1 ; ...; xn ). Đa thức nội suy Newton lùi xuất phát từ nút nội suy xn : Pn (x) = yn + (x − xn )f (xn ; xn−1 ) + (x − xn )(x − xn−1 )f (xn ; xn−1 ; xn−2 ) +... + (x − xn )(x − xn−1 )...(x − x1 )f (xn ; xn−1 ; ...; x0 ). 1.1.3 Nhận xét Đa thức nội suy Lagrange, như ta đã thấy rất đơn giản và dễ tính nếu các nút nội suy đã được cố định. Nhưng nếu như ta bổ sung thêm nút nội suy thì bậc của đa thức nội suy tăng theo, tất cả các đa thức nội suy cơ bản thay đổi, như vậy muốn tìm đa thức nội suy ta phải tính lại tất cả các đa thức nội suy cơ bản, hay nói cách khác phương pháp này không có tính kế thừa. Phương pháp nội suy Newton khắc phục được nhược điểm của nội suy Lagrange ở chỗ khi thêm vào lưới nội suy một nút nội suy mới xn+1 , ta chỉ cần thêm vào đa thức nội suy Pn (x) một số hạng. Tuy nhiên, khi số mốc nội suy lớn thì nội suy bằng đa thức thường xảy ra hiện tượng phù hợp trội (overfitting) do bậc của đa thức thường tăng theo số mốc nội suy. Hơn nữa, đa số các bài toán nội suy trong các ứng dụng thực tiễn lại là bài toán nội suy nhiều biến. Một phương pháp nội suy được đề xuất bởi Powell vào năm 1987 là phương pháp nội suy hàm cơ sở bán kính (Radial Basis Function-RBF) có thể chuyển từ bài toán nội suy hàm nhiều biến về nội suy hàm một biến. Hơn nữa còn cho kết quả rất tốt, đặc biệt với bài toán nội suy hàm nhiều biến trên tập dữ liệu phân tán. 1.2 Nội suy hàm số với dữ liệu phân tán Bài toán 1.1. [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: ( n ) X F = span{B1 , B2 , ..., Bn } = ck Bk ; ck ∈ R . (1.1) k=1 11 Tìm hàm Pf ∈ F sao cho Pf (xi ) = yi ; i = 1, 2, ..., n, (1.2) vì Pf ∈ F nên ta có Pf (x) = n X ck Bk (x), x ∈ Rd . (1.3) k=1 Từ (1.2) và (1.3) ta có Ac = y, (1.4)  B1 (x1 ) B2 (x1 ) ... Bn (x1 )  B (x ) B2 (x2 ) ... Bn (x2 )  A =  2... 1 , Bn (x1 ) Bn (x2 ) ... Bn (xn ) (1.5) trong đó  c = [c1 , c2 , ..., cn ]T ; y = [y1 , ..., yn ]T . Bài toán 1.1 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ư sau: {B1 , B2 , ..., Bn } = {1, x, x2 , ..., xn−1 }. Tuy nhiên khi d ≥ 2 ta có kết quả sau: Định lý 1.2.1. (Mairhuber - Curtis) Nếu Ω ⊂ Rd , d ≥ 2 và chứa một điểm trong thì không tồn tại không gian Haar các hàm liên tục trên Ω. Trong đó, không gian Haar được định nghĩa như sau: Định nghĩa 1.2.2. Cho Ω ⊂ Rd , và F ⊂ C(Ω) là không gian tuyến tính hữu hạn chiều có cơ sở là {B1 , B2 , ..., Bn }. Ta nói F là không gian Haar trên Ω nếu detA 6= 0 với mọi bộ tâm phân biệt {x1 , x2 , ..., xn } trong Ω. Trong đó ma trận A = (Ajk )n×n ; Ajk = Bk (xj ); j, k = 1, 2, ..., n. Bộ tâm phân biệt được định nghĩa như sau: Định nghĩa 1.2.3. (Bộ tâm phân biệt) Bộ tâm phân biệt X là tập các điểm phân biệt của không gian Rd trong lân cận của điểm x0 . 12 Sự tồn tại của không gian Haar đảm bảo tính khả nghịch của ma trận nội suy, nghĩa là tồn tại duy nhất nghiệm của bài toán nội suy 1.1. Không gian các đa thức một biến bậc n − 1 chính là không gian Haar n chiều với tập dữ liệu (xj ; yj ), j = 1, ...n; xj ∈ R; yj ∈ R. Định lí Mairhuber-Curtis cho thấy rằng nếu muốn giải được bài toán nội suy dữ liệu phân tán trong không gian nhiều chiều thì cơ sở cần phụ thuộc vào các vị trí dữ liệu. Để thu được các không gian xấp xỉ phụ thuộc dữ liệu, chúng ta cần xét đến các hàm xác định dương và các ma trận dương. 1.2.1 Ma trận xác định dương Định nghĩa 1.2.4. Ma trận A giá trị thực đối xứng được gọi là xác định dương nếu dạng toàn phương tương ứng không âm: n X n X cj ck Ajk ≥ 0 với c = (c1 , c2 , ..., cn )T ∈ Rn . j=1 k=1 Dấu bằng chỉ xảy ra khi và chỉ khi c = (0, 0, ..., 0)T . Tính chất quan trọng của ma trận xác định dương là nó có tất cả các giá trị riêng đều dương và không suy biến. Nếu hệ cơ sở {Bk }nk=1 , trong bài toán 1.1 làm cho ma trận nội suy A xác định dương thì hệ (1.4) có nghiệm duy nhất. 1.2.2 Hàm xác định dương Định nghĩa 1.2.5. Hàm liên tục Φ : Rd −→ R là xác định dương trên Rd khi và chỉ khi nó là hàm chẵn và với mọi bộ tâm phân biệt từng đôi một X = {x1 , x2 , ..., xn } ⊂ Rd ; n ∈ N, và mọi vectơ c = (c1 , c2 , ...cn ) ∈ Rn thì dạng toàn phương n X n X cj ck Φ(xj − xk ) ≥ 0. (1.6) j=1 k=1 Đẳng thức xảy ra khi và chỉ khi c = (0, 0, ..., 0). Định nghĩa 1.2.6. Hàm một biến φ : [0, ∞) −→ R được gọi là xác định dương trên Rd nếu hàm nhiều biến tương ứng Φ(x) = φ(||x||) với ∀x ∈ Rd là xác định dương, (với ||x|| là một chuẩn nào đó trong Rd , ta thường dùng chuẩn Ơcơlit). Từ định nghĩa trên và tính chất của ma trận xác định dương ta thấy có thể sử dụng các hàm xác định dương Bk = Φ(x − xk ) là hệ hàm cơ sở 13 và khi đó ta có Pf (x) = n X ck Φ(x − xk ). (1.7) k=1 Ma trận nội suy A = [Ajk ]n×n , với Ajk = Bk (xj ) = Φ(xj − xk ); j, k = 1, ..., n. Tuy nhiên việc giải bài toán nội suy trong không gian nhiều chiều là khó khăn, do đó thay vì sử dụng hàm nhiều biến Φ(x) bởi hàm một biến φ cho tất cả số chiều d. 1.2.3 Hàm bán kính Định nghĩa 1.2.7. [7] Hàm Φ : Rd → R được gọi là hàm bán kính nếu tồn tại hàm một biến φ : [0, ∞) → R sao cho Φ(x) = φ(||x||) với ∀x ∈ Rd .(Trong đó ||x|| là một chuẩn nào đó trong Rd , ta thường dùng chuẩn Ơcơlit). 1.2.4 Hàm cơ sở bán kính( Radial Basis Function-RBF ) Định nghĩa 1.2.8. [7] Cho hàm bán kính Φ : Rd → R. Hàm số một biến φ : [0; ∞) → R thỏa mãn: Φ(x) = φ(r), được gọi là hàm cơ sở bán kính (với r = ||x||, ||.|| là một chuẩn nào đó trong Rd ta thường dùng chuẩn Ơcơlit). 1.2.5 Hàm bán kính xác định dương Định nghĩa 1.2.9. [7] Cho hàm Φ : Rd → R với hàm cơ sở tương ứng là φ. Ta nói φ xác định dương trên Rd khi và chỉ khi Φ xác định dương trên Rd . 1.2.6 Hàm bán kính xác định dương có điều kiện Định nghĩa 1.2.10. [7] Hàm chẵn, liên tục Φ : Rd → R được gọi là xác định dương có điều kiện bậc l nếu với mọi bộ tâm phân biệt từng đôi một {x1 , x2 , ..., xn } ⊂ Rd , n ∈ N, với mọi vectơ (c1 , c2 , ..., cn ) ∈ Rn và mọi đa thức p giá trị thực bậc nhỏ hơn l, thỏa mãn n X cj p(xj ) = 0, j=1 thì n X n X cj ck Φ(xj − xk ) ≥ 0, j=1 k=1 14 và công thức trên là đẳng thức khi và chỉ khi c là vectơ 0. Nhận xét i) Nếu một hàm là xác định dương có điều kiện bậc l trong không gian Rd thì nó sẽ là xác định dương có điều kiện với mọi bậc lớn hơn l. Cụ thể là nếu một hàm là xác định dương (l = 0) thì sẽ là xác định dương với mọi bậc l ∈ N. ii) Ma trận A với các phần tử Ajk = Φ(xj − xk ) tương ứng với hàm chẵn, liên tục và xác định dương có điều kiện bậc l, có thể được xem như là hàm xác định dương trên không gian vectơ c sao cho n X cj p(xj ) = 0, j=1 trong đó p là đa thức bậc nhỏ hơn l. 1.3 Một số hàm cơ sở bán kính và vấn đề tham số hình dạng Trong khuôn khổ luận văn này tôi trình bày một số hàm cơ sở bán kính thông dụng, với r = kx − xk k . Tên hàm Multiquadric Tên viết tắt MQ Inverse multiquadric IMQ Gaussian Gaus Định nghĩa √ φmq (r) = 1 + r2 1 φimq (r) = √ 1 + r2 −r2 φ(r) = e Bảng 1.1: Bảng một số hàm cơ sở bán kính dùng trong luận văn.[5] Hàm cơ sở bán kính φ(x) là xác định dương nếu ta nhân r với một số dương ε thì φ(rε) vẫn là xác định dương. Khi các mốc nội suy xác định thì giải pháp tối ưu là đưa vào hàm Φk một tham số hình dạng εk . Như vậy ta cần tìm εk để bài toán thỏa mãn điều kiện nội suy, đồng thời chất lượng nội suy là tốt nhất. Khi đó εk còn gọi là tham số tỉ lệ (scaling) của hàm cơ sở bán kính vì nó dùng để điều chỉnh độ rộng của miền ảnh hưởng của hàm cơ sở φ. Khi ||x − xk || > ε − εk thì giá trị hàm Φk (x) là rất nhỏ không có ý nghĩa vì nó gần triệt tiêu. Vì vậy ta nói hàm bán kính này chỉ có ảnh hưởng địa phương. * Tham số hình dạng cho một số hàm cơ sở bán kính. [5] 15 Tên hàm Multiquadric Tên viết tắt Biểu thức tham số√hóa hình dạng MQ φmq (εr) = ε2 + r2 1 Inverse multiquadric IMQ φimq (εr) = √ ε22 + r2 r Gaussian Gaus φ(r) = e− 2 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. 1.4 Kết luận Trong chương này chúng tôi đã trình bày một số vấn đề cơ bản nhất về lí thuyết của hàm bán kính, hàm cơ sở bán kính, hàm bán kính xác định dương và ma trận xác định dương. Đó là những kiến thức cơ bản nhất để phục vụ cho chương 2. Cũng trong chương này, chúng tôi trình bày bài toán nội suy hàm số trên tập dữ liệu phân tán. Đồng thời giới thiệu một số hàm cơ sở bán kính cùng với vấn đề cần thiết phải đưa vào một tham số hình dạng  > 0, sao cho số điều kiện của ma trận nội suy chấp nhận được. 16 Chương 2 Nội suy hàm cơ sở bán kính và ứng dụng tính đạo hàm 2.1 Nội suy hàm cơ sở bán kính Cho bài toán 1.1 và bộ Φk , k = 1, 2, · · · , n sao cho Φk (x) = Φ(x − xk ) = φ (kx − xk k) với k = 1, 2, ..., n và x ∈ Rd . (2.1) Khi đó nội suy hàm số dựa trên các hàm bán kính có nghĩa là tìm P f (x) = n X ck Φk (x) = k=1 n X ck φ(||x − xk ||), (2.2) k=1 thỏa mãn điều kiện (1.2), trong đó xk gọi là tâm của hàm bán kính Φk . Nếu Φk (x) là hàm xác định dương thì theo điều kiện nội suy ta có P f (xi ) = yi , i = 1, 2, ..., n. (2.3) Nghĩa là cần tìm các tham số ck thỏa mãn n X ck φ (kxi − xk k) = yi , i = 1, 2, ..., n. (2.4) i=1 Suy ra Ac = y, (2.5) trong đó Φ(x) là hàm xác định dương và được xác định theo (2.1). Khi đó ma trận nội suy   Φ(0) Φ(x1 − x2 ) ... Φ(x1 − xn )  Φ(x2 − x1 ) Φ(0) ... Φ(x2 − xn )  A=  ... Φ(xn − x1 ) Φ(xn − x2 ) ... Φ(0) c = [c1 , c2 , ..., cn ]T , y = [y1 , y2 , ..., yn ]T . Theo định nghĩa hàm xác định dương thì detA 6= 0, hơn nữa A là ma trận đối xứng xác định dương. 17 Nhận xét: i) Việc chọn hàm cơ sở phải gắn liền với đối tượng nghiên cứu. Vì vậy trong việc giải phương trình đạo hàm riêng thì các hàm cơ sở bán kính phải là các hàm khả vi liên tục và thậm chí phải khả vi liên tục vô hạn lần. ii) Để bài toán nội suy có nghiệm duy nhất ta cần chọn các hàm cơ sở Φk phù hợp sao cho detA 6= 0 (A là ma trận nội suy). 2.1.1 Nội suy với độ chính xác đa thức Nội suy với độ chính xác đa thức dựa trên hàm cơ sở bán kính có nghĩa là: Cần tìm P f (x) = n X ck φ(||x − xk ||) + M X dl pl (x); x ∈ Rd . l=1 k=1 Trong đó m−1 M = dimΠdm−1 = Cd+m−1 = (d + m − 1)! (m − 1)!d! là số chiều của không gian các đa thức có bậc nhỏ hơn hoặc bằng m − 1 của d biến và p1 , p2 , ..., pM là cơ sở của không gian đó. Theo điều kiện nội suy ta có P f (xi ) = yi ; i = 1, 2, ..., n, từ đó ta có hệ n phương trình với n + m ẩn ck và dl . Vì vậy để hệ có nghiệm duy nhất, ta thêm vào điều kiện: n X ck pl (xk ) = 0; l = 1, 2, ..., M. k=1 Do đó ta được điều kiện nội suy suy rộng:  n M P P   ck φ(||xi − xk ||) + dl pl (xi ) = yi ; xi ∈ Rd ; i = 1, 2, ..., n,  k=1 l=1 n P    (2.6) ck pl (xk ) = 0; l = 1, 2, ..., M. k=1 Ký hiệu: Φ(0) Φ(x1 − x2 )  Φ(x2 − x1 ) Φ(0) A= ... ... Φ(xn − x1 ) Φ(xn − x2 )  18  ... Φ(x1 − xn ) ... Φ(x2 − xn )   ... ... ... Φ(0) (2.7) P = (pil ) ; pil = pl (xi ), l = 1, 2, ..., M ; i = 1, 2, ..., n; d = (d1 , d2 , ..., dM )T . Đây là hệ n + M phương trình đối với các ẩn c1 , c2 , ..., cn và d1 , d2 , ..., dM . Hệ này có thể viết dưới dạng      A P c y = 0 (2.8) T d P 0 2.1.2 Sai số, ổn định và hội tụ của nội suy hàm cơ sở theo bán kính a) Ước lượng sai số Cho f : Ω ⊆ Rd → R ta ký hiệu NΦ (Ω) là không gian được sinh bởi Φ, đó là không gian Hilbert mà các phần tử của nó có dạng nΦ X cj Φ(· − xj ); xj ∈ Ω, j=1 trong đó cho phép nΦ = ∞ và tích vô hướng của nó được cho bởi *n + nΦ nΦ X nΦ Φ X X X cj Φ(· − xj ), di Φ(· − zi ) = cj di Φ(xj − zi ). j=1 i=1 j=1 i=1 Ký hiệu X = {x1 , x2 , ..., xn } là các vị trí dữ liệu. Khi đó n o hX,Ω = sup min kx − xj k x∈Ω xj ∈X được gọi là khoảng cách lấp đầy. Cho β = β1 , β2 , ..., βd ∈ N0d là đa chỉ số với |β| = d P βi ta định nghĩa toán i=1 tử vi phân Dβ như sau ∂ |β| D = . (∂x1 )β1 ...(∂xd )βd β Khi đó, với các hàm khả vi vô hạn lần như hàm Gauss và hàm IM Q thì ta có độ hội tụ cao bất kỳ. Nghĩa là, với Φ là hàm xác định dương bậc m, ∀l ∈ N và l ≥ max{|α|, m − 1} tồn tại các hằng số h0 (l), Cl > 0 sao cho l−|α| |Dα f (x) − Dα P f (x)| ≤ Cl hX,Ω |f |NΦ (Ω) trong đó f ∈ NΦ (Ω), h0 (l) > hX,Ω , α là bậc đạo hàm. b) Sự ổn định và số điều kiện của ma trận nội suy hàm RBF Bài toán nội suy (2.5) khi tính toán sẽ gặp sai số máy tính và dẫn đến A(c + ∆c) = y + ∆y. 19 (2.9)