Bài Toán Nội Suy Và Mạng Nơron RBF

Luận án tiến sĩ nghiên cứu bài toán nội suy và mạng nơron rbf, phát triển phương pháp mới, đánh giá hiệu quả ứng dụng trong lĩnh vực toán học tại Việt Nam.

• Tác giả: Đặng Thị Thu Hiền
• Trường học: Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Nghiên Cứu Về Mạng Nơron RBF Trong Bài Toán Nội Suy
• Loại tài liệu: Luận Án Tiến Sĩ Công Nghệ Thông Tin
• Năm xuất bản: 2009
• Địa điểm: Hà Nội

Tóm tắt

I. Mạng Nơ ron RBF Tổng Quan Về Bài Toán Nội Suy

Bài toán nội suy hàm là một vấn đề cổ điển nhưng quan trọng trong giải tích số, nhận dạng mẫu và nhiều ứng dụng. Bài toán này bao gồm việc tìm một hàm số g xấp xỉ một hàm f chưa biết, dựa trên một tập các điểm dữ liệu đã biết. Các phương pháp truyền thống như nội suy đa thức gặp khó khăn trong không gian nhiều chiều. Mạng nơ-ron RBF nổi lên như một giải pháp hiệu quả, kết hợp ưu điểm của các phương pháp học dựa trên mẫu và mạng nơ-ron truyền thống. Luận án này tập trung vào nghiên cứu và phát triển các thuật toán huấn luyện mạng RBF hiệu quả cho bài toán nội suy, đặc biệt trong các trường hợp có số lượng điểm dữ liệu lớn và yêu cầu thời gian thực.

1.1. Giới thiệu bài toán nội suy và ứng dụng

Bài toán nội suy có thể được hiểu là quá trình xây dựng một hàm số đi qua một tập hợp các điểm dữ liệu cho trước. Ứng dụng của nội suy rất đa dạng, từ việc xấp xỉ các hàm số phức tạp, dự đoán giá trị dựa trên dữ liệu quá khứ, đến xử lý ảnh và âm thanh. Việc lựa chọn phương pháp nội suy phù hợp phụ thuộc vào tính chất của dữ liệu và yêu cầu về độ chính xác và tốc độ tính toán. Theo tài liệu, "Nội suy hàm số là một bài toán quan trọng trong giải tích số và nhận dạng mẫu đang được ứng dụng rộng rãi."

1.2. Mạng nơ ron nhân tạo ANN và nội suy

Mạng nơ-ron nhân tạo cung cấp một phương pháp mạnh mẽ để giải quyết bài toán nội suy, đặc biệt trong trường hợp các hàm số phức tạp hoặc dữ liệu nhiễu. Khả năng học và xấp xỉ hàm của ANN cho phép xây dựng các mô hình nội suy linh hoạt và chính xác. Các kiến trúc mạng nơ-ron khác nhau, như mạng MLP và mạng RBF, có những ưu điểm và hạn chế riêng trong việc giải quyết các bài toán nội suy khác nhau. Mạng RBF đặc biệt hiệu quả nhờ khả năng hội tụ nhanh và đảm bảo đến cực trị toàn cục. Theo tài liệu gốc, mạng nơ ron nhân tạo là cách tiếp cận tốt để khắc phục những nhược điểm trên.

II. Mạng Nơ ron RBF Cách Tiếp Cận Cho Bài Toán Nội Suy

Mạng nơ-ron RBF (Radial Basis Function Network) là một loại mạng nơ-ron nhân tạo đặc biệt thích hợp cho bài toán nội suy. Cấu trúc của mạng bao gồm một lớp ẩn với các hàm cơ sở xuyên tâm (radial basis functions) và một lớp đầu ra tuyến tính. Việc huấn luyện mạng RBF bao gồm việc xác định các tham số của các hàm cơ sở, như vị trí tâm và độ rộng, cũng như các trọng số kết nối giữa lớp ẩn và lớp đầu ra. Ưu điểm của mạng RBF là khả năng xấp xỉ hàm phi tuyến tính một cách hiệu quả và tốc độ huấn luyện nhanh hơn so với các mạng nơ-ron khác.

2.1. Kiến trúc và hoạt động của mạng RBF

Mạng RBF bao gồm ba lớp chính: lớp đầu vào, lớp ẩn (với các nơ-ron RBF), và lớp đầu ra. Mỗi nơ-ron trong lớp ẩn tính toán khoảng cách giữa đầu vào và tâm của nó, sau đó áp dụng một hàm cơ sở để tạo ra một giá trị kích hoạt. Lớp đầu ra kết hợp các giá trị kích hoạt này để tạo ra kết quả nội suy. Việc lựa chọn hàm cơ sở thích hợp (ví dụ: Gaussian RBF, Multiquadric RBF) ảnh hưởng đến hiệu suất của mạng. Theo hình 5.5, mô hình kiến trúc mạng nơ ron RBF được mô tả chi tiết.

2.2. Các hàm cơ sở bán kính RBF phổ biến

Một số loại hàm cơ sở bán kính phổ biến bao gồm Gaussian RBF, Multiquadric RBF, và Inverse Multiquadric RBF. Gaussian RBF là lựa chọn phổ biến nhất, với dạng chuông quen thuộc. Multiquadric RBF và Inverse Multiquadric RBF có hình dạng khác biệt và có thể phù hợp hơn cho một số bài toán cụ thể. Việc lựa chọn hàm cơ sở phù hợp có thể ảnh hưởng đến độ chính xác và tính ổn định của mạng nội suy. Theo hình 2.2 mô tả hàm cơ sở bán kính Gauss với σ = 1.

2.3. Huấn luyện mạng RBF Các phương pháp chính

Có nhiều phương pháp huấn luyện mạng RBF, bao gồm phương pháp huấn luyện một pha, huấn luyện hai pha, và huấn luyện đầy đủ. Phương pháp huấn luyện một pha thường sử dụng thuật toán cực tiểu hóa lỗi để tìm các tham số tối ưu. Phương pháp huấn luyện hai pha tách biệt việc xác định tâm và độ rộng của các hàm cơ sở với việc xác định trọng số lớp đầu ra. Phương pháp huấn luyện đầy đủ cố gắng tối ưu hóa tất cả các tham số cùng một lúc, nhưng có thể tốn nhiều thời gian hơn. Theo tài liệu, thuật toán huấn luyện mạng có vai trò rất quan trọng, nó ảnh hưởng trực tiếp đến tính hội tụ và tổng quát của mạng.

III. Thuật Toán Mới Nâng Cao Hiệu Quả Huấn Luyện RBF Nội Suy

Luận án này đề xuất một thuật toán lặp hai pha mới để huấn luyện mạng nội suy RBF. Pha thứ nhất xác định tham số độ rộng cho các hàm cơ sở xuyên tâm, trong khi pha thứ hai tìm kiếm trọng số lớp đầu ra thông qua phép lặp xác định điểm bất động của một ánh xạ co. Phân tích toán học và kết quả thực nghiệm cho thấy thuật toán này có những ưu điểm vượt trội so với các thuật toán thông dụng. Nó có thể được sử dụng khi số lượng điểm nội suy lớn, dễ dàng ước lượng sai số huấn luyện, thời gian huấn luyện ngắn và khả năng tổng quát tốt hơn, đồng thời dễ song song hóa.

3.1. Nền tảng lý thuyết của thuật toán lặp hai pha

Thuật toán HDH, như đề xuất trong luận án, dựa trên lý thuyết về điểm bất động của ánh xạ co. Bằng cách chia quá trình huấn luyện thành hai pha, thuật toán này có thể tìm kiếm các tham số tối ưu một cách hiệu quả hơn. Pha đầu tiên tập trung vào việc xác định độ rộng của các hàm cơ sở, trong khi pha thứ hai tối ưu hóa trọng số lớp đầu ra. Theo tài liệu gốc, thuật toán này còn giúp việc ước lượng sai số huấn luyện dễ dàng hơn.

3.2. Mô tả chi tiết thuật toán lặp hai pha HDH

Pha 1 của thuật toán HDH xác định tham số độ rộng bằng cách sử dụng một phương pháp lặp, trong đó mỗi lần lặp cập nhật độ rộng dựa trên khoảng cách giữa các điểm dữ liệu. Pha 2 tìm kiếm trọng số lớp đầu ra bằng cách sử dụng một phép lặp xác định điểm bất động, đảm bảo sự hội tụ nhanh chóng và chính xác. Việc sử dụng phép lặp điểm bất động đảm bảo rằng thuật toán sẽ hội tụ đến một nghiệm duy nhất, đồng thời giúp ước lượng sai số.

3.3. So sánh thuật toán HDH với phương pháp Gradient

Kết quả thực nghiệm cho thấy thuật toán HDH có tốc độ hội tụ nhanh hơn và độ chính xác cao hơn so với phương pháp Gradient. Thuật toán HDH cũng ít bị ảnh hưởng bởi các tham số điều chỉnh hơn, làm cho nó dễ sử dụng hơn. Quan trọng nhất, HDH cho tính tổng quát tốt hơn, điều này quan trọng để đảm bảo rằng mạng RBF có thể hoạt động tốt trên dữ liệu chưa từng thấy.

IV. Nội Suy Mốc Cách Đều Thuật Toán Một Pha Tối Ưu

Trong trường hợp bài toán nội suy có các mốc cách đều, luận án đề xuất một thuật toán một pha mới để huấn luyện mạng RBF. Thay vì sử dụng khoảng cách Euclidean, thuật toán này sử dụng khoảng cách Mahalanobis thích hợp. Phân tích toán học và kết quả thực nghiệm cho thấy thuật toán này cải thiện đáng kể chất lượng mạng so với thuật toán hai pha, cả về thời gian huấn luyện và tính tổng quát.

4.1. Biểu diễn bài toán nội suy với mốc cách đều

Khi các mốc nội suy được phân bố đều trong không gian, có thể tận dụng thông tin này để thiết kế các thuật toán huấn luyện hiệu quả hơn. Thuật toán một pha đề xuất trong luận án khai thác tính chất cách đều của các mốc nội suy để tối ưu hóa quá trình huấn luyện. Khoảng cách Mahalanobis được sử dụng để điều chỉnh hình dạng của các hàm cơ sở, làm cho chúng phù hợp hơn với cấu trúc của dữ liệu.

4.2. Thuật toán một pha QHDH Mô tả chi tiết và ưu điểm

Thuật toán QHDH, thuật toán một pha mới, giảm đáng kể thời gian huấn luyện so với thuật toán HDH (hai pha). Nó cũng cải thiện độ chính xác và tính tổng quát của mạng. QHDH sử dụng một công thức cập nhật duy nhất để đồng thời điều chỉnh các tham số độ rộng và trọng số, loại bỏ nhu cầu lặp lại qua hai pha riêng biệt. Bảng 6.1 so sánh thời gian huấn luyện giữa thuật toán 2 pha HDH và 1 pha QHDH.

4.3. So sánh QHDH với các thuật toán huấn luyện khác

So sánh QHDH với các thuật toán huấn luyện nhanh khác như QTL và QTH cho thấy QHDH đạt được sự cân bằng tốt giữa tốc độ huấn luyện, độ chính xác và tính tổng quát. Kết quả thực nghiệm cho thấy QHDH vượt trội hơn trong nhiều trường hợp, đặc biệt khi số lượng điểm dữ liệu lớn. Bảng 6.2 so sánh sai số và thời gian huấn luyện của các thuật toán QHDH, HDH, QTL, QTH với 1331 mốc của hàm 3 biến.

V. Mạng RBF Địa Phương Giải Pháp Cho Bài Toán Thời Gian Thực

Đối với các bài toán thời gian thực, đặc biệt là bài toán động, luận án đề xuất một kiến trúc mạng địa phương. Mạng này chia miền xác định thành các miền con chứa số lượng điểm nội suy tương đối bằng nhau, sử dụng phương pháp phỏng theo thuật toán xây dựng cây k-d quen thuộc. Sau đó, thuật toán huấn luyện hai pha được sử dụng để huấn luyện mạng RBF trên mỗi miền con và ghép chúng lại theo ý tưởng nội suy spline.

5.1. Kiến trúc mạng RBF địa phương Phân vùng không gian

Mạng RBF địa phương phân vùng không gian đầu vào thành các vùng nhỏ hơn, mỗi vùng được xử lý bởi một mạng RBF riêng biệt. Cách tiếp cận này cho phép mạng thích ứng tốt hơn với các thay đổi cục bộ trong dữ liệu, làm cho nó phù hợp hơn cho các bài toán động. Quá trình phân vùng thường sử dụng thuật toán cây k-d để đảm bảo các vùng có số lượng điểm dữ liệu tương đương.

5.2. Thuật toán phân cụm nhờ cây k d Chi tiết kỹ thuật

Thuật toán cây k-d là một phương pháp hiệu quả để phân chia không gian thành các vùng nhỏ hơn. Thuật toán này đệ quy chia không gian dọc theo các trục tọa độ, sao cho mỗi vùng chứa một số lượng điểm dữ liệu nhất định. Quá trình chia dừng lại khi mỗi vùng chứa ít hơn một số lượng điểm dữ liệu tối đa được xác định trước. Theo hình 7.4 mô tả cây K-D mô tả tập dữ liệu trong không gian 2 chiều, với N=38, M=10.

5.3. Huấn luyện tăng cường mạng RBF địa phương cho bài toán động

Trong các bài toán động, dữ liệu có thể thay đổi theo thời gian. Để thích ứng với những thay đổi này, mạng RBF địa phương có thể được huấn luyện tăng cường khi có dữ liệu mới. Quá trình huấn luyện tăng cường bao gồm việc cập nhật các tham số của các mạng RBF cục bộ để phản ánh những thay đổi trong dữ liệu. Hình 7.9 so sánh thời gian huấn luyện tăng cường khi có mốc mới.

VI. Kết Luận Hướng Nghiên Cứu Mạng Nơ ron RBF Tương Lai

Luận án này đã trình bày một số đóng góp quan trọng trong lĩnh vực huấn luyện mạng nơ-ron RBF cho bài toán nội suy. Các thuật toán mới được đề xuất, bao gồm thuật toán lặp hai pha HDH và thuật toán một pha QHDH, cho thấy những ưu điểm vượt trội so với các phương pháp thông dụng. Kiến trúc mạng RBF địa phương cũng hứa hẹn là một giải pháp hiệu quả cho các bài toán thời gian thực. Tuy nhiên, vẫn còn nhiều hướng nghiên cứu tiềm năng trong tương lai.

6.1. Tóm tắt các đóng góp chính của luận án

Luận án này đã đề xuất các thuật toán huấn luyện mới cho mạng nơ-ron RBF, bao gồm HDH và QHDH. Nó cũng đã trình bày một kiến trúc mạng RBF địa phương cho các bài toán thời gian thực. Các kết quả thực nghiệm cho thấy các phương pháp đề xuất có hiệu suất tốt hơn so với các phương pháp hiện có. Các kết quả này đã được công bố trong các tạp chí khoa học và hội nghị quốc tế.

6.2. Hướng nghiên cứu tiếp theo cho mạng RBF nội suy

Các hướng nghiên cứu tiềm năng trong tương lai bao gồm việc phát triển các thuật toán huấn luyện thích ứng hơn, khám phá các kiến trúc mạng RBF phức tạp hơn, và áp dụng các phương pháp đề xuất cho các bài toán ứng dụng thực tế. Cần có thêm nghiên cứu để hiểu rõ hơn về các tính chất lý thuyết của mạng RBF và để phát triển các phương pháp hiệu quả hơn để lựa chọn các tham số mạng.

6.3. Ứng dụng mạng RBF trong các lĩnh vực thực tiễn

Mạng RBF có thể được áp dụng trong nhiều lĩnh vực thực tiễn, bao gồm điều khiển học, khai thác dữ liệu, xử lý ảnh, và nhận dạng mẫu. Việc sử dụng các thuật toán huấn luyện hiệu quả và các kiến trúc mạng phù hợp có thể giúp giải quyết các bài toán phức tạp trong các lĩnh vực này. Ứng dụng tiềm năng trong các lĩnh vực như dự báo thời tiết, dự đoán thị trường chứng khoán, và chẩn đoán y tế.

Trích đoạn nội dung tài liệu

CHƯƠNG 1. NỘI SUY HÀM SỐ VÀ MẠNG NƠRON Nội suy hàm số là một bài toán quan trọng trong giải tích số và nhận dạng mẫu [5,22,30,36,38] đang được ứng dụng rộng rãi. Bài toán nội suy hàm một biến đã được nghiên cứu từ rất sớm gắn liền với các tên tuổi lớn như Lagrange và Newton. Nhưng trong các ứng dụng thực tế ta thường phải giải quyết bài toán nội suy nhiều biến và nó chỉ mới được quan tâm nghiên cứu trong năm mươi năm gần đây cùng với sự phát triển mạnh mẽ của khoa học máy tính.

Đầu tiên, người ta phát triển nội suy nhiều biến theo hướng sử dụng đa thức nhưng không hiệu quả do phức tạp trong tính toán và kết quả ứng dụng không tốt. Các phương pháp k- lân cận gần nhất Cover và Hart (1967) và hồi quy trọng số địa phương cho một giải pháp đơn giản, dễ sử dụng với bài toán này và đang là một công cụ tốt. Tuy nhiên các phương pháp này không thể huấn luyện trước được, mà chỉ xác định khi biết điểm cần nội suy. Như vậy, việc xác định giá trị hàm nội suy tại mẫu mới thực hiện khi đã biết mẫu để xác định láng giềng (lân cận).

Cách tiếp cận này sẽ gặp khó khăn khi áp dụng cho các bài toán cần xác định trước hàm nội suy. Mạng nơron nhân tạo là cách tiếp cận tốt để khắc phục những nhược điểm trên. Mặc dù còn vướng nhiều vấn đề mở về lý thuyết, nhưng hiện nay mạng nơron nhân tạo là một công cụ hữu hiệu để giải các bài toán nội suy hàm nhiều biến trong các bài toán ứng dụng thực tiễn. Trong đó thông dụng nhất là mạng MLP và mạng RBF ( xem [14,15,30]).

Chương này giới thiệu những điểm cơ bản của bài toán nội suy hàm số và mạng nơron nhiều tầng truyền tới (MLP) cần cho nội dung chính của luận án.1 giới thiệu về bài toán nội suy bao gồm nội suy đa thức cho hàm một biến và các khái niệm và tiếp cận chính đối với bài toán nội suy hàm nhiều biến.2 trình 16 TIEU LUAN MOI download : [e-mail] bày tổng quan về mạng nơron nhân tạo và giới thiệu về các mạng nơron nhiều tầng truyền tới. Nội suy hàm số Trong nhiều bài toán, ta cần tính giá trị của một hàm số tại những điểm của đối số trong miền D nào đó của không gian n-chiều, nhưng không có biểu diễn tường minh hàm số mà chỉ xác định được giá trị của hàm số trên một tập hữu hạn điểm của D. Việc xác định gần đúng hàm này dẫn tới bài toán nội suy và xấp xỉ hàm số. Bài toán nội suy tổng quát Bài toán nội suy tổng quát được phát biểu như sau.

Xét hàm nhiều biến chưa biết f : D (Rn)Rm nhưng xác định được một tập mẫu gồm N phần tử x , y  k k N k 1 trong đó xkRn, ykRm ( k=1,. Ta cần tìm hàm g có dạng đủ tốt đã biết thỏa mãn: g(xi) = yi,  i = 1,.1) Các điểm xk được gọi là các mốc nội suy còn hàm g gọi là hàm nội suy của f. Hàm nội suy thường được dùng để xấp xỉ hàm f trên miền D, giá trị hàm nội suy tính được tại điểm x bất kỳ trên miền D gọi là giá trị nội suy của hàm f tại x (hay gọn hơn là giá trị nội suy tại x nếu không có sự nhầm lẫn).1 minh họa hàm nội suy trong trường hợp một biến. 17 TIEU LUAN MOI download : skknchat@gmail.1 Minh họa bài toán nội suy hàm một biến Những giá trị yk tại mốc nội suy tương ứng xk có thể chứa nhiễu và nhiều trường hợp việc giải hệ phương trình (1.1) không có nghiệm đúng đối với dạng hàm g đã biết hoặc cho kết quả nội suy không tốt.

Một cách tiếp cận khác là thay đòi hỏi thỏa mãn hệ phương trình (1.1) bởi một tiêu chuẩn xấp xỉ tốt nhất (đủ tốt) nào đó, thông dụng nhất là tiêu chuẩn cực tiểu tổng bình phương sai số (gọi là bình phương tối thiểu cho gọn). Với cách tiếp cận này ta có bài toán xấp xỉ. Nội suy hàm một biến Bài toán nội suy hàm một biến đã được nghiên cứu từ hơn ba thế kỷ đến nay và khá hoàn thiện, đặc biệt là nội suy bằng đa thức. Trước khi đi vào trường hợp đa thức, ta xét lược đồ giải quyết tổng quát.

a) Lược đồ giải quyết cho nội suy hàm một biến. Trường hợp hàm một biến, bài toán nội suy được phát biểu như sau: Một hàm số y =f(x) chỉ xác định được tại các điểm x0 = a<x1<.<xn= b và yi=f(xi) i≤n. Ta cần tìm một biểu thức giải tích đủ đơn giản g(x) để xác định giá trị gần đúng của y : y  g(x) tại các điểm x  [a,b] sao cho tại các điểm xi ta có: g(xi) = yi. 18 TIEU LUAN MOI download : [e-mail] Lược đồ giải quyết : Giả sử đã biết các giá trị yi của hàm số tại các mốc nội suy xi tương ứng.

Chọn trước một hàm phụ thuộc (n+1) tham số độc lập c j nj0 (c0,c1,.,cn,x) thoả mãn các điều kiện nhất định. Người ta xác định các cj cho biểu thức nội suy nhờ hệ phương trình.,cn, xk) = yk k = 0,.,cn,x) là hàm phi tuyến thì hệ phương trình (1.2) không đảm bảo duy nhất nghiệm nên người ta thường chọn  có dạng tuyến tính: n (1.,cn, x) =  c k  k ( x) k 0 Trong đó cj (j=1,.,n) là các tham số cần tìm và  k ( x)nk 0 là họ hàm độc lập tuyến tính cho trước thoả mãn điều kiện định thức ma trận.4) Khi đó các cj trong hệ (1.2) luôn giải được duy nhất nghiệm. Các hàm số k(x) thường được chọn theo kinh nghiệm hoặc đơn giản là hàm lũy thừa xk để dễ tính toán. Với các c j nj 0 đã xác định nhờ điều kiện (1.,cn, x) là hàm nội suy và dùng làm công thức để tính giá trị f(x).

Khi g lấy trong lớp đa thức bậc n ta dễ dàng xác định được nhờ đa thức nội suy Lagrange mà không phải thực hiện thủ tục giải hệ phương trình tuyến tính. b) Đa thức nội suy Lagrange Trường hợp f là hàm một biến với n +1 mốc nội suy và hàm nội suy dạng đa thức thì nó phải là đa thức bậc n để hệ phương trình (1.2) có duy nhất nghiệm 19 TIEU LUAN MOI download : skknchat@gmail. Khi đó hàm nội suy g(x) là đa thức nội suy Lagrange Ln(x) và được xây dựng như sau. Xây dựng đa thức nội suy Lagrange.

Ký hiệu Ln(x) là đa thức nội suy bậc n cần tìm. Ta xây dựng đa thức này dưới dạng n (1.6) L ( x)  k ik  (x  x ) n k i ik Thỏa mãn các điều kiện đã nêu và hàm g(x) = Ln(x) thoả mãn hệ phương trình (1.1) và là đa thức nội suy cần tìm. Sai số nội suy tại điểm x được ước lượng bằng công thức: f ( n 1) (c) n Rn ( x)  (n  1)! k 0  ( x  xk ) Với c là điểm thích hợp thuộc khoảng [a,b]. c) Công thức nội suy Newton cho trường hợp mốc cách đều Trường hợp các mốc nội suy thỏa mãn điều kiện: (b  a ) xi+1 – xi = xi = h = (i  0,1,., n  1) ta nói các mốc này cách đều.

n x  x0 Khi đó với phép biến đổi  t các đa thức Lkn là đa thức bậc n theo t. Đa thức h này chỉ phụ thuộc vào số mốc n và giá trị hàm tại các mốc nên có nhiều cách biểu diễn đơn giản, dễ sử dụng. Ở đây chúng tôi giới thiệu công thức Newton tiến để biểu diễn đa thức này. Trước hết ta xây dựng công thức tổng quát.

20 TIEU LUAN MOI download : [e-mail] Công thức tổng quát Đặt, x - x0 = th (1.8) Ta có,   x  x k  (t  k )h Thay vào (1. Các biểu diễn công thức này qua các sai phân hữu hạn cho ta các dạng công thức nội suy Newton. Ở đây sẽ trình bày công thức nội suy Newton tiến. Trước khi giới thiệu công thức, ta cần định nghĩa sai phân hữu hạn của hàm số.

Sai phân hữu hạn Trường hợp các mốc cách đều, tức là: xi+1 – xi = xi = h =const (i=1,2,. Các sai phân hữu hạn của hàm y = f(x) được xác định như sau: Sai phân cấp một: yi = yi+1 – yi Sai phân cấp hai: 2yi = yi+1 – yi ---------------------------------------- Sai phân cấp k: kyi = k-1yi+1 – k-1yi Với các sai phân được xác định như trên ta có công thức nội suy Newton như sau. Công thức nội suy Newton 21 TIEU LUAN MOI download : [e-mail] Với phép biến đổi x-x0 = th như trên đa thức nội suy được biễu diễn bởi công thức : t (t  1) 2 t (t  1).12) Rn ( x)  h n 1 f (c ) (n  1)! Sai số này cũng có thể ước lượng thô nhờ thêm vào mốc xn+1: n 1 y 0 (1.(t  n) (n  1)! Khi có nhiều mốc nội suy, hàm nội suy sẽ là đa thức bậc cao. Chúng thuộc loại hàm không ổn định (sai số đối số bé nhưng sai số hàm số lớn), và dễ xảy ra hiện tượng phù hợp trội (overfitting).

Tức là cho giá trị nội suy có sai số lớn tại các điểm khác mốc nội suy. Để khắc phục hiện tượng này, phương pháp thông dụng là dùng hàm nội suy Spline. d) Nội suy Spline Để khắc phục hiện tượng phù hợp trội khi có nhiều mốc nội suy, người ta dùng các đa thức bậc thấp trên mỗi đoạn con của đoạn [a,b] và ghép trơn đến mức cần thiết trên toàn đoạn thành hàm nội suy, các hàm này có tên gọi là hàm Spline. Hàm Spline Định nghĩa: Hàm Spline bậc (m,k) trên đoạn [a,b] là hàm số có các tính chất sau : 1.

Tồn tại phân hoạch a = x0 < x1 <.,n-1, nó là đa thức bậc m 2. Trên [a,b] nó có đạo hàm cấp k liên tục. 22 TIEU LUAN MOI download : [e-mail] Từ định nghĩa ta thấy để hàm thoả mãn điều kiện 2 thì chỉ cần đạo hàm các cấp  k ở hai phía của mỗi điểm chia xi (i=1,.,n-1) bằng nhau là đủ. Vì vậy nó còn được gọi là hàm ghép trơn.

Tập các hàm Spline bậc (m,k) trên đoạn [a,b] được ký hiệu là SPkm[a,b] nếu k = m-1 ta gọi Spline bậc m và ký hiệu SPm[a,b]. Xây dựng hàm nội suy Spline bậc m Giả sử y = f(x) đo được tại n+1 mốc nội suy a = x0 < x1 <.< xn = b là yi = f(xi) và Sm SPm[a,b] là hàm Spline được xác định bởi phân hoạch này.