Tài liệu (Luận văn thạc sĩ) Phương pháp vị trí sai kép

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGÔ THỊ BẮC PHƯƠNG PHÁP VỊ TRÍ SAI KÉP LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên, 10/2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGÔ THỊ BẮC PHƯƠNG PHÁP VỊ TRÍ SAI KÉP LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp toán sơ cấp Mã số: 8460113 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. TẠ DUY PHƯỢNG Thái Nguyên, 10/2018 i Mục lục Mở đầu 1 Chương 1. Các phương pháp số giải gần đúng phương trình 3 1.1 Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Phương pháp chia đôi . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Phương pháp lặp . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Phương pháp Newton-Raphson và một số mở rộng . . . . . . . . 15 1.5 Phương pháp dây cung . . . . . . . . . . . . . . . . . . . . . . . 19 Chương 2. Phương pháp vị trí sai kép 23 2.1 Phương pháp vị trí sai đơn . . . . . . . . . . . . . . . . . . . . . 23 2.2 Phương pháp vị trí sai kép . . . . . . . . . . . . . . . . . . . . . 35 2.3 Lịch sử phương pháp vị trí sai kép . . . . . . . . . . . . . . . . . 46 Kết luận 52 Tài liệu tham khảo 53 1 Mở đầu Nội dung Giải phương trình và hệ phương trình đã được giảng dạy trong trường phổ thông thường chỉ dừng lại ở kỹ thuật giải (phương pháp biến đổi tương đương, đặt ẩn phụ,...) một số lớp phương trình, hệ phương trình tương đối đơn giản. Mặt khác, các bài toán thực tế thường dẫn đến các phương trình và hệ phương trình phức tạp mà chỉ có thể giải nhờ phương pháp gần đúng. Vì vậy, việc đưa các phương pháp giải gần đúng phương trình và hệ phương trình vào chương trình phổ thông là có ý nghĩa. Các phương pháp giải gần đúng phương trình và hệ phương trình phi tuyến đã được trình bày khá kĩ trong các giáo trình Giải tích số, tuy nhiên, phương pháp vị trí sai và phương pháp vị trí sai kép còn chưa được quan tâm đúng mức trong các tài liệu tiếng Việt. Luận văn này có mục đích trình bày các phương pháp giải gần đúng phương trình và hệ phương trình, đặc biệt là phương pháp vị trí sai và phương pháp vị trí sai kép. Luận văn cố gắng minh họa các phương pháp giải gần đúng thông qua các ví dụ tính toán trên máy. Luận văn cũng cố gắng tìm hiểu và trình bày lịch sử của phương pháp vị trí sai kép. Luận văn trình bày các phương pháp số giải phương trình và hệ phương trình, đặc biệt là phương pháp vị trí sai và phương pháp vị trí sai kép trong hai chương: Chương 1. Các phương pháp số giải gần đúng phương trình Nhằm kết nối và làm sáng tỏ phương pháp vị trị sai và phương pháp vị trí sai kép trình bày trong Chương 2, chương này trình bày tổng quan các phương pháp số giải gần đúng phương trình. 2 Chương 2. Phương pháp vị trí sai kép Chương này trình bày phương pháp vị trí sai đơn và phương pháp vị trí sai kép giải phương trình đa thức và giải hệ phương trình tuyến tính. Luận văn được hoàn thành tại Khoa Toán–Tin, trường Đại học Khoa học, Đại học Thái Nguyên, dưới sự hướng dẫn của PGS.TS Tạ Duy Phượng. Tác giả xin được tỏ lòng biết ơn tới lãnh đạo Khoa Toán–Tin và các khoa chức năng của trường Đại học Khoa học, Đại học Thái Nguyên, đã tạo điều kiện tốt nhất cho tác giả trong quá trình học tập và hoàn thành luận văn đúng thời hạn. Tác giả xin chân thành cám ơn PGS.TS Tạ Duy Phượng đã tận tình hướng dẫn tác giả nghiên cứu đề tài và viết luận văn. Xin được cám ơn trường trung học phổ thông Hàn Thuyên đã tạo điều kiện thuận lợi để tác giả hoàn thành nhiệm vụ. Xin được cám ơn gia đình đã thông cảm và động viên khích lệ tác giả hoàn thành khóa học. Thái Nguyên, tháng 10 năm 2018 Người viết luận văn Ngô Thị Bắc 3 Chương 1 Các phương pháp số giải gần đúng phương trình Trong chương này, chúng tôi giới thiệu bài toán tìm nghiệm phương trình phi tuyến, các phương pháp số giải phương trình phi tuyến, bao gồm phương pháp chia đôi, phương pháp lặp, phương pháp Newton, phương pháp dây cung. Các phương pháp được trình bày chi tiết thuật toán và ví dụ minh họa, có so sánh giữa các phương pháp. 1.1 Kiến thức chuẩn bị Nhiều bài toán trong khoa học và kỹ thuật được phát biểu như sau. Bài toán 1.1.1 ([4]). Cho hàm liên tục f (x), tìm số x = ξ sao cho f (ξ) = 0. Các bài toán này được gọi là bài toán tìm nghiệm của phương trình f (x) = 0. Định nghĩa 1.1.2 ([4]). Số x = ξ thỏa mãn f (ξ) = 0 được gọi là một nghiệm của phương trình f (x) = 0 hay một không điểm của hàm f (x). Hàm f (x) có thể là hàm liên tục phi tuyến bất kì. Một số cách giải phương trình phi tuyến có thể là: 1. Tìm nghiệm giải tích: chỉ thực hiện được với một số phương trình đặc biệt. 4 2. Phương pháp đồ thị: hữu ích cho việc đưa ra dự đoán ban đầu cho các phương pháp khác. 3. Phương pháp số: gồm các phương pháp mở và các phương pháp bracket (khoảng). Các phương pháp bracket bắt đầu với khoảng phân ly chứa nghiệm và sử dụng một thủ tục để thu được khoảng phân ly nhỏ hơn chứa nghiệm. Ví dụ như phương pháp chia đôi, phương pháp vị trí sai. Trong các phương pháp mở, phương pháp bắt đầu với một dự đoán ban đầu. Trong mỗi lần lặp, ta tìm một dự đoán mới của nghiệm. Các phương pháp mở thường hữu ích hơn phương pháp bracket nhưng có thể chúng không hội tụ tới nghiệm. Một số phương pháp mở thường gặp là phương pháp lặp đơn, phương pháp Newton-Raphson, phương pháp dây cung. Cách phân loại các phương pháp giải phương trình phi tuyến được minh họa trong hình sau. Hình 1.1: Phân loại các phương pháp giải phương trình phi tuyến Hầu hết các phương pháp số tìm nghiệm về bản chất là phương pháp lặp. Ý tưởng của phương pháp lặp là: Bắt đầu với một phép xấp xỉ ban đầu x0 , xây dựng một dãy lặp {xk } bằng một công thức lặp với hy vọng rằng dãy này hội tụ tới một nghiệm của f (x) = 0. Hai khía cạnh quan trọng của phương pháp lặp là: sự hội tụ và tiêu chuẩn 5 dừng. Việc xác định một tiêu chuẩn dừng thống nhất là phức tạp vì nhiều lý do. Dưới đây là một tiêu chuẩn thô, có thể được sử dụng để dừng một phép lặp trong một chương trình máy tính. Tiêu chuẩn dừng của phương pháp lặp tìm nghiệm ([4]) Chấp nhận x = ck là một nghiệm của f (x) = 0 nếu thỏa mãn một trong các tiêu chuẩn sau: 1. |f (ck )| ≤ ε (Giá trị hàm nhỏ hơn hoặc bằng giới hạn chấp nhận được). |c − ck | 2. k−1 ≤ ε (Sự thay đổi tương đối nhỏ hơn hoặc bằng giới |ck | hạn chấp nhận được). 3. Số lần lặp k lớn hơn hoặc bằng một số N xác định trước. 1.2 Phương pháp chia đôi Như tên gợi ý từ tên của phương pháp, phương pháp này dựa trên việc chia đôi liên tục một khoảng chứa nghiệm. Ý tưởng chính của phương pháp rất đơn giản. Ý tưởng chính: Giả sử f là hàm liên tục trên đoạn [a, b] và f (a).f (b) < 0 thì phương trình f (x) = 0 có nghiệm thực x = ξ nằm trong đoạn [a, b]. a+b là điểm nằm giữa của [a, b]. Nếu 1. Chia đôi đoạn [a, b] và đặt c = 2 f (c) = 0 thì c là nghiệm. Ngược lại, một trong hai đoạn [a, c] hoặc [c, b] sẽ chứa nghiệm. 2. Tìm đoạn mà chứa nghiệm và tiếp tục chia đôi đoạn đó. 3. Tiếp tục quá trình chia đôi cho tới khi nghiệm nằm trong một đoạn đủ nhỏ sao cho đảm bảo độ chính xác yêu cầu. Để thực thi ý tưởng trên, ta phải biết trong mỗi phép lặp đoạn nào trong hai đoạn chứa nghiệm của f (x) = 0. Định lý giá trị trung gian trong giải tích giúp ta xác định khoảng trong mỗi phép lặp. Chứng minh của định lý này có thể xem trong giáo trình giải tích. 6 Định lý 1.2.1 (Định lý giá trị trung gian). Giả sử (i) f (x) liên tục trên đoạn đóng [a, b], và (ii) M là một số bất kỳ nằm giữa f (a) và f (b). Khi đó, tồn tại ít nhất một số c thuộc [a, b] sao cho f (c) = M . Hệ quả: Giả sử (i) f (x) liên tục trên đoạn đóng [a, b], và (ii) f (a) và f (b) ngược dấu. Khi đó tồn tại một nghiệm x = c của f (x) = 0 trong đoạn [a, b]. Thuật toán 1.2.2 (Phương pháp chia đôi, [4]). Đầu vào: f (x) là hàm cho trước, a0 , b0 là hai số thỏa mãn f (a0 )f (b0 ) < 0. Đầu ra: Một phép xấp xỉ nghiệm của f (x) = 0 trong [a0 , b0 ]. Với k = 0, 1, 2, . . ., thực hiện cho tới khi thỏa mãn: a + bk . • Tính ck = k 2 • Sử dụng tiêu chuẩn dừng kiểm tra nếu ck là nghiệm cần tìm. Nếu đúng thì dừng. • Nếu ck không là nghiệm cần tìm, kiểm tra nếu f (ck )f (ak ) < 0. Nếu đúng, đặt bk+1 = ck và ak+1 = ak . Nếu ngược lại, đặt ak+1 = ck , bk+1 = bk . Kết thúc.  Ví dụ 1.2.3. Tìm nghiệm dương của f (x) = x3 − 6x2 + 11x − 6 = 0 bằng phương pháp chia đôi. Giải. Tìm đoạn [a, b] chứa nghiệm. Vì phương pháp chia đôi tìm nghiệm trong một đoạn [a, b] cho trước, đầu tiên ta phải tìm đoạn [a, b] trước. Ta thực hiện theo định lý giá trị trung gian. Cho a0 = 2.5 và b0 = 4. Cả hai giả thiết trong định lý giá trị trung gian đều đúng với f (x) trên đoạn [2.5, 4]. (i) f (x) = x3 − 6x2 + 11x − 6 liên tục trên [2.5, 4]. (ii) f (2.5)f (4) = (−0.375).6 < 0. 7 Do đó, theo định lý giá trị trung bình tồn tại nghiệm của f (x) = 0 trong [2.5, 4]. Dữ liệu đầu vào. f (x) = x3 − 6x2 + 11x − 6 a0 = 2.5, b0 = 4. Lặp lần 1 (k = 0): a0 + b0 = 3.25. 2 Vì f (c0 )f (a0 ) = f (3.25)f (2.5) < 0, đặt b1 = c0 , a1 = a0 . c0 = Lặp lần 2 (k = 1): a1 + b1 = 2.8750. 2 Vì f (c1 )f (a1 ) > 0, đặt a2 = c1 = 2.8750, b2 = b1 . c1 = Lặp lần 3 (k = 2): a1 + b1 = 3.0625. 2 Vì f (c2 )f (a2 ) = f (3.0625)f (2.875) < 0, đặt b3 = c2 , a3 = a2 . c2 = Lặp lần 4 (k = 3): a 2 + b2 = 2.9688. 2 Rõ ràng các phép lặp hội tụ dần nghiệm chính xác x = 3. c3 = Chú ý 1.2.4.  1. Từ phát biểu của thuật toán chia đôi, thuật toán luôn luôn hội tụ tới nghiệm. 2. Tuy nhiên, tốc đội hội tụ của phương pháp chia đôi có thể rất chậm. 3. Có thể ở một lần lặp thứ k nào đó xảy ra việc tính ck có thể bị quá giới hạn máy tính. Tốt hơn ta nên tính ck bằng ck = a k + bk − a k . 2 Tiêu chuẩn dừng Vì đây là một phương pháp lặp, ta phải xác định một số tiêu chuẩn dừng mà cho phép phép lặp kết thúc. Dưới đây là một số tiêu chuẩn dừng thường gặp. 8 Cho ε là sai số cho phép, tức là ta muốn thu được nghiệm với sai số nhiều nhất là ε. Ta tìm số lần lặp ít nhất N cần thiết để phương pháp chia đôi đạt được độ chính xác mong muốn. Độ dài của đoạn sau N phép lặp là b0 − a0 < ε, tức là phải có 2N b0 − a0 . Để thu được độ chính xác ε ta 2N 2−N (b0 − a0 ) ≤ ε hay 2N ≥ b0 − a 0 . ε Suy ra N log10 2 ≥ log10 (b0 − a0 ) − log10 ε hay N≥ log10 (b0 − a0 ) − log10 ε . log10 2 Định lý 1.2.5 ([4]). Số lần lặp N cần thiết trong phương pháp chia đôi để thu được độ chính xác ε xác định bởi N≥ log10 (b0 − a0 ) − log10 ε . log10 2 (1.1) Nhận xét 1.2.6. Số lần lặp N chỉ phụ thuộc vào đoạn [a0 , b0 ] chứa nghiệm. Ví dụ 1.2.7. Tìm số lần lặp ít nhất để thuật toán chia đôi xấp xỉ nghiệm x = 3 của phương trình x3 − 6x2 + 11x − 6 = 0 với sai số cho phép 10−3 . Dữ liệu vào: ( đầu mút của đoạn: a = 2.5, b = 4 sai số cho phép: t = 10−3 . Sử dụng bất đẳng thức (1.1), thế giá trị của a0 và b0 vào trong công thức, ta được N≥ log10 (1.5) − log10 (10−3 ) log10 (1.5) + 3 = = 10.5507. log10 2 log10 2 Cho nên, cần ít nhất 11 lần lặp để thu được độ chính xác mong muốn khi sử dụng phương pháp chia đôi. 9 Nhận xét 1.2.8. Vì số lần lặp N cần để thu được độ chính xác phụ thuộc vào độ dài ban đầu của khoảng chứa nghiệm, ta nên cố gắng chọn đoạn ban đẩu [a0 , b0 ] nhỏ có thể. 1.3 Phương pháp lặp Định nghĩa 1.3.1 ([4]). Số (điểm) ξ được gọi là điểm bất động của hàm (ánh xạ) g(x) nếu g(ξ) = ξ. Giả sử phương trình f (x) = 0 được viết lại thành x = g(x), tức là f (x) = x − g(x) = 0. Khi đó bất kỳ điểm bất động ξ của g(x) là một nghiệm của phương trình f (x) = 0 bởi vì f (ξ) = ξ − g(ξ) = ξ − ξ = 0. Do đó, ta có thể tìm nghiệm của f (x) = 0 bằng cách tìm điểm bất động của x = g(x), mà tương đương với tìm nghiệm của phương trình f (x) = 0. Việc tìm nghiệm của phương trình f (x) = 0 bằng cách tìm điểm bất động của x = g(x) ngay lập tức gợi ý thuật toán lặp như sau. Bắt đầu với giá trị đề xuất ban đầu x0 và lập dãy {xk } xác định bởi xk+1 = g(xk ), k = 0, 1, 2, . . . . Nếu dãy {xk } hội tụ, thì {limk→∞ xk = ξ} là nghiệm của f (x) = 0. Từ đó lại phát sinh câu hỏi: Bài toán 1.3.2 ([4]). Cho f (x) = 0 trong đoạn [a, b]. Bằng cách nào ta viết f (x) = 0 dưới dạng x = g(x) sao cho dãy {xk } xác định bởi xk+1 = g(xk ) sẽ hội tụ tới nghiệm x = ξ với bất kỳ cách chọn phép xấp xỉ ban đầu x0 ? Cách đơn giản nhất để viết f (x) = 0 dưới dạng x = g(x) là cộng x vào cả hai vế, tức là x = f (x) + x = g(x). 10 Nhưng không phải lúc nào ta cũng làm được điều này để được dãy lặp hội tụ. Thật vậy, xét lại Ví dụ 1.2.3. Ta có f (x) = x3 − 6x2 + 11x − 6 = 0. Định nghĩa g(x) = x + f (x) = x3 − 6x2 + 12x − 6. Ta biết phương trình có nghiệm thuộc [2.5, 4], cụ thể có nghiệm x = 3. Bắt đầu phép lặp xk+1 = g(xk ) với x0 = 3.5. Khi đó, ta có x1 = g(x0 ) = 5.375, x2 = g(x1 ) = g(5.3750) = 40.4434, x3 = g(x2 ) = g(40.4434) = 5.6817 × 104 , x4 = g(x3 ) = g(5.6817 × 104 ) = 1.8340 × 1014 . Rõ ràng dãy {xn } phân kỳ. Sự hội tụ và phân kỳ của phương pháp lặp được minh họa bằng đồ thị sau. Hình 1.2: Sự hội tụ của phương pháp lặp điểm bất động Định lý sau cho ta điều kiện đủ của g(x) để đảm bảo sự hội tụ của dãy {xk } với bất kỳ phép xấp xỉ x0 trong [a, b]. Định lý 1.3.3 (Lặp điểm bất động, [4]). Cho f (x) = 0 viết dưới dạng x = g(x). Giả sử g(x) thỏa mãn các tính chất sau: 11 (i) Với mọi x thuộc [a, b], g(x) ∈ [a, b], tức là g(x) nhận mọi giá trị giữa a và b. (ii) g 0 (x) tồn tại trên (a, b) với tính chất rằng tồn tại hằng số dương 0 < r < 1 sao cho |g 0 (x)| ≤ r, với mọi x ∈ (a, b). Khi đó, (i) tồn tại duy nhất điểm bất động x = ξ của g(x) trong [a, b]. (ii) với bất kỳ x0 ∈ [a, b], dãy {xk } xác định bởi xk+1 = g(xk ), k = 0, 1, . . . hội tụ tới điểm bất động x = ξ, tức là hội tụ tới nghiệm ξ của f (x) = 0. Định lý này là hệ quả của định lý điểm bất động Banach trong không gian metric đầy đủ. Tuy nhiên, để thuận lợi trong sử dụng, ta sẽ chứng minh bằng kiến thức sơ cấp. Chứng minh của định lý lặp điểm bất động cần tới hai định lý quan trọng trong giải tích: định lý giá trị trung gian và định lý giá trị trung bình. Định lý giá trị trung gian đã được phát biểu trước đây. Bây giờ ta sẽ phát biểu định lý giá trị trung bình. Định lý 1.3.4 (Định lý giá trị trung bình). Cho f (x) là hàm thỏa mãn (i) nó liên tục trên [a, b]. (ii) nó khả vi trên (a, b). Khi đó tồn tại c thuộc (a, b) sao cho f (b) − f (a) = f 0 (c). b−a Chứng minh của Định lý 1.3.3. Chứng minh gồm ba bước: sự tồn tại, tính duy nhất, và sự hội tụ. Vì một điểm bất động của g(x) là một nghiệm của f (x) = 0, điều này đồng nghĩa với chứng minh tồn tại một điểm bất động trong [a, b] và nó là duy nhất. 12 Đầu tiên, xét trường hợp g(a) = a hoặc g(b) = b. Nếu g(a) = a, thì x = a là một điểm bất động của g(x). Do đó, x = a là nghiệm của f (x) = 0. Nếu g(b) = b, thì x = b là một điểm bất động của g(x). Do đó, x = b là nghiệm của f (x) = 0. Tiếp theo, xét trường hợp tổng quát khi hai giả thiết trên không đúng. Tức là g(a) 6= a và g(b) 6= b. Trong trường hợp này, g(a) > a và g(b) < b bởi vì theo giả thiết thiết (i), cả g(a) và g(b) thuộc [a, b] và vì g(a) 6= a và g(b) 6= b. Bây giờ, đặt h(x) = g(x) − x. Ta sẽ chỉ ra h(x) thỏa mãn cả hai giả thiết của định lý giá trị trung gian. Vì g(x) liên tục, h(x) cũng liên tục trên [a, b]. Ta có h(a) = g(a) − a > 0 và h(b) = g(b) − b < 0. Nên theo định lý giá trị trung gian, tồn tại số c thuộc đoạn [a, b] sao cho h(c) = 0. Điều này có nghĩa là g(c) = c. Tức là x = c là một điểm bất động. Điều này chứng minh phần sự tồn tại trong định lý. Ta sẽ chứng minh tính duy nhất bằng phản chứng. Giả sử ξ1 và ξ2 là hai điểm bất động của g(x) trong [a, b] và ξ1 6= ξ2 . Vì g(x) khả vi nên nó liên tục trên đoạn [ξ1 , ξ2 ]. Nên theo định lý giá trị trung bình, tồn tại c ∈ (ξ1 , ξ2 ) sao cho g(ξ2 ) − g(ξ1 ) = g 0 (c). ξ2 − ξ1 Do g(ξ1 ) = ξ1 , g(ξ2 ) = ξ2 , ta được ξ2 − ξ1 = g 0 (c). ξ2 − ξ1 Tức là g 0 (c) = 1, mẫu thuẫn với giả thiết (ii). Do đó, ξ1 = ξ2 . Cho ξ là một nghiệm của f (x) = 0. Khi đó sai số tuyệt đối tại bước thứ k + 1 là ek+1 = |ξ − xk+1 |. (1.2) Để chứng minh dãy hội tụ, ta cần chỉ ra limk→∞ ek+1 = 0. Áp dụng định lý giá trị trung bình cho g(x) trong [xk , ξ]. Vì g(x) cũng thỏa mãn cả hai giả thiết của định lý giá trị trung bình trong đoạn [xk , ξ], ta được g(ξ) − g(xk ) = g 0 (c), ξ − xk (1.3) 13 trong đó xk < c < ξ. Vì x = ξ là một điểm bất động của g(x), nên g(ξ) = ξ. Ngoài ra, từ phép lặp x = g(x), ta có xk+1 = g(xk ). Nên từ (1.3) ta có ξ − xk+1 = g 0 (c). ξ − xk Lấy trị tuyệt đối cả hai vế ta có |ξ − xk+1 | = |g 0 (c)| |ξ − xk | (1.4) ek+1 = |g 0 (c)| ≤ r. ek (1.5) hay Từ đây ta có ek+1 ≤ rek . Vì hệ thức (1.5) đúng với mọi k, ta có ek ≤ rek−1 . . Tiếp tục quá trình này, cuối cùng ta có ek+1 ≤ rk+1 e0 , trong e0 là sai số ban đầu. Do r < 1, ta có rk+1 → 0 khi k → ∞. Do đó, lim ek+1 = lim |xk+1 − ξ| ≤ lim rk+1 e0 = 0. k→∞ k→∞ k→∞ Điều này chứng minh dãy {xk } hội tụ tới x = ξ và x = ξ là điểm bất động duy nhất của g(x). Ví dụ 1.3.5. Tìm nghiệm dương của x3 − 6x2 + 11x − 6 trong đoạn [2.75, 4] sử dụng phương pháp lặp điểm bất động. Giải. Ta viết f (x) = 0 dưới dạng x = g(x) sao cho thỏa mãn các giả thiết của Định lý 1.3.3. Ta đã thấy ở trên rằng cách viết g(x) = x + f (x) = x3 − 6x2 + 12x − 6 không thỏa mãn. Bây giờ ta viết f (x) = 0 dưới dạng x= 1 (−x3 + 6x2 + 6) = g(x). 11 Khi đó, với mọi x ∈ [2.75, 4] thì g(x) ∈ [2.75, 4] (g(2.75) = 2.7798, g(4) = 1 (−3x2 + 12x) giảm trong [2.75, 4] và nhỏ hơn 1 với mọi x 3.4545). g 0 (x) = 11 trong [2.75, 4] (g 0 (2.75) = 0.9375 và g 0 (4) = 0). Do đó, cả hai giả thiết trong Định lý 1.3.3 được thỏa mãn. Theo Định lý 1.3.3, với bất kỳ x0 thuộc [2.75, 4], dãy {xk } hội tụ về điểm bất động. Bắt đầu với x0 = 3.5 và sử dụng phép lặp xk+1 = g(xk ) = 1 (−x3 + 6x2 + 6), 11 k = 0, 1, 2, . . . , 11. 14 Ta thu được x0 = 3.5 x1 = g(x0 ) = 3.329545455 x2 = g(x1 ) = 3.236756342 x3 = g(x2 ) = 3.177215941 x4 = g(x3 ) = 3.135923768 x5 = g(x4 ) = 3.105943352 x6 = g(x5 ) = 3.083511734 x7 = g(x6 ) = 3.066373777 x8 = g(x7 ) = 3.05307696 x9 = g(x8 ) = 3.042644693 x10 = g(x9 ) = 3.034388089 x11 = g(x10 ) = 3.027809501. Rõ ràng dãy này hội tụ tới nghiệm x = 3.  Ví dụ 1.3.6. Tìm nghiệm của x − cos x = 0 trong 0, π2 .
Giải. Ta viết f (x) = 0 dưới dạng x = g(x) sao cho xk+1 = g(xk ) hội tụ với bất kỳ cách chọn x0 trong 0, π2 . Từ f (x) = x − cos x = 0, ta thu được x = cos x.   Do đó, nếu ta chọn g(x) = cos x, thì với mọi x ∈ 0, π2 , g(x) ∈ 0, π2 , g 0 (x) =     − sin x, |g 0 (x)| < 1 trong 0, π2 . Do đó cả hai tính chất của Định lý 1.3.3 được
thỏa mãn. Theo định lý lặp điểm bất động, phép lặp phải hội tụ với bất kỳ cách chọn x0 ∈ 0, π2 . Điều này được kiểm chứng bằng các tính toán sau (trên
máy tính Caiso fx-570VN PLUS). π 4 x1 = 0.7071067812 x0 = x2 = 0.7602445971 x3 = 0.7246674809 x4 = 0.7487198858 15 x5 = 0.7325608446 x6 = 0.7434642113 x7 = 0.7361282565 x8 = 0.7410736871 x9 = 0.737744159 x10 = 0.7399877648.  1.4 Phương pháp Newton-Raphson và một số mở rộng Phương pháp Newton là một cách chọn đặc biệt của hàm g(x) trong phương pháp lặp. Giả sử f 00 (x) tồn tại và liên tục trên [a, b] và ξ là một nghiệm đơn của f (x), tức là f (ξ) = 0 và f 0 (ξ) 6= 0. Chọn g(x) = x − Khi đó g 0 (x) = 1 − f (x) . f 0 (x) (f 0 (x))2 − f (x)f 00 (x) f (x)f 00 (x) = . (f 0 (x))2 (f 0 (x))2 f (ξ)f 00 (ξ) Vì f (ξ) = 0 và 6= 0 nên = = 0. Do g 0 (x) liên tục, điều (f 0 (ξ))2 này có nghĩa tồn tại một lân cận của nghiệm x = ξ sao cho với mọi điểm x f 0 (ξ) g 0 (ξ) trong lân cận, |g 0 (x)| < 1. Do đó, nếu g(x) được chọn như bên trên và phép xấp xỉ ban đầu x0 được chọn sao cho đủ gần x = ξ, thì phương pháp lặp điểm bất động đảm bảo sự hội tụ. Điều này dẫn tới phương pháp cổ điển sau mà còn được gọi là phương pháp Newton hay phương pháp Newton-Raphson. Thuật toán 1.4.1 (Phương pháp Newton, [4]). Đầu vào: Hàm f (x) cho trước, phép xấp xỉ ban đầu x0 , sai số cho phép ε, số lần lặp tối đa N . Đầu ra: Nghiệm xấp xỉ x = ξ hoặc thông báo thuật toán không hội tụ. 16 Giả thiết: x = ξ là một nghiệm đơn của f (x). Với k = 0, 1, . . . thực hiện cho tới khi hội tụ hoặc không hội tụ. • Tính f (xk ), f 0 (xk ). • Tính xk+1 = xk − f (xk ) . f 0 (xk ) • Kiểm tra điều kiện hội tụ: dừng nếu |f (xk )| < ε, hoặc |xk+1 − xk | < ε, |xk | hoặc k > N .  Kết thúc. Định nghĩa 1.4.2 ([4]). Phép lặp xk+1 = xk − Newton. f (xk ) được gọi là phép lặp f 0 (xk ) Ta có giải thích hình học của phương pháp Newton như sau: • Đầu tiên x1 có thể được coi như giao điểm với trục Ox của đường tiếp tuyến của đồ thị f (x) tại (x0 , f (x0 )). • Phép xấp xỉ thứ hai x2 là giao điểm với trục Ox của đường tiếp tuyến của đồ thị f (x) tại (x1 , f (x1 )) và tiếp tục. Hình 1.3: Biểu diễn hình học của phương pháp Newton Ví dụ 1.4.3. Tìm nghiệm thực dương của f (x) = cos x − x3 = 0. 17 Giải. Do f (0) = 1, f (1) = cos 1 − 1 < 0, không điểm dương phải nằm giữa 0 và 1. Lấy x0 = 0.5. Sử dụng công thức: xk+1 = xk − f (xk ) . f 0 (xk ) Tính f 0 (x) = − sin x − 3x2 . Ta có các phép lặp: x1 = x0 − x2 = x1 − x3 = x2 − x4 = x3 − x5 = x4 − f (x0 ) f 0 (x0 ) f (x1 ) f 0 (x1 ) f (x2 ) f 0 (x2 ) f (x3 ) f 0 (x3 ) f (x4 ) f 0 (x4 ) = 0.5 − cos(0.5) − (0.5)3 = 1.112141637 − sin(0.5) − 3(0.5)2 = 0.9096726937 = 0.8672638182 = 0.8654771353 = 0.8654740331.  Chú ý 1.4.4 ([4]). 1. Ta có thể thu được lựa chọn khôn ngoan của x0 bằng cách vẽ đồ thị của f (x) nếu có thể. Tuy nhiên, có vẻ như không có hướng dẫn rõ ràng về cách chọn điểm bắt đầu x0 đảm bảo sự hội tụ của phương pháp Newton đến một nghiệm mong muốn. 2. Nếu x0 xa nghiệm, phương pháp Newton có thể phân kỳ. 3. Với một số hàm, điểm bắt đầu có thể mắc vào lặp vô hạn lần theo nghĩa rằng dãy các phép lặp sẽ dao động và không hội tụ về nghiệm. Tính căn bậc hai của một số dương A: √ √ Việc tính A tương đương với giải phương trình x2 − A = 0. Do đó, số A có thể được tính bằng cách áp dụng phương pháp Newton giải phương trình f (x) = x2 − A. Vì f 0 (x) = 2x, ta có thuật toán toán sau để tính căn bậc hai của số dương A. Thuật toán 1.4.5. (Phương pháp Newton tính √ A)