Newton's Method

1.1.7 연습 : Newton's method 가 나옵니다.

위키피디아가 최고!!

Newton's method 는 어떤 함수 f(x) 가 있을 때 f(x) = 0 이 되는 값을 approximation 하는 방법입니다.

즉, 방정식의 근을 근사로 구하는 방법이죠. 링크가 깨지지 않는 이상 이 그림 하나면 해결이 됩니다.

결론은 Xn+1 = Xn - f(Xn) / f'(Xn) 이라는 것이고, 이 책에서는 제곱근을 구하는데 사용합니다.

책에 설명되어 있는 알고리즘은 "x의 제곱근에 가까운 값 y가 있을 때, y 와 x / y 의 평균을 구하면 진짜 제곱근에 더 가까운 값을 구할 수 있다" 이것인데 이해가 잘 안됩니다.

여기서

sqrt(b) = a -> a^2 = b (b의 제곱근은 a) 라고 했을 때, 

a^2 - b = 0 즉, 이차 방정식의 근을 구하는 문제가 됩니다. b는 주어지기 때문에 a를 구하는 것입니다.

여기서 위에서 사용한 Newton's Iteration 을 적용해보면,

new a = a - (a^2 - b) / (2a)

식을 정리하면

new a = (a + b / a) / 2

예제에는 2의 제곱근을 구한다고 했으므로

new a = (a + 2 / a) / 2

이미 이곳에서 처음에 사용한 알고리즘이 설명이 됩니다.

"x의 제곱근에 가까운 값 y가 있을 때, y 와 x / y 의 평균을 구하면 진짜 제곱근에 더 가까운 값을 구할 수 있다"

x = 2, y = a 라고 대입하면 되지요.

한번 대입해 볼까요?

처음에 가까운 값을 1이라고 했으므로

new a = (1 + 2) / 2 = 1.5

new a = (1.5 + 2 / 1.5) / 2 = 1.4167..

...

...

..

끝.