Tài liệu Ngoại suy trong phân tích dự báo và ứng dụng

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG VĂN TRUYỀN NGOẠI SUY TRONG PHÂN TÍCH DỰ BÁO VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG VĂN TRUYỀN NGOẠI SUY TRONG PHÂN TÍCH DỰ BÁO VÀ ỨNG DỤNG 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. VŨ MẠNH XUÂN Thái Nguyên - 2016 i Mục lục Danh sách hình vẽ iii Danh sách bảng v Mở đầu 1 Chương 1. Khái quát về phân tích dự báo 3 1.1 Khái niệm dự báo . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Đặc điểm của dự báo . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Các phương pháp dự báo . . . . . . . . . . . . . . . . . . . . . . 4 1.3.1 Phương pháp dự báo định tính . . . . . . . . . . . . . . 5 1.3.2 Phương pháp dự báo định lượng . . . . . . . . . . . . . . 5 Phương pháp ngoại suy trong dự báo . . . . . . . . . . . . . . . 5 1.4.1 Khái niệm phương pháp ngoại suy . . . . . . . . . . . . 5 1.4.2 Các tính chất của ngoại suy . . . . . . . . . . . . . . . . 6 Các phương pháp ngoại suy . . . . . . . . . . . . . . . . . . . . 7 1.5.1 Phương pháp ngoại suy được suy ra từ nội suy . . . . . . 7 1.5.2 Phương pháp hồi quy tuyến tính đơn . . . . . . . . . . . 14 1.5.3 Mô hình hồi quy đa thức . . . . . . . . . . . . . . . . . . 17 1.4 1.5 Chương 2. Một số bài toán ứng dụng 18 2.1 Thử nghiệm dự báo trong tính toán khoa học . . . . . . . . . . 2.2 Một số dự báo trong quản lý đào tạo tại trường Đại học Khoa học 25 2.2.1 Dự báo số lượng tuyển sinh . . . . . . . . . . . . . . . . 18 25 ii 2.3 2.2.2 Dự báo kết quả tuyển sinh theo từng ngành . . . . . . . 32 2.2.3 Dự báo lượng tốt nghiệp của trường Đại học Khoa học . 37 Một vài ứng dụng trong đời sống và kinh tế . . . . . . . . . . . 40 Kết luận 56 Tài liệu tham khảo 56 iii Danh sách hình vẽ 1.1 1.2 Nội suy hàm Runge . . . . . . . . . . . . . . . . . . . . . . . . . Độ lệch và các đường hồi quy lý thuyết, thực nghiệm . . . . . . 12 16 2.1 2.2 2.3 Đồ thị của đa thức f (x) (Bài toán 2.1.1). . . . . . . . . . . . . . Đồ thị của hàm Φ(x) (Bài toán 2.1.1). . . . . . . . . . . . . . . Đồ thị so sánh dữ liệu trong Bảng 2.1 và mô hình hồi quy tuyến tính của nó. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Đồ thị so sánh dữ liệu trong Bảng 2.1 và mô hình hồi quy tam thức của nó. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phân bố các điểm dữ liệu Bảng 2.2. . . . . . . . . . . . . . . . . Đồ thị của đa thức f (x) (Bài toán 2.1.3). . . . . . . . . . . . . . Đồ thị so sánh dữ liệu trong Bảng 2.2 và mô hình hồi quy tuyến tính của nó. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Đồ thị hàm f 1(x). . . . . . . . . . . . . . . . . . . . . . . . . . Đồ thị hàm f 2(x). . . . . . . . . . . . . . . . . . . . . . . . . . Đồ thị hàm f 3(x). . . . . . . . . . . . . . . . . . . . . . . . . . Đồ thị so sánh dữ liệu trong Bảng 2.3 và mô hình hồi quy tuyến tính của nó. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Đồ thị hàm f (x) (Bài toán 2.2.2). . . . . . . . . . . . . . . . . . Biểu đồ số lượng thẻ ngân hàng theo các năm (Đvt: triệu thẻ). . Mô hình hồi quy tuyến tính số lượng thẻ ngân hàng. . . . . . . Phân bố các điểm dữ liệu Bảng 2.10. . . . . . . . . . . . . . . . Đồ thị minh họa đa thức f (x) (Bài toán 2.3.2 ). . . . . . . . . . Đồ thị so sánh dữ liệu trong Bảng 2.10 và mô hình hồi quy tuyến tính của nó. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Đồ thị so sánh dữ liệu trong Bảng 2.10 và mô hình hồi quy tam thức của nó. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Đồ thị minh hoạ hàm g(x) biểu diễn giá vàng mua vào. . . . . . Mô hình hồi quy tam thức biểu diễn giá vào mua vào. . . . . . . 20 20 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20 21 22 24 24 25 27 28 29 30 32 41 43 44 44 45 46 47 48 iv 2.21 2.22 2.23 2.24 2.25 2.26 2.27 2.28 2.29 Đồ thị minh hoạ hàm h(x) biểu diễn giá vàng bán ra. . . . . . . Biểu đồ số liệu tham gia giao thông tại thành phố Hồ Chí Minh. Đồ thị minh họa đa thức biểu diễn số lượng xe ô tô. . . . . . . . Đồ thị minh họa đa thức biểu diễn số lượng xe máy. . . . . . . . Biểu đồ mức chi tiêu bình quân đầu người (Đvt: Nghìn VNĐ/ người/ tháng). . . . . . . . . . . . . . . . . . . . . . . . . . . . . Đồ thị minh họa đa thức biểu diễn mức chi tiêu cho ăn uống . . Đồ thị minh họa đa thức biểu diễn mức chi tiêu trung bình . . . Biểu đồ doanh thu và tốc độ tăng trưởng ngành sữa Việt Nam (Đv: Doanh thu: nghìn tỉ đồng, tốc độ tăng trưởng: %). . . . . . Đồ thị minh họa đa thức biểu diễn tốc độ tăng trưởng ngành sữa 49 50 51 51 52 53 53 54 54 v Danh sách bảng 2.1 2 Bảng một số giá trị của tích phân Φ(x) = √ π Z 0 x 2 e−t dt. . . . . 3 (x + t) 2 2.2 Bảng một số giá trị của tích phân f (x) = cos x t dt. . . e + sin tx 2.3 Kết quả tuyển sinh chính quy của trường Đại học Khoa học từ năm 2003 đến năm 2015. . . . . . . . . . . . . . . . . . . . . . . 2.4 Kết quả tuyển sinh liên thông của trường Đại học Khoa học giai đoạn từ năm 2005 đến năm 2015. . . . . . . . . . . . . . . . . . 2.5 Kết quả tuyển sinh theo ngành của trường Đại học Khoa học giai đoạn từ năm 2009 đến năm 2015 . . . . . . . . . . . . . . . 2.6 So sánh kết quả dự báo với số liệu thực tế tuyển sinh của trường Đại học Khoa học năm 2016 . . . . . . . . . . . . . . . . . . . . 2.7 Số lượng sinh viên tốt nghiệp hệ chính quy. . . . . . . . . . . . . 2.8 Sinh viên chính quy tốt nghiệp theo ngành. . . . . . . . . . . . 2.9 So sánh kết quả dự báo số lượng sinh viên tốt nghiệp K10 với số lượng sinh viên thực tế đang học K10 . . . . . . . . . . . . . 2.10 Dân số của một quốc gia từ năm 1975 đến 2005 . . . . . . . . . 2.11 Giá vàng SJC từ tháng 3 đến tháng 9 năm 2016 (Đvt: triệu đồng/lượng). . . . . . . . . . . . . . . . . . . . . . . . . . . . . R x2 18 23 26 31 33 37 37 38 40 42 46 1 Mở đầu Nhiều bài toán trong tự nhiên và xã hội không xuất phát từ các hàm số đã cho mà từ những bộ số liệu cụ thể có được do quan sát hay đo, đếm, .... Người ta muốn từ những bộ số liệu cụ thể này tìm được giá trị của hàm số (chưa biết) tại các điểm chưa được khảo sát, từ đó dẫn đến các kỹ thuật nội suy, ngoại suy. Nội suy thường cho kết quả tốt, xấp xỉ gần đúng giá trị thực, còn ngoại suy có thể cho sai số lớn hơn. Nhưng trên thực tế, ngoại suy thường có ứng dụng lớn hơn do nó đưa ra những dự báo cả về định tính lẫn định lượng cho tương lai. Đề tài này nhằm nghiên cứu các kỹ thuật nội suy, ngoại suy và tìm các ứng dụng trong các bài toán thực tế. Các bài toán chọn ở đây thuộc 3 nhóm. Nhóm thứ nhất là ngoại suy trên một số hàm số đã biết nhằm kiểm chứng sai số và độ tin cậy của việc tính toán. Nhóm thứ hai là vận dụng cho bài toán tuyển sinh thực tế của Trường Đại học Khoa học. Nhóm thứ ba là một số thử nghiệm về dự báo giá cả một số lĩnh vực trong đời sống kinh tế. Bố cục luận văn được chia thành 2 chương ngoài phần mở đầu, phần kết luận và các tài liệu tham khảo cụ thể như sau: Chương 1: Khái quát về phân tích dự báo Chương này trình bày về khái niệm dự báo, các đặc điểm, các phương pháp ngoại suy trong dự báo. Chương 2: Một số bài toán ứng dụng Chương này trình bày một số bài toán thử nghiệm thuộc 3 nhóm bài toán như đã nêu trên. Luận văn được thực hiện và hoàn thành tại trường Đại học Khoa học - Đại học Thái Nguyên dưới sự hướng dẫn trực tiếp của TS. Vũ Mạnh Xuân. Tác giả xin bày tỏ lòng biết ơn chân thành và sâu sắc tới các thầy cô, những người đã tận tâm giảng dạy và chỉ bảo tác giả trong suốt quá trình học tập và thực hiện luận văn. 2 Tác giả xin chân thành cảm ơn Ban Giám hiệu, Phòng Đào tạo, Khoa Toán - Tin trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Cuối cùng tác giả xin gửi lời cảm ơn tới gia đình, bạn bè, đồng nghiệp đã động viên, giúp đỡ và tạo điều kiện tốt nhất cho tác giả khi học tập và nghiên cứu. Tôi xin chân thành cảm ơn. Thái Nguyên, tháng 10 năm 2016 Học viên Dương Văn Truyền 3 Chương 1 Khái quát về phân tích dự báo Chương này giới thiệu khái niệm dự báo, đặc điểm, các phương pháp dự báo thường dùng và phương pháp ngoại suy trong dự báo. Các kiến thức của chương được tổng hợp từ các tài liệu [1]–[4] và [5]. 1.1 Khái niệm dự báo Dự báo là một khoa học và nghệ thuật tiên đoán những sự việc sẽ xảy ra trong tương lai, trên cơ sở phân tích khoa học về các dữ liệu đã thu thập được. Khi tiến hành dự báo cần căn cứ vào việc thu thập, xử lý số liệu trong quá khứ và hiện tại để xác định xu hướng vận động của các hiện tượng trong tương lai nhờ vào một số mô hình toán học (định lượng). Tuy nhiên dự báo cũng có thể là một dự đoán chủ quan hoặc trực giác về tương lai (định tính) và để dự báo định tính được chính xác hơn, người ta cố loại trừ những tính chủ quan của người dự báo. Dù định nghĩa có sự khác biệt nào đó, nhưng đều thống nhất về cơ bản là dự báo bàn về tương lai, nói về tương lai. Dự báo trước hết là một thuộc tính không thể thiếu của tư duy của con người, con người luôn luôn nghĩ đến ngày mai, hướng về tương lai. Trong thời đại công nghệ thông tin và toàn cầu hóa, dự báo lại đóng vai trò quan trọng hơn khi nhu cầu về thông tin thị trường, tình hình phát triển tại thời điểm nào đó trong tương lai càng cao. Dự báo được sử dụng trong nhiều lĩnh vực khác nhau, mỗi lĩnh vực có một yêu cầu về dự báo riêng nên phương pháp dự báo được sử dụng cũng khác nhau. 4 1.2 Đặc điểm của dự báo Không có cách nào để xác định tương lai là gì một cách chắc chắn (tính không chính xác của dự báo). Dù phương pháp chúng ta sử dụng là gì thì luôn tồn tại yếu tố không chắc chắn cho đến khi thực tiễn diễn ra. Đến thế kỷ XVI, XVII khi mà các môn khoa học tự nhiên như toán học, hóa học, vật lý học xuất hiện. Lúc đầu, dự báo với độ chính xác cao thường áp dụng vào trong vật lý cổ điển, hóa học và đặt trong phạm vi không gian và thời gian rất khắt khe. Sau đó, sự xuất hiện nhiều dự báo mà hiện tượng dự báo rất phức tạp, chịu sự tác động của nhiều yếu tố: sự tiến bộ của khoa học - kỹ thuật, sự phát triển của kinh tế - xã hội, chính trị, sự thay đổi về tâm lý và chuẩn mực đạo đức xã hội đòi hỏi dự báo phải vận dụng các phương pháp thống kê xác suất (dự báo với độ tin cậy nào đó chứ không phải là chính xác hoàn toàn). Trong dự báo, luôn luôn có các điểm mù. Chúng ta không thể dự báo một cách chính xác hoàn toàn điều gì sẽ xảy ra trong tương lai. Hay nói cách khác, không phải cái gì cũng có thể dự báo được nếu chúng ta thiếu hiểu biết về vấn đề cần dự báo. 1.3 Các phương pháp dự báo Có nhiều học giả có cách phân loại phương pháp dự báo khác nhau. Tuy nhiên theo học giả Gordon, trong hai thập kỷ gần đây, có 8 phương pháp dự báo được áp dụng rộng rãi trên thế giới: - Tiên đoán - Ngoại suy xu hướng - Phương pháp chuyên gia - Phương pháp mô phỏng - Phương pháp ma trận tác động qua lại - Phương pháp kịch bản - Phương pháp cây quyết định - Phương pháp dự báo tổng hợp Tuy nhiên, theo phân loại tại Việt Nam các phương pháp dự báo thường chia thành 2 nhóm chính là phương pháp định tính và phương pháp định lượng. 5 1.3.1 Phương pháp dự báo định tính Phương pháp này dựa trên cơ sở nhận xét của những yếu tố liên quan, dựa trên những ý kiến về các khả năng có liên hệ của những yếu tố liên quan này trong tương lai. Phương pháp định tính có liên quan đến mức độ phức tạp khác nhau, từ việc khảo sát ý kiến được tiến hành một cách khoa học để nhận biết các sự kiện tương lai hay từ ý kiến phản hồi của một nhóm đối tượng hưởng lợi (chịu tác động) nào đó. 1.3.2 Phương pháp dự báo định lượng Mô hình dự báo định lượng dựa trên số liệu quá khứ, những số liệu này giả sử có liên quan đến tương lai và có thể tìm thấy được. Tất cả các mô hình dự báo theo định lượng có thể sử dụng thông qua chuỗi thời gian và các giá trị này được quan sát đo lường các giai đoạn của từng chuỗi. Tuy nhiên hiện nay thông thường khi dự báo người ta thường hay kết hợp cả phương pháp dự báo định tính và định lượng để nâng cao mức độ chính xác của dự báo. Bên cạnh đó vấn đề cần dự báo đôi khi không thể thực hiện được thông qua một phương pháp dự báo đơn lẻ mà đòi hỏi kết hợp nhiều hơn một phương pháp nhằm mô tả đúng bản chất của dự báo. Một phương pháp được áp dụng để dự báo là phương pháp ngoại suy. Trong mục tiếp theo chúng tôi sẽ trình bày phương pháp ngoại suy trong dự báo. 1.4 Phương pháp ngoại suy trong dự báo 1.4.1 Khái niệm phương pháp ngoại suy Định nghĩa 1.4.1. Ngoại suy là dựa trên những số liệu đã có về một đối tượng được quan tâm để đưa ra suy đoán hoặc dự báo về hành vi của đối tượng đó trong tương lai. Ngoại suy có 2 dạng chính là ngoại suy theo số liệu lát cắt và ngoại suy theo chuỗi số liệu lịch sử. Ngoại suy theo số liệu lát cắt: Là dựa trên hành vi của một số thành phần tại một thời điểm nào đó để ngoại suy về hành vi của các thành phần khác cũng tại thời điểm đó. Ngoại suy theo chuỗi số liệu: Là dựa trên chuỗi số liệu lịch sử và sử dụng kỹ thuật kinh tế lượng để đưa ra dự báo đối với biến quan tâm. Giả thiết cơ 6 bản là hành vi của biến được dự báo sẽ tiếp tục trong tương lai như đã diễn ra trong quá khứ. 1.4.2 Các tính chất của ngoại suy Tính chất 1.4.2. Ngoại suy mang tính chất xác suất. Mỗi đối tượng dữ liệu ngoại suy đều vận động theo một quy luật nào đó, một quỹ đạo nhất định nào đó, đồng thời trong quá trình phát triển nó luôn luôn chịu sự tác động của môi trường, hay các yếu tố bên ngoài. Bản thân môi trường hay các yếu tố tác động cũng không phải là đứng im mà luôn luôn trong trạng thái vận động và phát triển không ngừng, về phía chủ thể dữ liệu ngoại suy, những thông tin hiểu biết về đối tượng ở tương lai bao giờ cũng nghèo nàn hơn hiện tại. Vì vậy dù các thuật toán ngoại suy có hoàn thiện, có tin cậy đến đâu cũng không thể chắc chắn rằng các dữ liệu ngoại suy là hoàn toàn chính xác. Hay nói một cách khác ngoại suy dữ liệu bao giờ cũng mang tính xác suất. Tính chất 1.4.3. Ngoại suy dữ liệu là đáng tin cậy. Ngoại suy mang tính xác suất nhưng đáng tin cậy vì nó dựa trên những cơ sở lý luận và phương pháp luận khoa học. Đó là phép biện chứng duy vật và lịch sử, hệ thống các lý luận về khoa học, về kinh tế và xã hội. Phương pháp và công cụ xử lý thông tin ngày càng hiện đại. Xét về mặt bản chất, ngoại suy dữ liệu là sự phản ảnh vượt trước, là những giả thiết về sự phát triển của dữ liệu ngoại suy trong tương lai được đưa ra trên cơ sở nhận thức các quy luật phát triển và những điều kiện ban đầu với tư cách là những giả thiết. Theo đà phát triển của khoa học kỹ thuật, trình độ nhận thức quy luật và các điều kiện ban đầu ngày càng được hoàn thiện thì độ tin cậy của dữ liệu ngoại suy cũng không ngừng được nâng cao độ tin cậy. Tính chất 1.4.4. Ngoại suy dữ liệu mang tính chất đa kết quả. Mỗi phương pháp ngoại suy được thực hiện trên những giả thiết nhất định – ngoại suy có điều kiện. Tập hợp các giả thiết như vậy gọi là phông dữ liệu ngoại suy. Ngoại suy có thể được tiến hành trên các phông dữ liệu ngoại suy khác nhau, do những nguyên nhân chủ quan và khách quan khác nhau và vì vậy có thể có nhiều kết quả ngoại suy khác nhau. Tính đa kết quả một mặt là thuộc tính khách quan của dữ liệu ngoại suy, nhưng mặt khác lại là phù hợp với yêu cầu của công tác quản lý, nó làm cho việc ra quyết định cũng như chỉ đạo thực hiện quyết định quản lý trở nên linh hoạt hơn, dễ thích nghi với sự biến đổi vô cùng phức tạp của tình hình thực tế. 7 1.5 Các phương pháp ngoại suy Trong tiểu mục này chúng tôi nêu một số phương pháp ngoại suy thường dùng như: phương pháp ngoại suy suy ra từ nội suy, phương pháp hồi quy tuyến tính đơn và mô hình hồi quy đa thức. 1.5.1 Phương pháp ngoại suy được suy ra từ nội suy Chúng ta biết rằng nội suy là một bài toán cơ bản của giải tích số. Trong đó một trường hợp thường gặp của bài toán này là cần phục hồi hàm số f (x) đối với mọi điểm x ∈ [a, b] trong khi chỉ biết giá trị của nó tại một số điểm x0 , x1 , . . . , xn ∈ [a, b]. Những giá trị này thường là các giá trị quan sát, hoặc đo đạc được. Bài toán nội suy hàm số một biến được phát biểu như sau: Trên đoạn [a, b] cho các điểm nút a ≤ x0 < x1 < . . . < xn ≤ b và tại các điểm này cho các giá trị f (xi ) với i = 0, 1, . . . , n của hàm f (x). Cần xây dựng hàm g(x) dễ tính và trùng với hàm f (x) tại các điểm nút trên, nghĩa là g(xi ) = f (xi ) với i = 0, 1, . . . , n. (1.1) Sau khi xây dựng được hàm g(x) ta sẽ dùng nó để tính giá trị tại các đầu mút ngoài đoạn [a, b]. Đó chính là phương pháp dùng nội suy để suy ra ngoại suy. Dưới đây chúng tôi nêu hai phương pháp nội suy kinh điển là phương pháp nội suy Newton và phương pháp nội suy Lagrange. Phương pháp nội suy Lagrange Đa thức Lagrange là một phương pháp thay thế hữu hiệu để giải đồng thời các phương trình từ ràng buộc rằng đa thức phải đi qua các giá trị dữ liệu. Cho các nút nội suy a ≤ x0 < x1 < . . . < xn ≤ b và các giá trị của hàm f (x) tại các nút nội suy: yi = f (xi ), với i = 0, 1, . . . , n. Như đã trình bày ở trên, chúng ta sẽ tìm một đa thức Pn (x) bậc n Pn (x) = n X k=0 Ck xk . (1.2) 8 Từ điều kiện nội suy Pn (xi ) = f (xi ) với i = 0, 1, . . . , n. (1.3) Cho ta hệ phương trình để xác định các hệ số Ck với k = 0, 1, . . . , n. C0 + C1 x0 + . . . + Cn xn0 = f (x0 ) ...... (1.4) C0 + C1 xn + . . . + Cn xnn = f (xn ) Hệ (1.4) có nghiệm duy nhất nên đa thức nội suy (1.2) luôn tồn tại duy nhất. Để xây dựng công thức tính đa thức (1.2) mà không cần giải hệ (1.4) ta xét các đa thức bậc n có dạng Pi (x) = (x − x0 ) . . . (x − xi−1 )(x − xi+1 ) . . . (x − xn ) . xi − x0 . . . (xi − xi−1 )(xi − xi+1 ) . . . (xi − xn ) (1.5) Để ý rằng  Pi (xj ) = δij = 1 nếu i = j 0 nếu i 6= j (1.6) yi Pi (x). (1.7) Đặt Pn (x) = n X i=0 Từ (1.6) ta có Pn (xj ) = n X yi Pi (xj ) = yj (j = 0, 1, . . . , n) i=0 Như vậy Pn (x) là đa thức nội suy duy nhất cần tìm và được gọi là Đa thức nội suy Lagarange. Đây phương pháp đặc biệt thuận tiện để nội suy đa thức từ bảng giá trị khi các điểm giá trị không cách đều nhau. Phương pháp này thích hợp để tìm kiếm các giá trị gần nhất trong bảng và sau đó sử dụng nội suy bậc nhỏ nhất phù hợp với dạng hàm của dữ liệu. Đa thức bậc cao đi qua đồng thời nhiều giá trị của bảng có thể biến động nhanh chóng giữa các giá trị trong bảng. ? Sai số của phép nội suy đa thức Lagrange: Đánh giá sai số tức là ta cần đánh đánh giá độ lệch |f (x) − Pn (x)|, sai số này được cho Định lý sau. 9 Định lý 1.5.1. Giả sử hàm số f (x) ∈ C n+1 [a, b], tức là có đạo hàm liên tục đến cấp n + 1 trên [a, b] chứa tất cả các nút nội suy xi với i = 0, 1, . . . , n. Khi đó sai số của nội suy Rn (x) = f (x) − Pn (x) có dạng Rn (x) = f (n+1) (ξ) ωn+1 (x), (n + 1)! (1.8) trong đó, ξ là điểm phụ thuộc x và thuộc đoạn [a, b], còn ωn+1 (x) = (x − x0 )(x − x1 ) . . . (x − xn ) = n Y (x − xi ). (1.9) i=0 và x là điểm cần đánh giá sai số. Chứng minh. Nếu x trùng với một trong các nút nội suy thì Rn (x) = 0. Vì thế ta chỉ xét sai số Rn (x) khi x 6= xi với i = 0, 1, . . . , n. Khi đó ωn+1 (x) 6= 0. Xét hàm với biến số z: F (z) = Rn (z) − kωn+1 (z) (1.10) Hằng số k được chọn từ điều kiện F (x) = 0, nghĩa là k= f (x) − Pn (x) Rn (x) = ωn+1 (x) ωn+1 (x) (1.11) Mặt khác, F (xi ) = 0 với i = 0, 1, . . . , n nên F (z) có n + 2 nghiệm phân biệt x, x0 , x1 , . . . , xn . Theo Định lý Rolle thì F 0 (z) có ít nhất n + 1 nghiệm, . . . , F (n+1) (z) có ít nhất 1 nghiệm. Giả sử nghiệm đó là ξ, rõ ràng ξ = ξ(x) và nằm trong [a, b]. Như vậy 0 = F (n+1) (ξ) = f (n+1) (ξ) − k(n + 1)! f (n+1) (ξ) hay k = . Từ hệ trên và (1.11) ta suy ra (1.8). (n + 1)!   Nhận xét 1.5.2. Gọi Mn+1 = max f (n+1) (x) ta có đánh giá a≤x≤b |f (x)| − Pn (x)| ≤ Mx |ωn+1 (x)|. (n + 1)! Phương pháp nội suy Newton Phương pháp nội suy Newton xây dựng một đa thức dựa vào các điểm dữ liệu cho trước. Nếu có n + 1 giá trị (từ 0 đến n), ta có xây dựng một đa thức duy nhất Pn có bậc n mà đi qua tất cả n + 1 điểm. 10 Cho một tập n + 1 điểm ((x0 , y0 ) = f (x0 )), . . . , ((xn , yn ) = f (xn )), (1.12) trong đó các điểm xi là phân biệt. Ta dễ dàng xác định đa thức nội suy nếu ta xây dựng nó dưới dạng sau Pn (x) = C0 +C1 (x−x0 )+C2 (x−x0 )(x−x1 )+. . .+Cn (x−x0 )(x−x1 ) · · · (x−xn−1 ). (1.13) Bây giờ dùng điều kiện nội suy Pn (xi ) = f (xi ) ta thu được hệ phương trình hệ số Ci như sau f (x0 ) = C0 , (1.14) f (x1 ) = C0 + C1 (x1 − x0 ), (1.15) f (x2 ) = C0 + C1 (x1 − x0 ) + C2 (x2 − x0 )(x2 − x1 ), .. . (1.16) f (xn ) = C0 + C1 (xn − x0 ) + C2 (xn − x0 )(xn − x1 ) + . . . + Cn (xn − x0 )(xn − x1 ) · · · (xn − xn−1 ). (1.17) Từ hệ trên ta thu được C0 = f (x0 ), f (x1 ) − f (x0 ) C1 = , x1 − x0 C2 = f (x2 )−f (x1 ) x2 −x1 − f (x1 )−f (x0 ) x1 −x0 x2 − x0 (1.18) (1.19) , (1.20) .. . Các biểu thức ở vế phải của các phương trình trên thường được ký hiệu bằng f [x0 ], f [x1 , x0 ], f [x2 , x1 , x0 ], . . . và được gọi là các tỉ sai phân bậc 0 tại điểm x0 , bậc 1 tại điểm x0 , x1 , bậc 2 tại điểm x0 , x1 , x2 , . . . . Tỉ sai phân bậc k của hàm f tại x0 , x1 , . . . , xk là f [xk , xk−1 , . . . , x0 ] = f [xk , xk−1 , . . . , x0 ] − f [xk−1 , xk−2 , . . . , x1 ] xk − x0 Theo đó ta có thể viết Pn (x) = f [x0 ] + f [x1 , x0 ](x1 − x0 ) + f [x2 , x1 , x0 ](x − x0 )(x − x1 )+ + f [xn , xn−1 , . . . , x0 ](x − x0 )(x − x1 ) . . . (x − xn−1 ). (1.21) 11 Ta có thể chỉ ra rằng f [xk ,xk−1 , . . . , x0 ] = k X i=0 f (xi ) . (1.22) (xi − x0 )(xi − x1 ) · · · (xi − xi−1 )(xi − xi+1 ) · · · (xi − xk ) Hai biểu diễn trên được gọi là đa thức nội suy dạng Newton. Dạng đa thức nội suy như này sẽ thuận tiện nếu ta có sự tăng theo dãy của mạng dữ liệu, tức là ta thêm điểm thứ n+2 và tăng bậc của đa thức từ n lên (n+1). Quá trình này chỉ yêu cầu tính thêm một số hạng f [xn+1 , xn , . . . , x0 ](x − x0 )(x − x1 ) · · · (x − xn ) trong biểu diễn của Pn (x). ? Sai số của đa thức nội suy Newton: Từ định nghĩa các tỷ sai phân viết cho hàm f (x), tương tự như trên ta thu được f (x) =f [x0 ] + f [x1 , x0 ](x1 − x0 ) + f [x2 , x1 , x0 ](x − x0 )(x − x1 )+ + f [xn , xn−1 , . . . , x0 ](x − x0 )(x − x1 ) . . . (x − xn−1 ) + f [xn , xn−1 , . . . , x0 ](x − x0 )(x − x1 ) . . . (x − xn ) So với (1.21) ta thấy f (x) = Pn (x) + ωn+1 (x)f [xn , xn−1 , . . . , x0 ], trong đó, ωn+1 (x) = (x − x0 )(x − x1 ) . . . (x − xn ) = n Y (x − xi ). i=0 Theo công thức (1.8) ta có: f (n+1) (ξ) Rn (x) = ωn+1 (x), (n + 1)! vậy f (n+1) (ξ) f [xn , xn−1 , . . . , x0 ] = ωn+1 (x), ξ ∈ (a, b). (n + 1)! Hiện tượng Runge Khi một hàm f được xấp xỉ trên đoạn [a, b] bằng phương pháp nội suy đa thức P , sự khác biệt giữa f và P (theo lý thuyết) sẽ bằng không tại các điểm nội suy. Một cách tự nhiên, ta mong rằng hàm f sẽ được xấp xỉ tốt tại các điểm ở giữa, khi số điểm tăng lên, phép nội suy này sẽ trở nên tốt hơn. 12 Hiện tượng Runge là một vấn đề xảy ra khi sử dụng phép nội suy đa thức với các đa thức bậc cao. Nó được phát hiện bởi Carl David Tolme Runge khi nghiên cứu dáng điệu sai số khi sử dụng phép nội suy đa thức để xấp xỉ các hàm trơn và đơn giản nhất định. Một ví dụ cụ thể của hiện tượng đáng chú ý này là hàm Runge: f (x) = 1 , 1 + x2 (1.23) trên đoạn [-5, 5]. Ký hiệu Pn là đa thức nội suy hàm này tại n + 1 điểm cách đều nhau trên đoạn [−5, 5], bao gồm cả các điểm đầu mút. Để sử dụng phương pháp Newton, ta chọn 11 điểm cách đều nhau (tức là, ta tìm đa thức nội suy cấp 10). Trong đoạn [a, b], tập n điểm cách đều nhau là xi = a + (i − 1) b−a , 1 ≤ i ≤ n. n−1 (1.24) Hình 1.1: Nội suy hàm Runge Như minh họa trong Hình 1.1, đường cong thu được nhận giá trị âm, mà hiển nhiên, f (x) không có. Cụ thể hơn, đường nội suy thu được dao động dần về đầu mút của khoảng. Khi thêm càng nhiều điểm ta sẽ thu được đa thức bậc cao hơn và điều này chỉ làm vấn đề trở nên tồi tệ hơn với độ dao động rộng hơn. Vì vậy trong các bài toán ở Chương 2 chúng tôi chỉ chọn một số nút nội suy đáng tin cậy để thành lập đa thức nội suy. 13 Ví dụ 1.5.3. Tìm đa thức nội suy hàm y = 3x trên đoạn [−1, 1] dựa vào các giá trị của hàm tại các điểm x0 = −1, x1 = 0, x2 = 1. Sử dụng đa thức này 1 5 tính giá trị gần đúng tại x = và x = . 2 4 Giải. Ta có đa thức nội suy Lagrange như sau: (x + 1)(x − 1) (x + 1)x 1 x(x − 1) +1 +3 1 3 (−1)(−1 − 1) 1(−1) 1+1 1 = (2x2 + 4x + 3) 3 P2 (x) = 1 5 Tính giá trị của đa thức khi x = , x = . 2 4   1 2 P2 = 11 ≈ 1, 833, 6 = 89 ≈ 3, 708. 24   P2 5 4 5 1 và x = thì giá trị của hàm số y = 3x 2 4 lần lượt có giá trị xấp xỉ bằng 1, 732 và 3, 948. Nhận xét 1.5.4. Tại các giá trị x = Ví dụ 1.5.5. Cho quan hệ y = f (x) bởi x 1.3 2.8 4.5 6.3 7.4 y 4.2557 6.6421 11.5334 15.1436 18.3085 1) Dựng đa thức nội suy? 2) Tính gần đúng f (3), f (4), f (6) (nội suy)? 3) Tính gần đúng f (8), f (9) (ngoại suy)? Giải. 1) Lập bảng tỉ sai phân Khi đó ta có đa thức nội suy Newton P4 (x) = 4.2557 + 1.5909(x − 1.3) + 0.4020(x − 1.3)(x − 2.8) − 0.1302(x − 1.3)(x − 2.8)(x − 4.5) + 0.0410(x − 1.3)(x − 2.8)(x − 4.5)(x − 6.3) = 0.0410x4 − 0.7411x3 + 4.64879x2 − 9.310845x + 10.01444