›
›

Bài giảng môn Phương pháp tính - Đỗ Thị Tuyết Hoa

pdf 68 trang hapham 1920
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng môn Phương pháp tính - Đỗ Thị Tuyết Hoa", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_mon_phuong_phap_tinh_do_thi_tuyet_hoa.pdf

Nội dung text: Bài giảng môn Phương pháp tính - Đỗ Thị Tuyết Hoa

  1. ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN ^ [ ] \ ” \ ] [ ^ Biên soạn: GV.Đỗ Thị Tuyết Hoa BÀI GIẢNG MÔN PHƯƠNG PHÁP TÍNH (Dành cho sinh viên khoa Công nghệ thông tin) ( TÀI LIỆU LƯU HÀNH NỘI BỘ ) ĐÀ NẴNG, NĂM 2007
  2. MỤC LỤC CHƯƠNG I NHẬP MÔN 5 1.1. Giới thiệu môn phương pháp tính 5 1.2. Nhiệm vụ môn học 5 1.3. Trình tự giải bài toán trong phương pháp tính 5 CHƯƠNG II SAI SỐ 7 2.1. Khái niệm 7 2.2. Các loại sai số 7 2.3. Sai số tính toán 7 CHƯƠNG III TÍNH GIÁ TRỊ HÀM 9 3.1. Tính giá trị đa thức. Sơ đồ Hoocner 9 3.1.1. Đặt vấn đề 9 3.1.2. Phương pháp 9 3.1.3. Thuật toán 9 3.1.4. Chương trình 10 3.2. Sơ đồ Hoocner tổng quát 10 3.2.1. Đặt vấn đề 10 3.2.2. Phương pháp 10 3.2.3. Thuật toán 12 3.3. Khai triển hàm qua chuỗi Taylo 12 CHƯƠNG IV GIẢI GẦN ĐÚNG PHƯƠNG TRÌNH 14 4.1. Giới thiệu 14 4.2. Tách nghiệm 14 3.3. Tách nghiệm cho phương trình đại số 16 4.4. Chính xác hoá nghiệm 17 4.4.1. Phương pháp chia đôi 17 4.4.2. Phương pháp lặp 19 4.4.3. Phương pháp tiếp tuyến 21 4.4.4. Phương pháp dây cung 22 2
  3. CHƯƠNG V GIẢI HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH 26 5.1. Giới thiệu 26 5.2. Phương pháp Krame 26 5.3. Phương pháp Gauss 27 5.3.1. Nội dung phương pháp 27 5.3.2. Thuật toán 27 5.4. Phương pháp lặp Gauss - Siedel (tự sửa sai) 28 5.4.1. Nội dung phương pháp 28 5.4.2. Thuật toán 30 5.5. Phương pháp giảm dư 31 5.5.1. Nội dung phương pháp 31 5.5.2. Thuật toán 32 CHƯƠNG VI TÌM GIÁ TRỊ RIÊNG - VECTƠ RIÊNG 34 6.1. Giới thiệu 34 6.2. Ma trận đồng đạng 34 6.3. Tìm giá trị riêng bằng phương pháp Đanhilepski 35 6.3.1. Nội dung phương pháp 35 6.3.2. Thuật toán 37 6.4. Tìm vectơ riêng bằng phương pháp Đanhilepski 38 6.4.1. Xây dựng công thức 38 6.4.2. Thuật toán 39 CHƯƠNG VII NỘI SUY VÀ PHƯƠNG PHÁP BÌNH PHƯƠNG BÉ NHẤT 41 7.1. Giới thiệu 41 7.2. Đa thức nội suy Lagrange 42 7.3. Đa thức nội suy Lagrange với các mối cách đều 43 7.4. Bảng nội suy Ayken 44 7.4.1. Xây dựng bảng nội suy Ayken 45 7.4.2. Thuật toán 46 7.5. Bảng Nội suy Ayken (dạng 2) 46 7.6. Nội suy Newton 48 7.6.1. Sai phân 48 3
  4. 7.6.2. Công thức nội suy Newton 49 7.7. Nội suy tổng quát (Nội suy Hecmit) 51 7.8. Phương pháp bình phương bé nhất 53 CHƯƠNG VIII TÍNH GẦN ĐÚNG TÍCH PHÂN XÁC ĐỊNH 57 8.1. Giới thiệu 57 8.2. Công thức hình thang 57 8.3. Công thức Parabol 58 8.4. Công thức Newton-Cotet 59 MỘT SỐ CHƯƠNG TRÌNH THAM KHẢO 62 TÀI LI ỆU THAM KHẢO 68 4
  5. CHƯƠNG I NHẬP MÔN 1.1. Giới thiệu môn phương pháp tính Phương pháp tính là bộ môn toán học có nhiệm vụ giải đến kết quả bằng số cho các bài toán, nó cung cấp các phương pháp giải cho những bài toán trong thực tế mà không có lời giải chính xác. Môn học này là cầu nối giữa toán học lý thuyết và các ứng dụng của nó trong thực tế. Trong thời đại tin học hiện nay thì việc áp dụng các phương pháp tính càng trở nên phổ biến nhằm tăng tốc độ tính toán. 1.2. Nhiệm vụ môn học - Tìm ra các phương pháp giải cho các bài toán gồm: phương pháp (PP) đúng và phương pháp gần đúng. + Phương pháp: chỉ ra kết quả dưới dạng một biểu thức giải tích cụ thể. + Phương pháp gần đúng: thường cho kết quả sau một quá trình tính lặp theo một quy luật nào đó, nó được áp dụng trong trường hợp bài toán không có lời giải đúng hoặc nếu có thì quá phức tạp. - Xác định tính chất nghiệm - Giải các bài toán về cực trị - Xấp xỉ hàm: khi khảo sát, tính toán trên một hàm f(x) khá phức tạp, ta có thể thay hàm f(x) bởi hàm g(x) đơn giản hơn sao cho g(x) ≅ f(x). Việc lựa chọn g(x) được gọi là phép xấp xỉ hàm - Đánh giá sai số : khi giải bài toán bằng phương pháp gần đúng thì sai số xuất hiện do sự sai lệch giữa giá trị nhận được với nghiệm thực của bài toán. Vì vậy ta phải đánh giá sai số để từ đó chọn ra được phương pháp tối ưu nhất 1.3. Trình tự giải bài toán trong phương pháp tính - Khảo sát, phân tích bài toán - Lựa chọn phương pháp dựa vào các tiêu chí sau: + Khối lượng tính toán ít + Đơn giản khi xây dựng thuật toán + Sai số bé 5
  6. + Khả thi - Xây dựng thuật toán: sử dụng ngôn ngữ giả hoặc sơ đồ khối (càng mịn càng tốt) - Viết chương trình: sử dụng ngôn ngữ lập trình (C, C++, Pascal, Matlab, ) - Thực hiện chương trình, thử nghiệm, sửa đổi và hoàn chỉnh. 6
  7. CHƯƠNG II SAI SỐ 2.1. Khái niệm Giả sử x là số gần đúng của x* (x* : số đúng), Khi đó ∆ = x − x ∗ gọi là sai số thực sự của x Vì không xác định được ∆ nên ta xét đến 2 loại sai số sau: - Sai số tuyệt đối: Giả sử ∃ ∆ x > 0 du be sao cho x − x * ≤ ∆ x Khi đó ∆ x gọi là sai số tuyệt đối của x ∆ x - Sai số tương đối : δ x = x 2.2. Các loại sai số Dựa vào nguyên nhân gây sai số, ta có các loại sau: - Sai số giả thiết: xuất hiện do việc giả thiết bài toán đạt được một số điều kiện lý tưởng nhằm làm giảm độ phức tạp của bài toán. - Sai số do số liệu ban đầu: xuất hiện do việc đo đạc và cung cấp giá trị đầu vào không chính xác. - Sai số phương pháp : xuất hiện do việc giải bài toán bằng phương pháp gần đúng. - Sai số tính toán : xuất hiện do làm tròn số trong quá trình tính toán, quá trình tính càng nhiều thì sai số tích luỹ càng lớn. 2.3. Sai số tính toán Giả sử dùng n số gần đúng x i (i = 1, n ) để tính đại lượng y, với y = f(xi) = f(x1, x2, , xn) Trong đó : f là hàm khả vi liên tục theo các đối số xi Khi đó sai số của y được xác định theo công thức sau: n ∂ f Sai số tuyệt đối: ∆ y = ∑ ∆ x i i =1 ∂ x i n ∂ ln f Sai số tương đối: δy = ∑ ∆x i i=1 ∂x i - Trường hợp f có dạng tổng: y = f(x i ) = ±x1 ± x 2 ± ± x n 7
  8. ∂f n = 1 ∀i suy ra ∆ y = ∑ ∆ x i ∂x i i =1 - Trường hợp f có dạng tích: x *x * *x y = f (x ) = 1 2 k i x * *x k +1 n x1.x2 xm lnf =ln =(lnx1 +lnx2 + +lnxm)−(lnxm+1 + +lnxn ) xm+1 xn n n ∂ ln f 1 ∆x i = ∀i => δ y = ∑ = ∑δx i ∂x i x i i=1 x i i=1 n Vậy δ y = ∑ δx i i=1 - Trường hợp f dạng luỹ thừa: y = f(x) = x α (α > 0) lny = lnf = αlnx ∂lnf α ∆x = Suy ra δy = α. = αδ x ∂x x x Ví dụ. Cho a ≈ 10.25; b ≈ 0.324; c ≈ 12.13 Tính sai số của: a 3 3 y = ; y2 =a −b c 1 b c 1 GiảI δ y = δ ( a 3 ) + δ ( b c ) = 3 δ a + δ b + δ c 1 2 ∆ a ∆ b 1 ∆ c = 3 + + a b 2 c 3 3 3 ∆y2 =∆(a )+∆(b c)= a δ(a )+ b cδ(b c) ∆ a ∆ b 1 ∆ c ∆ y = 3 a 3 + b c ( + ) 2 a b 2 c 8
  9. CHƯƠNG III TÍNH GIÁ TRỊ HÀM 3.1. Tính giá trị đa thức. Sơ đồ Hoocner 3.1.1. Đặt vấn đề Cho đa thức bậc n có dạng tổng quát : n n-1 p(x) = a0x + a1x + + an-1x+ an (a#0) Tính giá trị đa thức p(x) khi x = c (c: giá trị cho trước) 3.1.2. Phương pháp Áp dụng sơ đồ Hoocner nhằm làm giảm đi số phép tính nhân (chỉ thực hiện n phép nhân), phương pháp này được phân tích như sau: p(x) = ( ((a0x + a1)x +a2)x+ +an-1 )x + an Ö p(c) = ( ((a0c + a1)c +a2)c+ +an-1 )c + an Ö Đặt p0 = a0 p1 = a0c + a1 = p0c + a1 p2 = p1c + a2 . . . . . . . . pn = pn-1c + an = p(c) Sơ đồ Hoocner a0 a1 a2 an-1 an p0*c p1*c pn-2*c pn-1*c p0 p1 p2 pn-1 pn= p(c) 4 Vd: Cho p(x) = x6 + 5x + x3 - x - 1 Tính p(-2) Áp dụng sơ đồ Hoocner: 1 0 -5 2 0 -1 -1 -2 4 2 -8 16 -30 1 -2 -1 4 -8 15 -31 Vậy p(-2) = -31 3.1.3. Thuật toán + Nhập vào: n, c, các hệ số ai (i = 0,n ) 9
  10. + Xử lý: Đặt p = a0 Lặp i = 1 → n : p = p * c + ai + Xuất kết quả: p 3.1.4. Chương trình #include #include main ( ) { int i, n; float c, p, a [10]; clrsr (); printf (“Nhap gia tri can tinh : ”); scanf (“%f”,&c); printf (“Nhap bac da thuc : ”); scanf (“%d”,&n); printf (“Nhap các hệ số: \n”); for (i = 0, i<=n; i++) { printf (“a[%d] = ”, i); scanf (“%f”, &a[i]); } p = a[0]; for (i=1, i<=n; i++) p = p*c + a[i]; printf (“Gia tri cua da thuc : %.3f”, p); getch ( ); } 3.2. Sơ đồ Hoocner tổng quát 3.2.1. Đặt vấn đề Cho đa thức bậc n có dạng tổng quát : n n-1 p(x) = a0x + a1x + + an-1x + an (a0 # 0) (1) Xác định các hệ số của p(y + c), trong đó y: biến mới, c: giá trị cho trước 3.2.2. Phương pháp n n-1 Giả sử: p(y+c) = b0y + b1y + + bn-1y + bn (2) Như vậy ta phải xác định các hệ số bi (i = 0, n) 10
  11. ‰ Xác định bn Xét y=0, từ (2) => p(c) = bn ‰ Xác định bn-1 ’ p(x) = (x-c) p1 (x) + p(c) (1 ) Trong đó p1(x) : đa thức bậc n-1 n−1 n−2 p(y + c) = y(b0 y + b1y + + bn−2 y + bn−1) + bn Đặt x=y+c ta có: n−1 n−2 p(x) = (x − c)(b0 y + b1y + + bn−2 y + bn−1) + bn (2’) Đồng nhất (1’) & (2’) suy ra: n-1 n-2 p1(x) = b0y + b1y + + bn-2y + bn - 1 Xét y = 0, p1(c) = bn-1 Tương tự ta có: bn-2 = p2(c), , b1 = pn-1(c) Vậy bn-i = pi(c) (i = 0 >n) , b0 =a0 Với pi(c) là giá trị đa thức bậc n-i tại c Sơ đồ Hoocner tổng quát: a0 a1 a2 an-1 an p0*c p1*c pn-2*c pn-1*c p0 p1 p2 pn-1 pn= p(c)=bn ’ ’ ’ p0 *c p1 *c pn-2 *c ’ ’ ’ p0 p1 p2 pn-1 = p1(c)=bn-1 Ví dụ: Cho p(x) = 2x6 + 4x5 - x2 + x + 2. Xác định p(y-1) 11
  12. Áp dụng sơ đồ Hoocner tổng quát : \p(x) 2 4 0 0 -1 1 2 -2 -2 2 -2 3 -4 p1(x) 2 2 -2 2 -3 4 -2 -2 0 2 -4 7 p2(x) 2 0 -2 4 -7 11 -2 2 0 -4 p3(x) 2 -2 0 4 -11 -2 4 -4 p4(x) 2 -4 4 0 -2 6 p5(x) 2 -6 10 -2 2 -8 6 5 4 2 Vậy p(y-1) = 2y - 8y + 10y - 11y +11y- 2 3.2.3. Thuật toán - Nhập n, c, a [i] (i = 0, n ) - Lặp k = n → 1 Lặp i = 1 → k : ai = ai-1 * c + ai - Xuất ai (i = 0, n ) 3.3. Khai triển hàm qua chuỗi Taylo Hàm f(x) liên tục, khả tích tại x0 nếu ta có thể khai triển được hàm f(x) qua chuỗi Taylor như sau: f ′(x )(x − x ) f ′′(x )(x − x ) 2 f (n ) (x )(x − x ) n f (x) ≈ f (x ) + 0 0 + 0 0 + + 0 0 0 1! 2! n! khi x0 = 0, ta có khai triển Macloranh: f ′(0)x f ′′(0)x 2 f (n) (0)x n f (x) ≈ f (0) + + + + + + 1! 2! n! x 2 x 4 x 6 Ví dụ: Cosx ≈ 1− + − + 2! 4! 6! 12
  13. BÀI TẬP 1. Cho đa thức p(x) = 3x5 + 8x4 –2x2 + x – 5 a. Tính p(3) b. Xác định đa thức p(y-2) 2. Khai báo (định nghĩa) hàm trong C để tính giá trị đa thức p(x) bậc n tổng quát theo sơ đồ Hoocner 3. Viết chương trình (có sử dụng hàm ở câu 1) nhập vào 2 giá trị a, b. Tính p(a) + p(b) 4. Viết chương trình nhập vào 2 đa thức pn(x) bậc n, pm(x) bậc m và giá trị c. Tính pn(c) + pm(c) 5. Viết chương trình xác định các hệ số của đa thức p(y+c) theo sơ đồ Hoocner tổng quát 6. Khai báo hàm trong C để tính giá trị các hàm ex, sinx, cosx theo khai triển Macloranh. 13
  14. CHƯƠNG IV GIẢI GẦN ĐÚNG PHƯƠNG TRÌNH 4.1. Giới thiệu Để tìm nghiệm gần đúng của phương trình f(x) = 0 ta tiến hành qua 2 bước: - Tách nghiệm: xét tính chất nghiệm của phương trình, phương trình có nghiệm hay không, có bao nhiêu nghiệm, các khoảng chứa nghiệm nếu có. Đối với bước này, ta có thể dùng phương pháp đồ thị, kết hợp với các định lý mà toán học hỗ trợ. - Chính xác hoá nghiệm: thu hẹp dần khoảng chứa nghiệm để hội tụ được đến giá trị nghiệm gần đúng với độ chính xác cho phép. Trong bước này ta có thể áp dụng một trong các phương pháp: + Phương pháp chia đôi + Phương pháp lặp + Phương pháp tiếp tuyến + Phương pháp dây cung 4.2. Tách nghiệm * Phương pháp đồ thị: Trường hợp hàm f(x) đơn giản - Vẽ đồ thị f(x) - Nghiệm phương trình là hoành độ giao điểm của f(x) với trục x, từ đó suy ra số nghiệm, khoảng nghiệm. Trường hợp f(x) phức tạp - Biến đổi tương đương f(x)=0 g(x) = h(x) - Vẽ đồ thị của g(x), h(x) - Hoành độ giao điểm của g(x) và h(x) là nghiệm phương trình, từ đó suy ra số nghiệm, khoảng nghiệm. * Định lý 1: Giả sử f(x) liên tục trên (a,b) và có f(a)*f(b)<0. Khi đó trên (a,b) tồn tại một số lẻ nghiệm thực x ∈ (a,b) của phương trình f(x)=0. Nghiệm là duy nhất nếu f’(x) tồn tại và không đổi dấu trên (a,b). 14
  15. Ví dụ 1. Tách nghiệm cho phương trình: x3 - x + 5 = 0 Giải: f(x) = x3 - x + 5 f’(x) = 3x2 - 1 , f’(x) = 0 x = ±1/ 3 Bảng biến thiên: x - ∞ −1/ 3 1/ 3 +∞ f’(x) + 0 - 0 + yCĐ phæång trçnh coï 1 nghiãûm x ∈ (1, 2) 15
  16. * Âënh lyï 2: (Sai säú) Giaí sæí α laì nghiãûm âuïng vaì x laì nghiãûm gáön âuïng cuía phæång trçnh f(x)=0, cuìng nàòm trong khoaíng nghiãûm [ a,b] vaì f '(x) = ≥ m ≥ 0 khi a ≤ x f (x) ≤ b. Khi âoï x − α ≤ m Vê du 3. Cho nghiãûm gáön âuïng cuía phương trình x4 - x - 1 = 0 laì 1.22. Haîy æåïc læåüng sai säú tuyãût âäúi laì bao nhiãu? Giải: f (x) = f (1.22) = 1.224 - 1.22 - 1 = - 0,0047 0 ⇒ nghiãûm phæång trçnh x ∈ (1.22 , 1.23) f '(x) = 4 x3 -1 > 4*1.223 - 1 = 6.624 = m ∀x ∈ (1.22 , 1.23) Theo âënh lyï 2 : ∆x = 0.0047/6.624 = 0.0008 (vç |x - α | 0, am là hệ số âm đầu tiên. Khi đó mọi nghiệm m dương của phương trình đều ≤ N = 1 + a / a 0 , với a = max {⏐ai⏐} i = 0, n sao cho ai < 0. Ví dụ 4. Cho phương trình: 5x5 - 8x3 + 2x2 - x + 6 = 0 Tìm cận trên nghiệm dương của phương trình trên Giải: Ta có a2 = -8 là hệ số âm đầu tiên, nên m = 2 a = max( 8, 1) = 8 Vậy cận trên của nghiệm dương: N = 1 + 8 / 5 * Âënh lyï 5: 16
  17. Cho phæång trçnh (1), xeït caïc âa thæïc: n n ϕ1(x) = x f (1/x) = a0 + a1x + + anx n n n-1 n-2 n ϕ2(x) = f(-x) = (-1) (a0x - a1x + a2x - + (-1) an) n n n n-1 n-2 n ϕ3(x) = x f(-1/x) = (-1) (anx - an-1x + an-2x - + (-1) a0) Giaí sæí N0, N1, N2, N3 laì cáûn trãn caïc nghiãûm dæång cuía caïc âa thæïc f(x), ϕ1(x), ϕ2(x), ϕ3(x). Khi âoï moüi nghiãûm dæång cuía phtrçnh (1) âãöu nàòm trong khoaíng [1/N1, N0] vaì moüi nghiãûm ám nàòm trong khoaíng [-N2,-1/N3] Vê duû 5. Xét phương trình 2 3x + 2x - 5 = 0 → N0 = 1 + 5/3 (âënh lyï 4) 2 ϕ1(x) = 3 + 2x - 5x → N1 khäng täön taûi (a0 - (1 +5/3) = - 8/3 4.4. Chính xác hoá nghiệm 4.4.1. Phương pháp chia đôi a. Ý tưởng Cho phương trình f(x) = 0, f(x) liên tục và trái dấu tại 2 đầu [a,b]. Giả sử f(a) 0 [ai, bi] = [(ai-1+ bi-1)/2, bi] nếu f((ai-1+ bi-1)/2) < 0 Như vậy: - Hoặc nhận được nghiệm đúng ở một bước nào đó: µ = (ai-1+ bi-1)/2 nếu f((ai-1+ bi-1)/2) = 0 - Hoặc nhận được 2 dãy {an} và {bn}, trong đó: 17
  18. {an}: là dãy đơn điệu tăng và bị chặn trên {bn}: là dãy đơn điệu giảm và bị chặn dưới nên ∃ lim a n = lim b n = µ là nghiệm phương trình n → α Ví dụ 6. Tìm nghiệm phương trình: 2x + x - 4 = 0 bằng ppháp chia đôi Giải: - Tách nghiệm: phương trình có 1 nghiệm x ∈ (1,2) - Chính xác hoá nghiệm: áp dụng phương pháp chia đôi ( f(1) 0 - Lặp c = (a+b)/2 nếu f(c) > 0 → b = c ngược lại a = c trong khi (⏐f(c)⏐> ε) /* ⏐a - b⏐ > ε và f(c) != 0 */ 18
  19. - Xuất nghiệm: c 4.4.2. Phương pháp lặp a. Ý tưởng Biến đổi tương đương: f(x) = 0 x = g(x) Chọn giá trị ban đầu x0 ∈khoảng nghiệm (a,b), tính x1 = g(x0), x2 = g(x1), , xk = g(xk-1) Như vậy ta nhận được dãy {xn}, nếu dãy này hội tụ thì tồn tại giới hạn n→∞ limx n =η (là nghiệm phương trình ) b. Ý nghĩa hình học Hoành độ giao điểm của 2 đồ thị y=x và y=g(x) là nghiệm phương trình C y y y = x B y = x y = g(x) A A B C µ x x x 2 1 0 x µ x x1 x x 0 2 Hình a Hình b Trường hợp hình a: hội tụ đến nghiệm µ Trường hợp hình a: không hội tụ đến nghiệm µ (phân ly nghiệm) Sau đây ta xét định lý về điều kiện hôi tụ đến nghiệm sau một quá trình lặp Định lý (điều kiện đủ) Giả sử hàm g(x) xác định, khả vi trên khoảng nghiệm [a,b] và mọi giá trị g(x) đều thuộc [a,b]. Khi đó nếu ∃ q > 0 sao cho ⏐g’(x)⏐≤q<1 ∀x (a,b) thì: + Quá trình lặp hội tụ đến nghiệm không phụ thuộc vào x0 ∈ [a,b] + Giới hạn n→∞ limx n =η là nghiệm duy nhất trên (a, b) Lưu ý: - Định lý đúng nếu hàm g(x) xác định và khả vi trong (-∞,+∞), trong khi đó điều kiện định lý thoả mãn. 19
  20. - Trong trường hợp tổng quát, để nhận được xấp xỉ xn vớI độ chính xác ε cho trước, ta tiến hành phép lặp cho đến khi 2 xấp xỉ liên tiếp thoả mãn: 1− q x −x ≤ ε n+1 n q Ví dụ 7. Tìm nghiệm: x3 - x - 1 = 0 bằng phương pháp lặp Giải: - Tách nghiệm: phương trình có một nghiệm ∈ (1,2) - Chính xác hoá nghiệm: x + 1 x 3 − x −1 = 0 ⇔ x = x 3 −1; x = ; x = 3 x + 1 x 2 Chọn g(x) = 3 x +1 1 1 g'(x) = 3 áp dụng phương pháp lặp (chọn x0 = 1) 3 x g(x) = x +1 1 1.260 1.260 1.312 1.312 1.322 1.322 1.324 1.324 1.325 1.325 1.325 -3 ⏐x4 - x5⏐ ε - Xuất nghiệm: x (hoặc y) 20
  21. 4.4.3. Phương pháp tiếp tuyến a. Ý tưởng Chọn x0 ∈ khoảng nghiệm (a, b) Tiếp tuyến tại A0 (x0, f(x0)) cắt trục x tại điểm có hoành độ x1, Tiếp tuyến tại A1 (x1, f(x1)) cắt trục x tại điểm có hoành độ x2, , Tiếp tuyến tại Ak (xk, f(xk)) cắt trục x tại điểm có hoành độ xk, Cứ tiếp tục quá trình trên ta có thể tiến dần đến nghiệm µ của phương trình. * Xây dựng công thức lặp: Phương trình tiếp tuyến tại Ak (xk, f(xk)) y - f(xk) = f’(xk)*(x - xk) Tiếp tuyến cắt trục x tại điểm có toạ độ (xk+1, 0) Do vậy: 0 – f(xk) = f’(xk)*(xk+1 - xk) f (x k ) x k+1 = x k − f '(x k ) b. Ý nghĩa hình học y f(x) A0 → tiếp tuyến A1 x [ ] µ a x2 x1 x0 b Định lý (điều kiện hội tụ theo Furiê_điều kiện đủ) Giả sử [a,b] là khoảng nghiệm của phương trình f(x)=0. Đạo hàm f’(x), f’’(x) liên tục, không đổi dấu, không tiêu diệt trên [a,b]. Khi đó ta chọn xấp xỉ nghiệm ban đầu x0 ∈[a,b] sao cho f(x0)*f’’(x0) > 0 thì quá trình lặp sẽ hội tụ đến nghiệm. Ví dụ 8. Giải phương trình: x3 + x - 5 = 0 bằng phương pháp tiếp tuyến Giải: - Tách nghiệm: f(x) = x3 + x - 5 21
  22. f’(x) = 3x2 + 1 > 0 ∀x n→−∞ limf (x)=− ∞ , n→+∞ limf (x)=+ ∞ Phương trình trên có 1 nghiệm duy nhất f(1)* f(2) = (-3)*5 0 ∀x ∈ (1, 2) f’(x) > 0 ∀x Thoả mãn điều kiện hội tụ Furiê, áp dụng phương pháp tiếp tuyến Chọn với x0 = 2 ( vì f(2). f’’(2) > 0) x f(x)/f’(x) 2 0.385 1.615 0.094 1.521 0.005 1.516 0.000 1.516 Vậy nghiệm x ≈ 1.516 c. Thuật toán - Khai báo hàm f(x), fdh(x) - Nhập x - Lặp y= x x = y – f(y)/fdh(y) trong khi ⏐x - y⏐> ε - Xuất nghiệm: x (hoặc y) 4.4.4. Phương pháp dây cung a. Ý tưởng Giả sử [a, b] là khoảng nghiệm phương trình f(x)=0. Gọi A, B là 2 điểm trên đồ thị f(x) có hoành độ tương ứng là a, b. Phương trình đường thẳng qua 2 điểm A(a,f(a)), B(b, f(b)) có dạng: y − f (a) x − a = f (b) − f (a) b − a 22
  23. Dây cung AB cắt trục x tại điểm có toạ độ (x1, 0) 0 − f (a) x − a Do đó: = 1 f (b) − f (a) b − a (b − a)f (a) x = a − 1 f (b) − f (a) Nếu f(a)*f(x1) 0 23
  24. Bảng kết quả: a b x f(x) 1 2 1.333 -0.447 1.333 1.379 -0.020 1.379 1.385 -0.003 1.385 1.386 -0.000 1.386 1.386 Vậy nghiệm phương trình: x ≈1.386 c. Thuật toán - Khai báo hàm f(x) - Nhập a, b - Tính x = a – (b-a)f(a) / (f(b)-f(a)) - Nếu f(x)*f(a) ε Ngược lại Lặp a = x x = a – (b-a)f(a) / (f(b)-f(a)) trong khi ⏐x - a⏐> ε - Xuất nghiệm: x 24
  25. BÀI TẬP 1. Tìm nghiệm gần đúng các phương trình: a. x3 – x + 5 = 0 b. x3 – x – 1 = 0 c. sinx –x + 1/4 = 0 d. x4 – 4x – 1= 0 bằng phương pháp chia đôi với sai số không quá 10-3 2. Tìm nghiệm gần đúng các phương trình: a. x3 – x + 5 = 0 b. x4 – 4x – 1 = 0 bằng phương pháp dây cung với sai số không quá 10-2 3. Tìm nghiệm gần đúng các phương trình: a. ex – 10x + 7 = 0 b. x3 + x – 5 = 0 bằng phương pháp tiếp tuyến với sai số không quá 10-3 4. Dùng phương pháp lặp tìm nghiệm dương cho phương trình x3 – x – 1000 = 0 với sai số không quá 10-3 5. Tìm nghiệm dương cho phương trình: x3 + x2 –2x – 2 = 0 6. Tìm nghiệm âm cho phương trình: x4 - 3x2 + 75x – 1000 = 0 7. Dùng các phương pháp có thể để tìm nghiệm gần đúng cho phương trình sau: cos2x + x – 5 = 0 8. Viết chương trình tìm nghiệm cho có dạng tổng quát: n n-1 f(x) = a0x + a1x + + an-1x + an = 0 a. Áp dụng phương pháp chia đôi b. Áp dụng phương pháp dây cung 9. Viết chương trình tìm nghiệm cho phương trình ex – 10x + 7 = 0 bằng phương pháp tiếp tuyến. 10. Viết chương trình xác định giá trị x1, x2 theo định lý 3. 11. Viết chương trình tìm cận trên của nghiệm dương phương trình đại số theo định lý 4. 25
  26. CHƯƠNG V GIẢI HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH 5.1. Giới thiệu Cho hệ phương trình tuyến tính: a11x1 + a12x2 + + a1nxn = a1n+1 a21x1 + a22x2 + + a2nxn = a2n+1 an1x1 + an2x2 + + annxn = ann+1 Hệ phương trình trên có thể được cho bởi ma trận: a11 a12 a1n a1n+1 a21 a22 a2n a2n+1 Ann+1 = an1 an2 ann ann+1 Vấn đề: Tìm vectơ nghiệm x = (x 1 , x 2 , , x n ) * Phương pháp: - Phương pháp đúng (Krame, Gauss, khai căn): Đặc điểm của các phương pháp này là sau một số hữu hạn các bước tính, ta nhận được nghiệm đúng nếu trong quá trình tính toán không làm tròn số - Phương pháp gần đúng (Gauss Siedel, giảm dư): Thông thường ta cho ẩn số một giá trị ban đầu, từ giá trị này tính giá trị nghiệm gần đúng tốt hơn theo một qui tắc nào đó. Quá trình này được lặp lại nhiều lần và với một số điều kiện nhất định, ta nhận được nghiệm gần đúng. 5.2. Phương pháp Krame - Khai báo hàm Dt tính định thức ma trận vuông cấp n - Nhập n, aij (i = 1,n; j =1,n +1) - d = Dt (A) - Xét + d = 0 + d # 0 {di = Dt(Ai) ; xi = di/d } 26
  27. 5.3. Phương pháp Gauss 5.3.1. Nội dung phương pháp - Biến đổi Ma trận A về ma trận tam giác trên a11 a12 a1n a1n+1 a21 a22 a2n a2n+1 A = an1 an2 ann ann+1 a11 a12 a1n a1n+1 0 a'22 a'2n a'2n+1 → A= 0 0 a'nn a'nn+1 Cách biến đổi A → A’: Thực hiện n-1 lần biến đổi Lần biến đổi i (làm cho aji = 0; j = i + 1 → n) bằng cách: dòng j = dòng j + dòng i * m (m = -aji / aij ) - Tìm nghiệm theo quá trình ngược: xn → nn-1 → → x1 Ví dụ 1. Giải hệ phương trình 1 2 -1 3 5 1 2 -1 3 5 -2 X 2 1 0 -1 2 → 0 -3 2 -7 -8 1 X -1 3 2 4 8 5/3 0 5 1 7 13 1 X -2 0 5 1 4 4/3 0 4 3 7 14 1 2 -1 3 5 1 2 -1 3 5 0 -3 2 -7 -8 0 -3 2 -7 -8 −17 0 0 13/3 -14/3 -1/3 → 0 0 13/3 -14/3 -1/3 13 0 0 17/3 -7/3 10/3 0 0 0 49/13 49/13 ⇒ x4 = 1; x3 = 1; x2 = 1; x1 = 1 Vậy nghiệm hệ phương trình x = (1,1,1,1) 5.3.2. Thuật toán - Nhập n, aij ( i = 1, n, j = 1, n +1) (nhập trực tiếp hoặc từ file) 27
  28. - Biến đổi A → A’ (ma trận tam giác trên) Lặp i = 1 → n -1 Tìm j sao cho aji # 0 + Xét aij = 0 → Hoán đổi dòng i và dòng j cho nhau + Lặp j = i + 1 → n • m = -aij/aii • Lặp k = i → n +1 ajk = ajk + aik * m - Tìm nghiệm ⎛ n ⎞ ⎜ ⎟ x i = ⎜a in+1 − ∑a ijx j ⎟ / a ii ( i =n→ 1) ⎝ j=i+1 ⎠ Lặp i = n → 1 • s = 0 • lặp j = i + 1 → n S = S + aij * xj • xi = (ain+1 - s)/aii - Xuất xi (i=1→n) 5.4. Phương pháp lặp Gauss - Siedel (tự sửa sai) 5.4.1. Nội dung phương pháp → → → Biến đổi hệ phương trình về dạng: x= B x + g → → x = (x1, x 2 , ,x n ); g = (g1,g 2 , ,g n ) ; B = {bij}n Cách biến đổi: a11x1 +a12x2 + + a1nxn = a1n+1 a21x1 +a22x2 + + a2nxn = a2n+1 an1x1 +an2x2 + + annxn = ann+1 n x1 = (a n+1 − ∑a1jx j )/ a11(j ≠1) j=1 n x n = (a nn+1 − ∑ a njx j ) / a nn (j ≠ n) j=1 Tổng quát: 28
  29. n xi = (a in+1 − ∑a ijx j )/ a ii (j ≠ i) (*) j=1 → 0 0 0 Cho hệ phương trình xấp xỉ nghiệm ban đầu: x 0 = (x 0 , x 2 , , x n ) → → 1 1 1 Thay x 0 vào (*) để tính: x 1 = (x 0 , x 2 , , x n ) n 1 0 x i = (a in +1 − ∑ a ij x j ) / a ii ( j ≠ i) j=1 → → Tương tự, tính x 2 , x 3 , n k +1 k Tổng quát: x i = (a in +1 − ∑ a ij x j ) / a ii ( j ≠ i) j=1 Quá trình lặp sẽ dừng khi thoả mãn tiêu chuẩn hội tụ tuyệt đối: k + i k x i − x i < ε (∀i = 1, n ) k k k Khi đó x k = (x 1 , x 2 , , x n ) là nghiệm của hệ phương trình Điều kiện hội tụ: Hệ phương trình có ma trận lặp B thoả mãn: n r1 = max ∑ bij < 1 i j=1 n hoặc r2 = max ∑ bij < 1 j i=1 n 2 hoặc r3 = ∑∑bij < 1 i1==1 j thì quá trình sẽ hội tụ đến nghiệm. Ví dụ 2. Giải hệ phương trình 10 2 1 10 1 10 2 10 1 1 10 8 x1 = -0,2x2 - 0,1x3 + 1 x2 = -0,1x1 - 0,2x3 + 1,2 x3 = -0,1x1 - 0,1x2 + 0,8 29
  30. 0 -0,2 -0,1 B = -0,1 0 -0,2 -0,1 -0,1 0 g = (1, 1.2, 0.8) 3 Do r1 = max∑ bij =0.3 = ε ) t=1 30
  31. xi = yi } trong khi (t) - Xuất xi (i =1→n) 5.5. Phương pháp giảm dư 5.5.1. Nội dung phương pháp Biến đổi hệ phương trình về dạng: a1n + 1 - a11x1 - a12x2 - - a1nxn = 0 a2n + 1 - a21x1 - a22x2 - - a2nxn = 0 (1) ann + 1 - an1x2 - an2x2 - - annxn = 0 Chia dòng i cho aii # 0 b1n + 1 - b12x2 - b13x2 - - x1 = 0 b2n + 1 - b21x1 – b23x3 - - x2 = 0 (2) bnn + 1 - bn1x1 - bn2x2 - - xn = 0 → 0 0 0 Cho vectơ nghiệm ban đầu x 0 = ( x 1 , x 2 , , x n ) → Vì x 0 không phải là nghiệm nên: 0 0 0 0 b1n+1 - b12x2 - b13x3 - - x1 = R1 0 0 0 0 b2n+1 - b21x1 - b23x3 - - x2 = R2 0 0 0 0 bnn+1 - bn1x1 - bn2x2 - - xn = Rn → 0 0 0 R1 ,R2, ,Rn là các số dư do sự sai khác giữa x 0 với nghiệm thực của hệ phương trình 0 0 0 0 Tìm Rs = max {|R1 |, | R2 |, | Rn |} vaì laìm triãût tiãu phán tæí âoï bàòng 0 1 0 0 caïch cho xs mäüt säú gia δxs = Rs , nghéa laì xs = xs + Rs Tính lại các số dư : 1 Rs = 0 1 0 0 0 R i = Ri - bis * δxs = Ri - bis * Rs (i = 1Æ n) k Cæï tiãúp tuûc quaï trçnh làûp trãn cho âãún khi : ⎟Ri ⎟< ε (∀i = 1Æn) thç Xk = k k k (x1 , x2 , xn ) laì nghiãûm cuía hã phtrçnh. 31
  32. Ví dụ 3. Giải hệ phương trình: 10 -2 -2 6 -2 10 -1 7 1 1 -10 8 Giải: Biến đổi về hệ phương trình tương đương 0,6 + 0,2 x2 + 0,2x3 - x1 = 0 0,3 + 0,2 x1 + 0,2x3 - x2 = 0 0,8 + 0,1 x1 + 0,1x2 - x3 = 0 → → Cho x 0 = (0,0,0) → R 0 = (0.6, 0.7, 0.8) 0 0 R 3 = max{R i } ∀i = 1,3 0 0 x31 = x 3 + R 3 = 0.8 0 0 R2 = R 2 + b 23.R 3 = 0.7 + 0.1× 0.8 = 0.78 1 0 0 R 1 = R 1 + b13.R 3 = 0.6 + 0.2× 0.8 = 0.76 → R1 = (0.76, 0.78, 0) Tương tự ta có bảng kết quả: x1 x2 x3 R1 R2 R3 0 0 0 0.6 0.7 0.8 0.8 0.76 0.78 0 0.78 0.92 0 0.08 0.92 0 0.18 0.17 0.96 0.04 0 0.19 0.99 0.07 0.02 0 0.99 0 0.03 0.01 0.99 0.01 0 0.01 1 0.01 0 0 1 0 0.01 0 1 0 0 0 Vậy nghiệm hệ phương trình x = (1, 1, 1) 5.5.2. Thuật toán - Nhập n, aij, xi - Biến đổi hệ phương trình (1) về dạng (2) 32
  33. for (i=1, i ε) thi t =1 /* cho lap*/ trong khi ( t ) - Xuất nghiệm: x[i] (i = 1→n) Lưu ý: - Phương pháp chỉ thực hiện được khi aii # 0, nếu không phảI đổi dòng - Quá trình hội tụ không phụ thuộc vào x0 mà chỉ phụ thuộc vào bản chất của hệ phương trình. - Mọi hệ phương trình có giá trị riêng λ ≥ 1 đều hội tụ đến nghiệm một cách nhanh chóng. - Nếu các phần tử aii càng lớn hơn các phần tử trên dòng bao nhiêu thì quá trình hội tụ càng nhanh. 33
  34. CHƯƠNG VI TÌM GIÁ TRỊ RIÊNG - VECTƠ RIÊNG 6.1. Giới thiệu Cho ma trận vuông cấp n a11 a12 a1n a21 a22 a2n A = an1 an2 ann → Tìm giá trị riêng, Vectơ riêng x của ma trận A → Nghĩa là: tìm λ và x sao cho : det (A - λE) = 0 ( E : Ma trận đơn vị) → (A - λE) x = 0 Để tránh việc khai triển định thức (đòi hỏi số phép tính lớn) khi tìm λ ta có thể áp dụng phương pháp Đanhilepski. Ở phương pháp này ta chỉ cần tìm ma trận B sao cho B đồng dạng với ma trận A và B có dạng ma trận Phơrêbemit. p1 p2 pn-1 pn 1 0 0 0 P = 0 1 0 0 0 0 1 0 Khi đó giá trị riêng của ma trận A cũng là giá trị riêng của ma trận B. 6.2. Ma trận đồng đạng 6.2.1. Định nghĩa Ma trận B gọi là đồng dạng với ma trận A (B ∼ A) nếu tồn tại ma trận không suy biến M (det(M)≠ 0) sao cho B = M-1A M 6.2.2. Tính chất: A ∼ B ⇒ B ∼ A A ∼ B, B ∼ C ⇒ A ∼ C A ∼ B ⇒ giá trị riêng λ của A và B trùng nhau. 34
  35. 6.3. Tìm giá trị riêng bằng phương pháp Đanhilepski 6.3.1. Nội dung phương pháp Thực hiện n-1 lần biến đổi: -1 -1 * Lần biến đổi 1: Tìm M , M sao cho A1 = M A M ∼ A và dòng n của A1 có dạng: 0 0 0 1 0 1 0 0 -1 0 1 0 -1 M = M n-1j = anj an1 an2 ann 0 0 1 1 0 0 0 0 1 0 0 1 M = − a n1 − a n2 − a nn a a nn−1 a nn−1 nn−1 a nn−1 0 0 0 1 1 nếu j = n -1 a nn − 1 Mn-1j = − a nj nếu j # n - 1 a nn −1 A1 = M-1 A M ∼ A * Lần biến đổi 2: Chọn M-1, M sao cho A2 = M-1 A1 M ∼ A1 và dòng n-1 của A2 có dạng: 0 0 0 1 0 0 A2 ∼ A1 , A1∼ A => A2 ∼ A (tính chất) . * Lần biến đổi thứ n-1 Ta nhận được ma trận An-1 ∼ A và An-1 có dạng của P. Khi đó định thức n n n-1 det (P-λE) = (-1) (λ - p1 λ - - pn-1λ - pn) n n-1 det (p-λE) = 0 ⇔ λ - p1 λ - - pn-1λ - pn = 0 35
  36. Giải phương trình, suy ra λ Ví dụ 1. Tìm giá trị riêng của ma trận: 2 1 0 A = 1 3 1 n = 3 0 1 2 ta tìm: p1 p2 P3 P = 1 0 0 0 1 0 Lần 1: Chọn 1 0 0 1 0 0 -1 M = 0 1 2 M = 0 1 -2 010 0 0 1 2 1 -2 -1 A1 = M A M = 1 5 -5 0 1 0 Lần 2: Chọn 1 5 -5 M-1 = 0 1 0 0 0 1 1 -5 5 M = 0 1 0 0 0 1 7 -14 8 -1 A2 = M A1M= 1 0 0 =P 0 1 0 Giá trị riêng λ là nghiệm phương trình: λ3 - 7λ2 + 14λ - 8 = 0 ⇔ (λ-2) (λ-1) (λ-4) = 0 ⇔ λ = 2; λ=1; λ=4 36
  37. 6.3.2. Thuật toán - Nhập n, aij ( i,j = 1Æn) - Khai báo hàm nhân 2 ma trận vuông cấp n n (C = A x B => cij = ∑ aik × bkj ) k=1 - Lặp k = n -1 → 1 (phần tử biến đổi : ak+1 k ) /* Tính 2 ma trận M, M1 (M1 la ma tran nghich dao cua M) */ for i = 1 → n for j = 1 n if i ≠ k if i = j {M[i,j] = 1; M1[i,j] = 1 } else {M[i,j] = 0; M1[i,j] = 0 } else { M1[i,j] = a[k+1,j] if (j = k) M[i,j] = 1/a[k+1,k] else M[i,j] = - a[k+1,j]/a[k+1,k] } /* Gọi hàm nhân 2 lần */ Lần 1 : vào A, M; ra B Lần 2 : vào M1; B; ra A - Xuất aij ( i,j = 1→n) ™ Thuật toán nhân 2 ma trận for (i=1, i < = n; i++) for (j=1; j< = n; j++) { c[i] [j] = 0 for (k=1; k < = n; k++) c[i] [j] + = a [i] [k] * b [k] [j] } 37
  38. 6.4. Tìm vectơ riêng bằng phương pháp Đanhilepski 6.4.1. Xây dựng công thức → Gọi y là vectơ riêng của ma trận P ∼ A → Ta có: (P - λE) y = 0 → → P y = λE y -1. → → M A. M . y = λE y Nhân 2 vế cho M: → → M M-1. A M y = M λE y → → A M y = λ E M y → → Đặt x = M y → → A x = λE x → (A - λE) x = 0 → → Vậy x = M y là vectơ riêng của A −1 −1 −1 P = M n−1 .M n−2 M1 .A.M1 .M 2 .M n−1 Mi: Ma trận M xác định được ở lần biến đổi thứ i và M = M1 M2 Mn-1 → Xác định y → (P-λE) y = 0 p1 - λ p2 pn-1 pn y1 1 λ 0 0 y2 = 0 0 0 1 -λ yn (p1 - λ)y1 + p2y2 + + pn-1yn-1 + pnyn = 0 y1 - λy2 = 0 yn-1 - λyn = 0 cho: yn = 1 ⇒ yn-1 = λ , 2 n-1 yn-2 = λ yn-1 = λ , , y1 = λ 38
  39. → Vậy y = (λn-1, λn-2, , λ2, λ, 1) Ví dụ 2. Tìm vectơ riêng của A 2 1 0 A = 1 3 1 0 1 2 → Giải: Gọi y là vectơ riêng của ma trận P ∼ A Ở ví dụ 1 ta có: → λ1 = 2 ⇒ y 1 = (4, 2, 1) → λ2 = 1 ⇒ y 2 = (1, 1, 1) → λ3 = 4 ⇒ y 3 = (16, 4, 1) Tìm M: 1 0 0 1 -5 -5 1 -5 5 1 1 M = M1 .M 2 = 0 1 -2 0 1 0 = 0 1 -2 0 1 0 0 0 1 0 0 1 → → x = M y 1 -5 5 4 -1 → x 1 = 0 1 -2 2 = 0 0 0 1 1 1 1 -5 5 1 1 → x 2 = 0 1 -2 1 = -1 0 0 1 1 1 1 -5 5 16 1 → x 3 = 0 1 -2 4 = 2 0 0 1 1 1 Vậy vectơ riêng của A: → → → x 1 = (-1, 0, 1) x 2 = (1, -1, 1) x 3 = (1, 2, 1) 6.4.2. Thuật toán Bổ sung thêm lệnh trong thuật toán tìm trị riêng như sau: 39
  40. - Khởi tạo B1 = E - Lặp k = n-1 → 1 /* Tính 2 ma trận M, M1 */ /* Gọi hàm nhân 3 lần */ Lần 1: vào A, M; ra B Lần 2: vào M1, B; ra A Lần 3: vào B1, M; ra B /* Gán lại ma trận B1=B */ - Xuất aij, bij 40
  41. CHƯƠNG VII NỘI SUY VÀ PHƯƠNG PHÁP BÌNH PHƯƠNG BÉ NHẤT 7.1. Giới thiệu Trong toán học ta thường gặp các bài toán liên quan đến khảo sát và tính giá trị các hàm y = f(x) nào đó. Tuy nhiên trong thực tế có trường hợp ta không xác định được biểu thức của hàm f(x) mà chỉ nhận được các giá trị rời rạc: y0, y1, , yn tại các điểm tương ứng x0, x1, , xn. Vấn đề đặt ra là làm sao để xác định giá trị của hàm tại các điểm còn lại. Ta phải xây dựng hàm ϕ (x) sao cho: ϕ (xi) = yi = f (xi) với i = 0, n ϕ (x) ≈ f (x) ∀x thuộc [a, b] và x ≠ xi - Bài toán xây dựng hàm ϕ (x) gọi là bài toán nội suy - Hàm ϕ (x) gọi là hàm nội suy của f(x) trên [a, b] - Các điểm xi ( i = 0, n ) gọi là các mốc nội suy Hàm nội suy cũng được áp dụng trong trường hợp đã xác định được biểu thức của f(x) nhưng nó quá phức tạp trong việc khảo sát, tính toán. Khi đó ta tìm hàm nội suy xấp xỉ với nó để đơn giản phân tích và khảo sát hơn. Trong trường hợp đó ta chọn n+1 điểm bất kỳ làm mốc nội suy và tính giá trị tại các điểm đó, từ đó xây dựng được hàm nội suy (bằng công thức Lagrange, công thức Newton, ). Trường hợp tổng quát: hàm nội suy ϕ(x) không chỉ thoả mãn giá trị hàm tại mốc nội suy mà còn thoả mãn giá trị đạo hàm các cấp tại mốc đó. ϕ’(x0) = f’(x0); ϕ’(x1) = f’(x1); ϕ’’(x0) = f’’(x0); ϕ’’(x1) = f’’(x1); Nghĩa là ta tìm hàm nội suy của f(x) thỏa mãn bảng giá trị sau: 41
  42. xi x0 x1 xn yi =f(xi) y0 y1 yn y'i=f’(xi) y'0 y'1 y'n y'’i=f’’(xi)y'’0 y'’1 y'’n 7.2. Đa thức nội suy Lagrange Giả sử f(x) nhận giá trị yi tại các điểm tương ứng xi (i = 0, n ), khi đó đa thức nội suy Lagrange của f(x) là đa thức bậc n và được xác định theo công thức sau: n i Ln (x) = ∑ y i p n (x) i = 0 i (x − x0 )(x − x1) (x − xi−1)(x − xi+1) (x − x n ) TS(x) pn (x) = = (xi − x 0 )(xi − x1) (xi − xi−1)(xi − xi+1) (xi − x n ) MS Đặt W(x) = (x - x0)(x - x1) (x - xn) W(x) Suy ra: TS(x) = ; MS = W' (xi ) x - x i n yi Ln(x) = W(x) ∑ i=0 (x - xi )W'(xi ) Ví dụ 1. Cho hàm f(x) thoả mãn: xi 0 1 2 4 f(xi) 2 3 -1 0 Tìm hàm nội suy của f(x), tính f(5) Giải: Cách 1: W(x) = x (x - 1) (x - 2) (x - 4) W’(0) = (-1) (-2)(-4) = -8 W’(1) = 1 (-1) (-3) = 3 W’(2) = 2 (1) (-2) = -4 W’(4) = 4 (3) (2) = 24 2 3 1 L3(x) = x(x − 1)(x − 2)(x − 4)( + + ) x(−8) 3(x − 1) 4(x − 2) 42
  43. 1 = (−(x − 1)(x − 2)(x − 4) + 4x(x − 2)(x − 4) + x(x − 1)(x − 4)) 4 1 = (x − 4)(−(x −1)(x − 2)+ 4x(x − 2)+ x(x −1)) 4 1 = (x − 4)(4x 2 − 6x − 2) 4 Cách 2: (x −1)(x − 2)(x − 4) x(x − 2)(x − 4) x(x −1)(x − 4) L3(x) = 2 + 3 −1 (−1)(−2)(−4) 1(−1)(−3) 2(1)(−2) 1 = (x − 4)(4x 2 − 6x − 2) 4 7.3. Đa thức nội suy Lagrange với các mối cách đều Giả sử hàm f(x) nhận giá trị yi tại các điểm tương ứng xi ( i = 0, n ) cách đều một khoảng h. x − x Đặt t = 0 , khi đó: h x - x0 = h*t xi - x0 = h *i x- x1 = h(t - 1) xi = x1 = h(i-1) x - xi-1 = h(t- (i-1)) xi - xi-1 = h x - xi+1 = h(t -(i+1)) xi - xi+1 = -h x - xn = h(t - n) xi - xn = -h(n - i) t(t −1) * * (t − (i −1)(t − (i +1)) * * (t − n) p' (x + ht) = n 0 i(i −1) * *1(−1)n−i *1* 2 * * (n − i) t(t −1) * * (t − n) = (t − i) *i!(n − i)!*(−1)n−i n n−i yi (−1) Ln(x0 + ht) = t(t -1) (t - n) ∑ i=0 (t −i)i!(n −i)! n n−i i i t(t −1) (t − n) (−1) .y cn Ln(x0 + ht) = ∑ n! i=0 t − i Ví dụ 2. Tìm hàm nội suy của f(x) thoả mãn: 43
  44. xi 0 2 4 f(x0) 5 -2 1 Giải: Cách 1: W(x) = x (x - 2) (x - 4) W’(0) = (0 - 2) (0 - 4) = -8 W’(2) = (2 - 0) (2 - 4) = -4 W’(4) = (4 - 0) (4 - 2) = 8 5 2 1 L2(x) = x(x − 2)(x − 4)( − + ) 8(x − 0) (x − 2)(−4) (x − 4).8 1 5 2 1 = x(x − 2)(x − 4) + ( − + ) 8 4x (x − 2) 4(x − 4) 1 = (5(x − 2)(x − 4) + 4x(x − 4) + x(x − 2)) 8 1 1 = (10x 2 − 48x + 40) = (5x 2 − 24x + 20) 8 4 Cách 2: t(t −1)(t −2) 5C0 −2C1 1.C2 L (2t) = ( 2 − 2 + 2 ) 2 2! t −0 t −1 t −2 t(t −1)(t − 2) 5 4 1 = ( + + ) 2 t t −1 t − 2 1 2 = (5(t −1)(t−2)+4t(t −2)+t(t −1) 2 1 (10t 2 − 24t + 10) = 5t 2 − 12t + 5 = 2 5 2 Vậy L (x) = x −6x +5 2 4 7.4. Bảng nội suy Ayken 44
  45. Khi tính giá trị của hàm tại một điểm x=c nào đó bất kỳ mà không cần phải xác định biểu thức của f(x). Khi đó ta có thể áp dụng bảng nội suy Ayken như sau 7.4.1. Xây dựng bảng nội suy Ayken c-x0 x0-x1 x0-x2 x0-xn d1 d2 x1-x0 c-x1 x1-x2 x1-xn d3 x2-x0 x2-x1 c-x2 x2-xn xn-x0 xn-x1 xn-x2 c-xn dn W(c) = (c- x0)( c- x1) ( c- xn) : Tích các phần tử trên đường chéo W’(xi) = (xi - x0)( xi – x1) (xi - xi-1) (xi - xi+1) (xi - xn) (c - xi) W’(xi) = (xi - x0)( xi – x1) (xi - xi-1) (c- xi)(xi - xi+1) (xi - xn) di = (c-xi) W’(xi) : Tích các phần tử trên dòng i (i=0,1, ,n) n yi f(c) ≈ Ln(c) = W(c).∑ i=0 (c − xi )W'(xi ) n y i f(c) ≈ W(c) ∑ i = 0 d i Ví dụ 3. Tính f (3. 5) khi biết f(x) thoả mãn xi 1 2 3 4 5 yi 3 2 7 -1 0 Giải Xây dựng bảng nội suy Ayken 2.5 -1 -2 -3 -4 60 1 1.5 -1 -2 -3 -9 2 1 0.5 -1 -2 2 3 2 1 -0.5 -1 3 4 3 2 1 -1.5 -36 W(3.5) = 1.40625 45
  46. 1 2 7 1 f(3.5) ≈ L4 (3.5) = − + − 20 9 2 3 7.4.2. Thuật toán - Nhập: n, xi, yi (i = 0, n), c - w = 1; s = 0; - Lặp i = 0 → n { w = w*(c - xi) d = c - xi Lặp j = 0 → n Nếu j != i thì d = d * (xi - xj) s = s + yi/d } - Xuất kết quả: w * s 7.5. Bảng Nội suy Ayken (dạng 2) Xét hàm nội suy của 2 điểm: x0, x1 x − x 1 x − x 0 L01 = y 0 + y1 x 0 − x 1 x 1 − x 0 y0 (x1 −x) − y1(x0 −x) = x1 −x0 y0 x0-x = y1 x1-x x1-x0 Hàm nội suy của hai điểm x0, xi y0 x0-x L0i(x) = yi xi-x xi-x0 Xét hàm p(x) có dạng: L01(x) x1-x p(x) = L0i(x) xi-x xi - x1 46
  47. L01(x0) (xi – x0) - L0i(x0) (x1 – x0) y0(xi - x1) p(x0) = = = y0 xi - x1 xi - x1 y1 (xi - x1) P(x1) = = y1 xi - x1 -y1 (x1 - xi) P(xi) = = yi xi - x1 Vậy p(x) là hàm nội suy của 3 điểm x0, x1, xi Tổng quát: Hàm nội suy của n+1 điểm x0, x1, xn L012 n-2 n-1(x) xn-1-x L012 n(x) = L012 n-2 n(x) xn-x xn - xn-1 Bảng Nội suy Ayken (dạng 2) xi yi Loi(x) Lo1i(x) Lo12i(x) Lo12 n(x) xi - x x0 y0 x0 - x x1 y1 Lo1(x) x1 - x x2 y2 Lo2(x) Lo12(x) x2 - x x3 y3 Lo3(x) Lo13(x) Lo123(x) xn yn Lon(x) Lo1n(x) Lo12n(x) Lo12 n(x) xn - x Ví dụ 4. Cho f(x) thoả mãn: xi 1 2 3 4 5 yi 2 4 5 7 8 Tính f (2.5) 47
  48. Giải: Áp dụng bảng Ayken (dạng 2) xi yi Loi(x) Lo1i(x) Lo12ix Lo123ix xi - x 1 2 -1.5 2 4 5 -0.5 3 5 4.25 4.625 0.5 4 7 4.5 4.875 4.5 1.5 5 8 4.25 4.875 4.562 4.407 2.5 Vậy f(2.5) ≈ 4.407 Chú thích : L01(-2.5) = (2(-0.5) - 4(-1.5)) / (2-1) = 5 7.6. Nội suy Newton 7.6.1. Sai phân Cho hàm f(x) và h là hằng số, khi đó: ∆f(x) = f (x + h) - f(x) được gọI là sai phân cấp 1 đốI vớI bước h. ∆2f(x) = ∆[∆f(x)] : sai phân cấp 2 Tổng quát: ∆kf(x) = ∆[∆k-1 f(x)] : sai phân cấp k Cách lập bảng sai phân: 2 3 n xi f(xi) ∆f(xi) ∆ f(xi) ∆ f(xi) ∆ f(xi) x0 y0 x1 y1 ∆f(x0) 2 x2 y2 ∆f(x1) ∆ f(x0) 2 3 x3 y3 ∆f(x2) ∆ f(x1) ∆f (x0) n xn yn ∆f(xn-1) ∆ f(x0) 48
  49. 7.6.2. Công thức nội suy Newton Giả sử hàm f(x) nhận giá trị yi tại các mốc xi cách đều một khoảng h. Khi đó hàm nội suy Newton là một đa thức bậc n được xác định như sau: Ln(x) = Coϕ0(x) + C1ϕ1(x) + + Cnϕn(x) (*) Trong đó: ϕ0(x) = 1; x − x (x − x )( x − x ) ϕ ( x ) = 0 ; ϕ (x) = 0 1 ; 1 h 2 h 2 2! . (x − x0 )(x − x1) (x − xn−1) ϕ (x) = n hnn! Lớp các hàm ϕi(x) có tính chất sau: - ϕi(x0) = 0 ∀i = 1, n - ∆ϕk(x) = ϕk-1(x) * Xác định các hệ số Ci (i = 0, n ) Sai phân cấp 1 của Ln(x) : (1) ∆Ln(x) = C0∆ϕ0(x) + C1∆ϕ1(x) + C2∆ϕ2(x) + + Cn∆ϕn(x) = C1ϕ0(x) + C2ϕ1(x) + + Cnϕn-1(x) Sai phân cấp 2 của Ln(x) : 2 (2) ∆ Ln(x) = C1∆ϕ0(x) + C2∆ϕ1(x) + + Cn∆ϕn-1(x) = C2ϕ0(x) + C3ϕ1(x) + + Cnϕn-2(x) Sai phân cấp n của Ln(x) : n (n) ∆ Ln(x) = Cnϕ0(x) = Cn Thay x = x0 vào (*), (1), (2), , (n) ta được: 2 n C0 = Ln(x0) ; C1 = ∆Ln(x0) ; C2 = ∆ Ln(x0) ; ; Cn= ∆ Ln(x0) 49
  50. Vì Ln(x) ≈ f(x) nên: Ln(x0) ≈ f(x0) ; ∆Ln(x0) ≈ ∆f(x0) ; 2 2 n n ∆ Ln(x0) ≈ ∆ f(x0) ; ; ∆ Ln(x0) ≈ ∆ f(x0) Vậy : x − x (x − x )(x − x ) L (x) ≈ f (x ) + ∆f (x ) 0 + ∆2f (x ) 0 1 n 0 0 h 0 2 h 2! (x − x )(x − x ) ( x − x ) + + ∆n f (x ) 0 1 n−1 0 h n n! Ví dụ 5. Xây dựng hàm nội suy Newton thoả mãn: xi 1 2 3 4 5 yi 2 4 5 7 8 Giải Lập bảng sai phân: 2 3 4 xi f(xi) ∆f(xi) ∆ f(xi) ∆ f(xi) ∆ f(xi) 1 2 2 4 2 3 5 1 -1 4 7 2 1 2 5 8 1 -1 -2 -4 Hàm nội suy Newton: x − x (x − x )(x − x ) (x − x )(x − x )(x − x ) L (x) ≈ 2 + 2 0 − 0 1 + 2 0 1 2 n 1 2! 3! (x − x )(x − x )(x − x )(x − x ) − 4 0 1 2 3 4! 50
  51. 7.7. Nội suy tổng quát (Nội suy Hecmit) Xây dựng hàm nội suy của f(x) thoả mãn giá trị hàm và giá trị đạo hàm các cấp theo bảng giá trị sau: xi x0 x1 xn yi =f(xi) y0 y1 yn y'i=f’(xi) y'0 y'1 y'n yi'’= f’’(xi) y''0 y’’1 y’’n (k) (k) (k) (k) (k) yi =f (xi) y1 y2 yn Giả sử hàm nội suy cần tìm là đa thức bậc m: Hm(x) k m = n + ∑ s i (Si : số giả thiết được cho ở đạo hàm cấp i ) i=1 Hm(x) = Ln(x) + W(x) Hp(x) ( Vì Hm(xi) = Ln(xi) + W(xi) Hp(xi) = yi ) Với: W(x) = (x-x0) * (x-x1)* *(x-xn) p= m - (n + 1) Đạo hàm cấp 1: H’m(x) = Ln’(x) + W(x) H’p(x) + W’(x)Hp(x) Xét tại các điểm xi: Hm(xi) = Ln’(xi) + 2W(xi) H’p(xi) + W’(xi)Hp(xi) = yi 0 => Hp(xi) Đạo hàm cấp 2: H”m(x) = Ln’’(x) + 2W’(x) H’p(x) + W’’(x) Hp(x) + W(x)Hp”(x) 51
  52. Xét tại các điểm xi: ’’ H”m(xi) = Ln’’(xi) + 2W’(xi) H’p(xi) + W’’(xi) Hp(xi) + W(xi)Hp”(xi) =yi 0 => Hp’(xi) (k-1) Tương tự: Đạo hàm đến cấp k suy ra Hp (xi) Ta xác định hàm Hp(x) thoả mãn: xi x0 x1 xn Hp(xi) h0 h1 hn Hp’(xi) h'0 h'1 h'n (k-1) (k-1) (k-1) (k-1) Hp (xi) h0 h1 hn Về bản chất, bài toán tìm hàm Hp(x) hoàn toàn giống bài toán tìm hàm Hm(x). Tuy nhiên ở đây bậc của nó giảm đi (n+1) và giả thiết về đạo hàm giảm đi một cấp. Tiếp tục giải tương tự như trên, cuối cùng đưa về bài toán tìm hàm nộI suy Lagrange (không còn đạo hàm). Sau đó thay ngược kết quả ta được hàm nội suy Hecmit cần tìm Hm(x). Ví dụ 6. Tìm hàm nội suy của hàm f(x) thoả mãn: xi 0 1 3 f(xi) 4 2 0 f’(xi) 5 -3 Giải: Hàm nội suy cần tìm là đa thức H4(x) H4(x) = L2(x) + W(x) H1(x) 52
  53. W(x) = x(x-1)(x-3) =x3 – 4x2 +3x 4(x − 1)( x − 3) x(x − 3) L (x) = + 2 2 3 − 2 1 2 = (x − 7x +12) 3 2 7 H ' ( x ) = x − + (3x 2 − 8 x + 3)H ( x ) + W(x)H' ( x ) 4 3 3 1 1 7 22 H ' (0) = − x + 3H (0) = 5 => H (0) = 4 3 1 1 9 5 2 H ' (1) = − x − 2 H (1) = - 3 => H (1) = 4 3 1 1 3 Tìm hàm H1(x) thoả mãn: xi 0 1 H1(xi) 22/9 2/3 22 (x −1) 2 (x −1) −16x + 22 H1(x) = + = 9 (0 −1) 3 (1− 0) 9 2 Vậy H4(x) =(x –7x +12)/3 + x(x-1)(x-3)(-16x +22)/9 7.8. Phương pháp bình phương bé nhất Giả sử có 2 đại lượng (vật lý, hoá học, ) x và y có liên hệ phụ thuộc nhau theo một trong các dạng đã biết sau: - y = fax + b - y = a + bx + cx2 Tuyến tính - y = a + bcosx + csinx - y = aebx Phi tuyến tính - y = axb 53
  54. nhưng chưa xác định được giá trị của các tham số a, b, c. Để xác định được các tham số này, ta tìm cách tính một số cặp giá trị tương ứng (xi, yi), i=1, 2, ,n bằng thực nghiệm, sau đó áp dụng phương pháp bình phương bé nhất. * Trường hợp: y = ax + b Gọi εi sai số tại các điểm xi εi = yi - a - bxi n 2 Khi đó tổng bình phương các sai số: S = ∑ ε i i =1 Mục đích của phương pháp này là xác định a, b sao cho S là bé nhất. Như vậy a, b là nghiệm hệ phương trình: ∂S = 0 ∂a 1 ∂S = 0 ∂b 2 2 2 2 Ta có: S = Σ(yi + a + b xi - 2ayi - 2bxiyi + 2abxi) ∂S n = ∑(2a − 2yi + 2bxi ) ∂a i=1 n ∂S 2 = ∑(2bxi − 2xi yi + 2axi ) ∂b i=1 n n na + b∑ x i = ∑ y i 1 ⇔ i=1 i=1 n n n 2 a∑xi + b∑xi =∑xiyi i=1 i=1 i=1 Giải hệ phương trình ta được: a, b * Trường hợp y = a + bx + cx2 Gọi εi sai số tại các điểm xi 2 εi = yi - a - bxi - cxi 54
  55. n 2 Khi đó tổng bình phương các sai số: S = ∑ ε i i =1 Các hệ số a, b xác định sao cho S là bé nhất. Như vậy a, b, c là nghiệm của hệ phương trình: n n n ∂S 2 = 0 na + b ∑ x i + c ∑ x i = ∑ y i ∂a i = 1 i = 1 i = 1 n n n n ∂S 2 3 = 0 ⇔ a ∑ x i + b∑ x i + c∑ x i = ∑ x i y i ∂a i =1 i =1 i =1 i =1 n n n n ∂S 2 3 2 = 0 a ∑ x i + b∑ x i + c∑ x i 4 = ∑ x i y i ∂c i =1 i =1 i =1 i =1 Giải hệ phương trình ta được a, b, c * Trường hợp: y = aebx Lấy Logarit cơ số e hai vế: Lny = lna + bx Đặt Y = lny; A = lna; B = b; X = x Ta đưa về dạng: Y = A + BX Giải hệ phương trình ta được A, B => a = eA, b=B * Trường hợp y = axb Lấy Logarit cơ số 10 hai vế: Lgy = lga + blgx Đặt Y = lgy; A = lga; B = b; X = lgx Ta đưa về dạng: Y = A + BX Giải hệ phương trình ta được A, B => a = 10A, b=B Ví dụ 7. Cho biết các cặp giá trị của x và y theo bảng sau: xi 0.65 0.75 0.85 0.95 1.15 yi 0.96 1.06 1.17 1.29 1.58 Lập công thức thực nghiệm của y dạng aebx 55
  56. Giải Ta có: y = aebx Lấy Logarit cơ số e hai vế: Lny = lna + bx Đặt Y = lny; A = lna; B = b; X = x Ta đưa về dạng: Y = A + BX Xi = xi 0.65 0.75 0.85 0.95 1.15 Yi = lnyi -0.04 0.06 0.18 0.25 0.46 2 ΣXi ΣXi ΣXiYi ΣYi 4.35 3.93 0.92 0.89 Phương pháp bình phương bé nhất: A, B là nghiệm hệ phương trình n n nA + B ∑ X i = ∑ Y i i = 1 i = 1 n n n 2 A∑ X i + B∑ X i =∑ X iYi i=1 i=1 i =1 5A + 4.35B =0.89 4.35A + 3.93B = 0.92 Giải hệ phương trình ta được: A = -.069, B = 1 Suy ra: a = eA = ½, b = B =1 1 Vậy f(x) = e x 2 56
  57. CHƯƠNG VIII TÍNH GẦN ĐÚNG TÍCH PHÂN XÁC ĐỊNH 8.1. Giới thiệu Xét hàm số f(x) liên tục trên [a,b], nếu xác định được nguyên hàm F(x) ta có công thức tính tích phân: b ∫ f (x)dx = F(b) − F(a) a Nhưng trong đa số các trường hợp ta không xác định được nguyên hàm của, hoặc không xác định được biểu thức của f(x) mà chỉ nhận được các giá trị của nó tạI nhưng điểm rời rạc. Trong trường hợp như vậy ta có thể sử dụng các công thức gần đúng sau để tính tích phân: - Công thức hình thang. - Công thức Parabol - Công thức Newton _Cotet 8.2. Công thức hình thang Chia [a, b] thành n đoạn bằng nhau với khoảng cách h = (b - a)/n theo các điểm chia: x0=a, x1=a+h, , xn = b b x 1 x 2 x n ∫∫∫f (x )dx = ∫ f (x )dx + f (x )dx + + f (x )dx = S a x x x 0 = a 1 n −1 S là diện tích giới hạn bởi đường cong f(x), x=a, x=b, và trục x S 1 f(x) S Sn x0 =a x1 xn-1 xn = b Xét trên [x0, x1], ta xem đường cong f(x) là đường thẳng 57
  58. 1 S ≈ S = h(y + y ) 1 hthang 2 0 1 Tương tự: 1 S ≈ h ( y + y ) 2 2 1 2 1 S ≈ h(y + y ) n 2 n−1 n b h Vậy: ∫ f (x )dx ≈ ( y 0 + 2 y1 + 2 y 2 + + 2 y n −1 + y n ) a 2 8.3. Công thức Parabol Chia [a, b] thành 2n đoạn bằng nhau với khoảng cách h = (b - a)/2n theo các điểm chia: x0=a, x1=a+h, , x2n = b b x 2 x 4 x 2n ∫∫f (x)dx = ∫ f (x)dx + ∫ f (x)dx + + f (x)dx a x 0 x 2 x 2n −2 Xét trên [x0, x2] xem đường cong f(x) là Parabol (nội suy bậc 2 của 3 điểm x0, x1, x2) (x − x )(x − x ) (x − x )(x − x ) f (x) ≈ L (x) = y 1 2 + y 0 2 + 2 0 (x − x )(x − x ) 1 (x − x )(x − x ) 0 1 0 2 1 0 1 2 (x − x 0 )(x − x1) + y2 (x 2 − x 0 )(x 2 − x1) x2 x2 ∫∫f (x)dx ≈ L2 (x)dx x0 x0 Thay x0 = a, x1 = a + h , x2 = a+2h vào, ta có: x2 h f (x)dx ≈ (y + 4y + y ) ∫ 3 0 1 2 x0 Tương tự: 58
  59. x4 h f (x)dx ≈ (y + 4y + y ) ∫ 3 2 3 4 x2 x2n h f (x)dx ≈ (y + 4y + y ) ∫ 3 2n−2 2n−1 2 x2n−2 b h Vậy: ∫f (x)dx ≈ (y0 + 4y1 + 2y2 + + 2y2n−2 + 4y2n−1 + y2n ) a 3 5 Ví dụ. Tính J = dx theo 3 cách ∫ 2 1 1+ x Giải 5 Cách 1: J =arctgx 1 = arctg5 − Π / 4 ≈ 0.588 Cách 2: chia [1, 5] thành 4 đoạn bằng nhau (h=1) với các điểm chia xi 1 2 3 4 5 yi 1/2 1/5 1/10 1/17 1/26 Công thức hình thang: J ≈ (1/2 + 2/5 +2/10 +2/17 + 1/26) /2 ≈ 0.628 Cách 3: Công thức Parabol: J ≈ (1/2 + 4/5 +2/10 +4/17 + 1/26) /3 ≈ 0.591 8.4. Công thức Newton-Cotet Chia [a, b] thành n đoạn bằng nhau với khoảng cách h = (b - a)/n với x0=a; x1 = a + h , , xn = b. Đặt x = a + (b - a)t => dx = (b - a) dt xi a a+h a + 2h b ti 0 1/n 2/n 1 Khi đó: b 1 1 ∫∫f (x)dx = (b − a) f (a + (b − a)t)dt = (b − a) ∫Φ(t)dt a 0 0 Với φ(t)= f(a + (b - a)t Xem φ(t) là hàm nội suy Lagrange của n + 1 điểm: t0, t1, , tn 59
  60. 1 2 2 (t − )(t − ) (t −1) (t − 0)(t − ) (t −1) Φ(t) ≈ L (t) = y n n + y n + n 0 1 2 1 1 1 2 1 (− )(− ) (−1) ( − 0)( − ) ( −1) n n n n n n 1 n −1 (t − 0)(t − ) (t − ) + y n n n 1 n −1 (1− 0)(1− ) (1− ) n n 1 1 Khi đó: ∫∫Φ(t)dt ≈ Ln (t)dt 0 0 1 i −1 i +1 1 (t − 0)(t − ) (t − )(t − ) (t −1) Đặt Pi = n n n dt n ∫ i i 1 i i −1 i i +1 i 0 ( − 0)( − ) ( − )( − ) ( −1) n n n n n n n n b n i Vậy: ∫ f (x)dx ≈ (b − a)∑ yi pn a i=0 Xét n = 1 ( h = b-a ) 1 1 0 t −1 1 1 t − 0 1 P1 = ∫ dt = − ; P1 = ∫ dt = 0 0 −1 2 0 1− 0 2 b y0 y1 h ∫ f (x)dx = (b − a)( + ) = (y0 + y1 ) → Công thức hình thang a 2 2 2 i Lưu ý: Giá trị của Pn có thể tra trong bảng sau: i n Pn 1 1/2 1/2 2 1/6 4/6 1/6 3 1/8 3/8 3/8 1/8 4 9/71 16/45 2/15 16/45 9/70 5 19/288 25/95 25/144 25/144 25/95 19/288 60
  61. BÀI TẬP 1. Khai báo (định nghĩa) hàm trong C để tính gần đúng tích phân xác định của f(x) tr ên [a, b] (đối kiểu con trỏ hàm) a. Dùng công thức hình thang b. Dùng công thức Parabol c. Dùng công thức Newton-cotet 2. Viết chương trình tính gần đúng tích phân xác định trên [a, b] của 1 hàm f(x) cụ thể (sử dụng các hàm đã khai báo trong câu 1). So sánh kết quả, nhận xét. 61
  62. MỘT SỐ CHƯƠNG TRÌNH THAM KHẢO 1. Tính gần đúng tích phân xác định # include # include "conio.h" # include "math.h" # define PI 3.14159 float d[10];int n; double g(double x) { return 1/(1+x*x); } double tp(double (*f)(double),float a,float b) { int n=100,i; float s,h=(b-a)/n; s=(f(a)+f(b))/2; for (i=1; i<n;i++) s+=f(a+i*h); return s*h; } void nhap(float *a, int *n) { int i; printf("\n Nhap bac da thuc: ");scanf("%d",n); printf("\n Nhap he so cua ham da thuc:\n"); for (i=0;i<=*n; ++i) { printf(" a[%d]=",i); scanf("%f",a+i); } } double f(double x) { float p=d[0]; int i; for(i=1;i<=n;i++) p=p*x+d[i]; return p; } main() { float a,b; char tt; 62
  63. while (1) { printf("\n Nhap can de tinh tich phan: "); scanf("%f%f",&a,&b); /*printf("a= "); scanf("%f",&a); printf("b= "); scanf("%f",&b);*/ printf("\nS1=%.3f",tp(sin,0,PI)); printf("\nS2=%.3f",tp(cos,0,PI/2)); printf("\nS3=%.3f",tp(g,a,b)); nhap(d,&n); printf("\nS4=%.3f",tp(f,a,b)); printf("\n\n Ban tiep tuc ko(c/k)?"); tt=getch(); if (tt!='c') break; } } 2. Tim nghiem gan dung cua phtrinh da thuc bac n bang PP chia doi # include # include "conio.h" # include "math.h" # define eps 1e-3 float f(float); void nhap(float *, int ); float d[10]; int n; void main() { float a,b,c; char tt; while (1) { printf("\n Nhap bac phuong trinh: ");scanf("%d",&n); nhap(d,n); printf("\n Nhap khoang nghiem: "); scanf("%f%f",&a,&b); /* printf("a= "); scanf("%f",&a); printf("b= "); scanf("%f",&b);*/ if (f(a)*f(b) = 1e-3 && f(c)!=0) { printf("\n%.3f %.3f %.3f",a,b,f(c)); if (f(b)*f(c)>0) b=c; else a=c; c=(a+b)/2; 63
  64. } printf("\n\n Nghiem phtrinh: %.3f",c); } else if (f(a)*f(b)>0) printf(" ( %f, %f) khong phai la khoang nghiem",a,b); else if (f(a)==0) printf(" \n Nghiem phtrinh: %.3f",a); else printf(" \n Nghiem phtrinh: %.3f",b); printf("\n\n Ban tiep tuc ko(c/k)?"); tt=getch(); if (tt!='c') break;} } void nhap(float *a, int n) { int i; printf("\n Nhap he so cua phuong trinh:\n"); for (i=0;i<=n; ++i) { printf(" a[%d]=",i); scanf("%f",a+i); } } /* ham tinh gia tri da thuc*/ float f(float x) { float p=d[0]; int i; for(i=1;i<=n;i++) p=p*x+d[i]; return p; } 3. PP tiếp tuyến # include "conio.h" # include "math.h" # define eps 1e-3 float f(float x); float fdh(float x); main() { float a,b; char tt; while (1) { printf("\nNhap xap xi ban dau: "); scanf("%f",&a); /*b=a-f(a)/fdh(a); 64
  65. printf("\n%.3f %.3f %f",a,-f(a)/fdh(a),b);*/ do { b=a; a=b-f(b)/fdh(b); printf("\n%.3f %.3f %f",b,-f(b)/fdh(b),a); } while (fabs(a-b) >= 1e-3 ); printf("\nNghiem phtrinh: %.3f",a); printf("\nTiep tuc ko(c/k)?"); tt=getch(); if (tt=='k' || tt=='K') break;} } float f(float x) { return exp(x)-10*x+7; } float fdh(float x) { return exp(x)-10; } 4. Giải hệ phtrình đại số tuyến tính bằng PP Gauss # include # include "conio.h" # include "math.h" void nhap(float *a, int n,int m); void xuatmt(float *a, int n,int m); main() { float a[10][10]; float x[10],m,s; char tt; int n,i,j,k; while (1) { printf("\n Nhap n= "); scanf("%d",&n); printf("\n Nhap he so cua he phuong trinh:\n"); for (i=1;i<=n; ++i) for (j=1;j<=n+1;++j) { printf(" pt[%d%d]=",i,j); scanf("%f",&m); a[i][j]=m; } 65
  66. for (i=1;i =1;i ) { s=a[i][n+1]; for(k=i+1;k<=n;k++) s-=a[i][k]*x[k]; x[i]=s/a[i][i]; } printf("\nNghiem he phtrinh:"); for(i=1;i<=n;i++) printf("%.3f ",x[i]); printf("\n\n Ban tiep tuc ko(c/k)?"); tt=getch(); if (tt!='c') break;} } /* Ham nhap mang a(m,n)*/ void nhap(float *a, int n,int m) { int i,j; printf("\n Nhap he so cua he phuong trinh:\n"); for (i=1;i<=m; i++) for (j=1;j<=n;j++) { printf(" pt[%d%d]=",i,j); scanf("%f",a+i*n+j); } } /* Ham xuat mang a(m,n)*/ void xuatmt(float *a, int n,int m) { int i,j; 66
  67. for (i=1;i<=m; i++) { printf("\n"); for (j=1;j<=n;j++) printf("%.3f ",*(a+i*n+j)); } } 67
  68. TÀI LI ỆU THAM KHẢO [1] Đặng Quốc Lương, Phương pháp tính trong kỹ thuật, Nhà xuất bản xây dựng Hà nội, 2001 [2] Phan Văn Hạp, Giáo trình Cơ sở phương pháp tính tập I,II. Trường ĐH Tổng hợp Hà nội, 1990 [3] Cao quyết Thắng, Phương pháp tính và Lập trình Turbo Pascal. Nhà XB giáo dục, 1998 [4] Tạ Văn Đĩnh, Phương pháp tính. Nhà XB giáo dục, 1994 [5] Dương Thủy Vỹ, Phương pháp tính. Nhà XB khoa học & kỹ thuật, 2001 [6] Phan Văn Hạp, Bài tập phương pháp tính và lập chương trình cho máy tính điện tử. Nhà XB đại học và trung học chuyên nghiệp, 1978 [7] Ralston A, A first course in numberical analysis. McGraw – Hill, NewYork, 1965 68