뉴턴-랩슨 메소드

뉴턴-랩슨 메소드

메소드 1

20180831\_192324.png

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

$\alpha$ 와 충분히 가까운 초기값 $x_{0}$ 에 대해 $$ x_{n+1} := x_{n} - {{ f ( x_{n} ) } \over { f' ( x_{n} ) }} $$ 과 같이 정의된 수열 $\left\{ x_{n} \right\}$ 은 $n \to \infty$ 일 때 $\alpha$ 로 쿼드러틱하게 수렴한다.

설명

뉴턴-랩슨 메소드는 그냥 뉴턴 메소드라고 불리기도 한다. 미분가능성이나 연속성과 같은 조건이 있긴 하지만 그래도 간단하고 수렴속도가 빨라 방정식 $f(x) = 0$ 의 근사해를 찾는데 유용한 방법이다.

쿼드러틱Quadratic하게 수렴한다는 말은 수렴률을 이야기할 때 $2$차적으로 수렴한다는 말인데, 적절한 번역이 없다. $1$ 차가 ‘선형’으로 번역되는 것에 비하면 그냥 $2$ 차로 수렴한다는 말은 너무 두리뭉술하고 쓰이는 용례가 적어 부득이하게 영어표현을 그대로 썼다. 그럼에도 굳이 언급한 것은 대부분의 경우 바이섹션 메소드에 비해 수렴하는 속도가 빠름을 수학적으로 보일 수 있기 때문이다.

20180831\_192719.png 그러나 ‘$\alpha$ 의 근방’이나 ‘충분히 가까운 초기값’이라는 표현에서 눈치챌 수 있듯, 실제로는 마냥 생각 없이 쓸 수 있는 방법이 아니다. 위와 같이 재수 없게 초기값을 잘못 줘서 $0$ 으로 나누는 문제가 일어나거나 수열 자체가 해와 먼 곳으로 갈 수도 있다. 그래서 코드를 쓸 때도 특정 횟수 안에 해를 구하지 못했다면 그냥 계산을 포기하는 등의 예외처리가 필요하다.

이러한 발산 에러는 수학적으로 수렴성이 증명되었음에도 실제로 쓸 때는 충분히 일어날법한 문제가 된다. 가장 중요한 사용자가 ‘$\alpha$ 의 근방’이나 ‘충분히 가까운 초기값’을 정확하게 파악하지 못할 수 있기 때문이다. 바이섹션 메소드가 느리든 어떻든 반드시 해를 구해주는 것과 비교해보면 분명한 단점이라고 할 수 있다.

같이보기

조금 더 강한 조건이 있다면 쿼드러틱하면서도 수렴성이 완전히 보장된 뉴턴-푸리에 메소드를 고려해볼 수 있다. 하지만 이 방법은 본질적으로 뉴턴-랩슨 메소드의 ‘$\alpha$ 의 근방’ 속으로 폐구간 $[a,b]$ 를 집어넣은 것에 불과하기도 하다. 따라서 조건만 다 체크한다면 뉴턴-랩슨 메소드와 정확히 똑같아지고, 별도로 다른 코드를 작성할 필요가 없다.

증명

전략: 테일러 전개를 통해 $2$차 항을 끌어낸 후 재귀적인 부등식을 만들어 수렴성을 보인다.

Part 1. 테일러 전개

$f$ 를 $x_{n}$ 에 대해 테일러 전개하면 $x$ 와 $x_{n}$ 사이의 $\xi_{n}$ 에 대해 $$ \displaystyle f(x) = f(x_{n} ) + (x - x_{n}) f’(x_{n}) + {{(x - x_{n})^2 } \over {2}} f’' (\xi_{n}) $$ $f( \alpha ) = 0$ 이므로 $x = \alpha$ 를 대입하면 $$ \displaystyle 0 = f(x_{n} ) + ( \alpha - x_{n}) f'(x_{n}) + {{( \alpha - x_{n})^2 } \over {2}} f'' (\xi_{n}) $$ 양변을 $f'(x_{n})$ 으로 나누면 $$ \displaystyle 0 = {{f(x_{n} )} \over {f'(x_{n})}} + \alpha - x_{n} + {{( \alpha - x_{n})^2 } \over {2}} {{f'' (\xi_{n})} \over { f'(x_{n}) }} $$ $\displaystyle {{ f ( x_{n} ) } \over { f' ( x_{n} ) }} - x_{n} = - x_{n+1}$ 이므로 $$ \displaystyle 0 = \alpha - x_{n+1} + {{( \alpha - x_{n})^2 } \over {2}} {{f'' (\xi_{n})} \over { f'(x_{n}) }} $$ 이항해서 정리하면 $$ \begin{equation} \displaystyle \alpha - x_{n+1} = - {{f'' (\xi_{n})} \over { 2 f'(x_{n}) }} ( \alpha - x_{n})^2 \end{equation} $$


Part 2. 수렴성

$f'$ 는 $\alpha$ 근방에서 연속이고 $f'(\alpha) \ne 0$ 이므로 모든 $x \in I_{\delta}$ 에 대해 $f'(x) \ne 0$ 을 만족하는 $ I_{\delta} : = [ \alpha - \delta , \alpha + \delta ]$ 가 존재한다.

$\displaystyle M( \delta ) := {{ \max_{x \in I_{\delta} } | f'' (x) | } \over { 2 \min_{x \in I_{\delta} } | f'(x) | }}$ 이라고 두면 $\delta$ 를 작게 잡을때마다 $\displaystyle \max_{x \in I_{\delta} } | f'' (x) |$ 은 커지지 않고 $\displaystyle \min_{x \in I_{\delta} } | f'(x) |$ 은 작아지지 않으므로 $M ( \delta )$ 전체는 커지지 않는다. 따라서 $M(\delta) | \alpha - x_{0} | < 1$ 이 성립하도록 하는 $x_{0} \in I_{\delta}$ 가 존재하게끔 충분히 작은 $\delta = \delta_{0}$ 를 잡을 수 있다. 바로 이 $x_{0}$ 가 $\alpha$ 와 충분히 가까운 초기값이다.

이 $\delta_{0}$ 에 대해 이제 $M:= M(\delta_{0})$ 라고 하자.

$(1)$ 의 양변에 절대값을 취하면 $$ | \alpha - x_{n+1}| \le M | \alpha - x_{n} |^2 $$ 양변에 $M$ 을 곱하면 $$ M | \alpha - x_{n+1}| \le M^2 | \alpha - x_{n} |^2 $$ 우변을 제곱으로 묶어내면 $$ M | \alpha - x_{n+1}| \le ( M | \alpha - x_{n} | )^2 $$ 이 과정을 $x_{n+1}$ 에서 $x_{0}$ 가 나올때까지 반복하면 $$ M | \alpha - x_{n+1}| \le ( M | \alpha - x_{n} | )^2 \le ( M | \alpha - x_{n-1} | )^4 \le \cdots \le ( M | \alpha - x_{0} | )^{2^{n+1}} $$ 정리하면 $$ \displaystyle | \alpha - x_{n} | \le {{1 } \over {M}} ( M | \alpha - x_{0} | )^{2^{n}} $$ $M | \alpha - x_{0} | < 1$ 이므로 $n \to \infty$ 일 때 $x_{n} \to \alpha$


Part 3. 쿼드러틱하게 수렴

$(1)$ 에 의해 $\displaystyle {{ \alpha - x_{n+1} } \over { ( \alpha - x_{n})^2 }} = - {{f'' (\xi_{n})} \over { 2 f'(x_{n}) }}$ 이고 $x_{n} \to \alpha$ 일 때 $\xi_{n} \to \alpha$ 이므로 $$ \displaystyle \lim_{n \to \infty} {{\alpha - x_{n+1} } \over { ( \alpha - x_{n} )^2 }} = - \lim_{n \to \infty} {{f''( \xi_{n} )} \over { 2 f' ( x_{n} ) }} = -{{f''(\alpha)} \over { 2 f' ( \alpha ) }} $$

설명에서도 수렴성이 항상 보장되지는 않는다고 했는데, 실제로 증명과정에서도 충분히 작은 $I$ 를 잡는다.

구현

20180831\_193141.png

아래는 R로 작성된 코드다. df에 도함수를 넣으면 도함수로 바로 계산을 하고, 생략하면 미분계수를 따로 구해서 쓴다. itmax 옵션은 최대로 반복할 횟수인데, 디폴트로 $1000$ 번을 반복해도 원하는만큼의 정밀한 해가 구해지지 않으면 계산을 포기한다.

d<-function(f,x,tol=10^(-8))
{
  h<-1
  d1<-1
  d2<-0
  
  while(abs(d1-d2)>tol)
  {
    d1<-d2
    d2<-(f(x+h)-f(x))/h
    h<-h/2
  }
  return(d2)
}
 
Newton<-function(f,x0,df=FALSE,itmax=10^3,tol=10^(-8))
{
  if(f(x0)==0){return(x0)}
  denom=0
  
  x1 = x0 - f(x0)/d(f,x0)
  
  for(i in 1:itmax)
  {
    if(is.function(df)){
      denom=df(x1)
    }else{
      denom=d(f,x1)
    }
    if(denom==0){stop('Zero Derivative')}
    
    x2 = x1 - f(x1)/denom
    if(abs(x2-x1)<tol){
      return(x2)
    }else{
      x1 = x2
    }
  }
  
  stop('Maybe Wrong Initial Point')
}
 
f<-function(x) {x^3 + 8}
Newton(f,7)
 
g<-function(x) {x^6 - x - 1}
Newton(g,3)
 
h<-function(x) {exp(x)-1}
Newton(h,-2)

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

댓글