Xem mẫu
- 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ệ
nguon tai.lieu . vn