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
- 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