Tài liệu ứng dụng phương pháp gần đúng giải phương trình đại số không tuyến tính

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN KHẮC TRIỆU ỨNG DỤNG PHƯƠNG PHÁP GẦN ĐÚNG GIẢI PHƯƠNG TRÌNH ĐẠI SỐ KHÔNG TUYẾN TÍNH LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội, 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN KHẮC TRIỆU ỨNG DỤNG PHƯƠNG PHÁP GẦN ĐÚNG GIẢI PHƯƠNG TRÌNH ĐẠI SỐ KHÔNG TUYẾN TÍNH LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán giải tích Mã số : 60 46 01 02 Người hướng dẫn khoa học TS. Nguyễn Văn Hùng HÀ NỘI, 2017 Mục lục Mở đầu 1 1 KIẾN THỨC CHUẨN BỊ 1.1 . . . . . . . . . . . . 3 1.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Ý nghĩa hình học của nghiệm . . . . . . . . . . 3 1.1.3 1.2 Nghiệm của phương trình một ẩn 3 Sự tồn tại nghiệm thực của phương trình (1.1) . 4 Khoảng phân li nghiệm . . . . . . . . . . . . . . . . . . 5 1.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 1.2.2 5 Phương pháp tìm khoảng phân li nghiệm của phương trình f (x) = 0 . . . . . . . . . . . . . . . . . . . . 1.3 6 Sai số . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.1 7 1.3.2 2 Khái niệm . . . . . . . . . . . . . . . . . . . . . . Các loại sai số: . . . . . . . . . . . . . . . . . . . 7 MỘT SỐ PHƯƠNG PHÁP GẦN ĐÚNG GIẢI PHƯƠNG TRÌNH ĐẠI SỐ PHI TUYẾN 8 2.1 Các bước giải gần đúng phương trình f (x) = 0 . . . . . 8 2.2 Phương pháp chia đôi . . . . . . . . . . . . . . . . . . . 9 2.3 Phương pháp điểm sai (Method of False Position) . . . 11 2.4 Phương pháp dây cung . . . . . . . . . . . . . . . . . . 13 2.5 20 2.6 Phương pháp lặp đơn . . . . . . . . . . . . . . . . . . . 26 2.7 3 Phương pháp Newton . . . . . . . . . . . . . . . . . . . Đánh giá tốc độ hội tụ của các phương pháp . . . . . . . 29 ỨNG DỤNG 3.1 Tìm nghiệm gần đúng của phương trình đại số không tuyến tính f (x) = 0 3.2 35 . . . . . . . . . . . . . . . . . . . . Giải một số phương trình bằng phần mềm Maple 35 . . . 50 3.2.1 Giới thiệu phần mềm Maple . . . . . . . . . . . . 50 3.2.2 Chức năng cốt lõi . . . . . . . . . . . . . . . . . . 50 3.2.3 Lập trình Maple cho một số phương pháp giải gần đúng phương trình đại số không tuyến tính . . . . 51 Kết luận 62 Tài liệu tham khảo 63 Lời cảm ơn Tôi xin bày tỏ lòng biết ơn sâu sắc tới TS Nguyễn Văn Hùng. Thầy đã tận tình hướng dẫn và giải đáp những thắc mắc của tôi, giúp đỡ tôi hoàn thành luận văn này. Qua đây, tôi xin chân thành cảm ơn tới các thầy cô giáo phòng Sau đại học, các thầy cô giáo khoa Toán cũng như các thầy cô giáo giảng dạy lớp thạc sĩ K19 chuyên ngành Toán giải tích trường Đại học Sư phạm Hà Nội 2 đã giúp đỡ tôi trong suốt quá trình học tập. Tôi xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè, đồng nghiệp đã luôn quan tâm, động viên và tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập và hoàn thành luận văn. Hà Nội, tháng 6 năm 2017 Tác giả Nguyễn Khắc Triệu Lời cam đoan Tôi xin cam đoan, dưới sự hướng dẫn của TS. Nguyễn Văn Hùng, luận văn thạc sĩ chuyên ngành Toán giải tích với đề tài "Ứng dụng phương pháp gần đúng giải phương trình đại số không tuyến tính" được hoàn thành bởi chính sự nhận thức của bản thân tác giả. Trong suốt quá trình nghiên cứu thực hiện luận văn, tác giả đã kế thừa những thành tựu của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, tháng 06 năm 2017 Tác giả Nguyễn Khắc Triệu 1 MỞ ĐẦU 1. Lý do chọn đề tài Các bài toán thực tế (trong thiên văn, đo đạc ruộng đất,. . . ) dẫn đến việc cần phải giải các phương trình đại số không tuyến tính (hay phương trình phi tuyến), tuy nhiên, các phương trình này thường phức tạp, do đó nói chung khó có thể giải được. Hơn nữa, vì các công thức nghiệm thường phức tạp, cồng kềnh, nên cho dù có công thức nghiệm, việc khảo sát các tính chất nghiệm qua công thức cũng vẫn gặp phải rất nhiều khó khăn. Vì vậy, ngay từ thời Archimedes, các phương pháp gần đúng giải phương trình phi tuyến đã được xây dựng. Ngày nay các phương trình đại số phi tuyến thường được giải bằng các phương pháp gần đúng như: Phương pháp chia đôi, phương pháp lặp, phương pháp Newton. . . Với mong muốn tìm hiểu sâu hơn về việc giải phương trình đại số phi tuyến, dưới sự hướng dẫn của TS Nguyễn Văn Hùng, tôi đã chọn đề tài: “Ứng dụng phương pháp gần đúng giải phương trình đại số không tuyến tính” để thực hiện luận văn của mình. 2. Mục đích nghiên cứu • Luận văn nghiên cứu một số phương pháp gần đúng giải phương trình đại số phi tuyến. 2 • Ứng dụng một số phương pháp gần đúng giải phương trình sơ cấp 3. Nhiệm vụ nghiên cứu Nghiên cứu một số phương pháp gần đúng giải phương trình đại số phi tuyến. 4. Đối tượng và phạm vi nghiên cứu • Đối tượng nghiên cứu:Phương trình đại số phi tuyến. • Phạm vi nghiên cứu: Nghiên cứu các phương pháp gần đúng giải phương trình đại số phi tuyến. 5. Phương pháp nghiên cứu • Vận dụng các kiến thức của Giải tích hàm, Giải tích số. • Thu thập các tài liệu liên quan đến phương trình đại số phi tuyến. • Phân tích, tổng hợp và hệ thống kiến thức liên quan tới phương trình đại số phi tuyến. 6. Đóng góp của luận văn Cố gắng xây dựng luận văn thành một tài liệu tổng quan tốt về đề tài giải gần đúng phương trình đại số không tuyến tính 3 Chương 1 KIẾN THỨC CHUẨN BỊ 1.1 Nghiệm của phương trình một ẩn 1.1.1 Định nghĩa Xét phương trình một ẩn: f (x) = 0 (1.1) trong đó: f là một hàm số cho trước của đối số x Giá trị x0 được gọi là nghiệm của phương trình (1.1) nếu f (x0 ) = 0 Nghiệm của phương trình (1.1) có thể là số thực hoặc số phức, nhưng ở đây ta chỉ khảo sát các nghiệm thực. 1.1.2 Ý nghĩa hình học của nghiệm Các nghiệm của phương trình (1.1) là hoành độ giao điểm của đồ thị hàm số y = f (x) với trục hoành. 4 y y = f (x) O N (a2 ; 0) x M (a1 ; 0) Có thể biến đổi phương trình (1.1) về dạng g(x) = h(x), khi đó nghiệm của phương trình (1.1) là các hoành độ giao điểm của hai đồ thị (C1 ) : y = g(x) và (C2 ) : y = h(x). y y = h(x) y = g(x) x x1 O 1.1.3 x2 Sự tồn tại nghiệm thực của phương trình (1.1) Trước khi tìm cách tính gần đúng nghiệm thực của phương trình (1.1) ta phải kiểm tra xem nghiệm thực đó có tồn tại hay không. Khi đo ta có thể sử dụng đồ thị hoặc sử dụng định lý sau. Định lí 1.1. (Bolzano - Cauchy) 5 Nếu hàm số f (x) liên tục trên đoạn [a,b] và thoả mãn điều kiện f (a)f (b) < 0 thì phương trình f (x) = 0 có ít nhất một nghiệm trong khoảng (a,b). Chứng minh. Không mất tính tổng quát giả sử f (a) < 0, f (b) > 0, ta a+b chia đôi đoạn [a,b] bởi điểm chia 2 a+b TH1:f ( ) = 0 ta có định lí được chứng minh. 2 a+b a+b TH2:f ( ) = 0. Đặt c = , khi đó ta xét đoạn [a1 , b1 ]. 2 2 a+b a+b Với a1 = a, b1 = nếu f ( ) > 0. 2 2 a+b a+b Với a1 = , b1 = b nếu f ( ) < 0. 2 2 a1 + b1 Ta lại chia đôi đoạn [a1 , b1 ] bởi điểm chia . Có thể xảy ra hai 2 khả năng. a1 + b1 Khả năng 1: f ( ) = 0 ta có định lí được chứng minh. 2 Khả năng 2: Ta lại thu được đoạn [a2 , b2 ] là một trong hai nửa của đoạn [a1 , b1 ] sao cho f (a2 )f (b2 ) < 0. Ta tiếp tục lặp các đoạn đó. Khi đó hoặc sau một số hữu hạn bước ta sẽ gặp trường hợp f ( ai + b i )= 2 0. Và khi đó định lí được chứng minh. Hoặc được một dãy vô hạn các đoạn chứa nhau. Khi đó đối với đoạn thứ n, [an , bn ], (n = 1, 2, 3...) ta sẽ có f (an ) < 0, f (bn ) > 0 và độ dài của b−a đoạn bằng bn − an = n . 2 Dãy các đoạn ta lập được thoả mãn các điều kiện của bổ đề về dãy b−a các đoạn lồng nhau, bởi vì theo trên lim (bn − an ) = lim ( n ) = 0. n→∞ n→∞ 2 6 Vì vậy cả hai dãy { an } , { bn } dần tới giới hạn chung lim (an ) = n→∞ lim (bn ) = c n→∞ Mà rõ ràng c ∈ [a, b]. Ta chứng minh điểm c thoả mãn yêu cầu của định lí Thật vậy do tính liên tục của hàm số tại x = c, ta có f (c) = lim f (an ) ≤ 0 n→∞ Và f (c) = lim f (bn ) ≥ 0 n→∞ Vậy f (c) = 0. Ta có định lí được chứng minh. 1.2 Khoảng phân li nghiệm 1.2.1 Định nghĩa Định nghĩa 1.1. Đoạn [a, b] (hoặc khoảng (a, b)) được gọi là khoảng phân li nghiệm của phương trình f (x) = 0 nếu nó chứa một và chỉ một nghiệm của phương trình đó. Định lí 1.2. Nếu hàm số y = f (x) liên tục, đơn điệu trên [a, b] và f (a)f (b) ≤ 0 thì [a, b] là một khoảng phân li nghiệm của phương trình f (x) = 0. Chứng minh. Theo định lí (Bolzano - Cauchy) ta có phương trình f (x) = 0 có ít nhất một nghiệm trên [a, b]. Giả sử c1 , c2 là hai nghiệm phân biệt của phương trình f (x) = 0 Ta có f (c1 ) = f (c2 ) = 0. Vì hàm số y = f (x) liên tục, đơn điệu trên [a, b] nên c1 = c2 (trái với giả thiết). 7 Do đó phương trình f (x) = 0 có nghiệm duy nhất trên [a, b] Vì vậy theo định nghĩa 1 thì [a, b] là một khoảng phân li nghiệm của phương trình f (x) = 0. Nếu f (x) có đạo hàm thì điều kiện đơn điệu có thể thay bằng điều kiện không đổi dấu của đạo hàm. Ta có định lí sau Định lí 1.3. Nếu hàm số y = f (x) liên tục, đạo hàm f (x) không đổi dấu trên [a, b] và f (a)f (b) < 0 thì [a, b] là một khoảng phân li nghiệm của phương trình f (x) = 0. Chứng minh. Ta có hàm số y = f (x) liên tục, đạo hàm f (x) không đổi dấu trên [a, b] nên hàm số y = f (x) liên tục, đơn điệu trên [a, b]. Theo định lí 1.2 hàm số y = f (x) liên tục, đơn điệụ trên [a, b] và f (a)f (b) < 0 thì [a, b] là một khoảng phân li nghiệm của phương trình f (x) = 0. 1.2.2 Phương pháp tìm khoảng phân li nghiệm của phương trình f (x) = 0 a) Phương pháp giải tích Nếu f (x) liên tục, xét dấu của f (x) tại hai đầu mút của miền xác định và tại những điểm xi mà f (xi ) = 0 suy ra ước lượng khoảng phân li nghiệm. Một đa thức bậc n có không quá n nghiệm, vì vậy phương trình đa thức bậc n có không quá n khoảng phân li nghiệm. b) Phương pháp hình học. 8 Vẽ đồ thị của hàm số y = f (x) trên giấy kẻ ô vuông suy ra ước lượng khoảng phân li nghiệm (hoành độ giao điểm của đồ thị hàm số y = f (x) với trục hoành). Trường hợp khó vẽ đồ thị của hàm số y = f (x), có thể biến đổi y = f (x) về hàm tương đương h(x) = g(x). Vẽ đồ thị hàm số y = h(x) và y = g(x) suy ra khoảng phân li nghiệm. 1.3 Sai số Khi giải toán bằng phương pháp gần đúng thì sai số xuất hiện do sự sai lệch giữa giá trị nhận được với nghiệm thực của bài toán, vì vậy ta phải đánh giá sai số để từ đó chọn ra phương án tối ưu nhất. 1.3.1 Khái niệm Giả sử x là số gần đúng của x∗ (x∗ là số đúng), khi đó ∆ = |x − x∗ | gọi là sai số thực sự của x. Vì không xác định được ∆ nên ta xét đến hai loại sai số sau: - Sai số tuyệt đối: Giả sử ∃∆x > 0 đủ bé sao cho |x − x∗ | ≤ ∆x khi đó ∆x gọi là sai số tuyệt đối của x. ∆x - Sai số tương đối: δx = |x| 1.3.2 Các loại sai số: Dựa vào nguyên nhân sai số, ta có các loại sau: - Sai số giả thiết: Xuất hiện do việc giả thiết bài toán đạt được một số điều kiện lí tưởng nhằm làm giảm độ phức tạp của bài toán. 9 - Sai số do số liệu ban đầu: Xuất hiện do việc đo đạc và cung cấp giá trị đầu vào không chính xác. - Sai số phương pháp: Xuất hiện do việc giải bài toán bằng phương pháp gần đúng. - Sai số tính toán: Xuất hiện do quá trình làm tròn số trong quá trình tính toán, quá trình tính toán càng nhiều thì sai số tích luỹ càng lớn. Định lí 1.4. Với hàm số f (x) liên tục và khả vi trên [a, b], ngoài ra ∃m1 : 0 < m1 ≤ |f (x)| , ∀x ∈ [a, b] ⇔ m1 = min |f (x)| và xn ∈ [a, b] [a,b] là xấp xỉ của nghiệm α, khi đó ta có đánh giá: |xn − α| |f (xn )| m1 10 Chương 2 MỘT SỐ PHƯƠNG PHÁP GẦN ĐÚNG GIẢI PHƯƠNG TRÌNH ĐẠI SỐ PHI TUYẾN 2.1 Các bước giải gần đúng phương trình f (x) = 0 Để tìm nghiệm gần đúng của phương trình đại số phi tuyến, ta tiến hành qua hai bước: Bước 1: Tìm khoảng chứa nghiệm Một phương trình nói chung có nhiều nghiệm. Ta cần tìm khoảng chứa nghiệm, tức là khoảng (a, b) trong đó phương trình có nghiệm (có duy nhất nghiệm). Đối với bước này ta có thể dùng phương pháp đồ thị kết hợp các định lí mà toán học hỗ trợ. Bước 2: Giải gần đúng phương trình. Thu hẹp dần khoảng chứa nghiệm để hội tụ được đến giá trị nghiệm gần đúng với độ chính xác cho phép. Nhằm làm cơ sở lí thuyết cho các tính toán trong chương 3, trong chương 2 tác giả xin vắn tắt trình bày nội dung của năm phương pháp thực hiện trong bước này: - Phương pháp chia đôi - Phương pháp điểm sai (Method of False Position). 11 - Phương pháp dây cung - Phương pháp Newton - Phương pháp lặp đơn 2.2 Phương pháp chia đôi a) Bài toán: Giả sử [a, b] là khoảng phân li nghiệm của phương trình f (x) = 0 (1). Tìm nghiệm thực gần đúng của (1) trên [a, b] với sai số không vượt quá ε cho trước. b) Nội dung của phương pháp. y y = f (x) O a x0 x α b y a O y = f (x) x0 x1 α x b 12 - Chọn x0 là điểm giữa [a, b] làm nghiệm gần đúng x0 = a+b 2 + Nếu f (x0 ) = 0 ⇒ x0 là nghiệm đúng ⇒ Dừng. + Nếu f (x0 ) = 0 và sai số ∆x0 ε thì x0 là nghiệm gần đúng cần tìm với sai số ∆x0 ⇒ Dừng + Nếu f (x0 ) = 0 và sai số ∆x0 > ε thì xét dấu f (a)f (x0 ): Nếu f (a)f (x0 ) < 0 thì khoảng phân li nghiệm mới là [a, x0 ] Nếu f (a)f (x0 ) > 0 thì khoảng phân li nghiệm mới là [x0 , b] - Lặp lại phương pháp chia đôi với khoảng phân li nghiệm mới - Quá tình lặp lần lượt cho ta các nghiệm gần đúng x0 , x1 , ... và kết thúc khi tìm được xn với sai số ∆xn ε. c) Đánh giá sai số 2 Gọi α là nghiệm đúng ta có: 1 1 Bước 0: ∆0 = |α − x0 | ≤ 1 (b − a) , ∆x0 = 1 (b − a). 2 2 1 1 1 1 Bước 1: ∆1 = |α − x1 | ≤ (b − a) = 2 (b − a) , ∆x1 = 2 (b − a). 2 2 2 2 ... 1 1 1 Bước n: ∆n = |α − xn | ≤ (b − a) = n+1 (b − a) , ∆xn = n 2 2 2 1 (b − a). n+1 d) Sự hội tụ về nghiệm Ta có: |xn − α| ≤ ⇒ lim |xn − α| ≤ lim 1 1 2n+1 (b − a) (b − a) = 0 ⇒ lim |xn − α| = 0. x→∞ 2n+1 Vậy dãy xn hội tụ về nghiệm của phương trình khi n → ∞. x→∞ x→∞ e) Sơ đồ tóm tắt phương pháp chia đôi. - Cho phương trình f (x) = 0 13 - Ấn định sai số ε cho phép. - Xác định khoảng phân li nghiệm [a, b]. - Giải thuật của phương pháp chia đôi. f) Ưu 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: Hội tụ về nghiệm chậm. 2.3 Phương pháp điểm sai (Method of False Position) a) Ý tưởng của phương pháp y f (b) a x0 O x b f (a) Tận dụng quan sát toán học trong hình trên, bằng kỹ thuật vẽ cát tuyến từ giá trị của hàm tại a tới giá trị của hàm tại b. Và ước lượng nghiệm khi tại đó nó cắt nhau với trục hoành. Dựa trên hai tam giác đồng dạng, được trình bày trong hình trên, ta được: 0 − f (a) 0 − f (b) = x0 − a x0 − b ⇒ (x0 − a)f (b) = (x0 − b)f (a) ⇒ bf (a) − af (b) = x0 (f (a) − f (b)) 14 Từ đó ta có nghiệm x0 theo công thức: bf (a) − af (b) x0 = f (a) − f (b) b−a ⇒ x0 = b − f (b) f (b) − f (a) a−b Hay x0 = a − f (a) f (a) − f (b) b) Nội dung phương pháp Bước 1: Lấy a1 = a, b1 = b. Cho n = 1, 2, 3, ... ta đặt: xn = an − an − b n f (an ) f (an ) − f (bn ) Bước 2: Kiểm tra Nếu f (an )f (xn ) < 0 khi đó nghiệm nằm giữa khoảng (an , xn ) ⇒ chọn an+1 = an , bn+1 = xn Nếu f (an )f (xn ) > 0 khi đó nghiệm nằm giữa khoảng (xn , bn ) ⇒ chọn an+1 = xn , bn+1 = bn Nếu f (an )f (xn ) = 0 khi đó nghiệm là xn Bước 3: Kiểm tra sai số Đặt |εn | = xn+1 − xn xn+1 Nếu |εn | > ε quay lại bước 2. Nếu |εn | = ε dừng thuật toán c) Sự hội tụ của nghiệm Không làm giảm tính tổng quát ta giả sử: