logo

시컨트 메소드 📂수치해석

시컨트 메소드

메소드

20180903\_131323.png 20180903\_131333.png 20180903\_131343.png

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

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

설명

황금비

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

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

초기값 문제

20180903\_131820.png

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

증명 1

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

Part 1. 계차상

f[x0,x1]:=f(x1)−f(x0)x1−x0f[x0,x1,x2]:=f[x1,x2]−f[x0,x1]x2−x0 \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’(ξ)=f[x0,x1]f ’ ( \xi ) = f [ x_{0} , x_{1} ] 와 12f’’(ζ)=f[x0,x1,x2]\displaystyle {{1} \over {2}} f ’’ ( \zeta ) = f [ x_{0} , x_{1} , x_{2} ] 를 만족하는 ξ∈H{x0,x1}ζ∈H{x0,x1,x2} \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. α−xn+1=−(α−xn−1)(α−xn)f′′(ζn)2f’(ξn)\displaystyle \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f ''( \zeta _{n} ) } \over { 2 f ’ ( \xi_{n} ) }}

xn+1=xn−f(xn)xn−xn−1f(xn)−f(xn−1)x_{n+1} = x_{n} - f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} 의 양변에 −1-1 을 곱하고 α\alpha 를 더하면 α−xn+1=α−xn+f(xn)xn−xn−1f(xn)−f(xn−1) \alpha - x_{n+1} = \alpha - x_{n} + f ( x_{n} ) {{ x_{n} - x_{n-1} } \over { f ( x_{n} ) - f ( x_{n-1} ) }} 이고, α−xn+1=α−xn+xnf(xn)−xn−1f(xn)f(xn)−f(xn−1)=xnf(xn)−xn−1f(xn)+αf(xn)−xnf(xn)−αf(xn−1)+xnf(xn−1)f(xn)−f(xn−1)=1f(xn)−f(xn−1)[−xn−1f(xn)+αf(xn)−αf(xn−1)+xnf(xn−1)]=1f(xn)−f(xn−1)[(α−xn−1)f(xn)−(α−xn)f(xn−1)]=−(α−xn−1)(α−xn)f(xn)−f(xn−1)[f(xn)xn−α−f(xn−1)]=−(α−xn−1)(α−xn)f(xn)−f(xn−1)[f(xn)−f(α)xn−α−f(xn−1)−f(α)xn−1−α]=−(α−xn−1)(α−xn)1f(xn)−f(xn−1)[f[xn,α]−f[xn−1,α]]=−(α−xn−1)(α−xn)xn−xn−1f(xn)−f(xn−1)[f[xn,α]−f[xn−1,α]xn−xn−1]=−(α−xn−1)(α−xn)f[xn−1,xn,α]f[xn−1,xn] \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*} 이다. 정리하면 α−xn+1=−(α−xn−1)(α−xn)f[xn−1,xn,α]f[xn−1,xn] \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} ] }} 이고, 계차상의 성질에 의해 다음을 얻는다. α−xn+1=−(α−xn−1)(α−xn)f′′(ζn)2f’(ξn) \alpha - x_{n+1} = - ( \alpha - x_{n-1} ) ( \alpha - x_{n} ) {{ f ''( \zeta _{n} ) } \over { 2 f ’ ( \xi_{n} ) }}

Part 3. 수렴성

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

M:=max⁡x∈I∣f′′(x)∣2min⁡x∈I∣f′(x)∣ M := {{ \max_{x \in I } | f '' (x) | } \over { 2 \min_{x \in I} | f '(x) | }} 이라고 정의하면 Part 1에서 얻은 결과에 따라 ∣α−xn+1∣≤∣α−xn∣∣α−xn−1∣M | \alpha - x_{n+1}| \le | \alpha - x_{n} | | \alpha - x_{n-1} | M 양변에 MM 을 곱하면 ∣α−xn+1∣M≤(∣α−xn∣M)⋅(∣α−xn−1∣M) | \alpha - x_{n+1}| M \le ( | \alpha - x_{n} | M ) \cdot ( | \alpha - x_{n-1} | M ) 충분히 작은 II 를 상정했으므로 ε:=max⁡{(∣α−xn∣M),(∣α−xn−1∣M)}<1 \varepsilon := \max \left\{ ( | \alpha - x_{n} | M ) , ( | \alpha - x_{n-1} | M ) \right\} < 1 을 잡으면 ∣α−xn+1∣M≤ε2 | \alpha - x_{n+1}| M \le \varepsilon^2 ∣α−xn+3∣M≤(∣α−xn+2∣M)⋅(∣α−xn+1∣M)≤ε2⋅ε=ε3 | \alpha - x_{n+3}| M \le ( | \alpha - x_{n+2}| M ) \cdot ( | \alpha - x_{n+1}| M ) \le \varepsilon^2 \cdot \varepsilon = \varepsilon^3 ∣α−xn+4∣M≤(∣α−xn+3∣M)⋅(∣α−xn+2∣M)≤ε3⋅ε2=ε5 | \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 위와 같은 방법으로 부등식 ∣α−xn+m+1∣M≤(∣α−xn+m∣M)⋅(∣α−xn+m−1∣M)≤εqm⋅εqm−1=εqm+1 | \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} } 을 얻는다.

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

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

■

구현

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

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

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)

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

20180903\_125940.png

  1. Atkinson. (1989). An Introduction to Numerical Analysis(2nd Edition): p68~69. ↩︎