[수치해석 04] 개구간법(Open Methods)

구간법(Bracketing methods)

미리 설정된 구간 내에서 근을 구하는 방식으로, 반복적으로 구간법을 적용해 참값의 추정값을 구할 수 있다.

추정값이 참값에 접근하므로 수렴한다.

 

개구간법(Open methods)

한개 또는 두개의 초기값으로 계산을 시작한다.

계산이 진행됨에 따라 발산하여 근에서 멀어질 수도, 수렴하여 근에 가까워질 수도 있다.

수렴하는 경우, 구간법에 비해 빠르게 수렴한다.

 

 

이분법

개구간법. 빠르게 수렴하고 있음.

 

개구간법. 발산하고 있음

 

고정점 반복법

 

g(X) = X 인 X(i) 를 함수 g 의 고정점이라고 한다.

ex) g(x) = x^2 - 2 이면, g(2) = 2 이므로, (2, 2)는 고정점

 

g(X) = X 이므로, g(X) - X = 0 의 근이 고정점.

 

사용 방법 : f(x) = 0 을 x = g(x) 형태로 변형하여 계산

 

ex)

 

이전 계산 단계의 X(i)를 이용하여 새로운 추정값 X(i+1) 에 대한 식을 계산하는 반복식을 얻을 수 있다.

근사 백분율 상대오차를 이용하여 추정값을 얻는다.

X(i+1) = g(Xi)

백분율 상대오차

 

𝜀t, 참 백분율 상대오차를 구하려면, 참값을 따로 계산하여 얻어야 한다.. 이 부분에서 삽질했다.

위 식을 계산하는 파이썬 코드.

from math import exp

x = 0
xp = 0
fx = lambda x: exp(-1 * x)
rfx = lambda x: exp(-1 * x) -x
et = 100.0
ea = 100.0
curVal = x

xt = 0.567138449664162 
# xt 구하려면 참값 먼저 구해야 한다. excel로 구했음

findet = lambda a : abs((xt - a) / xt) * 100.0
findea = lambda xtp, xt : abs((xtp- xt)/xtp) * 100.0

for i in range(1,11):
    x = xp
    etb = et
    xp = fx(x)
    ea = findea(xp, x)
    et = findet(xp)
    print(xp, ea, et, et/etb, sep='\t')
    
#결과
#1.0     100.0   76.32378841395116       0.7632378841395117
#0.36787944117144233     171.8281828459045       35.13410325304401       0.46032965584058816
#0.6922006275553464      46.85363946133844       22.05143699307311       0.6276362551294825
#0.5004735005636368      38.30914659333314       11.754616379827834      0.533054439196876
#0.6062435350855974      17.446789681151248      6.895156807758647       0.5865913939642867
#0.545395785975027       11.156622525381316      3.8337488318787423      0.5560060400025838
#0.5796123355033789      5.9033508144086735      2.199442807413849       0.5737055044203311
#0.5601154613610891      3.480866979624528       1.2383199035846812      0.563015277965206
#0.571143115080177       1.9308039312598229      0.70611777748209        0.5702224243008809
#0.5648793473910495      1.1088682420515694      0.3983334712097725      0.5641176074481086

et / et-1 의 값은 0.56 내외로 존재하게 된다.

 

수렴

선형 수렴은 고정점 반복법의 특징이다.

각 반복 계산에 대한 참 백분율 상대오차(𝜀t)는 이전의 반복 계산에서 나온 오차에 대략 비례한다.

(위의 경우 0.56정도에 수렴)

 

수렴과 발산의 개념을 그래프로 설명.

한 방정식을 두 방정식으로 분리, f1(x) = f2(x) 을 y1 = f1(x) 과 y2 = f2(x) 로 분리하여 따로 그래프를 그린다.

이들 함수가 교차하는 x 값이 f(x) = 0 의 근이 된다.

 

ex)

(a), (b) 는 수렴

(c), (d) 는 발산

(a), (c) 는 단조

(b), (d) 는 진동 또는 나선 형태

 

y2 = g(x) 의 기울기의 절대값이 y1 = x 의 기울기보다 작을 때, 즉, |g'(x)| < 1 이면 수렴한다

 

고정점 반복법의 수렴

고정점 반복법 알고리즘

def Fixpt(g, x0, es, imax):
    xr = x0
    iter = 0
    ea = 100
    while ea >= es and iter < imax:
    	iter += 0
        xrold = xr
        xr = g(xrold)
        if xr != 0:
            ea = abs((xr-xrold)/xr) * 100.0
    return (xr, ea, iter)

예시

from math import exp
fx = lambda x: exp(x * -1)

print(Fixpt(fx, 0, 1e-4, 50))

# 결과
# (0.56714343762633, 7.172649124324047e-05, 27)

Newton-Raphson 법

많이 사용되는 개구간법 중 하나.

X(i) : 근의 초기 가정값

X(i+1) : ( X(i) , f( X(i) ) )에서의 접선이 x축과 만나는 점에서의 개선된 근의 추정값

 

( X(i) , f( X(i) ) ) 에서의 접선의 기울기는 f'( X(i) ) 이고, ( X(i), f( X(i) ) ), ( X(i + 1) , 0) 을 지난다.

 

공식

 

예시

 

위에서 고정점 반복법을 이용해 해결한 문제를 Newton-Raphson 방식으로 풀어보자

결과

from math import exp

ft = lambda t: t - (exp(t* -1) - t) / (-exp(t* -1) -1)
print(Fixpt(ft, 0, 1e-4, 50))

#결과
#(0.5671432904097811, 2.2106391984397623e-05, 4)

Taylor 급수 전개로 Newton-Raphson 법 유도하기

Taylor 급수

테일러 급수

1차 도함수 이상을 무시

x축과의 교점을 찾는다.

x(i+1)에 대해 정리

오차 분석

오차는 이전단계의 제곱에 비례

Newton-Raphson 법이 수렴이 잘 되지 않는 경우

• 근 주변에 변곡점이 존재
• 국부적인 최소값 부근에서 진동
• 0에 가까운 기울기를 만날때
• 추정해를 예측하는 접선이 x축과 수평

코드 구현

def newtraph(f, df, x0, es, imax):
    """
    @input f : 함수
    @input df : 도함수
    ...
    """
    xr = x0
    iter = 0
    ea = 100
    while ea >= es and iter < imax:
        iter+= 1
        xrold = xr
        xr = xr - f(xr)/df(xr)
        if xr != 0:
            ea = abs((xr-xrold)/xr) * 100
    return (xr, ea, iter)


fx = lambda x: x*x - 9
dfx = lambda x: 2*x 
# newtraph(fx,dfx,5, 1e-5, 20)
print(newtraph(fx,dfx,5, 1e-5, 20))

# 결과
# (3.0, 4.6566128730773926e-08, 5)

 

할선법

Newton-Raphson법은 도함수를 구해야 하는데, 이를 자동으로 구하거나, 얻는게 어려운 경우가 존재한다.

이런 경우. 도함수를 근사하여 다음과 같이 표현한다.

이 식을 Newton-Raphson 공식에 넣는다 

이 공식은 2개의 초기값 ((i - 1) 과 (i) 에 대응)을 필요로 한다.

두 값 사이에서 f(x)의 부호가 변할 필요가 없고, 해를 포함할 필요도 없다.

 

수정된 할선법

위와 같은 경우에도 2개의 초기 가정값을 구하기 어려울 수 있다. 이 경우 추정을 위해 변화량을 이용한다.

원래 공식에 넣는다.

delta의 값은 적절하게 설정할 필요가 있는데,

 

너무 작으면 분모에서 뺄셈의 무효화가 일어날 수 있다.

너무 작으면 발산할 수도 있다.