›
›

Phương pháp tính - Chương 3: Nội suy và bình phương cực tiểu

ppt 26 trang vanle 4370
Download
Bạn đang xem 20 trang mẫu của tài liệu "Phương pháp tính - Chương 3: Nội suy và bình phương cực tiểu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptphuong_phap_tinh_chuong_3_noi_suy_va_binh_phuong_cuc_tieu.ppt

Nội dung text: Phương pháp tính - Chương 3: Nội suy và bình phương cực tiểu

  1. BỘ MƠN TỐ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ỂU • TS. NGUYỄN QUỐC LÂN (04/2006)
  2. NỘI DUNG 1- NỘI SUY ĐA THỨC LAGRANGE 2- SAI SỐ NỘI SUY LAGRANGE 3- NỘI SUY NEWTON (MỐC CÁCH ĐỀU) 4- NỘI SUY GHÉP TRƠN (SPLINE) BẬC BA 5- BÌNH PHƯƠNG CỰC TIỂU
  3. BÀI TỐN TỔNG QUÁT VỀ NỘI SUY Nội suy: Bảng chứa (n+1) cặp dữ liệu { (xk, yk) }, k = 0 → n Mốc nội suy x0 x1 x = xk  xn-1 xn Giá trị nội suy y0 y1 y = ? yn-1 yn 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 = ? 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( )
  4. NỘ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 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, y ? Mốc nội suy xk 2 2.5 4 bảng Giá Trị nội suy yk 0.5 0.4 0.25 Cách 1: 3 mốc n = 2 L(x) = ax2 + bx + c (3 hệ số cần tìm) L(2) = 0.5 4a + 2b + c = 0.5 L(2.5) = 0.4 6.25a + 2.5b + c = 0.4 L(4) = 0.25 16a + 4b + c = 0.25 ybảng L(3) = 0.325
  5. VÍ DỤ SAI SỐ max f (n+1)(x) Sai số: f (x) − L(x) a,b (x − x )(x − x ) = (n +1)! 0 n Nội suy tại x Ước lượng sai số của việc xấp xỉ giá trị 115 bằng đa thức nội suy Lagrange bậc hai hàm y = xâyx 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ứ 4 3 −5 Giải: f (x) = x M = max f (3) (x) = max x 2 a,b 100,144 8 1 f (115)− L(115) M  (115−100)(115−121)(115−144) 3! Kết quả: Nhắc lại: Sai số: luơn làm trịn lên!
  6. NHIỀ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 Mốc NS 2 2.5 4 3 mốc 3 ĐT NSCS Giá Trị NS 0.5 0.4 0.25 (x − 2.5)(x − 4) ĐTNSCS L0(x) 1 0 0 L (x) = 0 (2 − 2.5)(2 − 4) ĐTNSCS L1(x) 0 1 0 ĐTNSCS L (x) 0 0 1 L(x) 2 L2 (x) (x − 2)(x − 4) (x − 2)(x − 2.5) L1(x) L1(x) = L2 (x) = (2.5 − 2)(2.5 − 4) (4 − 2)(4 − 2.5) L0 (x) Đa thức nội suy: L(x) = 0.5L0(x) + 0.4L1(x) + 0.25L2(x) Thiết lập cơng thức tổng quát với (n + 1) mốc {(xk, yk)}?
  7. CƠ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: Lk (xk ) =1 Lk (x0 ) = Lk (x1 ) = = Lk (xk−1 ) = Lk (xk+1 ) = = Lk (xn ) = 0 (x − x0 )(x − xk−1 )(x − xk+1 )(x − xn ) Lk (x) = , 0 k n (xk − x0 )(xk − xk−1 )(xk − xk+1 )(xk − xn ) Đa thức nội suy L(x) = y0L0 (x) + y1L1(x) ++ yn Ln (x) Ư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 yk
  8. VÍ 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? (x − 2)(x −3)(x − 4) L (x) = L (3.5) = 0.0625 0 (1− 2)(1−3)(1− 4) 0 (3.5−1)(3.5−3)(3.5− 4) L2 (3.5) = L (3.5) = = 1 (2 −1)(2 −3)(2 − 4) L3 (3.5) = L(x) = 5L0 (x) + 7L1(x) +8L2 (x)+ 9L3 (x) L(3.5) = 8.4375 Viết biểu thức Lk(x) (Khơng tính!) Thay x → Giá trị
  9. 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 : Mốc NS Gtrị NS 2 3 yk yk yk x y 0 0 y 0 2 x1 y1 y 0 3 x y y1 y 2 2 2 y 0 y 1 x3 y3 2 Cấp 1: y = y – y VD: Bảng sai 2 k k+1 k xk yk y y 1 2 Ví dụ: y0 = y1 – y0 phân 3 mốc 2 2 4 1 2y = y – y (cách đều) 3 k k+1 k 3 7
  10. ĐA THỨC NỘI SUY NEWTON Đa thức nội suy Newton tiến: x x0 (đầu bảng) x − x0 t = x = x0 +th Đa thức nội suy tiến: h t(t −1) t(t −1)(t − n +1) N(x) = y + t y + 2 y ++ n y 0 0 2! 0 n! 0 Đa thức theo t & Sai phân nằm trên đường chéo tiến Đa thức nội suy Newton lùi: x xn (cuối bảng) x − x t = n x = x + th Đa thức nội suy lùi: h n t(t +1) t(t + n −1) N(x) = y + t y + 2 y ++ n y n n−1 2! n−2 n! 0 Sai phân nằm trên đường chéo lùi (từ cuối bảng đi lên)
  11. 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) x y y 2y 3y 15 0.2588 20 0.3420 25 0.4226 30 0.5 35 0.5736 40 0.6428 45 0.7071 50 0.7660 55 0.8192
  12. VÍ DỤ NỘI SUY NEWTON x −15 Đa thức nội suy tiến: x 15 t = x =15 + 5t 5 t(t −1) t(t −1)(t − 2) N (t) = 0.2588 + 0.0832t − 0.0026 − 0.0006 1 2 3! x = 16 t = 0.2 N1(0.2) = 0. 2756 sin16 = 0. 2756 x − 55 Đa thức nội suy lùi: x 55 t = x = 55 + 5t 5 t(t +1) t(t +1)(t + 2) N (t) = 0.8192 + 0.0532t − 0.0057 − 0.0003 2 2 3! x = 54 t = –0.2 N2(–0.2) = 0.80903 sin54 = 0. 8090 Câu hỏi: Tính tại x = 54 với Nội suy tiến. Nhận xét? Tất cả sai phân: Nội suy Newton  Lagrange!
  13. 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) xk –1 –0.5 0. 0.5 1. yk 0.038 0.138 1 0.138 0.038 Giá trị L(0.95) = Giá trị chính xác f(0.95) = 0.04
  14. KẾ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!
  15. NỘI SUY GHÉP TRƠN Nội suy Lagrange: Bậc quá lớn Đồ thị phức tạp Thay đ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
  16. Ý TƯỞNG NỘI SUY GHÉP TRƠN BẬC 3 S0 (x1 ) = y1 S1(x) S0 (x) S2 (x) S (x ) = y 0 0 0 S0 (x1 ) = S1(x1 ) S'0 (x1 ) = S'1 (x1 ) S''0 (x0 ) = 0 S''0 (x1 ) = S''1 (x1 ) x0 , x1 x1, x2  x2 , x3 
  17. 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: x 1 2 3 y 2 3 –4 Hàm nội suy: S (x) = a + b x + c x2 + d x3, x 1,2 S(x) = 0 0 0 0 0 2 3 S1(x) = a1 + b1x + c1x + d1x , x 2,3 Dạng thuận tiện hơn: S0 (x) = a0 + b0 (x −1)+, x 1,2 S(x) = S1(x) = a1 + b1(x − 2)+, x 2,3
  18. 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 –1 2 3 S0 = a0 + b0 (x − x0 )+ c0 (x − x0 ) + d0 (x − x0 ) , x x0 , x1 S = a + b (x − x )+ c (x − x )2 + d (x − x )3 , x x , x  S = 1 1 1 1 1 1 1 1 1 2  2 Sn−1 = an−1 + bn−1(x − xn−1 )+ cn−1(x − xn−1 ) +, x xn−1, xn  2/ Điều kiện nội suy: S(xk) = yk, k = 0, 1 n Sk (xk+1) = Sk+1(xk+1) 3/ Ghép trơn: Sk '(xk+1) = Sk+1'(xk+1) k = 0 → (n − 2) Sk "(xk+1) = Sk+1"(xk+1) 4/ Điều kiện biên tự nhiên: S’’(x0) = S’’(xn) = 0
  19. 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 T II/ c = [c0, cn] là nghiệm (cn = S’’(xn)/2) hệ Ac = e với 1 0 0 0   0 0 3(a − a ) 3(a − a ) h 2(h + h ) h 0   0 2 1 − 1 0 0 0 1 1 h1 h0 3(a − a ) 3(a − a ) 0 h1 2(h1 + h2) h2 0  3 2 − 2 1 A = e = h2 h1 3(a − a ) 3(a − a ) 0  hn−2 2(hn−2 + hn−1) hn−1 n n−1 − n−1 n−2 h h n−1 n−2 0 0 1 0 ak+1 − ak hk (2ck + ck+1) Bước III: bk = − ,k = 0 n −1 hk 3 ck+1 − ck dk = , k = 0  n −1 3hk
  20. 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 sau Mốc NS x0 = 1 x1 = 2 x2 = 3 x3 = 4 Giá trị NS y0 = 2 y1 = 1 y2 = 3 y3 = 2 a + b x −1 + c x −1 2 + d x −1 3, x 1,2 0 0( ) 0( ) 0( )   Hàm spline 2 3 S = a1 + b1(x − 2)+ c1(x − 2) + d1(x − 2) , x 2,3 2 3 a2 + b2(x −3)+ c2(x −3) + d2(x −3) , x 3,4 Bước I: Độ dài bước chia h0 = h1 = h2 =1. Hệ số: ak = yk , 0 k 3 a0 = 2, a1 =1, a2 = 3, a3 = 2
  21. BẢNG TÍNH NỘI SUY SPLINE (GHÉP TRƠN) BẬC 3 k hk ak bk ek ck dk 0 1 2 0 0 1 1 1 2 1 3 3 2 0 0 T Bước II: c3 = g”(x3)/2 c = [c0, c1, c2, c3] là nghiệm c − c a − a h 2c + c III/ b , d , 0 k 2: 1 0 1 0 0 ( 0 1 ) k k d0 =  b0 = −  3h0 h0 3
  22. BÌNH PHƯƠNG CỰC TIỂU Thực nghiệm: Thống kê lượng mưa 12 tháng & vẽ đồ thị Tháng 1 2 3 4 5 6 7 8 Lượng mưa 550 665 540 580 610 605 570
  23. PHƯƠ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 n 2 F = h(xk ) − yk  → min k=1 h(xk )− yk y = h(x)
  24. TRƯỜNG HỢP TUYẾN TÍNH n 2 h tuyến tính: h(x) = ax + b F(a,b) = axk + b − yk  k=1 n n n 2 F = 0 a  xk + b  xk =  xk yk a k=1 k=1 k=1 Điểm dừng: n n F = 0 b a  xk + nb =  yk k=1 k=1 Giải hệ 2 phương trình 2 ẩn tìm a, b. So với đường cong y 2 = h1(x) Tổng S =  (h1(xk) – yk) : 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 xk 1 2 3 4 5 6 7 8 9 10 yk 1.3 3.5 4.2 5.0 7.0 8.8 10.1 12.5 13. 15.6
  25. ĐA THỨC BÌNH PHƯƠNG CỰC TIỂU BẬC CAO n h(x) = ax2 + bx + c 2 2 F(a,b,c) = axk + bxk + c − yk  k=1 n 4 a xk + b+ c =  F = 0 k =1 a n 3 Điểm dừng: F = 0 a x + b+ c =  b  k k =1 F = 0 n c 2 a xk + b+ nc =  k =1 Tổng quát: Điểm dừng hàm tổng bình phương độ lệch n h = ax2 + bx 2 2 F F F(a,b) = axk + bxk − yk  = = 0 k=1 a b
  26. HÀM MŨ 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. n n a x2 + lnb x = n  k  k 2 k =1 k =1 F(a,b) = ax + lnb − ln y   k k n k =1 a xk + nlnb = k =1 2 VD: Xấp xỉ k xk yk lnyk xk xklnyk 1 1.00 5.10 1.629 1.0000 1.629 bảng số với 2 1.25 5.79 1.756 1.5625 2.195 p/pháp bình 3 1.50 6.53 1.876 2.2500 2.814 phương cực 4 1.75 7.45 2.008 3.0625 3.514 tiểu 5 2.00 8.46 2.135 4.0000 4.270  7.50 9.404 11.875 14.422