zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Khoa học tự nhiên

Đồ án Toán 1: 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ố ngôn ngữ C++

Chia sẻ: Dang Ngoc Duc | Ngày: | Loại File: PDF | Số trang:47

Báo xấu

262
lượt xem 44
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 1 tìm nghiệm của hệ phƣơng trình tuyến tính, phần 2 nội suy và lấy xấp xỉ hàm số là những nội dung chính trong đồ án Toán 1 "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ố ngôn ngữ C++". Mời các bạn cùng tham khảo để có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ án Toán 1: 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ố ngôn ngữ C++

Đồ án Toán 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 LỚP: 120C0101 PHẠM THANH TÂM MS: C1201104 LỚP: 120C0101 NIÊN KHÓA: 2012 - 2016 TP. Hồ Chí Minh, tháng 11 năm 2014 1
Đồ án Toán 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 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 LỚP: 120C0101 PHẠM THANH TÂM MS: C1201104 LỚP: 120C0101 NIÊN KHÓA: 2012 - 2016 TP. Hồ Chí Minh, tháng 11 năm 2014 2
Đồ án Toán 1 NHẬN XÉT CỦA GIẢNG VIÊN HƢỚNG DẪN ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... 3
Đồ án Toán 1 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! 4
Đồ án Toán 1 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ế. 5
Đồ án Toán 1 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 6
Đồ án Toán 1 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.1014. 7
Đồ án Toán 1 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: ( )→ ( )→ 8
Đồ án Toán 1 ( )→ ( )→ ( )→ ( ) 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. 9
Đồ án Toán 1 - Vòng lặp j=i+1n. s=s+ aij*xj. (số nghiệm luôn
Đồ án Toán 1 11
Đồ án Toán 1 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. 12
Đồ án Toán 1 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ố: ‖ ‖ 13
Đồ án Toán 1 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 0 0 0 1 2 2 3 3 5 5 2 1,92 0,08 3,19 0,19 5,04 0,04 3 1,9094 0,0106 3,1944 0,0044 5,0446 0,0046 4 1,90923 0,00017 3,19495 0,00055 5,04480 0,0002 Ta nhận xét rằng với m = 4 thì | | ;| | | | 14
Đồ án Toán 1 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à 15
Đồ án Toán 1 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 16
Đồ án Toán 1 17
Đồ án Toán 1 18
Đồ án Toán 1 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 → 19
Đồ án Toán 1 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) 20

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.01: Bộ Luận Văn Thạc Sĩ Quản Trị Kinh Doanh MBA

165 tài liệu

2068 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.