Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 이분법(Bisection Method): 함수의 근 찾기

수학과 컴퓨터 과학에서 방정식의 근(root)을 구하는 문제는 가장 기본적인 주제 중 하나입니다. 이 글에서는 주어진 구간에서 연속인 함수 f(x)의 근을 찾는 대표적인 수치 해석 기법인 이분법(Bisection Method)을 C++로 구현하는 방법을 단계별로 살펴봅니다.

함수 f(x)와 두 수 a, b가 주어졌을 때, f(a)와 f(b)의 부호가 서로 다르고(즉, f(a) × f(b) < 0), 함수 f(x)가 구간 [a, b]에서 연속이라고 가정해 봅시다. 우리의 목표는 이분법을 이용해 구간 [a, b] 사이에 존재하는 근의 값을 찾는 것입니다.

이분법이란 무엇인가?

이분법은 함수 f(x)의 근, 즉 f(x) = 0을 만족하는 x의 값을 찾기 위해 사용되는 수치 해석 방법입니다. 사용자가 지정한 'a'와 'b' 사이의 범위 내에서 근의 값을 찾아냅니다.

예시

방정식 f(x) = x² − 4
이 방정식은 x = 2일 때 0이 됩니다. 즉, 2² − 4 = 0
따라서 이 함수 f(x)의 근은 2입니다.

만약 함수 f(x)가 주어진 구간 [a, b]에서 연속이고, f(a)의 부호와 f(b)의 부호가 서로 다르다면, 중간값 정리(Intermediate Value Theorem)에 의해 해당 구간 안에는 반드시 f(m) = 0을 만족하는 값 m이 존재합니다.

즉, m ∈ [a, b]이면서 f(m) = 0인 값이 바로 우리가 찾으려는 근입니다. 하나의 함수는 여러 개의 근을 가질 수도 있습니다.

구간의 양 끝에서의 함숫값 f(a)와 f(b)의 부호가 다르다는 것은, 그 사이 어딘가에서 그래프가 x축을 반드시 지난다는 의미입니다. 이 구간 사이의 근을 찾기 위해 구간을 절반으로 나누고 그 중심값을 변수 m에 저장합니다.

m = (a + b) / 2

구간을 나눈 후에는 f(m)의 부호에 따라 근이 존재하는 쪽의 새로운 구간을 선택하고, 같은 과정을 반복합니다. 이렇게 구간을 계속 절반씩 줄여 나가면 설정한 오차 범위(EP) 안에서 근에 수렴하는 값을 얻을 수 있습니다.

입력 및 출력 예시

입력: x³ − x² + 2 ; a = -500, b = 100
출력: 근의 값은 : -0.991821

입력: x³ − x² + 2 ; a = -200, b = 300
출력: 근의 값은 : -1.0025

문제 해결 접근 방법

  • 방정식과 구간의 값 a, b를 입력받습니다.
  • 구간을 m = (a + b) / 2로 나눕니다.
    • f(m) = 0이면 m이 곧 근이므로 m을 출력합니다.
  • f(m) ≠ 0인 경우:
    • f(a) × f(m) < 0이면 근은 a와 m 사이에 존재합니다.
    • f(b) × f(m) < 0이면 근은 b와 m 사이에 존재합니다.

알고리즘

시작
Step 1 -> double solution(double x) 함수
    return x*x*x - x*x + 2
Step 2 -> double bisection(double a, double b) 함수
    solution(a) * solution(b) >= 0이면,
        "You have not assumed right a and b" 출력
        반환
    c = a 로 설정
    while ((b-a) >= EP) 동안 반복
        c = (a+b)/2
        solution(c) == 0.0이면
            break
        else if solution(c)*solution(a) < 0
            b = c
        else
            a = c
    "The value of root" 출력
Step 3 -> int main() 함수
    a = -500, b = 100으로 선언 및 초기화
    bisection(a, b) 호출
종료

C++ 전체 코드

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

// 이분법으로 해를 구할 예제 함수. 함수는 x^3 - x^2 + 2
double solution(double x) {
    return x*x*x - x*x + 2;
}

// EPSILON(EP) 오차 범위 내에서 solution(x)의 근을 출력
void bisection(double a, double b) {
    if (solution(a) * solution(b) >= 0) {
        cout << "You have not assumed right a and b\n";
        return;
    }
    double c = a;
    while ((b-a) >= EP) {
        // 중간 지점 찾기
        c = (a+b)/2;
        // 중간 지점이 근인지 확인
        if (solution(c) == 0.0)
            break;
        // 근이 있는 쪽 구간을 선택하여 반복
        else if (solution(c)*solution(a) < 0)
            b = c;
        else
            a = c;
    }
    cout << "The value of root is : " << c;
}

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

실행 결과

The value of root is : -0.991821

마무리

이분법은 매 반복마다 탐색 구간이 절반으로 줄어들기 때문에 구현이 간단하면서도 항상 수렴을 보장한다는 강력한 장점이 있습니다. 다만 수렴 속도가 비교적 느린 편이므로, 더 빠른 수렴이 필요한 경우 뉴턴-랩슨법(Newton-Raphson Method) 등과 함께 비교하여 상황에 맞는 기법을 선택하는 것이 좋습니다.