[알고리즘]뉴턴법 : 수치 계산

뉴턴 - 랩슨법(Newton-Raphson Method)

주어진 함수의 근을 찾기 위한 반복적인 수치 방법 중 하나.

뉴턴법은 함수의 접선을 반복해서 그어, 어떠한 수치의 근삿값을 계한하는 알고리즘이다.

예를 들어서 $\sqrt{2}$의 근삿값을 구하려고 할 때

1. 초깃값 a를 정하고, 함수 $y=x^2$과 $y=2$을 그린다.

2. 아래의 과정을 반복

-1) $y=x^2$의 점 $(a,a^2)$에서의 접선을 그린다.
-2) $a$의 값을 '접선과 직선 $y=2$의 교점'의 $x$좌표로 변경

3. 모든 조작을 끝낸 후 $a$ 값이 바로 $\sqrt{2}$의 근삿값이다.

• 동작 단계

1. 초기값 $a$의 값을 2로 정하겠다.
   ( $\sqrt{2}$와 어느정도 가깝고 적당한 값을 선정)

2. $y=x^2$과 $y=2$의 그래프를 그린다.
   여기서 중요한 부분은 두 그래프 교점의 $x$ 좌표가 $\sqrt{2}$라는 것이다.
   ($2=x^2$ => $x=\sqrt{2}$)

3. $a=2$이므로 $(2,4)$를 지나는 접선 하나를 그린다.
   $f(x)=x^2$에서 접근의 기울기는 $f'(2)$가 된다.
   따라서 접선의 식 => $y=4x-4$

4. 앞에서 구한 접선과 $y=2$의 교차 지점은 $(1.5,2)$

-- 1번째 사이클 --

5. 한번의 사이클을 통하여 구한 교점의 값을 $a$로 설정하여 사이클을 한번 더 진행 한다.

위 동작 단계처럼 진행 시 $a$의 값은 아래와 같이 바뀐다.

사이클 횟수	$a$의 값	일치하는 자릿수
초기값	2	0개
1회	1.5	1개
2회	1.416666...	3개
3회	1.4142156862745098...	6개
4회	1.414213562374689910626...	12개
5회	1.4142135623730950488016896	24개

위 처럼 해당 사이클 횟수가 증가하면 일치하는 자릿수가 배로 늘어나는 것을 확인 할 수 있다.
이와 같이 몇번의 뉴턴법을 사용하면 몇번의 계산만으로 $\sqrt{2}$의 값을 거의 정확하게 구할 수 있다.

코드로 나타내면 아래와 같이 작성이 가능하다.

		double r = 2.0; // √2를 구할 것이므로
		double a = 2.0; // 초깃값은 적당한 수를 할당합니다.
		for (int i = 1; i <= 5; i++) {
			// 점 (a, f(a))의 x 좌표와 y 좌표를 구합니다.
			double japyo_x = a;
			double japyo_y = a * a;
			
			// 접선 식 y = jupseon_a * x + jupseon_b를 구합니다.
			double jupseon_a = 2.0 * japyo_x;
			double jupseon_b = japyo_y - jupseon_a * japyo_x;
			
			// 다음 a의 값 next_a를 구합니다.
			double next_a = (r - jupseon_b) / jupseon_a;
			System.out.format("Step #%d: a = %.12f -> %.12f\n", i, a, next_a);
			a = next_a;
		}

위에서는 $\sqrt{2}$를 구하는 알고리즘을 봤다.
일반적으로 $f(x)=r$이 되는 $x$의 값은 다음과 같은 과정을 거치면 구할 수 있다.

1. $a$에 적절한 초기값 설정
2. -1) $y=f(x)$위 점$(a,f(a))$에서의 접선을 구한다.
   -2) $a$의 값을 "접선과 직선 $y=r$의 교점"의 $x$좌표로 변경
3. 조작을 끝낸 후 $a$의 값이 $f(x)=r$이 되는 근삿값이다.

이렇게 일반화 한 뉴턴법을 사용한다면 다양한 근삿값을 구할 수 있다.

예를 들어

• $f(x) = x^2 , r=2$ 일 때 ➡️ $\sqrt{2}$
• $f(x) = x^3 , r=2$ 일 때 ➡️ $^3\sqrt{2}$
• $f(x) = e^x , r=2$ 일 때 ➡️ $\log_e{2}$
• $f(x) = x^x , r=2$ 일 때 ➡️ $x^x=2$ 가 되는 $x$값이 계산 된다.

수치 계산과 관련되어 뉴턴법을 설명을 했지만, 수치 계산에 있어 뉴턴법 외 다른 방법도 있다.

• 수치 미분* 수치 적분

  모든 함수가 다항식 함수 처럼 정확하게 미분 계수를 계산할 수 없다. 대신 근삿값을 수치적으로 계산할 수 있는데 이것을 수치 미분법이라고 한다.
  그리고 미분의 반대로 적분 또한 근삿값을 구하는 것을 수치 적분이라고 한다.

• 아주 큰 정수 계산

  '만의 자릿수 X 만의 자릿수' 처럼의 거대한 수를 연산할 때 하나 하나 계산을 하는 것이 아닌 Karatsuba법 또는 고속 푸리에 변환을 사용하면 빠르게 계산이 가능하다.