알고리듬 #9 뉴턴법과 근사해 : 미분·적분으로 수치 계산해보기

이번 글에서는 정답을 찾기 어려울 때 최대한 정답에 근접한 답을 억지로 찾아내는 근사해에 대해 다룬다.

이런 정답에 근접한 답을 구하기 위해서는 값의 변화량을 추론할 수 있어야 하는데 그것을 도와주는것이 미분과 접선의 방정식이다.

미분과 기울기 : 함수에서 값의 순간 변화량

사실 수학은 연속적인 수로 계속 이어져 있다.

이 연속적인 수들을 극한을 통해 어느 한 특정한 지점으로 계속 줄여나가다 보면 그 지점에서의 특정할 수를 근사하게 찾아낼 수 있고, 이 때의 값의 변화율을 기록한 것을 미분값(접선의 기울기)라고 부른다.

미분

접선의 방정식

도함수 : 순간변화율의 기록한 또다른 함수

특정 함수를 미분한 결과를 도함수라고 부른다.

미분이 특정한 순간의 순간 변화율을 구한것이라고 했다.

그렇다면 이 연속적인 수들의 집합을 특정 순간을 변경해 가면서 그때 마다의 순간 변화율을 기록한다면 이 또한 하나의 함수로 표현 할 수 있을 것이다.  이것을 도함수라 부른다.

뉴턴법(Newton's method/Newton–Raphson method)

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

이것은 시각화 해서 보여주는게 빠를 것 같다. 

y = X^2이라는 함수에 대해 root(2)의 근삿값을 찾는다고 가정해보자

step1

적당히 근처에 있는 값 하나를 특정한다(y = 2)

그리고 이 값을 f(x)에 대입하여 그 지점에서의 접선의 방정식을 만들어 

y = 2와의 교점을 구한다.

여기서의 결과는 1.5가 나온다

Step2

이전 스텝에서 구해진 결과를 a에 대입한다.

a = 1.5

이 값을 f(x)에 대입하여 접선의 방정식을 구한다. 

그리고 이 접선과 y = 2와의 교점을 구한다.

이것을 적당히 반복하면 다음과 같이 규칙이 나타남을 알 수 있다.

조작 횟수	a의 값	일치하는 자릿수의 갯수
초깃값	2	0개
step1	1.50000000000000....	1개
step2	1.41666666666666....	3개
step3	1.41421568627450....	6개
stpe4	1.41421356237468991...	12개

뉴턴법은 각 반복점에서 도함수 f′(x(n))가 필요하므로, 해당 점에서 미분값을 계산할 수 없거나 f′(x(x))이 0에 가깝다면 적용과 수렴이 어려울 수 있습니다. 또한 초기값 선택에 민감하므로 항상 최선이라고 할 수는 없다.

그럼에도 근사해를 빠르게 얻을 수 있다는 장점이 있어 널리 쓰인다.

적분의 값을 근사적으로 계산하는 방법을 수치적분이라고 합니다(예: 사다리꼴, 심프슨).

도함수를 구하기 어렵다면 수치미분(유한차분) 으로 f′(x)를 근사해 뉴턴 갱신식을 변형할 수 있다.

다만 차분 간격 h선택에 따른 절단·반올림 오차와 잡음 민감도를 주의해야 한다.

도함수 없이도 수렴하는 할선법(secant), 브렌트(Brent) 같은 대안도 실무에서 자주 사용된다.

아주 큰 정수나 다항식의 곱셈을 빠르게 할 때는 Karatsuba나 FFT 기반 곱셈(고속 푸리에 변환)이 쓰인다.

FFT는 그래픽스/신호처리 응용에서도 널리 사용되므로 별도로 다루겠다.