Phương pháp chia đôi

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 formula_1 với biến thực formula_2 và hàm số liên tục formula_3 trên đoạn formula_4 mà ở đó, formula_5. Khi ấy, theo định lý giá trị trung bình, hàm số liên tục formula_6 phải có ít nhất một nghiệm trong khoảng formula_7. 

Ở mỗi bước của phương pháp, trung điểm formula_8 được xác định và giá trị formula_9. Nếu formula_10, 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 formula_11 trái dấu, hoặc formula_12 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.

=== 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
formula_14
Do formula_15 và formula_16, hơn nữa hàm số formula_6 liên tục, nên formula_6 có ít nhất một nghiệm trên đoạn formula_19.
Khi ấy, với formula_20, ta xác định trung điểm 
formula_21,
sau đó tính formula_22. Do formula_23 cùng dấu với formula_24, ta thay formula_25 bằng formula_26, sau đó tiếp tục lặp lại phương pháp này với formula_27. 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, formula_28 dần hội tụ đến nghiệm đúng của phương trình là formula_29.

== Sự hội tụ và sai số ==
Phương pháp này đảm bảo dãy formula_30 xác định bằng phương pháp chia đôi sẽ hội tụ tới nghiệm đúng formula_31 của phương trình formula_1 trên đoạn formula_33 nếu formula_3 là hàm số liên tục và formula_5. 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ứ formula_36, sai số tương đối của phương pháp này được đánh giá bởi công thức
formula_37

Bằng công thức trên, khi ấy để sai số nhỏ hơn một giá trị formula_38 tuỳ ý, số bước lặp formula_36 được chặn trên bởi công thức
formula_40.
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ố formula_38 sau formula_42 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