[Numerical Analysis] Solving Equations, Root Finding Method

• 식의 해를 구하는 방법에 대하여 기술한 포스팅이다. 
• 'Numerical Methods and Optimizaiton : An Introduction (Sergiy Butenko)' - chapter 4 를 참고하였다 

 

 

1. Fixed Point Method

만약 root를 찾고 싶은 식 $F(x)$ 를 다음과 같이 표현해보자

$$F(x)= 0$$

위의 식은 다음과 같이 $f(x)$ 로 바꾸어 해를 구하면 iterative 한 방법으로 구할 수 있다

$$f(x)  = x - \alpha F(x)\ \alpha \neq 0$$

이때 $f(x)$ 가 $x$ 와 같아지는 $x^*$를 찾는다면 자연스럽게 

$$f(x^*) = x^* - \alpha F(x^*)\\ 0 =  - \alpha F(x^*)$$

와 같아짐을 알수있다.

 

이와 같은 성질을 이용하여 다음과 같이 iteration을 $f(x^*) = x^*$ 가 될 때까지 진행하여 해를 구할 수 있다.

$$x_{k+1} = f(x_k),\ \ k = 0,1,...$$

 

• 하지만 convergence 하지 못하는 경우가 존재한다.

2. Bracketing Method

함수 $f : [a,b] \rightarrow \mathbb{R}$ 에서 양수의 함수값의 곱이 음수를 가지는 경우 해가 존재함을 intermediate value theorem을 통해 알 수 있다. Bracketing method 는 이와 같은 경우 a 와 b 사이의 값인 c 의 함수값의 음양여부에 따라 a 혹은 b로 치환하여 범위를 iterative하게 줄여 나가는 방법을 이용한다.

 

2.1 Bisection method 

c 를 a와 b의 중간값으로 지정하고 범위를 줄여나가는 방법이다.

 

위의 그림과 같은 예시에서 중간 값 c 의 함수값 $f(c)$를 확인하여 같은 부호를 지닌 a 혹은 b 를 c 의 값으로 치환하여 범위를 줄인다. 그림의 예시를 통해 확인 해 보면 첫번째 iteration의 $c_0$ 와 같은경우 b 의 함수값과 부호가 - 로 같으므로 b1의 값이 c0으로 치환되어 첫번째 iteration 이후의 범위는 [a , b1] = [a , c0] 가 된다.

 

2.2 Regular-falsi method

bisection method 와 유사한 방법으로 a 와 b 사이의 중간값을 c 로 잡는 대신 (a , f(a)), (b, f(b)) 직선의 방정식과 x 과의 접점을 c 로 잡아 범위를 줄여나가는 방식이다.

$$y-f(b) = \frac{f(b)-f(a)}{b-a}(x-b)$$

이 때 x 축과의 접접을 구하기 위하여 y = 0 을 대입하면,

$$0-f(b) = \frac{f(b)-f(a)}{b-a}(x-b)$$

$$\frac{f(b)-f(a)}{b-a} = -\frac{f(b)}{x-b} = \frac{f(b)}{b-x}$$

와 같음을 알수있다. 이를 x에 관하여 정리하면

$$x = b-f(b)\frac{b-a}{f(b)-f(a)}=\frac{af(b)-bf(a)}{f(b)-f(a)}$$

즉 k번째 iteration의 새롭게 확인하여야 할 함수값 $c_k$는 

$$c_k = \frac{a_kf(b_k)-b_kf(a_k)}{f(b_k)-f(a_k)}$$

이경우도 첫번째 iteration c0의 함수값 ($f(c_0)$)이 음의 부호를 가지므로 b 가 c 로 치환된다.

 

3. Newton-Raphson method

Newton's method 도 regula-falsi method 와 유사한 방법으로 진행된다. 다른 점이 있다면 Newton's method 의 직선의 방정직은 시작점 $x_0$에서의 함수의 tangent line을 구하여 이 직선과 x 축이 만나는 다음 점을 $x_1$으로 iteration을 나아간다는 것이다. 이러한 iteration을 수행하기 위하여 first order Taylor's series approximation이 사용된다.

 

$x_k$ 에서의 접점의 방정식을 first order Taylor's series approximation 을 통해 표현하면,

$$f(x) \sim f(x_k) + f'(x_k)(x-x_k)$$

x 축에 해당하는 값을 구하기 위하여 $f(x) = 0$ 을 넣고 x에 관하여 정리하면

(이때 x는 다음 iteration 인 k+1 ineration의 x 값이 되므로 $x_{k+1}$ 으로 적도록 하겠다)

$$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$$

아래와 같이 접점의 방정식을 통해 iteration이 진행됨을 확인해 볼 수 있다.

4. Secant Method

Newton's method의 응용으로, derivative ($f'(x)$) 를 계산하는 방법 대신 difference-based approximation을 사용하는 방법을 사용한다.

$$f'(x) \approx \frac{f(x_k) - f(x_{k-1})}{x_k-x_{k-1}}$$

이를 사용하여 iteration을 표현하면

$$x_{k+1} = x_k - f(x_k)\frac{x_k - x_{k-1}}{f(x_k)-f(x_{k-1})}$$