뉴턴 방법

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

 정의 
연속 미분 가능 함수 가 영점 를 갖는다고 하자. 또한, 라고 하자. 그렇다면, 다음을 만족시키는 열린집합 가 존재한다.
 임의의 에 대하여, 수열  ()은 로 수렴한다.
이를 통해 영점 를 근사하는 방법을 뉴턴 방법이라고 한다. 반복 계산을 정지하기 위한 정지조건은 할선법에서 사용된 것 중 하나가 쓰인다. 뉴턴 방법은 매우 효과적인 방법이지만 초기 가정치 를 근에 충분히 가깝게 하지 않으면 수렴하지 않는다는 단점이 있다. 또한 접선이 거의 수평인 즉 인 를 선택해선 안 된다.

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

 점렬의 단조성 
만약 가 2번 연속 미분 가능 함수라면,
 만약 임의의 에 대하여 라면, 은 증가 수열이다.
 만약 임의의 에 대하여 라면, 은 감소 수열이다.

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

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

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

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

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

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

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

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

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

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

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

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

 같이 보기 
 이분법 (수학)
 할선법

 각주 

 참고 문헌 


분류:수치해석학
분류:근 찾기 알고리즘
분류:최적화 알고리즘