Giải gần đúng nghiệm của hệ phương trình tuyến tính và các phương pháp nội suy hàm số bằng ngôn ngữ C

Đồ án Toán 1 1 TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM TRƢỜNG ĐẠI HỌC TÔN ĐỨC THẮNG KHOA TOÁN – THỐNG KÊ ĐỒ ÁN TOÁN 1 TÊN ĐỀ TÀI: - GIẢI GẦN ĐÚNG NGHIỆM CỦA HỆ PHƢƠNG TRÌNH TUYẾN TÍNH VÀ CÁC PHƢƠNG PHÁP NỘI SUY HÀM SỐ BẰNG NGÔN NGỮ C++ Giảng viên hƣớng dẫn: ThS. LÊ TRUNG NGHĨA Sinh viên thực hiện: ĐẶNG NGỌC ĐỨC MS: C1201002 PHẠM THANH TÂM MS: C1201104 LỚP: 120C0101 LỚP: 120C0101 NIÊN KHÓA: 2012 - 2016 TP. Hồ Chí Minh, tháng 11 năm 2014 Đồ án Toán 1 2 TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM TRƢỜNG ĐẠI HỌC TÔN ĐỨC THẮNG KHOA TOÁN – THỐNG KÊ ĐỒ ÁN TOÁN 1 TÊN ĐỀ TÀI - GIẢI GẦN ĐÚNG NGHIỆM HỆ PHƢƠNG TRÌNH TUYẾN TÍNH VÀ CÁC PHƢƠNG PHÁP NỘI SUY HÀM SỐ BẰNG NGÔN NGỬ C++ Giảng viên hƣớngdẫn: ThS. LÊ TRUNG NGHĨA Sinh viên thực hiện: ĐẶNG NGỌC ĐỨC MS: C1201002 PHẠM THANH TÂM MS: C1201104 LỚP: 120C0101 LỚP: 120C0101 NIÊN KHÓA: 2012 - 2016 TP. Hồ Chí Minh, tháng 11 năm 2014 Đồ án Toán 1 3 NHẬN XÉT CỦA GIẢNG VIÊN HƢỚNG DẪN ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... Đồ án Toán 1 4 LỜI CẢM ƠN Trong quá trình thực hiện đề tài đồ án này chúng em nhận đƣợc nhiều sự giúp đỡ từ các thầy cô trong khoa Toán – Thống kê, Trƣờng Đại học Tôn Đức Thắng. Các thầy cô đã hƣớng dẫn tận tình chỉ bảo những kinh nghiệm quý báu. Trong quá trình học tập chúng em cũng đã không ngừng học tập, cùng với sự giúp đỡ của bạn bè vì đó mà chúng em đã hoàn thành đề tài đồ án nhƣ mong muốn này. Nay chúng em xin đƣợc gởi lời cảm ơn đến các thầy cô đặc biệt là thầy Lê Trung Nghĩa - ngƣời đã hƣớng dẫn tận tình, tạo điều kiện tốt nhất cho chúng em để có thể hoàn thành tốt cuốn báo cáo này. Nhóm chúng em cũng xin đƣợc gởi lời cảm ơn đến gia đình và bạn bè đã động viên khuyến khích trong những lúc khó khăn nhất. Một lần nữa chúng em xin chân thành cảm ơn! Chúc tất cả mọi ngƣời sức khỏe và thành công! Đồ án Toán 1 5 LỜI NÓI ĐẦU Trong cuốn báo cáo này, chúng em xin trình bày hai phần: Phần 1: Đối với một hệ phƣơng trình, chúng ta luôn có cách giải tìm ra nghiệm chính xác của nó. Ngƣời ta xây dựng cách tính nghiệm chính xác thông qua công thức Cramer. Tuy nhiên khi gặp một hệ phƣơng trình có số ẩn lớn thì việc áp dụng công thức Cramer không còn đơn giản. Để giải quyết vấn đề này ngƣời ta xây dựng công thức khác là Gauss và phƣơng pháp lặp Seidel. Phƣơng pháp này làm giảm đƣợc số lƣợng phép tính đáng kể so với phƣơng pháp Cramer với độ chính xác theo mức độ từ thấp đến cao. Vì vậy trong phần này, chúng em trình bày nội dung của “GIẢI GẦN ĐÚNG HỆ PHƢƠNG TRÌNH TUYẾN TÍNH BẰNG CÁC PHƢƠNG PHÁP GAUSS, LẶP SEIDEL”. Phần 2: 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ủa các hàm 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 giá trị của f(xi) rời rạc tại các điểm nút xi tƣơng ứng. Vấn đề đặt ra là làm sao ta đi tính đƣợc các giá trị của hàm f(x) tại các điểm còn lại. Để giải quyết vấn đề này ngƣời ta đã xây dựng một hàm φ(xi) = yi = f(xi) với ( i = 0,1,,n ) φ(x) ≈ f(x) với mọi x ϵ [a;b] và x ≠ xi. ta xây dựng hàm φ(x) gọi là bài toán nội suy. Ngoài ra phƣơng pháp bình phƣơng tối thiểu đƣợc dùng để lặp các công thức thực nghiệm. Khi tìm mối liên hệ giữa hai đại lƣợng x và y phải tiến hành thí nghiệm rồi quan sát, đo đạc. Rồi dựa vào dữ liệu thu đƣợc, ta lập mối liên hệ hàm số y = f(x) cụ thể gọi là lập công thức thực nghiệm. Nói chung việc tìm ra hàm f(x) là gần đúng. Việc tìm ra hàm số xấp xỉ của hàm số f(x) bằng phƣơng pháp bình phƣơng nhỏ nhất sẽ rất phức tạp nếu ta không biết đƣợc dạng của hàm số xấp xỉ. Trong phần này chúng em trình bày dung nội dung “NỘI SUY LAGRANGE, NEWTON VÀ PHƢƠNG PHÁP BÌNH PHƢƠNG NHỎ NHẤT”. Cách để tìm ra nghiệm xấp xỉ của các phƣơng trình hay hàm số có rất nhiều. Chúng em chỉ liệt kê một số phƣơng pháp thông dụng có ứng dụng thực tế. Đồ án Toán 1 6 MỤC LỤC Trang PHẦN 1: TÌM NGHIỆM CỦA HỆ PHƢƠNG TRÌNH TUYẾN TÍNH 1. Giới thiệu chung 7 2. Phƣơng pháp Cramer 7 3. Phƣơng pháp Gauss 8 3.1. Nội dung phƣơng pháp 8 3.2. Thuật toán 9 3.3. Code chƣơng trình 10 4. Phƣơng pháp Lặp Seidel 12 4.1. Nội dung phƣơng pháp 12 4.2. Thuật toán 15 4.3. Code chƣơng trình 16 PHẦN 2: NỘI SUY VÀ LẤY XẤP XỈ HÀM SỐ 19 1. Giới thiệu chung về phƣơng pháp 19 2. Nội suy Lagrange 20 2.1. Đa thức nội suy Lagrange 20 2.2. Thuật toán 22 2.3. Code chƣơng trình 23 3. Nội suy Newton 24 3.1. Đa thức nội suy Newton 24 3.2. Thuật toán 30 3.3. Code chƣơng trình 31 4. Phƣơng pháp bình phƣơng nhỏ nhất – Lấy xấp xỉ hàm số 32 4.1. Nội dung phƣơng pháp và các dạng thƣơng gặp 32 4.2. Thuật toán 41 4.3. Code chƣơng trình 43 KẾT LUẬN 46 TÀI LIỆU THAM KHẢO 47 Đồ án Toán 1 7 PHẦN 1: TÌM NGHIỆM CỦA HỆ PHƢƠNG TRÌNH TUYẾN TÍNH 1. Giới thiệu chung. Cho hệ phƣơng trình tuyến tính: { (1) Hệ phƣơng trình trên có thể đƣợc cho bởi ma trận: ( ) (2) Vấn đề đặt ra là tìm nghiệm ⃗ = ( x1 , x2, ..., xn ) - Phƣơng pháp đúng (Cramer, 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 quy 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. 2. Phƣơng pháp Cramer. Sự tồn tại và nghiệm duy nhất của hệ: ∆ = det(A)s Nếu ∆ = 0 thì ma trận A suy biến do đó hệ (1) suy biến. suy ra từ ∆: Bằng cách thay cột thứ i bằng cột ở vế phải. Định lý Cramer : Nếu ∆ ≠ 0 thì hệ (1) không suy biến và có nghiệm duy nhất được tính bởi công thức: (3) Nhận xét: Công thức thu gọn dể nhớ, đẹp. Tuy nhiên khi n đủ lớn phải thực hiện số lƣợng lớn các phép tính. Việc tính các định thức sẽ gặp nhiều khó khăn. Nc(n) – số lƣợng phép tính cần làm khi hệ có n phƣơng trình. Nc(n) = (n +1)!n Với n = 15 ta có Nc(15) = 3.10 14 . Đồ án Toán 1 8 3. Phƣơng pháp Gauss. 3.1. Nội dung phƣơng pháp Nội dung khử dần các ẩn về hệ tƣơng đƣơng có dạng tam giác trên rồi giải từ dƣới lên mà không phải tính định thức. Ví dụ: Xét hệ phƣơng trình sau: (4) Khử các ẩn → (5) Giải ngƣợc từ dƣới lên → tìm đƣợc các ẩn. Quá trình (4) → (5): sử dụng các phép biến đổi sơ cấp trên dòng của ma trận. Quá trình (5): quá trình ngƣợc. Khối lƣợng phép tính Nc(n) = Với n = 15 ta có Nc(15) = 2570 nhỏ hơn nhiều so với phƣơng pháp Cramer. Ví dụ: Giải hệ phƣơng trình { Giải: Ta đƣa hệ phƣơng trình về ma trận: ( ) Ta dùng các phép biến đổi sơ cấp trên dòng của ma trận đƣa ma trận về dạng bậc thang: ( ) → ( ) → Đồ án Toán 1 9 ( ) → ( ) → ( ) → ( ) Vậy hệ phƣơng trình đả cho tƣơng đƣơng với hệ sau: { { Vậy hệ có nghiệm duy nhất là: x* = ( 2 ; 1 ; 5 ; -3) 3.2. Thuật toán: Bước 1: - Nhập số liệu. - Nhập vào số ẩn. - Nhập các phần tử của ma trận hệ số mở rộng. Bước 2: - Biến đổi ma trận về dạng tam giác trên. - Kiểm tra phần tử aii + Nếu aii = 0 thì hoán đỗi dòng i. + Nếu aii khác 0 thì ta tìm đƣợc hệ số khử.  Thực hiện vòng lặp cho i chạy từ 1 đến n (số dòng).  Thực hiện vòng lặp cho j chạy từ i+1 đến n+1(số cột). Đặt c = (hệ số khử) Lặp cho k chạy từ i đến n+1: aj,k=c*ai,k+aj,k Bước 3: - Tìm nghiệm theo quy trình ngƣợc. ∑ - s=0. Đồ án Toán 1 10 - Vòng lặp j=i+1n. s=s+ aij*xj. (số nghiệm luôn <= số ẩn) - In ra nghiệm xi 3.3. Code chƣơng trình : Đồ án Toán 1 11 Đồ án Toán 1 12 4. Phƣơng pháp Lặp Seidel. 4.1. Nội dung phƣơng pháp - Cho hệ phƣơng trình: Ax = f (6) Biến đổi về dạng tƣơng đƣơng: x = Bx + g (7) B ( ) suy ra từ A và g suy ra từ f (8) - Chọn x(0) nào đó làm nghiệm gần đúng đầu tiên của phƣơng trình và tính các nghiệm gần đúng tiếp theo: x(1), x(2),, x(m) theo phƣơng pháp lặp đơn: x (m) = Bx (m-1) + g ; (m>=1) (9) Với x(0) cho trƣớc. (10) Trong đó: (Bx)i = ∑ (11) Phƣơng pháp tính x(m) theo (9) gọi là phương pháp lặp đơn trong đó: B là ma trận lặp. Đồ án Toán 1 13 Sự hội tụ và sai số của phƣơng pháp Định nghĩa sự hôi tụ Giả sử là nghiệm của hệ phƣơng trình (1) tức (6) nếu xi (m) → khi m →∞; i = 1, 2,..., n → phƣơng pháp lặp hội tụ. Định lý về sự hội tụ của phƣơng pháp lặp đơn Đối với ma trận B nếu chuẩn hàng: r0 = max{∑ | | ∑ | | ∑ | | } (12) hoặc chuẩn cột: r1 = max{∑ | | ∑ | | ∑ | | } (13) hoặc chuẩn Ơclit: r2 = (∑ ∑ | | ) ⁄ (14) Khi đó (9), (10) sẽ hội tụ bất kì đầu x(0) nào và sai số đƣợc đánh giá: ‖ ‖ ‖ ‖ ; (15) - r0< 1 → p =0; ‖ ‖ {| |}, - r1< 1 → p =1; ‖ ‖ ∑ | | - r2< 1 → p =2; ‖ ‖ ∑ ⁄ Các bƣớc tính: 1. Cho hệ phƣơng trình Ax= f. 2. Ẩn định sai số cho phép ε. 3. Ax = f → x = Bx + g. 4. Kiểm tra thỏa mãn điều kiện hội tụ (12), (13), (14). 5. Chọn x(0) tùy ý (là vecto không hay là g). 6. Tính x(m+1) = Bx(m) + g, với m = 1, 2, 3, cho tới khi ‖ ‖ → x(m) ≈ α 7. Sai số: ‖ ‖ Đồ án Toán 1 14 Ví dụ: Xét hệ phƣơng trình sau: { Tìm nghiệm gần đúng với độ chính xác ε = 1.10-3 bằng phƣơng pháp lặp đơn. Giải: Ta đƣa hệ phƣơng trình về dạng x = Bx + g { Ma trận B có đƣợc là: B = ( ) và g =( ) Kiểm tra điều kiện hội tụ (12), (13), (14). ∑| | ∑| | ∑| | Chọn phƣơng pháp lặp hội tụ với mọi x(0) cho trƣớc. Chọn x(0) = ( ) kết quả tính đƣợc cho trong bảng sau: m x1 (m) Δx1 x2 (m) Δx2 x3 (m) Δx3 0 1 2 3 4 0 2 1,92 1,9094 1,90923 2 0,08 0,0106 0,00017 0 3 3,19 3,1944 3,19495 3 0,19 0,0044 0,00055 0 5 5,04 5,0446 5,04480 5 0,04 0,0046 0,0002 Ta nhận xét rằng với m = 4 thì | | ;| | | | Đồ án Toán 1 15 max{| |} thỏa đề bài ta dừng quá trình tính. Sai số: ‖ ‖ = Vậy kết luận: { 4.2. Thuật toán Bước 1:  Nhập dữ liệu.  Nhập ma trận hệ số của hệ phƣơng trình (ma trận A).  Kiểm tra dữ liệu vừa nhập.  Nhập cột hệ số tự do (ma trận B).  Kiểm tra dữ liệu vừa nhập.  Nhập số lần lặp. Bước 2:  Chọn nghiệm ban đầu x=(0, 0,..., 0)  Để xi = 0. Dùng vòng lặp (for) cho i chạy 1n. Quá trình lặp: Sử dụng vòng lặp do {} while (...) (lặp cho đến khi thỏa không điều kiện thì dừng).  Các lệnh trong vòng lặp do {} while (): Dùng vòng lặp for cho i = 1n. { Đặt S = 0; Dùng vòng lặp for cho j = 1n S = S + aij*xj Đặt d = xi Xi= (-S + aii *d + bi )/aii Denta=|d-xi| } Vòng lặp do {...} while (...) dừng khi số lần lặp lớn hơn số lần quy định và khi Denta ≥ 0. Có hai khả năng sảy ra khi vòng lặp do {...} while (...) dừng là Đồ án Toán 1 16 Nếu Denta < 0 thì nghiệm đạt độ chính xác trong số lần lặp đã cho trƣớc. Nếu Denta = 0 thì nghiệm không đạt độ chính xác sau số lần lặp cho trƣớc. Bước 3: Xuất nghiệm. 4.3. Code chƣơng trình Đồ án Toán 1 17 Đồ án Toán 1 18 Đồ án Toán 1 19 PHẦN 2: NỘI SUY VÀ LẤY XẤP XỈ HÀM SỐ 1. Giới thiệu chung về phƣơng pháp. 1.1. Nội suy 1.1.1. Đặt vấn đề: Cho hàm số y = f(x) mà không biết biểu thức của giải tích hàm, chỉ biết giá trị của hàm tại một số hữu hạn điểm trên đoạn [a ; b] (bằng đo đạc hoặc thực nghiệm). x x0 x1. xi xn-1 xn y = f(x) y0 y1 yi yn-1 yn Tìm giá trị của hàm số tại một số điểm trung gian khác. 1.1.2. Bài toán nội suy: Xây dựng một hàm φ(x) có biểu thức đơn giản, có giá trị trùng với giá trị của hàm f(x) tại các điểm x0, x1,, xn, còn tại các điểm khác trên đoạn [a ; b] thì hàm φ(x) khá gần f(x) (phản ảnh đúng quy luật f(x)) → có thể suy ra giá trị gần đúng của hàm f(x) tại các điểm bất kì thỏa mãn x0 < x < xn. Hàm φ(x) – đƣợc gọi là hàm nội suy của f(x) trên đoạn [a ; b] Ý nghĩa hình học: Ta đi xây đƣờng cong y = φ(x) đi qua các điểm cho trƣớc (xi ; yi); i = 0, 1,, n 1.2. Đa thức nội suy Thƣờng chọn đa thức làm hàm nội suy vì: - Đa thức là loại hàm đơn giản. - Luôn có đạo hàm và nguyên hàm. Bài toán: Trên đoạn a ≤ x ≤ b, chọn một lƣới các điểm chia (điểm nút) xi; i = 0, 1, 2,, n với a ≤ x0, x1, x2,, xn ≤ b. Cho các giá trị tƣơng ứng của hàm y = f(x) tại các nút: x x0 x1. xi xn-1 xn y = f(x) y0 y1 yi yn-1 yn Cần xây dựng một đa thức bậc n: (1) Sao cho Pn(x) trùng với f(x) tại các nút xi → Đồ án Toán 1 20 1.3. Sự duy nhất của đa thức nội suy Đa thức nội suy Pn(x) của hàm f(x) định nghĩa ở trên nếu có thì chỉ có một mà thôi. → Đa thức nội suy có thể có nhiều cách xây dựng nhƣng do tính duy nhất nên các dạng của nó đều có thể quay về nhau. 2. Nội suy Lagrange. 2.1. Đa thức nội suy Lagrange ∑ (2) Trong đó li(x) - đa thức bậc n → Pn(x) – đa thức bậc n { → → (2): Đa thức nội suy Lagrange Nội suy tuyến tính (n = 1) x x0 x1 y y0 y1 Từ (2) → (3) Có dạng P1(x) = Ax + B – bậc nhất đối với x Nội suy bậc 2 (n = 2) x x0 x1 x2 y y0 y1 y2 (4) Đồ án Toán 1 21 P2(x) có dạng: P2(x) = Ax 2 + Bx + C – bậc hai đối với x. Sai số nội suy. Định lý: Nếu hàm f(x) liên tục trên [a ; b] và có trong [a ; b] đạo hàm liên tục đến cấp n+1 thì sai số nội suy rn(x) = f(x) – Pn(x) có biểu thức sau: (5) ([a ; b] khoảng chứa các nút xi) Gọi | | Thì | | || o Ƣu điểm của đa thức nội suy Lagrange: Đơn giản. o Nhƣợc điểm: Thêm một nút thì phải tính lại toàn bộ. Ví dụ: Cho bảng sau: x 1 2 3 4 y 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ị của bảng tại x = 3,5. Khi đó ta có đa thức nội suy bằng: Đồ án Toán 1 22 P3(x) = 5l0(x) + 7l1(x) + 8l2(x) + 9l3(x) => P3 (3,5) = 8,4375 Ghi chú: Viết biểu thức li(x) ( không tính ! ) Thay x → Giá trị. 2.2. Thuật toán (Nội suy Lagrange) Bƣớc 1:  Nhập dữ liệu.  Nhậpsố lƣợng mốc nội suy.  Nhập giá trị xi và f(xi).  Nhập giá trị x cần tính. Bƣớc 2:  Dựa vào công thức: ∑ ; i ≠ j  Hàm tính Ln(x): + Vòng lặp for cho in + Vòng lặp for cho jn + Nếu i≠j: - Đặt u = u*(x - x[j]). - Đặt v = v*(x[i] - x[j]). - Đặt Ln(x) = w = w + ((u/v)*y[i]). Bƣớc 3:  Xuất ra trị giá của hàm f(xi) cần tìm. Đồ án Toán 1 23 2.3. Code chƣơng trình (Nội suy Lagrange) Đồ án Toán 1 24 3. Nội suy Newton. 3.1. Đa thức nội suy Newton. 3.1.1. Nội suy Newton với mốc không cách đều. Tỉ sai phân (tỉ hiệu) hữu hạn : Cho y = f(x) có giá trị yi = f(xi) tại các nút xi không cách đều nhau. Tỉ sai phân cấp 1 (hạng 1): Tỉ sai phân cấp 2: Đồ án Toán 1 25 . Tỉ sai phân cấp n: 3.1.2. Đa thức nội suy Newton với mốc không cách đều. Dạng tiến: Dạng lùi: Ví dụ: Cho bảng nội suy sau: x -1 2 3 5 6 y 0 1 -2 1 3 a) Hảy lập bảng tính các tỉ hiệu. b) Viết đa thức nội suy y = P(x) và tính y(4). Giải: Ta lập bảng sau: ▲Ghi chú: Ở đây ta kí hiệu THi là tỉ hiệu tiến cấp i vàTHi * là tỉ hiệu lùi cấp i. Đồ án Toán 1 26 Đa thức nội suy Newton là:  Dạng tiến: = > y(4) = P4(x) = - .  Dạng lùi: = > y(4) = P4(x) = . 3.1.3. Nội suy Newton với mốc cách đều. - Sai phân (Hiệu) hữu hạn: Hàm số y = f(x) có giá trị yi = f(xi) tại các nút xi cách đều nhau với xi+1 – xi = h = const; i = 1, 2,, n. Suy ra: Có x0 thì x1 = x0 + h; x2 = x0 + 2h ; xi = x0 + ih - Định nghĩa sai phân hữu hạn của hàm y = f(x) Sai phân cấp 1 (hạng 1): Sai phân cấp hai: Sai phân cấp ba: Sai phân cấp n là sai phân của sai phân cấp n – 1. Đồ án Toán 1 27 3.1.4. Đa thức nội suy Newton tiến với mốc cách đều (nội suy về phía phải). - Trƣờng hợp các nút cách đều, đa thức có dạng: - Xác định a0, a1, a2, , an. Từ điều kiện Pn(xi) = yi - x = x0 ; a0 = Pn(x0) = y0 - x = x1; ; - x = x2; – → - Đỗi biến: Ta đặt: t = → x = x0 + t.h xi = x0 + i.h → x - xi = x – x0 – i.h = t.h – i.h = (t – i )h; → - Thƣờng dùng để tính các giá trị của của hàm ở gần x0 đầu bảng. 3.1.5. Đa thức nội suy Newton lùi – với mốc cách đều (nội suy về phía trái). Với cách làm tƣơng tự nhƣng bắt đầu với x = xn. Ta có thể suy ra. Đồ án Toán 1 28 - Ƣu điểm của công thức nôi suy Newton: Thêm nút chỉ cần thêm số hạng, không cần phải tính lại. - Để thuận tiện tính toán thƣờng ta lập bảng sai phân đƣờng chéo. * Bảng sai phân đường chéo của công thức nội suy tiến: * Bảng sai phân đường chéo của công thức nội suy lùi: Đồ án Toán 1 29 3.1.6. Sai số của phép nội suy Newton. Vẫn dùng công thức sai số đã biết trong phần nội suy Lagrange nhƣng thay đạo hàm hạng n + 1 bằng sai phân hạng n + 1. → Với công thức nội suy tiến: → Với công thức nội suy lùi: Ví dụ: Nội suy Newton: Đa thức nội suy tiến: x ≈ 150 = > – x = 16 0 = > t = 0,2 = > N1(0,2) = 0,2756. sin16 0 = 0,2756. Đa thức nội suy lùi: x ≈ 550 => t = => x = 55+5t – x = 54 0 => t = - 0,2 => N2(-0,2) = 0,80903. sin54 0 = 0,8090. x y y 2y 3y 15 0,5588 0,0832 0,0532 - 0,0026 - 0,0057 -0,0006 - 0,0003 20 0,3420 25 0,4226 30 0,5 35 0,5736 40 0,6428 45 0,7071 50 0,7660 55 0,8192 Đồ án Toán 1 30 ▲ Nhận xét: Tất cả các sai phân: Nội suy Lagrange ≡ Newton. 3.2. Thuật toán (Nội suy Newton) Bƣớc 1:  Nhập dữ liệu:  Nhập số lƣợng các mốc nội suy.  Nhập các giá trị xi và f(xi).  Nhập trị giá x cần tính. Bƣớc 2: Lập bảng tỉ hiệu + Đặt a1 = y1 + Dùng vòng lặp thứ nhất cho j = 1 n - 1 + Dùng vòng lặp thứ hai cho i = 1 n - j yi = (yi+1 - yi )/( xi+j - xi ). Sau khi kết thúc vòng lặp thứ hai, Đặt y1 = aj+1. Thực hiện cho đến khi j = n - 1 thì quá trình lập bảng tỉ hiệu kết thúc. + Dùng đa thức nội suy Newton dạng tiến + Tính: Ln(x) = y0 + (x - x0)TH1 + (x - x0) (x - x1)TH2 + ... + (x - x0)... (x - xn-1)THn . - Đặt biến kq = TH1 hay kq = y0 - Dùng vòng lặp thứ nhất cho i = 2  n p=1; .- Dùng vòng lặp thứ hai cho j = 1 i (j không bằng i) p = p*(x - xj); kq = kq + p*ai Thực hiện cho đến khi i=n thì quá trình tính Ln(x) kết thúc. Cách khác có thể dùng đa thức nội suy Newton dạng lùi và hoàn toàn tƣơng tự chỉ lấy giá trị trong bảng tỉ hiệu có thể bằng cách xây dựng lại bảng tỉ hiệu dạng lùi rồi tính Ln(x). Bƣớc 3: Kết thúc xuất r