Finding roots

$ f(x) = 0 $의 해를 찾는 방법은 여러가지가 있고 x값 또한 하나의 수, 평면에서의 좌표, 3차원 이상의 공간에서의 좌표 등 여러가지 형태로 나타낼 수 있다

 

이 때 closed form expression은 일반적으로 손으로 써서 계산했던 근의 공식이라던가 사칙연산으로 나타낼 수 있는 값과 같이 일반적으로 받아들여지는 연산들의 조합으로 이루어진 solution을 말한다

이와 반대로 non-closed form(open) expression은 재귀와 같이 식으로 나타낼 수는 없지만 적절한 값을 찾아낼 수 있는 solution이다

반복적인 연산은 프로그래밍으로 구현하게 된다

 

수치해석에서의 여러 해를 구하는 방법을 크게 세가지 카테고리로 나누어 알아보자

 

Graphcial Methods

 

해를 구하기 위해 직접 그래프를 그려보는 방법이다

해가 정확하지 않아 사용에 한계가 있지만 주어진 구간에 해가 몇개인지, 해의 값이 어디쯤인지 등을 파악하기 위해 사용할 수 있다

 

 

Bracketing Methods

 

1. Incremental search

 

 

구간을 일정하게 나누어서 근이 있는지 없는지 확인하는 방법이다

$ f(x_l)f(x_u) < 0 $이면 최소 그 구간에 한개 이상의 해가 있음을 알 수 있다

구간이 너무 작으면 탐색 시간이 오래 걸리고 구간이 크면 정확한 해를 구할 수 없다

위 그림에서 incremental search를 적용한다면 0~1, 2~3, 5~6구간에서는 해가 없다고 판단한다는 것이 이 방법의 단점이다

 

2. Bisection

 

 

bisection 방법은 구간을 일정하게 나누어서 시작하는 incremental search와는 다르게 구간을 점점 좁혀나가는 방법이다

반복될 때 마다 구간은 두개의 구간으로 나뉘게 되는데 이 때 $ f(x_l)f(x_u) < 0 $인 구간을 선택하여 해가 더 작아진 구간에 포함되도록 하는 방법이다

종료조건은 threshold값보다 relative 에러값이 작아질 때 이다

$$ | {\epsilon}_a | = |{{x_r^{new} - x_r^{old}} \over {x_r^{new}}}| 100 % $$ 

위 값이 지정한 값보다 작아진다면 반복을 종료하고 해당 시점에서의 범위의 중점인 $ x_r $을 해로 사용한다

 

이 방법을 파이썬으로 구현해보았다

 

# bisection function
# Assume that there is only one root in the interval[lower,upper]
 
def bisection(lower,upper,x_old,Th):
 
    x_new = (lower+upper)/2
 
    if abs((x_old-x_new)/x_new)*100<Th:
        print("The root is estimated to be",round(x_new,6))
        return
    if function(lower)*function(upper)<0:
        if function(x_new)*function(upper)<0:
            bisection(x_new,upper,x_new,Th)
        else:
            bisection(lower,x_new,x_new,Th)
    else:
        print("Wrong interval",lower,upper)

 

함수를 재귀적으로 호출하면서 interval을 줄여주는 것을 볼 수 있다

bracket method들의 공통적인 단점인 중근 파악의 어려움과 한 공간에 여러가지 해가 있는 경우는 감지하지 못한다

 

3. False Position 

bisection method와 비슷하지만 구간을 반으로 나누는 것이 아니라 $ f(x_l),f(x_u) $를 직선화하여 구하는 방법이다

 

 

기존 범위의 두 x좌표를 이용하여 y좌표를 찾아 그 두 좌표를 직선으로 연결하여 x축과의 교점을 찾는다

이 점을 기준으로 새로운 구간을 결정할 수 있다

$$ x_r = x_u - {{f(x_u)(x_l-x_u)}  \over {f(x_l)-f(x_u)}} $$

직선의 방정식을 이용하면 위와 같은 식을 쉽게 만들어 낼 수 있다

이 방법은 bisection 방법보다 일반적으로 성능이 더 좋지만 아래와 같은 특정 경우 수렴하여 더 오래 걸릴 수도 있다

 

 

 

Open Methods

 

bracket methods와 다르게 구간이 아닌 한개 이상의 starting point에서 시작하는 방법이다

특정 식을 반복하여 실행하면서 점점 가까운 해를 찾는다

일반적으로 bracket methods보다 빠르고 중근의 경우 해의 값을 찾을 수 있다

하지만 그 해의 값이 중근인지 3중근인지 등은 파악하지 못한다

 

1. Newton-Raphson Method

 

 

f(x)의 도함수를 이용하여 접선을 그리고 그 접선이 x축과 만나는 점을 다음 해의 위치로 설정한다

반복할수록 실제 해와 가까워진다

식으로 나타내면 다음과 같다

$$ x_{i+1} = x_i - {{f(x_i)} \over {f^\prime (x_i)} } $$

 

장점은 해에 빠르게 수렴한다는 것이고 단점은 미분 불가능한 함수에서는 사용 불가능하다는 점이다

또한 initial guess와 real root 사이에 변곡점이 존재하지 않아야한다는 조건이 있다

 

파이썬으로 간단하게 구현한 경우 아래와 같다

 

# Newton-Raphson
 
def Newton_Raphson(x_old,Th):
    x_new = x_old - function(x_old)/differential_function(x_old)
    if abs((x_old-x_new)/x_new)*100<Th:
        print("The root is estimated to be",round(x_new,6))
        return   
    Newton_Raphson(x_new,Th)

 

 

2. Secant Method

Newton-Raphson method의 변형으로 도함수를 구할 수 없는 경우 사용 가능하다

미분 대신 $ f^\prime (x_i) ={ {f(x_{i-1})-f(x_i)} \over {x_{i-1}-x_i}} $와 같은 approximate값을 이용하는 것이다

approximate값을 대입하면 해를 구하는 식은 다음과 같아진다

$$ x_{i+1} = x_i - {{f(x)(x_{i-1}-x_i)}\over{f(x_{i-1})-f(x_i)}} $$

 

Newton-Raphson과는 다르게 두개의 초기값이 필요하지만 미분 불가능한 함수에서도 사용 가능하다

 

Wolfram MathWorld

Applied Numerical Methods with MATLAB for Engineers and Scientists