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 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. 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.
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. 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.
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.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. Số lần lặp k lớn hơn hoặc bằng một số N xác định trước.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).
Chia đôi đoạn [a, b] và đặt c = là điểm nằm giữa của [a, b]. Nếu 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. Tìm đoạn mà chứa nghiệm và tiếp tục chia đôi đoạn đó.
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.
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]. Đầu ra: Một phép xấp xỉ nghiệm của f (x) = 0 trong [a0 , b0 ]., 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. Tìm nghiệm dương của f (x) = x3 − 6x2 + 11x − 6 = 0 bằng phương pháp chia đô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. Cả hai giả thiết trong định lý giá trị trung gian đều đúng với f (x) trên đoạn [2. (i) f (x) = x3 − 6x2 + 11x − 6 liên tục trên [2. 7 Do đó, theo định lý giá trị trung bình tồn tại nghiệm của f (x) = 0 trong [2.
Dữ liệu đầu vào. 2 Rõ ràng các phép lặp hội tụ dần nghiệm chính xác x = 3. 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. Tuy nhiên, tốc đội hội tụ của phương pháp chia đôi có thể rất chậm.
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 bk − a k ck = 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. b0 − a0 Độ dài của đoạn sau N phép lặp là. Để thu được độ chính xác ε ta 2N b0 − a0 phải có < ε, tức là 2N 2−N (b0 − a0 ) ≤ ε hay b0 − a 0 2N ≥.
ε Suy ra N log10 2 ≥ log10 (b0 − a0 ) − log10 ε hay log10 (b0 − a0 ) − log10 ε N≥. 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 log10 (b0 − a0 ) − log10 ε N≥ .1) log10 2 Nhận xét 1. Số lần lặp N chỉ phụ thuộc vào đoạn [a0 , b0 ] chứa nghiệm. 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 log10 (1. 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. 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ể.3 Phương pháp lặp Định nghĩa 1.
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. 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. 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.
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.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]. 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. 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. 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. 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.