할선법과 오차(Secant method)

지난 글에서 [뉴턴의 방법]을 살펴보았습니다. 뉴턴의 방법은 매우 빠른 대신 미분을 해야 한다는 단점이 있었습니다. 이번에 소개할 할선법(Secant method)은 뉴턴의 방법과 같은 아이디어를 사용하면서 미분을 하지 않는 방법입니다. 할선법의 특이한 점은, 뉴턴의 방법에서 미분계수의 역할을 평균변화율이 대신하는 것입니다. 미분 대신 평균 변화율을 사용하기 때문에 시작점이 두 개 필요합니다.

기본 아이디어

1. 함수 f(x) 위에 두 점을 알고 있다. 

2. f(x)를 그 두 점을 지나는 직선의 방정식이라고 생각한다. 

3. 그 직선의 방정식의 근은 앞서 사용한 두 점보다 f(x)=0의 근에 가깝다.

4. 직선으로 근사하고 근을 구하는 과정을 반복하면 f(x)=0의 근으로 수렴한다.

 

점화식

함수 f(x)위에 두 점 $(x_n,f(x_n)) , (x_{n-1},f(x_{n-1})$을 알고 있을 때, 그 두 점을 지나는 직선의 방정식은 다음과 같습니다.

$$ y=\frac{f(x_n-)- f(x_{n-1})}{x_n -x_{n-1}}(x-x_n) + f(x_n) \tag1 $$

(1) 식은 함수 f(x)를 두 점을 기준으로 근사한 함수입니다. f(x)=0을 만족하는 x를 찾기 위해 근사식의 근을 구합니다. 근사식의 근을 $x_{n+1}$라고 할 때, (1) 식에 $(x_{n+1},0)$을 대입하여 정리합니다.

$$ x_{n+1}= x_n - f(x_n) \frac{x_n - x_{n-1}}{f(x_n)- f(x_{n-1})} , \; \; n \ge 1 \tag2 $$

(2) 식은 할선법의 점화식입니다. 뉴턴의 방법에서 점화식과의 유사성을 알 수 있습니다. 할선법의 점화식에서 평균변화율을 미분계수로 치환하면 뉴턴법의 점화식이 됩니다.

$$f'(x_n) \approx \frac{f(x_n)-f(x_{n-1})}{x_n - x_{n-1}} \tag3$$

오차

뉴턴방법에서 했던 것과 같은 방법으로 할선법이 얼마나 빠르게 수렴하는지 알아보겠습니다. 여기서부터는 식의 결과만 나열하겠습니다. 

(2) 식을 미적분학의 기법과 대수 계산을 하면 다음과 같은 식을 얻을 수 있습니다. f(x)의 근을 a라고 합시다. 

$f(a)=0, \alpha \in (a, x_n) , \beta \in (x_n , x_{n-1})$

$$a -x_{n+1} = (a-x_n)(a-x_{n-1}) \left[ \frac{-f''(\alpha)}{2 f'(\beta)} \right] \tag4 $$

오차의 크기를 간단히 보기 위해 (4) 식을 치환하여 정리합니다. 모든 항에 대해 $\left[ \frac{-f''(\alpha)}{2 f'(\beta)} \right]$의 값이 거의 같다고 가정합시다. 

$\varepsilon_n \equiv a-x_n , \left[ \frac{-f''(\alpha)}{2 f'(\beta)} \right]  = M $

$$\varepsilon_{n+1} = \varepsilon_{n} \varepsilon_{n-1} M \tag5$$

$= (\varepsilon_{n})^1 (\varepsilon_{n-1})^1 M^1$

$= (\varepsilon_{n-1})^2 (\varepsilon_{n-2})^1 M^2$

$ = (\varepsilon_{n-2})^3 (\varepsilon_{n-3})^2 M^3$

$ = (\varepsilon_{n-3})^5 (\varepsilon_{n-4})^3 M^3$

$ = (\varepsilon_{n-4})^8 (\varepsilon_{n-5})^5 M^4$

(5) 식을 계속 진행해 보면, 할선법의 오차들의 비율이 피보나치 수로 나오는 것을 알 수 있습니다. a에 충분히 가까운 $x_0, x_1$의 수렴성은 다음과 같다고합니다.

$$ \lim_{n \rightarrow \infty} {\frac{ | a-x_{n+1}|}{|a-x_n|^r}} = \left| \frac{f''(a)}{2f'(a)} \right|^{r-1} \equiv c \tag6$$

$$ c= |M|^{r-1} , \: r= \frac{1+\sqrt 5}{2}=1.62...$$

마치며

뉴턴의 방법과 할선법의 공통점은 선형함수로 근사한다는 것입니다. 선형함수로 문제를 번형시켜서 쉽게 풀고, 그 결과를 다시 문제에 넣어 더 비슷한 문제를 만들어 푸는 것입니다. 이렇게 문제를 선형성을 갖도록 변형시키는 것을 선형화(linearization)라고 합니다.