룽게 현상

1. 개요

룽게 현상 Runge's Phenomenon
무엇이	등간격 절점 고차 다항식 보간이 구간 끝에서 진동·발산
원 예제	1/(1+x2), [−5, 5] (룽게, 1901)
발산 영역	|x| > 3.63 (같은 것: [−1,1] 위 1/(1+25x2) 에서 |x| > 0.7267)
원인	복소평면 특이점 + 등간격 절점의 퍼텐셜 불균형
처방	체비쇼프 절점, 최소제곱 저차 근사, 스플라인, 유리 보간

점을 더 찍었더니 그래프가 더 나빠졌다. 수치해석 첫 학기의 배신.

룽게 현상(Runge’s phenomenon)은 매끄러운 — 심지어 실축 위에서 무한히 미분 가능한 — 함수를 등간격 절점에서 다항식으로 보간할 때, 차수를 올릴수록 구간 양 끝에서 보간 다항식이 크게 진동하며 오차가 무한대로 커지는 현상이다. 칼 룽게가 1901년 $f(x) = 1/(1+x^2)$ 을 $[-5,5]$ 에서 보간해 보인 것이 원조다.

기본 그림과 르베그 상수 실측표, 체비쇼프 절점으로의 처방은 보간과 근사와 체비쇼프 다항식에 이미 있다. 이 문서는 그다음 질문들을 다룬다. 정확히 어디서부터 발산하는가, 왜 하필 $1/(1+25x^2)$ 은 터지고 $1/(1+x^2)$ 은 안 터지는가, 이론상 수렴해야 할 때도 왜 컴퓨터에서는 터지는가, 그리고 “등간격 데이터로는 원리적으로 어디까지 할 수 있나”에 대한 2011년의 불가능성 정리다.

2. 어디서부터 터지나 — 퍼텐셜 이론의 답

$n+1$ 개 절점 $x_0,\dots,x_n$ 에서의 보간 오차는 복소 적분으로 쓸 수 있다($\Gamma$ 는 구간과 절점을 감싸고 $f$ 의 특이점은 피하는 곡선).

$$f(x) - p_n(x) = \frac{1}{2\pi i}\oint_\Gamma \frac{\omega(x)}{\omega(t)}\,\frac{f(t)}{t - x}\,dt, \qquad \omega(z) = \prod_{k=0}^{n}(z - x_k)$$

핵심은 비율 $|\omega(x)/\omega(t)|$ 다. $n \to \infty$ 에서 $|\omega(z)|^{1/n} \to e^{\phi(z)}$ 로 가는데, 등간격 절점(극한 밀도가 균일)에 대해서는

$$\phi(z) = \tfrac12\,\mathrm{Re}\big[(z+1)\log(z+1) - (z-1)\log(z-1)\big] - 1$$

이다. 이 퍼텐셜은 구간 위에서 평평하지 않다 — 가운데 $\phi(0) = -1$, 끝 $\phi(\pm1) = \log 2 - 1 \approx -0.307$ 로 끝이 높다. 그래서 오차는 대략 $e^{n[\phi(x) - \phi(z_0)]}$ 처럼 굴고($z_0$ 는 $\Gamma$ 를 더 이상 키울 수 없게 막는, 가장 가까운 특이점), 결론은 이렇다.

실수 $x$ 에서 보간이 수렴하는 것은 $\phi(x) < \phi(z_0)$ 일 때, 즉 $x$ 를 지나는 $\phi$ 의 등고선 안에 특이점이 없을 때다.

$f = 1/(1+25x^2)$ 의 극점은 $z_0 = \pm 0.2i$ 다. 계산하면 $\phi(0.2i) \approx -0.7057$, 이 값을 실축에서 다시 만나는 점이 $x_c \approx \pm 0.7267$. 그러니 $|x| < 0.7267$ 에서는 수렴, 바깥에서는 발산이다. $[-5,5]$ 로 늘이면 $5 \times 0.7267 = 3.63$ — 룽게가 1901년에 적은 경계값 그대로다.

2.1. 언제 터지고 언제 안 터지나

거꾸로, 구간 전체에서 수렴하려면 특이점이 끝점 $\pm 1$ 을 지나는 등고선 바깥에 있어야 한다. 이 등고선은 허축을 $\pm 0.5255i$ 에서 지난다(럭비공 모양이라 흔히 “룽게 럭비공”이라 부른다). 따라서 $f_a(x) = 1/(1+a^2x^2)$ 의 극점 $\pm i/a$ 가 바깥에 있을 조건은

$$\frac1a > 0.5255 \quad\Longleftrightarrow\quad a < 1.903.$$

$1/(1+x^2)$ 을 $[-1,1]$ 에서 보간하면($a = 1$) 멀쩡하고, 같은 함수를 $[-5,5]$ 에서 하면($a = 5$) 터지는 이유가 이것이다. 함수가 “나빠서”가 아니라 구간 크기에 비해 특이점이 실축에 가까워서 터진다. 실수 위에서만 보면 이 함수에는 아무 흠도 없다 — 룽게 현상이 처음 보는 사람을 당황시키는 이유다.

3. 숫자로 — 이론과 부동소수점

바리센트릭 형식으로 배정밀도 보간한 최대 오차($[-1,1]$ 에서 20001 점 샘플). $a = 1.5$ 는 럭비공 바깥, $a = 2.5$·$5$ 는 안쪽이다.

$a$	절점	$n=10$	$n=20$	$n=40$	$n=60$
1.5	등간격	$1.6\times10^{-2}$	$2.2\times10^{-3}$	$7.3\times10^{-5}$	1.5
1.5	체비쇼프	$1.0\times10^{-3}$	$2.0\times10^{-6}$	$7.4\times10^{-12}$	$1.0\times10^{-15}$
2.5	등간격	0.25	0.60	6.3	72
5	등간격	1.9	60	$1.1\times10^{5}$	$3.0\times10^{8}$
5	등간격, $\lvert x\rvert<0.7$ 만	0.30	0.13	0.074	0.045
5	체비쇼프	0.11	$1.5\times10^{-2}$	$2.9\times10^{-4}$	$5.4\times10^{-6}$

세 가지가 보인다.

1. $a = 5$ 의 가운데 영역($|x| < 0.7$)은 정말로 수렴한다 — 다만 경계 0.7267 이 바로 옆이라 지수가 작아서 기어간다.
2. $a = 1.5$ 는 이론상 구간 전체에서 수렴해야 하는데, $n = 40$ 까지 잘 내려가다가 $n = 60$ 에서 오차 1.5 로 폭발한다. 이건 근사 이론이 아니라 반올림 문제다. 등간격 르베그 상수는 $\Lambda_n \sim 2^{n+1}/(e\,n\ln n)$ 로 자라서 $n = 60$ 이면 $10^{15}$ 대이고, 배정밀도 반올림 $10^{-16}$ 이 그대로 $O(1)$ 로 증폭된다. 해석적으로 안전한 함수도 등간격 고차 보간은 부동소수점이 죽인다.
3. 체비쇼프 절점은 $a = 5$ 에서도 $n=40$ 에 $2.9\times10^{-4}$ — 번스타인 타원 반지름 $\rho = 0.2 + \sqrt{1.04} \approx 1.22$ 에서 오는 예측 $\rho^{-n} \approx 3.5\times10^{-4}$ 와 자릿수가 맞는다.

4. 더 나쁜 소식들

• 번스타인(1912): $|x|$ 를 $[-1,1]$ 에서 등간격 보간하면 $x = -1, 0, 1$ 을 제외한 모든 점에서 발산한다. 해석성이 없으면 럭비공 논리조차 없다.
• 파버(1914): 절점 배치를 어떻게 정하든, 그 배치로는 균등 수렴하지 않는 연속함수가 반드시 존재한다. 체비쇼프 절점도 “모든 연속함수”에는 무력하다 — 다만 립시츠 연속만 돼도 수렴하니 실무에서 문제가 될 일은 거의 없다.
• 불가능성 정리(플라테·트레페텐·카위클라르스, 2011): 등간격 표본 $n$ 개에서 해석함수를 근사하는 방법이 기하급수로 수렴한다면, 그 방법은 반드시 기하급수로 나쁜 조건을 가진다. 안정한 방법이 낼 수 있는 최선은 $e^{-C\sqrt n}$ 의 근-지수(root-exponential) 수렴이다. 등간격 데이터만 주어진 상황에서는 원리적으로 공짜 점심이 없다는 뜻이다.¹

5. 처방 — 절점을 고를 수 있느냐 없느냐

절점을 고를 수 있으면: 체비쇼프(또는 르장드르·가우스-로바토) 절점을 쓴다. 끝에 점을 몰아 퍼텐셜 $\phi$ 를 구간 위에서 평평하게 만드는 것이 이 처방의 본질이다 — 평평하면 위의 “등고선 안팎” 문제가 사라진다. 스펙트럴 방법과 스펙트럴 요소법이 등간격이 아니라 로바토 절점을 쓰는 이유이고, 고차 유한요소의 요소 내부 절점이 같은 이유로 등간격을 피한다(삼각형·사면체에서는 페케테 점 같은 대안이 쓰인다).

등간격 데이터밖에 없으면(측정·실험·영상 데이터는 거의 다 그렇다):

• 차수를 낮춘 최소제곱. $m$ 개 점을 다 지나게 하지 말고 차수 $d \ll m$ 로 최소자승법 근사를 한다. 코퍼스미스-리블린(1992)·라흐마노프(2007)의 결과로 $d \lesssim \sqrt m$ 정도면 안정하다. $a = 5$ 에서 실측: $m = 100$ 점에 $d = 20$ 이면 $1.4\times10^{-2}$, $m = 1600$ 점에 $d = 80$ 이면 $1.0\times10^{-7}$. 수렴은 하지만 위 불가능성 정리대로 근-지수 속도다.
• 구간별 저차 다항식. 스플라인 보간은 차수를 3 에 묶고 구간을 쪼개므로 룽게 현상이 원천적으로 없다. CAD·애니메이션·표 보간의 기본값.
• 유리 보간. 플로터-호만(2007)의 바리센트릭 유리 보간은 등간격 절점에서도 극점이 생기지 않고 르베그 상수가 로그 정도로만 자란다.
• 목 체비쇼프(mock-Chebyshev): 촘촘한 등간격 격자에서 체비쇼프 절점에 가장 가까운 점들만 골라 보간한다. 데이터를 일부 버리는 대신 체비쇼프의 성질을 흉내낸다.

6. 다른 곳에 숨은 룽게

• 고차 뉴턴-코츠 적분. 등간격 보간 다항식을 적분하는 것이라 차수를 올리면 가중치에 음수가 섞이고 커진다(수치적분). 가우스·클렌쇼-커티스 구적이 이걸 피한다.
• 고차 유한차분 스텐실. 등간격 격자에서 스텐실 폭을 무작정 늘리면 계수 크기가 커지고 끝 경계 근처의 일방향 스텐실이 불안정해진다. 경계에서만 차수를 낮추는 이유 중 하나다.
• 깁스 현상과의 구분. 깁스 현상은 불연속 함수를 근사할 때 점프 근처에 약 9% 오버슈트가 남는 것이고, 차수를 올려도 사라지지 않지만 커지지도 않는다. 룽게 현상은 매끄러운 함수에서 끝이 발산한다. 둘 다 “고차 = 진동”이라 섞어 부르기 쉬운데 원인도 처방도 다르다.²
• 고차 다항식 회귀. 데이터 분석에서 등간격 시계열에 10차 다항식 추세선을 그었을 때 양 끝이 하늘로 솟는 것도 같은 집안이다. 외삽은 말할 것도 없다.³

7. 관련 문서

• 보간과 근사 · 체비쇼프 다항식 · 르베그 상수 · 스플라인 보간
• 깁스 현상 · 수치적분 · 클렌쇼-커티스 구적
• 스펙트럴 방법 · 스펙트럴 요소법 · 최소자승법
• 바리센트릭 보간

8. Footnotes

1. 이 정리가 나온 뒤로 “우리 방법은 등간격 데이터에서 지수 수렴하면서 안정하다”는 논문 초록을 보면 어디서 조건수를 숨겼는지 찾아보는 게 국룰이 됐다. 대개는 실험한 $n$ 이 작다. ↩

2. 시험 문제로 “룽게 현상과 깁스 현상의 차이를 서술하시오”가 나오면 “매끄러움 vs 불연속, 발산 vs 유계” 두 줄이면 만점이다. 이걸 헷갈리면 교수의 눈빛이 깁스 오버슈트만큼 차가워진다. ↩

3. 엑셀 추세선 옵션에서 다항식 차수를 6 까지만 허용하는 것이 우연인지 배려인지는 알 수 없지만, 결과적으로 수많은 보고서를 룽게로부터 구했다. ↩