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(x_n-\sqrt2)]) |
0 | 2 | 0.5857864 |
1 | 1.5 | 0.0857864 |
2 | 1.41666666666667 | 0.0024531 |
3 | 1.41421568627451 | 2.123901 × 10-6 |
4 | 1.41421356237469 | 1.59495 × 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)이 초깃값으로 선택된다.
- (초깃값을 정확한 해로 정한 것이 아니라면) 아무리 반복해도 그 해에 무한히 수렴하는 근삿값이 구해질 뿐 정확한 값이 나오진 않는다. 때문에 유효숫자를 정해두고 거기까지만 계산하여 더 이상 변화가 없을 때 끊는 방식으로 주로 사용한다.