Phương pháp chia đôi – Thuật toán và ví dụ là gì

Phương pháp chia đôi là gì?

Phương pháp phân đôi là một trong những giải pháp số cơ bản để tìm nghiệm của phương trình đa thức. Nó đóng ngoặc khoảng mà nghiệm của phương trình nằm trong đó và chia chúng thành hai nửa trong mỗi lần lặp cho đến khi tìm được nghiệm. Do đó, phương pháp phân đôi cũng được gọi là phương pháp đóng ngoặc.

Tuy nhiên, do cơ chế hoạt động tương tự như thuật toán tìm kiếm nhị phân nên phương pháp chia đôi còn được gọi là phương pháp tìm kiếm nhị phân, phương pháp chia đôi hoặc phương pháp phân đôi. Nó chủ yếu dựa trên định lý giá trị trung gian.

Tìm nghiệm nguyên của phương trình

Trong ví dụ này, chúng tôi chỉ xem xét các phương trình có một biến độc lập. Nó có thể là tuyến tính hoặc phi tuyến. Các phương trình tuyến tính được sử dụng để biểu diễn đồ thị của một đường thẳng, trong khi các phương trình phi tuyến tính được sử dụng để biểu diễn các đường cong.

Căn nguyên của một phương trình có nghĩa là giá trị của biến độc lập thỏa mãn phương trình. Ví dụ: nghiệm của phương trình f(x)= 4-x² = 0 là 2 vì f(2) = 4-2² = 0.

Giả sử f(x) là hàm liên tục thực. Theo định lý giá trị trung gian, phương trình f(x)=0 có ít nhất một nghiệm nằm giữa a và b nếu f(a)f(b) < 0. Hàm f(x) có nghiệm là “c,” giữa a và b.

Biểu diễn đồ họa của phương pháp chia đôi

Biểu đồ sau đây biểu diễn cơ chế hoạt động của phương pháp chia đôi. Từ biểu đồ, chúng ta có thể thấy rằng nghiệm của phương trình được đánh dấu màu đỏ.

Đầu tiên là:

Đầu tiên chúng tôi đưa ra hai dự đoán ban đầu, một₁ và B_1, mà f(a₁)f(b₁) < 0. Theo định lý giá trị trung gian, nghiệm phải nằm trong [a₁, b₁].
Chúng ta có thể tìm được trung điểm của một₁ và B_1,đó là b₂. Do đó, khoảng thời gian ban đầu bây giờ giảm xuống còn [a₁, b₂] bởi vì f(a₁)f(b₂) < 0.
Theo cách tương tự, khoảng thời gian được giảm cho đến khi tìm được nghiệm gần đúng.

Thuật toán phương pháp phân tách

Các bước áp dụng thuật toán chia đôi để tìm nghiệm phương trình f(x)=0 như sau

Bước 1) Chọn dự đoán ban đầu a, b và tỷ lệ dung sai e

Bước 2) Nếu f(a)f(b) >=0 thì nghiệm không nằm trong khoảng này. Như vậy sẽ không có giải pháp.

Bước 3) Tìm trung điểm c = (a+b)/2

(i) Nếu giá trị hàm số của trung điểm f(c) = 0 thì c là nghiệm. Chuyển sang bước 5.
(ii) Nếu f(a)f(c) < 0 thì nghiệm nằm giữa a và c. Khi đó đặt a = a, b = c.
(iii) Ngược lại đặt a = c, b = b.

Bước 4) Nếu sai số tuyệt đối cao hơn tỷ lệ dung sai hoặc (ba) > e, chuyển sang bước 3.

Bước 5) Hiển thị c là gốc gần đúng.

Hãy xem một ví dụ về thuật toán phương pháp chia đôi.
Chúng ta phải tìm nghiệm của hàm số liên tục sau bằng công thức phương pháp chia đôi.

f (x) = x³ - x² + 2

Ví dụ về phương pháp chia đôi

Bước 1) Hãy giả sử,

         a = -10,
         b = 10, và
         e = 1% hoặc 0.01

Bước 2) Bây giờ, chúng ta sẽ kiểm tra xem f(a)f(b) >= 0 hay không.

         f(a) = f(-10) = (-10)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Do đó, nghiệm của hàm trên nằm trong khoảng [-10, 10] này.

Bước 3) Khi đó điểm giữa c sẽ được tính trước.

Bây giờ cần kiểm tra các điều kiện sau:

(i) liệu f(c) = 0:
f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) nếu f(a)f(c) < 0:
f(c)f(a) = 2*(-1098) < 0

Điều kiện đã được đáp ứng. Đối với lần lặp tiếp theo, các giá trị sẽ là,

a = a = -10
b = c = 0

Bước 4) Vì (ba) = (0-(-10)) = 10>0.05, quá trình này sẽ được lặp lại. Các lần lặp tiếp theo được hiển thị trong bảng.

Lặp lại	a	b	c	ba	f(c)
1	-10	0	0	10	2
2	-5	0	-5	5	-148
3	-2.5	0	-2.5	2.5	-19.875
4	-1.25	0	-1.25	1.25	-1.52562
5	-1.25	-0.625	-0.625	0.625	1.36523
6	-1.25	-0.9375	-0.9375	0.3125	0.297119
7	-1.09375	-0.9375	-1.09375	0.15625	-0.50473
8	-1.01562	-0.9375	-1.01562	0.078125	-0.0791054
9	-1.01562	-0.976562	-0.976562	0.0390625	0.115003
10	-1.01562	-0.996094	-0.996094	0.0195312	0.0194703
11	-1.00586	-0.996094	-1.00586	0.00976562	-0.0294344

Bước 5) Ở lần lặp thứ 11, điều kiện ở bước 4 sẽ sai. Vì vậy, nghiệm của phương trình này là -1.00586.

Sơ đồ logic của phương pháp chia đôi

Mã giả

Start
Set a, b, e
if f(a)*f(b) >=0 
	Output("Root does not exist in this interval")
	Stop
while (b-a)>e do   
	c ← (a + b)/2    
	if f(c) = 0
        	break    
	end if 
	if f(c)*f(a) < 0 then
      	b ← c    
	else        
		a ← c
end while
Output(c)
Stop

Ví dụ về phương pháp chia đôi trong C/C++

Đầu vào:

#include<bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
	return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
	if (value(a) * value(b) >= 0)
	{
		cout << "The root does not lie in this interval\n";
		return;
	}
	double c = a;
	while ((b-a) >= Error)
	{
		c = (a+b)/2;
		if (value(c) == 0.0)
			break;
		else if (value(c)*value(a) < 0)
			b = c;
		else
			a = c;
	}
	cout << "The root is :" << c;
}
int main()
{
	double a =-10 , b = 10;
	bisection_method(a, b);
	return 0;
}

Đầu ra:

The root is :-1.00586

Ví dụ về phương pháp chia đôi trong Python