Bài giảng Phương Pháp tính - Nguyễn Xuân Thảo

Nội dung text: Bài giảng Phương Pháp tính - Nguyễn Xuân Thảo

1. Bài giảng Phương Pháp Tính 2015 Học phần: Phương pháp tính Số tín chỉ: 03 (dùng cho sinh viên khoa CNTT và Khoa Cơ điện của HV Nông nghiệp Việt Nam) Tài liệu chính: Nguyễn Xuân Thảo, Bài giảng Phương pháp tính (Soạn 2015). Tài liệu tham khảo: [1]. Dương Thủy Vĩ, Phương pháp tính, Nhà xuất bản khoa học kĩ thuật, Hà Nội 2006. [2]. Phạm Kỳ Anh, Giải tích số, Nhà XB ĐHQG, Hà Nội 2008 [3]. Phạm Hạ Thủy, Phương pháp tính, Nhà xuất bản tài chính, Hà Nội 2010. [4]. Tạ Văn Đĩnh, Phương pháp tính, Nhà xuất bản Giáo dục Việt Nam, Hà Nội 2011. [5]. Phạm Phú Triêm, Nguyễn Bường, Giải tích số, Nhà xuất bản ĐHQG, Hà Nội 2000. [6]. Nguyễn Trường Chấng, Nguyễn Thế Thạch, Hướng dẫn sử dụng và giải toán trên máy tính Casio fx 570 ES, Nhà xuất bản Giáo dục, Hồ Chí Minh 2008. Nên dùng máy tính Casio fx 570 ES. Máy tính sẽ hỗ trợ cho chúng ta tính toán, đồng thời cũng thuận lợi cho việc giải thích và thực hiện các bước lặp của thuật toán tính toán một cách dễ hiểu và trực quan, dễ thực hiện được ngay. Một số chú ý ban đầu trên máy Casio: + Muốn lấy các kí hiệu chữ vàng trên bàn phím ta bấm tổ hợp phím 푆푕푖 푡 + với kí tự cần lấy, chẳng hạn muốn lấy giá trị , ta bấm 푆푕푖 푡 × 10 + Muốn lấy các kí hiệu chữ đỏ trên bàn phím ta bấm tổ hợp phím 푙 푕 + với kí tự cần lấy, chẳng hạn muốn lấy giá trị e, ta bấm 푙 푕 × 10 . + Máy có 9 biến (A, B, C, D, E, F, X, Y, M) nên có thể dùng để giải hệ phương trình đại số 3 biến theo phương pháp lặp. + Trong quá trình hướng dẫn thao tác trên máy, để tránh dài dòng ta quy ước: Các chữ số trong phương trình không viết trong khung phím , bấm phím trong khung , các chữ trong dấu () chỉ giải thích, chẳng hạn với (Y?) là nhập giá trị của Y. Để tránh quá dài cho bài giảng, sau những ví dụ ban đầu giúp SV làm quen với các thao tác trên máy Casio, những ví dụ về sau tôi chỉ gợi ý viết lại phương trình hoặc chỉ cho kết quả tính toán mà không hướng dẫn thao tác bấm phím. 1
2. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam Chương 0. Giới thiệu về phương pháp tính Tên gọi: 1. Phương pháp tính (Computational methods) 2. Phương pháp số (Numerical methods) 3. Giải tích số (Numerical analysis) 4. Toán học tính toán (Computational mathematics) PPT là một môn khoa học nghiên cứu cách giải gần đúng , chủ yếu là giải số, các phương trình, các bài toán xấp xỉ hàm số và các bài toán tối ưu. Có nhiều lí do nghiên để cứu giải gần đúng các bài toán như công thức giải đúng không hoặc khó thực hiện, dữ liệu thu thậpđược không chính xác, yêu cầu về mặt thời gian Cụ thể trong các bài toán sẽ nêu kĩ hơn. + Xấp xỉ hàm số: Thay một hàm số có dạng phức tạp hoặc một hàm số dưới dạng bảng bởi những hàm số đơn giản hơn (Bài toán nội suy, bài toán xấp xỉ) + Giải gần đúng các phương trình : Tìm nghiệm số gần đúng của một Phương trình đại số. + Giải gần đúng các bài toán tối ưu: QHTT, QH lồi, Sự khác biệt giữa toán lý thuyết và toán học tính toán (PPT) + Toán lý thuyết chỉ quan tâm đến chứng minh sự tồn tại nghiệm, khảo sát dáng điệu của hàm số và một số tính chất định tính của nghiệm. + Toán học tính toán đề xuất thuật giải trên máy tính, quan tâm đến các vấn đề: thời gian chạy trên máy, bộ nhớ cần sử dụng để giải bài toán, tốc độ hội tụ và sự ổn định của thuật giải. Ta xét sự khác biệt này qua các ví dụ sau: 1 Ví dụ 1. Giả sử ta cần tính tích phân 푛 −1 ∗ 푛 = 0 푒 , 푛 ∈ ∗ + Lý thuyết: 푛 ≥ 0, ∀푛 ∈ . Tích phân từng phần 푛 = 1 − 푛 푛−1 và 1 = 1 −1 1 ∗ 푒 = ≈0.367879 . Từ đó có thể tính được , ∀푛 ∈ . 0 푒 푛 + Phương pháp tính: Nếu ta tiếp tục tính theo công thức truy hồi 푛 = 1 − 푛 푛−1 ∗ thì 9 ≈ −0.068480. Điều này là sai vì thực chất 푛 ≥ 0, ∀푛 ∈ . Nguyên nhân 1 sai số bắt đầu từ chỗ 1 = 푒 ≈ 0.367879 và được tích lũy theo từng bước tính truy 1 hồi. Cho dù có tính chính xác 1 = 푒 đến thế nào đi chăng nữa thì vẫn nhận được < 0 với đủ lớn. Khắc phục hiện tượng này do khả năng xử lí của mỗi kĩ sư (người tính toán). Một phương pháp có thể nghĩ tới cho bài toán này là ta tính toán theo công thức 1 1 truy hồi ngược = 푛−1(1 − ) với chú ý 0 ≤ ≤ 푛 = , 푛−1 푛 푛 0 푛+1 lim푛→0 푛 = 0. 1 Nếu cho ≈ 0 thì sai số mắc phải 휀 < . 20 20 21 2
3. Bài giảng Phương Pháp Tính 2015 1 1 1 Khi đó ≈ với sai số mắc phải 휀 < × . 19 20 19 21 20 −12 Đến 9 sai số chỉ còn 휀9 < 10 (rất nhỏ) và 9 ≈ 0.091623. Thực hành tính toán trên máy Casio fx 570 ES Plus. 1 −1 - bước 0: Tính ≈ 0.367879 1 = 0 푒 . Bấm máy □ □ 푙 푕 푙 푕 푒 ∎ 푙 푕 − 1 푖 푕 ể푛 để 푛푕ậ ậ푛 0 1 = □ - bước lặp: Tính 푛 = 1 − 푛 푛−1∀푛 ≥ 2. Ta coi 푛 ≔ , 푛−1 ≔ ( A, B có trong máy Casio), phương trình là = 1 − 푛 , ∀푛 ≥ 2. + n = 2 ta có phương trình = 1 − 2 = 0.264242. Bấm máy 푙 푕 푙 푕 퐿 1 − 2 푙 푕 퐿 đến đây máy sẽ hỏi giá trị ? nhập 0.367879 sẽ cho kết quả 0.264242. + n = 3 ta có phương trình = 1 − 2 = 0.207274. Bấm máy, từ màn hình kết quả tính ở bước n = 2, ta dùng phím di chuyển lên đến phương trình = 1 − 2 sửa thành = 1 − 3 rồi giải với = 0.264242. Cụ thể ⊲ ⊲ (푠ử 푡푕à푛푕 = 1 − 3 ) 퐿 Rồi nhập như bước trên để tính toán sẽ cho kết quả 0.207274. Các bước khác làm tương tự đến bước lặp muốn tính. Tương tự với việc tính ngược −1 푛−1 = 푛 (1 − 푛 ). Ví dụ 2. Giải hệ ptđstt = , là ma trận vuông cấp 푛. 푒푡 ≠ 0. det + Lý thuyết: Đây là hệ Cramer, công thức nghiệm = 푖, trong đó nhận 푖 det 푖 được từ bằng cách thay cột thứ 푖, 푖 = 1,2, , 푛, bởi cột . + PPT: Ta phải tính 푛 + 1 định thức, mỗi định thức có 푛! số hạng, mỗi số hạng có 푛 thừa số nên phải có 푛 − 1 phép nhân. Vì vậy để giải được bài toán này cần 푛! 푛 + 1 (푛 − 1) phép tính nhân (chưa kể các phép tính khác). Giả sử có một bài toán 20 biến (푛 = 20) (thực tế 푛 có thể lên đến hàng ngàn, hàng vạn biến) và máy tính thực hiện được 105 phép tính/1s. Khi đó để thực hiện hết các phép tính nhân (với 푛 = 20) cần đến 3. 108 năm! (Không còn ý nghĩa thực tế và tốn kém). 1 1 11 1 1 1 1 2 3 1 6 2 3 1 1 1 13 1 1 1 Ví dụ 3. Giải hệ 2 = . Đặt = . 2 3 4 12 2 3 4 1 1 1 3 47 1 1 1 3 4 5 60 3 4 5 1 1 + Lý thuyết: Nghiệm đúng của hệ 2 = 1 . 3 1 3
4. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 1 + PPT. Khi tính toán, ta thay ≈ 0.333, tìm nghiệm theo các phương pháp số tốt 3 1 1.090 nhất hiện nay (tính đến năm 2008) ta nhận được 2 ≈ 0.488 . Kết quả này 3 1.491 không hoàn toán chính xác. Nguyên nhân ma trận A có số điều kiện (cont (A)) rất xấu. Nhận xét: Trong quá trình giải số một bài toán có thể nảy sinh nhiều vấn đề mà lý thuyết không quan tâm và không thể giải quyết được. Do đó cần một khoa học riêng chuyên nghiên cứu việc giải số các bài toán. Gọi là phương pháp tính. Quan hệ giữa phương pháp tính và tin học Để giải một bài toán thực tế, người ta phải lần lượt thực hiện các công đoạn của quá trình mô phỏng số sau: + Bước 1. Xây dựng mô hình toán học cho bài toán thực tế. + Bước 2. Tính tương thích của mô hình với các hiện tượng thực tế. vấn đề tồn tại (và có thể duy nhất) của lời giải. Phác thảo phương hướng tính toán. + Bước 3. Rời rạc hóa mô hình: Người ta thường dùng các phương pháp sai phân, phần tử hữu hạn v.v để quy bài toán lien tục về các bài toán với số ẩn hữu hạn. + Bước 4. Xây dựng thuật toán: Ở công đoạn này, người ta chú ý đến các vấn đề như độ phức tạp của thuật toán, tính hội tụ, ổn định của phương pháp giải. + Bước 5. Cài đặt và khai thác tin học. Chương 1. Số xấp xỉ và sai số § 1. Số xấp xỉ 1. Sai số tuyệt đối, sai số tương đối Trong thực tế nhiều khi đại lượng chính xác cần tính toán ta không biết được, do đó ta cần phải dùng một số thay thế cho đại lượng đó để tính toán. Định nghĩa 1. Số xấp xỉ (số gần đúng). Ta gọi là số gần đúng của số chính xác , kí hiệu là ≈ , nếu như khác không nhiều và được dùng thay thế trong tính toán. Nếu > thì được gọi là số xấp xỉ trên của . Nếu < thì được gọi là số xấp xỉ dưới của . Định nghĩa 2. Đại lượng ∆ = − là sai số thật sự của số xấp xỉ . Đại lượng ∆= |∆ | là sai số tuyệt đối của . 4
5. Bài giảng Phương Pháp Tính 2015 Vì chưa biết nên ∆ cũng chưa biết. Do đó ∆ chưa biết. Trong tính toán ta sẽ dùng đại lượng ∆ ≥ ∆ làm sai số tuyệt đối giới hạn của . Tất nhiên, để sự xấp xỉ được chính xác thì ∆ được xác định càng nhỏ càng tốt. Ví dụ 1. Giả sử số chính xác là = và = 3.14. Ở đây ∆ = − = 3.14 − chưa biết. Ta có 3.14 ∆ . Nếu lấy 3.14 ∆ . ∆ Định nghĩa 3. Sai số tương đối của là 훿 = . | | ∆ Trong tính toán dùng 훿 = thay thế cho 훿. | | Ví dụ 2. Sản lượng của một nhà máy dự đoán là 105 (tấn); nhưng thực tế sản xuất đạt 100 (tấn). Sai số là ∆ = − = 105 − 100 = 5 (tấn), ∆= 5 (tấn) . Nếu tính theo kg thì ∆ = − = 105000 − 100000 = 5000 (kg), ∆= 5000 (kg). Sai số tuyệt đối (trong trường hợp này) phụ thuộc vào đơn vị đo. ∆ 5 Nếu dùng sai số tương đối 훿 = = = 5%. Sai số tương đối không phụ | | 100 thuộc vào giá trị đo. Ví dụ 3. Bạn có vui lòng trả thêm 1 triệu để mua một đồ vật? Nếu là một cái xăm xe máy thì chắc chắn câu trả lời là không. Nếu là một chiếc ô tô 4 chỗ thì câu trả lời có. Do đó, vấn đề quyết định ở đây không phải là số tiền trả thêm (độ tăng tuyệt đối) mà là tỉ số giữa số tiền tăng thêm và giá trị của đồ vật cần mua (sai số tuyệt đối). Quy ước: Viết số chính xác dưới dạng = ± ∆ . 2. Sai số quy tròn Thông thường ta viết một số thực dưới dạng hệ số thập phân. Chẳng hạn 25 = 2 × 101 + 5 × 100 25.6 = 2 × 101 + 5 × 100 + 6 × 10−1 −25.6 = −(2 × 101 + 5 × 100 + 6 × 10−1) Một số thập phân có dạng tổng quát −1 −푛+1 = ±(훼 × 10 + 훼 −1 × 10 + ⋯ + 훼 −푛+1 × 10 ) với là số nguyên dương; 0 0, thì có phần lẻ gồm chữ số; nếu 푛 = +∞ thì là số thập phân vô hạn. Thu gọn của là vứt bỏ các chữ số bên phải của để được một số 1 ngắn gọn hơn và gần đúng nhất với . 5
6. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam Chẳng hạn ≈ 3.141592 ≈ 3.14159 ≈ 3.1416 ≈ 3.142 ≈ 3.14; 4.25 ≈ 4.2; 4.135 ≈ 4.14. Quy tắc thu gọn Sai số quy tròn tuyệt đối 휃 1 = | − 1|. Tóm lại: Sai số gặp phải khi dùng số quy tròn 1 cho số đúng là 1 − ≤ 1 − + − = 휃 1 + ∆ . 3. Chữ số có nghĩa và chữ số đáng tin Chữ số có nghĩa Định nghĩa 4. Trong hệ thập phân chữ số có nghĩa là những chữ số được tính từ chữ số khác không đầu tiên tính từ trái sang phải. Chẳng hạn 0.0002405 chỉ có 4 chữ số có nghĩa. Chữ số đáng tin Định nghĩa 5. Trong cách viết −1 −푛+1 = ±(훼 × 10 + 훼 −1 × 10 + ⋯ + 훼 −푛+1 × 10 ) 1 1 số 훼 là số đáng tin nếu ∆ ≤ × 10푗 ; là số nghi ngờ nếu ∆ > × 10푗 , 푗 = 푗 2 2 1, , − 푛 + 1. Ví dụ 4. Số xấp xỉ = 3.7284 với ∆ = 0.0047 có 3 chữ số đáng tin là 3, 7, 2 và 2 chữ số nghi ngờ là 8, 4. Vì 1 - Đối với chữ số 4: × 10−4 = 0.5 × 10−4 ∆ = 0.0047, 2 Chú ý. - Khi viết số gần đúng (xấp xỉ) chỉ nên giữ lại 1 hoặc 2 chữ số nghi ngờ để khi tính toán, sai số chỉ tác động lên các chữ số nghi ngờ mà thôi. - Sau một chữ số nghi ngờ luôn là số nghi ngờ, trước chữ số đáng tin luôn là chữ số đáng tin. § 2. Xác định sai số của hàm số khi biết sai số của đối số 1. Công thức tổng quát Xét hàm hai biến = , với , là các biến. Bài toán: Cho biết các sai số tuyệt đối giới hạn, tương đối giới hạn của các biến , . Hãy tìm các sai số tương ứng của . ′ ′ Công thức số gia: ∆ = , × ∆ + , × ∆ Giả sử , 푌 là các giá trị chính xác của các biến (nhưng không biết được), ta có 푈 = ( , 푌) là giá trị chính xác của hàm (cũng không biết được). Giả sử , là các giá trị xấp xỉ của các biến với các sai số tuyệt đối giới hạn tương ứng là ∆ , ∆ . ′ ′ ′ ′ Ta có |∆ | = | , × ∆ + , × ∆ | ≤ | , | × ∆ + | , | × ∆ 6
7. Bài giảng Phương Pháp Tính 2015 ′ ′ Ta chọn ∆ = | , | × ∆ + | , | × ∆ là sai số tuyệt đối giới hạn cần tìm cho = , . Sai số tương đối giới hạn: ∆ | ′ , |×∆ +| ′ , |×∆ 훿 = = = | ln ′ | × ∆ + | ln ′ | × ∆ | | | , | Tổng quát: Cho hàm số khả vi = ( 1, 2, , 푛 ). 푛 ′ + Sai số tuyệt đối giới hạn ∆ = 푖=1 | 푖 ( 1, 2, , 푛 ) | × ∆ 푖 ∆ + Sai số tương đối giới hạn 훿 = = 푛 | ln ′ | × ∆ | | 푖=1 푖 푖 Ví dụ 5. Cho hình thang có đáy lớn = 12 ± 0.5 , đáy bé = 8 ± 0.4 ( ), chiều cao 푕 = 5 ± 0.3 ( ). Hãy tính gần đúng diện tích 푆 và sai số tuyệt đối giới 푕 hạn ∆ . Biết 푆 = + × . 푆 2 2. Sai số của tổng đại số ∆ ∆ +∆ Xét hàm = ± ta có: ∆ = ∆ + ∆ và 훿 = = | | | | Chú ý về sai số của hiệu: Nếu , rất gần nhau thì = − có thể rất nhỏ, do đó ∆ +∆ 훿 = có thể rất lớn. Khắc phục: cố gắng tránh phép trừ hai số gần nhau; nếu | − | không tránh được phải lấy nhiều chữ số đáng tin cậy để tăng độ tin cậy của tính toán. 3. Sai số của tích Xét hàm = 1 2 푛 Ta có 훿 = 훿 1 + ⋯ + 훿 푛 và ∆ = 훿 | |. Hệ quả: 훿 = × 훿 . 4. Sai số của thương Xét hàm = ( ≠ 0). Ta có 훿 = 훿 + 훿 và ∆ = 훿 | |. § 3. Các loại sai số Trong tính toán ta thường gặp các sai số 1. Sai số giả thiết: Do mô hình hóa bài toán trong thực tế. Sai số này không thể loại trừ được 2. Sai số phương pháp: Phương pháp thay thế bài toán phức tạp bằng phương pháp đơn giản được gọi là phương pháp gần đúng. Sai số do phương pháp gần đúng tạo ra gọi là sai số phương pháp. 3. Sai số các số liệu: Các sai số thường đo được bằng thực nghiệm do đó có sai số. 7
8. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 4. Sai số do tính toán: Các số tính toán vốn đã có sai số, còn thêm sai số qui tròn, nên sau khi tính toán sẽ xuất hiện sai số tính toán. Chương 2. Tính gần đúng nghiệm thực của phương trình đại số và siêu việt §1. Đặt vấn đề 1. Bài toán Bài toán: Tìm nghiệm của phương trình = 0, trong đó ( ) là một hàm đại số hoặc siêu việt. Lý do: + Trừ một số trường hợp đặc biệt = 0 có thể có công thức giải đúng, nói chung là phức tạp. Do đó ta phải giải gần đúng. + Các hệ số của trong thực tế chỉ biết gần đúng, vì thế việc giải đúng = 0 nhiều khi chẳng những không thực hiện được mà nhiều khi còn không có ý nghĩa. Việc giải gần đúng nghiệm thực của = 0 được tiến hành theo hai bước + Bước 1. Tìm một khoảng phân ly nghiệm của = 0. + Bước 2. Tìm nghiệm với độ chính xác cần thiết. 2. Khoảng phân li nghiệm Định nghĩa: Khoảng ( , ) được gọi là khoảng phân li nghiệm của = 0 nếu , chỉ chứa duy nhất một nghiệm của = 0. Định lí: Nếu hàm số ( ) liên tục trên ( , ) và < 0, ′ ( ) không đổi dấu trong ( , ) thì ( , ) là khoảng phân li nghiệm của = 0. Khoảng phân li nghiệm thường được tìm qua việc khảo sát hàm số. Khoảng phân li nghiệm càng hẹp thì việc tìm nghiệm xấp xỉ càng tốt. ta có thể chia đôi khoảng phân li ban đầu để tìm các khoảng phân li nghiệm hẹp hơn. Ví dụ 1. = 2 − 5 − 3 = 0 có khoảng phân li nghiệm là (-1, 0) và (4,5). §2. Phương pháp chia đôi 1. Nội dung phương pháp - Giả sử ( , ) là khoảng phân li nghiệm của = 0. 8
9. Bài giảng Phương Pháp Tính 2015 - Để cho tiện theo dõi ta gọi ∗ là nghiệm đúng của phương trình = 0, tức là ∗ = 0. Các bước tiến hành phương pháp chia đôi - Bước 1. Chia đôi khoảng ( , ). + + + Nếu = 0 thì ∗ = là nghiệm của phương trình. 2 2 + + + Nếu ≠ 0 thì chọn khoảng , = , hoặc , = 2 1 1 2 1 1 + ( , ) sao cho ) ( < 0. 2 1 1 + - Bước 2. Tính 1 1 rồi lặp lại như bước 1. 2 Cứ như vậy ta thu được một dãy con lồng nhau 푛 , 푛 ⊂ 푛−1, 푛−1 ⊂ ⋯ ⊂ 1, 1 ⊂ ( , ) − có ) ( < 0 và − = → 0 (푛 → +∞). 푛 푛 푛 푛 2푛 ∗ Do đó 푛 , 푛 → (푛 → +∞) . − Sai số tuyệt đối giới hạn Δ = . 푛 2푛 Ưu điểm, nhược điểm của phương pháp chia đôi - Ưu điểm: đơn giản, dễ lập chương trình chạy trên máy tính, chắc chắn hội tụ. - Nhược điểm: tốc độ hội tụ chậm. Sơ đồ khối 2. Ví dụ Ví dụ 1. Giải gần đúng 3 − − 1 = 0 trên (1, 2) bằng phương pháp chia đôi sau 5 bước lặp và đánh giá sai số (tính toán 5 chữ số phần thập phân). Giải. Ta kiểm ta điều kiện của phương pháp chia đôi với = 3 − − 1. Vì 1 = −1, 2 = 5, nên khoảng (1, 2) là khoảng phân li nghiệm. Bảng giá trị tính toán − n 푛 + 푛 f( ) 푛 = 푛 푛 Δ푛 = 푛 2 2푛 0 1 1.5 2 0.875 1 1 1 1.25 1.5 -0.29688 0.5 2 1.25 1.375 1.5 0.22461 0.25 3 1.25 1.3125 1.375 -0.05151 0.125 4 1.3125 1.34375 1.375 0.08261 0.0625 5 1.3125 1.32813 1.34375 0.01458 0.03125 ∗ Ta có nghiệm xấp xỉ sau 5 bước lặp là 5 ≈ 1.32813 với sai số 5 − ≤ 0.03125. 9
10. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam Trong thực hành trên máy Casio Fx 570 ES PLUS. ( đọc tương ứng giữa các dòng) B. lặp Bấm máy Màn hình máy Casio Giải thích 1+2 3 + Tính + Bấm = (nhấn nút + Kết qủa = 1.5 2 2 푛 + 푛 1+2 3 푛 = = = 푆 ⇔ để chuyển phân 2 2 2 n = 0 số và thập phân) + Bấm + Trắng + Trở về màn hình tính toán 3 + 푛푠 푆푕푖 푡 2 − + 푛푠 − 푛푠 − 1 + Tính hàm hàm = 푛푠 − 1 3− −1 tại =32 7 + = + Kết quả = 0.875 + đọc kết quả 8 Từ màn hình kết quả ở bước n = 0 ta bấm + △ (mũi tên lên ở phím 4 1 + 2 + trở về tính bước lặp tiếp theo mũi tên) 2 + Di chuyển mũi tên phải, 1 + 1.5 1+1.5 + Tính bước lặp 푛 = 1+2 2 trái để sửa 2 2 1+1.5 thành 2 n = 1 5 5 + = + kết quả = 1.25 + đọc kết quả = 1.25 4 4 3 + △ (mũi tên lên ở phím 4 + 푛푠 − 푛푠 − 1 + Tính hàm hàm = mũi tên) 3− −1 tại =54 + = + Kết quả -0.296875 + đọc kết quả n = 2, Thao tác tương tự 3, Ngoài ra còn có các cách bấm máy khác, như phép gán hàm , nhưng phức tạp hơn. Các bạn đọc có thể tìm hiểu thêm. Ví dụ 2. Giải gần đúng 3 − − 1 = 0 trên (1, 2) bằng phương pháp chia đôi trong các trường hợp sau a) Sai số không vượt quá 2 × 10−2. b) Kết quả có ít nhất 3 chữ số đáng tin Gợi ý: a) Có 2 cách làm Cách 1. Làm tương tự như ví dụ 1, đến khi cột sai số nhỏ hơn hoặc bằng 2 × 10−2. Cách 2. Theo công thức đánh giá sai số, ta tìm số bước lặp cần thực hiện. 10
11. Bài giảng Phương Pháp Tính 2015 − 2−1 1 Sai số tuyệt đối giới hạn Δ = = = . Theo yêu cầu bài toán 푛 2푛 2푛 2푛 1 Δ = ≤ 2 × 10−2, và 푛 ≥ 6. Vậy cần ít nhất 6 phép lặp. 푛 2푛 b) Vì trước chữ số đáng tin là chữ số đáng tin, nên muốn kết quả có ít nhất 3 chữ số đáng tin thì đằng sau dấu thập phân phải có ít nhất 2 chữ số đáng tin (vì phần nguyên có 1 chữ số do khoảng phân li là (1, 2)). Vậy sai số cần tính 1 1 là Δ = ≤ × 10−2, hay 푛 ≥ 8. Vậy cần ít nhất 8 phép lặp 푛 2푛 2 §3. Phương pháp lặp 1. Nội dung phương pháp Mô tả phương pháp: Giả sử phương trình = 0 ⟺ = 휑 (1). Khoảng ( , ) phân li nghiệm. Giả sử 0 ∈ ( , ) bất kì. Đặt 푛+1 = 휑 푛 , ∀푛 ≥ 0. Sự hội tụ của phương pháp Ta có định lí sau: Định lí 1. Giả sử 휑 là hàm số liên tục, khả vi trên ( , ) sao cho a) ∀ ∈ , : 휑′ ( ) ≤ 푞 휀(1−푞) 푙푛 | | 1− 0 + 1 ≔ 푛 . 푙푛푞 0 Hơn nữa công thức (*) cho ta đánh giá hậu nghiệm, thuận lợi cho quá trình tính 휀(1−푞) toán. Nếu sai số của hai quá trình liên tiếp − < thì − 휉 < 휀. 푛 푛−1 푞 푛 + Nếu , = ( 0 − , 0 + ) thì để 휑 ( , ) ⊂ , chỉ cần 휑( 0 − 0| ≤ 1 − 푞 . 11
12. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam + Nếu 휑 là đơn điệu tăng thì để 휑 ( , ) ⊂ , chỉ cần ≤ 휑 , 휑 ≤ . Nếu 휑 là đơn điệu giảm thì để 휑 ( , ) ⊂ , chỉ cần ≤ 휑 , 휑 ≤ . Chú ý 2. Có nhiều cách từ = 0 suy ra = 휑 nhưng chọn 휑 sao cho thỏa mãn điều kiện của định lí 1 để đảm bảo tốc độ hội tụ. Ưu nhược điểm của phương pháp - Ưu điểm: + Xấp xỉ ban đầu không nhất thiết phải thật gần nghiệm đúng ∗. + Phép lặp có khả năng tự sửa sai. Nếu xấp xỉ thứ k, mắc sai số thì có thể coi như xấp xỉ ban đầu mới. + Có các đánh giá sai số tiên nghiệm và hậu nghiệm. + Dễ lập trình trên máy tính (thể hiện qua sơ đồ khối). + Dễ song song hóa. - Nhược điểm: Khi 푞 gần 1 thì tốc độ hội tụ rất chậm. Sơ đồ khối Chú ý: Tổng quát có thể đưa = 0 về = 휑 như sau: Đặt 휑 = + 휇 ( ) (chú ý = 0) với 휇 ≠ 0 được chọn sao cho 휑′ ( ) 1 (loại), 휑2 1.05 ≈ 1 1 −2 9.75608 ∉ (1,2) (loại). Với hàm 휑 = ( + 1)3 có 휑′ = ( + 1) 3 là 3 −2 −5 hàm nghịch biến vì 휑′′ = ( + 1) 3 < 0, ∀ ∈ 1,2 . Do đó 휑′ 2 = 9 0.16025 ≤ 휑′ ≤ 휑′ 1 = 0.20999, hay 휑′ ≤ 푞 = 0.25 < 1. Mặt khác, 12
13. Bài giảng Phương Pháp Tính 2015 1 휑′ > 0, nên 휑 = ( + 1)3 đồng biến và 1 1, ta chọn hàm ψ(x) là hàm ngược của hàm 휑′ thì ta có 휓′ ≤ 푞 = < 1. 13
14. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam Chẳng hạn với Ví dụ 1, ta có 2 ≤ ′ = 3 2 − 1 ≤ 11, ∀ ∈ (1,2). Ta có 1 x3−x−1 2 9 thể chọn 휑 = − = − và 휑′ ≤ 1 − = = 푞 và 11 11 11 11 1 0. 14
15. Bài giảng Phương Pháp Tính 2015 b. Nội dung phương pháp ∗ Tìm dãy xấp xỉ nghiệm 푛 푛≥0 cho nghiệm đúng . Thuật toán dừng ở bước thứ n thỏa mãn điều kiện dừng 휀. Xuất phát từ điểm 0 → 1 → ⋯ → 푛 → ⋯ theo công thức 푛 ( 푛 − ) 푛+1 = 푛 − (푛 = 0, 1,2, ) 푛 − ( ) trong đó + = nếu là điểm Fourier và chọn 0 = , + = nếu là điểm Fourier và chọn 0 = . Sai số phương pháp (2 cách đánh giá) ( ) + Giả sử ′ ( ) ≥ > 0, ∀ ∈ [ , ] ta có − ∗ ≤ 푛 푛 + Giả sử ′ ( ) không đổi dấu trên [ , ] và 0 0, ∀ ∈ (1,2). Do đó ′′ = 6 đồng biến trên (1,2) và ′′ = 6 ≥ "(1) = 6 > 0, ∀ ∈ (1,2). Từ đây ta thấy ′ = 3 2 − 1 đống biến và ′ ≥ ′ 1 = 2 > 0, từ đây ta cũng có = 2. Do đó các đạo hàm ′ và ′ ′ không đổi dấu trên (1,2). Hai điều kiện của phương pháp dây cung thỏa mãn, nên ta có thể thực hiện phương pháp dây cung. + Tìm điểm Fourier. Kiểm tra ta có 1 "(1) = (−1).6 0. Do đó 2 là điểm Fourier. Vậy trong công thức lặp ta có d = 2 và 0 = 1. 3 푛 ( 푛 − ) ( 푛 − 푛 −1)( 푛 −2) + Công thức lặp 푛+1 = 푛 − = 푛 − 3 , với 0 = 1. 푛 − ( ) 푛 − 푛 −6 ( ) 3− −1 Sai số − ∗ ≤ 푛+1 = 푛+1 푛+1 . 푛+1 2 15
16. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam + Bảng kết quả tính toán 3− −1 Bước lặp 푛+1 Sai số 푛 +1 푛 +1 2 n = 0 1.16667 0.28935 n = 1 1.25311 0.14268 n = 2 1.29344 0.06477 n = 3 1.31128 0.02829 n = 4 1.31899 0.01215 n = 5 1.32228 5.2× 10−3 n = 6 1.32368 2.2× 10−3 n = 7 1.32428 9.34× 10−4 Đến đây thì sai số nhỏ hơn 10−3 nên ta dừng thuật toán và kết luận nghiện gần đúng cần tìm là 8 = 1.32428. Thao tác trên máy tính bấm tay. Ở đây tính song song 2 cột 푛+1 và sai số nên ta dùng 2 biến gán, biến X dùng để tính 푛+1 và biến Y dùng để tính sai số Nhập các hàm 푌3−푌−1 1 Hàm tính sai số (bấm trước tính giá trị lặp tính ), bấm = kết quả 푛+1 2 2 (máy sẽ tính với như 푌 = 0). 푆푕푖 푡 푕 푙 푕 푌 푆푕푖 푡 2 − 푙 푕 푌 − 1 ⊲ 2 = ( 3− −1)( −2) 1 Hàm tính , bấm − = kết quả (máy sẽ tự tính với = 0). 푛+1 3− −6 3 푙 푕 − ( 푙 푕 푆푕푖 푡 2 − 푙 푕 − 1 ) ( 푙 푕 − 2 ) ⊲ ( 푙 푕 푆푕푖 푡 2 − 푙 푕 − 6 ) = Sau khi nhập hàm ta tính toán theo cách n Bấm máy Màn hình tính Giải thích Kết quả Tính X Tính Y X Y X Y x s.số 0 1 푆푕푖 푡 푅 퐿 1 → gán X=1 Dịch chuyển mũi 7 X=1.16667 1 tên lên hàm tính 6 theo X, bấm = 푆푕푖 푡 푅 퐿 푌 7 7 Gán kết quả Gán kết quả 푆푕푖 푡 푅 퐿 → → 푌 6 6 X=1.16667 Y=1.16667 Dịch chuyển 0.28935 Y=0.28935 Sai số mũi tên lên ứng với hàm tính theo 1 Y, bấm = 16
17. Bài giảng Phương Pháp Tính 2015 1 Dịch chuyển mũi 1.25311 X=1.25311 2 tên lên hàm tính theo X, bấm = 푆푕푖 푡 푅 퐿 푆푕푖 푡 푅 퐿 1.25311 1.25311 Gán kết quả Gán kết quả X=1.25311 Y=1.25311 푌 → → 푌 Dịch chuyển 0.14268 Y=0.14268 Sai số mũi tên lên ứng với hàm tính theo 2 Y, bấm = 2,3 Làm tương tự như bước n = 1. , Cách khác là nhập tính 푛+1 như các ví dụ trên (tính qua hàm bới biến Ans) đến khoảng 10 bước lặp (ngoài nháp), sau đó tính sai số và ghi lại kết quả theo yêu cầu. 3. Dddd Hhhhhhhhhhhhhhhhhh §5. Phương pháp tiếp tuyến 1. Nội dung phương pháp e. Ý tưởng phương pháp Trong phương pháp này ta luôn giả thiết các điều kiện sau thỏa mãn: + [a, b] là khoảng phân li nghiệm của = 0 + ( ) khả vi hai lần trên trên [ , ] và ′ ( ), ′′ ( ) không đổi dấu trên [ , ]. Định nghĩa: Điểm ∈ [ , ] được gọi là điểm Fourier nếu ′′ > 0. f. Nội dung phương pháp ∗ Tìm dãy xấp xỉ nghiệm 푛 푛≥0 cho nghiệm đúng . Thuật toán dừng ở bước thứ n thỏa mãn điều kiện dừng 휀. Xuất phát từ điểm 0 → 1 → ⋯ → 푛 → ⋯ theo công thức 푛 푛+1 = 푛 − (푛 = 0, 1,2, ) ′ 푛 trong đó + nếu là điểm Fourier thì chọn 0 = , + nếu là điểm Fourier và chọn 0 = . Sai số phương pháp (2 cách đánh giá) ( ) + Giả sử ′ ( ) ≥ > 0, ∀ ∈ [ , ] ta có − ∗ ≤ 푛 푛 + Giả sử ′ ( ) không đổi dấu trên [ , ] và 0 < ≤ ′ ( ) ≤ , ′′ ( ) ≤ ∀ ∈ [ , ]. Ta có − ∗ ≤ 1 − 2. 1 푛 2 푛+1 푛 Ưu điểm, nhược điểm của phương pháp + Ưu điểm:t.ốc dộ hội tụ nhanh hơn phương pháp dây cung + Nhược điểm: Khó lập trình tính toán hơn phương pháp dây cung. 17
18. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam g. Sơ đồ khối h. 2. Một số ví dụ Ví dụ 1. Giải gần đúng 3 − − 1 = 0 trên (1, 2) bằng phương pháp dây cung với độ chính xác 10−3 (tính toán 5 chữ số phần thập phân). Giải Ta kiểm tra điều kiện thực hiện của phương pháp tiếp tuyến, với = 3 − − 1. + 1 2 = −1 . 5 0, ∀ ∈ (1,2). Do đó ′′ = 6 đồng biến trên (1,2) và ′′ = 6 ≥ "(1) = 6 > 0, ∀ ∈ (1,2). Từ đây ta thấy ′ = 3 2 − 1 đống biến và ′ ≥ ′ 1 = 2 > 0, từ đây ta cũng có = 2. Do đó các đạo hàm ′ và ′ ′ không đổi dấu trên (1,2). Hai điều kiện của phương pháp tiếp tuyến thỏa mãn, nên ta có thể thực hiện phương pháp tiếp tuyến. + Tìm điểm Fourier. Kiểm tra ta có 1 "(1) = (−1).6 0. Do đó 2 là điểm Fourier. Vậy trong công thức lặp ta có 0 = 2. 3 푛 ( 푛 − 푛 −1) + Công thức lặp 푛+1 = 푛 − ′ = 푛 − 2 , với 0 = 2. ( ) 3 푛 −1 ( ) 3− −1 Sai số − ∗ ≤ 푛+1 = 푛+1 푛+1 . 푛+1 2 + Bảng kết quả tính toán 3− −1 N 푛+1 Sai số, 푛+1 푛+1 2 0 1.54545 0.57288 1 1.35961 0.07685 3 1.32580 2.3× 10−3 4 1.32472 2.3× 10−6 Đến đây ta có thể kết luận, nghiệm gần đúng cần tìm là 5 ≈ 1.32472. Nhận xét, tốc độ hội tụ của phương pháp tiếp tuyến nhanh hơn. Chỉ cần sau 5 vòng lặp ta đã đạt được độ chính xác 2.3× 10−6 (sau 8 vòng lặp phương pháp dây cung mới đạt được độ chính xác 9.34× 10−4). 18
19. Bài giảng Phương Pháp Tính 2015 Chương 3. Giải hệ phương trình đại số §1. Đặt vấn đề 1. Bài toán Bài toán: Giải hệ phương trình đại số . = trong đó = là mà trận hệ 푖푗 푛×푛 số, = 1, , 푛 là ma trận ẩn, = 1, , 푛 là ma trận hệ số tự do. 푒푡 Nếu 푒푡 ≠ 0 thì . = ⟺ = −1. hay = 푗 , 푗 = 1, , 푛. Như đã 푗 det biết, khi n đủ lớn việc tìm nghiệm theo công thức này rất khó khăn. Do đó cần nghiên cứu các phương pháp giải hệ phương trình đại số tuyến tính. * Hai loại phương pháp giải: nhóm phương pháp giải trực tiếp và nhóm phương pháp lặp. - Nhóm phương pháp trực tiếp: Cramer, Gauss, Gauss-Jordan, . Các phương pháp này sử dụng với hệ có kích thước nhỏ và hệ số đúng. - Nhóm phương pháp lặp: Giả sử ∗ là nghiệm đúng của hệ . = . Nhưng ta khó xác định được ∗ (có thể do n lớn), do đó ta tìm một dãy xấp xỉ nghiệm ( ) hội tụ dần đến ∗. Ta dừng lại khi đạt được độ chính xác cần thiết. ≥0 Phương pháp lặp có lợi hơn khi giải hệ phương trình có kích thước lớn và hệ số gần đúng. Khi giải hệ . = , người ta thương phân biệt hai loại ma trận. a) Ma trận lưu trữ được: là ma trận mà các phần tử của nó có thể lưu trữ và xử lí ở bộ nhớ trong. Kích thước của bài toán này thường không lớn lắm, khoảng 푛 = (103). b) Ma trận thưa: Ma trận có rất nhiều phần tử bằng 0. Các phần tử khác 0 có thể lưu trữ được trong bộ nhớ trong của máy tính, hoặc tính được theo một công thức truy hồi nào đó. Với loại ma trận này người ta có thể giải . = với 푛 = (106). Trong chương trình của chúng ta chỉ xét ma trận dạng lưu trữ được. 2. Số điều kiện của ma trận a) Chuẩn của ma trận: Chuẩn của ma trận vuông = , kí hiệu , là 푖푗 푛×푛 một số thực thỏa mã các điều kiện sau: N1) ≥ 0, ∀ = và = 0 khi và chỉ khi là ma trận không. 푖푗 푛×푛 N2) 훼 = 훼 , 훼 ∈ 푅 N3) + = + với mọi , là ma trận vuông cùng cấp. 19
20. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam N4) . ≤ . với mọi , là ma trận vuông cùng cấp. Người ta thường dùng ba chuẩn sau: 푛 + chuẩn theo cột 1 = max푗 =1, ,푛 푖=1 푖푗 . 1 푛 2 2 + chuẩn Euclid 2 = 푖,푗 =1 푖푗 푛 + chuẩn theo hàng ∞ = max푖=1, ,푛 푗 =1 푖푗 1 2 1 Ví dụ 1. Với ma trận = 1 −1 3 ta có 1 2 −3 1 = max 1 + 1 + 1 , 2 + −1 + 2 , 1 + 3 + −3 = 7 1 2 2 2 2 2 2 2 2 2 2 = 1 + 2 + 1 + 1 + (−1) + 3 + 1 + 2 + (−3) 2 = 31 ∞ = max 1 + 2 + 1 , 1 + −1 + 3 , 1 + 2 + −3 = 6. Véc tơ ma trận = 1, , 푛 ta có 푛 + chuẩn theo cột 1 = 푖=1 푖 . 1 푛 2 + chuẩn Euclid 2 = 푖=1 푖 2 푛 + chuẩn theo hàng ∞ = max푖=1, ,푛 푖=1 푖 b) Số điều kiện của ma trận vuông là 표푛 = .‖ −1‖. Nếu 표푛 ≫ 1 thì ma trận được gọi là có điều kiện xấu. 3. Sự không ổn định của hêệ pương trình đại số tuyến tính Nhiều trường hợp ta gặp những hệ phương trinìnđại số tuyến tính mà một sự thay đổi nhỏ trên các hệ số có thể dẫn đến việc thay đổi rất lớn về nghiệm. hệ phương trình như vậy gọi là hệ không ổn định trong tính toán; ngược lại hệ gọi là ổn định. 2 1 + 2 = 2 Ví dụ 2. Hệ có nghiệm 1 = 0.5 và 2 = 1. 2 1 + 1.01 2 = 2.01 2 1 + 2 = 2 Nếu thay đổi trên hệ số thành hệ có nghiệm 1 = 5 và 2. 01 1 + 1 2 = 2.05 2 = −8. Nghiệm thay đổi rất nhiều, có thể không còn ý nghĩa đối với các bài toán 20
21. Bài giảng Phương Pháp Tính 2015 2 1 thực tế. Lý do ma trận hệ số = có điều kiện rất xấu 표푛 = 2 1.01 −1 2. 2 = 501.005. Chú ý: Nếu 표푛 ≫ 1 hệ không ổn định, còn 표푛 ≈ 1 hệ ổn định. 4. § Phương pháp Gauss 1. Nội dung phương pháp Bài toán: Giải hệ phương trình đại số . = trong đó = là mà trận 푖푗 푛×푛 hệ số, = 1, , 푛 là ma trận ẩn, = 1, , 푛 là ma trận hệ số tự do. Nhắc lại phép biến đổi sơ cấp: + Đổi chỗ hai hàng + Nhân một hàng với một số khác 0. + Nhân một hàng với một số rồi cộng vào cào hàng khác. Nội dung phương pháp Gauss: có hai quá trình + Thuận: dùng phép biến đổi sơ cấp đưa phương trình . = về phương trình ′. = ′ trong đó ′ là ma trận tam giác trên thu được từ bằng các phép biến đổi sơ cấp. 푖ế푛 đổ푖 푠ơ ấ Sơ đồ ⋮ ′ ⋮ ′ ′ + Ngược: Từ . = ′ ta tìm nghiệm theo thứ tự từ 푛 → 푛−1 → ⋯ → 2 → 1. Quá trình tính toán được lưu trên bảng (xem ví dụ). 4푛3+9푛2−7푛 푛 푛−1 (2푛+5) 푛(푛+2) Khối lượng tính toán: 푆 = trong đó phép nhân, 푛 6 5 2 푛 푛−1 (2푛+5) phép chia, phép cộng hoặc trư. 5 Sai số của phương pháp Gaus: Chỉ có thể có sai sôố qui troò, sai số tính toán, không có sai số phương pháp. ( ) Ưu điểm, nhược điểm của phương pháp Gauss: Khi có một hệ số 푖푗 = 0 ở bước k, thì phương pháp Gauss phải đổi cột hoặc đổi phương trình. Điều này đẫn đến sai số hoặc không chính xác của phương pháp thậm chí không thực hiện được. Ví dụ 1. Giả hệ phương trình sau bằng phương pháp Gauss 21
22. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 1 + 2 + 1.1 3 = 3.1 2 1 + 2 + 3.3 3 = 6.3 3 1 + 4.1 2 + 3 = 8.1 Giải. Ta thực hiện phương pháp Gauss theo bảng sau: Giải thích 1 2 3 h.số tự do Tổng hệ Quá số trình 1 1 1.1 3.1 6.2 2 1 3.3 6.3 12.6 3 4.1 1 8.1 16.2 Để nguyên H1 1 1 1.1 3.1 6.2 −2 1 + 2 → 2 -1 1.1 0.1 0.2 −3 1 + 3 → 3 1.1 -2.3 -1.2 -2.4 Thuận 1 1 1.1 3.1 6.2 -1 1.1 0.1 0.2 1.1 2 + 3 → 3 -1.09 -1.09 -2.18 1 1 1.1 3.1 6.2 −1 2 → 2 1 -1.1 -0.1 -0.2 1 3 → 3 1 1 2 −1.09 1 1 2 Ngược 1 1 2 1 1 2 Đến đây ta có nghiệm 1 = 2 = 3 = 1. Cột tổng hệ số giúp kiểm tra nhanh xem các kết quả tính toán đúng không. Tương ứng trên mỗi hàng, nếu không có sai số thì giá trị tổng sẽ bằng tổng của các hệ số thành phần. 2. Phương pháp Gauss tìm ma trận nghịch đảo 푖ế푛 đổ푖 푠ơ ấ Sơ đồ ⋮ [I⋮ −1] Với là ma trận đơn vị cùng cấp với A. Việc thực hiện trên bảng cũng giống như việc giải hệ phương trình. 3. Dđ 22
23. Bài giảng Phương Pháp Tính 2015 §3 Một số phương pháp lặp A. Phương pháp lặp Jacobi 1. Nội dung phương pháp Bài toán: Tìm nghiệm gần đúng của phương trình . = với độ chính xác ′ ∗ ∗ 휀, tức là tìm véc tơ xấp xỉ nghiệm đúng thỏa mãn ′ − | | với 푖푗 푛×푛 푖푖 푗 ≠푖 푖푗 푖 = 1,2, , 푛. Khi là ma trận chéo trội thì phương pháp lặp trên được gọi là phương pháp lặp Jacobi và phép lặp chắc chắn hội tụ. Đồng thời, từ . = biến đổi thành = + 훽 bằng cách chia hai vế phương trình thứ i của hệ cho 푖푖 (푖 = 1,2, , 푛), sau đó chuyển vế tách thành = + 훽, khi đó là ma trận có các phần tử trên đường chéo đều bằng 0 và ∞ < 1. (sXem thêm các ví dụ) 2. Một số ví dụ Ví dụ 1. Dùng phương pháp lặp đơn tìm nghiệm gần đúng của hệ phương trình sau 3 bước lặp và đánh giá sai số (tính toán 4 chữ số phần thập phân). 23
24. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 4 1 + 0.24 2 − 0.08 3 = 8 0.09 1 + 3 2 − 0.15 3 = 9 (*) 0.04 1 + 0.08 2 + 4 3 = 20 4 0.24 −0.08 Ta có ma trận hệ số = 0.09 3 −0.15 là ma trận chéo trội. Ta có thể 0.04 0.08 4 thực hiện được phương pháp lặp đơn. 1 = −0.06 2 + 0.02 3 + 2 Hệ (*) tương đương với hệ 2 = −0.03 1 + 0.05 3 + 3 ( ). 3 = −0.01 1 + 0.02 2 + 5 0 −0.06 0.02 2 Ta có ma trận = −0.03 0 0.05 có ∞ = 0.08 < 1 và 훽 = 3 . −0.01 0.02 0 5 2 Từ ( ) ta có công thức lặp ( +1) = ( ) + 훽, ∀ ≥ 0 với (0) = 훽 = 3 , 5 tức là giải hệ ( +1) ( ) (0) 1 0 −0.06 0.02 1 2 1 2 ( +1) ( ) (0) 2 = −0.03 0 0.05 × 2 + 3 với 2 = 3 , ∀ ≥ 0 ( +1) −0.01 0.02 0 ( ) 5 (0) 5 3 3 3 Kết quả tính toán được ghi trong bảng sau k 0 1 2 3 ( ) 1 2 1.92 1.9094 1.9092 ( ) 2 3 3.19 3.1944 3.1949 ( ) 3 5 5.04 5.0446 5.0447 Đánh giá sai số (3) − ∗ ≤ ∞ (3) − (2) = 4.4× 10−5. ∞ 1− ∞ ∞ Thực hiện trên máy Casio: Cách 1. Gán (0) ≔ Mat A, B≔ Mat B, 훽 ≔ Mat C. Khi đó kết quả phép lặp (1) = (0) + 훽 trong máy tính là kết quả của 푡 × 푡 + 푡 , sau bước này cho (1) 푙à 푡 푛푠. Kết quả của cá phép lặp ( +1) = ( ) + 훽, ≥ 1 được thực hiện là 푡 × 푡 푛푠 + 푡 , mỗi lần lặp là một lần bấm phím = . 24
25. Bài giảng Phương Pháp Tính 2015 Nhập số liệu: Nhập Bấm máy Màn hình Giải thích Mat A 표 푒 6 1 3 (chọn ma 2 Nhập ma trận trận) 2 = 3 = 5 = 3 cấp 3 × 1 5 Mat B 푆푕푖 푡 4 2 2 0 −0.06 0.02 Nhập ma trận −0.03 0 0.05 cấp (thực 1 ( 푕ọ푛 푡 ậ푛) 0 = 3 × 3 −0.01 0.02 0 hiện ngay khi −0.06 = 0.02 = màn hình đã 0 = nhập Mat A) MatC 푆푕푖 푡 4 2 3 2 Nhập ma trận 3 cấp 3 × 1 (thực 3 ( 푕ọ푛 푡 ậ푛) 2 = 5 hiện ngay khi 3 = 5 = màn hình đã nhập Mat B) Sau khi nhập số liệu ta tính toán + phép toán (1) = (0) + 훽 tức là 푡 × 푡 + 푡 푆푕푖 푡 4 3 4 (Mat B) × 푆푕푖 푡 4 3 3 (Mat A) + 푆푕푖 푡 4 3 5 = 1.92 Kết quả Ans = 3.19 (tức là (1)) 5.04 + phép tính (2) = (1) + 훽 tức là 푡 × 푡 푛푠 + 푡 푆푕푖 푡 4 3 4 (Mat B) × 푆푕푖 푡 4 3 6 (Mat Ans) + 푆푕푖 푡 4 3 5 = 1.9094 Kết quả Ans = 3.1944 (tức là (2)) 5.0446 + Tính các ( +1) = ( ) + 훽, ≥ 2, lúc này ta chỉ cần bấm phím = mỗi lần bấm dấu = cho ta kết quả của một phép lặp. Cách 2. (Trực quan hơn cách 1, nhưng thủ công hơn) Ta gán 1 ≔ , 2 ≔ 푌, 3 ≔ . Khi đó ( ) trở thành = −0.06푌 + 0.02 + 2 푌 = −0.03 + 0.05 + 3 = −0.01 + 0.02 푌 + 5 Nhập hàm, chỉ nhập các vế phải của hệ phương trình, cách nhau bởi dấu “:”. (hàm 1) −0.06 푙 푕 푌 + 0.02 푙 푕 + 5 푙 푕 : (푕à 2, 푣푖ế푡 푙푖ề푛 푣à 푛푕ậ 푡ươ푛 푡ự) 푙 푕 : (hàm 3) 25
26. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam Đến đây máy sẽ hỏi các ẩn có trong phương trình, từ phương trình 1, đến phương trình 3, vì ở đây phương trình 1 khuyết X, nên ta nhập giá trị các biến tương ứng xong rồi ấn phím = sẽ đọc kết quả. Bước Bấm máy Màn hình Giải thích Nhập X Y A −0.06푌 + 0.02 + 2: Nhập các hàm trong hàm − 0.03 + 0.05 vế phải + 3: − 0.01 + 0.02 푌 + 5 c.bị Hỏi lần lượt các biến Bắt dầu tính với biến ban đầu của 3 = 5 = (0) n = 0 2 = Y=3, A=5, X=2 Nhậpgiá trị các biến ở bước lặp này n =1 = (pt tìm X) 1.92 X=1.92 = (pt tìm Y) 3.19 Y=3.19 = (pt tìm A) 5.04 A=5.04 3.19 (Y?) 3.19 = (A?) 5.05 = (X?) 1.92 = Ví dụ 2. Dùng phương pháp lặp đơn tìm nghiệm gần đúng của hệ phương trình sau 4 bước lặp và đánh giá sai số (tính toán 4 chữ số phần thập phân). 6 1 + 15 2 + 2 3 = 72 1 + 2 + 54 3 = 110 ( ) 27 1 + 6 2 − 3 = 85 Giải. Đây chưa phải là hệ có ma trận hệ số chéo trội, ta dùng các phép biến đổi sơ cấp đưa về hệ tương đương có ma trận hệ số chéo trội. Chẳng hạn đổi phương trình thứ 3 lên phương trình đầu, phương trình thứ 2 xuống phương trình thứ 3. Ta được hệ sau tương đương với hệ ( ) như sau 26
27. Bài giảng Phương Pháp Tính 2015 27 1 + 6 2 − 3 = 85 6 1 + 15 2 + 2 3 = 72 ( ) 1 + 2 + 54 3 = 110 Đến đây ta thực hiện các bước như ví dụ 1 đối với hệ (*). Ta có kết quả như bảng sau k 0 1 2 3 4 ( ) 1 3.1481 2.1569 2.491 2.4009 2.4315 ( ) 2 4.800 3.2691 3.6852 3.5451 3.5833 ( ) 3 2.0370 1.8898 1.9365 1.9226 1.9269 Sai số (4) − ∗ ≤ 0.0161. ∞ 3. Mmm B. Phương pháp lặp Seidel 1. Nội dung phương pháp Bài toán: Tìm nghiệm gần đúng của phương trình . = với độ chính xác ′ ∗ ∗ 휀, tức là tìm véc tơ xấp xỉ nghiệm đúng thỏa mãn ′ − < 휀. Với = 1,2, ∞. Thông thường chọn = ∞ (dễ kiểm tra hơn). Nội dung phương pháp: Từ . = biến đổi thành = + 훽 với = và 훽 = 훽 , , 훽 . 푖푗 푛×푛 1 푛 Ta tách ma trận = + trong đó là ma trận tam giác dưới thu được từ mà các phần tử trên dường chéo chính của đều bằng 0 (các phần tử khác 0 (nếu có) của đều nằm dưới đường chéo chính), và = − . Sau đó tìm tìm dãy lặp ( ) theo công thức ≥0 ( +1) = ( +1) + ( ) + 훽, ∀ ≥ 0 với (0) tùy ý, thường chọn (0) = 훽. - Điều kiện hội tụ: ≤ 푞 < 1. 푖−1 푛 - Sai số (đánh giá theo chuẩn . ∞ ). Với 1 = 0, 푖 = 푗 =1 | 푖푗 |, 푞푖 = 푗 =푖 | 푖푗 |, 푞푖 휇 = max푖 , 푖 = 1,2, , 푛. 1− 푖 휇 +1 + Sai số tiên nghiệm: ( +1) − ∗ ≤ (1) − (0) ∞ 1−휇 ∞ 휇 + Sai số hậu nghiệm: ( +1) − ∗ ≤ ( +1) − ( ) . ∞ 1−휇 ∞ - Ưu điểm, nhược điểm: + Ưu điểm: tốc độ hội tụ nhanh hơn phương pháp Jacobi. 27
28. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam + Nhược điểm: Đánh giá sai số phức tạp hơn phương pháp Jacobi. 2. Ví dụ Ví dụ 3. Dùng phương pháp lặp Seidel tìm nghiệm gần đúng của hệ phương trình sau 3 bước lặp và đánh giá sai số (tính toán 4 chữ số phần thập phân). 4 1 + 0.24 2 − 0.08 3 = 8 0.09 1 + 3 2 − 0.15 3 = 9 (I) 0.04 1 + 0.08 2 + 4 3 = 20 4 0.24 −0.08 Ta có ma trận hệ số = 0.09 3 −0.15 là ma trận chéo trội. Ta có thể 0.04 0.08 4 thực hiện được phương pháp lặp đơn. 1 = −0.06 2 + 0.02 3 + 2 Hệ (*) tương đương với hệ 2 = −0.03 1 + 0.05 3 + 3 (II). 3 = −0.01 1 + 0.02 2 + 5 0 −0.06 0.02 2 Ta có ma trận = −0.03 0 0.05 có ∞ = 0.08 < 1 và 훽 = 3 . Ta −0.01 0.02 0 5 0 0 0 0 −0.06 0.02 tách = + trong đó = −0.03 0 0 và = 0 0 0.05 −0.01 0.02 0 0 0 0 Từ đó ta có công thức lặp ( +1) = ( +1) + ( ) + 훽, ∀ ≥ 0 với (0) = 2 훽 = 3 , tức là giải hệ 5 ( +1) ( +1) ( ) 1 0 0 0 1 0 −0.06 0.02 1 2 ( +1) ( +1) ( ) 2 = −0.03 0 0 2 + 0 0 0.05 × 2 + 3 ( +1) −0.01 0.02 0 ( +1) 0 0 0 ( ) 5 3 3 3 (0) 1 2 (0) với 2 = 3 , ∀ ≥ 0 (0) 5 3 Kết quả tính toán được ghi trong bảng sau k 0 1 2 3 4 ( ) 1 2 1.92 1.9093 1.9092 1.9092 ( ) 2 3 3.1924 3.19495 3.19496 3.19496 ( ) 3 5 5.0446 5.0448 5.0448 5.0448 휇 Vì (4) ≡ (3) nên sai số (4) − ∗ ≤ (4) − (3) = 0. ∞ 1−휇 ∞ 28
29. Bài giảng Phương Pháp Tính 2015 Thực hiện trên máy Casio fx 570: Làm tương tự như cách 2 của ví dụ 1, nhưng trong quá trình nhập hàm số ta nhập đầy đủ cả phương trình. Bước Bấm máy Màn hình Giải thích Nhập X Y A X=−0.06푌 + 0.02 + Nhập các hàm hàm 2: 푌 = −0.03 + trong hệ phương 0.05 + 3: = trình. −0.01 + 0.02 푌 + 5 c.bị Hỏi lần lượt các biến Bắt dầu tính với 3 = 5 = biến ban đầu của (0) n = 0 Y=3, A=5, X=2 Nhậpgiá trị các biến ở bước lặp này n =1 = (pt tìm X) 1.92 X=1.92 = (pt tìm Y) 3.19 Y=3.19 = (pt tìm A) 5.04 A=5.04 n = Chỉ cần bấm phím 2,3, = máy sẽ hỏi giá trị các biên, ta lấy luôn giá trị đã xuất hiện trên màn hình 3. nnnn C. nnnn 29