뉴턴 방법

함수 f는 파란 선, 각 접선은 빨간 선이다. 접선의 영점을 반복적으로 취해 나갈 때, x_n과 실제 영점의 오차가 점차 줄어듦을 확인할 수 있다.

수치해석학에서 뉴턴 방법(틀:Llang)은 실숫값 함수의 영점을 근사하는 방법의 하나이다. 뉴턴-랍슨 방법(틀:Llang)이라고도 불린다.

정의

연속 미분 가능 함수 $f:[a,b]\to ℝ$가 영점 $\hat{x}\in (a,b)$를 갖는다고 하자. 또한, $f^{\prime }(\hat{x})\ne 0$라고 하자. 그렇다면, 다음을 만족시키는 열린집합 $\hat{x}\in U\subseteq (a,b)$가 존재한다.

• 임의의 $x_0\in U$에 대하여, 수열 $x_{n+1}=x_n-f(x_n)/f^{\prime }(x_n)$ ($n\in \{0,1,2,\dots \}$)은 $\hat{x}$로 수렴한다.

이를 통해 영점 $\hat{x}$를 근사하는 방법을 뉴턴 방법이라고 한다. 반복 계산을 정지하기 위한 정지조건은 할선법에서 사용된 것 중 하나가 쓰인다.틀:Sfn 뉴턴 방법은 매우 효과적인 방법이지만 초기 가정치 $x_0$를 근에 충분히 가깝게 하지 않으면 수렴하지 않는다는 단점이 있다. 또한 접선이 거의 수평인 즉 $f^{\prime }(x_0)\approx 0$인 $x_0$를 선택해선 안 된다.틀:Sfn

성질

오차

만약 $f$가 2번 연속 미분 가능 함수라면, 점렬의 항과 영점 사이의 오차에 대하여 다음을 만족시키는 상수 $c$가 존재한다.

$|x_{n+1}-\hat{x}|\le c|x_n-\hat{x}{|}^2$

점렬의 단조성

만약 $f$가 2번 연속 미분 가능 함수라면,

• 만약 임의의 $x\in U$에 대하여 $f^{\prime }(x)f^{″}(x)<0$라면, $(x_n{)}_{n=0}^{\mathrm{\infty }}$은 증가 수열이다.
• 만약 임의의 $x\in U$에 대하여 $f^{\prime }(x)f^{″}(x)>0$라면, $(x_n{)}_{n=0}^{\mathrm{\infty }}$은 감소 수열이다.

예제

루트값 구하기

틀:Math를 만족하는 양수 틀:Math를 구해서 결국 틀:Mvar의 루트값을 구해보자. 뉴튼방법은 루트값을 구하는 여러 가지 계산법 중에 하나이다. 루트를 구하는 이 문제를 다음과 같이 함수 틀:Math의 해를 구하는 문제로 생각할 수 있다. 1차 미분은 틀:Math로 주어진다.

612의 루트값을 계산하는 경우를 다뤄보자. 초기값을 틀:Math로 하고, 뉴튼법을 적용하면 다음과 같다:

$\begin{array}{ccccccc}{x}_1& =& x_0-\frac{f(x_0)}{f^{\prime }(x_0)}& =& 10-\frac{10^2-612}{2\times 10}& =& 35.6\\ x_2& =& x_1-\frac{f(x_1)}{f^{\prime }(x_1)}& =& 35.6-\frac{35.6^2-612}{2\times 35.6}& =& \underset{\_}{2}6.395505617978\dots \\ x_3& =& ⋮& =& ⋮& =& \underset{\_}{24.7}90635492455\dots \\ x_4& =& ⋮& =& ⋮& =& \underset{\_}{24.7386}88294075\dots \\ x_5& =& ⋮& =& ⋮& =& \underset{\_}{24.7386337537}67\dots \end{array}$

여기서 참값과 같은 부분의 숫자는 밑줄이 그어져있다. 많지 않은 몇번의 반복을 통해 매우 정확한 루트값이 계산되는 것을 볼 수 있다.

위의 반복 수식을 아래와 같이 재배열하면 루트를 구하는 바빌로니안 방법을 얻는다:

$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}=x_n-\frac{x_n^2-a}{2x_n}=\frac{1}{2}(2x_n-(x_n-\frac{a}{x_n}\left)\right)=\frac{1}{2}(x_n+\frac{a}{x_n})$

즉, 루트를 구하는 뉴튼법은 결국 현재 추측한 루트값의 틀:Math 과 틀:Math의 산술_평균을 반복적으로 적용한 것이다.

틀:Math의 해 구하기

틀:Math을 만족하는 틀:Math를 구하는 문제를 생각해보자. 이 문제는 틀:Math이 0이 되는 해를 찾는 문제로 바뀔 수 있다. 1차 미분은 틀:Math로 주어진다. 모든 틀:Math에 대해 틀:Math 이고 틀:Math에 대해 틀:Math이므로, 이 함수가 0이되는 구간은 0과 1사이라는 것을 알 수 있다.

초기 추정해를 틀:Math라 하고 뉴튼방법을 적용하면 (초기값을 0으로 선택하면 미분값이 0이 되고, 0으로 나누기 연산을 해서 계산이 실패한다. 즉, 무한대값이 발생한다. 뉴튼방법에서 초기값 선택은 해로 수렴하는데 큰 영향을 미친다) 아래와 같은 결과를 얻는다:

$\begin{array}{ccccccc}{x}_1& =& x_0-\frac{f(x_0)}{f^{\prime }(x_0)}& =& 0.5-\frac{\cos 0.5-0.5^3}{-\sin 0.5-3\times 0.5^2}& =& 1.112141637097\dots \\ x_2& =& x_1-\frac{f(x_1)}{f^{\prime }(x_1)}& =& ⋮& =& \underset{\_}{0.}909672693736\dots \\ x_3& =& ⋮& =& ⋮& =& \underset{\_}{0.86}7263818209\dots \\ x_4& =& ⋮& =& ⋮& =& \underset{\_}{0.86547}7135298\dots \\ x_5& =& ⋮& =& ⋮& =& \underset{\_}{0.8654740331}11\dots \\ x_6& =& ⋮& =& ⋮& =& \underset{\_}{0.865474033102}\dots \end{array}$

여기서 참값과 같은 부분의 숫자는 밑줄이 그어져있다. 구해진 틀:Math값은 소숫점아래 12자리까지 참값과 같다. 위의 계산예에서 2자리까지 참값과 일치하는 틀:Math가 이어지는 계산에서 5자리, 10자리로 일치하는 이차수렴(quadratic convergence)속도를 보이는 것을 알 수 있다.

프로그램

아래 프로그램은 뉴튼방법을 쥴리아 언어로 구현한 것으로 미분값 fprime을 갖는 함수 f의 근을 구한다.

근의 초기값은 틀:Math으로 설정되었고 함수는 틀:Math 미분은 틀:Math이다.

뉴튼 방법이 매번 반복될 때마다 갱신되는 값은 x1이다. 반복 계산할 때마다 분수의 나눠지는 분모부분이 (yprime) 너무 작아지지 않는지 (epsilon보다 더 작아지지 않는지) 확인한다. 즉, 틀:Math이 발생하면 큰 수치오차가 발생한다.

x0            = 1         # The initial guess
f(x)          = x^2 - 2   # The function whose root we are trying to find
fprime(x)     = 2x        # The derivative of the function
tolerance     = 1e-7      # 7 digit accuracy is desired
epsilon       = 1e-14     # Do not divide by a number smaller than this
maxIterations = 20        # Do not allow the iterations to continue indefinitely
solutionFound = false     # Have not converged to a solution yet

for i = 1:maxIterations
  y      = f(x0)
  yprime = fprime(x0)

  if abs(yprime) < epsilon            # Stop if the denominator is too small
    break
  end

  global x1 = x0 - y/yprime           # Do Newton's computation

  if abs(x1 - x0) <= tolerance        # Stop when the result is within the desired tolerance
    global solutionFound = true
    break
  end

  global x0 = x1                      # Update x0 to start the process again
end

if solutionFound
  println("Solution: ", x1)           # x1 is a solution within tolerance and maximum number of iterations
else
  println("Did not converge")         # Newton's method did not converge
end

같이 보기

• 이분법 (수학)
• 할선법

참고 문헌

• 틀:서적 인용