인스타 릴스에서 본 방정식 x^(x+1) = 16, 끝까지 풀어보기

1. Motivation

문제의 릴스. “Can you solve this?”

인스타 릴스에서 누가 이런 문제를 올려놨다.
안 그래도 할 거 없어서 풀어볼까 하고 샤프로 끄적거려봤는데, 내가 가진 ‘상식’으로는 풀 수 없었다.

(x+1)\ln x=\ln 16

여기서 더 할 게 없다.
댓글을 봐도 ‘2’라고 하는 사람들과 ‘3’이라고 하는 사람들이 많았다.
넣어보면 딱 봐도 아닌데. ( $$2^3=8$$ , $$3^4=81$$ . 답은 2와 3 사이 어딘가에 있고, 둘 다 아니다.)

성격상 이런 거 못 참아서, 리서치(?)한 내용을 간략하게 올려본다.

2. Lambert’s W (Introduction)

사실 진짜 별거 아니다.
$$f(x)=xe^x$$ 이 함수의 역함수를 $$W(x)$$ 함수라고 표기하는 방식이다.

즉, $z=W(z)e^{W(z)}$ 를 만족하는 함수 $$W(z)$$ 를
Lambert W Function 이라고 부른다.
일종의 표기법을 만들어낸 것뿐이지, 뭔가 거창한 풀이에 대한 내용은 없다.

왼쪽: $$y=we^w$$ . 이 그래프를 옆으로 뒤집은 것이 $$W$$ 다. 오른쪽: 우리 문제에 해당하는 $$we^w+w$$ . 단조증가라 해가 딱 하나다.

위의 문제는 다음과 같이 적을 수 있다.
$(x+1)\ln x=\ln 16$
이때, $x=e^{\ln x}$ 이므로
$x\ln x+\ln x=\ln 16$
$e^{\ln x}\ln x+\ln x = \ln 16$

이제 $\ln x = w$ 라고 치환하면, 다음의 형태로 변형된다.

we^w+w=\ln 16

이는 아까 봤던 $$we^w=z$$ 꼴의 형태와 다르다.
그래서 좀 더 ‘일반화된’ 람베르트 W를 정의한다.

$$we^w+pw=z$$ 형태의 방정식의 해를 $$w=W_p(z)$$ 라고 정의하자.

그럼 위 식은 $$p=1$$ , $z=\ln 16$ 인 식이므로

x=e^{W_1(\ln 16)}

다음과 같이 표현할 수 있다.
근데 사실 우리는 그냥 기호를 쓴 것뿐이라, 여기에서 더 계산할 수는 없다. 값을 실제로 얻으려면 결국 수치적으로 풀어야 한다.

3. Newton-Raphson Method

인공지능을 배우면서 Gradient Descent와 같이 배운 게 기억난다.
방법은 단순하다.

어떤 그래프 위의 추측값에서 접선을 긋는다.
그 접선이 x축과 만나는 점을 다음 추측값으로 삼는다.
일정 횟수 동안 1과 2를 반복한다.

그림으로 보면 이게 전부다. 시작점을 일부러 멀리( $$x_0=1.9$$ ) 잡아도 세 번 만에 답 근처에 도착한다.

우리의 목표는 $x^{x+1}=16$ 의 해를 찾는 것이므로, 이는 $x^{x+1}-16=0$ 의 해를 찾는 것과 동치다.

함수 $f(x)=x^{x+1}-16$ 이라고 정의하자.
일단 1번(어떤 그래프 위의 추측값에서 접선 긋기) 과정에서 접선을 그어야 하니까, $$f(x)$$ 의 도함수 $$f'(x)$$ 를 구해야겠다.
고등학교 미적 시간에 배운 로그미분법을 활용하면 쉽게 미분이 가능하다.

$y=x^{x+1}$ 이면 $\ln y=(x+1)\ln x$ 이므로,

$\frac{y'}{y}=\ln x+(x+1)\frac{1}{x}$

$y'=y\left(\ln x+(x+1)\frac{1}{x}\right)=x^{x+1}\left(\ln x+1+\frac{1}{x}\right)$

즉 $f'(x)=x^{x+1}\left(\ln x+1+\frac{1}{x}\right)$ 가 된다.

이제 1번은 끝났으니, 2번을 보자.
2번에 따르면, 우리의 다음 추측값 $x_{n+1}$ 은 현재 추측값 $$x_n$$ 에 대한 식으로 나타낼 수 있겠다.

$$x_n$$ 에서 그은 접선이 $$x$$ 축과 만나는 곳이 $x_{n+1}$ 이므로,
접선과 $$x$$ 축이 이루는 각을 $\theta$ 라고 두면

\tan\theta = f'(x_n)=\frac{f(x_n)-0}{x_n-x_{n+1}}

이 식을 정리하면:

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}

다음과 같은 점화식을 얻을 수 있다. (이게 Newton-Raphson의 정수다.)

1번과 2번 알고리즘을 제대로 정의했으니, 이제 직접 구해보자.
사람들의 댓글로 보아 일단 해는 $$x=2$$ 와 $$x=3$$ 사이에 존재한다.
(너무나도 당연하게도. $$f(2)=-8<0$$ , $$f(3)=65>0$$ 이고 $$f$$ 는 연속이니, 중간값 정리에 의해 그 사이 어딘가에서 0을 지난다.)

한 2.3 정도로 시작해보자. $$x_0=2.3$$ .

f(2.3)=2.3^{3.3}-16\approx-0.3793

f'(2.3)=2.3^{3.3}\left(\ln 2.3+1+2.3^{-1}\right)\approx35.4230

x_1=2.3-\frac{-0.3793}{35.4230}\approx2.3107

처음 한 번 돌렸을 때의 결과는 2.3107이 나왔다.
$$f(2.3)$$ 이 음수였으니, 2.3보다는 조금 더 큰 쪽으로 움직인 셈이다.

귀찮으니 파이썬으로 후딱 계산을 때리면 다음과 같은 결과가 나온다.

import math

f  = lambda x: x**(x+1) - 16
fp = lambda x: x**(x+1) * (math.log(x) + 1 + 1/x)

x = 2.3
for n in range(1, 5):
    x = x - f(x) / fp(x)
    print(n, round(x, 6))
# 1 2.310711
# 2 2.310572
# 3 2.310572
# 4 2.310572

$$x_1=2.31071$$
$$x_2=2.31057$$
$$x_3=2.31057$$

두 번 만에 소수점 다섯째 자리까지 딱 멈춰버린다. (Newton-Raphson은 해 근처에서 자릿수가 매 단계 두 배씩 늘어나는 ‘이차 수렴’을 한다.)
이로써 위 문제의 답은 $x\approx2.3106$ 이라고 근사할 수 있다.

Gradient Descent와 뭐가 다른가

둘 다 ‘기울기를 보고 다음 위치를 정한다’는 점은 같다. 하지만 GD는 손실 $$L$$ 을 최소화하려고 $-\eta L'(x)$ 만큼 조금씩 내려가고(학습률 $\eta$ 를 사람이 정한다), Newton은 $$f=0$$ 이 되는 점을 찾으려고 $$f/f'$$ 만큼 한 번에 뛴다(보폭을 접선이 알아서 정한다). GD를 최적화 문제 $$L'(x)=0$$ 에 Newton으로 풀면 $x_{n+1}=x_n-L'(x_n)/L''(x_n)$ 이 되는데, 이게 딥러닝에서 말하는 2차 최적화(Newton’s method for optimization)다. 이차 미분(Hessian)이 너무 비싸서 잘 안 쓸 뿐이다.

대신 Newton은 시작점을 잘못 잡으면(예: $f'(x_n)\approx0$ 인 곳) 엉뚱한 곳으로 튀거나 발산할 수 있다. 위 문제처럼 함수가 단조증가하고 볼록하면 아무 데서 시작해도 잘 간다.

4. Fixed-Point Iteration Method

전에는 미분과 도함수를 사용했다면, 이번에는 우리에게 주어진 방정식 자체를 변형시키는 방법을 써보자.

핵심은 이렇다.
우리에게 주어진 방정식은 $$f(x)=0$$ .
이 식을 어떤 방법이든 $$x=g(x)$$ 의 꼴로 변형시킨다.
만약 $$x=g(x)$$ 의 해를 찾을 수 있으면, 이 해 $$x^*$$ 를 ‘고정점 (Fixed Point)‘이라고 칭한다.
(즉, 이 고정점에서 $$g(x^*)$$ 의 값을 계산하면 자기 자신인 $$x^*$$ 가 나오는 것.)

이를 이용해 다음과 같은 과정을 거친다.

적절한 $$x_0$$ 에서 시작한다.
점화식 $x_{n+1}=g(x_n)$ 을 계속 반복한다.
2번 과정이 수렴하면, 이 수렴값은 고정점이며, 그 고정점은 우리가 찾는 해다.

여기에서 중요한 건, 변형시킨 $$g(x)$$ 의 형태다.
이 $$g(x)$$ 를 어떻게 만드느냐에 따라 이 방법이 성공하느냐 실패하느냐가 갈린다.

예를 들면, 엄청 간단하게 $x=\frac{16}{x^x}$ 라고 뒀다고 생각해보자.
그럼 점화식은 다음과 같다.

x_{n+1}=\frac{16}{x_n^{x_n}}

그러나 이 점화식을 계속 사용해보면, 값은 수렴하지 않고 발산해버린다. ( $2.3 \to 2.36 \to 2.13 \to 3.22 \to \cdots$ )
이유는 해 근처에서 $$|g'(x)|<1$$ 이라는 조건을 만족하지 않기 때문이다.
이를 축소사상원리(Contraction Mapping Principle) 라고 부른다.
(4.1에서 설명한다.)

이번엔 좀 더 적절한 방식으로 변형해보자.

x_{n+1}=e^{\frac{\ln 16}{x_n+1}}

아까와 같이 $$x_0=2.3$$ 에서 시작해보자.
$x_1\approx2.3168$
$x_2\approx2.3070$
$x_3\approx2.3127$
$x_4\approx2.3093$

뭔가 2.31 근처를 빙빙 도는 느낌이다.
(이렇게 위아래로 진동하며 수렴하는 것을 ‘나선형 수렴’이라고 부른다. Newton-Raphson보다 훨씬 느리지만, 계속 돌리면 결국 같은 값 2.3106으로 간다.)

고정점 반복을 그림으로 그리면 ‘거미줄(cobweb) 다이어그램’이 된다. $$x_n$$ 에서 위로 올라가 $$g$$ 를 만나고, 옆으로 가서 $$y=x$$ 를 만나면 그게 $x_{n+1}$ . 왼쪽은 $$g'$$ 의 기울기가 $$y=x$$ 보다 완만해서 안으로 말려 들어가고, 오른쪽은 가팔라서 튕겨 나간다.

즉, $x\approx2.31$ 로 근사할 수 있다.

import math
g = lambda x: math.exp(math.log(16) / (x + 1))
x = 2.3
for n in range(1, 8):
    x = g(x)
    print(n, round(x, 4))
# 1 2.3168 / 2 2.3070 / 3 2.3127 / 4 2.3093 / 5 2.3113 / 6 2.3101 / 7 2.3108

4.1. Contraction Mapping Principle

$$x=g(x)$$ 에서 왜 $$x^*$$ 를 구하는 조건이 $$|g'(x^*)|<1$$ 일까?

1. 먼저 직관적으로, 기하학적으로 분석해보자.

$$x=g(x)$$ 의 해가 $$x^*$$ 라는 것은 $$y=x$$ , $$y=g(x)$$ 의 교점의 $$x$$ 좌표가 $$x^*$$ 라는 뜻이기도 하다.

이때, $$|g'(x^*)|<1$$ 의 의미는 $$g(x)$$ 그래프의 $$x^*$$ 에서의 접선의 기울기가 1보다 작다는 뜻.
즉, $$y=x$$ 의 기울기보다 완만하다는 뜻.
그래서 점화식의 과정을 그래프로 나타내보면 점점 $$x^*$$ 와의 거리가 줄어드는 것이다.

반대로, $$|g'(x^*)|>1$$ 이면 $$y=x$$ 의 기울기보다 가파르게 되어서
점화식의 과정 그래프가 $$x^*$$ 에서 튕겨나가게 된다.
즉 발산하게 된다.

2. 직관에서 좀 더 나아가, 평균값 정리를 이용해 축소사상원리를 증명할 수 있다.

평균값 정리를 기억하는가?

어떤 그래프가 $$[a, b]$$ 에서 연속이고 $$(a, b)$$ 에서 미분가능하다면 $\frac{f(b)-f(a)}{b-a}=f'(c)$ 를 만족하는 $c \in (a,b)$ 가 적어도 하나 존재한다.

결국 미분가능한 함수에서, 그래프 위의 두 점을 이은 선(할선)과 평행한 접선이 반드시 존재한다는 정리다.

어떤 단계 $$n$$ 에서의 추측값 $$x_n$$ 과 $$x^*$$ 사이의 오차를
$$e_n=x_n-x^*$$ 라고 정의하자.
그럼 다음 단계의 오차 $e_{n+1}$ 은 다음과 같이 정의된다.

e_{n+1}=x_{n+1}-x^*=g(x_n)-g(x^*)

이때, 평균값 정리에 따라 $$x_n$$ 과 $$x^*$$ 사이의 어떤 점 $$c$$ 에 대해 다음이 성립한다.

\[g(x_n)-g(x^*)=g'(c)(x_n-x^*)\]

이를 위의 오차에 대입하면,

e_{n+1}=g'(c)\cdot e_n

마지막으로 위 식의 양변에 절댓값을 취하면

|e_{n+1}|=|g'(c)|\cdot |e_n|

이게 무슨 뜻이냐.
만약 $$|g'(x)|<1$$ 이라면, $$|g'(c)|$$ 는 1보다 작은 어떤 $$k$$ 가 된다.

|e_{n+1}| = k\cdot |e_n|

즉 위와 같은 관계가 되어 오차가 매 단계 $$k$$ 배씩 줄어든다.

숫자로 확인해보기

우리 $g(x)=e^{\ln 16/(x+1)}$ 의 도함수는 $g'(x)=-\frac{\ln 16}{(x+1)^2}\,g(x)$ 이고, 해 근처에서 $g'(x^*)\approx-0.58$ 이다. 절댓값이 1보다 작으니 수렴하고, 부호가 음수라서 매번 반대편으로 넘어간다 — 그래서 위에서 본 것처럼 2.3168, 2.3070, 2.3127, … 하고 위아래로 진동(나선형 수렴)한 것이다. 오차가 매 단계 약 0.58배씩만 줄어드니(선형 수렴), 자릿수가 매 단계 두 배가 되는 Newton과 속도 차이가 어마어마하다. 아래 그림이 그 차이다.

이 원리를 완비거리공간에서 일반화한 것이 바나흐 고정점 정리(Banach fixed-point theorem) 이고, 미분방정식 해의 존재성 증명(Picard 반복)부터 강화학습의 Bellman 연산자 수렴 증명까지 온갖 곳에서 같은 논리가 반복된다.

세 방법 모두 같은 답으로 가지만, 오차가 줄어드는 속도는 전혀 다르다. 로그 축에서 직선이면 선형 수렴, 아래로 꺾여 떨어지면 이차 수렴.

5. Conclusion

Desmos로 그려본 $y=x^{x+1}$ 과 $$y=16$$ 의 교점. $x\approx2.31057$ .

방법	필요한 것	반복 몇 번에 소수 5자리?	한 줄 요약
Lambert W ( $$W_1$$ )	표기법	— (닫힌 식은 나오지만 계산은 못 함)	답의 ‘이름’을 붙여줌
Newton-Raphson	$$f$$ , $$f'$$	2번	접선의 $$x$$ 절편으로 점프, 이차 수렴
고정점 반복	잘 고른 $$g$$	약 15번	축소사상이면 수렴, 선형 수렴
이분법	부호가 바뀌는 구간	약 18번	느리지만 절대 안 망함

Newton-Raphson도, 고정점 반복도, Desmos도 전부 같은 곳( $x\approx2.3106$ )을 가리킨다.
모르는 걸 알게 되어서 기분은 좋았다.
근데 내 두 시간은 어디 갔지?

참고 자료

Lambert W function — Wikipedia: 가지 구조, 급수 전개, 어디에 쓰이는지 총정리.
István Mező, Árpád Baricz, On the generalization of the Lambert W function, Trans. Amer. Math. Soc. 369 (2017). $$xe^x+rx=a$$ 의 해 $$W_r(a)$$ — 이 글의 $$W_p$$ 가 정확히 이것.
Newton’s method — Wikipedia, Fixed-point iteration — Wikipedia, Banach fixed-point theorem — Wikipedia.
scipy.special.lambertw: 표준 Lambert W를 파이썬에서 바로 계산할 때. ( $$x^x=a$$ 같은 문제는 $x=\ln a/W(\ln a)$ 로 닫힌 식이 나온다.)

방법	필요한 것	반복 몇 번에 소수 5자리?	한 줄 요약
Lambert W ( $\(W_1\)$ )	표기법	— (닫힌 식은 나오지만 계산은 못 함)	답의 ‘이름’을 붙여줌
Newton-Raphson	$\(f\)$ , $\(f'\)$	2번	접선의 $\(x\)$ 절편으로 점프, 이차 수렴
고정점 반복	잘 고른 $\(g\)$	약 15번	축소사상이면 수렴, 선형 수렴
이분법	부호가 바뀌는 구간	약 18번	느리지만 절대 안 망함