Solving Nonlinear Equations 01-Bisection Method, Regula Falsi method

Bisection Method

Bisection method는 $f(x)=0$ 형태의 방정식에서 수치해를 구하는 방법이다.

1. 구하려는 해의 함수값은 0이므로 $x$축 선상에 있을것이다.
2. 해가 있을 것으로 추정되는 범위 $[a,b]$를 설정한다.
3. 이때, 함수 $f(x)$는 해당구간에서 연속이어야한다. (구간내에서 함수값이 정의 되지 않는다면 수치해를 구할 수 없다.)
4. 핵심: 함수가 구간 $[a,b]$에서 x축과 만난다는 것은 해의 왼쪽과 오른쪽의 함수값의 부호가 다르다.→ 이점을 이용해 수치해에 접근한다.

구간내에서 근의 왼쪽과 오른쪽의 함수값 부호가 다르다.

Bisection Method 알고리즘

1. 해가 존재할것이라고 생각되는 구간 $[a,b]$를 설정한다. 만약 구간 내의 해가 존재한다면 $f(a)f(b)<0$일 것이다.
2. 첫번째 수치해 추정치를 구간 $[a,b]$의 중점을 택한다.$$ x_{NS1}=\frac{a+b}{2} $$
3. 만약 $f(a)\cdot f(x_{NS1})<0$ 이면 $x_{TS}$는 $a$와 $x_{NS}$사이에 존재한다.
4. 만약 $f(b)\cdot f(x_{NS1})<0$이면 $x_{TS}$는 $b$와 $x_{NS}$사이에 존재한다.
5. 위에서 구한 새로운 수치해를 이용해서 다음 범위를 구하는 방식을 구하고 있는 범위가 사전에 설정한 errorbound나 tolerance내로 들어올 때까지 반복적으로 수행한다.

범위가 반씩 줄어들면서 X_NS가 X_TS에 점점 수렴해가는 것을 볼 수 있다.

 

---

Regula Falsi method

Regula Falsi Method는 $f(x)=0$형태의 방정식 근을 찾는 수치해석적 방법이다.

1. 구하려는 해의 함수값은 0이므로 $x$축 위에 위치할 것이다.
2. 해를 포함할것이라고 예상되는 범위 $[a,b]$를 설정한다.
3. 이때, 함수 $f(x)$는 범위 $[a,b]$안에서 연속이어야 한다. (구간내의 함수값이 정의되지 않는다면 수치해를 구할 수 없다.)
4. 핵심: 각 단계에서 범위끝점을 직선으로 잇는다. 이때 $x$축과 만나는 점(일차함수의 근)을 새로운 범위의 끝점으로 설정하여 범위를 줄여나간다.

→ 주어진 범위 $[a,b]$에서 $(a,f(a))$와 $(b,f(b))$를 직선으로 그을때 만들어지는 일차함수는 다음과 같다.

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

위의 일차함수가 $x$축과 만나는 지점은 $y=0$일때로 다음과 같다.

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

위의 구한 해를 수치해 $x_{NS}$ 로 하여 새로운 범위를 설정하여 위의 방법을 반복한다.

Regula Falsi method 알고리즘

1. 해가 존재할것이라고 생각되는 범위 $[a,b]$를 설정한다. 이때 해가 존재하기 위해서는 $f(a)\cdot f(b)<0$을 만족해야한다. (Bisection Method와 비슷하다)
2. $x_{NS}=\frac{af(b)-bf(a)}{f(b)-f(a)}$을 이용하여 수치해를 구한다.
3. 수치해를 이용해 새로운 범위를 결정한다.
   1. 만약, $f(a)\cdot f(x_{NS})<0$일경우 새로운 범위는 $[a,x_{NS}]$이다.
   2. 만약, $f(b)\cdot f(x_{NS})<0$일경우 새로운 범위는 $[x_{NS},b]$이다.
4. 위에서 구한 새로운 범위를 이용해서 과정 2~3을 반복한다.
5. 사전에 설정한 specificed tolerance나 error bound내로 범위가 들어오면 과정을 종료한다.

Regula-Falsi Method를 사용하여 수치해가 실근에 수렴하는 과정