📂수치해석

뉴턴-랩슨 메소드

메소드 ¹

$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$ 차로 수렴한다는 말은 너무 두리뭉술하고 쓰이는 용례가 적어 부득이하게 영어표현을 그대로 썼다. 그럼에도 굳이 언급한 것은 대부분의 경우 바이섹션 메소드에 비해 수렴하는 속도가 빠름을 수학적으로 보일 수 있기 때문이다.

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

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

같이보기

• 고차원에 대해 일반화된 뉴턴-랩슨 메소드
• 뉴턴-푸리에 메소드: $f,f’,f’’$ 가 폐구간 $[a,b]$ 에서 연속이라고 하자. $f$ 가 $[a,b]$ 에서 해를 갖고 증가함수거나 감소함수면 $\displaystyle x_{n+1} = x_{n} - {{ f ( x_{n} ) } \over { f ' ( x_{n} ) }}$ 과 같이 정의된 수열 $\left\{ x_{n} \right\}$ 은 $n \to \infty$ 일 때 $\alpha$ 로 쿼드러틱하게 수렴한다.

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

증명

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

Part 1. 테일러 전개

$f$ 를 $x_{n}$ 에 대해 테일러 전개하면 $x$ 와 $x_{n}$ 사이의 $\xi_{n}$ 에 대해 $$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$ 를 대입하면 $$0 = f(x_{n} ) + ( \alpha - x_{n}) f '(x_{n}) + {{( \alpha - x_{n})^2 } \over {2}} f '' (\xi_{n})$$ 양변을 $f ' (x_{n})$ 으로 나누면 $$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}$ 이므로 $$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}}$$ 정리하면 $$| \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$ 이므로 $$\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$ 를 잡는다.

구현

아래는 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)