근사 이론(Approximation theory)

컴퓨터의 수학 라이브러리가 $\sin x$나 $e^x$를 구할 때 실제로 하는 계산은 대개 덧셈과 곱셈입니다. 그러니 함수를 다항식으로 바꾸어야 하는데, 어떤 다항식이 가장 좋을까요? 테일러 급수⁠(Taylor series)⁠는 한 점에서의 미분값만으로 다항식을 만들어 그 점 근처에서는 아주 정확하지만, 멀어질수록 오차가 커집니다. 근사 이론은 구간 전체를 봅니다. 오차를 구간 안의 가장 큰 오차 $\max|f(x) - p(x)|$로 잽니다. 구간의 모든 x에서 f(x)와 p(x)의 차를 구해 그 크기 가운데 가장 큰 값을 고른다는 뜻입니다. 그리고 이것을 가장 작게 하는 다항식을 찾습니다. 두 함수 사이의 이 '가장 큰 어긋남'을 체비쇼프 거리⁠(Chebyshev distance)⁠라고도 합니다.

이 물음을 처음 체계적으로 던진 사람은 상트페테르부르크의 파프누티 체비쇼프였습니다. 그는 증기기관의 피스톤을 곧게 움직이는 제임스 와트의 연결 장치를 연구하다가, 1853년 무렵 '곡선을 가장 작은 최대 오차로 흉내 내는' 문제를 세웠습니다. 와트의 장치는 원 운동으로 직선을 흉내 내는데 완벽할 수는 없으니, 어긋남의 최댓값을 가장 작게 하자는 것이었습니다.

가장 좋은 직선. 가장 쉬운 경우부터 해 봅시다. [0, 1]에서 함수 를 직선 $y = mx + c$로 흉내 냅니다. 기울기⁠(slope)⁠ $m =$ , 절편 $c =$ 를 움직여 가장 큰 오차를 줄여 보세요. 가운데의 접선 가장 좋은 직선

왼쪽은 함수(흰색검은색)와 직선(파랑), 오른쪽은 오차 $f - p$(분홍)이고, 노란 점이 가장 큰 오차가 나는 곳입니다.

직선을 조금씩 옮기다 보면 규칙이 보입니다. 가장 큰 오차가 한 곳에서만 나면 직선을 그쪽으로 조금 밀어 줄일 수 있습니다. 더 줄일 수 없는 순간은 오차가 같은 크기로, 부호를 바꿔 가며 세 번 나타날 때입니다. $x^2$이라면 가장 좋은 직선은 $x - 1/8$이고, 오차 $x^2 - (x - 1/8)$은 x = 0, 1/2, 1에서 +1/8, −1/8, +1/8입니다. 가운데 점의 접선⁠(tangent line)⁠ $x - 1/4$는 양 끝에서 오차가 1/4이니 두 배나 나쁩니다.

이 규칙을 일반화한 것이 체비쇼프의 등진동 정리입니다. 먼저 말 하나를 정합니다. 다항식의 차수는 그 안에 든 x의 가장 높은 거듭제곱입니다. 직선 mx + c는 차수가 1 이하이고, $3x^2 + 1$은 차수가 2입니다. 정리는 이렇습니다. 구간 [a, b]에서 끊김 없이 이어진(연속인) 함수 f와 차수가 n 이하인 다항식 p를 생각합니다. p가 최대 오차를 가장 작게 하는 다항식이라는 것은, 오차 $f - p$가 그 최대 크기 E에 적어도 n + 2개의 서로 다른 점에서 +E, −E, +E, …처럼 번갈아 닿는다는 것과 같습니다. 그런 다항식은 오직 하나입니다. 직선은 n = 1이니 1 + 2 = 3개의 점이고, 위에서 본 세 점이 그것입니다.

이 성질을 거꾸로 쓰면 가장 좋은 다항식을 찾을 수 있습니다. 오차가 번갈아 닿을 점들을 짐작해 두고, 그 점들에서 오차가 같은 크기로 번갈아 나도록 다항식을 고친 뒤, 실제로 최대 오차가 나는 점들로 짐작을 바꾸기를 되풀이합니다. 1934년 키이우의 예브게니 레메즈가 만든 이 방법을 레메즈 알고리즘⁠(algorithm)⁠이라 하고, 오늘날 수학 함수 라이브러리의 다항식 계수가 흔히 이렇게 만들어집니다.

체비쇼프 다항식⁠(Chebyshev polynomial)⁠. 등진동하는 가장 깨끗한 예가 체비쇼프 다항식 $T_n$입니다. $x = \cos\theta$로 두고 $T_n(x) = \cos n\theta$로 정합니다. n = 2라면 삼각함수의 덧셈정리⁠(angle addition formulas)⁠에서 나오는 배각 공식 $\cos 2\theta = 2\cos^2\theta - 1$에 따라 $T_2(x) = 2x^2 - 1$입니다. 일반적으로는 덧셈정리⁠(addition formula)⁠ $\cos(n+1)\theta = \cos n\theta\cos\theta - \sin n\theta\sin\theta$와 $\cos(n-1)\theta = \cos n\theta\cos\theta + \sin n\theta\sin\theta$를 더해 $\cos(n+1)\theta + \cos(n-1)\theta = 2\cos\theta\cos n\theta$를 얻습니다. x로 바꿔 쓰면 $T_{n+1} = 2x\,T_n - T_{n-1}$이라는 점화식⁠(recurrence relation)⁠입니다. $T_0 = 1$, $T_1 = x$에서 시작해 x를 곱하고 빼기만 하니 $T_n$은 정말로 x의 다항식입니다. 예를 들어 $T_3 = 2x(2x^2 - 1) - x = 4x^3 - 3x$입니다.

θ가 0에서 π까지 가는 동안 $\cos n\theta$는 1과 −1에 번갈아 n + 1번 닿습니다. 그래서 [−1, 1]에서 $T_n$은 −1과 1 사이를 꽉 채워 n + 1번 오가며 흔들립니다. 이 흔들림이 또 하나의 '가장 작은' 성질을 줍니다. 가장 높은 거듭제곱 $x^n$ 앞에 붙은 수를 최고차항 계수라 하는데, 점화식에서 매번 2x를 곱하므로 $T_n$의 최고차항 계수는 $2^{n-1}$입니다($T_3$이라면 4). 그러니 $2^{1-n}T_n$은 최고차항 계수가 1입니다. 최고차항 계수가 1인 n차 다항식 가운데 [−1, 1]에서 최댓값의 크기가 가장 작은 것이 바로 $2^{1-n}T_n$이고, 그 최댓값은 $2^{1-n}$입니다.

까닭은 이렇습니다. 최고차항 계수가 1이면서 최댓값의 크기가 $2^{1-n}$보다 작은 n차 다항식 q가 있다고 해 봅시다. $2^{1-n}T_n$이 $+2^{1-n}$과 $-2^{1-n}$에 번갈아 닿는 n + 1개의 점에서, 차 $2^{1-n}T_n - q$는 양수와 음수를 번갈아 가집니다. 그러니 그 사이사이에서 적어도 n번 0이 됩니다. 그런데 두 다항식의 $x^n$ 항은 서로 지워지므로 이 차의 차수는 n − 1 이하이고, 0이 아닌 (n − 1)차 이하 다항식은 n − 1번보다 많이 0이 될 수 없습니다. 모순이므로 그런 q는 없습니다.

점을 지나게 하기: 룽게 현상⁠(Runge's phenomenon)⁠. 더 손쉬운 방법은 구간에서 점 몇 개를 골라 그 점들을 정확히 지나는 다항식을 만드는 것입니다(다항식 보간⁠, polynomial interpolation⁠). 서로 다른 n + 1개의 점을 지나는 n차 이하 다항식은 하나뿐이고, 라그랑주의 공식으로 바로 적을 수 있습니다. 점을 늘리면 점점 좋아질 것 같지만, 1901년 독일의 카를 룽게는 그렇지 않은 예를 보였습니다. 함수 를 점 개로 보간⁠(interpolation)⁠해 봅시다. 차수 $n =$ .

처음 값 n = 10에서 고르게 놓은 점이면 가장 큰 오차는 약 1.9이고 양 끝 근처에서 납니다. 체비쇼프 점으로 바꾸면 약 0.11로 줄어듭니다. n을 20으로 올리면 고르게 놓은 점의 오차는 약 60으로 오히려 커지고, 체비쇼프 점의 오차는 약 0.015로 더 줄어듭니다. 점을 늘린다고 늘 좋아지는 것이 아니며, 점을 어디에 두느냐가 중요하다는 것이 룽게 현상입니다.

오차가 왜 이렇게 되는지는 보간 오차의 공식이 일부 알려 줍니다. f가 n + 1번 미분⁠(differentiation)⁠ 가능하면, 각 x마다 구간 안의 어떤 점 ξ('크시')가 있어서 다음이 성립합니다.

$$f(x) - p(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\,(x - x_0)(x - x_1)\cdots(x - x_n).$$

여기서 $x_0, \ldots, x_n$은 보간에 쓴 점입니다. 앞의 분수에서 $f^{(n+1)}(\xi)$는 f를 n + 1번 미분한 함수의 ξ에서의 값이고, (n + 1)!('n + 1 계승⁠(factorial)⁠')은 1 × 2 × … × (n + 1)입니다. 이 분수는 함수가 정하고, 뒤의 곱은 점을 어디에 두느냐가 정합니다. 점을 고르게 두면 이 곱이 양 끝 근처에서 가운데보다 훨씬 크게 흔들립니다.

룽게의 함수 $1/(1 + 25x^2)$은 실수⁠(real number)⁠에서는 매끄럽지만, x를 복소수⁠(complex number)⁠로 넓히면 $\pm i/5$에서 분모가 0이 되어 값이 무한대로 치솟습니다. 이런 점을 극이라 합니다(영점과 극⁠, zeros and poles⁠). 극이 구간 가까이 있으면 도함수⁠(derivative function)⁠가 차수와 함께 빠르게 커집니다(수렴반경⁠(radius of convergence)⁠). 이 함수라면 앞의 분수가 대략 $5^{n+1}$만큼 자랍니다. 그래서 고르게 놓은 점에서는 양 끝의 오차가 폭발하고, 점 21개(n = 20)로는 최대 오차가 약 60입니다.

뒤의 곱의 최댓값을 가장 작게 만드는 점 배치가 바로 $T_{n+1}$의 영점(값이 0이 되는 점)인 체비쇼프 점 $x_k = \cos\frac{(2k+1)\pi}{2n+2}$(k = 0, 1, …, n)입니다. 반원 위에 고르게 놓은 점을 지름에 내려 찍은 것이라 양 끝에 촘촘합니다. 이때 곱은 최고차항 계수가 1인 n + 1차 다항식 $2^{-n}T_{n+1}$이 되므로, 앞 절의 성질에 따라 그 최댓값 $2^{-n}$이 가능한 가장 작은 값입니다. 같은 함수를 체비쇼프 점 21개로 보간하면 최대 오차는 약 0.015로 떨어집니다.

흔히 이 성공을 위의 공식만으로 설명할 수 있다고 생각하지만, 그렇지 않습니다. 룽게 함수에서는 앞의 분수가 $5^{n+1}$ 꼴로 자라므로, 뒤의 곱을 $2^{-n}$으로 줄여도 둘을 곱한 위쪽 어림은 n과 함께 오히려 커집니다. 공식의 어림만으로는 오차가 줄어든다는 보장이 나오지 않습니다. 실제로 수렴⁠(convergence)⁠하는 까닭은 따로 알려져 있습니다. 함수가 구간 [−1, 1]과 그 둘레의 복소평면⁠(complex plane)⁠에서 극 같은 특이점⁠(singularity)⁠ 없이 매끄러우면(룽게 함수처럼 극이 구간에서 떨어져 있으면), 체비쇼프 점에서의 보간은 n이 커질수록 빠르게 수렴합니다. 다만 1914년 게오르크 파버는 어떤 점 배치를 미리 정해 두든 보간이 수렴하지 않는 연속함수가 있다는 것도 보였습니다. 보간은 편리하지만 만능은 아닙니다.

바이어슈트라스의 정리. 그렇다면 연속함수라면 무엇이든 다항식으로 원하는 만큼 가깝게 할 수 있을까요? 1885년, 일흔을 앞둔 카를 바이어슈트라스가 답했습니다. 바이어슈트라스 근사 정리⁠(Weierstrass approximation theorem)⁠: 닫힌 구간 [a, b]의 연속함수 f와 양수 ε('엡실론', 아무리 작아도 됩니다)이 주어지면, 구간의 모든 x에서 $|f(x) - p(x)| \lt \varepsilon$인 다항식 p가 있습니다. 다항식열이 f로 균등 수렴⁠(uniform convergence)⁠하게 할 수 있다는 말입니다. 이 정리는 미분할 수 없는 점이 있는 $|x|$에도, 바이어슈트라스 자신이 1872년에 발표한 '어디서도 미분할 수 없는 연속함수'에도 통합니다. 테일러 급수로는 어림도 없는 함수들입니다.

1912년 하르키우의 세르게이 번스타인은 확률⁠(probability)⁠로 이 정리를 다시 증명하며 다항식을 직접 적어 보였습니다. 앞면이 나올 확률이 x인 동전을 n번 던져 앞면이 k번 나오면 $f(k/n)$을 상금으로 받는다고 합시다. 상금의 기댓값⁠(expected value)⁠은 다음과 같습니다.

$$B_n f(x) = \sum_{k=0}^{n} f\!\left(\tfrac{k}{n}\right) \binom{n}{k} x^k (1-x)^{n-k}$$

이것은 x의 다항식이고, 큰 수의 법칙⁠(law of large numbers)⁠에 따라 k/n은 거의 언제나 x 근처에 있으니 기댓값은 f(x)에 다가갑니다(이항분포⁠, binomial distribution⁠). 수렴은 느리지만, 존재를 보이는 데는 이보다 투명한 증명이 드뭅니다.

1937년 미국의 마셜 스톤은 이 정리를 다항식이 아닌 함수들의 모임으로 넓혔습니다(스톤–바이어슈트라스 정리). 모임이 세 조건을 갖추면 됩니다. 첫째, 상수 함수가 들어 있습니다. 둘째, 모임의 함수끼리 더하고 곱하고 상수배해도 모임 안에 남습니다. 셋째, 서로 다른 두 점 x ≠ y를 어떻게 골라도 그 두 점에서 다른 값을 갖는 함수가 모임에 있습니다. 다항식 전체는 세 조건을 다 갖춥니다(셋째는 함수 x 하나로 충분합니다). 또 다른 예로, 연속인 주기함수⁠(periodic function)⁠를 삼각다항식($\sin kx$와 $\cos kx$에 수를 곱해 더한 것)으로 구간 전체에서 한꺼번에 가깝게 근사할 수 있다는 사실도 이 정리의 특별한 경우입니다(푸리에 급수⁠, Fourier series⁠). 신경망⁠(neural network)⁠이 닫힌 유계 영역(경계를 포함하고 끝없이 뻗지 않는 영역)에서 연속함수를 얼마든지 가깝게 흉내 낼 수 있다는 보편 근사 정리⁠(universal approximation theorem)⁠도 같은 계열의 정리입니다(신경망). 다만 이 정리들은 근사가 있다는 것만 말할 뿐, 얼마나 큰 다항식이나 신경망이 필요한지는 따로 따져야 합니다.

이어지는 곳.

• 최대 오차 대신 오차의 제곱합을 줄이면 최소제곱⁠(least squares)⁠과 정사영⁠(orthogonal projection)⁠의 문제가 되고, 그 연속판이 푸리에 급수입니다.
• 어느 잣대로 재느냐에 따라 '가장 좋은' 답이 달라지는 이야기는 Lp 노름⁠(Lp norm)⁠과 근사와 오차에 있습니다.
• 함수열이 구간 전체에서 한꺼번에 다가간다는 말의 정확한 뜻은 점별 수렴과 균등 수렴⁠(pointwise and uniform convergence)⁠에 있습니다.
• 근을 찾는 반복법은 뉴턴 방법⁠(Newton's method)⁠에 있습니다.
• 가장 큰 오차를 가장 작게 하는 문제는 선형 계획법⁠(linear programming)⁠으로도 풀 수 있고, 가장 좋은 것 고르기의 한 모습입니다.
• 체비쇼프의 제자 안드레이 마르코프는 다항식의 도함수가 얼마나 클 수 있는지를 다룬 부등식으로 이 분야에 이름을 남겼습니다.
• 근사 이론은 신경망 설계에도 쓰입니다. HiPPO(2020)는 지금까지 들어온 입력 전체를 르장드르 다항식(구간에서 서로 직교⁠(orthogonality)⁠하는 다항식들)으로 가장 잘 근사하는 계수를 기억으로 들고 다니게 했고, 이 생각이 상태 공간 모형⁠(state space model)⁠ S4의 출발점이 되었습니다.
• 근사는 맞춰 본 구간 안에서만 믿을 수 있습니다. 그래서 언어 모델⁠(language model)⁠이 학습 때보다 긴 문맥을 읽게 할 때는, 처음 보는 큰 위치 번호를 그대로 넣기(외삽⁠, extrapolation⁠)보다 번호를 학습한 범위 안으로 줄여 넣는 편(보간)이 대개 더 안정적입니다(위치 인코딩⁠(positional encoding)⁠).