파이썬에서 뉴턴 랩슨 방법

근사값을 구할 때 가장 보편적으로 사용하는 알고리즘은 아이작  뉴턴이 고안한 것이다.

한 개의 변수를 가진 다항식은 0이거나 0이 아닌 항들의 합이다. 각 항은 상수와 음수가 아닌 값만큼 거듭제곱된 변수의 곱으로 이루어져 있다. 예를 들어 3X^2 + 2X +3이라는 다항식에서 첫 번째 항 3x^2는 상수 3과 제곱된 변수 x의 곱이다.

만약 다항식 p와 실수 r이 있다면 x=r일 때 다항식의 값을 P(r)이라고 할 것이다. 방정식 p=0의 해는 p의 근이다. 즉 P(r)=0이 될 때의 r인 것이다. 그러므로 예를 들어 24의 제곱근의 근사값을 찾는 문제가 주어졌을 때는 x^2 - 24 = 0에서 x의 값을 찾으면 된다.

뉴턴은 어떤 값 guess가 다항식의 근의 근사값일 때 p'가 p의 1차 도함수라고 한다면 guess - P(guess)/P'(guess)가 더 나은 근사값이 된다는 원리를 증명하였다. 어떤 상수 k와 계수 c가 있을 때 cx^2 + k의 1차 도함수는 2cx이다. 또 x^2 - k의 1차 도함수는 2x이다. 그러므로 현재의 추측 값에서 다시한번 y - (y^2 - k)/2y를 구하여 더 나은 근사값을 구할 수 있음을 알 수 있다. 이것을 연속 근사법(successive approximation)이라고 한다.

다음 코드는 이런 방법으로 제곱근의 근사값을 좀 더 빠르게 구하는 것을 구현한 코드이다. 

epsilon = 0.01
k = 24.0
i = 0
guess = k/2.0
while abs(guess*guess - k) >= epsilon:
    i = i + 1
    guess = guess - (((guess**2) - k)/(2*guess))
print('Square root of', k, 'is about', guess)
print('반복회수 : ', str(i))

 

출력결과

Square root of 24.0 is about 4.8989887432139305
반복회수 :  4