자바스크립트로 배우는 SICP - 6. 평균 감쇠와 뉴턴 방식을 이용한 함수의 고정점 구하기

이분법과 평균감쇠 방법과 뉴턴 방법을 이용하여 함수의 고정점을 구하는 방법을 알아보고 이를 추상화해보자!

2023-10-29 | 독서 | 15min

오늘 부분은 생각보다 까다롭지만 추상화의 정수를 보여주는 파트라고 할 수 있을 것 같다. 5일차 포스트와 더불어 진짜 좋아하는 파트이다. 그럼 키워드부터 알아보자! 참고로 5일차 포스트에서는 수치 연산을 추상화하는 방법을 알아보았다면, 이번 포스트는 한 발짝 더 나아가 일반화/추상화의 좀 더 본격적인 예시들을 다룬다. 그럼 알아보러 가보자!

키워드

오늘의 키워드는 다음과 같다.

이분법, 방정식의 근
함수의 고정점
평균감쇠
함수를 반환하는 함수
뉴턴 방법
추상화 그리고 일급 함수

그럼 하나씩 키워드 중심으로 살펴보자!

방정식의 근 구하기

방정식의 근을 구하는 방법은 다들 알 것이다! 인수분해를 하거나, 근의 공식을 이용하거나, 노가다 등의 방법들을 활용했던 기억이 날 것이다. 그렇다면 프로그램에서 방정식의 근을 어떻게 구할까? 그 방법에 대해서 알아보자.

이분법

방정식 $f(x) = 0$ 의 근을 구하려면 어떤 방법이 있을까? 함수 $f$ 가 연속함수라는 가정 하에, 0이 되는 지점을 포함하는 구간 $(a,b)$ 를 잡았을 때, 다음 부등식이 성립할 것이다.

f(a)<0<f(b)

이는 고등학교 때 다루는 사이값 정리(또는 중간값 정리)에 해당하는 내용이다! 더 많은 정보는 여기를 참고하자.

위 개념이 바로 이분법 의 핵심이다! 그럼 이분법이 무엇인지 살펴보자.

이분법(bisection method) 또는 구간 반분법(interval halving method)은 방정식 $f(x) = 0$ 의(여기서 $f$ 는 연속함수)의 근(들)을 구하는 간단하지만 강력한 방법이다. … 그러한 영점을 구하는 방법은 이렇다. $x$ 를 $a$ 와 $b$ 의 평균으로 설정하고 $f(x)$ 를 계산한다. 만일 $f(x)>0$ 이면 $a$ 와 $x$ 사이에 $f$ 의 영점이 존재한다. 만일 $f(x)<0$ 이면 $x$ 와 $b$ 사이에 $f$ 의 영점이 존재한다.

즉, 구간의 평균값에 대한 함수 값을 구했을 때, 그 부호를 판단하여 함수의 영점이 구간 사이에 존재하도록 구간의 한쪽 끝을 평균값으로 대체하여 구간의 범위를 줄여나가는 방법이 바로 이분법이다!

코드로 구현하면?

그럼 이를 코드로 구현해보자! 다음은 함수의 영점을 찾는 함수이다.

function close_enough(x, y) {
    return abs(x - y) < 0.001;
}

function search(f, neg_point, pos_point) {
	const mid_point = average(neg_point, pos_point);
	if (close_enough(neg_point, pos_point)) {
		return mid_point;
	} else {
		const test_value = f(mid_point);
		return positive(test_value)
					 ? search(f, neg_point, mid_point)
					 : negative(test_value)
					 ? search(f, mid_point, pos_point)
					 : mid_point;
	}
}

위 코드에서는 neg_point 와 pos_point 를 초기 구간으로 설정하고 있다.
average 함수를 이용하여 구간의 평균값을 구하고 있다.
close_enough 함수로 구간의 간격을 구하여 충분히 가까울 때 평균값을 반환한다. → 종료 판정 조건
구간의 간격이 충분히 가깝지 않을 때, 평균값의 함수값인 f(mid_point) 가 양수인지 positive 함수로 판단하여 이후 재귀적 과정을 거칠 구간을 새롭게 정하고(평균값 이용) 재귀 호출을 진행한다.

이게 최선일까?

앞서 구현된 코드의 단점은 무엇일까? 만약 매개변수로 대입하는 구간 경계값이 잘못될 경우, 그 어떠한 처리도 진행되지 않고 있다! 만약 구간의 두 끝점이 모두 양수이거나 음수이면 이분법을 적용할 수 없다. 이를 개선한 코드는 다음과 같다!

function half_interval_method(f, a, b) {
    const a_value = f(a);
    const b_value = f(b);
    return negative(a_value) && positive(b_value)
           ? search(f, a, b)
           : negative(b_value) && positive(a_value)
           ? search(f, b, a)
           : error("values are not of opposite sign");
}

우선 두 끝점의 함수값을 각각 a_value , b_value 로 설정한다.
그리고 두 값들이 각각 음수, 양수인지를 확인하는 과정을 추가해서 서로 부호가 다르지 않을 경우, 에러를 반환하도록 구성한 함수이다.

증가차수는?

그럼 이분법 코드의 증가 차수는 어떻게 될까?

직관적으로는 매 구간이 절반으로 줄기에 $\theta(logn)$ 일 것이라는 예상이 가능하다. (실제로 그렇다!)

더욱 구체적으로 작성할 수는 없을까? 있다! 기존의 구간이었던 $(a,b)$ 의 구간 길이을 $L$ 이라고 하자. 그리고 close_enough 함수 내에 있을 허용 오차 범위를 $T$ 라고 했을 때, 증가차수는 $\theta(log\frac{L}{T})$ 이 된다!

함수의 고정점

함수의 고정점이라는 것은 무엇일까? 정의는 다음과 같다.

함수 \space f에 \space 대해 \space f(x) = x를 \space 충족하는 \space 수

그러면 고정점 이라는 개념을 어떤 방법으로 programmatic 하게 적용할 수 있을까? 다음 과정을 생각해보자!

f(x) \rightarrow f(f(x)) \rightarrow f(f(f(x))) \rightarrow \space \cdots

위와 같이 이전의 함수 반환 값을 다시 대입하는 과정을 거치면 된다! 즉, 초기 추측값에서 출발해서 함숫값이 별로 변하지 않을 때까지 $f$ 를 반복적으로 적용하면 $f$ 의 고정점을 발견할 수 있다.

이를 코드로 구현하면 다음과 같다.

const tolerance = 0.00001; // 오차범위를 설정한 것이다.
 
function fixed_point(f, first_guess) {
	function close_enough(x, y) { // 오차범위 내에 있는지에 대한 여부를 검사한다.
		return abs(x - y) < tolerance;
	}
	function try_with(guess) { // 반복적으로 함수 f를 적용한다.
		const next = f(guess);
		return close_enough(guess, next)
					 ? next
					 : try_with(next);
	}
	return try_with(first_guess);
}

위 코드는 크게 오차범위 내에 있는지를 확인하는 close_enough 함수와 반복적으로 함수 f 를 적용하는 try_with 함수로 나눠진다. 이렇게 구성된 fixed_point 함수는 고정점을 구할 함수와 초기 추측값을 대입하면, 반복적으로 함수를 적용하여 반환값이 추측값과 가까운 정도를 확인하여 고정점을 구할 수 있다!

한 예시로, 코사인 함수의 고정점을 구하는 과정을 fixed_point 로 구현하면 다음과 같다.

fixed_point(math_cos, 1);

평균감쇠

다른 예시로 제곱근을 구하는 함수를 생각해보자! 그러면 똑같이 위와 같은 형태로 구현하면 되려나?

function sqrt(x) {
	return fixed_point(y => x/y, 1);
}

다시 돌아와서, 위에서 작성한 코드는 제곱근 함수의 고정점을 구하는 함수로 적절할까? 아니다!

y_3 = x/y_2 = x(x/y_1) = y_1

사실 y ⇒ x/y 형태의 함수는 무한루프를 조성해버린다! 해당 함수의 적용이 두 번 이뤄지면, 다시 원래의 값으로 돌아와 끝없이 함수의 적용을 반복하게 된다. (위의 등식을 보자!)

그럼 어떻게 무한루프를 피해갈 수 있을까? 다음 코드를 보자.

function sqrt(x) {
	return fixed_point(y => average(y, x / y), 1)
}

앞서 언급한 코드와 차이점은 y ⇒ x/y 가 아닌 y ⇒ average(y, x / y) 이다!

y = x/y \Longleftrightarrow y = \frac{1}{2}(y+\frac{x}{y})

사실 average 함수가 있기도 하고 뭔가 형태가 특이해 보이지만, 전개하면 결국 같은 식이다…!

그럼 이렇게 바꾸었을 때는 차이점이 무엇인가? 기존처럼 함수가 무한루프에 빠지지 않고 정상적으로 값을 반환한다! 이러한 방식을 평균 감쇠(average damping) 라고 한다.

함수 by 함수

지금까지 다뤄왔던 추상화 방법은 이름 짓기, 함수 만들기, 함수를 인수로 받는 함수 만들기였다. 여기서 한 단계 더 나아가서 함수를 반환하는 함수에 대해서 알아보자!

다음은 앞서 제곱근을 구하는 평균 감쇠 함수를 일반화한 함수이다! 함수의 형태와 상관없이 특정 함수의 평균 감쇠를 위한 함수를 만들면 다음과 같을 것이다.

function average_damp(f) {
	return x => average(x, f(x));
}

다시 이를 이용하여 sqrt 함수를 재작성하면 다음과 같다.

function sqrt(x) {
	return fixed_point(average_damp(y => x / y), 1)
}

이렇게 추상화된 평균 감쇠를 이용한 고정점을 구하는 함수는 크게 세 가지 영역으로 구분될 수 있다.

fixed_point 라는 고정점을 구하기 위한 함수 → 함수의 종류와 무관
average_damp 라는 평균 감쇠를 이용하는 함수 → 함수의 종류와 무관
y ⇒ x/y 라는 우리가 고정점을 구하려 하는 대상이 되는 함수 → 함수의 종류와 유관

즉, 이제 y ⇒ x/y 자리에 다른 함수를 넣는다면, 다른 함수의 고정점을 평균감쇠로 구할 수 있게 되는 것이다!

그렇다면 이번엔 세제곱근을 구하는 cube_root 라는 함수를 작성해보자!

function cube_root(x) {
	return fixed_point(average_damp(y => x / square(y)), 1);
}

여기서는 $y \mapsto x^2/y$ 를 대신 넣어다고 보면 된다!

뉴턴 방법을 이용한 고정점 찾기

기초 미적분 교과서들은 뉴턴 방법을, $x_{n+1}=x_n-g(x_n)/g^{'}(x_n)$ 의 점화식을 반복해서 적용하여 근삿값을 구하는 과정으로 설명한다.

뉴턴 방법에 대한 자세한 설명은 여기를 참고하자! 아래는 뉴턴 방법의 함수를 나타낸 것이다!

f(x) = x - \frac{g(x)}{g^{'}(x)}

이제 이를 코드로 구현해보자. 우선 도함수의 정의는 다음과 같다!

함수 g의 도함수의 정의는 아래와 같다.
$g'(x) = \frac{g(x+dx)-g(x)}{dx}$

이제 이를 코드로 옮기는 다음과 같이 작성할 수 있다.

const dx = 0.00001; // 임의로 설정한 값이다!
function deriv(g) {
	return x => (g(x + dx) - g(x)) / dx
}

이렇게 구현한 deriv 라는 함수를 이용하여 뉴턴 함수를 구현하면 다음과 같을 것이다.

function newton_transform(g) {
	return x => x - g(x) / deriv(g)(x)
}

그리고 이를 앞서 언급한 fixed_point 를 이용하여 뉴턴 방법을 이용한 고정점을 구하는 함수는 다음과 같이 작성할 수 있다!

function newtons_method(g, guess) {
	return fixed_point(newton_transform(g), guess);
}

평균감쇠 방법에서 단순하게 뉴턴 방법 으로 바뀌었다는 점을 기억해두면 좋을 것이다!

이를 적용하여 sqrt 함수를 재구현하면 다음과 같다. (여기서 뉴턴 방법을 위한 함수로 다시 바꿔야 한다. y ⇒ y/x 가 아닌 y ⇒ $y^2 - x$ 로 생각해야 한다!)

function sqrt() {
	return newtons_method(y => square(y) - x, 1)
}

앞의 함수를 데려와서 비교해보자! 형태가 매우 유사하다!

function sqrt(x) {
	return fixed_point(y => average(y, x / y), 1)
}
 
function sqrt() {
	return newtons_method(y => square(y) - x, 1)
}

어라? 형태가 비슷하다…? 그럼…?

바로 앞선 예시가 비슷한 형태를 띠고 있다! 이를 추상화해보자.

function fixed_point_of_transform(g, transform, guess) {
	return fixed_point(transform(g), guess)
}

이는 고정점을 구하는 함수만 남긴 채로 뉴턴일지, 평균 감쇠일지를 결정할 수 있도록 transform , g 를 매개변수로 설정하여 추상화하고, 초기 추정값인 guess 까지 받아 구현한 하나의 함수를 받아 그 함수의 고정점을 찾는 함수의 일반적 형태를 작성한 것이다.

다시 이 틀을 이용하여 sqrt 를 구현한 두 방법을 작성하면 다음과 같다.

// 평균 감쇠를 이용한 방법
function sqrt(x) {
	return fixed_point_of_transform(y => x/y, average_damp, 1)
}
// 뉴턴 방법을 이용한 방법
function sqrt(x) {
	return fixed_point_of_transform(y => square(y) - x, newton_transform, 1)
}

일급자격을 지닌 함수

일반적으로 프로그래밍 언어는 계산적 요소들의 조작방식에 제약을 가한다. 이러한 제약이 가장 적은 요소를 일급 자격의 요소 라고 한다! 이 자격은 다음의 권리와 특권을 지니다.

이름 으로 지칭할 수 있다 → 어휘적 환경을 조성해 이와 연결지을 수 있다는 것이다!
함수에 전달하는 인수 가 될 수 있다. → 매개변수로서 이용이 가능하다!
함수가 돌려주는 반환값 이 될 수 있다.
자료 구조 에 포함할 수 있다

이러한 일급 자격을 지닌 자바스크립트의 가장 대표적인 예시가 바로 함수 인 것이다. 그리고 지금까지 많은 추상화 방법들을 통해 공통의 패턴을 찾아 함수를 구현했듯 함수를 이용하면 표현력의 이득이 엄청나게 크다!

마무리

지금까지 1장의 내용을 읽어보았다! 내용 하나하나가 무시할 수 없을만큼 귀하고 질 높은 내용들이라 책너두 챌린지를 하면서 20페이지 가량씩 보는게 오히려 나에게 도움을 준 것 같았다. 누적된 이전의 내용들이 이후의 내용 이해에 도움을 주다보니 더욱 머릿속에 오래 남았던 것 같았다. 쨋든 오늘 하루도 알찼다! 다음은 2장으로 가보자~~