구석에서 몰래보는 IT를 다루는 블로그

Evaluation of e^x using infinite Series

문제를 풀기에 앞서,

방법 1은 사용자가 Term를 지정해주는 방법, 테일러급수를 이용하여 접근을 하였다.

방법 2는 특정 조건까지 무한히 차수를 늘려가며 계산하는 방법이다.

import numpy as np
import math
import matplotlib.pyplot as plt

# 방법1
def func_e(x,n):
  approx_e = 0
  for i in range(n):
    num = x**i
    denom = math.factorial(i)
    term = num / denom
    approx_e += term
  print(approx_e, term)
  return approx_e
  
# 방법2 슈도코드를 기반으로 프로그래밍
# e^-10 을 구해보고자한다.
maxit = 1000000
es = 0.00000000001
x = -10

iter = 1
sol = 1
ea = 100
fac = 1
while True:
  solold = sol
  fac *= iter
  sol = sol + x**iter / fac
  iter += 1

  if sol !=  0 :
    ea = abs((sol - solold) / sol ) * 100
  print("iter=", iter, "  ea=", ea, "  es=", es, "  sol=", sol)

  if ea <= es or iter >= maxit :
    print("exact value = ", sol)
    break

Sin, Cos, 자연로그 함수 테일러 전개식을 Python으로 구현해보자

Sin, Cos, 자연로그 함수의 테일러 전개는 다음과 같다.

import math
import numpy as np
import matplotlib.pyplot as plt

# n 차수 Taylor Series

# Sin(x)
def func_sin( x,n ) :
  approx_sin = 0
  for i in range(n):
    coef = (-1)**i
    denom = math.factorial(2*i+1)
    num = x**(2*i+1)
    
    approx_sin += coef * num / denom
  return approx_sin

# Cos(x)
def func_cos( x, n ) : 
  approx_cos = 0;
  for i in range (n) :
    coef = (-1)**i
    denom = math.factorial(2*i)
    num = x**(2*i)

    approx_cos += coef * num / denom
  return approx_cos

# e^x
def func_e( x, n ) :
  approx_e = 0
  for i in range( n ) :
    coef = 1
    denom = math.factorial( i )
    num = x**i

    approx_e += coef * num / denom
  return approx_e

Taylor Series - 3 Terms Sin, Cos 함수 그래프를 그려보자

함수가 만들었다면 3 차수 Taylor 함수 그래프를 그려보자.

# 그래프로 나타내보자
angles = np.arange( -2*np.pi, 2*np.pi, 0.1)

# 진짜 sin함수인 p_sin 과 우리가 만든 테일러 급수 t_sin
p_sin = np.sin(angles)
t_sin = [func_sin(angle,3) for angle in angles]

# 진짜 cos수인 p_cos 과 우리가 만든 테일러 급수 t_cos
p_cos = np.cos(angles)
t_cos = [func_cos(angle,3) for angle in angles]

# Sin 함수
fig, g1 = plt.subplots()
g1.plot(angles,p_sin)
g1.plot(angles,t_sin)
g1.set_ylim([-5,5])
g1.legend(['sin() function','Taylor Series - 3 terms'])

# Cos 함수
fig, g2 = plt.subplots()
g2.plot(angles,p_cos)
g2.plot(angles,t_cos)
g2.set_ylim([-5,5])
g2.legend(['cos() function','Taylor Series - 3 terms'])

plt.show()

[참고]  ax.set_ylim([-5,5]) 를 함으로써 y의 범위를 축소시켜 관찰할 수 있는데, 이를 설정하지 않았을 경우

아래의 그림과 상당히 큰 y값 사이에서 진동하는 모습을 관찰 할 수가 없을 것이다.

Taylor Series - n Terms : Sin, Cos함수와 1 ~ 6 Terms 함수 비교

앞에서 만들어둔 func_cos( x, n ) 함수를 활용하여

1 ~ 5 차수까지의 Cos Taylor 함수를 그래프에 그려서 비교해보자.

import math
import numpy as np
import matplotlib.pyplot as plt

angles = np.arange( -2*np.pi, 2 * np.pi, 0.1)
p_cos = np.cos( angles )
p_sin = np.sin ( angles )

fig, g1 = plt.subplots()
g1.set_ylim([-7,3])
g1.plot(angles, p_sin)

fig, g2 = plt.subplots()
g2.set_ylim([-7,3])
g2.plot( angles,p_cos )

# 1차수부터 5차수 까지의 Sin Taylor Series
for n in range ( 1, 6 ) :
  t_sin = [func_sin(angle, n) for angle in angles]
  g1.plot(angles, t_sin)

# 1차수부터 5차수 까지의 Cos Taylor Series
for n in range( 1, 6 ):
  t_cos = [func_cos( angle, n ) for angle in angles]
  g2.plot( angles,t_cos )

plt.show()

[참고] 관찰하기 편하도록 set_ylim([ -7, 3 ])로 지정해 주었습니다.

작업한 Colab 주소

Open Method

Bracketing method는 두 점 사이. Lower Bound와 Upper Bound 사이에서 근의 유무를 찾아냈습니다.

두 점을 이용해서 근을 탐색하였고 방법마다 속도의 차이는 있겠지만 반드시 근을 찾아냈습니다.

하지만 Open Methods는 하나의 점만으로 근을 찾아낼 수 있습니다.

Simple Fixed-Point Iteration방법과 Newton-Raphson 방법이 있습니다.

방법 1) Simple Fixed-Point Iteration

하나의 점 ( 고정 점) 을 지나가는 함수에 대해서 조사하는 방법으로 만일 y = x와 교점이 없다면 이 방법을 사용할 수 없습니다.

다음과 같은 방법으로 y = x와 주어진 함수의 교점을 찾아낼 수 있도록 함수를 변형하는 것이 중요합니다.

시작점 c(i)를 잡았다면 f(c)의 값을 y = x 함수에 직교하도록 그어서 닿은 점을 c(i+1) 구합니다.

반복해서 c(i+1)의 값을 이용해 f(c(i+1))의 값을 구해 y = x 함수에 직교하도록 그어서 닿은 점을 c(i+2) 구합니다.

다음과 같은 과정을 반복하던 중 f(c(i)) = c(i)인 값이 Root가 되는 값입니다.

[예제]

[아래의 Solution] f(x)식을 우선 변형하여 접근합니다.

그래프를 그려보면 반복할 수록 근에 가까워지는지 또는 진동하거나 발산하는지 알 수 있다.

(a) (b) 의 경우, 근에 수렴하고 있지만,

(c) (d) 의 경우, 근에서 점점 멀어지고 있는 상황이다.

The Newton-Raphson Method

가장 널리 사용되고있는 Root-locating formulas

시작점 x(i)에서 직교하는 직선을 그어 x축과 만다는 점 x(i+1)를 구한다.

x(i+1)에서 직교하는 직선을 그어 x축과 만나는 점 x(i+2)를 구한다.

. . . . .(과정을 반복해서 근을 찾아간다). . . . . .

동일한 예제를 통해 이해해보자. 다음 함수의 근을 구해보자.

x(i)를 반복할수록 근에 가까워질 수 있는데

단, 4번 만에 실제 값에 가까워진 것을 알 수 있다.

Quadratic Convergence : 실제 값(참 값)에 해당하는 숫자가 과정을 거칠 때마다 2배씩 늘어나는 과정을 의미한다.

더보기

Quadratic Convergence

자료의 출처  [위키백과 : 뉴턴 방법]

그러나 언제나 하나의 방법이 모든 상황에서 최고의 방법이 될 수는 없다.

f(x) = x ^ 10 - 1 함수에 대한 근을 구하고자 할 때 시작점 x = 0.5에서 근을 구해보자.

실제 값( 참 값) x = 1에서 Iteration을 반복할수록 멀어지고 있음을 알 수 있다. 이처럼 뉴턴 방법 또한 항상 최적의 방법이 될 수 없고, 시작 값에 따라서 다른 결과를 마주할 수 있다.

(a), (b) Root 근처에 가지 못하고 헛돌고 있는 상황

(c) Root을 찾지 못하고 값이 많이 튀고 있는 상황

(d) Root가 없음을 알지 못하고 탐색 중인 상황

The Newton-Raphson Method를 사용해서 프로그래밍할 때 팁

1) 그래프에 점을 찍어가면서 상황을 관찰하기

2) 반복할 때 Iteration Max를 정해 부어서 Oscillating, Convergnet, Divergent solution을 방지할 수 있다.

3) f(x)에서 편미분 한 값이 0이 될 경우엔 더 이상 탐색하지 못하므로 이 상황에 대해 인지해야 한다.

요약

Open Method는 Bracketing Methods과는 달리 한 점을 이용해서 근을 구할 수 있으며

Newton-Raphson, Simple Fixed-Point 방법이 있다.

Simple Fixed-Point 방법의 경우 y = x 함수에 접점이 없다면 해를 구할 수 없고, 그래프를 그리며 plotting 과정을 통해 관찰하여 해에 근접하는지 발산하는지를 파악할 수 있다.

Newton-Raphson의 경우, 한 시작점에서 직교하는 접선을 이용하는 방식으로 시작 점에 따라서 근을 구할 수도 못 구할 수도 있다. 항상 Best인 방법은 없다.

The False-Position Method

이전 포스팅에서 다룬 Bisection의 단점.

  1) 근이 있다는 것에 대해서는 명백하지만 "Brute-Force" 접근 방법으로 상대적으로 비효율적이다.

  2) 지속해서 접근하다 보면 둘 점 사이의 간격이 너무나 가까워져 Round-Off Error를 다룰 때 보았듯이

오차가 커지는 현상이 있다.

  3) 오차가 감소하긴 하지만 증가하다가 감소하는 그래프이다.

이번시간에 다룰 False-Position Method는 Bisection과 같은 Bracketing 방법이지만 접근 방법이 조금 다르다.

False-Position은 두 점 xl, xu사이의 중간값으로 접근하는 Bisection과 달리

f(xl), f(xu) 사이의 점을 끄어 x축과 만나는 점 xr을 구한다.

f(xr)의 값을 이용해서 범위를 좁혀 나간다.

f(xl) < 0 이고 f(xr) < 0 인경우 다음 반복 시에는 xl 대신 xr을 이용하여 f(xr), f(xl) 사이의 선을 끄어

x축과 만나는 새로운 점 xr을 구해서 반복해 나간다. 

동일한 문제를 Bisection과 False Position으로 접근 하였을때

오차 감소율은 다음과 같았다.

그러나 False-Position이 항상 좋은 것만은 아니다.

Pitfalls of the False-Position Method

▷ Biseciton을 통해 접근하였을 때 결과

▷ False-Position으로 접근 하였을 때 결과

두 표를 비교해 보았을 때

Bisection은 단 6번 만에 오차율이 1.6%였으나, False-Position은 59.2%로 접근하는 대에 상당한 시간이 걸릴 것으로 추측된다.

False-Position 접근 방법을 그래프를 통해 보면 시간이 오래 걸리는 이유를 쉽게 알 수 있다.

1.0에 교점의 간격이 상당히 촘촘한 것을 알 수 있다.

Modified False Position

기존 False Position을 수정하여 촘촘하게 접근하여 걸리던 시간을 단축시키고자 하는 방법입니다.

Bisection과 False-Position 방법을 합쳐서 만든 방법으로

Bisection보다는 작은 Step을, False 보다는 큰 Step으로 간격을 줄여 나갑니다.

[Pseudocode]

위 함수를 0.01% 오차율을 위해서는

False-position 방법으로 접근하였을 때 39번

Bisection 방법으로 접근하였을때 14번의 반복이 필요했다면

Modified false-position 방법으로 접근 하였을 때는 12번의 반복으로 충분했다. 

Limit, Multiple Roots

우리가 원하는 근을 찾아내기 위해서는 다음과 같은 순서를 통해 찾아낼 수 있었다.

1) 근이 있는 범위부터 찾아낸다.

2) 사용하고자 하는 정책을 활용해서 범위 내에 근이 존재하는 범위를 좁혀 나간다.

그러나 근이 있는 범위를 잘 설정하지 못하면 다음과 같은 문제가 야기된다.

위와 같은 함수에서 범위를 잘못 설정한다면 우리가 원하는 값을 얻지 못할 수도 있다.

범위 내에 다중 근이 존재할 경우 다음과 같이 문제가 생길 수 있다.

다음 시간에는 이과 같은 문제를 해결하고자 한다.

요약

Bisection과 다른 방법으로 False-Position Method를 알아보았다.

두 점 사이에 직선을 그어서 그 직선이 x축과 만나는 점 xr를 찾아서 f(xr)이 0보다 큰지, 작은지에 따라서 범위를 좁여 나아가는 방식이다.

False-Position Method는 Bisection과 비교하였을 때

오차 감소율이 계속해서 감소한다는 차이점이 있지만 Bisection보다 다소 오랜 시간 걸릴 수도 있다

Roof of Equations

우리가 근을 찾고자 한다면 어떻게 해야 할까?

고등학교 때 2차 함수에서 근의 공식을 떠올려 보면

다음과 같은 식을 이용해서 x에 대한 근을 구할 수 있을 것이다.

하지만, 그보다 고 차원의 식이나, 초월함수의 경우엔 어떻게 구해야 할까?

최대한 가까운 근을 얻고자 노력하고 그 오차를 줄여 나가면서 극복할 수 있을 것이다.

다음과 같이 앞서 테일러급수에서 보았듯이, x에 대한 차수를 늘려 가면서 원하는 그래프에 가까워질 것이다.

그러나 Algebraic Function. 즉, 대수 함수에서는 가능했지만 초월함수에서는 상황이 조금 다르다.

초월함수에서는 어떤 방식으로 접근해야 근을 구할 수 있을까?

어느 방법만을 사용하는 것이 아니라, 모든 방법을 동원해서 접근하고자 노력해야 한다.

Graphical, 먼저 그래프를 그려서 시각적으로 우리가 이해한다면 접근하기 쉬울 것이다.

Bracketing Method 방법은 임의의 두 점을 정해서 두 점의 함숫값의 곱이 0보다 작다면

다른 하나의 함숫값은 양수, 다른 함수값은 음수일 것이므로 두 점 사이에는 0을 지나는 점이 하나 이상 존재할 것이다.

예제 1] Sin 10x + cos 3x

그럼 예제를 통해 한번 이해해보자 다음과 같은 f(x) 식이 있을 때, root는 x=0에서 x=5 사이 몇몇 근이 존재한다.

문제를 풀기 위해 그래프를 그려보자.

우리는 sin 10x + cos 3x 그래프를 보면서 4.2와 4.3 사이에 근이 있음을 할 수 있다.

예제 2] 정확한 값에 접근하기 위한 방법 Bisection Method

만일 그래프를 그렸을 때, 12와 16 사이에서 정확한 근에 접근하기 위해서는 어떻게 해야 할까?

12와 16 사이의 중간값 14를 기준으로

1) [12,14] [14,16] 사이에서 근이 있는 범위를 추려낸다.

그래프를 보면 알겠지만 12와 14 사이의 곱은 0보다 크므로 둘 사이에 근이 없음을 알 수 있다.

따라서 [14,16]에 대해서 조사해보니 근이 존재함을 알 수 있었다.

2) 다시 14와 16 사이의 중간값 15를 기준으로 [14,15] [15,16] 사이의 값을 조사한다.

14와 15 사이에 근이 존재함을 알 수 있다.

3) 이 과정을 반복한다. 14와 15 사이의 중간값 14.5를 기준으로 조사를 진행한다.

총 6번의 반복을 통해 아래와 같은 그래프 결과를 얻었다.

그러나, 반복 횟수에 따른 Error 관계를 보면 다음과 같은 그래프가 그려진다.

전체적으로 보았을 때 감소는 하지만 상향과 하향을 반복하며 감소하고 있다.

The Bisection Method

[Pseudocode]

요약

대수 함수와 달리 초월함수에서는 Bisection과 Open Methods를 통해서 근에 접근할 수 있다.

(Open Methods는 추후에 다룰 예정입니다.)

Bisection은 f(x) f(y) < 0 일 때, [x, y] 사이에 근이 있다. 근 사이를 좁히기 위해서 xr= (x+y) / 2로 접근한다.

다음 조건 중 하나라도 만족하면 중단한다.

   1) ea < es

   2) iter >= 사용자가 정한 최대 반복 횟수

   3) f(xr) = 0

어느덧 평화로운 모험 섬을 참가하고자

기회의 섬을 방문한 술식전개X냥냥펀치

이후 필드 보스를 잡으러 와서 인벤토리를 정리하던 도중

기분이 좋은 소리를 듣게 되는데...

네?

네?

.. 네?!!!!!!!!!!!!!

Yeaaaahhhhh~

이로써 섬의 마음 반납하면 총 61개가 완성된다고?!

시험 끝나고 나면 기억의 오르골도 도전해 보아야겠군요

그래서 이스 라펠님 오르페우스의 별은 언제 주시나요...ㅠㅠ