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

Phương pháp chia đôi trong giải tích số là một trong những kỹ thuật quan trọng và hữu ích để giải quyết các bài toán tìm nghiệm của phương trình, đặc biệt là trong những trường hợp mà không thể áp dụng các phương pháp giải đại số truyền thống. Kỹ thuật này dựa trên nguyên lý tìm kiếm nghiệm trong một khoảng cho trước bằng cách chia đôi khoảng đó thành hai phần nhỏ hơn, từ đó xác định được vị trí của nghiệm thông qua việc kiểm tra dấu của hàm số tại các đầu mút của các khoảng. Phương pháp này không chỉ đơn giản và dễ hiểu mà còn đảm bảo tính chính xác cao, giúp các nhà khoa học và kỹ sư nhanh chóng tìm ra giải pháp cho những bài toán phức tạp trong thực tiễn. Với ứng dụng rộng rãi trong lĩnh vực toán học, vật lý, và kỹ thuật, phương pháp chia đôi trở thành một phần thiết yếu trong giải tích số hiện đại.

Cụ thể hơn, phương pháp chia đôi là một thuật toán số học dùng để tìm nghiệm của phương trình $f(x) = 0$ trong một khoảng $[a, b]$ mà hàm $f(x)$ liên tục. Phương pháp dựa trên định lý giá trị trung gian: Nếu $f(a) \cdot f(b) < 0$ , thì tồn tại ít nhất một nghiệm $c \in [a, b]$ sao cho $f(c) = 0$ .

(Định lý giá trị trung gian là một trong những định lý quan trọng trong giải tích. Nó được phát biểu như sau: Nếu một hàm số liên tục trên một đoạn $[a, b]$ có giá trị $f(a)$ và $f(b)$ , thì với mọi giá trị $y$ nằm giữa $f(a)$ và $f(b)$ , tồn tại ít nhất một điểm $c$ trong khoảng $(a, b)$ sao cho $f(c) = y$ .)

Ý tưởng chính:

Chọn khoảng $[a, b]$ sao cho $f(a) \cdot f(b) < 0$ .
Tính điểm giữa: $c = \frac{a + b}{2}$ .
Xác định dấu của $f(c)$ :
Nếu $f(a) \cdot f(c) < 0$ , thì nghiệm nằm trong khoảng $[a, c]$ , thay $b$ bằng $c$ .
Nếu $f(b) \cdot f(c) < 0$ , thì nghiệm nằm trong khoảng $[c, b]$ , thay $a$ bằng $c$ .
Nếu $f(c) = 0$ , thì $c$ chính là nghiệm.
Lặp lại quá trình cho đến khi khoảng cách giữa $a$ và $b$ đủ nhỏ (độ chính xác mong muốn).

Thuật toán chi tiết:

Đầu vào:

Hàm $f(x)$ .
Khoảng ban đầu $[a, b]$ sao cho $f(a) \cdot f(b) < 0$ .
Sai số $\epsilon$ (độ chính xác mong muốn).

Quy trình:

Kiểm tra điều kiện $f(a) \cdot f(b) < 0$ . Nếu không thỏa mãn, dừng thuật toán.
Tính $c = \frac{a + b}{2}$ .
Kiểm tra:

Nếu $|f(c)| < \epsilon$ hoặc $|b - a| < \epsilon$ : Dừng, nghiệm gần đúng là $c$ .
Nếu $f(a) \cdot f(c) < 0$ : Đặt $b = c$ .
Nếu $f(c) \cdot f(b) < 0$ : Đặt $a = c$ .

Quay lại bước 2.

Đầu ra:

Nghiệm gần đúng $c$ .
Số lần lặp.

Ưu điểm:

Dễ hiểu, dễ triển khai.
Đảm bảo hội tụ nếu hàm liên tục và khoảng $[a, b]$ thỏa mãn $f(a) \cdot f(b) < 0$ .

Nhược điểm:

Hội tụ chậm so với các phương pháp khác (vd: Newton-Raphson, Secant).
Yêu cầu khoảng ban đầu $[a, b]$ phải chứa nghiệm (điều kiện $f(a) \cdot f(b) < 0$ ).

Ví dụ minh họa:

Tìm nghiệm của phương trình $f(x) = x^3 - x - 2 = 0$ trên khoảng $[1, 2]$ với sai số $\epsilon = 0.001$ .

Bước đầu tiên:

$f(1) = -2, f(2) = 4$ ( $f(1) \cdot f(2) < 0$ ).

Tính $c = \frac{1 + 2}{2} = 1.5$ .

$f(1.5) = 1.5^3 - 1.5 - 2 = -0.125$ .

Vì $f(1) \cdot f(1.5) < 0$ , đặt $b = 1.5$ .

Tiếp tục lặp:

Khoảng mới: $[1, 1.5]$ , tính $c = \frac{1 + 1.5}{2} = 1.25$ .

Lặp lại cho đến khi khoảng cách giữa $a$ và $b$ nhỏ hơn $\epsilon$ .

Nghiệm gần đúng là: $x \approx 1.324$ .

Mã Python:

def bisection_method(func, a, b, tol):
    if func(a) * func(b) >= 0:
        print("Invalid interval: f(a) and f(b) must have opposite signs.")
        return None

    iteration = 0
    while (b - a) / 2 > tol:
        c = (a + b) / 2
        if func(c) == 0:
            return c, iteration
        elif func(a) * func(c) < 0:
            b = c
        else:
            a = c
        iteration += 1

    return (a + b) / 2, iteration

# Ví dụ sử dụng
f = lambda x: x**3 - x - 2
root, iters = bisection_method(f, 1, 2, 1e-3)
print(f"Root: {root}, Iterations: {iters}")

Mã MATLAB:

function [root, iterations] = bisection_method(func, a, b, tol)
    if func(a) * func(b) >= 0
        error('Khoảng [a, b] không hợp lệ: f(a) và f(b) phải trái dấu.');
    end

    iterations = 0;
    while (b - a) / 2 > tol
        c = (a + b) / 2;
        if func(c) == 0
            break;
        elseif func(a) * func(c) < 0
            b = c;
        else
            a = c;
        end
        iterations = iterations + 1;
    end

    root = (a + b) / 2;
end

% === Sử dụng ===
f = @(x) x^3 - x - 2;
a = 1;
b = 2;
tol = 1e-3;
[root, iterations] = bisection_method(f, a, b, tol);
fprintf('Nghiệm gần đúng: %.5f\n', root);
fprintf('Số lần lặp: %d\n', iterations);

Discover more from Science Comics

Subscribe to get the latest posts sent to your email.