반응형
def isqrt(n):
x = n
y = (x+1)/2
while y < x:
x = y
y = (x+n/x)/2
return x
루트 n 을 구하는 뉴튼의 방법인데. 어떻게 구해지는 건가?
---
f(x) = x, g(x) = n/x 두 그래프는 (sqrt(n), sqrt(n)) 에서 교차한다. 하나는 단조증가, 하나는 단조감소함수이다.
위 코드에서는
x_(k+1) = ( f(x_k) + g(x_k) )/2
점화식으로 x_k 수열을 만들어 나간다.
그래프에서는 삼각주 모양을 점점 줄여 나가면서 교차점에 다다르게 되는 형상이다.
f(x), g(x) 가 (sqrt(n), sqrt(n)) 에서 교차하는 단조증가/감수 함수이기만 하면 되나?
위 파란색 부분 뻘생각이니까 혹시 검색을 통해 들어오신 분들은 크게 신경쓰지 마시길. 더 정확한 정의 등은 위키백과등을 참고하세요.
---
원래는 F(x) = x^2 - n = 0 을 구하기 위해, 시작점 (x_0, F(x_0))에서의 접선을 구하고, 다시 접선이 x축과 만나는 x_1을 구하고, 하는 작업을 반복하는 것. 접선의 식이 y = F'(x_0) x - F'(x_0) x_0 + F(x_0) 이므로, y 를 0으로 하는 x_1 은 x_1 = x_0 - F(x_0)/F'(x_0) 가 된다.
728x90