Solving Nonlinear Equations 03 - Fixed-Point Iteration Method

Fixed-Point Iteration Method

Fixed-point iteration 방법은 $f(x)=0$ 형태의 방정식의 수치해를 구할 때 사용하는 방법이다.

$x=g(x)$형태의 방정식을 $f(x)=0$형태로 바꾸어 해를 구한다.

$$ x=g(x)\Rightarrow f(x)=g(x)-x=0\,\, $$

$y=x$와 $y=g(x)$의 교차점을 Fixed-Point라고 한다.

Fixed-Point Iteration Method 알고리즘

1. 해석해가 존재한다고 추정되는 근처에 $x$축상에 임의로 $x_1$값을 정한다.

2. $x_1$에서 수직으로 올라가서 $g(x)$와 만나는 지점 $g(x_1)$값을 찾는다.

3. $g(x_1)$값에서 수평으로 따라가서 $y=x$와 만나는 점을 찾아 그 점에서 수직으로 내려간다.

    이때의 값을 $x_2$로 한다.

4. 수치해가 충분히 해석해에 수렴할때까지 위의 과정을 반복한다.

 

- 위의 과정을 살펴보면 수치해 $x_2$는 이전 수치해 $x_1$의 $g(x_1)$값으로 정해짐을 알수 있다.

($y=x$ 는 $y$와 $x$값이 같으므로 $g(x_1)$에서 수평으로 가서 $y=x$를 만나 수직으로 내려가면 값이 동일하다.)

$$ x_{i+1}=g(x_i) $$

Fixed-Point Iteration

- 함수의 형태가 $f(x)=0$이면 그 자체로는 $x=g(x)$형태가 나오지 않아 위의 방법을 사용하지 못한다.

$f(x)$항에 $x$항을 더하고 빼줌으로서 아무것도 변하지 않았지만 위의 $x=g(x)$의 형태를 만들어 Fixed-Point itearation을

사용할 수 있다. ($f(x)+x-x=0\rightarrow f(x)+x=x=g(x)$)

$$ x=x+f(x)=g(x) $$

 

Fixed-Point Iteration이 수렴하지 않는 경우

Fixed-Point Iteration이 수렴하지 않는 경우

 

위의 그림에서처럼 과정이 반복될수록 교차지점(해석해)로부터점점 멀어져가는 것을 볼 수 있다.

- 해석해 근처에서 함수 g(x)의 미분값이 y=x의 미분값인 1보다 커지게 되면 Fixed-Point Iteration을 사용시 발산한다. 

  따라서 Fixed-Point Iteration을 적용하기 위해서는 함수 g(x)가 교차지점(Fixed-Point)의 근처에서 미분값이 1보다 작아야한다.

$$ |g'(x)|<1 $$

언제 반복을 중지 해야할까?

일반적으로 수치해석을 통해 해를 구해야하는 경우에는 해석해를 알 수 없는 경우가 많다. 

따라서 추정상대오차나 공차를 사전에 설정한 값과 비교하여 반복의 중지여부를 결정해야한다.