구간 해석

1. 개요[편집]

구간 해석(interval analysis)은 수를 하나의 근사값이 아니라 참값을 반드시 품는 구간 $[\underline{x},\overline{x}]$ 로 다루고, 모든 연산이 그 포함 관계를 깨뜨리지 않도록 바깥쪽으로 반올림하며 계산하는 방식이다. 핵심 요구조건은 딱 한 줄, 포함 성질(inclusion property)이다.

$$X \circ Y \;\supseteq\; \{\, x \circ y \;:\; x \in X,\; y \in Y \,\}$$

부동소수점 연산이 “16자리쯤 맞을 것이다”라는 통계적 기대를 주는 데 반해, 구간 해석은 “정답은 무조건 이 상자 안에 있다”는 증명 가능한 진술을 준다. 대가는 구간이 자꾸 뚱뚱해진다는 것. 이 문서의 절반은 그 비만과 싸우는 이야기다.

무어(Ramon E. Moore)가 1962년 박사학위 논문과 1966년 저서 Interval Analysis 로 체계를 세웠고, 오늘날에는 정확 술어의 동적 필터, 분지한정법 기반 전역 최적화의 하계 계산, 그리고 컴퓨터 보조 증명이라는 세 곳에서 밥값을 한다.

2. 구간 산술의 규칙[편집]

사칙연산은 단조성에서 곧바로 나온다.

$$X + Y = [\underline{x}+\underline{y},\ \overline{x}+\overline{y}], \qquad X - Y = [\underline{x}-\overline{y},\ \overline{x}-\underline{y}]$$

곱셈은 네 끝점 곱의 최소·최대, 나눗셈은 $0 \notin Y$ 일 때 $X \times [1/\overline{y}, 1/\underline{y}]$ 다. $Y$ 가 0을 품으면 결과가 두 개의 반직선으로 쪼개지는 확장 구간 나눗셈이 되는데, 이게 쓰레기가 아니라 오히려 뒤에 나올 구간 뉴턴법의 핵심 도구다.

여기서 타협 불가능한 것이 방향 반올림(directed rounding)이다. 하한은 $-\infty$ 쪽으로, 상한은 $+\infty$ 쪽으로 반올림해야 포함 성질이 유지된다. 다행히 IEEE 754는 최근접-짝수 말고도 $\pm\infty$ 방향과 0 방향 반올림 모드를 표준으로 요구하므로, 하드웨어를 새로 살 필요는 없다. 문제는 소프트웨어 쪽이다. 컴파일러가 -ffast-math 로 결합법칙을 마음대로 쓰거나, 중간 결과를 확장 정밀도 레지스터에 남겨 두거나, 벡터화하면서 반올림 모드 설정을 무시하면 포함 보장이 조용히 증발한다. 구간 라이브러리가 유난히 컴파일 옵션에 예민한 이유다.¹

3. 의존성 문제 — 같은 변수는 두 번 나오면 안 된다[편집]

구간 산술이 실패하는 첫 번째 지점은 정확도가 아니라 표현이다. 구간 연산은 피연산자끼리 독립이라고 가정하므로, 같은 변수가 식에 여러 번 나타나면 그 상관관계를 잃어버린다. $X = [-1, 1]$ 에 대해

$$X - X = [-2, 2] \neq [0,0], \qquad X \times X = [-1, 1] \neq [0, 1]$$

가 되는 것이 대표적이다. 뒤엣것 때문에 제대로 된 라이브러리는 곱셈과 별개로 전용 제곱 연산 sqr을 제공한다. 이 현상을 의존성 문제(dependency problem)라 하고, 계산 결과의 과대평가를 부르는 주범이다.

실무적 대응은 세 가지다. 첫째, 식을 다시 쓴다. $x(1-x)$ 보다 $\tfrac14 - (x-\tfrac12)^2$ 가, 다항식은 호너 형태가 대개 좁은 구간을 준다. 수학적으로 같은 식이 수치적으로 전혀 다른 답을 준다는 점에서, 같은 문제라도 어떤 알고리즘을 고르느냐로 정확도가 갈리는 조건수 이야기와 정확히 같은 정신이다. 둘째, 정의역을 잘게 쪼갠다. 셋째, 아예 상관관계를 들고 다니는 산술로 갈아탄다(아래 아핀 산술).

4. 감싸기 효과[편집]

두 번째 실패 지점은 시간 적분에서 나온다. 초기 조건 상자를 룽게-쿠타법 같은 적분기로 전진시키면, 상자는 회전하고 늘어나 평행사변형이 된다. 그런데 구간 벡터는 축에 평행한 상자만 표현할 수 있으므로 매 스텝 그것을 다시 축평행 상자로 감싸야 하고, 그때마다 부피가 늘어난다. 이 손실이 스텝마다 곱해지면서 지수적으로 폭발하는 것이 감싸기 효과(wrapping effect)다.² 45도 회전만 반복해도 스텝당 $\sqrt2$ 배씩 늘어난다고 생각하면 감이 온다.

대응책은 좌표계를 상자에 맞추는 것이다. 로너(Lohner)의 QR 기반 방법은 매 스텝 오차 전파 행렬을 QR 분해해 직교 기저를 따라가는 상자로 표현을 바꿔 감싸기를 억제한다. CAPD 같은 엄밀 ODE 적분 패키지의 뼈대가 이것이다.

5. 세분하면 얼마나 좁아지는가[편집]

구간이 얼마나 부푸는지는 정량화가 된다. 함수 $f$ 의 자연 구간 확장(식의 연산을 그대로 구간 연산으로 바꾼 것) $F(X)$ 는 참 치역 $f(X)$ 를 포함하고, 초과 폭은 구간 폭 $w(X)$ 에 1차로 비례한다. 반면 평균값 형식

$$f(X) \subseteq f(m) + F'(X)\,(X - m), \qquad m = \mathrm{mid}(X)$$

의 초과 폭은 $O(w(X)^2)$ 다. 그래서 $X$ 를 $n$ 조각으로 나눠 합집합을 취하면, 자연 확장은 $O(1/n)$, 평균값 형식은 $O(1/n^2)$ 로 참 치역에 수렴한다. 세분은 언제나 이기지만, 좋은 형식을 고르면 훨씬 빨리 이긴다가 무어 이론의 요약이다. 참고로 $F'(X)$ 는 손으로 미분할 필요 없이 자동 미분을 구간 산술 위에서 돌리면 그대로 나온다 — 두 기법의 궁합이 좋은 이유다.

6. 검증된 계산 — 근의 존재를 증명하기[편집]

구간 해석이 단순한 오차 봉투 계산과 갈라지는 지점이 여기다. 1변수 구간 뉴턴법은 $0 \notin F'(X)$ 일 때

$$N(X) = m - \frac{f(m)}{F'(X)}, \qquad m = \mathrm{mid}(X)$$

를 정의하는데, 평균값 정리 덕분에 $X$ 안의 모든 근은 $N(X)$ 안에도 있다. 여기서 두 가지 결론이 컴퓨터의 유한한 계산만으로 따라 나온다.

• $N(X) \cap X = \emptyset$ 이면 → $X$ 안에 근이 없다(존재하지 않음의 증명).
• $N(X) \subseteq X$ 이면 → $X$ 안에 근이 정확히 하나 존재한다(존재와 유일성의 증명). 이후 반복은 뉴턴-랩슨법처럼 2차 수렴한다.

다변수로 넘어가면 구간 행렬의 역행렬이 골치라, 크라브칙(Krawczyk, 1969) 연산자를 쓴다. $Y$ 를 $F'(m)$ 의 근사 역행렬(보통의 부동소수점으로 구해도 된다)로 두고

$$K(X) = m - Y f(m) + \big(I - Y\,F'(X)\big)(X - m)$$

를 계산했을 때 $K(X) \subseteq \mathrm{int}\,X$ 이면, 브라우어 고정점 정리에 의해 $X$ 안에 $f$ 의 영점이 존재하고 유일하다. 역행렬을 구간으로 뒤집을 필요가 없다는 게 실용적 승부처다. 이 판정을 자동으로 돌려 주는 것이 룸프(Rump)의 INTLAB verifynlss 계열이며, “수치해로 나온 답이 진짜 해 근처인지”를 사후에 검증하는 표준 도구가 됐다.

이 기법으로 굴러간 대표적 증명들:

• 란포드(1982) — 파이겐바움 재규격화 사상의 고정점 존재를 구간 산술로 증명. 컴퓨터 보조 증명의 원형.
• 헤일스(1998) — 케플러 추측(구 쌓기). 구간 산술과 선형계획 하계를 조합했고, 심사에 몇 년이 걸린 끝에 2014년 형식 증명(Flyspeck)으로 마무리됐다.
• 터커(2002) — 로렌츠 방정식의 끌개가 진짜 쌍곡 이상끌개임을 증명해 스메일의 14번 문제를 해결. 스메일 말굽의 덮음 관계를 구간으로 확인하는 방식은 이후 이 분야 표준 문법이 됐다.

7. 의존성을 줄이는 무기[편집]

7.1. 아핀 산술[편집]

콤바와 스톨피(1993)의 아핀 산술(affine arithmetic)은 값을 구간이 아니라 잡음 기호의 1차식으로 들고 다닌다.

$$\hat{x} = x_0 + \sum_{i=1}^{n} x_i \varepsilon_i, \qquad \varepsilon_i \in [-1,1]$$

덧셈·뺄셈·스칼라배는 기호 계수끼리 그대로 처리되므로 $\hat{x} - \hat{x} = 0$ 이 정확히 성립한다. 의존성 문제의 정면 해결책인 셈. 대신 곱셈·나눗셈 같은 비선형 연산마다 새 잡음 기호가 하나씩 생겨 항의 개수가 늘어나므로, 주기적으로 작은 항들을 하나로 뭉치는 압축(condensation)이 필요하다.

7.2. 테일러 모형[편집]

베르츠와 마키노의 테일러 모형(Taylor model)은 함수를 다항식 $P$ + 구간 나머지 $I$ 로 표현한다. 정의역 폭 $w$ 에 대해 나머지가 $O(w^{n+1})$ 로 줄어들므로 고차로 갈수록 급격히 좁아지고, 다항식 부분이 변수 간 상관을 통째로 기억하므로 감싸기 효과에도 강하다. COSY INFINITY로 소행성 궤도나 가속기 빔의 장시간 거동을 엄밀하게 감싸는 계산이 이 계열이다. 값은 비싸다 — 다변수 다항식 산술이니 항 수가 차수와 차원에 따라 폭발한다.

8. 현실 — 어디에 쓰고 어디에 안 쓰는가[편집]

• 비용. 연산당 2~4배는 기본이고, 반올림 모드를 오가면 파이프라인이 꼬여 더 느려질 수 있다. 그래서 코드 전체를 구간으로 돌리는 대신 작고 결정적인 커널에만 쓴다. 정확 술어에서 구간이 0을 걸칠 때만 정확 산술로 내려가는 필터 구조가 전형적이다.
• 분기. 구간에는 전순서가 없다. if (x > 0) 이 참도 거짓도 아닌 경우가 생기며, 이때 양쪽을 다 따라가거나 구간을 쪼개야 한다. 알고리즘을 그대로 옮기면 안 되는 이유.
• 큰 계는 못 버틴다. 자유도 수십만짜리 유한요소법 모델을 구간으로 풀면 의존성과 감싸기가 겹쳐 결과 구간이 “아마도 $[-\infty, \infty]$” 수준으로 무의미해진다. 강건 설계에서 구간을 쓸 때 부분 구조나 축소 모델로 내려가는 것이 그 때문이다.
• 최악값이지 확률이 아니다. 구간은 분포를 모르는 인식론적 불확실성에 어울리는 표현이고, 확률적 전파는 몬테카를로 방법·다항식 카오스 전개의 몫이다. 불확실성 정량화에서 둘을 섞어 쓰는 확률-상자(p-box) 접근도 여기서 나온다.
• 표준과 도구. 2015년 IEEE Std 1788로 구간 산술의 의미론이 표준화됐다. 구현은 INTLAB(MATLAB), C-XSC, Boost.Interval, MPFI, CAPD(동역학), COSY INFINITY(테일러 모형), Julia의 IntervalArithmetic.jl 등이 있고, 중심-반지름 표현을 쓰는 Arb 계열의 구(ball) 산술도 사실상 같은 가족이다.³

한 줄로 정리하면, 구간 해석은 전역 최적화와 정리 증명이 필요한 자리에서만 값을 하는 비싼 보험이다. 잔차가 $10^{-12}$ 로 떨어졌다고 안심하는 대신 “그래서 진짜 해가 있긴 하냐”를 묻고 싶을 때, 이 도구가 대답할 수 있는 유일한 도구다.

9. 관련 문서[편집]

• 부동소수점 연산 · 조건수 · 정확 술어
• 뉴턴-랩슨법 · 자동 미분 · 분지한정법
• 로렌츠 방정식 · 스메일 말굽 · 룽게-쿠타법
• 강건 설계 · 불확실성 정량화 · 검증 및 확인

10. Footnotes[편집]

1. 그래서 구간 라이브러리 문서 첫 페이지에는 “이 최적화 플래그를 켜지 마시오” 목록이 붙어 있다. 성능을 위해 켠 플래그가 증명을 무효화한다는 건 꽤 킹받는 구도인데, 컴파일러 입장에서는 “수학적으로 같은 식”이니 억울할 것도 없다. 결국 표준 준수 모드로 컴파일하고 느린 걸 감수하는 게 국룰. ↩

2. 국내 문헌에서는 “포장 효과”로도 옮긴다. 어느 쪽이든 상자를 다시 상자로 싸느라 부피가 늘어난다는 그림은 같다. 선형계에서는 회전 행렬을 알고 있으니 이론상 회피가 가능하지만, 비선형계에서는 매 스텝 새로 싸는 수밖에 없다. ↩

3. 구간(하한·상한)과 구(중심·반지름)는 표현만 다르고 목적은 같다. 다중정밀도에서는 반지름을 낮은 정밀도로 저장할 수 있어 구 쪽이 메모리에서 유리해, 해석적 수론 계산 같은 고정밀 분야는 대부분 구 산술로 넘어갔다. ↩