Phương pháp chia đôi

Hình minh họa phương pháp chia đôi sau vài bước để chia đôi đoạn [a₁;b₁]. 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

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)<0$. 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 < 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 TOLcho n = 1khi n $\leq$ 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 + 1nhậ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.

Bước lặp thứ...	$a_{n}$	$b_{n}$	$c_{n}$	$f(c_{n})$
1	1	2	1.5	−0.125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1.5625	0.2521973
5	1.5	1.5625	1.5312500	0.0591125
6	1.5	1.5312500	1.5156250	−0.0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	−0.0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	−0.0051789
11	1.5205078	1.5214844	1.5209961	−0.0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

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 chia đôi

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)<0$. 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^{*}|\leq {\frac {|b-a|}{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\leq n_{1/2}=\left\lceil \log _{2}\left({\frac {|b-a|}{\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 Phương pháp chia đôi

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

Tham khảo Phương pháp chia đôi

• Burden, Richard L.; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm", Numerical Analysis (ấn bản thứ 3), PWS Publishers, ISBN 0-87150-857-5

Bản mẫu:Thuật toán tìm nghiệm