Phương pháp chia đôi

[[Hình:Bisection method.svg|250px|thumb|Hình minh họa phương pháp chia đôi sau vài bước để chia đôi đoạn [a1;b1]. Chấm đỏ thể hiện nghiệm đúng của phương trình.]]

Trong toán học, phương pháp chia đôi (tiếng Anh: bisection method hoặc dichotomy method) là một thuật toán tìm nghiệm cho bất cứ hàm liên tục nào, khi đã biết hai giá trị của hàm đó trái dấu nhau. Như tên gọi, phương pháp này liên tục chia đôi đoạn chứa nghiệm và lựa chọn đoạn con mà ở đó hàm số đổi dấu, khi này theo định lý giá trị trung bình, đoạn này phải chứa nghiệm của hàm số đó. Phương pháp này dù đơn giản và trực quan nhưng có tốc độ chậm, từ đó thường chỉ được sử dụng để xấp xỉ nghiệm, sau đó nghiệm được xấp xỉ sẽ là nghiệm dự đoán cho các phương pháp có tốc độ hội tụ nhanh hơn.
Đối với các đa thức, có nhiều phương pháp hơn để kiểm tra sự tồn tại của nghiệm trên một đoạn như định lý về dấu của Descartes, định lý Sturm, từ đó mở rộng hơn phương pháp chia đôi để tìm đủ tất cả các nghiệm của một đa thức.

Đối với các đa thức, có nhiều phương pháp hơn để kiểm tra sự tồn tại của nghiệm trên một đoạn như định lý về dấu của Descartes, định lý Sturm, từ đó mở rộng hơn phương pháp chia đôi để tìm đủ tất cả các nghiệm của một đa thức.
Đối với các đa thức, có nhiều phương pháp hơn để kiểm tra sự tồn tại của nghiệm trên một đoạn như định lý về dấu của Descartes, định lý Sturm, từ đó mở rộng hơn phương pháp chia đôi để tìm đủ tất cả các nghiệm của một đa thức.

Phương pháp
Phương pháp chia đôi được sử dụng để giải số phương trình f(x) = 0 với biến thực x và hàm số liên tục f trên đoạn [a, b] mà ở đó, f(a)f(b) . Khi ấy, theo định lý giá trị trung bình, hàm số liên tục f(x) phải có ít nhất một nghiệm trong khoảng (a,b) .

Ở mỗi bước của phương pháp, trung điểm c = \dfrac{a+b}{2} được xác định và giá trị f(c) . Nếu f(c) = 0 , phương pháp đã tìm được chính xác nghiệm và dừng lại, nhưng nếu không, thì hoặc f(a), f(c) trái dấu, hoặc f(c), f(b) trái dấu. Khi ấy, đoạn tiếp theo để thực hiện phương pháp chia đôi sẽ là đoạn mà ở đó, hàm số tại hai đầu mút có giá trị trái dấu, sau đó lặp lại quy trình trên. Phương pháp này sẽ tiếp tục cho đến khi độ dài của khoảng trở nên nhỏ đến mức cần thiết.

Dưới đây là một đoạn mã giả miêu tả thuật toán của phương pháp chia đôi.
đầu vào: hàm số f, hai đầu mút a, b, sai số cho phép TOL, số phép lặp nmax
điều kiện: a \le nmax:
> c = (a+b)/2
> nếu f(c) = 0 hoặc (b-a)/2 > nhận về giá trị c, dừng quá trình
> nếu không:
>> nếu f(c) cùng dấu f(a), thay a bằng c
>> nếu f(c) cùng dấu f(b), thay b bằng c
>> n = n + 1
nhận về giá trị c, dừng quá trình

Ví dụ: Tìm nghiệm của một đa thức
Ví dụ này sử dụng phương pháp chia đôi để tìm nghiệm của đa thức
f(x) = x^3 - x - 2 \,.
Do f(1) = (1)^3 - (1) - 2 = -2 và f(2) = (2)^3 - (2) - 2 = +4 \,, hơn nữa hàm số f(x) liên tục, nên f(x) có ít nhất một nghiệm trên đoạn [1, 2] .
Khi ấy, với a_1 = 1, b_1 = 2, , ta xác định trung điểm
c_1 = \dfrac{a_1 + b_1}{2} ,
sau đó tính f(c_1) = -0,125 . Do f(c_1) cùng dấu với f(a_1) , ta thay a_1 = 1 bằng a_2 = 1,5 , sau đó tiếp tục lặp lại phương pháp này với a_2 = 1,5, b_2 = 2 . Xem bảng dưới đây sau 15 bước lặp để tìm giá trị xấp xỉ nghiệm của phương trình.

Sau 15 bước lặp, c_n dần hội tụ đến nghiệm đúng của phương trình là 1,521 .

Sự hội tụ và sai số
Phương pháp này đảm bảo dãy (c_n) xác định bằng phương pháp chia đôi sẽ hội tụ tới nghiệm đúng x^ của phương trình f(x) = 0 trên đoạn [a,b] nếu f là hàm số liên tục và f(a)f(b) . Sai số tuyệt đối của phương pháp này giảm đi một nửa sau mỗi bước, nên phương pháp này hội tụ với tốc độ tuyến tính (bậc nhất). Hơn nữa, ở bước thứ n , sai số tương đối của phương pháp này được đánh giá bởi công thức
|c_n-x^|\le\frac{2^n}.

Bằng công thức trên, khi ấy để sai số nhỏ hơn một giá trị \epsilon tuỳ ý, số bước lặp n được chặn trên bởi công thức
n \le n_{1/2} = \left\lceil\log_2\left(\frac{\epsilon}\right)\right\rceil, .
Lợi điểm duy nhất của phương pháp chia đôi khi xét phương trình trên tập các hàm liên tục là luôn đảm bảo hội tụ tới nghiệm của phương trình với sai số \epsilon sau n_{1/2} bước, tuy nhiên lại có tốc độ hội tụ chậm mà có thể đánh đổi được để lấy tốc độ hội tụ nhanh hơn như phương pháp dây cung, phương pháp Ridders, hay phương pháp Brent. Phương pháp chia đôi cũng có thể được cải thiện để có tốc độ hội tụ tốt hơn mà không bao giờ gặp trường hợp xấu là phương pháp ITP.

Xem thêm

Tìm kiếm nhị phân
Thuật toán Lehmer-Schur
Dãy đoạn lồng nhau

Tham khảo