Giáo trình Toán ứng dụng - Nguyễn Như Thành

tìm [a, b] thoả mãn các điều kiện sau: 1. f(a).f(b) < 0 (2.4) 2. f’(x) không đổi dấu trong (a, b) (2.5) 3. f’’(x) không đổi dấu trong (a, b) (2.6) Phương pháp dây cung Giả sử đã tìm được khoảng (a, b) thỏa ba điều kiện (2.4) (2.5) (2.6) đã nêu ở trên của phương trình f(x) = 0, nghĩa là f(a).f(b) < 0; và ∀x ∈ (a, b) thì f’(x), f’’(x) giữ nguyên một dấu. Nội dung của phương pháp dây cung là trong [a, b] ngưòi ta thay đường cong y = f(x) bởi dây cung của nó, nghĩa là xem nghiệm gần đúng của phương trình f(x) = 0 trùng với hoành độ giao điểm x1 của dây cung nối hai điểm A[a,f(a)], B[b, f(b)] với trục Ox . nghiệm đúng x0 nghiệm đúng A B x1 a=x0 x1 b a b f’’(x)>0 f(a)<0 f’’(x)<0 f(a)>0 A B Hình 4.1: Phương pháp dây cung Phương trình dây cung AB là phương trình đường thẳng qua hai điểm nên có dạng: = (2.7) trong đó x0 có thể lấy là a (hoặc b)thì d sẽ là b (hoặc a). Vì vậy cung cắt trục Ox tại điểm (x1, 0) trong phương trình 2.7 cho y = 0 và x = x1 ta được: d - x x1 = x0 - f(x0) (2.8) Để nhận được nghiệm chính xác hơn, ta lặp lại quá trình trên đối với khoảng (x1,d); ta thu được: x2 = x1 - f(x1) và ... Người ta đã chứng minh được rằng: Dãy x0, x1, x2, ... sẽ tiến dần đến nghiệm đúng của phương trình (2.1), nếu chọn x0 sao cho f’’(x) và f(x0) khác dấu, tức là f’’(x).f(x0) < 0, và khi đó d sẽ là f(x0).f(d) < 0. Ví dụ2.2: Tìm nghiệm gần đúng của phương trình : f(x) = x3 - x - 1 = 0, biết [1, 2] là khoảng phân li nghiệm, đã tìm ở trên. Giải: Ta có f’(x) = 3x2 -1 > 0∀x ∈ [1, 2] f’’(x) = 6x > 0 ∀x∈[1, 2] Ta chọn : x0 = 1 (vì f(1) < 0, tức là f’’(x).f(1) < 0) và d = 2. Theo công thức (2.8) ta có : x1 = 1 - (-1) 1.167 Ta áp dụng công thức (2.8) cho khoảng phân li nghiệm mới (1.167, 2), ta có : x2 = 1.167 - 1.253 Vậy nghiệm gần đúng của phương trình là 1.253 (muốn thu được nghiệm chính xác hơn ta có thể áp dụng công thức (2.8) một vài lần nữa) Phương pháp tiếp tuyến (newton) Giả sử đã tìm được khoảng (a, b) thỏa ba điều kiện (2.4) (2.5) (2.6) đã nêu ở trên của phương trình f(x) = 0, nghĩa là f(a).f(b) < 0; và x (a, b) thì f’(x), f’’(x) giữ nguyên một dấu. Nội dung của phương pháp tiếp tuyến là trong [a, b] người ta thay đường cong y = f(x) bởi tiếp tuyến của đường cong tại A hoặc B, tức xem nghiệm gần đúng của phương trình f(x) = 0 trùng với hoành độ giao điểm x1 giữa tiếp tuyến của đường cong tại A hoặc B với trục Ox (đối với loại đường nào thì lấy tiếp tuyến tại A hoặc B thì sẽ trình bày sau) f’’(x)>0 f(a)<0 nghiệm đúng B b=x0 a x1 A Hình 4.2: Phương pháp tiếp tuyến Giả sử chọn x0 = a thì tại A(x0, f(x0)), phương trình tiếp tuyến với đường cong y = f(x) tại điểm A sẽ là : y - f(x0) = f’(x0)(x - x0). Vì tiếp tuyến cắt với trục Ox tại điểm (x1, 0) nên toạ độ đó phải thỏa mãn phương trình tiếp tuyến : - f(x0) = f’(x0)(x - x0) Từ đó ta có : x1 = x0 - (2.9) Để nhận được nghiệm chính xác hơn, ta lặp lại quá trình trên đối với điểm (x1, f(x1)) ta thu được : x2 = x1 - và ... Người ta đã chứng minh được rằng : Dãy x0, x1, x2, ... sẽ tiến dần đến nghiệm đúng của phương trình (2.1), nếu chọn x0 sao cho f’’(x) và f(x0) cùng dấu, tức là f’’(x).f(x0) > 0. Ví dụ2.3: Tìm nghiệm gần đúng của phương trình : f(x) = x3 - x - 1 = 0, biết [1, 2] là khoảng phân li nghiệm, đã tìm ở trên. Giải: Ta có f’(x) = 3x2 -1 > 0 x [1, 2] f’’(x) = 6x > 0 x [1, 2] Ta chọn: x0 = 2 (vì f(2) > 0, tức là f’’(x).f(2) > 0). Theo công thức (2.9) ta có: x1 = 2 - 1.571 Ta áp dụng phương pháp tiếp tuyến một lần nữa, ta thay x0 bởi x1 : x2 = 1.571 - 1.367 Vậy nghiệm gần đúng của phương trình là 1.367 (muốn thu được nghiệm chính xác hơn ta có thể áp dụng công thức (2.9) một vài lần nữa) Phương pháp phối hợp Giả sử (a, b) là khoảng phân li nghiệm của phương trình f(x) = 0, nghĩa là: f(a).f(b) < 0; f’(x), f’’(x) x (a, b)giữ nguyên một dấu. Với điều kiện đó, nếu áp dụng đồng thời hai phương pháp : Dây cung cho nghiệm gần đúng x1, còn tiếp tuyến cho nghiệm gần đúng , thì x1 và sẽ nằm về hai phía của nghiệm. Vì vậy, khoảng phân li nghiệm sẽ được thu hẹp nhanh hơn. Lần nữa áp dụng đồng thời hai phương pháp cho đoạn [, x1] ta được [,x2]. Tiếp tục áp dụng quá trình trên cho đến khi hiệu số giữa hai nghiệm gần đúng bên trái và bên phải có trị tuyệt đối bé hơn sai số cho phép thì dừng và chọn nghiệm gần đúng là trung bình cộng của chúng. Cách tìm nghiệm như vậy gọi là phương pháp phối hợp của phương pháp dây cung và phương pháp tiếp tuyến. B f ’’(x)>0 f ’(x)>0 a1 a2 b a b2 b1 A Hình 4.3: Phương pháp phối hợp Ví dụ2.4: Tìm một nghiệm của phương trình : f(x) = xex - 2 = 0 với độ chính xác đến 0.01 bằng phương pháp phối hợp. Giải: Trước hết ta xác định khoảng phân li nghiệm . f(x) ) = xex - 2 xác định và liên tục x R f’(x) = ex + xex = ex(1 + x) = 0 x = - 1 f’’(x) = ex + ex + xex = ex(2 + x) Ta có bảng biến thiên : x - - 1 + f’(x) - 0 + f(x) m Ta có : f(0) = - 2 < 0 f(1) = e - 2 > 0 và f’(x) > 0 x (0, 1) f’’(x) > 0 x (0, 1) Vậy (0, 1) là khoảng phân li nghiệm.Do thỏa mãn 3 điều kiện (2.4) (2.5) (2.6) nên đồng thời áp dụng hai phương pháp dây cung và tiếp tuyến. Theo phương pháp dây cung : do f’’(x) > 0 nên chọn x0 sao cho f’’(x).f(x0) < 0 x0 = 0 và do đó d = 1. Theo công thức (2.8) x1 = x0 - f(x0) = 0 - (- 2) = 0.7358 Theo phương pháp tiếp tuyến : do f’’(x) > 0 nên chọn = 1 vì f(1) >0. Theo công thức (2.9) : = - = 1 - = + 0.8679 Vì - x1 = 0.8679 - 0.7358 = 0.1321 > 0.01 nên tiếp tục lần nữa hai phương pháp trên trong (0.7358 ; 0.8679). Theo phương pháp dây cung : x2 = x1 - f(x1) (với d1 = 0.8679) = 0.7358 - 0.8528. Theo phương pháp tiếp tuyến : = - = 0.8679 - 0.8534. Vì - x2 = 0.8534 - 0.8528 = 0.0006 < 0.01 Vậy có thể xem nghiệm gần đúng của phương trình là : x = (x2+ ) = (0.8534 + 0.8528) = 0.8531. Phương pháp chia đôi Giả sử phương trình f(x) = 0 (2.1) có nghiệm thực phân li trong [a, b] . Ta tìm cách thu nhỏ dần khoảng phân li nghiệm bằng cách chia đôi liên tiếp các khảng phân li nghiệm đa tìm ra. Trước hêt ta chia đôi khoảng [a, b], điểm chia là: c = (a + b)/2. Rõ ràng khoảng phân li nghiệm mới sẽ là [a, c] hay [c, b]. Ta tính f(c). Nếu f(c) = 0 thì c chính là nghiệm đúngcủa phương trình (thường thì f(c) 0). Nếu f(c) 0 ta so sánh dấu của f(c) với dấu của f(a) để suy ra khoảng phân li nghiệm thu nhỏ. Nếu f(c) trái dấu với f(a) thì khoảng phân li nghiệm thu nhỏ là [a, c] . Nếu f(c) cùng dấu với f(a) thì khoảng phân li nghiệm thu nhỏ là [c, b] . Như vậy sau khi chia đôi khoảng [a,b] ta được khoảng phân li nghiệm thu nhỏ là [a, c] hay [c, b], ký hiệu là [a1, b1] , nó nằm trong khoảng [a, b] và chỉ dài bằng nửa khoảng [a, b] túc là b1 - a1 = (b - a) Tiếp tục chia đôi khoảng [a1, b1] và làm như trên ta sẽ được khoảng phân li nghiệm thu nhỏ mới, ký hiệu là [a2, b2], nó nằm trong khoảng [a1, b1] tức là trong [a, b] và chỉ dài bằng nửa khoảng [a1, b1] : b2 - a2 = (b1 - a1) = (b - a) Lặp lại việc làm trên đến lần thứ n ta được khoảng phân li nghiệm thu nhỏ thứ n, ký hiệu là [an, bn] , nó nằm trong [a, b] và chỉ dài bằng 1/2n của [a, b] : an bn ; bn - an = Vậy có thể lấy an làm giá trị gần đúng của , lúc đó sai số là bn - an = (2.10) cũng có thể lấy bn làm giá trị gần đúng của , lúc đó sai số là bn - an = (2.11) Do đó với n đủ lớn, an, hay bn đều đủ gần . Khi n thì an, bn. Ví dụ 2.5: Tìm nghiệm gần đúng của phương trình : f(x) = x3 - x - 1 = 0, biết [1, 2] là khoảng phân li nghiệm, đã tìm ở trên Giải: Ta có : [1 , 2] và f(1) = 1 - 1 - 1 < 0 f(2) = 23 - 2 - 1 > 0 Ta chia đôi khoảng [1, 2] điểm chia là 3/2. f() = ()2 - - 1 > 0 trái dấu với f(1) . Vậy [1, 3/2]. Ta chia đôi khoảng [1, 3/2], điểm chia là 5/4. Ta có f(5/4) < 0 , cùng dấu với f(1). Vậy [5/4; 3/2]. Ta chia đôi khoảng [5/4; 3/2] , điểm chia là 11/8. Ta có f(11/8) > 0 , trái dấu với f(5/4). Vậy [5/4; 11/8]. Ta chia đôi khoảng [5/4; 11/8] , điểm chia là 21/16. Ta có f(21/16)< 0, cùng dấu với f(5/4). Vậy [21/16; 11/8]. Ta chia đôi khoảng [21/16; 11/8] , điểm chia là 43/32. Ta có f(43/32) > 0, trái dấu với f(21/16). Vậy [21/16; 43/32]. Ta dừng quá trình chia đôi tại đây và lấy 21/16 = 1.3125 hay 43/32 = 1.34375 làm giá trị gần đúng của thì sai số không vượt quá 1/25 = 1/32 = 0.03125. Phương pháp lặp Giả sử phương trình f(x) = 0 có nghiệm thực phân li trong [a, b]. Trước hết ta chuyển phương trình về dạng tương đương x = φ(x) (2.12) Sau đó ta chon một số x0 nào đó [a, b] làm xấp xỉ đầu rồi tính dần dãy số xntheo qui tắc xn = φ(xn - 1), n = 1, 2, ... (2.13) x0 cho trước [a, b] (2.14) Quá trình tính này được lặp đi lặp lại nên phương pháp này gọi là phương pháp lặp , hàm φ gọi là hàm lặp. Người ta chứng minh được rằng : Dãy x0, x1, x2, ... sẽ tiến dần đến nghiệm đúng của phương trình (2.1), nếu chọn hàm φ(x) sao cho trị tuỵệt đối của hàm φ’(x) nhỏ hơn q 0 ta có thể chọn x0 [a, b] một cách bất kì , còn nếu φ’(x) < 0 thì phải chọn theo qui tắc : (a + b) x0 = a khi a << x0 = b khi << b (2.15) Muốn biết thuộc nữa khoảng nào ta chỉ cần tính f() rồi so sánh dấu của nó với dấu của f(a). Và dừng quá trình tính khi< sai số cho phép. Giải hệ thống phương trình đại số tuyến tính Mục tiêu: Xác định được các phương pháp tìm nghiệm của hệ phươngtrình tuyến tính; Biết cách đánh giá sai số của phương pháp. Phát biểu bài toán Trong mục này, ta xét việc giải phương trình đại số tuyến tính n phương trình n ẩn : a11x1+a12x2++a1nxn=a1n+1a21x1+a22x2++a2nxn=a2n+1 an1x1+an2x2++annxn=ann+1 (3.1) trong đó aij (i,j=1,n) là những số đã biết, gọi là các hệ số của hệphương trình (3.1); ain+1 (i=1,n) cũng là các số đã biết, gọi là vế phải của hệ thống phương trình (3.1); xi (i=1,n) là các ẩn số phải tìm. Ký hiệu : A = a11a11a1na21a22a2nan1an2ann gọi là ma trận hệ số của hệ phương trình (3.1) b=a1n+1a2n+1 ann+1 và x=x1x2xn gọi là vectơ vế phải và vectơ ẩn số của hệ phương trình (3.1). Hệ phương trình có thể viết gọn dưới dạng : Ax = b (3.2) Nếu ma trận hệ số A không suy biến, nghĩa là : detA =a11a11a1na21a22a2nan1an2ann≠ 0 thì hệ phương trình (3.1) có nghiệm duy nhất. Thật vậy, vì detA ≠0 nên tồn tại ma trận nghịch đảo A-1. Nhân bên trái hai vế của (3.2) với A-1, nhận được : A-1Ax = A-1b x = A-1b (3.3) Như vậy, (3.3) cho ta nghiệm của hệ phương trình (3.1) và nghiệm ấy là duy nhất. Ta đã biết phương pháp Crame giải đúng hệphương trình (3.1) bằng công thức : Xi =∆i∆ , (i =1,n ) Trong đó :∆ = detA; ∆i là định thức cấp n thu được từ ∆bằng cách thay cột thứ i của ∆ bằng cột vế phải b của hệphương trình (3.1). Phương pháp Gauss Phương pháp Gaoxơ là một phương pháp được dùng phổ biến giải hệ phương trình (3.1) bằng cách khử dần các ẩn số, không phải tính một định thức nào. a. Nội dung phương pháp Để đơn giản việc trình bày, xét hệ 4 phương trình 4 ẩn số sau: a11(0)x1+a12(0)x2+a13(0)x3+a14(0)x4=a15(0)a21(0)x1+a22(0)x2+a23(0)x3+a24(0)x4=a25(0)a31(0)x1+a32(0)x2+a33(0)x3+a34(0)x4=a35(0)a41(0)x1+a42(0)x2+a43(0)x3+a44(0)x4=a45(0)(3.4) Nội dung cơ bản của phương pháp Gaoxơ là khử dần các ẩn số để đưa hệ (3.4) về hệ “tam giác” tương đương (ma trận hệ số của hệ là ma trận tam giác trên): x1+a12(1)x2+a13(1)x3+a14(1)x4=a15(1)x2+a23(2)x3+a24(2)x4=a25(2)x3+a34(3)x4=a35(3)x4=a45(4) (3.5) Sau đó giải hệtừ dưới lên trên. Quá trình đưa hệ (3.4) về hệ (3.5) gọi là quá trình thuận, quá trình giải hệ (3.5) gọi là quá trình ngược. i) Quá trình thuận: Khử x1. Giả sử a11(0)¹ 0 (a11(0) gọi là trụ thứ nhất). Chia phương trình đầu của hệ (3.4) cho a11(0), ta nhận được : x1 + a12(1) x2 + a13(1)x3 + a14(1)x4 = a15(1) (3.6) với a1j(1)/a11(0) ; j = 2, 3, 4,5 Dùng phương trình (3.6) khử x1 trong ba phương trình còn lại của hệ (3.6). Muốn thế, đem phương trình thứ hai của hệ (3.4) trừ phương trình (3.6) đã nhân với a21(0); đem phương trình thứ ba của hệ (3.4) trừ phương trình (3.6) đã nhân với a31(0); đem phương trình thứ tư của hệ (3.4) trừ phương trình (3.6) đã nhân với a41(0). Kết quả nhận được hệ ba phương trình sau : (3.7) Với aij(1) = aij(0) - ai1(1) a1j(1) ; i = 2, 3, 4; j = 2,3,4,5 Khử x2. Giả sử a22(1)¹ 0 (a22(1) gọi là trụ thứ hai). Chia phương trình đầu của hệ (4.30) cho a22(1) ta được : (3.8) Với Đem phương trình thứ hai của hệ (3.7) trừ phương trình (3.8) đã nhân với a32(1); đem phương trình thứ ba của hệ (3.7) trừ phương trình (3.8) đã nhân với a42(1). Kết quả nhận được hệ số hai phương trình sau : (3.9) Với Khử x3. Giả sử a33(2)¹ 0 (a33(2)) gọi là trụ thứ ba). Chia phương trình đầu của hệ (3.9) cho a33(2) và đem phương trình thứ hai của hệ (3.9) trừ phương trình vừa nhận được đã nhân với a43(2), ta được : (3.10) (3.11) Cuối cùng, nếu a44(3)¹ 0 (a44(3) gọi là trụ thứ tư), ta chia phương trình (3.11) cho a44(3), phương trình (3.11) có dạng : x4 = a45(4) (3.12) với a45(4) = a45(3)/a44(3) Rõ ràng là nếu các phần tử trụ a11(0), a22(1), a33(2) và a44(3) khác không thì hệ thống phương trình (3.4) tương đương với hệ thống phương trình “tam giác” sau : (3.13) ii) Quá trình ngược : Giải hệ thống (3.13) từ dưới lên ta có : x4 = a45(5) x3 = a35(3) - a34(3) x4 x2 = a25(2) - a23(2) - a24(2)x4 x1 = a15(1) - a12(1)x2- a13(1)x3 - a14(1)x4 Sơ đồ tính : Phân tích quá trình áp dụng phương pháp Gaoxơ ở mục 1 ta thấy : để đưa hệ thống (3.4) về hệ thống “tam giác” tương đương (3.13), chỉ cần tính các hệ số aij(1) aij(2).Kết quả tính, trong trường hợp không dùng máy tính điện tử, thường được ghi thành bảng, gọi là sơ đồ Gaoxơ, trong đó cột å dùng để kiểm tra quá trình tính. Sơ đồ Gaoxơ x1 x2 x3 x4 Số hạng tự do å Quá trình a11(0) a21(0) a31(0) a41(0) a12(0) a22(0) a32(0) a42(0) a13(0) a23(0) a33(0) a43(0) a14(0) a24(0) a34(0) a44(0) a15(0) a25(0) a35(0) a45(0) a16(0) a26(0) a36(0) a46(0) Quá trình thuận 1 a12(1) a13(1) a14(1) a15(1) a16(1) a22(1) a23(1) a24(1) a25(1) a26(1) a32(1) a33(1) a34(1) a35(1) a36(1) a42(1) a43(1) a44(1) a45(1) a46(1) 1 a23(2) a24(2) a25(2) a26(2) a33(2) a34(2) a35(2) a36(2) A43(2) A44(2) a45(2) a46(2) 1 a34(3) a35(3) a36(3) a44(3) a45(3) a46(3) 1 a45(4) a46(4) 1 1 1 1 x4 x3 x2 x1 Quá trình ngược Chú ý: Phương pháp Gaoxơ có thể được dùng để tính định thức vì khi đã chuyển định thức về dạng tam giác trên thì định mức sẽ bằng tích của các phần tử trên đường chéo chính. Ví dụ 3.1: Dùng phương pháp Gaoxơ giải hệ thống phương trình sau : (*) Giải : Kết quả tính toán được ghi trong bảng 1. Từ bảng 1, ta nhận được nghiệm của hệ thống (*) là : x1 = 1,00000; x2 = 2,00000 ; x3 = 3,00000; x4 = - 1,00000 Bảng 1: x1 x2 x3 x4 Số hạng tự do å Quá trình 2,0 0,4 0,3 1,0 1,0 0,5 -1,0 0,2 -0,1 4,0 1,0 2,5 1,0 -8,5 5,2 -1,0 2,7 21,9 -3,9 9,9 6,6 18,3 1,6 12,6 Quá trình thuận 1 0,50 -0,05 0,50 1,35 3,30 0,30 4,02 -8,70 21,36 16,98 -1,15 1,015 5,05 -4,305 0,610 -0,30 2,55 -1,50 8,55 9,30 1 13,40 -29,00 71,20 56,60 16,425 -28,300 77,575 65,700 6,570 -10,200 29,910 26,280 1 -1,72298 4,72298 4,00000 1,11998 -1,11998 0,00000 1 -1,00000 0,00000 1 1 1 1 -1,0000 3,0000 2,0000 1,0000 0,00000 4,00000 3,00000 2,00000 Quá trình ngược Nội suy và phương pháp bình phương cực tiểu Mục tiêu: Xác định được bài toán nội suy; Mô tả các phương pháp nội suy đa thức, biết cách tìm các đa thức nội suy theo cácphương pháp đó; Xác định và giải được các bài toán bằng phương pháp bình phương cực tiểu; Biết cách đánh giá sai số của các phương pháp. Đa thức nội suy Trong thực tế, nhiều khi gặp những hàm số y = f(x) mà không biết biểu thức giải tích cụ thể f của chúng, ta chỉ biết các giá trị yo, y1, ... yn của hàm số tại các điểm khác nhau xo, x1, ... xn của đoạn [a,b]. Các giá trị này có thể nhận được thông qua thí nghiệm, đo đạc,... Khi sử dụng những hàm số trên, ta cần biết các giá trị của chúng tại các điểm không trùng với xi (i = 0, 1, 2, ..., n). Muốn thế, ta tìm cách xây dựng một đa thức : Pn(x) = aoxn + a1xn-1 + ... + an-1x + an thoả mãn : Pn(xi) = f(xi) = yi, i = 0,1,2, ..., n (4.1) Pn(x) gọi là đa thức nội suy của hàm f(x), các điểm xi, i = gọi là các nút nội suy. Về hình học, có nghĩa là tìm đường cong : Y = Pn(x) = aoxn + a1xn-1 + ... + an-1x + an y Đi qua các điểm Mi(xi, yi) đã biết (i = ) của đường cong y = f(x). y=f(x) Mn-1 M0 M1 Mi 0 Mn y=Pn(x) Xn Xn-1 Xi X1 X0 x Hình 4.4: Đường cong y=f(x) và y=Pn(x) Sau đó, ta dùng đa thức Pn(x) thay cho hàm số f(x) để tính gần đúng giá trị của hàm số f(x) tại các điểm x ¹ xi (i = ). Nếu điểm x Î (xo, xn) thì phép tính trên gọi là phiép tính nội suy. Nếu điểm x Ï (xo, xn) (x ở ngoài (xo, xn)) thì phép tính trên gọi là phép tính ngoại suy. Sở dĩ ta chọn đa thức Pn(x) vì trong tính toán, đa thức là hàm số dễ tính nhất. Nhằm giảm bớt khối lượng tính, người ta cũng dùng đa thức nội suy Pn(x) thay cho hàm số f(x) để tính gần đúng giá trị của hàm số f(x) tại các điểm x ¹ xi(i = ) trong trường hợp biểu thức giải tích cụ thể của hàm số f(x) đã biết nhưng tương đối phức tạp, nhất là khi phải tính nhiều giá trị. Về sự duy nhất của đa thức nội suy, ta có định lý sau : Định lý 4.1: Đa thức nội suy Pn(x) của hàm số f(x), nếu có, thì chỉ có một mà thôi. Chứng minh : Giả sử những điều kiện (4.1), ta xây dựng được hai đa thức nội suy khác nhau Pn(x) và Qn(x) với : Pn(xi) = yi; Qn(xi) = yi (i = ) Khi đó Pn(x) - Qn(x) là một đa thức bậc không lớn hơn n, nhưng lại triệt tiêu tại n + 1 điểm xi khác nhau vì : Pn (xi) - Qn(xi) = yi - yi = 0(i = ) Vậy : Pn(x) - Qn(x) = 0 (nghĩa là Pn(x) - Qn(x) bằng không với mọi x), hay : Pn(x) = Qn(x). Đó là điều phải chứng minh. Tính giá trị của đa thức : sơ đồ Hoócne Cho đa thức bậc n : Pn(x) = aoxn + a1xn-1 + ... + an-1x + an Với hệ số thực ak (k = 0, 1, 2, ..., n), cần tính giá trị của đa thức tại x = c : Ph(c) = aocn + a1cn-1 + ... + an-1c + an (4.2) Cách tính Pn(c) tiết kiệm nhất về số phép tính như sau : ta viết (4.2) dưới dạng : Pn(c) = (...((((aoc + a1)c + a2)c + a3)c + ... + an -1)c + an) Vậy để tính Pn(c), chỉ cần tính lần lượt các số : bo = ao b1 = a1 + boc b2 = a2 + b1c b3 = a3 + b2c ... bn = an + bn - 1c = Pn(c) Để tiện tính toán, người ta thường dùng sơ đồ sau, gọi là sơ đồ Hoócne : ao a1 a2 ... an C + boc b1c ... bn-1c bo b1 B2 ... bn = Pn(c) Ví dụ : Dùng sơ đồ Hoócne, tính giá trị của : P3(x) = 3x3 + 2x2 - 5x + 7 Tại x = 3 Giải : Ta có : 3 2 -5 7 3 + 9 33 84 3 11 28 91= P3(3) Đa thức nội suy Lagrăng Thành lập đa thức nội suy Lagrăng Giả sử trên [a,b] cho n +1 giá trị khác nhau của đối số : xo, x1, ..., xn và biết, đối với hàm số y = f(x), những giá trị tương ứng : Bây giờ ta xây dựng đa thức nội suy Ln(x), bậc không cao hơn n, thoả mãn điều kiện : Theo cách của Lagrăng Trước hết, xây dựng đa thức li(x) thoả mãn điều kiện : (*) Vì đa thức li(x) phải tìm triệt tại n điểm xo, x1, ..., xi-1, xi+1, ... , xn nên li(x) có thể viết dưới dạng : li(x) = Ci(x - x0) (x - x1) .. (x - xi-1)(x - xi+1) ... (x - xi+1) ... (x - xn) (4.3) trong đó Ci là hằng số phải tìm. Đặt x = xi trong (4.3) và để ý điều kiện (4.3), ta có : li(xi) = Ci(xi - x0) (xi - x1) .. (xi - xi-1)(xi - xi-1) ... (xi - xi+1) ... (xi - xn) Trong đó : Thay vào (6.32), ta có : (4.4) Đa thức li(x) bậc n được gọi là đa thức Lagrăng cơ bản. Bây giờ, ta xét đa thức sau : (4.5) Dễ thấy rằng bậc của đa thức Ln(x) không cao hơn n và do điều kiện (*), có : (4.6) Vậy đa thức Ln(x), xác định bởi (4.44) là đa thức nội suy phải tìm. Thay biểu thức của li(x) từ (4.44) vào (4.45), nhận được : (4.7) Đây là đa thức nội suy Lagrăng. Sau đây là sẽ xét hai trường hợp hay sử dụng của đa thức nội suy Lagrăng. i) Nội suy bậc nhất hay nội suy tuyến tính : Khi n = 1, ta có hai nút nội suy xo và x1, và : (4.8) Phương trình y = L1(x) chính là phương trình đường thắng đi qua hai điểm Mo(xo, yo) và M1(x1 , y1). ii) Nội suy bậc hai : Khi n = 2, ta có nút nội suy xo, x1, x2 và : (4.9) Phương trình y = L2(x) chính là phương trình đường parabol đi qua ba điểm Mo(xo,yo), M1(x1, y1) và M2(x2, y2). Ví dụ 4.1: Hãy xây dựng đa thức nội suy Lagrăng của hàm số y = sinpx, chọn các nút nội suy là : xo = 0, x1 = và x2 = . Giải: Ta có : yo = sin0 = 0; y1 = sin. Áp dụng công thức (4.9), nhận được : Ví dụ 4.2 : Cho bảng giá trị hàm số y = log10x X 300 304 305 307 Y 2,4771 2,4829 2,4843 2,4871 Tính gần đúng log10301 bằng đa thức nội suy Lagrăng. Giải : Dùng (6.35) với n = 3, ta có : + = 1,2739 + 4,9 658 - 4,4717 + 0,7106 = 2,4786 Đánh giá sai số : Để đánh giá độ lệch giữa đa thức nội suy Lagrăng Ln(x) và hàm số f(x) tại các điểm x ¹ xi (i = ) ta xét định lý sau : Định lý 2 : Nếu hàm số y = f(x) liên tục trên [a,b] và có đạo hàm liên tục đến cấp n + 1 trong (a,b) thì sai số nội suy Rn(x) = f(x) - Ln(x) có dạng sau : (4.10) Trong đó c phụ thuộc x và Î [a,b], pn+1(x) = (x - xo)(x - x1) ... (x - xn) Chứng minh : Xét hàm số phụ sau : u(x) = f(x) - Ln(x) - kpn+1(x) (4.11) Trong đó k là hằng số sẽ lựa chọn sau. Hàm số u(x) có n+1 nghiệm tại các điểm xo, x1, ... , xn. Bây giờ ta chọn k sao cho hàm số u(x) có nghiệm thứ n + 2 tại một điểm bất kỳ nhưng cố định của [a,b], không trùng với các nút nội suy. Muốn thế, chỉ cần cho : f() - Ln() - kpn+1() = 0 Vì kpn+1() ¹ 0 nên : Với giá trị k vừa chọn, hàm số u(x) bằng 0 tại n + 2 điểm : xo, x1, x2, ..., xn, trên [a,b]. Ap dụng định lý Rôn, thấy rằng đạo hàm u’(x) có không ít hơn n+1 nghiệm trên [a,b]. Lại áp dụng định lý Rôn vào đạo hàm u’(x), thấy rằng đạo hàm cấp hai u’’(x) có không ít hơn nghiệm trên [a,b]. Tiếp tục lập luận như trên, thấy rằng trên [a,b] đạo hàm u(n+1)(x) có ít nhất một nghiệm c, nghĩa là : u(n+1)(c) = 0 Vì Nên theo (4.11) có : ! Tại x = c, nhận được : hay (4.12) Từ (6.40) và (6.41) suy ra : và : (4.13) Vì là một điểm bấ kỳ của [a, b] không trùng với các nút nội suy, nên có thể viết lại (4.13) dưới dạng : (4.14) trong đó : c phụ thuộc x và nằm trên [a,b]. Đó là công thức xác định số hạng dư của đa thức nộ suy Ln(x). Chú ý rằng (4.14) đúng với mọi điểm của [a,b], kể cả những điểm nút nội suy. Đặt Mn+1= , nhận được đánh giá sau đối với sai số tuyệt đối của đa thức nội suy Lagrăng : (4.15) Ví dụ 4.3 : Cho bảng giá trị của hàm số y = sinx như sau : X 0 Y 0 0,707 1 Tính gần đúng sin bằng đa thức nội suy Lagrăng và đánh giá sai số của giá trị gần đúng nhận được. Giải : Dùng (4.9), ta có : Để đánh giá sai số của giá trị gần đúng nhận được, ta dùng (4.15) Vì , nên : và . Đa thức nội suy Newton Bây giờ ta xét một cách khác để xây dựng đa thức nội suy: cách của Niutơn. Trước hết ta đưa vào khái niệm tỉ hiệu. Giả sử hàm y = y(x) có bảng giá trị là bằng 4-1 ở mục 1. Tỉ hiệu cấp một của y tại xi, xjlà : Tỉ hiệu cấp hai của y tại xi, xj, xklà : ... Với y(x) = P(x) là một đa thức bậc 2 thỉ tỉ hiệu cấp một tại x, là : Là một đa thức bậc n -1, tỉ hiệu cấp hai tại x, xo, x1 là Là một đa thức bậc n -2, ... tỉ hiệu cấp n + 1 Từ định nghĩa của các tỉ hiệu ta suy ra : Pn(x) = Pn(xo) + (x - xo) Pn (x, xo) Pn[x, xo] = Pn[xo, x1] + (x - x1) Pn(x, xo, x1) Pn[x, xo, x1] = Pn[xo, x1, x2] + (x - x2)Pn [x, xo, x1, x2] . . . . . . Pn[x, xo, ..., xn-1] = Pn[xo, ..., xn] + (x - xn)Pn[x, xo, ..., xn] Từ đó và vì Pn[x, xo, ..., xn] = 0 ta có : Pn(x) = Pn(xo) + (x - xo) Pn(xo, x1) + (x - xo) (x - x1) Pn(xo, x1, x2) + ... + (x - xo) ... (x - xn-1)Pn[xo, ..., xn] (4.16) Nếu Pn(x) = pn(x) là đa thức nội suy của hàm y = f(x) thì : Pn(xi) = pn(xi) = f(xi) = yi, i = 0, 1, ... n Do đó các tỉ hiệu từ cấp một đến cấp n của Pn và của y ở (4.16) là trùng nhau. Vì vậy thay cho (4.16) ta có : pn(x) = yo + (x - xo) y [xo, x1] + (x - xo)(x - x1) y [xo, x1, x2] + ... + (x - xo) (x - x1) ... (x - xn-1) y [xo ..., xn] (4.17) Đa thức này goi là đa thức Niutơn tiến xuất phát từ nút xo của hàm y = f(x) Đa thức sau đây là đa thức Niutơn lùi xuất phát từ nút xn của hàm y = f(x) Pn(x) = yn + (x - xn) y [xn, xn-1] + (x - xn) (x - xn-1) y[xn, xn-1, xn-2] + ... + (x - xn) (x - xn-1) ... (x - x1) y [xn, ... xo] (4.18) Chú ý rằng, theo định nghĩa, các tỉ hiệu có tính đối xứng : y[xi, xj] = y[xj, xi] y[xi, xj, xk] = y[xk, xj, xi] ... Chú thích : Đa thức Niutơn (4.17) trùng với đa thức Lagrangiơ nhưng bố trí cách thức khác. Theo cách của Niutơn khi thêm một nút xn+1 vào lưới nội suy ta chỉ phải thêm vào pn(x) một số hạng. pn+1(x) = pn(x) + (x - xo) ... (x - xn) (x - xn+1), y [xo,..., xn, xn+1] mà không phải xây dựng lại tất cả các đa thức cơ sở như cách làm của Lagrange. Trường hợp của nút cách đều Giả sử các nút xj cách đều : xi = xo + ih, i = 0, 1, ..., n i) Trước hết ta đưa vào khái niệm sai phân tiến Sai phân tiến cấp một tại i : Dyi = yi+1 - yi Sai phân tiến cấp hai tại i : D2yi = D(Dyi) = yi+2 - 2yi+1 + yi Sai phân tiến cấp n tại i là : Dnyi = D(Dn-1yi) Khi đó ta có : Bây giờ đặt x = xo + ht trong đa thức Niutơn tiến ta đ