[수치해석] 2강 | Roots & Bracketing Methods

이번 장에서는 비선형 방정식의 근(Root)을 수치적으로 찾는 방법에 대해 알아본다.

📌 이번 장의 핵심

① 방정식의 근(Root)이란?
② 근이 존재하는 구간은 어떻게 찾을까?
③ Incremental Search
④ Bisection Method
⑤ 오차와 종료 조건
⑥ False-Position Method

01. 방정식의 근(Root)이란?

함수에서 다음 조건을 만족하는 x를 근(Root)이라고 한다.

f(x) = 0

예를 들어 2차방정식은 근의 공식을 이용해 해를 구할 수 있다. 하지만 복잡한 고차방정식이나 비선형 방정식은 간단한 공식만으로 근을 구하기 어려운 경우가 있다.

ax⁵ + bx⁴ + cx³ + dx² + ex + f = 0

이러한 경우 컴퓨터를 이용해 값을 반복적으로 계산하면서 실제 근에 가까운 값을 찾아가는 수치적인 방법을 사용할 수 있다.

02. Graphical Method

가장 직관적인 방법은 함수를 그래프로 그려보는 것이다.

우리가 찾으려는 조건은 f(x) = 0이므로, 그래프에서는 함수와 x축이 만나는 지점이 근이 된다.

▲ 함수 f(x)가 x축과 만나는 지점이 f(x) = 0의 근이다.

03. 근이 존재하는 구간 찾기

연속함수 f(x)에서 두 지점을 다음과 같이 정의해보자.

• x_l : Lower Bound
• x_u : Upper Bound

두 지점의 함수값을 곱했을 때

f(x_l) × f(x_u) < 0

이라면 두 함수값의 부호가 서로 다르다는 뜻이다.

💡 핵심

f(x_l)이 양수이고 f(x_u)가 음수이거나, 그 반대라면 연속함수는 두 점 사이에서 적어도 한 번 f(x) = 0을 지나게 된다.

▲ 양 끝점의 함수값 부호가 다르면 연속함수는 그 사이에서 x축을 통과한다.

 

⚠️ 주의

f(x_l) × f(x_u) < 0 이라고 해서 근이 정확히 하나라는 뜻은 아니다.

적어도 하나의 근이 존재한다는 의미로 이해하면 된다.

04. 부호 검사만으로 찾기 어려운 경우

근이 존재한다고 해서 항상 함수값의 부호가 바뀌는 것은 아니다. 대표적인 예가 함수가 x축에 접하는 경우이다.

▲ 근이 존재하지 않거나 짝수개의 근이 존재할 수 있다

▲ 함수가 x축에 접하면 근이 존재해도 함수값의 부호가 변하지 않을 수 있다.

짝수 중복근(Even-Multiplicity Root)은 단순한 부호 변화 검사만으로는 놓칠 수 있다.

05. Bracketing Method

Bracketing Method란 근의 양쪽에 두 값을 설정해서 근을 그 사이에 가둔 뒤, 구간을 점점 좁혀가는 방법이다.

f(x_l) × f(x_u) < 0

x_l 설정

↓

근(Root)이 존재하는 구간

↓

x_u 설정

06. Incremental Search

처음부터 적절한 x_l과 x_u를 알고 있는 것은 아니다. 따라서 일정한 간격으로 x를 증가시키면서 함수값의 부호가 바뀌는 지점을 찾을 수 있다.

▲ 일정한 간격으로 함수값을 확인하면서 + → − 또는 − → +가 나타나는 구간을 찾는다.

⚠️ Incremental Search의 한계

간격이 너무 크면 여러 개의 근을 한 번에 지나칠 수 있다. 또한 짝수 중복근처럼 부호가 바뀌지 않는 근은 단순한 부호 검사로 찾기 어렵다.

07. ⭐ Bisection Method

Bisection Method(이분법)은 근이 존재하는 구간을 반복적으로 절반씩 나누는 방법이다.

먼저 중간점 x_r을 계산한다.

x_r = (x_l + x_u) / 2

▲ x l 과 x u 의 중간값 x r 을 계산한다.

Bisection 알고리즘

STEP 1
f(x_l) × f(x_u) < 0인 구간 설정

↓

STEP 2
x_r = (x_l + x_u) / 2

↓

STEP 3
f(x_l) × f(x_r)의 부호 확인

↓

근이 존재하는 절반만 새로운 구간으로 선택

↓

원하는 오차에 도달할 때까지 반복

==========================================================

Case A
f(x_l) × f(x_r) < 0
→ 근이 왼쪽 구간에 있으므로 x_u = x_r

Case B
f(x_l) × f(x_r) > 0
→ 근이 오른쪽 구간에 있으므로 x_l = x_r

Case C
f(x_r) = 0
→ x_r이 정확한 근이므로 계산 종료

08. 언제 계산을 멈출까?

컴퓨터가 계산을 무한히 반복할 수는 없다. 따라서 Termination Criterion(종료 조건)이 필요하다.

실제 근을 모르는 경우에는 현재 반복값과 이전 반복값을 비교하여 근사 백분율 상대오차를 계산한다.

ε_a = | (x_r^new − x_r^old) / x_r^new | × 100%

미리 설정한 허용 오차를 ε_s라고 하면,

ε_a < ε_s

가 되었을 때 반복 계산을 종료한다.

09. Bisection의 오차

초기 구간의 크기를 다음과 같이 정의한다.

Δx⁰ = x_u⁰ − x_l⁰

Bisection은 반복할 때마다 구간을 절반으로 줄이므로, n회 반복한 후의 오차 범위는 다음과 같이 표현된다.

E_aⁿ = Δx⁰ / 2ⁿ

💡 핵심

Bisection Method에서는 반복 횟수가 한 번 증가할 때마다 근을 포함하는 구간의 크기가 1/2로 감소한다.

원하는 오차 E_a,d를 얻기 위해 필요한 반복 횟수는 강의자료에서 다음과 같이 나타낸다.

n ≈ log₂ (Δx⁰ / E_a,d)

10. Python으로 Bisection 구현하기

def bisect1(func, xl, xu, maxit=20):

    # 초기 구간이 근을 포함하는지 확인
    if func(xl) * func(xu) > 0:
        return "initial estimates do not bracket solution"

    for i in range(maxit):

        # 중간값 계산
        xm = (xl + xu) / 2

        # 근이 오른쪽 구간에 있는 경우
        if func(xm) * func(xl) > 0:
            xl = xm

        # 근이 왼쪽 구간에 있는 경우
        else:
            xu = xm

    return xm

11. False-Position Method

Bisection Method는 함수값의 크기와 관계없이 항상 구간의 정확한 가운데를 선택한다.

x_r = (x_l + x_u) / 2

하지만 실제 근이 한쪽에 훨씬 가까운 경우라면 함수값을 이용해서 위치를 추정할 수도 있다.

이 아이디어를 이용하는 방법이 False-Position Method(Regula Falsi)이다.

▲ 두 점을 연결한 직선이 x축과 만나는 위치를 새로운 근의 추정값 x r 로 사용한다.

False Position에서 x_r은 다음과 같이 계산한다.

x_r = [f(x_u)x_l − f(x_l)x_u] / [f(x_u) − f(x_l)]

* 최종 정리 *

① Root

f(x) = 0

② Bracketing 조건

f(x_l) × f(x_u) < 0

③ Bisection

x_r = (x_l + x_u) / 2

④ 상대 근사 오차

ε_a = | (x_r^new − x_r^old) / x_r^new | × 100%

⑤ n회 반복 후 오차

E_aⁿ = Δx⁰ / 2ⁿ

⑥ 필요한 반복 횟수

n ≈ log₂ (Δx⁰ / E_a,d)

⑦ False Position

x_r = [f(x_u)x_l − f(x_l)x_u] / [f(x_u) − f(x_l)]