뉴턴 방법 문서 원본 보기

[[파일:NewtonIteration Ani.gif|섬네일|300px|오른쪽|함수 f는 파란 선, 각 접선은 빨간 선이다. 접선의 영점을 반복적으로 취해 나갈 때, x<sub>n</sub>과 실제 영점의 오차가 점차 줄어듦을 확인할 수 있다.]]

[[수치해석학]]에서 '''뉴턴 방법'''({{llang|en|Newton's method}})은 실숫값 [[함수]]의 [[영점]]을 근사하는 방법의 하나이다.
'''뉴턴-랍슨 방법'''({{llang|en|Newton–Raphson method}})이라고도 불린다.

== 정의 ==
[[연속 미분 가능 함수]] <math>f\colon[a,b]\to\mathbb R</math>가 영점 <math>\hat x\in(a,b)</math>를 갖는다고 하자. 또한, <math>f'(\hat x)\ne 0</math>라고 하자. 그렇다면, 다음을 만족시키는 열린집합 <math>\hat x\in U\subseteq(a,b)</math>가 존재한다.
* 임의의 <math>x_0\in U</math>에 대하여, 수열 <math>x_{n+1}=x_n-f(x_n)/f'(x_n)</math> (<math>n\in\{0,1,2,\dots\}</math>)은 <math>\hat x</math>로 수렴한다.
이를 통해 영점 <math>\hat x</math>를 근사하는 방법을 '''뉴턴 방법'''이라고 한다. 반복 계산을 정지하기 위한 정지조건은 [[할선법]]에서 사용된 것 중 하나가 쓰인다.{{Sfn|Abdelwahab Kharab|Ronald B. Guenther|p=65-66|2013}} 뉴턴 방법은 매우 효과적인 방법이지만 초기 가정치 <math>x_0</math>를 근에 충분히 가깝게 하지 않으면 수렴하지 않는다는 단점이 있다. 또한 접선이 거의 수평인 즉 <math>f'(x_0)\approx 0</math>인 <math>x_0</math>를 선택해선 안 된다.{{Sfn|Abdelwahab Kharab|Ronald B. Guenther|p=67-68|2013}}

== 성질 ==
=== 오차 ===
만약 <math>f</math>가 2번 연속 미분 가능 함수라면, 점렬의 항과 영점 사이의 오차에 대하여 다음을 만족시키는 상수 <math>c</math>가 존재한다.
:<math>|x_{n+1}-\hat x|\le c|x_n-\hat x|^2</math>

=== 점렬의 단조성 ===
만약 <math>f</math>가 2번 연속 미분 가능 함수라면,
* 만약 임의의 <math>x\in U</math>에 대하여 <math>f'(x)f''(x)<0</math>라면, <math>(x_n)_{n=0}^\infty</math>은 증가 수열이다.
* 만약 임의의 <math>x\in U</math>에 대하여 <math>f'(x)f''(x)>0</math>라면, <math>(x_n)_{n=0}^\infty</math>은 감소 수열이다.

==예제==
===루트값 구하기===
{{math|1=''x''<sup>2</sup> = ''a''}}를 만족하는 양수 {{math|''x''}}를 구해서 결국 {{mvar|a}}의 루트값을 구해보자. 뉴튼방법은 루트값을 구하는 여러 가지 계산법 중에 하나이다. 루트를 구하는 이 문제를 다음과 같이 함수 {{math|1=''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'') = ''x''<sup>2</sup> − ''a''}}의 해를 구하는 문제로 생각할 수 있다. 1차 미분은 {{math|1=''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'') = 2''x''}}로 주어진다.

612의 루트값을 계산하는 경우를 다뤄보자. 초기값을 {{math|1=''x''<sub>0</sub> = 10}}로 하고, 뉴튼법을 적용하면 다음과 같다:

:<math>\begin{matrix}
 x_1 & = & x_0 - \dfrac{f(x_0)}{f'(x_0)} & = & 10 - \dfrac{10^2 - 612}{2 \times 10} & = & 35.6\qquad\qquad\qquad\quad\;\,{} \\
 x_2 & = & x_1 - \dfrac{f(x_1)}{f'(x_1)} & = & 35.6 - \dfrac{35.6^2 - 612}{2 \times 35.6} & = & \underline{2}6.395\,505\,617\,978\dots \\
 x_3 & = & \vdots & = & \vdots & = & \underline{24.7}90\,635\,492\,455\dots \\
 x_4 & = & \vdots & = & \vdots & = & \underline{24.738\,6}88\,294\,075\dots \\
 x_5 & = & \vdots & = & \vdots & = & \underline{24.738\,633\,753\,7}67\dots
\end{matrix}
</math>

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

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

:<math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^2 - a}{2 x_n} = \frac{1}{2}\biggl(2x_n - \Bigl(x_n - \frac{a}{x_n}\Bigr)\biggr) = \frac{1}{2}\Bigl(x_n + \frac{a}{x_n}\Bigr)</math>

즉, 루트를 구하는 뉴튼법은 결국 현재 추측한 루트값의 {{math|''x<sub>n</sub>''}} 과 {{math|{{sfrac|''a''|''x''<sub>''n''</sub>}}}}의 [[산술_평균]]을 반복적으로 적용한 것이다.

==={{math|1=cos(''x'') = ''x''<sup>3</sup>}}의 해 구하기===
{{math|1=cos(''x'') = ''x''<sup>3</sup>}}을 만족하는 {{math|''x''}}를 구하는 문제를 생각해보자. 이 문제는 {{math|1=''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'') = cos(''x'') − ''x''<sup>3</sup>}}이 0이 되는 해를 찾는 문제로 바뀔 수 있다. 1차 미분은 {{math|1=''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'') = −sin(''x'') − 3''x''<sup>2</sup>}}로 주어진다. 모든 {{math|''x''}}에 대해 {{math|cos(''x'') ≤ 1}} 이고 {{math|''x'' > 1}}에 대해 {{math|''x''<sup>3</sup> > 1}}이므로, 이 함수가 0이되는 구간은 0과 1사이라는 것을 알 수 있다.

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

:<math>\begin{matrix}
 x_1 & = & x_0 - \dfrac{f(x_0)}{f'(x_0)} & = & 0.5 - \dfrac{\cos 0.5 - 0.5^3}{-\sin 0.5 - 3 \times 0.5^2} & = & 1.112\,141\,637\,097\dots \\
 x_2 & = & x_1 - \dfrac{f(x_1)}{f'(x_1)} & = & \vdots & = & \underline{0.}909\,672\,693\,736\dots \\
 x_3 & = & \vdots & = & \vdots & = & \underline{0.86}7\,263\,818\,209\dots \\
 x_4 & = & \vdots & = & \vdots & = & \underline{0.865\,47}7\,135\,298\dots \\
 x_5 & = & \vdots & = & \vdots & = & \underline{0.865\,474\,033\,1}11\dots \\
 x_6 & = & \vdots & = & \vdots & = & \underline{0.865\,474\,033\,102}\dots
\end{matrix}
</math>

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

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

근의 초기값은 {{math|1=''x''<sub>0</sub> = 1}}으로 설정되었고 함수는 {{math|1=''<span style{{=}}"letter-spacing:0.2em">f</span>''(''x'') = ''x''<sup>2</sup> − 2}} 미분은 {{math|1=''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x'') = 2''x''}}이다.

뉴튼 방법이 매번 반복될 때마다 갱신되는 값은 <code>x1</code>이다. 반복 계산할 때마다 분수의 나눠지는 분모부분이 (<code>yprime</code>) 너무 작아지지 않는지 (<code>epsilon</code>보다 더 작아지지 않는지) 확인한다. 즉, {{math|''<span style{{=}}"letter-spacing:0.15em">f</span>′''(''x''<sub>''n''</sub>) ≈ 0}}이 발생하면 큰 수치오차가 발생한다.

<syntaxhighlight lang="julia">
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
</syntaxhighlight>

== 같이 보기 ==
* [[이분법 (수학)]]
* [[할선법]]

== 각주 ==
{{각주}}

== 참고 문헌 ==
* {{서적 인용|저자1=Abdelwahab Kharab|저자2=Ronald B. Guenther|제목=An Introduction to Numerical Methods A MATLAB Approach|번역제목=이공학도를 위한 수치해석|날짜=2013|출판사=학산미디어|isbn=978-89-966211-8-8 |ref=harv}}

{{위키공용분류}}
{{전거 통제}}
{{위키데이터 속성 추적}}

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