시컨트 메소드

메소드

$f,f’,f’’$ 가 $\alpha$ 의 근방에서 연속이고 $f(\alpha) = 0, f '(\alpha) \ne 0$ 이라고 하자.

$\alpha$ 와 충분히 가까운 초기값 $x_{0} , x_{1}$ 에 대해 $$ x_{n+1} := x_{n} - f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} $$ 과 같이 정의된 수열 $\left\{ x_{n} \right\}$ 은 $n \to \infty$ 일 때 $\alpha$ 로 $\displaystyle {{1 + \sqrt{5} } \over {2}}$ 차 수렴한다.

설명

황금비

수렴차수가 상당히 낯이 익을 것이다. 바로 황금비인 $\displaystyle {{1 + \sqrt{5} } \over {2}} = 1.618 \cdots$ 인데, 수열의 정의에서 세 개의 연속된 항을 사용해서 증명 중에 피보나치 수열이 등장한다. 시컨트 메소드의 유용성을 언급하기 이전에 상당히 흥미로운 현상이다. 이 차수는 시컨트법이 바이섹션 메소드보다는 빠르지만, 뉴턴-랩슨 메소드보다는 느림을 의미한다.

뉴턴-랩슨 메소드가 더 빠른데도 굳이 이런 방법을 고안한 이유는 도함수를 구하는 게 지나치게 어려울 때가 있기 때문이다. 또한 계산량으로 비교하자면 수렴차수가 낮기 때문에 뉴턴-랩슨 메소드에 비해 계산 횟수가 많긴 하지만, 한 번 한 번의 계산 비용 측면에선 시컨트 메소드가 나을 수 있다. 어떤 방법이 더 나은지는 문제에 달려있다. (그러나 솔직히 말해서 뉴턴 메소드 외엔 거의 안 쓴다.)

초기값 문제

뉴턴-랩슨 메소드와 마찬가지로 초기값이 잘못 주어질 경우, 충분히 $\alpha$ 와 가깝지 않아서 수렴하지 않을 수 있다.

증명 ¹

• $\mathscr{H} \left\{ a,b,c, \cdots \right\}$ 는 $a,b,c, \cdots$ 를 포함하는 가장 작은 구간을 나타낸다.

Part 1. 계차상

$$ \begin{align*} f [ x_{0} , x_{1} ] :=& {{ f ( x_{1} ) - f ( x_{0} ) } \over { x_{1} - x_{0} }} \\ f [ x_{0} , x_{1} , x_{2} ] :=& {{ f [ x_{1} , x_{2} ] - f [ x_{0} , x_{1} ] } \over { x_{2} - x_{0} }} \end{align*} $$ 을 정의하자. 이들을 계차상이라 부르며, $f ’ ( \xi ) = f [ x_{0} , x_{1} ]$ 와 $\displaystyle {{1} \over {2}} f ’’ ( \zeta ) = f [ x_{0} , x_{1} , x_{2} ]$ 를 만족하는 $$ \begin{align*} \xi \in& \mathscr{H} \left\{ x_{0} , x_{1} \right\} \\ \zeta \in& \mathscr{H} \left\{ x_{0} , x_{1} , x_{2} \right\} \end{align*} $$ 가 존재한다.

Part 2. $\displaystyle \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f ''( \zeta _{n} ) } \over { 2 f ’ ( \xi_{n} ) }}$

$x_{n+1} = x_{n} - f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }}$ 의 양변에 $-1$ 을 곱하고 $\alpha$ 를 더하면 $$ \alpha - x_{n+1} = \alpha - x_{n} + f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} $$ 이고, $$ \begin{align*} \alpha - x_{n+1} =& \alpha - x_{n} + {{ x_{n} f ( x_{n} ) - x_{n-1} f ( x_{n} ) } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \\ =& {{ x_{n} f ( x_{n} ) - x_{n-1} f ( x_{n} ) + \alpha f(x_{n}) - x_{n} f(x_{n}) - \alpha f(x_{n-1}) + x_{n} f(x_{n-1}) } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \\ =& {{1 } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ - x_{n-1} f ( x_{n} ) + \alpha f(x_{n}) - \alpha f(x_{n-1}) + x_{n} f(x_{n-1} ) \right] \\ =& {{1 } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ ( \alpha - x_{n-1} ) f ( x_{n} ) - ( \alpha - x_{n} ) f(x_{n-1} ) \right] \\ =& - {{ ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ {{ f ( x_{n} ) } \over { x_{n} - \alpha }} - {{ f(x_{n-1}) }} \right] \\ =& - {{ ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ {{ f ( x_{n} ) - f(\alpha) } \over { x_{n} - \alpha }} - {{ f(x_{n-1} ) - f( \alpha) } \over { x_{n-1} - \alpha }} \right] \\ =& - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ 1 } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ f[ x_{n} , \alpha ] - f[ x_{n-1} , \alpha ] \right] \\ =& - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} \left[ {{ f[ x_{n} , \alpha ] - f[ x_{n-1} , \alpha ] } \over { x_{n} - x_{n-1} }} \right] \\ =& - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f [ x_{n-1} , x_{n} , \alpha ] } \over { f [ x_{n-1} , x_{n} ] }} \end{align*} $$ 이다. 정리하면 $$ \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f [ x_{n-1} , x_{n} , \alpha ] } \over { f [ x_{n-1} , x_{n} ] }} $$ 이고, 계차상의 성질에 의해 다음을 얻는다. $$ \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f ''( \zeta _{n} ) } \over { 2 f ’ ( \xi_{n} ) }} $$

Part 3. 수렴성

주어진 가정을 모두 만족하는 $\alpha$ 의 근방으로써 충분히 작은 $I : = [ \alpha - \delta , \alpha + \delta ]$ 를 생각하자.

$$ M := {{ \max_{x \in I } | f '' (x) | } \over { 2 \min_{x \in I} | f '(x) | }} $$ 이라고 정의하면 Part 1에서 얻은 결과에 따라 $$ | \alpha - x_{n+1}| \le | \alpha - x_{n} | | \alpha - x_{n-1} | M $$ 양변에 $M$ 을 곱하면 $$ | \alpha - x_{n+1}| M \le ( | \alpha - x_{n} | M ) \cdot ( | \alpha - x_{n-1} | M ) $$ 충분히 작은 $I$ 를 상정했으므로 $$ \varepsilon := \max \left\{ ( | \alpha - x_{n} | M ) , ( | \alpha - x_{n-1} | M ) \right\} < 1 $$ 을 잡으면 $$ | \alpha - x_{n+1}| M \le \varepsilon^2 $$ $$ | \alpha - x_{n+3}| M \le ( | \alpha - x_{n+2}| M ) \cdot ( | \alpha - x_{n+1}| M ) \le \varepsilon^2 \cdot \varepsilon = \varepsilon^3 $$ $$ | \alpha - x_{n+4}| M \le ( | \alpha - x_{n+3}| M ) \cdot ( | \alpha - x_{n+2}| M ) \le \varepsilon^3 \cdot \varepsilon^2 = \varepsilon^5 $$ 위와 같은 방법으로 부등식 $$ | \alpha - x_{n+m+1}| M \le ( | \alpha - x_{n+m}| M ) \cdot ( | \alpha - x_{n+m-1}| M ) \le \varepsilon^{ q_{m} } \cdot \varepsilon^{ q_{m-1} } = \varepsilon^{ q_{m+1} } $$ 을 얻는다.

피보나치 수열의 일반항: 수열 $\left\{ F_{n} \right\}$ 이 $F_{n+1} := F_{n} + F_{n-1}$ 과 같이 정의되어있다고 하자. $F_{0} = F_{1} = 1$ 이면 $\displaystyle r_{0} : = {{1 + \sqrt{5} } \over {2}}$ 와 $\displaystyle r_{1} : = {{1 - \sqrt{5} } \over {2}}$ 에 대해 $\displaystyle F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} $

$\left\{ q_{m} \right\}$ 은 다름아닌 피보나치 수열로, 충분히 큰 $m$ 에 대해 $$ q_{m} \sim {{1} \over {\sqrt{5}}} ( 1.618 )^{m+1} $$ 이다. 따라서 $$ | \alpha - x_{n+m}| \le {{1} \over {M}} \varepsilon^{ q_{m} } $$ 이고, $n \to \infty$ 일 때 $x_{n} \to \alpha$ 이고 그뿐만 아니라 $$ {{1 + \sqrt{5} } \over {2}} \sim 1.618 $$ 차로 수렴함을 확인할 수 있다.

■

구현

아래는 R로 작성된 코드다.

itmax 옵션은 최대로 반복할 횟수인데, 디폴트로 $1000$ 번을 반복해도 원하는만큼의 정밀한 해가 구해지지 않으면 계산을 포기한다.

Secant<-function(f,x0,x1,itmax=10^3,tol=10^(-8))
{
  if(f(x0)==f(x1)){stop('Wrong Initial Values')}
  
  x2 = x1 - f(x1) \ast ( ( x1  - x0 ) / ( f(x1) - f(x0) ) )
  for(i in 1:itmax)
  {
    x0 = x1
    x1 = x2
    x2 = x1 - f(x1) \ast ( ( x1  - x0 ) / ( f(x1) - f(x0) ) )
    if(abs(x2-x1)<tol) {return(x2)}
  }
  
  stop('Maybe Wrong Initial Point')
}
 
f<-function(x) {x^3 + 8}
Secant(f,-7,7)
 
g<-function(x) {x^6 - x - 1}
Secant(g,0,3)
 
h<-function(x) {exp(x)-1}
Secant(h,-2,-1)

위 코드를 실행시킨 결과는 다음과 같다.