Bài giảng Phương pháp tính: Chương 3 - TS. Nguyễn Quốc Lân

Chia sẻ: Na Na | Ngày: | Loại File: PPT | Số trang:26

Thêm vào BST

Báo xấu

588
lượt xem 143
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Phương pháp tính: Chương 3 trình bày phương pháp nội suy và bình phương cực tiểu. Nội dung chương này bao gồm: Nội suy đa thức Lagrange, sai số nội suy Lagrange, nội suy Newton (mốc cách đều), nội suy ghép trơn (Spline) bậc ba, bình phương cực tiểu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Phương pháp tính: Chương 3 - TS. 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ỂU • TS. NGUYỄN QUỐC LÂN (04/2006)
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
BÀI TOÁ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 Moác noäi suy x0 x1 … x = α ∉{ xk } … xn-1 xn Giaù trò noäi y0 y1 … y=? … yn-1 yn 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 = α? 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 Đ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 Moác noäi suy xk 2 2.5 4 Tại x = 3, ybảng ≈ ? Giaù Trò noä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
VÍ DỤ SAI SỐ ------------------------------------------------------------------------------------------------------------------------------------ max f ( n +1) ( x ) Sai số: f ( x) − L( x) ≤ [ a ,b ] ( x − x0 )  ( x − xn ) = ∆ Noäi taïix ( n + 1)! suy Ướ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 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ứ 4 3 −52 Giải: f ( x ) = x ⇒ M = max f ( 3) ( x) = max x [ 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!
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 Moác NS 2 2.5 4 3 mốc ⇒ 3 ĐT NSCS Giaù Trò NS 0.5 0.4 0.25 ÑTNSCS L0(x) 1 0 0 ( x − 2.5)( x − 4) L0 ( x) = ÑTNSCS L1(x) 0 1 0 ( 2 − 2.5)( 2 − 4) L( x ) ÑTNSCS L2(x) 0 0 1 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)}?
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 ) ⇒ Ñathöùc suyL( x) = y0 L0 ( x) + y1 L1 ( x) +  + yn Ln ( x) noäi Ư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
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) L0 ( x ) = ⇒ L0 ( 3.5) = 0.0625 (1 − 2)(1 − 3)(1 − 4) ( 3.5 − 1)( 3.5 − 3)( 3.5 − 4) L2 (3.5) = L1 ( 3.5) = = ( 2 − 1)( 2 − 3)( 2 − 4) L3 (3.5) = L( x) = 5 L0 ( x) + 7 L1 ( x) + 8 L2 ( x ) + 9 L3 ( x) ⇒ L( 3.5) = 8.4375 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 NS Gtrò NS ∆yk ∆2 yk ∆3 yk x0 y0 x1 y1 ∆y0 ∆2 y0 x2 y2 ∆y1 ∆3 y0 ∆2 y1 x3 y3 ∆y2 Cấp 1: ∆ yk = yk+1 – yk VD: Bảng sai xk yk ∆y ∆2 y Ví dụ: ∆ y0 = y1 – y0 phân 3 mốc 1 2 2 1 2 4 3 ∆ yk = ∆ yk+1 – ∆ yk … 2 (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 t= ⇔ x = x0 +th ⇒ Đa thức nội suy tiến: h t ( t − 1) 2 t (t − 1)  (t − n + 1) n N ( x ) = y0 + t∆y0 + ∆ y0 +  + ∆ y0 2! n! Đ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 − xn t= ⇔ x = xn + th ⇒ Đa thức nội suy lùi: h t ( t + 1) 2 t  (t + n − 1) n N ( x ) = yn + t∆yn −1 + ∆ yn − 2 +  + ∆ y0 2! n! Sai 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°) 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
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 ) N1 (t ) = 0.2588 + 0.0832t − 0.0026 − 0.0006 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 2 (t ) = 0.8192 + 0.0532t − 0.0057 − 0.0003 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!
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
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!
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
Ý TƯỞNG NỘI SUY GHÉP TRƠN BẬC 3 ------------------------------------------------------------------------------------------------------------ S 0 ( x1 ) = y1 S1 ( x ) S0 ( x ) S2 ( x) S 0 ( x0 ) = y0 S 0 ( x1 ) = S1 ( x1 )  S '0 ( x1 ) = S '1 ( x1 ) S ' '0 ( x0 ) = 0 S ' ' ( x ) = S ' ' ( x )  0 1 1 1 [ x0 , x1 ] [ x1 , x2 ] [ x2 , x3 ]
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 0 ( x ) = a0 + b0 x + c0 x 2 + d 0 x 3 , x ∈ [1,2] S ( x) =   S1 ( x ) = a1 + b1 x + c1 x 2 + d1 x 3 , x ∈ [ 2,3] Dạng thuận tiện hơn:S ( x ) = a + b ( x − 1) +  , x ∈ [1,2]  0 S ( x) =  0 0 S1 ( x ) = a1 + b1 ( x − 2 ) +  , x ∈ [ 2,3]
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 S 0 = a0 + b0 ( x − x0 ) + c0 ( x − x0 ) 2 + d 0 ( x − x0 ) 3 , x ∈ [ x0 , x1 ]  S = a1 + b1 ( x − x1 ) + c1 ( x − x1 ) + d1 ( x − x1 ) , x ∈ [ x1 , x2 ] 2 3 S = 1  S = a + b ( x − x ) + c ( x − x ) 2 +  , x ∈ [ x , x ]  n −1 n −1 n −1 n −1 n −1 n −1 n −1 n 2/ Điều kiện nội suy: S(xk) = yk, k = 0, 1 … n  S k ( xk +1 ) = S k +1 ( xk +1 )  3/ Ghép trơn:  S k ' ( xk +1 ) = S k +1 ' ( xk +1 ) k = 0 → ( n − 2 )   S k " ( xk +1 ) = S k +1" ( xk +1 ) 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 II/ c = [c0, … cn]T 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  3(a − a ) 3( a − a ) h0    0 h1 2(h1 + h2 ) h2 0    3 2 − 2 1  A=   e= h2 h1   .................... .......... .......... .......... ..........  .......... .......... .......... .......... ..    0  hn − 2 2(hn − 2 + hn − 1) hn − 1   3(an − an −1 ) 3( an −1 − an −2 )   −     hn −1 hn −2   0 .......... .......... .... 0 1    0   ak +1 − ak hk (2ck + ck +1 ) Bước bk = − , k = 0 ... n − 1 hk 3 III: ck +1 − ck dk = , k = 0  n −1 3hk
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 Moác NS x0 = 1 x1 = 2 x2 = 3 x3 = 4 Giaù trò y0 = 2 y1 = 1 y2 = 3 y3 = 2 NS a0 + b0 ( x − 1) + c0 ( x − 1) 2 + d 0 ( x − 1) 3 , x ∈ [1,2]   Hàm spline S =  a1 + b1 ( x − 2 ) + c1 ( x − 2 ) + d1 ( x − 2 ) , x ∈ [ 2,3] 2 3   a2 + b2 ( x − 3) + c2 ( x − 3) 2 + d 2 ( x − 3) 3 , x ∈ [ 3,4] Bước I: Độ dài bước h0 = h1 = h2 = 1. chia số: ak = yk , 0 ≤ k ≤ 3 ⇒ a0 = 2, a1 = 1, a2 = 3, a3 = 2 Hệ