/ TECHNOLOGY

(알고리즘) 뉴턴의 방법

golang 튜토리얼 보다가 예제로 나온 것 오랜만에 수학 공부한게 재미있기도 하고 나중에 시험 문제도 한번 내 봐야지 싶어서 정리

enter image description here

뉴턴의 방법

수열의 점화식을 이용해서 다양한 무리수의 근삿값을 구하는데 활용된다. 프로그래밍에도 사용되는데, 컴퓨터가 사칙연산만 가능하므로, 이에 사용할 수 있다. 간단히 실험해보니 3제곱근도 척척 잘된다. ^^ 여기서 구하고자 하는 것은 sqrt(2)이다.

원리는 1/2차 방적식과 미분 공부 잘했으면 간단히 이해 될 것이고, 아니면 조금 어렵다? ㅋㅋㅋㅋ

일단, 위 그림의 x0 지점에서 미분하면, 1차 함수가 생길 것이다. 미분을 했기에 기울기는 나왔고, (x0, f(x0))이라는 좌표를 알기에 1차 함수는 다음과 다음과 같이 된다.

y = f`(x0) * ( x - x0 ) + f(x0)  
where, y와x가 함수의 입출력 값

고등 때 다행히 똑바로 공부해서 바로 기억났음 ㅎㅎㅎ 여기서 y = 0이라고 하면,

0 = f`(x0) * ( x1 - x0 ) + f(x0)
치환하면, 
x1 = x0 - f(x0) / f`(x0)

이것을 반복하다보면, 위 그림에서 근수라 할 수 있는 y = 0 인 지점, a값의 가장 가까운 근삿값을 구할 수 있다.

제곱근 구하기

사실 위 얘기는 이해가 나름 쉽게 되는데 이거와 제곱근과의 관계가 머인지 당황 스러울 것이다. 제곱근2를 생각 해보자. 근수값을 모른다고 하면,

근수값^2 = 2
즉, 
x^2 = 2

이다. 이걸 함수로 다음과 같이 표현 할 수 있다.

x^2 -2 = 0 
즉, y = 0 인 함수가 되고 미분 하면은 2x

여기에 위 공식을 쓰려면 초기 값을 넣어야 하는데 보통은 1을 넣고 반복하다 보면, 근수에 수렴하는 근사값을 구할 수 있다. 보통 4번 정도면 찾아가는 것으로 보인다.

x1 = 1 - (-1) / 1 = 2
x2 = 2 - 2 / 4 = 1.5
x3 = 1.5 - (1.5^2 - 2) / 3 = 1.417
x4 = 1.417 - (1.417^2 - 2) / (2*1.417) = 1.4142

4번의 반복으로 근삿값이 근수와 동일해졌다.

golang으로 표현

func Sqrt(x float64) float64 {
    z := 1.0 // 시작값으로 float형식으로 표현
	for i :=0 ; i< 5 ; i++ {
		z = z - (z * z - x) / (2 * z)
	}
}

func main() {
    fmt.Println(Sqrt(4))
}

3제곱근을 구하려면?

제곱근의 함수는,

x^2 = 2 (2의 제곱근의 경우) 
y = 0 = x^2 - 2
미분은 y` = 2x

이므로, 3제곱근을 구하려면,

x^3 = 2 (2의 3제곱근의 경우)
즉,
y = 0 = x^3 - 2
미분은 y` = 3x^2

이다. 잘된다!!! ㅎㅎ

참고

http://blog.naver.com/dydrogud22/110190167873 http://blog.naver.com/leebs/40186733049 http://go-tour-kr.appspot.com/#23