뉴턴-랩슨 방법

역사 raw
대문 랜덤 문서 최근 토론
분류

1. 개요2. 상세3. 예시
3.1. [math(sqrt{2})]의 근삿값 구하기3.2. 의 근의 근삿값 구하기
4. 주의할 점5. 기타

1. 개요[편집]

Newton–Raphson method

미분가능한 함수 f:[a,b]→Rf:\left[a, b\right]\to\mathbb{R}에 대해 x에 대한 방정식 f(x)=0f\left(x\right)=0의 근의 근사값을 구하는 알고리즘.

2. 상세[편집]

구간 [a,b]\left[a, b\right]에서 임의로 원소 x0x_0를 택하고 다음과 같은 점화식을 정의한다.
xn=xn−1−f(xn−1)f′(xn−1)\displaystyle x_{n}=x_{n-1}-\frac{f\left ( x_{n-1} \right )}{f'\left ( x_{n-1} \right )}
그러면 특정 조건 하에서는 극한값 lim⁡n→∞xn\displaystyle \lim_{n\to\infty}x_n이 존재하고 그 극한값이 방정식의 근이 된다.

3. 예시[편집]

3.1. [math(sqrt{2})]의 근삿값 구하기[편집]

2\sqrt{2}는 방정식 x2−2=0{x}^{2}-2=0의 한 근이다. f(x)=x2−2f\left ( x \right )=x^{2}-2로 놓으면 f′(x)=2xf'\left(x\right)=2x이므로 점화식은 다음과 같다.
xn=xn−1−xn−12−22xn−1\displaystyle x_{n}=x_{n-1}-\frac{{x_{n-1}}^{2}-2}{2x_{n-1}}
x0=2x_0=2라고 하면 다음과 같이 계산된다. 볼드체는 실제 값과 일치하는 자릿수.
n
xnx_n
∣xn2−2∣\left | {x_n}^{2}-2 \right |
0
2
2
1
1.5
0.25
2
1.41666666666667
0.006944444444445
3
1.41421568627451
6.00730488287127×10−66.00730488287127\times{10}^{-6}
4
1.41421356237469
4.51061410444709×10−124.51061410444709\times{10}^{-12}
근에 빠른 속도로 수렴하는 것을 볼 수 있다.

3.2. ex−5x−13=0e^{x}-5x-13=0의 근의 근삿값 구하기[편집]


{f(x)=ex−5x−13f′(x)=ex−5\begin{cases}f\left ( x \right )=e^{x}-5x-13 \\ f'\left ( x \right )= e^{x}-5\end{cases}로 놓자.
그러면 점화식은 다음과 같다.
xn=xn−1−exn−1−5xn−1−13exn−1−5\displaystyle x_{n}=x_{n-1}-\frac{e^{x_{n-1}}-5x_{n-1}-13}{e^{x_{n-1}}-5}
x0=2.5x_0=2.5라 하면
n
xnx_n
∣ex−5x−13∣\left|e^{x}-5x-13\right|
0
2.5
13.3175
1
4.354161815124195798851178994132
43.03077
2
3.763092592016330437643144443986
11.26599
3
3.467253291595249561814786479631
1.712326
4
3.403947713273494508244070291062
0.062884
5
3.401440601093522986200834613223
0.000094
6
3.401436823600939240742703523282
2.140935×10^-10
7
3.401436823592377958986325308771
1.099696×10^-21
8
3.401436823592377958986281333550
2.901424×10^-44

참고로 정확한 값은
x=−15(Wz(−15e135+13)),z∈Zx=-\dfrac{1}{5}\left(W_ z(-\frac{1}{5e^{\frac{13}{5}}+13})\right),z \in \mathbb{Z}이고 WzW_z에 대해서는 람베르트 W함수에 대해 참고

4. 주의할 점[편집]

  • 초기값을 설정하는데 공을 들일 필요가 있다. 영 좋지 않은 초기값을 선택하면 근을 찾는데 많은 시간이 소모될 수 있음은 물론, 값이 수렴하지 않고 발산하는 경우도 생길 수 있다. 통계학에서 추정에 활용될 때는 주로 적률이용추정량(Method of Moment Estimator)이 초기값으로 선택된다.
  • (초기값을 정확한 해로 정한 것이 아니라면) 아무리 반복해도 그 해에 무한히 수렴하는 근사값이 구해질뿐 정확한 값이 나오진 않는다. 때문에 유효숫자를 정해두고 거기까지만 계산하여 더 이상 변화가 없을 때 끊는 방식으로 주로 사용한다.

5. 기타[편집]

  • 서양에서 제곱근 값을 구할때 쓰였던 바빌로니아 법, 헤론의 방법 등은 이 뉴턴-랩슨 방법의 특수한 형태이다. 제곱근 문서 참고.