Chương 4: Nội suy và xấp xỉ hàm

Chương 4 NỘI SUY VÀ XẤP XỈ HÀMI. ĐẶ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àmXé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).II. ĐA THỨC NỘY SUY LAGRANGE: Cho hàm y = f(x) và bảng sốx xo x1 x2 . . . xn y yo y1 y2 . . . ynTa xây dựng đa thức nội suy hàm f(x) trên [a,b]=[x0, xn]. ĐặtTa có Đa thức có bậc ≤ n và thỏa điều kiện Ln(xk) = ykgọi là đa thức nội suy Lagrange của hàm fVí 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).n = 2GiảiĐa thức nội suy Lagrangef(2)  Ln(2) = -2/3 Cách biểu diễn khác : ’(xk) = (xk-x0)(xk-x1)...(xk-xk-1)(xk-xk+1)...(xk- xn)Đặt (x) = (x- x0)(x- x1) .... (x- xn)với Dk = ’(xk) (x-xk)Để tính giá trị của Ln(x), ta lập bảngx x0 x1 .... xnx0x1xnx- x0 x0- x1 .... x0- xnx1- x0 x- x1 .... x1- xn .... .... .... ....xn- x0 xn- x1 .... x- xn D0D1Dn(x)tích dòngtích đường chéoVí 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 = -6x = -6 -9 -7 -4 -9-7-4 3 -2 -5 2 1 -3 5 3 -2 30 -6 -30 -6Vậy f(-6)  L2(-6) = -6(-1/30+4/6+9/30) = -5.6Ví dụ : Cho hàm f và bảng sốx 0 1 3 4y 1 1 2 -1Tính gần đúng f(2)Ta lập bảng tại x = 2x = 2 0 1 3 40134 2 -1 -3 -4 1 1 -2 -3 3 2 -1 -1 4 3 1 -2-24 6 6-24 4 Vậy f(2)  L3(2) = 4(-1/24 + 1/6 + 1/3 +1/24) = 2 TH đặc biệt : các điểm nút cách đều với bước h = xk+1 – xkĐặtTa có xk = xo + kh x-xk = x- xo-kh = (q-k)h xi-xj = (xo+ih)-(xo+jh) = (i-j)h (x)=(x-x0)(x-x1) .... (x-xn)=q(q-1)(q-n)hn+1 ’(xk) = (xk-x0) ... (xk-xk-1)(xk-xk+1)  (xk-xn) = k.(k-1)  1.(-1)(-2)  (k-n)hn = (-1)n-k k! (n-k)! hnVí dụ : Cho hàm f và bảng sốx 1.1 1.2 1.3 1.4y 15 18 19 24Tính gần đúng f(1.25)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.375giải 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].ĐặtTa có công thức sai số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=1Giải Ta có n = 4, f(5)(x) = (ln2)52x M5 = max |f(5)(x)| = 2(ln2)5công thức sai sốIII. ĐA THỨC NỘY 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ượnggọi là tỉ sai phân cấp 1 của hàm f trên [xk,xk+1]Tỉ sai phân cấp 2Bằng qui nạp ta định nghĩa tỉ sai phân cấp pVí dụ : Cho hàm f và bảng sốx 1.0 1.3 1.6 2.0y 0.76 0.62 0.46 0.28Tính các tỉ sai phân kxkf(xk)f[xk,xk+1]f[xk,xk+1,xk+2]f[xk,xk+1,xk+2,xk+3]01231.01.31.62.00.760.620.460.28-0.4667-0.5333-0.45-0.1110.1190.23Giải : ta lập bảng các tỉ sai phân 2. Đa thức nội suy Newton : Tỉ sai phân cấp 1Tỉ sai phân cấp 2nênTiếp tục bằng qui nạp ta đượcĐặtTa đượcCông thức này gọi là công thức Newton tiến xuất phát từ điểm nút xoTương tự ta có công thức Newton lùiNếu hàm f có đạo hàm liên tục đến cấp n+1, ta có công thức đánh giá sai số : 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.7183Tính gần đúng f(0.12) bằng Newton tiến và f(0.9) bằng Newton lùixkf(xk)f[xk,xk+1]f[xk,xk+1,xk+2]f[xk,xk+1,xk+2,xk+3]00.30.7122.25992.52382.71830.86630.65980.6483-0.2950-0.01640.2786Giải : ta lập bảng các tỉ sai phân Newton lùiNewton tiếnTa có 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 - ykBằng qui nạp, Sai phân hữu hạn cấp p của hàm tại điểm xk 	pyk = (p-1yk) = p-1yk+1 - p-1ykTa có công thức Công thức Newton tiếnCông thức Newton lùiVí dụ : Cho hàm f xác định và bảng sốx 30 35 40 45 y 0.5 0.5736 0.6428 0.7071Tính gần đúng f(32) và f(44)xkf(xk)yk2yk3yk303540450.50.57360.64280.70710.07360.06920.0643-0.0044-0.0049-0.0005Giải : ta lập bảng các sai phân hữu hạn Newton lùiNewton tiến 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.2IV. 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-11. Đị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 . . . ynMộ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 : g(x) có đạo hàm đến cấp 2 liên tục trên [a,b] g(x)=gk(x) là 1 đa thức bậc 3 trên [xk,xk+1], k=0,1,..,n-1 g(xk) = yk, k=0,1, , n2. Cách xây dựng Spline bậc 3 : Đặt hk = xk+1 – xkgk(x) là đa thức bậc 3 nên có dạng : 	gk(x) = ak+bk(x-xk)+ck(x-xk)2+dk(x-xk)3 Ta có g(xk) = yk 	ak = yk, k = 0,1,, n g(x) khá vi liên tục đến cấp 2 nên Điều kiện (A) suy ra Điều kiện (C) suy raTa có 	gk’(x) = bk+2ck(x-xk)+3dk(x-xk)2	gk”(x) = 2ck+6dk(x-xk) Thay (2) vào (1) ta đước Điều kiện (B) suy ra Thay (2) và (3) vào (4) ta đượcPhương trình (5) là hệ pttt gồm n-1 pt, dùng để xác định các hệ số ck. Từ ck và (2) (3) ta xác định được tất cả các hệ số của đa thức gk(x)Phương trình (5) có vô số nghiệm, để có nghiệm duy nhất ta cần bổ sung thêm 1 số điều kiện Đị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) = 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 = 0B1. Tính hk=xk+1- xk, k = 0, n-1. ak= yk, k = 0, nB2. Giải hệ Ac = b tìm c = (co, c1, , cn)tB3. 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 GiảiB1. ho = 2, h1 = 3. ao = 1, a1 = 1, a2 = 4B2. Giải hệ Ac = b với c = (c0, c1, c2)tn = 2 co = c2 = 0, c1 = 3/10B3. Tính các hệ số bk, dk.Kết luận : spline tự nhiênVí dụ : Xây dựng spline tự nhiên nội suy hàm theo bảng sốx 0 1 2 3y 1 2 4 8B1. ho = h1= h2 = 1. ao = 1, a1 = 2, a2 = 4, a3 = 8n = 3B2. Giải hệ Ac = b với c = (c0, c1, c2,c3)tGiải ta được co = c3 = 0, c1 = 2/5, c2 = 7/5B3. Tính các hệ số bk, dk.Kết luận : spline tự nhiên4. Spline ràng buộc : 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Điều kiện g’(a) = , g’(b) =  xác định 2 pt : B2. Giải hệ Ac = b tìm c = (co, c1, , cn)tB3. Tính các hệ số bk, dk.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 1với điều kiện g’(0)=g’(2) = 0GiảiB1. ho = h1 = 1. ao = 1, a1 = 2, a2 = 1n = 2B2. Giải hệ Ac = b với c = (c0, c1, c2)tB3. Tính các hệ số bk, dk.Kết luận : spline ràng buộcV. BÀI TOÁN XẤP XỈ THỰC NGHIỆM : Xét bài toán thống kê lượng mưa trong 12 thángThực nghiệm (k=1..12)xk1 2 3 4 5 6 7 8yk550 650 540 580 610 605 ......Các giá trị yk được xác định bằng thực nghiệm nên có thể không chính xác. Khi đó việc xây dựng một đường cong đi qua tất cả các điểm Mk(xk, yk) cũng không còn chính xácBà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, trong thực tế thường ta tìm hàm f theo một trong các dạng sau : f(x) = A + Bx f(x) = A+Bx+Cx2- f(x) = Asinx+Bcosx f(x) = AeBx f(x) = AxB- f(x) = AlnBx 1. Trường hợp f(x) = A+ Bx : Phương trình bình phương cực tiểu có dạngBài toán qui về tìm cực tiểu của hàm 2 biến g(A,B)Điểm dừngSuy raSuy raVí dụ : Tìm hàm f(x) = A + Bx xấp xỉ bảng sốx1 1 2 2 2 3 3 4 5 6y1 2 2 3 4 4 5 5 6 7Theo pp BPCTTa có n = 10Giải hệ ptNghiệm A = 0.7671, B=1.0803Vậy f(x) = 0.7671+1.0803x2. Trường hợp f(x) = Acosx + Bsinx : Phương trình bình phương cực tiểu có dạngBài toán qui về tìm cực tiểu của hàm 2 biến g(A,B)Điểm dừngSuy raSuy raVí 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.14Theo pp BPCTTa có n = 5Giải hệ ptNghiệm A = -0.1633, B=0.0151Vậy f(x) = -0.1633cosx+0.0151sinxrad3. Trường hợp f(x) = Ax2 + Bsinx : Phương trình bình phương cực tiểu có dạngBài toán qui về tìm cực tiểu của hàm 2 biến g(A,B)Điểm dừngSuy raSuy raVí dụ : Tìm hàm f(x)=Ax2+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 BPCTTa có n =7Giải hệ ptNghiệm A = 0.4867, B=1.4657Vậy f(x) = 0.4857x2 + 1.4657sinx4. Trường hợp f(x) = A+ Bx+Cx2: Phương trình bình phương cực tiểu có dạngBài toán qui về tìm cực tiểu của hàm 3 biến g(A,B,C)Điểm dừngSuy raSuy raVí dụ : Tìm hàm f(x) = A + Bx+Cx2 xấp xỉ bảng sốx 1 1 2 3 3 4 5 y4.12 4.18 6.23 8.34 8.38 12.13 18.32 Theo pp BPCTTa có n = 7Giải hệ ptNghiệm A = 4.3, B=-0.71, C=0.69Vậy f(x) = 4.3-0.71x+0.69x2