Newton–Raphson method
1 개요
미분가능한 함수 [math]f:\left[a, b\right]\to\mathbb{R}[/math]에 대해 x에 대한 방정식 [math]f\left(x\right)=0[/math]의 근을 구하는 알고리듬
구간 [math]\left[a, b\right][/math]에서 임의로 원소 [math]x_0[/math]를 택하고 다음과 같은 점화식을 정의한다.
- [math]\displaystyle x_{n}=x_{n-1}-\frac{f\left ( x_{n-1} \right )}{f'\left ( x_{n-1} \right )}[/math]
그러면 특정 조건 하에서는 극한값 [math]\displaystyle \lim_{n\to\infty}x_n[/math]이 존재하고 그 극한값이 방정식의 근이 된다.
2 예시
1. [math]\sqrt{2}[/math]의 근삿값 구하기
[math]\sqrt{2}[/math]는 방정식 [math]{x}^{2}-2=0[/math]의 한 근이다. [math]f\left ( x \right )=x^{2}-2[/math]로 놓으면 [math]f'\left(x\right)=2x[/math]이므로 점화식은 다음과 같다.
- [math]\displaystyle x_{n}=x_{n-1}-\frac{{x_{n-1}}^{2}-2}{2x_{n-1}}[/math]
[math]x_0=2[/math]라고 하면 다음과 같이 계산된다.
| n | [math]x_n[/math] | [math]{x_n}^2-2[/math] |
| 0 | 2 | 2 |
| 1 | 1.5 | 0.25 |
| 2 | 1.41666666666667 | 0.0069444444 |
| 3 | 1.41421568627451 | 6.00730488287127E-06 |
| 4 | 1.41421356237469 | 4.51061410444709E-12 |
- 근에 빠른 속도로 수렴하는 것을 볼 수 있다.
2. [math]e^{x}-5x-13=0[/math]의 근의 근삿값 구하기
[math]\begin{cases}f\left ( x \right )=e^{x}-5x-13 \\ f'\left ( x \right )= e^{x}-5\end{cases}[/math]로 놓자.
그러면 점화식은 다음과 같다.
- [math]\displaystyle x_{n}=x_{n-1}-\frac{e^{x_{n-1}}-5x_{n-1}-13}{e^{x_{n-1}}-5}[/math]
[math]x_0=2.5[/math]라 하면
| n | [math]x_n[/math] | [math]\left|e^{x}-5x-13\right|[/math] |
| 0 | 2.5 | 13.3175 |
| 1 | 4.3541618151241957988511789941322 | 43.030776811062596188056120322497020 |
| 2 | 3.7630925920163304376431444439869738 | 11.265990571927481514206244917402415032 |
| 3 | 3.4672532915952495618147864796317871818 | 1.712326841620949317395497471413015541809 |
| 4 | 3.40394771327349450824407029106235922737880 | 0.0628849509258462182263701163275309881038890 |
| 5 | 3.401440601093522986200834613223549883787152058 | 0.00009446488073375744283276244278720823295292082 |
| 6 | 3.4014368236009392407427035232821017243471934192803 | 2.14093549169697551824648081631141180381787×10^-10 |
| 7 | 3.40143682359237795898632530877173633488429622077225499 | 1.0996964616094947860323883001994399×10^-21 |
| 8 | 3.401436823592377958986281333550199112038679107111090952638 | 2.901424803461507×10^-44 |
3 주의할 점
- 초기값을 설정하는데 공을 들일 필요가 있다. 영 좋지 않은 초기값을 선택하면 근을 찾는데 많은 시간이 소모될 수 있음은 물론, 값이 수렴하지 않고 발산하는 경우도 생길 수 있다.