Bài giảng Phương pháp tính - Chương 3: Nội suy và bình phương cực tiểu - Nguyễn Quốc Lân

BỘ MÔN TOÁN ỨNG DỤNG - ĐHBK-------------------------------------------------------------------------------------PHƯƠNG PHÁP TÍNH – HK 2 0506 CHƯƠNG 3 NỘI SUY VÀ BÌNH PHƯƠNG CỰC TIỂUTS. NGUYỄN QUỐC LÂN (04/2006) NỘI DUNG--------------------------------------------------------------------------------------------------------------1- NỘI SUY ĐA THỨC LAGRANGE2- SAI SỐ NỘI SUY LAGRANGE5- BÌNH PHƯƠNG CỰC TIỂU3- NỘI SUY NEWTON (MỐC CÁCH ĐỀU)4- NỘI SUY GHÉP TRƠN (SPLINE) BẬC BABÀI TOÁN TỔNG QUÁT VỀ NỘI SUY ---------------------------------------------------------------------------------------------------------------------------xk : mốc nội suy, yk : giá trị (hàm) nội suy Từ bảng này, nội suy giá trị ybảng tại điểm x = ? Moác noäi suyx0 x1 x =   xk xn-1 xn Giaù trò noäi suyy0 y1 y = ?yn-1 yn Nội suy đa thức: Xác định đa thức y = P(x) thoả điều kiện nội suy P(xk) = yk, k = 0 n  ybảng  P() Nội suy: Bảng chứa (n+1) cặp dữ liệu { (xk, yk) }, k = 0  nNỘI SUY ĐA THỨC LAGRANGE ---------------------------------------------------------------------------------------------------------------------------Bảng chứa (n+1) cặp số liệu {(xk,yk)} , k = 0  n ! đa thức L(x), bậc  n, thoả đ/kiện nội suy L(xk) = yk, k = 0 n Cách 1: 3 mốc  n = 2  L(x) = ax2 + bx + c (3 hệ số cần tìm)Tìm đa thức nội suy Minh hoạ bảng 3 dữ liệu: {(xk,yk)} , k=02 Tại x = 3, ybảng ? Moác noäi suy xk 22.54Giaù Trò noäi suy yk 0.50.40.25ybảng  L(3) = 0.325VÍ DỤ SAI SỐ ------------------------------------------------------------------------------------------------------------------------------------Sai số:Giải: Kết quả: Nhắc lại: Sai số: luôn làm tròn lên! Ước lượng sai số của việc xấp xỉ giá trị bằng đa thức nội suy Lagrange bậc hai hàm y = xây dựng tại các mốc x0 = 100, x1 = 121, x2 = 144. Yêu cầu: Làm tròn kết quả (sai số) đến chữ số lẻ thứ 4NHIỀU MỐC  ĐA THỨC NỘI SUY CƠ SỞ -----------------------------------------------------------------------------------------------------------------------Đa thức nội suy cơ sở tại xk: Lk(xk) = 1, Lk(xi) = 0  i  kĐa thức nội suy: L(x) = 0.5L0(x) + 0.4L1(x) + 0.25L2(x)Moác NS 22.54Giaù Trò NS0.50.40.25ÑTNSCS L0(x) 100ÑTNSCS L1(x)010ÑTNSCS L2(x)001Thiết lập công thức tổng quát với (n + 1) mốc {(xk, yk)}?3 mốc  3 ĐT NSCSCÔNG THỨC TỔNG QUÁT ---------------------------------------------------------------------------------------------------------------------------(n+1) mốc  (n+1) đa thức nội suy cơ sở. Đa thức nội suy cơ sở Lk(x) tại xk (k = 0 n): Lk(xk) = 1, Lk(xi) = 0  i  k:Ưu điểm: Công thức tổng quát cho đa thức nội suy L(x)Chỉ phụ thuộc bộ mốc {xk} (0  k  n), không phụ thuộc ykVÍ DỤ ----------------------------------------------------------------------------------------------------------------------Bảng 4 mốc 1, 2, 3, 4 ; 4 giá trị 5, 7, 8, 9. Viết ra biểu thức các đa thức nội suy cơ sở. Tính giá trị bảng tại x = 3.5?Viết biểu thức Lk(x) (Không tính!) Thay x  Giá trịNỘI SUY NEWTON – MỐC CÁCH ĐỀU -----------------------------------------------------------------------------------------------------------------Bảng {(xk,yk)} , k = 0  n, mốc nội suy cách đều: x0, x1 = x0 + h, x2 = x1 + h xn = xn-1 + h. Lập bảng sai phân :Moác NSGtrò NS x0 y0 x1 y1 x2 y2 x3 y3 2yk = yk+1 – yk Cấp 1: yk = yk+1 – ykVí dụ: y0 = y1 – y0 xkyky2y122437VD: Bảng sai phân 3 mốc (cách đều) ĐA THỨC NỘI SUY NEWTON ------------------------------------------------------------------------------------------------------------------Đa thức nội suy Newton tiến: x x0 (đầu bảng)  x = x0 +th  Đa thức nội suy tiến:Đa thức nội suy Newton lùi: x  xn (cuối bảng) x = xn + th  Đa thức nội suy lùi:Đa thức theo t & Sai phân nằm trên đường chéo tiếnSai phân nằm trên đường chéo lùi (từ cuối bảng đi lên)VÍ DỤ NỘI SUY NEWTON ------------------------------------------------------------------------------------------------------------------Cho bảng giá trị sinx từ 15  55. Xây dựng đa thức nội suy tiến (lùi) cấp 3 & tính sin16 (sin54)xyy 2y 3y 150.2588200.3420250.4226300.5350.5736400.6428450.7071500.7660550.8192VÍ DỤ NỘI SUY NEWTON ---------------------------------------------------------------------------------------------------------------------------Tất cả sai phân: Nội suy Newton  Lagrange!Đa thức nội suy tiến: x  15x = 16 t = 0.2  N1(0.2) = 0. 2756sin16 = 0. 2756Đa thức nội suy lùi: x  55x = 54 t = –0.2  N2(–0.2) = 0.80903 sin54 = 0. 8090Câu hỏi: Tính tại x = 54 với Nội suy tiến. Nhận xét?HIỆN TƯỢNG RUNGE ----------------------------------------------------------------------------------------------------------------Nội suy hàm f(x) = 1/(1+ 25x2), x  [-1, 1] bằng đa thức nội suy, 5 mốc cách đều. Tính L(0.95), so sánh giá trị tính được với giá trị chính xác f(0.95)Lập bảng nội suy: 5 mốc cách đều trên [–1, 1] x0 = –1, x1 = –0.5, x2 = 0, x3 = 0.5, x4 = 1 & yk = f(xk) Giá trị L(0.95) = Giá trị chính xác f(0.95) = 0.04 xk–1 –0.5 0.0.51.ykKẾT QUẢ ---------------------------------------------------------------------------------------------------------------So sánh đồ thị hàm ban đầu f(x) và đa thức nội suy P4(x) Tăng số nút có thể khiến sai số tăng!NỘI SUY GHÉP TRƠN --------------------------------------------------------------------------------------------------------------Nội suy Lagrange: Bậc quá lớn  Đồ thị phức tạpThay đa thức nội suy bậc n bằng đa thức nội suy bậc thấp (bậc 1, 2, 3 ) trên từng đoạn [xk, xk+1], k = 0 n – 1 Ý TƯỞNG NỘI SUY GHÉP TRƠN BẬC 3 ------------------------------------------------------------------------------------------------------------XÂY DỰNG HÀM NỘI SUY GHÉP TRƠN BẬC 3 ------------------------------------------------------------------------------------------------------------------Tìm hàm bậc 3 trên từng đoạn, liên tục và có đạo hàm đến cấp 2 nội suy bảng số liệu sau: Hàm nội suy:Dạng thuận tiện hơn:x123y23–4 NỘI SUY SPLINE (GHÉP TRƠN) BẬC 3 ---------------------------------------------------------------------------------------------------------------------------1/ Hàm dạng bậc 3 trên từng đoạn [xk,xk+1], k = 0  n –12/ Điều kiện nội suy: S(xk) = yk, k = 0, 1 n 3/ Ghép trơn: 4/ Điều kiện biên tự nhiên: S’’(x0) = S’’(xn) = 0 GIẢI THUẬT NỘI SUY SPLINE BẬC 3 -------------------------------------------------------------------------------------------------------------------------I/ Độ dài hk = xk+1 – xk, k = 0 n –1. Hệ số ak = yk, k = 0 n Bước III:II/ c = [c0, cn]T là nghiệm (cn = S’’(xn)/2) hệ Ac = e với VÍ DỤ NỘI SUY SPLINE (GHÉP TRƠN) BẬC 3 --------------------------------------------------------------------------------------------------------------------Lập hàm nội suy spline bậc 3 g(x) thoả điều kiện biên tự nhiên và nội suy bảng sauBước I: Độ dài bước chia Moác NSx0 = 1 x1 = 2 x2 = 3 x3 = 4 Giaù trò NSy0 = 2 y1 = 1 y2 = 3 y3 = 2 Hàm spline Hệ số: BẢNG TÍNH NỘI SUY SPLINE (GHÉP TRƠN) BẬC 3 --------------------------------------------------------------------------------------------------------------------------------Bước II: c3 = g”(x3)/2  c = [c0, c1, c2, c3]T là nghiệm khk ak bk ek ck dk 012001112133200III/ bk, dk, 0  k  2: BÌNH PHƯƠNG CỰC TIỂU ----------------------------------------------------------------------------------------------------------Thực nghiệm: Thống kê lượng mưa 12 tháng & vẽ đồ thịThaùng12345678Löôïng möa550665540580610605570PHƯƠNG PHÁP BÌNH PHƯƠNG CỰC TIỂU (BPCT) ----------------------------------------------------------------------------------------------------------------------Nhiều dữ liệu & yk có sai số: Aùp đặt L(xk) = yk: vô nghĩa! Giải quyết: h(x) xấp xỉ bảng {(xk, yk)} theo nghĩa BPCT TRƯỜNG HỢP TUYẾN TÍNH ---------------------------------------------------------------------------------------------------------------------------h tuyến tính: h(x) = ax + b Điểm dừng: Giải hệ 2 phương trình 2 ẩn tìm a, b. So với đường cong y = h1(x)  Tổng S =  (h1(xk) – yk)2: càng bé càng tốt VD: Tìm hàm bậc 1 xấp xỉ bảng sau theo nghĩa BPCT xk12345678910yk1.33.54.25.07.08.810.112.513.15.6ĐA THỨC BÌNH PHƯƠNG CỰC TIỂU BẬC CAO -------------------------------------------------------------------------------------------------------------------------------h(x) = ax2 + bx + c Điểm dừng: Tổng quát: Điểm dừng hàm tổng bình phương độ lệchh = ax2 + bxHÀM MŨ ---------------------------------------------------------------------------------------------------------------------------VD: Xấp xỉ bảng số với p/pháp bình phương cực tiểu y = h(x) = beax  lny = ax + lnb  Tương quan bậc 1 giữa lnyk & xk. Lập bảng {(xk, lnyk)} xác định a & lnb. kxkyklnykxk2xklnyk11.005.101.6291.00001.62921.255.791.7561.56252.19531.506.531.8762.25002.81441.757.452.0083.06253.51452.008.462.1354.00004.2707.509.40411.87514.422