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

Ở mỗi bước của phương pháp, trung điểm  được xác định và giá trị . Nếu , 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  trái dấu, hoặc  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 < b, f(a)*f(b) < 0
 đầu ra: giá trị xấp xỉ nghiệm phương trình f(x) = 0 nhỏ hơn sai số cho phép TOL
 cho n = 1
 khi n  nmax: 
 > c = (a+b)/2
 > nếu f(c) = 0 hoặc (b-a)/2 < TOL
 >> 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

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

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

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

 

Thuật toán tìm nghiệm