Phương pháp chia đôi là gì?
Phương pháp chia đôi (bisection) là một trong những kỹ thuật lâu đời và đáng tin cậy nhất để tìm nghiệm của một hàm liên tục \(f(x)\) — tức giá trị \(x\) sao cho \(f(x) = 0\). Cách làm là bắt đầu với một khoảng \([a, b]\) mà trên đó hàm số đổi dấu, sau đó liên tục chia đôi khoảng và giữ lại nửa khoảng vẫn còn chứa nghiệm. Vì sự đổi dấu luôn được duy trì ở mỗi bước nên phương pháp này chắc chắn hội tụ, miễn là \(f\) liên tục và \(f(a)\) cùng \(f(b)\) trái dấu nhau. Công cụ này áp dụng cho mọi hàm số thực không thứ nguyên và sử dụng đơn vị radian cho các hàm lượng giác.
Cách sử dụng máy tính
Nhập hàm số của bạn vào ô f(x), dùng x làm biến (ví dụ x-cos(x), x^2-2 hoặc exp(x)-3). Đặt đầu mút dưới a và đầu mút trên b sao cho nghiệm nằm giữa hai giá trị này — tích \(f(a)\cdot f(b)\) phải nhỏ hơn hoặc bằng 0. Chọn số lần lặp tối đa n và số chữ số muốn hiển thị. Công cụ sẽ trả về nghiệm gần đúng, giá trị của hàm số tại điểm đó (lẽ ra phải gần bằng 0) và số lần lặp thực tế đã cần đến.
Công thức
Ở mỗi bước, giá trị ước lượng là trung điểm \(x_n = (a_n + b_n) / 2\). Nếu \(|f(x_n)|\) nhỏ hơn sai số cho phép thì \(x_n\) được chấp nhận. Ngược lại, thuật toán giữ lại nửa khoảng nào vẫn còn đổi dấu: nếu \(f(a_n)\cdot f(x_n) > 0\) thì nghiệm nằm bên phải (gán \(a = x_n\)), còn không thì nghiệm nằm bên trái (gán \(b = x_n\)).
$$c = \frac{a + b}{2} \\[1.5em] \text{where}\quad \left\{ \begin{aligned} &\text{if } f(a)\cdot f(c) < 0 \Rightarrow b \leftarrow c \\ &\text{else} \Rightarrow a \leftarrow c \\ &\text{repeat up to } n \text{ times} \end{aligned} \right.$$Độ rộng của khoảng co lại theo \((b-a)/2^n\), nên sự hội tụ là tuyến tính — gần như mỗi bước thêm đúng được một chữ số nhị phân.
Ví dụ minh họa
Với \(f(x) = x - \cos(x)\) trên \([-10, 10]\): \(f(-10) \approx -10{,}84\) (âm) và \(f(10) \approx 10{,}84\) (dương), nên nghiệm đã được khoanh vùng. Việc chia đôi liên tục sẽ hội tụ về \(x \approx 0{,}7390851332151607\), chính là “số Dottie” nổi tiếng, nơi \(x = \cos x\), với \(f(x)\) gần như bằng 0.
Cách thực hiện phương pháp chia đôi bằng tay
Phương pháp chia đôi tìm nghiệm của \(f(x)=0\) bằng cách chia đôi lặp lại một khoảng được biết là chứa một nghiệm. Nó dựa trên Định lý Giá trị Trung gian: nếu \(f\) liên tục trên \([a,b]\) và \(f(a)\) và \(f(b)\) có dấu đối nhau, thì một nghiệm phải nằm giữa chúng.
- Xác minh khoảng chứa. Xác nhận rằng \(f(a)\cdot f(b)<0\). Nếu tích dương, khoảng không được đảm bảo chứa một nghiệm — chọn một \([a,b]\) khác.
- Tính điểm giữa. \(m=\dfrac{a+b}{2}\).
- Tính giá trị hàm số. Tìm \(f(m)\). Nếu \(f(m)=0\) (hoặc trong sai số cho phép), \(m\) là nghiệm và bạn dừng lại.
- Thay thế một điểm cuối theo dấu. Nếu \(f(a)\cdot f(m)<0\), nghiệm nằm trong \([a,m]\), vì vậy đặt \(b\leftarrow m\). Nếu không, nghiệm nằm trong \([m,b]\), vì vậy đặt \(a\leftarrow m\).
- Lặp lại các bước 2–4 cho đến khi \(|b-a|<\text{sai số cho phép}\) hoặc \(|f(m)|<\text{sai số cho phép}\), hoặc cho đến khi bạn đạt đến số lần lặp tối đa.
Ví dụ: \(f(x)=x^{3}-x-2\) trên \([1,2]\). Kiểm tra: \(f(1)=-2\), \(f(2)=4\), tích \(<0\) — khoảng chứa là hợp lệ.
| Lần lặp | a | b | m=(a+b)/2 | f(m) | Khoảng mới |
|---|---|---|---|---|---|
| 1 | 1.0000 | 2.0000 | 1.5000 | −0.125 | [1.5, 2] |
| 2 | 1.5000 | 2.0000 | 1.7500 | 1.6094 | [1.5, 1.75] |
| 3 | 1.5000 | 1.7500 | 1.6250 | 0.6660 | [1.5, 1.625] |
| 4 | 1.5000 | 1.6250 | 1.5625 | 0.2522 | [1.5, 1.5625] |
| 5 | 1.5000 | 1.5625 | 1.5313 | 0.0591 | [1.5, 1.5313] |
| 6 | 1.5000 | 1.5313 | 1.5156 | −0.0340 | [1.5156, 1.5313] |
Sau nhiều lần lặp hơn, khoảng đóng lại trên nghiệm thực 1.521380, cũng là nghiệm thực duy nhất của phương trình bậc ba \(x^{3}-x-2=0\) được tìm thấy bởi một 1.521380 trình giải trực tiếp.
Số lần lặp so với Sai số cho phép và Chiều rộng khoảng
Mỗi bước chia đôi làm giảm khoảng đi một nửa, vì vậy sau \(n\) lần lặp chiều rộng khoảng là \((b-a)/2^{\,n}\). Để đạt được sai số cho phép \(\text{sai số cho phép}\) trên vị trí của nghiệm, bạn cần khoảng
$$n \approx \log_2\!\left(\frac{b-a}{\text{sai số cho phép}}\right).$$Số lần chỉ tăng với lôgarit của độ chính xác, vì vậy ngay cả những sai số cho phép rất nhỏ cũng chỉ yêu cầu tương đối ít bước. Bảng dưới đây cho thấy số lần lặp được làm tròn lên cho một số kết hợp.
| Chiều rộng ban đầu \(b-a\) | Sai số cho phép mục tiêu | \(\log_2((b-a)/\text{sai số cho phép})\) | Số lần lặp cần thiết |
|---|---|---|---|
| 1 | \(10^{-3}\) | 9.97 | 10 |
| 1 | \(10^{-6}\) | 19.93 | 20 |
| 1 | \(10^{-10}\) | 33.22 | 34 |
| 10 | \(10^{-6}\) | 23.25 | 24 |
| 20 | \(10^{-6}\) | 24.25 | 25 |
| 100 | \(10^{-8}\) | 33.22 | 34 |
| 0.5 | \(10^{-12}\) | 38.86 | 39 |
Ví dụ, một khoảng chiều rộng 20 được tinh chỉnh đến \(10^{-6}\) cần \(\lceil\log_2(20/10^{-6})\rceil=\lceil 24.25\rceil=\) 25 lần lặp, và một khoảng chiều rộng 1 đến \(10^{-10}\) cần \(\lceil 33.22\rceil=\) 34. Giảm chiều rộng khởi đầu đi một nửa tiết kiệm chính xác một lần lặp; bình phương độ chính xác (một chữ số thập phân thêm) có giá khoảng 3.3 lần lặp.
Các thuật ngữ chính
- Nghiệm. Một giá trị \(x^{*}\) trong đó hàm số bằng không, \(f(x^{*})=0\); còn được gọi là không điểm hoặc nghiệm của phương trình.
- Khoảng chứa / khoảng \([a,b]\). Một cặp điểm cuối được cho là chứa một nghiệm. Đối với phương pháp chia đôi, nó phải thỏa mãn điều kiện thay đổi dấu.
- Thay đổi dấu. Điều kiện \(f(a)\cdot f(b)<0\), nghĩa là \(f\) nhận các dấu đối nhau tại các điểm cuối. Đối với một \(f\) liên tục, điều này đảm bảo ít nhất một nghiệm ở giữa (Định lý Giá trị Trung gian).
- Điểm giữa. Tâm của khoảng hiện tại, \(m=(a+b)/2\); mỗi bước kiểm tra điểm này và loại bỏ nửa không thể chứa nghiệm.
- Sai số cho phép. Mục tiêu độ chính xác dừng lặp lại, áp dụng cho chiều rộng khoảng \(|b-a|\) hoặc phần dư \(|f(m)|\).
- Hội tụ (tuyến tính). Phương pháp chia đôi hội tụ tuyến tính: sai số được giảm đi khoảng một nửa mỗi bước (sai số \(\le (b-a)/2^{n}\)), mang lại tiến trình ổn định nhưng không tăng tốc — khoảng một chữ số nhị phân chính xác thêm cho mỗi lần lặp.
- Lần lặp. Một chu kỳ đầy đủ của việc tính điểm giữa, tính giá trị hàm số, và cập nhật một điểm cuối. Số lần lặp được giới hạn bởi cài đặt số lần lặp tối đa.
Câu hỏi thường gặp
Vì sao tôi gặp lỗi “không có sự đổi dấu”? Phương pháp chia đôi đòi hỏi \(f(a)\) và \(f(b)\) phải trái dấu. Hãy điều chỉnh \(a\) và \(b\) cho đến khi chúng nằm hai bên của nghiệm.
Phương pháp này có tìm được nhiều nghiệm không? Không — nó chỉ trả về một nghiệm duy nhất nằm trong khoảng đã khoanh và không phát hiện được những nghiệm mà đường cong chỉ chạm trục chứ không cắt qua.
Vì sao nó chậm hơn phương pháp Newton? Phương pháp chia đôi hội tụ tuyến tính, mỗi bước thêm khoảng một chữ số nhị phân, trong khi phương pháp Newton hội tụ bậc hai. Vì vậy người ta thường dùng phương pháp chia đôi để tìm một điểm xuất phát an toàn, rồi để các phương pháp nhanh hơn tinh chỉnh tiếp.
