지난번까지는 shooting method에 대해 봤다. (비선형 문제들(Nonlinear problems) 과 shooting 방법). shooting method에서는 하나의 parameter에 과한한 방식이다. 그리고 아래의 비선형미분방정식의 해를 찾는 방식이다.
$$f(x) = 0$$
비선형 방정식을 풀기위해 사용되는 implicit 방법들이 있었다. scientific computing 의 많은 분야에서 방정식 문제는 어떠한 비선형 방정식의 해를 찾는것으로 결부되었다. 이것에 대해서는 차차 알아보겠다. 지금 이 글에서는 single variable를 갖는 함수들에게 집중해보겠다.
아래와 같은 다항식을 생각할 수 있다.
$$f(x) = \sum_{i=0}^n a_i x^i$$
위와 같은 경우에 대수의 기본정리에 의해서 $f$는 $n$개의 실수나 복소근을 갖는다는 것을 알고 있다. (물론 이때 multiplicity 를 고려해야한다.) . 일반적인 함수 $f$에 대하여 $f(x)=0$가 얼마나 많은 근을 갖는다는 것을 알기가 어렵다. 없을 수도 있고 유한개일 수도있고 무한개일수도 있다. $(a,b)$에서 많아야 하나의 해를 가질 조건중 하나는 아래와 같이 미분계수가 양수일 때이다.
$$f^{\prime}(x) >0 \text{ for all } x \in (a,b)$$
혹은 $ f^{\prime}(x) <0 \text{ for all } x \in (a,b)$일 때이다. 이것이 사실 해가 있다는 것을 의미하진 않는다. 그러나 $f$가 continuous 이고 $f(a)<0$이고 $f(b)>0$ 이라면 직관적으로 명백히 $f$는 $(a,b)$에서 적어도 하나의 해를 가질 것이다. 실제로도 그렇다. 그러면 이 해는 어떻게 찾을 것인가?
Bisection Method
$f(a)<0$이고 $f(b)>0$ 라고 가정해보자. 그러면 적어도 하나의 해가 $(a,b)$에는 존재한다. 이때는 미분가능성 마저 가정할 필요없다. 이러한 상황을 그림으로 그려보면 아래의 Figure 5.2와 같다.
$f$의 해를 근사하는 가장 간단한 방법중의 하나는 bisection method이다. $x_1 = \frac{1}{2}(a+b)$를 interval $(a,b)$의 중간점이라고 하고 $f(x_1)$를 계산해보자. 만약에 $f(x_1)>0$이라고 한다면 해 $x*$는 $a$와 $x_1$사이에 있을 것이다. 만약에 $f(x_1)<0$이라면 $x*$는 $x_1$과 $b$사이에 있다. 이 과정을 계속 반복하다보면 항상 얻어지는 interval에는 solution $x*$가 있을수 밖에 없다. 그림 5.2에서 관찰해보면 아래와 같은 성질을 만족한다.
명백히 각각의 bisection procedure의 매 step은 얻어지는interval 의 길이를 줄인다. 그리고 앞에서 언급했다시피 얻어지는 interval은 root인 $x*$를 포함한다. 그래서 $m$ step이후에는 얻어지는 interval 의 길이는 $(b-a)2^{-m}$이다. 그리고 이것은 error에 대한 bound를 보여준다.
$$|x_m – x^* | \leq \frac{|b-a|}{2^m}$$
이 bound는 $f(x_i)$들이 정확히 계산된다는 가정하에서 얻어진다. 물론 이것은 불가능에 가깝다. 왜냐하면 round off error가 존재하기 때문이다. 그러나 bisection method는 $f(x_i)$의 값을 이용하지 않는다. 대신에 $f(x_i)$의 부호를 이용한다. 그래서 bisection method를 사용하면 그래도 error잘 발생하진 않는다. $f(x_i)$의 부호가 정확히 계산되는 한에… round-off error가 부호를 변화시키는데 심각한 요소가 아니라고 생각들수 있다. 그런데 이것은 $f$의 절대값이 엄청 작을때이다. 만약에 $f(x_i)$의 부호가 정확하지 않다면 다음 subinterval을 선택하는데 있어서 잘못된 결정을 할 수 있다. 그리고 위에서 언급한 errorbound가 성립할 필요가 없다.
만약에 $f$의 값을 측정하는데 있어서 에러가 발생한다면 에러가 너무나도 크지 않는한 $f$의 부호자체는 잘 측정될것이다. $f$는 해 $x*$와 가까운 곳에서 0에 가까운 값을 갖는다. 반대로 생각할수도 있다. interval uncertainty라고 한다. $(x*-\epsilon, x*+\epsilon)$에서 $f$의 정확히 측정되지 못하는 상황이 있을수 있다.이러한 interval을 구하는데 까지 다다르렸을때 root에 대한 접근은 가장 문제가 심화된다. 불행하게도 이러한 interval을 미리 선정하는 것은 어렵다. 이것은 알려지지 않은 해 $x*$에 의존한다. 그래서 해의 근방에서 $f$의 flatness와.. 이러한 interval은 보통 관측가능하다. 잘못된 계싼을 하는동안에 말이다. 이것이 발생할 때 더이상의 counting 을 않하면 된다.
출처 및 참고글
-Golub, G. H., & Ortega, J. M. (2014). Scientific computing: an introduction with parallel computing. Elsevier.