1. 개요
Newton–Raphson method미분가능한 함수 [math(f\colon\left[a, b\right]\to\mathbb{R})]에 대해 [math(x)]에 대한 방정식 [math(f{\left(x\right)}=0)]의 근의 근삿값을 구하는 알고리즘.
2. 상세
구간 [math(\left[a, b\right])]에서 임의로 원소 [math(x_0)]를 택하고 다음과 같은 점화식을 정의한다.| [math(\displaystyle x_{n}=x_{n-1}-\frac{f\left ( x_{n-1} \right )}{f'\left ( x_{n-1} \right )})] |
3. 예시
3.1. 방정식 해의 근삿값 구하기
예제는 [math(sqrt{2})]이다.[math(\sqrt{2})]는 방정식 [math({x}^{2}-2=0)]의 한 근이다. [math(f\left ( x \right )=x^{2}-2)]로 놓으면 [math(f'\left(x\right)=2x)]이므로 점화식은 다음과 같다.
| [math(\displaystyle x_{n}=x_{n-1}-\frac{{x_{n-1}}^{2}-2}{2x_{n-1}})] |
| n | [math(x_n)] | [math(\left | {x_n}^{2}-2 \right |)] |
| 0 | 2 | 2 |
| 1 | 1.5 | 0.25 |
| 2 | 1.41666666666667 | 0.006944444444445 |
| 3 | 1.41421568627451 | [math(6.00730488287127\times{10}^{-6})] |
| 4 | 1.41421356237469 | [math(4.51061410444709\times{10}^{-12})] |
근에 빠른 속도로 수렴하는 것을 볼 수 있다.
3.2. 지수함수 해의 근삿값 구하기
예제 식은 [math(e^{x}-5x-13=0)]이다.[math(\begin{cases}f\left ( x \right )=e^{x}-5x-13 \\ f'\left ( x \right )= e^{x}-5\end{cases})]로 놓자.
그러면 점화식은 다음과 같다.
[math(\displaystyle x_{n}=x_{n-1}-\frac{e^{x_{n-1}}-5x_{n-1}-13}{e^{x_{n-1}}-5})]
[math(x_0=2.5)]라 하면| n | [math(x_n)] | [math(\left|{e}^{{x}_{n}}-5{x}_{n}-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\times10^{-10}</math> |
| 7 | 3.401436823592377958986325308771 | 1.099696\times10^{-21}</math> |
| 8 | 3.401436823592377958986281333550 | 2.901424\times10^{-44}</math> |
참고로 정확한 값은
[math(x=-\dfrac{1}{5}\left(W_ z(-\frac{1}{5e^{\frac{13}{5}}+13})\right),z \in \mathbb{Z})]이고 [math(W_z)]에 대해서는 람베르트 W 함수에 대해 참고
4. 주의할 점
- 초깃값을 설정하는데 공을 들일 필요가 있다. 영 좋지 않은 초깃값을 선택하면 근을 찾는 데 많은 시간이 소모될 수 있음은 물론, 값이 수렴하지 않고 발산하는 경우도 생길 수 있다. 통계학에서 추정에 활용될 때는 주로 적률이용추정량(Method of Moment Estimator)이 초깃값으로 선택된다.
- (초깃값을 정확한 해로 정한 것이 아니라면) 아무리 반복해도 그 해에 무한히 수렴하는 근삿값이 구해질 뿐 정확한 값이 나오진 않는다. 때문에 유효숫자를 정해두고 거기까지만 계산하여 더 이상 변화가 없을 때 끊는 방식으로 주로 사용한다.