Bài giảng Phương Pháp Tính

Bài giảng Phương Pháp Tính 2015 1 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. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 2 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: Ví dụ 1. Giả sử ta cần tính tích phân 𝐼𝑛 = 𝑥 𝑛𝑒𝑥−1 1 0 𝑑𝑥, 𝑛 ∈ 𝑁∗ + Lý thuyết: 𝐼𝑛 ≥ 0, ∀𝑛 ∈ 𝑁 ∗. Tích phân từng phần 𝐼𝑛 = 1 − 𝑛𝐼𝑛−1 và 𝐼1 = 𝑥𝑒𝑥−1𝑑𝑥 = 1 𝑒 ≈0.367879 1 0 . Từ đó có thể tính được 𝐼𝑛 , ∀𝑛 ∈ 𝑁 ∗. + 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 sai số bắt đầu từ chỗ 𝐼1 = 1 𝑒 ≈ 0.367879 và được tích lũy theo từng bước tính truy hồi. Cho dù có tính chính xác 𝐼1 = 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 truy hồi ngược 𝐼𝑛−1 = 𝑛 −1(1 − 𝐼𝑛) với chú ý 0 ≤ 𝐼𝑛 ≤ 𝑥 𝑛1 0 𝑑𝑥 = 1 𝑛+1 , lim𝑛→0 𝐼𝑛 = 0. Nếu cho 𝐼20 ≈ 0 thì sai số mắc phải 𝜀20 < 1 21 . Bài giảng Phương Pháp Tính 2015 3 Khi đó 𝐼19 ≈ 1 20 với sai số mắc phải 𝜀19 < 1 21 × 1 20 . Đến 𝐼9 sai số chỉ còn 𝜀9 < 10 −12 (rất nhỏ) và 𝐼9 ≈ 0.091623. Thực hành tính toán trên máy Casio fx 570 ES Plus. - bước 0: Tính 𝐼1 = 𝑥𝑒 𝑥−1𝑑𝑥 ≈ 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. + Lý thuyết: Đây là hệ Cramer, công thức nghiệm 𝑥𝑖 = det 𝐴𝑖 det 𝐴 , trong đó 𝐴𝑖 nhận đượ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). Ví dụ 3. Giải hệ 1 1 2 1 3 1 2 1 3 1 4 1 3 1 4 1 5 𝑥1 𝑥2 𝑥3 = 11 6 13 12 47 60 . Đặt = 1 1 2 1 3 1 2 1 3 1 4 1 3 1 4 1 5 . + Lý thuyết: Nghiệm đúng của hệ 𝑥1 𝑥2 𝑥3 = 1 1 1 . Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 4 + PPT. Khi tính toán, ta thay 1 3 ≈ 0.333, tìm nghiệm theo các phương pháp số tốt nhất hiện nay (tính đến năm 2008) ta nhận được 𝑥1 𝑥2 𝑥3 ≈ 1.090 0.488 1.491 . Kết quả này 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 𝑎. Bài giảng Phương Pháp Tính 2015 5 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. Nếu dùng sai số tương đối 𝛿 = ∆ |𝐴| = 5 100 = 5%. Sai số tương đối không phụ 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 𝑎 = ±(𝛼𝑚 × 10 𝑚 + 𝛼𝑚−1 × 10 𝑚−1 + ⋯ + 𝛼𝑚−𝑛+1 × 10 𝑚−𝑛+1) với 𝑚 là số nguyên dương; 0 < 𝛼𝑚 ≤ 9; 0 ≤ 𝛼𝑖 ≤ 9, 𝑖 = 𝑚 − 1, 𝑚 − 2, , 𝑚 − 𝑛 + 1; 𝛼𝑖 nguyên với 𝑖 = 𝑚, 𝑚 − 1, , 𝑚 − 𝑛 + 1. Nếu 𝑚 − 𝑛 + 1 ≥ 0 thì 𝑎 là số nguyên; nếu 𝑚 − 𝑛 + 1 = −𝑘, 𝑘 > 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 𝑎. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 6 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 𝑎 = ±(𝛼𝑚 × 10 𝑚 + 𝛼𝑚−1 × 10 𝑚−1 + ⋯ + 𝛼𝑚−𝑛+1 × 10 𝑚−𝑛+1) số 𝛼𝑗 là số đáng tin nếu ∆𝑎≤ 1 2 × 10𝑗 ; là số nghi ngờ nếu ∆𝑎> 1 2 × 10𝑗 , 𝑗 = 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ì - Đối với chữ số 4: 1 2 × 10−4 = 0.5 × 10−4 < ∆𝑎= 0.0047 - Đối với chữ số 8: 1 2 × 10−3 = 5 × 10−4 < ∆𝑎= 0.0047 - Đối với chữ số 2: 1 2 × 10−2 = 0.5 × 10−2 > ∆𝑎= 0.0047, 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ó |∆𝑢| = |𝑓𝑥 ′ 𝑥, 𝑦 × ∆𝑥 + 𝑓𝑦 ′ 𝑥, 𝑦 × ∆𝑦| ≤ |𝑓𝑥 ′ 𝑥, 𝑦 | × ∆𝑥 + |𝑓𝑦 ′ 𝑥, 𝑦 | × ∆𝑦 Bài giảng Phương Pháp Tính 2015 7 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,𝑥2, , 𝑥𝑛) | × ∆𝑥𝑖 𝑛 𝑖=1 + 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ố. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 8 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. Bài giảng Phương Pháp Tính 2015 9 - Để 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 𝑓 𝑎+𝑏 2 = 0 thì 𝑥∗ = 𝑎+𝑏 2 là nghiệm của phương trình. + Nếu 𝑓 𝑎+𝑏 2 ≠ 0 thì chọn khoảng 𝑎1, 𝑏1 = 𝑎, 𝑎+𝑏 2 hoặc 𝑎1, 𝑏1 = ( 𝑎+𝑏 2 , 𝑏) sao cho 𝑓 𝑎1)𝑓(𝑏1 < 0. - Bước 2. Tính 𝑓 𝑎1+𝑏1 2 rồi lặp lại như bước 1. Cứ như vậy ta thu được một dãy con lồng nhau 𝑎𝑛 , 𝑏𝑛 ⊂ 𝑎𝑛−1 , 𝑏𝑛−1 ⊂ ⋯ ⊂ 𝑎1, 𝑏1 ⊂ (𝑎, 𝑏) có 𝑓 𝑎𝑛)𝑓(𝑏𝑛 < 0 và 𝑏𝑛 − 𝑎𝑛 = 𝑏−𝑎 2𝑛 → 0 (𝑛 → +∞). 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 𝑎𝑛 𝑥𝑛 = 𝑎𝑛 + 𝑏𝑛 2 𝑏𝑛 f(𝑥𝑛 ) Δ𝑛 = 𝑏−𝑎 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. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 10 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 n = 0 + Bấm 1+2 2 = (nhấn nút 𝑆 ⇔ 𝐷 để chuyển phân số và thập phân) + Kết qủa 3 2 = 1.5 + Tính 𝑥𝑛 = 𝑎𝑛 +𝑏𝑛 2 = 1+2 2 = 3 2 + Bấm 𝐴𝐶 + Trắng + Trở về màn hình tính toán + 𝐴𝑛𝑠 𝑆𝑕𝑖𝑓𝑡 𝑥2 − 𝐴𝑛𝑠 − 1 + 𝐴𝑛𝑠3 − 𝐴𝑛𝑠 − 1 + Tính hàm hàm 𝑓 𝑥 = 𝑥3−𝑥−1 tại 𝑥=32 + = + Kết quả 7 8 = 0.875 + đọc kết quả n = 1 Từ màn hình kết quả ở bước n = 0 ta bấm + △ (mũi tên lên ở phím 4 mũi tên) 1 + 2 2 + trở về tính bước lặp tiếp theo + Di chuyển mũi tên phải, trái để sửa 1+2 2 thành 1+1.5 2 1 + 1.5 2 + Tính bước lặp 𝑥𝑛 = 1+1.5 2 + = + kết quả 5 4 = 1.25 + đọc kết quả 5 4 = 1.25 + △ (mũi tên lên ở phím 4 mũi tên) + 𝐴𝑛𝑠3 − 𝐴𝑛𝑠 − 1 + Tính hàm hàm 𝑓 𝑥 = 𝑥3−𝑥−1 tại 𝑥=54 + = + Kết quả -0.296875 + đọc kết quả n = 2, 3, Thao tác tương tự 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. Bài giảng Phương Pháp Tính 2015 11 Sai số tuyệt đối giới hạn Δ𝑛 = 𝑏−𝑎 2𝑛 = 2−1 2𝑛 = 1 2𝑛 . Theo yêu cầu bài toán Δ𝑛 = 1 2𝑛 ≤ 2 × 10−2, và 𝑛 ≥ 6. Vậy cần ít nhất 6 phép lặp. 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 là Δ𝑛 = 1 2𝑛 ≤ 1 2 × 10−2, hay 𝑛 ≥ 8. Vậy cần ít nhất 8 phép lặp §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 b) ∀𝑥 ∈ 𝑎, 𝑏 : 𝜑 𝑥 ∈ 𝑎, 𝑏 . Khi đó i) Phương trình 𝑥 = 𝜑 𝑥 có nghiệm duy nhất trên (𝑎, 𝑏). ii) Phép lặp 𝑥𝑛+1 = 𝜑 𝑥𝑛 hội tụ, hơn nữa ta có ước lượng 𝑥𝑛+1 − 𝑥 ∗ ≤ 𝑞(1 − 𝑞)−1|𝑥𝑛+1 − 𝑥𝑛 | (*) hoặc 𝑥𝑛+1 − 𝑥 ∗ ≤ 𝑞𝑛+1(1 − 𝑞)−1|𝑥1 − 𝑥0| (**) Chú ý: + công thức (**) thường dùng để đánh giá sai số tiên nghiệm. Tức là không cần tính toán các bước lặp ta cũng có thể chỉ ra số bước lặp cần thiết để thực hiện nghiệm gần đúng 𝑥𝑛 của nghiệm chính xác 𝑥 ∗ với độ chính xác 𝜀 cho trước. Thật vậy muốn 𝑥𝑛 − 𝑥 ∗ 𝑙𝑛 𝜀(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 toán. Nếu sai số của hai quá trình liên tiếp 𝑥𝑛 − 𝑥𝑛−1 < 𝜀(1−𝑞) 𝑞 thì 𝑥𝑛 − 𝜉 < 𝜀. + Nếu 𝑎, 𝑏 = (𝑥0 − 𝑟, 𝑥0 + 𝑟) thì để 𝜑 (𝑎, 𝑏) ⊂ 𝑎, 𝑏 chỉ cần 𝜑(𝑥0 − 𝑥0| ≤ 1 − 𝑞 𝑟. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 12 + 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, ∀𝑥 ∈ [𝑎, 𝑏]. Chẳng hạn từ 𝜑 𝑥 = 𝑥 + 𝜇 𝑥 𝑓 𝑥 ta có 𝜑′ 𝑥 = 1 + 𝜇 𝑥 𝑓′(𝑥). Ta có thể chọn 𝜇 𝑥 = − 1 𝑓 ′ (𝑥) . 2. Ví dụ Ví dụ 1. Giải gần đúng 𝑥3 − 𝑥 − 1 = 0 trên (1, 2) bằng phương pháp lặp đơn 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 Có nhiều cách chọn hàm 𝜑 𝑥 từ 𝑓 𝑥 = 0. Chẳng hạn từ 𝑥3 − 𝑥 − 1 = 0 ta có 𝑥 = 𝑥3 − 1 = 𝜑1 𝑥 𝑥 = 1 𝑥2 − 1 = 𝜑2 𝑥 𝑥 = (𝑥 + 1) 1 3 = 𝜑 𝑥 Nhưng ta chọn hàm thỏa mãn diều kiện hội tụ trong định lí về sự hội tụ của phương pháp lặp. Ta có: 𝜑1 ′ 𝑥 = 3𝑥2, 𝜑1 ′ 1.5 = 6.75 > 1 (loại), 𝜑2 1.05 ≈ 9.75608 ∉ (1,2) (loại). Với hàm 𝜑 𝑥 = (𝑥 + 1) 1 3 có 𝜑′ 𝑥 = 1 3 (𝑥 + 1) −2 3 là hàm nghịch biến vì 𝜑′′ 𝑥 = −2 9 (𝑥 + 1) −5 3 < 0, ∀ 𝑥 ∈ 1,2 . Do đó 𝜑′ 2 = 0.16025 ≤ 𝜑′ 𝑥 ≤ 𝜑′ 1 = 0.20999, hay 𝜑′ 𝑥 ≤ 𝑞 = 0.25 < 1. Mặt khác, Bài giảng Phương Pháp Tính 2015 13 𝜑′ 𝑥 > 0, nên 𝜑 𝑥 = (𝑥 + 1) 1 3 đồng biến và 1 < 𝜑 1 ≈ 1.25992 ≤ 𝜑 𝑥 ≤ 𝜑 2 ≈ 1.44225 < 2. Vậy các điều kiện của phép lặp thỏa mãn do đó ta có thể thực hiện phép lặp theo công thức 𝑥𝑛+1 = 𝜑 𝑥𝑛 = (𝑥𝑛 + 1) 1 3 với 𝑥0 = 1.4 (chú ý 𝑥0 có thể chọn tùy ý, nhưng nên dựa theo đánh giá về hàm 𝜑 𝑥 để chọn sao cho nhanh hội tụ). Sai số đánh giá theo công thức 𝑥𝑛+1 − 𝑥 ∗ ≤ 𝑞(1 − 𝑞)−1 𝑥𝑛+1 − 𝑥𝑛 = 0.25 × (1 − 0.25) −1|𝑥𝑛+1 − 𝑥𝑛 |. Bảng tính toán n 𝑥𝑛+1 = (𝑥𝑛 + 1) 1 3 Sai số 1 3 |𝑥𝑛+1 − 𝑥𝑛 | 0 1.33887 1 1.32740 2 1.32523 3 1.32481 4 1.32474 5 1.32472 7× 10−6 Thực hành trên máy Casio fx 570 ES Bước lặp Bấm máy Màn hình Giải thích n = 0 + 1.4 = + 1.4 + Khởi tạo 𝑥0 = 1.4, Ans = 1.4. + 𝐴𝐶 + trắng + Trở về màn hình chờ tính toán + 𝑆𝑕𝑖𝑓𝑡 𝐴𝑛𝑠 + 1 + 𝐴𝑛𝑠 + 1 3 + Tính toán 𝑥1 = (𝑥0 + 1) 1 3 + = + 1.3388659 + 𝑥1 ≈ 1.33887 n = 1 + = + 1.32739988 + 𝑥2 ≈ 1.32740 n = 2, 3, ... Tương tự như n = 1 (vì máy tính Casio có nhớ, đây là ưu việt của máy).  Một số chú ý về chọn hàm của phép lặp Chú ý 1: + Nếu hàm f x có 0 < 𝑚 ≤ 𝑓 ′ 𝑥 ≤ 𝑀, ∀𝑥 ∈ 𝑎, 𝑏 ta có thể đặt 𝜑 𝑥 = 𝑥 − 1 𝑀 𝑓 𝑥 , khi đó 0 ≤ 𝜑′ 𝑥 ≤ 1 − 𝑚 𝑀 = 𝑞 < 1. + Nếu hàm f(x) có −𝑀 ≤ 𝑓 ′ 𝑥 ≤ −𝑚 < 0, ∀𝑥 ∈ (𝑎, 𝑏) ta có thể đặt 𝜑 𝑥 = 𝑥 + 1 𝑀 𝑓 𝑥 , khi đó ta cũng có 0 ≤ 𝜑′ 𝑥 ≤ 1 − 𝑚 𝑀 = 𝑞 < 1. Chú ý 2: Nếu từ 𝑓 𝑥 = 0 ta tìm ra 𝑥 = 𝜑 𝑥 , hàm 𝜑 𝑥 có tính chất 𝜑′ 𝑥 ≥ 𝐴 > 1, ta chọn hàm ψ(x) là hàm ngược của hàm 𝜑′ 𝑥 thì ta có 𝜓′ 𝑥 ≤ 𝑞 = 1 𝐴 < 1. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 14 Chẳng hạn với Ví dụ 1, ta có 2 ≤ 𝑓 ′ 𝑥 = 3𝑥2 − 1 ≤ 11, ∀𝑥 ∈ (1,2). Ta có thể chọn 𝜑 𝑥 = 𝑥 − 1 11 𝑓 𝑥 = 𝑥 − x3−x−1 11 và 𝜑′ 𝑥 ≤ 1 − 2 11 = 9 11 = 𝑞 và 1 < 𝜑 1 = 1.0909 ≤ 𝜑 𝑥 ≤ 𝜑 2 = 1.54545 < 2. Do đó ta có thể chọn phép lặp 𝑥𝑛+1 = 𝜑 𝑥𝑛 = 𝑥𝑛 − 𝑥𝑛 3−𝑥𝑛−1 11 , 𝑥0 = 1.4 Bảng tính toán n 𝑥𝑛+1 ss 0 1.36873 0.09773 1 1.35096 0.05733 2 1.34053 0.03422 3 1.33431 0.02064 4 1.33056 0.01252 5 1.32828 7.6× 10−3 Ở đây so sánh với kết quả đã làm trong ví dụ 1 ta thấy phép lặp trên ví dụ 1 hội tụ nhanh hơn, lí do giá trị 𝑞 trong ví dụ 1 nhỏ hơn nhiều so với giá trị 𝑞 ở đâ𝑦. Một điều cũng dễ thấy là trong ví dụ 1, hai hàm 𝜑1 𝑥 và 𝜑 𝑥 có tính chất “ngược” của nhau. Vì 𝜑1 ′ 𝑥 = 3𝑥2 ≥ 3, ∀𝑥 ∈ 1,2 , nên ta chọn hàm 𝜑 𝑥 trong tính toán. Ví dụ 2. Giải gần đúng 𝑥3 − 𝑥 − 1 = 0 trên (1, 2) bằng phương pháp lặp đơn với độ chính xác 10−4. Hướng dẫn: Làm tương tự như ví dụ 1, đến khi gặp sai số cần thiết thì dừng lại. Ví dụ 3. Tìm nghiệm gần đúng của f x = x3 + x − 1000 = 0 trên (9,10) bằng phương pháp lặp đơn sau 5 bước lặp. 3. Ddđ 4. Nnnnn §4. Phương pháp dây cung 1. Nội dung phương pháp a. Ý 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. Bài giảng Phương Pháp Tính 2015 15 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 < 𝑚 ≤ 𝑓 ′(𝑥) ≤ 𝑀, ∀𝑥 ∈ [𝑎, 𝑏]. Ta có 𝑥𝑛 − 𝑥 ∗ ≤ 𝑀−𝑚 𝑚 𝑥𝑛+1 − 𝑥𝑛  Ưu điểm, nhược điểm của phương pháp + Ưu điểm: đơn giản, dễ lập trình. + Nhược điểm: tốc độ hội tụ chậm, điều kiện hơi chặt. c. Sơ đồ khối d. 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 dây cung, với 𝑓 𝑥 = 𝑥3 − 𝑥 − 1. + 𝑓 1 𝑓 2 = −1 . 5 < 0, nên (1,2) là khoảng phân li nghiệm. + 𝑓 ′ 𝑥 = 3𝑥2 − 1, 𝑓 ′′ 𝑥 = 6𝑥, 𝑓 ′′′ 𝑥 = 6 > 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, và 𝑓 2 𝑓"(2) = 5 × 12 = 60 > 0. Do đó 2 là điểm Fourier. Vậy trong công thức lặp ta có d = 2 và 𝑥0 = 1. + Công thức lặp 𝑥𝑛+1 = 𝑥𝑛 − 𝑓 𝑥𝑛 (𝑥𝑛−𝑑) 𝑓 𝑥𝑛 −𝑓(𝑑) = 𝑥𝑛 − (𝑥𝑛 3−𝑥𝑛−1)(𝑥𝑛−2) 𝑥𝑛 3−𝑥𝑛−6 , với 𝑥0 = 1. Sai số 𝑥𝑛+1 − 𝑥 ∗ ≤ 𝑓(𝑥𝑛+1) 𝑚 = 𝑥𝑛+1 3−𝑥𝑛+1−1 2 . Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 16 + Bảng kết quả tính toán Bước lặp 𝑥𝑛+1 Sai số 𝑥𝑛+1 3−𝑥𝑛+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 Hàm tính sai số (bấm trước tính giá trị lặp tính 𝑥𝑛+1), bấm 𝑌3−𝑌−1 2 = kết quả 1 2 (máy sẽ tính với như 𝑌 = 0). 𝑆𝑕𝑖𝑓𝑡 𝑕𝑦𝑝 𝐴𝑙𝑝𝑕𝑎 𝑌 𝑆𝑕𝑖𝑓𝑡 𝑥2 − 𝐴𝑙𝑝𝑕𝑎 𝑌 − 1 ⊲ 2 = 𝐴𝐶 Hàm tính 𝑥𝑛+1, bấm 𝑋 − (𝑋3−𝑋−1)(𝑋−2) 𝑋3−𝑋−6 = kết quả 1 3 (máy sẽ tự tính với 𝑋 = 0). 𝐴𝑙𝑝𝑕𝑎 𝑋 − ( 𝐴𝑙𝑝𝑕𝑎 𝑋 𝑆𝑕𝑖𝑓𝑡 𝑥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 tên lên hàm tính theo X, bấm = 7 6 X=1.16667 𝑥1 𝑆𝑕𝑖𝑓𝑡 𝑅𝐶𝐿 𝑋 𝑆𝑕𝑖𝑓𝑡 𝑅𝐶𝐿 𝑌 7 6 → 𝑋 7 6 → 𝑌 Gán kết quả X=1.16667 Gán kết quả Y=1.16667 Dịch chuyển mũi tên lên hàm tính theo Y, bấm = 0.28935 Y=0.28935 Sai số ứng với 𝑥1 Bài giảng Phương Pháp Tính 2015 17 1 Dịch chuyển mũi tên lên hàm tính theo X, bấm = 1.25311 X=1.25311 𝑥2 𝑆𝑕𝑖𝑓𝑡 𝑅𝐶𝐿 𝑋 𝑆𝑕𝑖𝑓𝑡 𝑅𝐶𝐿 𝑌 1.25311 → 𝑋 1.25311 → 𝑌 Gán kết quả X=1.25311 Gán kết quả Y=1.25311 Dịch chuyển mũi tên lên hàm tính theo Y, bấm = 0.14268 Y=0.14268 Sai số ứng với 𝑥2 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 < 𝑚 ≤ 𝑓 ′(𝑥) ≤ 𝑀, 𝑓 ′′ (𝑥) ≤ 𝑀1∀𝑥 ∈ [𝑎, 𝑏]. Ta có 𝑥𝑛 − 𝑥 ∗ ≤ 𝑀1 2𝑚 𝑥𝑛+1 − 𝑥𝑛 2.  Ư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. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 18 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, nên (1,2) là khoảng phân li nghiệm. + 𝑓 ′ 𝑥 = 3𝑥2 − 1, 𝑓 ′′ 𝑥 = 6𝑥, 𝑓 ′′′ 𝑥 = 6 > 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, và 𝑓 2 𝑓"(2) = 5 × 12 = 60 > 0. Do đó 2 là điểm Fourier. Vậy trong công thức lặp ta có 𝑥0 = 2. + Công thức lặp 𝑥𝑛+1 = 𝑥𝑛 − 𝑓 𝑥𝑛 𝑓 ′ (𝑥) = 𝑥𝑛 − (𝑥𝑛 3−𝑥𝑛−1) 3𝑥𝑛 2−1 , với 𝑥0 = 2. Sai số 𝑥𝑛+1 − 𝑥 ∗ ≤ 𝑓(𝑥𝑛+1) 𝑚 = 𝑥𝑛+1 3−𝑥𝑛+1−1 2 . + Bảng kết quả tính toán N 𝑥𝑛+1 Sai số, 𝑥𝑛+1 3−𝑥𝑛+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). Bài giảng Phương Pháp Tính 2015 19 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 𝑥𝑗 = 𝑑𝑒𝑡 𝐴𝑗 det 𝐴 , 𝑗 = 1, , 𝑛. Như đã 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 𝑋(𝑘) 𝑘≥0 hội tụ dần đến 𝑋∗. Ta dừng lại khi đạt được độ chính xác cần thiết. 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. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 20 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 . + chuẩn Euclid 𝐴 2 = 𝑎𝑖𝑗 2𝑛 𝑖 ,𝑗=1 1 2 + chuẩn theo hàng 𝐴 ∞ = max𝑖=1,,𝑛 𝑎𝑖𝑗 𝑛 𝑗=1 Ví dụ 1. Với ma trận 𝐴 = 1 2 1 1 −1 3 1 2 −3 ta có 𝐴 1 = max 1 + 1 + 1 , 2 + −1 + 2 , 1 + 3 + −3 = 7 𝐴 2 = 1 2 + 22 + 12 + 12 + (−1)2 + 32 + 12 + 22 + (−3)2 1 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 . + chuẩn Euclid 𝑋 2 = 𝑥𝑖 2𝑛 𝑖=1 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. Ví dụ 2. Hệ 2𝑥1 + 𝑥2 = 2 2𝑥1 + 1.01𝑥2 = 2.01 có nghiệm 𝑥1 = 0.5 và 𝑥2 = 1. Nếu thay đổi trên hệ số thành hệ 2𝑥1 + 𝑥2 = 2 2. 01𝑥1 + 1𝑥2 = 2.05 có nghiệm 𝑥1 = 5 và 𝑥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 Bài giảng Phương Pháp Tính 2015 21 thực tế. Lý do ma trận hệ số 𝐴 = 2 1 2 1.01 có điều kiện rất xấu 𝑐𝑜𝑛𝑑 𝐴 = 𝐴 2. 𝐴 −1 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ụ).  Khối lượng tính toán: 𝑆𝑛 = 4𝑛3+9𝑛2−7𝑛 6 trong đó 𝑛 𝑛−1 (2𝑛+5) 5 phép nhân, 𝑛(𝑛+2) 2 phép chia, 𝑛 𝑛−1 (2𝑛+5) 5 phép cộng hoặc trư.  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 Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 22 𝑥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ệ số Quá trình 1 1 1.1 3.1 6.2 Thuận 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 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 −1.09 𝐻3 → 𝐻3 1 1 2 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đ Bài giảng Phương Pháp Tính 2015 23 §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,∞. 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, , 𝛽𝑛 𝑇. Sau đó tìm tìm dãy lặp 𝑋(𝑘) 𝑘≥0 theo công thức 𝑋(𝑘+1) = 𝐵𝑋(𝑘) + 𝛽, ∀𝑘 ≥ 0 với 𝑋(0) tùy ý, thường chọn 𝑋(0) = 𝛽. - Điều kiện hội tụ: 𝐵 𝑝 ≤ 𝑞 < 1. - Sai số: + Sai số tiên nghiệm: 𝑋(𝑘+1) − 𝑋∗ 𝑝 ≤ ( 𝐵 𝑝 ) 𝑘+1 1− 𝐵 𝑝 𝑋(1) − 𝑋(0) 𝑝 + Sai số hậu nghiệm: 𝑋(𝑘+1) − 𝑋∗ 𝑝 ≤ 𝐵 𝑝 1− 𝐵 𝑝 𝑋(𝑘+1) − 𝑋(𝑘) 𝑝 . - Ưu điểm, nhược điểm của phương pháp. + Ưu điểm: Phương pháp lặp có khả năng tự sửa sai, có các đánh giá tiên nghiệm và hậu nghiệm, dễ lập trình tính toán. + Nhược điểm: Nếu 𝐵 𝑝 ≥ 1 thì phương pháp không hội tụ. Khi 𝐵 𝑝 bé hơn nhưng khá gần 1 thì hội tụ rất chậm.  Ma trận chéo trội: Định nghĩa. Ma trận 𝐴 = 𝑎𝑖𝑗 𝑛×𝑛 gọi là chéo trội nếu |𝑎𝑖𝑖 | > |𝑎𝑖𝑗 |𝑗≠𝑖 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). Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 24 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 (*) Ta có ma trận hệ số 𝐴 = 4 0.24 −0.08 0.09 3 −0.15 0.04 0.08 4 là ma trận chéo trội. Ta có thể thực hiện được phương pháp lặp đơn. Hệ (*) tương đương với hệ 𝑥1 = −0.06𝑥2 + 0.02𝑥3 + 2 𝑥2 = −0.03𝑥1 + 0.05𝑥3 + 3 𝑥3 = −0.01𝑥1 + 0.02𝑥2 + 5 (**). Ta có ma trận 𝐵 = 0 −0.06 0.02 −0.03 0 0.05 −0.01 0.02 0 có 𝐵 ∞ = 0.08 < 1 và 𝛽 = 2 3 5 . Từ (**) ta có công thức lặp 𝑋(𝑘+1) = 𝐵𝑋(𝑘) + 𝛽, ∀𝑘 ≥ 0 với 𝑋(0) = 𝛽 = 2 3 5 , tức là giải hệ 𝑥1 (𝑘+1) 𝑥2 (𝑘+1) 𝑥3 (𝑘+1) = 0 −0.06 0.02 −0.03 0 0.05 −0.01 0.02 0 × 𝑥1 (𝑘) 𝑥2 (𝑘) 𝑥3 (𝑘) + 2 3 5 với 𝑥1 (0) 𝑥2 (0) 𝑥3 (0) = 2 3 5 , ∀𝑘 ≥ 0 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) − 𝑋∗ ∞ ≤ 𝐵 ∞ 1− 𝐵 ∞ 𝑋(3) − 𝑋(2) ∞ = 4.4× 10−5. 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 = . Bài giảng Phương Pháp Tính 2015 25 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 trận) 2 = 3 = 5 = 2 3 5 Nhập ma trận cấp 3 × 1 Mat B 𝑆𝑕𝑖𝑓𝑡 4 2 2 1 (𝑐𝑕ọ𝑛 𝑚𝑎 𝑡𝑟ậ𝑛) 0 = −0.06 = 0.02 = 0 = 0 −0.06 0.02 −0.03 0 0.05 −0.01 0.02 0 Nhập ma trận cấp 3 × 3 (thực hiện ngay khi màn hình đã nhập Mat A) MatC 𝑆𝑕𝑖𝑓𝑡 4 2 3 3 (𝑐𝑕ọ𝑛 𝑚𝑎 𝑡𝑟ậ𝑛) 2 = 3 = 5 = 2 3 5 Nhập ma trận cấp 3 × 1 (thực hiện ngay khi 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 = Kết quả Ans = 1.92 3.19 5.04 (tức là 𝑋(1)) + phép tính 𝑋(2) = 𝐵𝑋(1) + 𝛽 tức là 𝑀𝑎𝑡 𝐵 × 𝑀𝑎𝑡 𝐴𝑛𝑠 + 𝑀𝑎𝑡 𝐶 𝑆𝑕𝑖𝑓𝑡 4 3 4 (Mat B) × 𝑆𝑕𝑖𝑓𝑡 4 3 6 (Mat Ans) + 𝑆𝑕𝑖𝑓𝑡 4 3 5 = Kết quả Ans = 1.9094 3.1944 5.0446 (tức là 𝑋(2)) + 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) Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 26 Đế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 hàm X 2 = Y 3 = A 5 = −0.06𝑌 + 0.02𝐴 + 2: − 0.03𝑋 + 0.05𝐴 + 3: − 0.01𝑋 + 0.02 𝑌 + 5 Nhập các hàm trong vế phải 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 𝑋(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 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 Bài giảng Phương Pháp Tính 2015 27 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 𝑋(𝑘) 𝑘≥0 theo công thức 𝑋(𝑘+1) = 𝐵𝑋(𝑘+1) + 𝐵𝑋(𝑘) + 𝛽, ∀𝑘 ≥ 0 với 𝑋(0) tùy ý, thường chọn 𝑋(0) = 𝛽. - Điều kiện hội tụ: 𝐵 𝑝 ≤ 𝑞 < 1. - Sai số (đánh giá theo chuẩn . ∞). Với 𝑝1 = 0, 𝑝𝑖 = |𝑏𝑖𝑗 | 𝑖−1 𝑗=1 , 𝑞𝑖 = |𝑏𝑖𝑗 | 𝑛 𝑗=𝑖 , 𝜇 = max𝑖 𝑞𝑖 1−𝑝𝑖 , 𝑖 = 1,2, , 𝑛. + Sai số tiên nghiệm: 𝑋(𝑘+1) − 𝑋∗ ∞ ≤ 𝜇𝑘+1 1−𝜇 𝑋(1) − 𝑋(0) ∞ + 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. Nguyễn Xuân Thảo- GV Khoa CNTT- Học viện nông nghiệp Việt Nam 28 + 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 0.04𝑥1 + 0.08𝑥2 + 4𝑥3 = 20 (I) Ta có ma trận hệ số 𝐴 = 4 0.24 −0.08 0.09 3 −0.15 0.04 0.08 4 là ma trận chéo trội. Ta có thể thực hiện được phương pháp lặp đơn. Hệ (*) tương đương với hệ 𝑥1 = −0.06𝑥2 + 0.02𝑥3 + 2 𝑥2 = −0.03𝑥1 + 0.05𝑥3 + 3 𝑥3 = −0.01𝑥1 + 0.02𝑥2 + 5 (II). Ta có ma trận 𝐵 = 0 −0.06 0.02 −0.03 0 0.05 −0.01 0.02 0 có 𝐵 ∞ = 0.08 < 1 và 𝛽 = 2 3 5 . Ta tách 𝐵 = 𝐵 + 𝐵 trong đó 𝐵 = 0 0 0 −0.03 0 0 −0.01 0.02 0 và 𝐵 = 0 −0.06 0.02 0 0 0.05 0 0 0 Từ đó ta có công thức lặp 𝑋(𝑘+1) = 𝐵 𝑋(𝑘+1) + 𝐵𝑋(𝑘) + 𝛽, ∀𝑘 ≥ 0 với 𝑋(0) = 𝛽 = 2 3 5 , tức là giải hệ 𝑥1 (𝑘+1) 𝑥2 (𝑘+1) 𝑥3 (𝑘+1) = 0 0 0 −0.03 0 0 −0.01 0.02 0 𝑥1 (𝑘+1) 𝑥2 (𝑘+1) 𝑥3 (𝑘+1) + 0 −0.06 0.02 0 0 0.05 0 0 0 × 𝑥1 (𝑘) 𝑥2 (𝑘) 𝑥3 (𝑘) + 2 3 5 với 𝑥1 (0) 𝑥2 (0) 𝑥3 (0) = 2 3 5 , ∀𝑘 ≥ 0 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) − 𝑋∗ ∞ ≤ 𝜇 1−𝜇 𝑋(4) − 𝑋(3) ∞ = 0. Bài giảng Phương Pháp Tính 2015 29 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 hàm X Y 3 = A 5 = X=−0.06𝑌 + 0.02𝐴 + 2: 𝑌 = −0.03𝑋 + 0.05𝐴 + 3: 𝐴 = −0.01𝑋 + 0.02 𝑌 + 5 Nhập các hàm trong hệ phương trình. 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 𝑋(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 = 2,3, Chỉ cần bấm phím = 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