Phương pháp chia đôi (bisection)

Thu hẹp dần khoảng phân li nghiệm bằng cách chia đôi

Cho phương trình f(x) = 0, f(x) liên tục và trái dấu tại 2 đầu [a,b]. Giả sử f(a) < 0, f(b) < 0 (nếu ngược lại thì xét –f(x)=0 ). Theo định lý 1, trên [a,b] phương trình có ít nhất 1 nghiệm µ.

Để tìm nghiệm gần đúng c, ta thực hiện một số hữu hạn lần quá trình lặp các bước sau đây: Bước 1: Ta chọn c là điểm chính giữa của đoạn [a, b] c = (a + b) / 2 Bước 2: Nếu f(c) = 0 thì ta khẳng định ngay c là nghiệm cần tìm và chuyển sang bước 4, ngược lại chuyển sang bước 3. Bước 3: Nếu f(a)f(c) < 0 thì ta đặt lại b = c và quay về bước 1. Còn nếu f(a)f(c) > 0 thì đặt lại a=c rồi cũng quay về bước 1. Bước 4: Thông báo nghiệm c tìm được và kết thúc công việc tìm nghiệm của phương trình f(x) = 0. Quá trình trên gọi là phương pháp chia đôi bởi vì cứ mỗi một lần lặp lại từ đầu thì khoảng [a, b] cần xem xét được thu gọn lại chỉ còn một nửa so với lần trước bởi điểm chính giữa c. Quá trình lặp trên cũng dừng lại khi đoạn [a,b] quá ngắn (nhỏ hơn một số dương rất nhỏ nào đó, gọi là sai số).

- Khai báo hàm f(x) (hàm đa thức, hàm siêu việt)

- Nhập a, b sao cho f(a)<0 và f(b)>0

- Lặp

c = (a+b)/2

nếu f(c) > 0 → b = c ngược lại a = c

trong khi (|f(c) |> ε) /* |a - b| > ε và f(c) != 0 */

Xuất nghiệm: c

Hay dưới dạng giả mã:

procedure Chia_doi

{

do

{ c = (a+b)/2

if (f(a) f(c) < 0) b=c;

else a=c;

} while (b-a <ε);

}

Như vậy:

- Hoặc nhận được nghiệm đúng ở một bước nào đó:

c = (ai-1+ bi-1)/2 nếu f(c) = 0

- Hoặc nhận được 2 dãy {an} và {bn}, trong đó:

{an}: là dãy đơn điệu tăng và bị chặn trên

{bn}: là dãy đơn điệu giảm và bị chặn dưới

Sai số ở bước n được tính theo công thức là:

e.VídụVí dụ 1: phương trình f(x) = 0 với f(x) = x ^ 3 - 4, thì nghiệm gần đúng với sai số 0.001 sẽ được tìm như sau10 1.4980 1.5000 1.4990 Vậy nghiệm gần đúng của phương trình trên là 1.499

Vídụ2:Tìm nghiệm phương trình: 2x + x - 4 = 0 bằng ppháp chia đôi

Giải:

- Tách nghiệm: phương trình có 1 nghiệm x trong (1,2)

- Chính xác hoá nghiệm: áp dụng phương pháp chia đôi ( f(1) < 0)

Bảng kết quả:

A b f(a).f(c)1 2 +1.5 -1.25 -1.375 +1.438 +1.406 +1.391 -1.383 +1.387 -1.385 -1.386 1.387=

Kết luận: Nghiệm của phương trình: x ≈ 1.386

Ví dụ 3: Cho phương trình f(x)=5x³ - cos3x = 0 trong khoảng cách ly nghiệm [0,1]. Với phương pháp chia đôi, nghiệm gần được tìm theo bảng sau:

Như vậy x₅ = 31/64.

Ví dụ 4: Ta xét phương trình f(x) = sin(x) - x2cos(x) =0. Phương trình này có nghiệm đúng là x = 0.

Ta thấy nếu a= -0.5, b = 2 thì f(a) = -0.6988, f(b) = 2.5739, tức là trái dấu. Vậy ta có thể áp dụng phương pháp chia đôi. Đặt ε = 1.0e-03 ta có sau 8 bước lặp ta nhận được nghiệm là 0.0005.

Ưu điểm của phương pháp chia đôi là đơn giản. Nhược điểm là tốc độ hội tụ chậm, không tận dụng được tính chất của hàm số f(x). Dù hàm số có dạng gì thì chúng ta cũng chỉ chia đôi, xét giá trị của hàm tại các điểm chia rồi quyết định chọn đoạn nào để chia tiếp. Nếu khoảng [a,b] ban đầu lớn thì phải khá nhiều bước mới đạt được độ chính xác cần thiết.