Chương trình C++ phương pháp chia đôi (Bisection Method)

Cho hàm f(x) với các số a và b, trong đó f(a) * f(b) > 0 và hàm f(x) nằm giữa a và b tức f(x) = [a, b]. Nhiệm vụ là tìm giá trị nghiệm nằm giữa khoảng a và b trong hàm f(x) dùng phương pháp chia đôi.

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

Phương pháp chia đôi dùng để tìm giá trị nghiệm trong hàm f(x) trong giới hạn cho trước bởi 'a' và 'b'. Nghiệm của hàm có thể định nghĩa là giá trị a sao cho f(a) = 0.

Ví dụ

Phương trình bậc hai F(x) = x^2 - 4x + 4 - 8 = x^2 - 4x - 4
Phương trình này bằng 0 khi x = 2.
Vậy nghiệm của hàm bậc hai F(x) là 2.

Nay, nếu hàm f(x) liên tục trong khoảng [a..b] và dấu của f(a) ≠ dấu của f(b) thì sẽ tồn tại giá trị m thuộc khoảng a và b sao cho f(m) = 0.

Giá trị m ∈ [a..b] sao cho f(m) = 0. Tức m là giá trị nghiệm có thể có nhiều.

Hình dưới minh họa khoảng f(a) và f(b). Để tìm nghiệm giữa các khoảng này, giới hạn được chia thành các phần và lưu trong biến m:

m = (a + b) / 2

Sau khi chia giới hạn, khoảng mới được tạo như hình dưới:

Ví dụ

Đầu vào: x^3 - x^2 + 2; a = -500, b = 100
Đầu ra: Giá trị nghiệm là: -0.991821

Đầu vào: x^3 - x^2 + 2; a = -200, b = 300
Đầu ra: Giá trị nghiệm là: -1.0025

Cách tiếp cận dùng trong chương trình dưới đây –

• Nhập phương trình và giá trị khoảng a, b
• Chia khoảng: m = (a + b) / 2
  • In m là nghiệm
• Nếu f(m) ≠ 0
  • Kiểm tra nếu f(a) * f(m) < 0
  • Thì nghiệm nằm giữa a và m
  • Kiểm tra nếu f(b) * f(m) < 0
  • Thì nghiệm nằm giữa b và m

Thuật toán

Bắt đầu
Bước 1 -> Trong hàm double solution(double x)
    Trả về x*x*x - x*x + 2
Bước 2 -> Trong hàm bisection(double a, double b)
    NẾU solution(a) * solution(b) >= 0 thì,
        In "Bạn chưa giả định đúng a và b"
        Trả về
    Kết thúc
    Gán c = a
    Vòng lặp Khi (b-a) >= EP
        Gán c = (a+b)/2
        NẾU solution(c) == 0.0
            Ngắt
        Kết thúc
        NGƯỢC LẠI NẾU solution(c)*solution(a) < 0
            Gán b = c
        Kết thúc NGƯỢC LẠI
        NGƯỢC LẠI
            Gán a = c
        Kết thúc
    Kết thúc
    In "Giá trị nghiệm"
Bước 3 -> Trong hàm int main()
    Khai báo và khởi tạo a = -500, b = 100
    Gọi hàm bisection(a, b)
Kết thúc

Ví dụ mã C++

#include <iostream>
using namespace std;
#define EP 0.01

// Ví dụ hàm nghiệm được xác định bằng phương pháp chia đôi
// Hàm là x^3 - x^2 + 2
double solution(double x) {
    return x*x*x - x*x + 2;
}

// In nghiệm của solution(x) với sai số EPSILON
void bisection(double a, double b) {
    if (solution(a) * solution(b) >= 0) {
        cout << "Bạn chưa giả định đúng a và b\n";
        return;
    }
    double c = a;
    while ((b-a) >= EP) {
        // Tìm điểm giữa
        c = (a+b)/2;
        // Kiểm tra điểm giữa có phải nghiệm không
        if (solution(c) == 0.0)
            break;
        // Quyết định phía để lặp lại
        else if (solution(c)*solution(a) < 0)
            b = c;
        else
            a = c;
    }
    cout << "Giá trị nghiệm là: " << c;
}

int main() {
    double a = -500, b = 100;
    bisection(a, b);
    return 0;
}

Đầu ra

Giá trị nghiệm là: -0.991821