이분법 알고리즘 및 예제

이분법이란 무엇인가요?

이분법은 다항식이나 초월방정식의 근을 찾는 가장 기본적인 수치 기법 중 하나입니다. 이 방법은 근을 포함하는 구간을 두 부분으로 나누고, 각 반복 단계에서 해당 구간을 다시 절반으로 나누어 허용 오차 범위 내에서 근을 찾을 때까지 계산합니다. 이러한 구간 나누기 방식 때문에 이분법은 '브래킷팅 방법'이라고도 불립니다.

이분법은 작동 방식이 이진 탐색과 유사하기 때문에 이진 탐색법, 반분법 또는 이분법이라고도 불립니다. 이 방법은 강력한 이론적 토대인 중간값 정리에 기반을 두고 있는데, 이 정리는 연속 함수가 어떤 구간에서 부호를 바꿀 때 그 구간 내 어딘가에서 반드시 0을 지나야 한다는 것을 보장합니다.

기본적인 정의를 살펴보았으니, 이제 방정식의 근을 찾는 것이 왜 중요한지, 그리고 이분법이 그 넓은 맥락에서 어떤 역할을 하는지 알아보겠습니다.

방정식의 근 찾기

이 논의에서는 독립 변수가 하나인 방정식에만 초점을 맞춥니다. 이러한 방정식은 선형 방정식일 수도 있고 비선형 방정식일 수도 있습니다. 선형 방정식은 직선 그래프를 나타내고, 비선형 방정식은 곡선이나 더 복잡한 형태를 나타냅니다.

방정식의 근은 방정식을 만족하는 독립 변수의 값입니다. 예를 들어, 방정식 f(x) = 4 – x의 근은 다음과 같습니다.² = 0은 2입니다. 왜냐하면 f(2) = 4 – 2이기 때문입니다.² = 0.

실수 연속 함수 f(x)를 생각해 봅시다. 중간값 정리에 따르면, f(a)f(b) < 0일 때 방정식 f(x) = 0은 a와 b 사이에 적어도 하나의 근을 갖습니다. 다시 말해, 함수 f(x)는 a와 b 사이 어딘가에 근 "c"를 갖습니다.

이 부호 변화 속성이 바로 이분법이 활용하는 핵심 요소입니다. 다음 절에서는 이 개념을 그래프로 나타낸 것을 보여줍니다.

이등분법의 그래픽 표현

다음 그래프는 이분법의 작동 원리를 나타냅니다. 그래프에서 방정식의 실제 근은 빨간색으로 표시되어 있습니다.

절차는 다음과 같이 요약할 수 있습니다.

• 먼저 두 개의 초기 추측값을 선택합니다.₁ 그리고 b₁, f(a)에 대해₁)f(b)₁) < 0. 중간값 정리에 따르면 근은 [a ] 범위 내에 있어야 합니다.₁, b₁].
• 그런 다음 a의 중간점을 계산합니다.₁ 그리고 b₁b는₂초기 간격은 이제 [a]로 줄어듭니다.₁, b₂] 왜냐하면 f(a₁)f(b)₂) < 0.
• 이와 같은 방식으로, 원하는 허용 오차 범위 내에서 근사해를 찾을 때까지 구간을 계속해서 절반씩 줄여 나갑니다.

기하학적 직관이 명확해졌으므로 이제 이 절차를 단계별 알고리즘으로 공식화할 수 있습니다.

이분법 알고리즘

이분법 알고리즘을 적용하여 방정식 f(x) = 0의 근을 찾는 단계는 다음과 같습니다.

단계 1) 초기 추측값 a, b 및 허용 오차율 e를 선택하십시오.

단계 2) 만약 f(a)f(b) >= 0이면, 근은 이 구간에 있지 않습니다. 따라서 [a, b] 내에는 해가 없습니다.

단계 3) 중점을 구하세요. c = (a + b)/2.

(i) 중간점에서의 함수값 f(c) = 0이면 c는 근입니다. 5단계로 이동합니다.
(ii) f(a)f(c) < 0이면 근은 a와 c 사이에 있습니다. 그러면 a = a, b = c로 설정합니다.
(iii) 그렇지 않으면 a = c, b = b로 설정합니다.

단계 4) 절대 오차가 허용 오차보다 크면, 즉 (b – a) > e이면 3단계로 돌아갑니다.

단계 5) c를 대략적인 근으로 표시합니다.

이분법 알고리즘의 실제 적용 사례를 살펴보겠습니다. 이분법 공식을 이용하여 다음 연속 함수의 근을 찾아보겠습니다.

에프(엑스) = 엑스³ -x² + 2

이분법 방법의 예

단계 1) 가정해 봅시다.

         a = -10,
         b = 10이고,
         e = 1% 또는 0.01.

단계 2) 이제 f(a)f(b) >= 0인지 확인하겠습니다.

         f(a) = f(-10) = (-10)³ – (-10)² + 2 = -1098
         f(b) = f(10) = (10)³ - (10)² + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

따라서 위 함수의 근은 구간 [-10, 10]에 있습니다.

단계 3) 다음으로 중간점 c를 계산합니다.

이제 다음 조건을 확인해야 합니다.

(i) f(c) = 0인지 여부:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2이므로 0과 같지 않습니다.

(ii) f(a)f(c) < 0인지 여부:
         f(c)f(a) = 2 * (-1098) < 0

조건이 충족되었습니다. 다음 반복에서 값은 다음과 같습니다.

         a = a = -10
         b = c = 0

단계 4) (b – a) = (0 – (-10)) = 10 > 0.01이므로 과정이 반복됩니다. 다음 반복은 아래 표에 나와 있습니다.

단계 5) 11번째 반복에서 4단계의 조건이 거짓이 됩니다. 따라서 이 방정식의 근사해는 -1.00586입니다.

수치 예제를 마쳤으므로 다음 섹션에서는 전체 제어 흐름을 나타내는 논리 다이어그램을 제시합니다.

이등분법 논리도

아래 순서도는 이분법의 결정 논리를 요약한 것으로, 범위 검사, 중간점 업데이트 및 허용 오차 검사를 포함합니다.

가짜-Code

아래 의사 코드는 알고리즘을 그대로 보여주며, 어떤 프로그래밍 언어로든 이분법을 구현하기 위한 청사진 역할을 합니다.

Start
Set a, b, e
if f(a)*f(b) >= 0
    Output("Root does not exist in this interval")
    Stop
while (b-a) > e do
    c ← (a + b)/2
    if f(c) = 0
        break
    end if
    if f(c)*f(a) < 0 then
        b ← c
    else
        a ← c
end while
Output(c)
Stop

C/의 이분법 예제C++

다음 C/C++ 이 프로그램은 이분법을 사용하여 함수 f(x) = x의 근을 찾습니다.³ -x² 구간 [-10, 10] 내에서 + 2.

입력:

#include <bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
    return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
    if (value(a) * value(b) >= 0)
    {
        cout << "The root does not lie in this interval\n";
        return;
    }
    double c = a;
    while ((b-a) >= Error)
    {
        c = (a+b)/2;
        if (value(c) == 0.0)
            break;
        else if (value(c)*value(a) < 0)
            b = c;
        else
            a = c;
    }
    cout << "The root is :" << c;
}
int main()
{
    double a = -10, b = 10;
    bisection_method(a, b);
    return 0;
}

출력:

The root is :-1.00586

Bisection 방법의 예 Python

The Python 아래 버전은 동일한 논리를 사용하여 비슷한 근사값을 도출하므로 빠른 실험 및 교육에 적합합니다.

입력:

def value(x):
    return x*x*x - x*x + 2

def bisection_method(a, b):
    if (value(a) * value(b) >= 0):
        return
    c = a
    while ((b-a) >= 0.01):
        c = (a+b)/2
        if (value(c) == 0.0):
            break
        if (value(c)*value(a) < 0):
            b = c
        else:
            a = c
    print("The root is : ", "%.4f" % c)

a = -10
b = 10
bisection_method(a, b)

출력:

The root is :  -1.0059

이등분법의 장점과 한계

다른 모든 수치 해석 기법과 마찬가지로 이분법에도 분명한 장점과 몇 가지 실질적인 단점이 있습니다. 아래 표는 가장 중요한 장점과 단점을 요약한 것입니다.

이등분법의 응용

이분법은 견고한 근 찾기 단계가 필요한 많은 실제적이고 현대적인 컴퓨팅 시나리오에서 사용됩니다.

• 엔지니어링 시뮬레이션: 열전달, 유체역학 및 구조 해석에 나타나는 비선형 방정식을 해결합니다.
• 재무 모델링: 정해진 해법이 없는 경우 수익률, 내부 수익률 및 손익분기점을 계산합니다.
• 기계 학습 및 AI: AI 기반 수치 해석 솔버에서 임계값을 찾고, 모델을 보정하고, 하이퍼파라미터를 조정합니다.
• 컴퓨터 그래픽: 곡선을 따라 광선과 표면의 교차점 및 매개변수 값을 결정합니다.
• 임베디드 시스템: 단순성과 예측 가능성이 속도보다 더 중요한 저자원 제어기에서 근사값을 구하는 방법.

자주 묻는 질문