Bài giảng Phương pháp tính - Chương 4: Nội suy và xấp xỉ hàm

Nội dung text: Bài giảng Phương pháp tính - Chương 4: Nội suy và xấp xỉ hàm

1. Chương 4 NỘI SUY VÀ XẤP XỈ HÀM
2. I. ĐẶT BÀI TOÁN : Để tính giá trị của một hàm liên tục bất kỳ, ta có thể xấp xỉ hàm bằng một đa thức, tính giá trị của đa thức từ đó tính được giá trị gần đúng của hàm
3. Xét hàm y = f(x) cho dưới dạng bảng số x xo x1 x2 . . . xn y yo y1 y2 . . . yn ▪ Các giá trị xk, k = 0, 1, , n được sắp theo thứ tự tăng dần gọi là các điểm nút nội suy ▪ Các giá trị yk = f(xk) là các giá trị cho trước của hàm tại xk Bài toán : xây dựng 1 đa thức pn(x) bậc ≤n thoả điều kiện pn(xk) = yk, k=0,1, n. Đa thức này gọi là đa thức nội suy của hàm f(x).
4. II. ĐA THỨC NỘI SUY LAGRANGE: y = f(x) và bảng số x xo x1 x2 . . . xn y yo y1 y2 . . . yn Ta xây dựng đa thức nội suy hàm f(x) trên [a,b]=[x0, xn]. Cho hàm
5. Đặt Ta có
6. Đa thức có bậc ≤ n và thỏa điều kiện Ln(xk) = yk gọi là đa thức nội suy Lagrange của hàm f Ví dụ : Cho hàm f và bảng số x 0 1 3 y 1 -1 2 Xây dựng đa thức nội suy Lagrange và tính gần đúng f(2).
7. Giải n = 2 Đa thức nội suy Lagrange f(2) ≈ Ln(2) = -2/3
8. ❖ Cách biểu diễn khác : Để tính giá trị của Ln(x), ta lập bảng x x0 x1 xn x0 x- x0 x0- x1 x0- xn D0 tích x1 x1- x0 x- x1 x1- xn D1 dòng xn xn- x0 xn- x1 x- xn Dn ω(x) tích đường chéo
9. Ví dụ : Cho hàm f và bảng số x -9 -7 -4 y -1 -4 -9 Tính gần đúng f(-6) Ta lập bảng tại x = -6 x = -6 -9 -7 -4 -9 3 -2 -5 30 -7 2 1 -3 -6 -4 -30 5 3 -2 -6 Vậy f(-6) ≈ L2(-6) = -6(-1/30+4/6+9/30) = -5.6
10. Ví dụ : Cho hàm f và bảng số x 0 1 3 4 y 1 1 2 -1 Tính gần đúng f(2) Ta lập bảng tại x = 2 x = 2 0 1 3 4 0 2 -1 -3 -4 -24 1 1 1 -2 -3 6 3 6 3 2 -1 -1 4 -24 4 3 1 -2 4 Vậy f(2) ≈ Ln(2) = 4(-1/24 + 1/6 + 1/3 +1/24) = 2
11. ● TH đặc biệt : các điểm nút cách đều với bước h = xk+1 – xk Đặt
12. Ví dụ : Cho hàm f và bảng số x 1.1 1.2 1.3 1.4 y 15 18 19 24 Tính gần đúng f(1.25) giải Ta có n = 3 x = 1.25 h = 0.1 q = (1.25-1.1)/0.1 = 1.5 Vậy f(1.25) ≈ 18.375
13. ❖ Công thức đánh giá sai số : Giả sử hàm f(x) có đạo hàm đến cấp n+1 liên tục trên [a,b]. Đặt Ta có công thức sai số
14. Ví dụ : Cho hàm f(x)=2x trên đoạn [0,1]. Đánh giá sai số khi tính gần đúng giá trị hàm tại điểm x=0.45 sử dụng đa thức nội suy Lagrange khi chọn các điểm nút xo=0, x1=0.25, x2=0.5, x3=0.75, x4=1 Giải (5) 5 x Ta có n = 4, f (x) = (ln2) 2 (5) 5 ⇒ M5 = max |f (x)| = 2(ln2) công thức sai số
15. III. ĐA THỨC NỘI SUY NEWTON: 1. Tỉ sai phân : Cho hàm y = f(x) xác định trên [a,b]=[xo, xn] và bảng số x xo x1 x2 . . . xn y yo y1 y2 . . . yn Đại lượng gọi là tỉ sai phân cấp 1 của hàm f trên [xk,xk+1]
16. Tỉ sai phân cấp 2 Bằng qui nạp ta định nghĩa tỉ sai phân cấp p
17. Ví dụ : Cho hàm f và bảng số x 1.0 1.3 1.6 2.0 y 0.76 0.62 0.46 0.28 Tính các tỉ sai phân Giải : ta lập bảng các tỉ sai phân k xk f(xk) f[xk,xk+1] f[xk,xk+1,xk+2] f[xk,xk+1,xk+2,xk+3] 0 1.0 0.76 -0.4667 -0.111 0.23 1 1.3 0.62 -0.5333 0.119 2 1.6 0.46 -0.45 3 2.0 0.28
18. 2. Đa thức nội suy Newton : ❖ Công thức Newton tiến
19. ❖ Công thức Newton lùi
20. Để đánh giá sai số của đa thức nội suy Newton, ta dùng công thức sai số của đa thức nội suy Lagrange
21. Ví dụ : Cho hàm f xác định trên [0,1] và bảng số x 0 0.3 0.7 1 y 2 2.2599 2.5238 2.7183 Tính gần đúng f(0.12) bằng Newton tiến và f(0.9) bằng Newton lùi Giải : ta lập bảng các tỉ sai phân xk f(xk) f[xk,xk+1] f[xk,xk+1,xk+2] f[xk,xk+1,xk+2,xk+3] 0 2 0.8663 Newton tiến 0.3 2.2599 -0.2950 0.6598 0.2786 0.7 2.5238 -0.0164 0.6483 Newton lùi 1 2.7183
22. 3. TH các điểm nút cách đều : Sai phân hữu hạn cấp 1 của hàm tại điểm xk Δyk = yk+1 - yk Bằng qui nạp, Sai phân hữu hạn cấp p của hàm tại điểm xk p p-1 p-1 p-1 Δ yk = Δ(Δ yk) = Δ yk+1 - Δ yk Ta có công thức
23. Công thức Newton tiến Công thức Newton lùi
24. Ví dụ : Cho hàm f và bảng số x 30 35 40 45 y 0.5 0.5736 0.6428 0.7071 Tính gần đúng f(32) bằng Newton tiến và f(44) bằng Newton lùi Giải : ta lập bảng các sai phân hữu hạn 2 3 xk f(xk) Δyk Δ yk Δ yk 30 0.5 0.0736 Newton tiến 35 0.5736 -0.0044 0.0692 -0.0005 40 0.6428 -0.0049 0.0643 Newton lùi 45 0.7071
25. ▪ Tính gần đúng f(32) : dùng công thức Newton tiến n = 3, xo = 30, q=(32-30)/5 = 0.4 ▪ Tính gần đúng f(44) : dùng công thức Newton lùi n = 3, xn = 45, p=(44-45)/5 = -0.2
26. IV. SPLINE bậc 3 : Với n lớn, đa thức nội suy bậc rất lớn, khó xây dựng và khó ứng dụng. Một cách khắc phục là thay đa thức nội suy bậc n bằng các đa thức bậc thấp (≤ 3) trên từng đoạn [xk,xk+1], k=0,1, ,n-1
27. 1. Định nghĩa : Cho hàm y=f(x) xác định trên đoạn [a,b] và bảng số x a=xo x1 x2 . . . xn=b y yo y1 y2 . . . yn Một Spline bậc 3 nội suy hàm f(x) là hàm g(x) thỏa các điều kiện sau : (i) g(x) có đạo hàm đến cấp 2 liên tục trên [a,b] (ii) g(x)=gk(x) là 1 đa thức bậc 3 trên [xk,xk+1], k=0,1, ,n-1 (iii) g(xk) = yk, k=0,1, , n
28. 2. Cách xây dựng Spline bậc 3 : Đặt hk = xk+1 – xk gk(x) là đa thức bậc 3 nên có thể viết dưới dạng : 2 3 gk(x) = ak+bk(x-xk)+ck(x-xk) +dk(x-xk) Các hệ số ak, bk, dk được xác định theo các công thức :
29. Hệ số ck được tính theo công thức Phương trình (4) là hệ pt tuyến tính gồm n-1 pt dùng để xác định các hệ số ck. Phương trình (4) có số ẩn = n+1 > số pt = n-1 (thiếu 2 pt) nên chưa giải được, để giải được ta cần bổ sung thêm 1 số điều kiện
30. ❖ Định nghĩa : ▪ Spline tự nhiên là spline với điều kiện g”(a) = g”(b) = 0 ▪ Spline ràng buộc là spline với điều kiện g’(a) = α, g’(b) = β
31. 3. Spline tự nhiên : Giải thuật xác định spline tự nhiên : Điều kiện g”(a)=g”(b) = 0 suy ra co = cn = 0 B1. Tính hk=xk+1- xk, k = 0, n-1. ak= yk, k = 0, n t B2. Giải hệ Ac = b tìm c = (co, c1, , cn)
32. B3. Tính các hệ số bk, dk. Ví dụ : Xây dựng spline tự nhiên nội suy hàm theo bảng số x 0 2 5 y 1 1 4
33. Giải n = 2 B1. ho = 2, h1 = 3. ao = 1, a1 = 1, a2 = 4 t B2. Giải hệ Ac = b với c = (c0, c1, c2) ⇒ co = c2 = 0, c1 = 3/10
34. B3. Tính các hệ số bk, dk. Kết luận : spline tự nhiên
35. Ví dụ : Xây dựng spline tự nhiên nội suy hàm theo bảng số x 0 1 2 3 y 1 2 4 8 n = 3 B1. ho =h1= h2 = 1. ao = 1, a1 = 2, a2 = 4, a3 = 8 t B2. Giải hệ Ac = b với c = (c0, c1, c2,c3)
36. Giải ta được co = c3 = 0, c1 = 2/5, c2 = 7/5
37. B3. Tính các hệ số bk, dk. Kết luận : spline tự nhiên
38. 4. Spline ràng buộc : Điều kiện g’(a) = α, g’(b) = β xác định 2 pt : Giải thuật xác định spline ràng buộc : B1. Tính hk=xk+1- xk, k = 0, n-1. ak= yk, k = 0, n
39. t B2. Giải hệ Ac = b tìm c = (co, c1, , cn) B3. Tính các hệ số bk, dk. như spline tự nhiên
40. Ví dụ : Xây dựng spline ràng buộc nội suy hàm theo bảng số x 0 1 2 y 1 2 1 với điều kiện g’(0)=g’(2) = 0 Giải n = 2 B1. ho = h1 = 1. ao = 1, a1 = 2, a2 = 1
41. t B2. Giải hệ Ac = b với c = (c0, c1, c2)
42. B3. Tính các hệ số bk, dk. Kết luận : spline ràng buộc
43. V. BÀI TOÁN XẤP XỈ THỰC NGHIỆM : Trong thực tế, các giá trị yk được xác định thông qua thực nghiệm hay đo đạc nên thường thiếu chính xác. Khi đó việc xây dựng một đa thức nội suy đi qua tất cả các điểm Mk(xk, yk) cũng không còn chính xác
44. Bài toán xấp xỉ thực nghiệm : là tìm hàm f(x) xấp xỉ bảng {(xk,yk)} theo phương pháp bình phương cực tiểu : Hàm f tổng quát rất đa dạng. Để đơn giản, ta tìm hàm f theo dạng : f(x) = A1f1(x) + A2f2(x)+ Các hàm f1(x), f2(x) có thể là hàm lượng giác, lũy thừa, mũ hay loga
45. 1. Trường hợp f(x) = Af1(x)+ Bf2(x) : Phương trình bình phương cực tiểu có dạng Bài toán qui về tìm cực tiểu của hàm 2 biến g(A,B) Điểm dừng Suy ra
46. Ví dụ : Tìm hàm f(x) = A + Bx xấp xỉ bảng số x 1 1 2 2 2 3 3 4 5 6 y 1 2 2 3 4 4 5 5 6 7 Theo pp BPCT Giải hệ pt Nghiệm A = 0.7671, B=1.0803 Vậy f(x) = 0.7671+1.0803x
47. Ví dụ : Tìm hàm f(x)=Acosx+Bsinx xấp xỉ bảng số x 10 20 30 40 50 y 1.45 1.12 0.83 1.26 1.14 Theo pp BPCT Giải hệ pt Nghiệm A = -0.1633, B=0.0151 Vậy f(x) = -0.1633cosx+0.0151sinx
48. 2 Ví dụ : Tìm hàm f(x)=Ax +Bsinx xấp xỉ bảng số x 1.3 1.5 1.8 2.0 2.4 2.6 2.7 y 2.7 1.8 3.51 3.1 3.78 3.9 4.32 Theo pp BPCT Giải hệ pt Nghiệm A = 0.4867, B=1.4657 2 Vậy f(x) = 0.4867x + 1.4657sinx
49. 2. Trường hợp f(x) = Af1(x)+ Bf2(x)+Cf3(x): Phương trình bình phương cực tiểu có dạng Bài toán qui về tìm cực tiểu của hàm 3 biến g(A,B,C)
50. Điểm dừng Suy ra
51. 2 Ví dụ : Tìm hàm f(x) = A + Bx+Cx xấp xỉ bảng số x 1 1 2 3 3 4 5 y 4.12 4.18 6.23 8.34 8.38 12.13 18.32 Theo pp BPCT Ta có số điểm n= 7 Giải hệ pt Nghiệm A = 4.3, B=-0.71, C=0.69 2 Vậy f(x) = 4.3-0.71x+0.69x