Giải gần đúng hệ phương trình bằng phương pháp lặp đơn

Ở phần lắp thêm nhất, giả dụ ta áp dụng phƣơng pháp Cramer nhằm giải các hệ phƣơng trình tuyến đường tính có phần solo giản. Tuy vậy khi chạm mặt một hệ phƣơng trình tất cả số ẩn to thì giám sát khá là dài cùng tốn thời gian. Chúng em nhận ra hai phƣơng pháp Gauss và lặp Seidelcũng đƣa ra đƣợc nghiệm đúng chuẩn hoặc gần đúng mực với không đúng số gồm thể chấp nhận đƣợc. Mặt khác, việc đo lường đơn giản, thời hạn chạy cấp tốc và huyết kiệm bộ nhớ nhiều so với phƣơng pháp Cramer. Đối với cùng 1 hệ phƣơng trình tất cả số ẩn rẻ thì ta tránh việc sữ dụng phƣơng pháp lặp Seidel này vì thời gian chạy đang lâu.Trong phần thiết bị hai, các phƣơng pháp nội suy cũng đƣa ra đƣợc đông đảo giá trị gần đúng của hàm f(x) tại các điểm nút xikhác. Tuy vậy trong thực tiễn các quý giá ysuy ra từ những điểm nút xilà xấp xỉ: yi≈ f(xi) từ đầy đủ giá trị đo đạc, thực nghiệm không trọn vẹn chính xác. Phải trong trƣờng hòa hợp này, lúc ta suy ra đƣợc đa thức nội suy rồi buộc cho các giá trị yi= f(xi) là không hợp l . Ai số chênh lệch từ mức thấp mang lại cao mặc dù vẫn có thể gật đầu đƣợc. Trƣờng vừa lòng có không ít những điểm nút thì nhiều thức nội suy sẽ có bậc lớn dẫn cho việc thống kê giám sát không thuận tiện. Ngoài ra nếu f(x) là hàm tuần hoàn thì phƣơng pháp nội suy này thật không phù hợp.


Bạn đang xem: Giải gần đúng hệ phương trình bằng phương pháp lặp đơn

*
*

Xem thêm:

Bạn sẽ xem trước đôi mươi trang tư liệu Giải sấp xỉ nghiệm của hệ phương trình con đường tính với các phương pháp nội suy hàm số bằng ngôn từ C, giúp xem tài liệu hoàn chỉnh bạn click vào nút download ở trên
Đồ án Toán 1 1 TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT phái nam TRƢỜNG ĐẠI HỌC TÔN ĐỨC THẮNG KHOA TOÁN – THỐNG KÊ ĐỒ ÁN TOÁN 1TÊ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áo viên hƣớng dẫn: ThS. LÊ TRUNG NGHĨA sv thực hiện: ĐẶNG NGỌC ĐỨC MS: C1201002 PHẠM THANH TÂM MS: C1201104 LỚP: 120C0101 LỚP: 120C0101NIÊN KHÓA: 2012 - 2016TP. Hồ Chí Minh, mon 11 năm 2014 Đồ án Toán 1 2 TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT phái nam TRƢỜNG ĐẠI HỌC TÔN ĐỨC THẮNG KHOA TOÁN – THỐNG KÊ ĐỒ ÁN TOÁN 1TÊ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: 120C0101NIÊN KHÓA: 2012 - năm nhâm thìn TP. Hồ Chí Minh, tháng 11 năm năm trước Đồ á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 đề bài đồ án này bọn chúng em dìm đƣợc những sự hỗ trợ từ những thầy cô vào khoa Toán – Thống kê, Trƣờng Đại học Tôn Đức Thắng. Những thầy cô đã hƣớng dẫn thiện chí 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 hoàn thành học tập, cùng rất sự giúp sức của đồng đội vì đó mà chúng em đã hoàn thành đề tài đồ vật án nhƣ mong muốn này. Nay chúng em xin đƣợc gửi lời cảm ơn đến những thầy cô nhất là thầy Lê Trung Nghĩa - ngƣời đang hƣớng dẫn tận tình, tạo thành điều kiện rất tốt cho chúng em để có thể chấm dứt tốt cuốn báo cáo này. Nhóm chúng em cũng xin đƣợc giữ hộ lời cảm ơn đến gia đình và anh em đã cổ vũ khuyến khích một trong những lúc khó khăn nhất. Một lần nữa chúng em xin tình thật cảm ơn! Chúc toàn bộ mọi ngƣời sức khỏe và thành công! Đồ án Toán 1 5 LỜI NÓI ĐẦU vào cuốn báo cáo này, chúng em xin trình diễn hai phần: Phần 1: Đối với một hệ phƣơng trình, họ luôn tất cả cách giải đưa ra nghiệm đúng chuẩn của nó. Ngƣời ta xây dựng phương pháp tính nghiệm đúng mực thông qua cách làm Cramer. Tuy nhiên khi chạm chán 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 phương pháp 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 chú ý so với phƣơng pháp Cramer với độ chính xác theo mức độ từ thấp cho cao. Bởi vậy vào 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: vào toán học, ta thƣờng chạm chán các bài xích toán liên quan đến khảo sát và tính giá bán trị của những hàm f(x) như thế nào đó. Tuy nhiên trong thực tế có trƣờng hòa hợp ta không khẳng định đƣợc biểu thức của hàm f(x) cơ mà chỉ dìm đƣợc quý hiếm của f(xi) rời rốc tại những điểm nút xi tƣơng ứng. Vấn đề đề ra là làm sao ta đi tính đƣợc những 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 đã tạo ra một hàm φ(xi) = yi = f(xi) cùng với ( i = 0,1,,n ) φ(x) ≈ f(x) với đa số x ϵ với x ≠ xi. Ta xây dừng hàm φ(x) hotline là việc nội suy. Ngoài ra phƣơng pháp bình phƣơng buổi tối thiểu đƣợc dùng để làm lặp các công thức thực nghiệm. Lúc tìm mối liên hệ giữa nhị đại lƣợng x với y phải thực hiện thí nghiệm rồi quan lại sát, đo đạc. Rồi phụ thuộc vào dữ liệu thu đƣợc, ta lập mối tương tác hàm số y = f(x) ví dụ gọi là lập công thức thực nghiệm. Nói chung việc tìm kiếm ra hàm f(x) là ngay gần đúng. Việc tìm kiếm ra hàm số giao động của hàm số f(x) bằng phƣơng pháp bình phƣơng nhỏ tuổi nhất đã rất phức tạp nếu ta ngần ngừ đƣợc dạng của hàm số xấp xỉ. Vào phần này chúng em trình bày dung văn bản “NỘI SUY LAGRANGE, NEWTON VÀ PHƢƠNG PHÁP BÌNH PHƢƠNG NHỎ NHẤT”. Phương pháp để tìm ra nghiệm xấp xỉ của các phƣơng trình hay hàm số tất cả rất nhiều. Chúng em chỉ liệt kê một trong những phƣơng pháp phổ biến 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. Trình làng chung về phƣơng pháp 19 2. Nội suy Lagrange đôi mươi 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. Ngôn từ phƣơng pháp và các dạng thƣơng gặp gỡ 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. Mang đến hệ phƣơng trình đường tính: { (1) Hệ phƣơng trình trên có thể đƣợc cho vị 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 những phƣơng pháp này là sau một vài hữu hạn những bƣớc tính. Ta dìm đƣợc nghiệm đúng nếu như trong quá trình giám sát và đo lường không làm tròn số. - Phƣơng pháp gần đúng (Gauss Siedel, sút dƣ): Thông thƣờng ta đến ẩn số một cực hiếm ban đầu, từ cực hiếm này tính cực hiếm nghiệm gần đúng tốt hơn theo một quy tắc làm sao đó. Quy trình này đƣợc tái diễn nhiều lần và với một trong những điều kiện tốt nhất định, ta thừa nhận đƣợc nghiệm ngay sát đúng. 2. Phƣơng pháp Cramer. Sự tồn tại cùng nghiệm độc nhất vô nhị của hệ: ∆ = det(A)s nếu ∆ = 0 thì ma trận A suy biến cho nên vì thế hệ (1) suy biến. Suy ra trường đoản cú ∆: bằng phương pháp thay cột máy i bởi cột sinh hoạt vế phải. Định lý Cramer : ví như ∆ ≠ 0 thì hệ (1) ko suy đổi mới và gồm nghiệm duy nhất được xem bởi công thức: (3) nhận xét: bí quyết thu gọn dể nhớ, đẹp. Tuy vậy khi n đủ phệ phải thực hiện số lƣợng lớn những phép tính. Việc tính những định thức sẽ chạm chán nhiều khó khăn. Nc(n) – số lƣợng phép tính bắt buộc làm lúc hệ có n phƣơng trình. Nc(n) = (n +1)!n với n = 15 ta bao gồm Nc(15) = 3.1014. Đồ án Toán 1 8 3. Phƣơng pháp Gauss. 3.1. Nội dung phƣơng pháp văn bản khử dần các ẩn về hệ tƣơng đƣơng tất cả dạng tam giác trên rồi giải tự dƣới lên mà chưa hẳn 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 → kiếm tìm đƣợc những ẩn. Quá trình (4) → (5): sử dụng những phép đổi khác sơ cấp trên dòng của ma trận. Quy 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ỏ tuổi hơn những 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 chiếc 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 đả đến tƣơng đƣơng với hệ sau: { {Vậy hệ tất cả nghiệm độc nhất vô nhị 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 thành phần của ma trận hệ số mở rộng. Cách 2: - chuyển đổi ma trận về dạng tam giác trên. - Kiểm tra thành phần aii + ví như aii = 0 thì hoán đỗi loại i. + trường hợp aii khác 0 thì ta tra cứu đƣợc hệ số khử.  tiến hành vòng lặp mang đến i chạy từ một đến n (số dòng).  triển khai vòng lặp mang lại j chạy từ i+1 đến n+1(số cột). Đặt c = (hệ số khử) Lặp mang lại k chạy từ bỏ i cho n+1: aj,k=c*ai,k+aj,k bước 3: - search 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 =1) (9) với x(0) mang đến trƣớc. (10) vào đó: (Bx)i = ∑ (11) Phƣơng pháp tính x(m) theo (9) call là phương thức lặp đối kháng trong đó: B là ma trận lặp. Đồ án Toán 1 13 Sự quy tụ và không đúng 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 như xi(m) → lúc 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 cùng với ma trận B nếu chuẩn chỉnh hàng: r0 = max (12) hoặc chuẩn chỉnh cột: r1 = max∑ (13) hoặc chuẩn chỉnh Ơclit: r2 = (∑ ∑ | | ) ⁄ (14) khi đó (9), (10) đang hội tụ bất kể đầu x(0) nào cùng sai số đƣợc đánh giá: ‖ ‖ ‖ ‖; (15) - r0 P3 (3,5) = 8,4375 Ghi chú: Viết biểu thức li(x) ( quanh đó ! ) chũm x → giá chỉ 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ới f(xi).  Nhập quý hiếm x buộc phải tính. Bƣớc 2:  phụ thuộc vào công thức: ∑ ; i ≠ j  Hàm tính Ln(x): + Vòng lặp for mang đến in + Vòng lặp for cho jn + ví như i≠j: - Đặt u = u*(x - x). - Đặt v = v*(x - x). - Đặt Ln(x) = w = w + ((u/v)*y). Bƣớc 3:  Xuất ra trị giá bán của hàm f(xi) đề xuất 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 biện pháp đều. Tỉ sai phân (tỉ hiệu) hữu hạn : đến y = f(x) có giá trị yi = f(xi) tại các nút xi không phương pháp đều nhau. Tỉ sai phân cấp cho 1 (hạng 1): Tỉ sai phân cấp cho 2: Đồ án Toán 1 25 . Tỉ không nên phân cung cấp n: 3.1.2. Đa thức nội suy Newton cùng với mốc không biện pháp đều. Dạng tiến: Dạng lùi: Ví dụ: mang lại 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 nhiều thức nội suy y = P(x) cùng 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 cung 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 cùng với mốc giải pháp đều. - không đúng phân (Hiệu) hữu hạn: Hàm số y = f(x) có mức giá trị yi = f(xi) tại các nút xi cách đều nhau cùng với xi+1 – xi = h = const; i = 1, 2,, n. Suy ra: tất cả x0 thì x1 = x0 + h; x2 = x0 + 2h ; xi = x0 + ih - Định nghĩa không nên phân hữu hạn của hàm y = f(x) sai phân cấp cho 1 (hạng 1): sai phân cấp cho hai: sai phân cung cấp ba: không nên phân cấp cho n là không đúng phân của không đúng 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 phương pháp đều (nội suy về phía phải). - Trƣờng hợp những nút phương pháp đều, đa thức tất cả dạng: - khẳng đị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 làm tính các giá trị của của hàm ở ngay gần x0 đầu bảng. 3.1.5. Đa thức nội suy Newton lùi – cùng với mốc biện pháp đều (nội suy về phía trái). Với giải pháp làm tƣơng từ nhƣng bước đầu với x = xn. Ta có thể suy ra. Đồ án Toán 1 28 - Ƣu điểm của phương pháp nôi suy Newton: Thêm nút chỉ cần thêm số hạng, không cần thiết phải tính lại. - Để tiện lợi tính toán thƣờng ta lập bảng sai phân đƣờng chéo. * Bảng không nên phân đường chéo cánh của công thức nội suy tiến: * Bảng không đúng phân đường chéo của bí quyết 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ách làm sai số đang biết trong phần nội suy Lagrange nhƣng cố đạo hàm hạng n + 1 bằng sai phân hạng n + 1. → Với cách làm nội suy tiến: → Với bí quyết nội suy lùi: Ví dụ: Nội suy Newton: Đa thức nội suy tiến: x ≈ 150 = > – x = 160 = > t = 0,2 = > N1(0,2) = 0,2756. Sin160 = 0,2756. Đa thức nội suy lùi: x ≈ 550 => t = => x = 55+5t – x = 540 => t = - 0,2 => N2(-0,2) = 0,80903. Sin540 = 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 ▲ thừa 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ới f(xi).  Nhập trị giá chỉ x đề xuất 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 đồ vật hai đến i = 1 n - j yi = (yi+1 - yi )/( xi+j - xi ). Sau khi xong xuôi vòng lặp thứ hai, Đặt y1 = aj+1. Thực hiện cho tới khi j = n - 1 thì quy trình lập bảng tỉ hiệu kết thúc. + cần sử 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 đổi mới kq = TH1 tốt kq = y0 - sử dụng vòng lặp thứ nhất cho i = 2  n p=1; .- dùng vòng lặp đồ vật hai mang lại j = 1 i (j không bằng i) p. = p*(x - xj); kq = kq + p*ai Thực hiện cho tới khi i=n thì quy trình tính Ln(x) kết thúc. Giải pháp khác hoàn toàn có thể dùng đa thức nội suy Newton dạng lùi và trọn vẹn tƣơng từ bỏ chỉ lấy quý giá 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: hoàn thành xuất r