제1부 수학적 기초

1.22 구간 해석과 집합 기반 추정: 구간 연산·수축자·보장된 위치추정

1.22.1 이 장에서 배우는 것 / 선수 지식 / 특히 중요한 독자

이 장은 측정 오차를 확률분포가 아닌 크기의 한계로 가정하고, 그 가정 아래 상태가 놓일 수 있는 집합 전체를 계산하는 구간 해석(interval analysis)과 집합 기반 추정을 다룬다. 결과는 가정이 성립하는 한 참값을 반드시 포함하는 상자(box)의 목록이며, 계산 중의 부동소수점 반올림까지 보장에 포함한다. 다룰 질문은 다섯 가지다. 구간 산술은 어떤 연산으로 이루어지며 같은 변수가 여러 번 나타나면 결과가 왜 과대 평가되는가, 평균값 형식과 분할은 과대 평가를 어떻게 줄이는가, 수축자와 집합 반전(SIVIA)은 비선형 조건을 만족하는 집합을 어떻게 상자로 구하는가, 이상치가 있을 때 q-릴랙스 교집합은 무엇을 보장하고 무엇을 포기하는가, 한계 오차 가정과 가우시안 가정은 어디에서 갈리는가.

배우는 것:

• 구간 산술과 과대 평가 — 포함 함수, 종속성 문제, 자연 포함 함수·평균값 형식·분할의 수렴 차수.
• 수축자와 집합 반전 — 전방-후방 전파(HC4), 뉴턴 구간 수축자, SIVIA, 거리 측정만으로 하는 보장된 위치추정.
• 이상치와 가정의 비교 — q-릴랙스 교집합, 한계 오차 대 가우시안, 가정이 어긋날 때의 실패 방식.
• 바깥 반올림 — 부동소수점에서의 보장과 그 한계.
• 라이브러리 확인 — mpmath·python-flint·pyinterval·codac과 같은 입력으로 비교.

선수 지식: 1.1(행렬 분해), 1.12(비선형 최소제곱), 1.19(확률변수·가우시안). 부동소수점 오차 일반은 1.18, 칼만·베이즈 필터는 9.1·9.3, 파티클 필터는 9.5, 위치추정 무결성은 9.25가 다룬다.

특히 중요한 독자: 위치·상태 오차의 상한을 증명해야 하는 엔지니어, 이상치가 흔한 환경(실내 측위·수중 음향 측위)의 연구자, 검증 가능한 추정 소프트웨어를 구현하는 개발자.

출처 방침. 서지는 Crossref 응답으로 확인했다(목록은 이 장 끝). 직접 읽은 자료: ① codac 저장소 codac2 브랜치의 codac2_CtcQInter.h·.cpp, codac2_CtcInverse.h, codac2_pave.h·.cpp, codac2_Paving.h, codac2_Interval.h(포함 파일 목록), ② mpmath의 ctx_iv.py(반올림 지정 부분), ③ pyinterval의 fpu.py(머리말과 up·down), ④ python-flint 0.9.0의 arb 문서 문자열. 직접 실행한 것: mpmath 1.4.1·python-flint 0.9.0·pyinterval 1.2.0(crlibm 확장 없이)·codac 2.1.2(Python 3.12.3, 2026-11-03; codac은 의존 패키지 vibes의 휠이 없어 --no-deps로 설치). 읽지 못한 것: 인용한 교과서·논문의 본문(정리 번호는 (확인 필요)), IEEE 1788의 본문. 이 장의 수치는 표준 라이브러리만 사용한 순수 파이썬 구현으로 계산했고, 가우스-뉴턴은 1.12의 구현을 불러와 사용했다.

1.22.2 개념 — 한계 오차 가정과 참값을 포함하는 집합

거리 센서의 사양이 "참 거리와의 차이가 $\epsilon$ 이하"라는 한계만 보증한다고 하자. 측정값 $d_i$ 하나는 표지 $a_i$ 둘레의 폭 $2\epsilon$인 환형(annulus) 조건 $\lVert p-a_i\rVert\in[d_i-\epsilon,\,d_i+\epsilon]$을 준다. 표지 여러 개의 환형을 교집합하면 로봇이 있을 수 있는 영역이 남고, 이 영역이 해 집합이다. 가정이 성립하면 참 위치는 해 집합 안에 있으므로 해 집합은 점 추정값 대신 위치의 보장된 범위로 사용된다.

두 접근이 제공하는 결론의 종류가 다르다. 확률 모델(1.19)은 오차의 분포를 가정하고 "참값이 이 타원 안에 있을 확률이 95%"라는 통계적 결론을 낸다. 구간 모델은 분포를 가정하지 않고 크기의 한계만 가정하며(미지이지만 한계가 있는 오차, unknown-but-bounded; Schweppe 1968) "한계가 맞으면 참값은 이 집합 안에 있다"는 결론을 낸다. 앞의 결론은 한계가 없는 오차에도 적용되고, 뒤의 결론은 한계가 깨지면 성립하지 않는다.

이 장은 해 집합을 계산하는 네 가지 도구를 정리한다. ① 구간 산술은 함수의 값 범위를 상자로 포함한다(포함 함수). ② 수축자는 조건을 만족할 수 없는 부분을 상자에서 제거한다. ③ SIVIA는 상자를 이등분(분기)하고 판정(한정)해 해 집합을 안쪽 상자와 경계 상자의 합집합으로 구한다. ④ 모든 연산을 바깥으로 반올림해 부동소수점 오차가 보장을 깨지 않게 한다.

1.22.3 원리

1.22.3.1 구간 산술과 포함 함수

결론: 구간 산술은 실수 연산을 구간 끝점의 연산으로 바꾸어, 입력이 구간 안의 어떤 값이어도 결과가 반환된 구간 안에 있음을 보장한다. 보장은 항상 성립하지만 반환된 구간이 실제 값의 범위보다 넓을 수 있다.

구간 $[x]=[\underline x,\overline x]$의 연산 $[x]\circ[y]$는 $\{x\circ y\mid x\in[x],\,y\in[y]\}$를 포함하는 최소 구간이다.

$$[x]+[y]=[\underline x+\underline y,\ \overline x+\overline y],\qquad [x]-[y]=[\underline x-\overline y,\ \overline x-\underline y]$$

$$[x]\cdot[y]=\bigl[\min\{\underline x\underline y,\underline x\overline y,\overline x\underline y,\overline x\overline y\},\ \max\{\underline x\underline y,\underline x\overline y,\overline x\underline y,\overline x\overline y\}\bigr]$$

나눗셈은 $0\notin[y]$일 때 $[x]\cdot[1/\overline y,\,1/\underline y]$이다. $0\in[y]$이면 결과가 두 구간의 합집합이 되며(확장 나눗셈) 이 장은 구현하지 않는다. 제곱은 곱과 다르다. $\underline x<0<\overline x$이면 $[x]^2=[0,\max(\underline x^2,\overline x^2)]$이지만 $[x]\cdot[x]$의 하한은 음수이다. 상자 $[\mathbf x]=[x_1]\times\cdots\times[x_n]$은 구간의 곱집합이다.

함수 $f$의 포함 함수(inclusion function) $[f]$는 모든 상자에서 값 범위 $f([\mathbf x])=\{f(x)\mid x\in[\mathbf x]\}\subseteq[f]([\mathbf x])$를 만족한다. 사칙과 초등 함수로 이루어진 식의 변수·연산을 구간·구간 연산으로 바꾼 자연 포함 함수(natural inclusion function)는 구간 산술의 포함 단조성에서 이 성질을 얻는다(Moore 1966; 정리 번호는 (확인 필요)). 컴퓨터에서는 끝점 연산도 바깥으로 반올림해야 성립한다(1.22.3.7).

1.22.3.2 종속성 문제와 과대 평가

결론: 같은 변수가 식에 두 번 이상 나타나면 구간 산술은 각 출현을 서로 독립인 값으로 취급해 결과를 넓힌다. 구간의 반폭 $w$가 줄면 과대 평가도 줄지만, 자연 포함 함수에서는 $w$에 비례하고 평균값 형식에서는 $w^2$에 비례해 줄어든다.

$x-x$에서 $[x]-[x]=[-2w,2w]$($2w$는 $[x]$의 폭)이고 참값은 0이다. 두 출현이 같은 $x$임을 구간 산술이 알지 못하기 때문이며, 이를 종속성 문제(dependency problem)라 한다. 결과와 참 값 범위의 폭 차이가 과대 평가(overestimation)이다. 같은 식을 $x$가 한 번만 나타나게 재작성하면 정확해진다. $x^2-2x=(x-1)^2-1$이 그 예이다.

재작성이 불가능하면 평균값 형식(mean-value form)을 사용한다. $f$가 미분 가능하면 임의의 $c\in[x]$에 대해 평균값 정리에서 다음이 성립한다.

$$f([x])\subseteq f(c)+[f']([x])\,\bigl([x]-c\bigr)$$

$[f']([x])$와 $[x]-c$의 폭이 모두 $w$에 비례하므로 그 곱에서 생기는 과대 평가는 $w^2$에 비례한다(Moore 1966; Neumaier 1990; 정리 번호는 (확인 필요)). $[f']([x])$가 0을 포함하는 넓은 구간에서는 이 이점이 작다.

1.22.3.3 상자와 값 범위: 분할과 래핑 효과

결론: 입력 상자를 $k$등분해 각 조각의 포함 함수를 합집합하면 값 범위의 포함이 정확해지고, 과대 평가는 자연 포함 함수에서 $1/k$, 평균값 형식에서 $1/k^2$로 줄어든다. 비용은 차원 $n$에서 $k^n$으로 늘어난다.

값 범위의 최솟값·최댓값은 분할과 한정으로 구한다. 한 조각의 포함 함수 하한이 지금까지 얻은 최소값의 상계보다 크면 그 조각에는 최솟값이 없으므로 버린다. 구간 전역 최적화가 이 방식이다(Hansen·Walster (확인 필요: 판·장)). SIVIA(1.22.3.5)는 같은 분할·한정 구조에서 값 범위 대신 조건의 만족 여부를 판정한다.

동적 시스템에서는 종속성이 시간 방향으로 누적된다. 상자를 선형 변환 $x_{k+1}=Rx_k$로 전파하면 회전한 집합을 다시 축 정렬 상자로 포함해야 하므로 변환마다 폭이 커진다(래핑 효과, wrapping effect). 한 변 0.2의 상자를 10도씩 36회 회전하면 참 집합은 원래 상자와 같지만 상자 산술의 한 변은 39.9이다(1.22.5 ①). 상태 전파의 구간 방법은 평행육면체 같은 비축 정렬 표현을 필요로 하며 이 장은 다루지 않는다.

1.22.3.4 수축자와 전방-후방 전파

결론: 수축자(contractor)는 상자를 입력받아 조건을 만족하는 점을 하나도 잃지 않고 더 작은 상자를 반환하는 연산자이다. 수축자로 해가 없는 부분을 먼저 제거하면 분할만 사용할 때보다 상자 평가 횟수가 줄어든다.

제약 $f(x)\in[\mathbf y]$의 수축자 $\mathcal C$는 $\mathcal C([\mathbf x])\subseteq[\mathbf x]$(수축)이고 $\{x\in[\mathbf x]\mid f(x)\in[\mathbf y]\}\subseteq\mathcal C([\mathbf x])$(해의 보존)를 만족한다(Chabert와 Jaulin 2009).

전방-후방 전파(HC4)는 식의 계산 트리를 이용한다. 전방 단계는 각 노드의 구간을 구간 산술로 계산하고 루트 구간을 $[\mathbf y]$와 교차한다. 후방 단계는 각 연산의 역연산으로 자식 노드의 구간을 교차해 수축한다. 거리 제약 $\sqrt{(x-a_1)^2+(y-a_2)^2}\in[d]$에서는 $u=x-a_1$, $v=y-a_2$, $s=u^2$, $t=v^2$, $q=s+t$, $r=\sqrt q$로 두고, 후방에서 $r\leftarrow r\cap[d]$, $q\leftarrow q\cap r^2$, $s\leftarrow s\cap(q-t)$, $t\leftarrow t\cap(q-s)$, $u\leftarrow u\cap(\pm\sqrt s)$, $v\leftarrow v\cap(\pm\sqrt t)$를 적용한다. $\pm\sqrt s$는 두 조각의 합집합이므로 두 교차 결과의 포함 구간을 취한다. 각 변수가 식에 한 번만 나타나면 전파 한 번이 변수별 최대 수축을 주고 (확인 필요: 정리 번호), 여러 번 나타나면 전파를 반복해도 선형 수렴에 머문다(1.22.5 ②).

뉴턴 구간 수축자. 스칼라 함수 $f$의 영점 $x^*\in[x]$는 평균값 정리에 의해 임의의 $c\in[x]$에서 $x^*\in c-f(c)/[f']([x])$를 만족한다. 따라서 $0\notin[f']([x])$이면 다음이 수축자이고 영점 근방에서 이차 수렴한다(Neumaier 1990; 정리 번호는 (확인 필요)).

$$[x]\leftarrow[x]\cap\Bigl(c-\frac{f(c)}{[f']([x])}\Bigr)$$

$0\in[f']([x])$이면 확장 나눗셈으로 결과가 두 구간이 되어 분할과 함께 사용한다. 다변수 형태(구간 가우스-자이델·크라보비치)는 이 장에서 구현하지 않았다.

1.22.3.5 집합 반전(SIVIA)과 보장된 위치추정

결론: 집합 반전은 제약 $f(x)\in[\mathbf y]$을 만족하는 집합 $\mathbb X=f^{-1}([\mathbf y])$를 상자의 합집합으로 안과 밖에서 동시에 근사한다. 안쪽 상자의 합집합은 $\mathbb X$의 부분집합이고 안쪽과 경계 상자의 합집합은 상위 집합이므로 면적의 하한과 상한이 함께 얻어진다.

SIVIA(set inversion via interval analysis; Jaulin과 Walter 1993)는 탐색 상자에서 시작해 상자마다 세 가지로 판정한다. $[f]([\mathbf x])\subseteq[\mathbf y]$이면 안쪽 상자, $[f]([\mathbf x])\cap[\mathbf y]=\emptyset$이면 제외, 그렇지 않으면 가장 넓은 변이 분해능 $\delta$ 이상일 때 이등분해 다시 판정한다. 폭이 $\delta$ 미만으로 남은 상자가 경계 상자이다. codac의 sivia는 수축 없이 이 판정과 분할만 수행하며(소스 확인), 수축자는 평가 횟수를 줄이기 위해 더한다.

거리 측정 위치추정은 이 구조에 그대로 들어맞는다. 표지 $a_i$까지의 측정 $d_i$와 오차 한계 $\epsilon$이 제약 $\lVert p-a_i\rVert\in[d_i-\epsilon,\,d_i+\epsilon]$, $i=1,\dots,m$을 이룬다. 모든 오차가 $\lvert e_i\rvert\le\epsilon$이면 참 위치 $p^*$가 $\mathbb X$에 속하므로 결과 상자 목록이 $p^*$를 포함한다. 이 포함은 확률이 아니라 한계 가정이 성립하는 모든 경우의 성질이다. 방위각 측정의 집합은 표지에서 뻗는 쐐기이며 같은 방식으로 구하지만 삼각 함수의 구간 계산이 필요하므로 이 장은 거리 측정만 구현했다(1.22.10). 분해능 $\delta$는 경계 상자의 크기이며 바깥 면적이 참 면적을 넘는 정도를 정한다.

1.22.3.6 이상치 허용: q-릴랙스 교집합

결론: 측정 $m$개 가운데 최대 $q$개가 이상치일 수 있다고 가정하면 해 집합은 $m-q$개 이상의 제약을 만족하는 점의 집합이다. 이상치 수가 $q$ 이하이면 참값을 포함하지만, $q$가 클수록 집합이 커지고 서로 떨어진 허위 집합이 나타난다.

집합 $X_1,\dots,X_m$의 q-릴랙스 교집합은 $m-q$개 이상에 속하는 점의 집합이다. $q=0$이면 일반 교집합이다. 일반 교집합은 이상치가 하나만 있어도 공집합이 될 수 있다. q-릴랙스 교집합은 어느 측정이 이상치인지 구분하지 않고도 정상 측정 $m-q$개 이상의 교집합을 부분집합으로 포함한다. 상자 수축은 각 제약의 수축 결과 $\mathcal C_i([\mathbf x])$를 따로 구한 뒤, 좌표마다 구간 $m$개 중 $m-q$개 이상에 속하는 점들의 포함 구간을 취한다. 끝점을 정렬하면 좌표당 $O(m\log m)$이다. 같은 방식이 codac의 CtcQInter(q는 위반해도 되는 제약의 최대 수)에 구현되어 있다(소스 확인). 1차원 구간 융합의 같은 문제는 Marzullo(1990)가, 로봇 상태추정에의 적용은 Jaulin(2009)이 다루었다 (확인 필요: 본문 미확인). 좌표별 포함은 정확한 q-릴랙스 교집합의 포함 상자 이상이므로 과대 근사이다.

1.22.3.7 부동소수점의 보장: 바깥 반올림

결론: 구간의 하한은 아래로, 상한은 위로 반올림해야 부동소수점 계산에서도 포함이 성립한다. 최근접 반올림만 사용하면 실수 참값을 포함하지 못하는 구간이 생기고, 그러면 해 집합이 참값을 잃을 수 있다.

IEEE 754는 방향 반올림을 정의하지만(IEEE 754-2019; 조항은 (확인 필요)) 파이썬에서 반올림 모드를 전환하는 방법은 이식성이 낮다. 이 장은 math.nextafter로 최근접 반올림 결과를 한 단계(1 ulp) 바깥으로 옮긴다. 사칙 연산과 제곱근은 최근접 반올림의 오차가 0.5 ulp 이하이므로 한 단계 바깥은 실수 결과를 포함하고, 정확한 방향 반올림보다 연산당 최대 1 ulp 넓은 구간이 된다. 방향 반올림 모드에서도 오차가 1 ulp 미만이므로 같은 이동이 포함을 유지하며, 이 장의 구현은 네 가지 반올림 모드에서 입력 20000쌍의 유리수 정확 결과를 모두 포함했다(1.22.5 ⑦). 이 방법은 오차가 1 ulp 미만임이 보장되는 연산에만 성립하므로 사인·아크탄젠트 같은 초월 함수의 라이브러리 구현에는 사용할 수 없다. 이 장의 코드는 초월 함수를 사용하지 않는다. 십진 상수는 이진 근사값의 양쪽 한 단계 구간으로 변환해야 실수 상수를 포함한다. 구간 산술의 표준은 IEEE 1788-2015이며 상세 조항은 확인하지 못했다 (확인 필요). 부동소수점 계산으로 엄밀한 결과를 얻는 방법 일반은 Rump(2010)가 정리했다.

1.22.3.8 확률적 방법과의 가정 비교

결론: 구간 방법은 오차 크기의 한계만 가정하고 한계가 성립하면 참값 포함을 보장한다. 가우시안 방법은 분포의 형태를 가정하고 통계적 포함 확률을 제공한다. 두 결론은 서로 다른 가정에서 나오므로 한쪽이 다른 쪽을 대체하지 않으며, 가정이 어긋날 때 구간 방법은 급격히, 가우시안 방법은 완만하게 나빠진다.

비선형 최소제곱의 해 $\hat x$와 공분산 $\sigma^2(J^\top J)^{-1}$(1.12·1.19)에서 마할라노비스 타원 $d^2\le\chi^2_2(0.95)=5.99$가 참값을 포함할 확률은 선형화가 맞고 오차가 가우시안이며 $\sigma$가 맞을 때 약 95%이다. 구간 방법의 해 집합은 모든 측정의 오차가 한계 안에 있을 때에만 참값을 포함한다. 실제 오차가 $[-\kappa\epsilon,\kappa\epsilon]$의 독립 균일이고 가정한 한계가 $\epsilon$($\kappa>1$)이면 $m$개 측정이 모두 한계 안일 확률은 $\kappa^{-m}$이므로 $m=4$에서 해 집합의 참값 포함 확률은 $\kappa^{-4}$이다. $\kappa=1.2$에서 0.482, $\kappa=2$에서 0.0625로 $\kappa$가 1을 조금만 넘어도 빠르게 떨어진다. 더 나아가 한계 위반이 있어도 해 집합이 비어 있지 않은 채 참값을 놓칠 수 있어 위반이 드러나지 않는다(1.22.5 ⑥). 추정량의 이론적 정확도 한계(크라메르-라오)는 1.20이, 베이즈 필터는 9.1가 다룬다.

1.22.4 알고리즘

ctc_dist(상자 [x]×[y], 표지 a, 구간 d):
  u ← [x]−a1 ; v ← [y]−a2 ; s ← u² ; t ← v² ; q ← s+t        (전방)
  q ← q ∩ ([d]∩[0,∞))² ; s ← s ∩ (q−t) ; t ← t ∩ (q−s)        (후방)
  u ← hull(u∩(+√s), u∩(−√s)) ; v ← hull(v∩(+√t), v∩(−√t))
  [x] ← [x]∩(u+a1) ; [y] ← [y]∩(v+a2) ; 어느 교집합이든 비면 ∅

qhull(구간 목록, k): 끝점을 정렬(같은 좌표에서는 여는 끝점이 먼저)해 겹친 구간 수를
  세고, 겹침이 k 이상인 끝점의 최소·최대 좌표를 반환(없으면 ∅)

sivia(탐색 상자, 제약 {(a_i, d_i)}, δ, q):
  스택 ← {탐색 상자}
  while 스택: b ← pop
    if (b 전체가 만족하는 제약 수) ≥ m−q:  안쪽 목록에 b ; continue
    각 제약으로 b 를 수축(빈 결과 제외) ; 남은 결과가 m−q 개 미만이면 b 버림
    b ← 좌표별 qhull(수축 결과, m−q)
    if b 의 최대 폭 < δ:  경계 목록에 b
    else:  가장 넓은 변으로 b 를 이등분해 스택에 추가
  return 안쪽 목록, 경계 목록

구현은 1.22.5의 코드에 있고, 뉴턴 수축자는 newton이다.

1.22.5 풀이 예제 — 종속성·수축자·집합 반전·이상치·가정 위반과 라이브러리 확인

구간 산술을 직접 구현해 종속성 문제와 과대 평가를 측정하고 평균값 형식과 분할로 줄어드는 과정을 보인다. HC4와 뉴턴 수축자를 비교한 뒤, 거리만 측정하는 2차원 위치추정에서 SIVIA의 해 집합 면적과 참값 포함을 검증한다. 이어서 바깥 반올림, 이상치와 q-릴랙스 교집합, 한계 오차 가정의 위반을 가우스-뉴턴·타원과 비교하고 라이브러리와 대조한다. 결론부터 적으면 다음과 같다. ① $x^2-2x$의 자연 포함 함수는 $[0,3]$에서 $[-6,9]$(폭 15)로 참 범위 $[-1,3]$(폭 4)의 3.75배이고, $x$를 한 번만 사용한 재작성은 $[-1,3]$으로 정확하다. $[2-w,2+w]$에서 과대 평가는 자연 포함 함수가 $8w$, 평균값 형식이 $4w^2$이며 $w=1/32$에서 0.2500 대 0.00391이다. ② 변수가 두 번 나타나는 $x^2-2x=1$에서 HC4는 반복마다 폭이 약 0.414배로 줄어 폭 $10^{-12}$ 미만에 32회, 뉴턴 수축자는 4회에 이른다. ③ 표지 4개, 한계 0.2 m에서 SIVIA(분해능 0.02 m)는 안쪽 78개·경계 102개 상자를 363회 평가해 구했고(수축자 없이는 597회) 안쪽 0.1337 m² ≤ 참 0.1475 m² ≤ 바깥 0.1538 m²이며 참값을 포함한다. ④ 바깥 반올림이 없으면 $0.1+0.2$·$\sqrt2\cdot\sqrt2$·$10\times0.1$의 결과 모두 실수 참값을 제외했고 바깥 반올림 구간은 모두 포함했다. ⑤ 이상치 1개에서 일반 교집합은 300회 모두 공집합이었고 $q=1$ 해 집합은 모두 참값을 포함했다(면적 중앙값 0.153 m²). 표지 6개·이상치 2개에서 $q=2$도 모두 포함했고 $q=1$이면 99.0%가 공집합이었다. ⑥ 한계 가정이 성립하면 참값 포함 비율이 구간 1.000, 가우스-뉴턴 95% 타원 0.984이다. 실제 오차 한계가 가정의 1.5배이면 구간 0.186(해석값 $1.5^{-4}=0.198$), 타원 0.672이고, 구간 결과의 12.6%만 공집합으로 위반이 드러났으며 68.8%는 공집합이 아니면서 참값을 놓쳤다. ⑦ 이 장의 구간 산술은 유리수 정확 연산과 $10^5$회 대조해 위반이 없었고, mpmath·pyinterval·codac의 구간은 정확한 자연 포함 함수와 끝점이 같은 반면 이 장의 구간은 끝점마다 1~7 ulp 넓었으며, codac의 수축자 기반 면적 0.1536은 이 장의 0.1538과 일치했다. codac 2.1.2는 import 시 FPU 반올림 모드를 상향으로 바꾸고 되돌리지 않았다.

import math

dn = lambda x: math.nextafter(x, -math.inf)
up = lambda x: math.nextafter(x, math.inf)

class Iv:
    """구간 [lo, hi]. 연산마다 1 ulp 바깥으로 반올림한다."""
    def __init__(s, lo, hi=None):
        s.lo, s.hi = lo, (lo if hi is None else hi)

    def __add__(a, b):
        b = b if isinstance(b, Iv) else Iv(b)
        return Iv(dn(a.lo + b.lo), up(a.hi + b.hi))

    def __sub__(a, b):
        b = b if isinstance(b, Iv) else Iv(b)
        return Iv(dn(a.lo - b.hi), up(a.hi - b.lo))

    def __mul__(a, b):
        b = b if isinstance(b, Iv) else Iv(b)
        p = [x * y for x in (a.lo, a.hi)
             for y in (b.lo, b.hi)]
        return Iv(dn(min(p)), up(max(p)))

    def __truediv__(a, b):  # 0이 b에 없을 때만
        q = [x / y for x in (a.lo, a.hi)
             for y in (b.lo, b.hi)]
        return Iv(dn(min(q)), up(max(q)))

    __radd__, __rmul__ = __add__, __mul__

    def sqr(a):
        p = (a.lo * a.lo, a.hi * a.hi)
        lo = 0.0 if a.lo <= 0 <= a.hi else dn(min(p))
        return Iv(lo, up(max(p)))

    def sqrt(a):
        return Iv(dn(math.sqrt(max(a.lo, 0.0))),
                  up(math.sqrt(a.hi)))

    def inter(a, b):
        lo, hi = max(a.lo, b.lo), min(a.hi, b.hi)
        return Iv(lo, hi) if lo <= hi else None

    def mid(a):
        return 0.5 * (a.lo + a.hi)

    def wid(a):
        return a.hi - a.lo

def bsqr(s, u):
    """u^2 = s의 후방 전파: u ∩ (±sqrt(s))의 포함 구간"""
    r = s.inter(Iv(0.0, math.inf))
    if r is None:
        return None
    r = r.sqrt()
    p, n = u.inter(r), u.inter(Iv(-r.hi, -r.lo))
    if p is None or n is None:
        return p or n
    return Iv(min(p.lo, n.lo), max(p.hi, n.hi))

def dist(b, a):
    """||p - a||의 포함 함수. b = [x 구간, y 구간]"""
    return ((b[0] - a[0]).sqr() + (b[1] - a[1]).sqr()).sqrt()

def inside(b, a, d):
    """상자 b 전체가 거리 조건을 만족하는가"""
    r = dist(b, a)
    return d.lo <= r.lo and r.hi <= d.hi

def ctc_dist(b, a, d):
    """HC4 전방-후방 전파: ||p - a|| 가 d에 속하는 상자"""
    u, v = b[0] - a[0], b[1] - a[1]
    s, t = u.sqr(), v.sqr()
    r = d.inter(Iv(0.0, math.inf))  # 거리는 0 이상
    q = None if r is None else (s + t).inter(r.sqr())
    if q is None:
        return None
    s, t = s.inter(q - t), t.inter(q - s)
    if s is None or t is None:
        return None
    u, v = bsqr(s, u), bsqr(t, v)
    if u is None or v is None:
        return None
    x, y = b[0].inter(u + a[0]), b[1].inter(v + a[1])
    return None if x is None or y is None else [x, y]

def newton(f, df, x):
    """1차원 뉴턴 수축자(df(x)가 0을 포함하지 않을 때)"""
    c = x.mid()
    return x.inter(Iv(c) - f(Iv(c)) / df(x))

def qhull(ivs, k):
    """구간 중 k개 이상에 속하는 점들의 포함 구간"""
    ev = sorted([(i.lo, 0) for i in ivs] +
                [(i.hi, 1) for i in ivs])
    n, pts = 0, []
    for x, kind in ev:
        n += 1 - kind
        if n >= k:
            pts.append(x)
        n -= kind
    return Iv(pts[0], pts[-1]) if pts else None

def sivia(box, cons, eps, q=0, ctc=True):
    """cons = [(표지, 거리 구간)]. 위반 q개까지 허용한 해 집합
    (안쪽 상자, 경계 상자, 평가 횟수)"""
    m, inn, bnd, stack, n = len(cons), [], [], [box], 0
    while stack:
        b = stack.pop()
        n += 1
        if sum(inside(b, a, d) for a, d in cons) >= m - q:
            inn.append(b)
            continue
        cs = [ctc_dist(b, a, d) if ctc else
              (b if dist(b, a).inter(d) else None)
              for a, d in cons]
        cs = [c for c in cs if c]
        if len(cs) < m - q:
            continue
        b = [qhull([c[i] for c in cs], m - q) for i in (0, 1)]
        if None in b:
            continue
        i = 0 if b[0].wid() >= b[1].wid() else 1
        if b[i].wid() < eps:
            bnd.append(b)
            continue
        h = b[i].mid()
        for k in (Iv(b[i].lo, h), Iv(h, b[i].hi)):
            stack.append(b[:i] + [k] + b[i + 1:])
    return inn, bnd, n

① 종속성 문제와 과대 평가. 식은 1.22.3.2의 것이고 평균값 형식의 $c$는 구간의 중점이다.

$x-x$는 자연 포함 함수가 반올림을 포함해 $[-1,1]$이고 평균값 형식은 도함수 구간이 $[0,0]$이어서 정확하다. $[0,3]$의 $x^2-2x$는 $[f']=[-2,4]$가 0을 포함해 평균값 형식($[-6.75,5.25]$)이 자연 포함 함수보다 조금 좁을 뿐이다. 구간을 $[2-w,2+w]$로 줄이면 차이가 벌어진다.

반폭이 1에서 1/4로 줄면 자연 포함 함수의 과대 평가는 1/4(8.0에서 2.0), 평균값 형식은 1/16(4.0에서 0.25)로 줄어든다(도해 1의 기울기 1과 2).

분할은 $[0,3]$을 $k$등분해 조각별 포함 함수의 합집합을 구한다(참 범위의 폭 4).

분할 수를 4배로 늘릴 때마다 자연 포함 함수의 과대 평가는 약 1/4(2.9375, 0.7461, 0.1873), 평균값 형식은 약 1/16(0.5000, 0.0313, 0.0020)이 되어 각각 $1/k$, $1/k^2$이다. 래핑 효과는 한 변 0.2의 상자를 10도씩 회전해 측정했다. 상자의 한 변은 1회 0.232, 6회 0.483, 12회 1.17, 24회 6.83, 36회 39.9이며, 회전마다 $\cos10^\circ+\sin10^\circ=1.1585$배(36회 199.4배)에 일치한다.

② 수축자: HC4 대 뉴턴. $x^2-2x-1=0$의 영점 $1+\sqrt2$를 $[2,3]$에서 구한다. HC4는 $x^2-2x=1$에 전방-후방 전파를 반복하고(코드 밖의 hc4_poly, 같은 Iv 사용), 뉴턴 수축자는 newton을 반복한다.

HC4의 폭 비는 0.4126·0.4136·0.4140으로 $1/(1+\sqrt2)=0.4142$에 수렴해 선형 수렴이고, 뉴턴 수축자는 이차 수렴이다. 뉴턴의 폭은 $2.7\times10^{-15}$(바깥 반올림에 따른 하한)에서 멈추며 극한 구간 $[2.414213562373094,\,2.414213562373096]$이 $1+\sqrt2=2.414213562373095$를 포함한다.

③ SIVIA 위치추정. 위 표지·참값에서 오차 없는 거리에 한계 $\epsilon$를 더한 측정으로 해 집합을 구한다. 표의 참 면적은 열 단위 적분(분할 4000)으로 구한 값이며 안쪽·바깥 면적이 매번 이 값을 사이에 두었다.

수축자는 평가 횟수를 1.6~1.8배 줄인다. 분해능 $\delta$를 바꾸면 다음과 같다($\epsilon=0.2$ m).

$\delta$를 절반으로 줄이면 평가 횟수는 2.1~2.6배, 바깥 면적의 초과분(바깥÷참 − 1)은 약 절반(0.208, 0.104, 0.043, 0.020)이 된다. 도해 2의 (가)는 $\delta=0.02$ m의 상자 목록이다.

④ 바깥 반올림. 십진 상수는 이진 근사값의 양쪽 한 단계 구간으로 변환했고, 실수 참값의 포함은 fractions.Fraction으로 판정했다.

바깥 반올림 없이 계산한 값은 세 경우 모두 실수 참값과 달랐다. 이 장의 구간 산술은 무작위 입력 $10^5$회에서 덧셈·뺄셈·곱셈·나눗셈·제곱·제곱근의 구간이 유리수 정확 결과를 모두 포함했고(위반 0), math.sqrt는 $10^5$회 모두 정확 반올림이었다. 곱 상한의 바깥 여유는 정확값 대비 최대 1.50 ulp이다.

⑤ 이상치와 q-릴랙스 교집합. 이상치는 측정에 $\pm(1\sim3)$ m를 더한 값이며 개수만큼의 표지에서 임의로 골랐다.

표지 4개에서 이상치 1개를 $q=1$로 허용하면 참값을 잃지 않으며 바깥 면적의 중앙값은 0.153 m²이다. 이상치 2개를 표지 4개에서 $q=2$로 허용하면 면적이 1.108 m², 연결 성분 수가 중앙값 5로 늘어 정보가 거의 남지 않는다. 표지 6개에서는 $q=2$의 면적이 0.101 m²이고 연결 성분이 1~4개이다. 허용 위반 수가 실제 이상치 수보다 작으면($q=1$) 99.0%가 공집합이지만 나머지 1.0%는 공집합이 아니면서 참값을 포함하지 않는 작은 집합이었다. 도해 2의 (나)는 허위 집합이 나타난 한 사례이다.

⑥ 한계 가정의 위반과 가우시안 타원. 같은 측정에 구간 방법(한계 $\epsilon=0.2$ m)과 가우스-뉴턴(1.12의 구현)의 95% 타원을 적용했다. 균일 오차의 한계를 $\kappa\epsilon$로 넓혀 가정 위반을 만들었고, 가우시안 오차(표준편차 $\sigma$)에서는 구간 방법의 한계를 $\epsilon=0.2$ m로 두고 타원은 실제 $\sigma$를 사용했다.

한계가 성립하는 균일 오차에서 구간 해 집합은 면적 중앙값 0.075 m²로 타원(0.129 m²)보다 작고 포함은 1.000이다. 가우시안 오차에서 한계를 $3\sigma$($\sigma=\epsilon/3$)로 잡으면 구간 포함이 0.996(해석값 $\mathrm{erf}(3/\sqrt2)^4=0.989$), $2\sigma$로 잡으면 0.850(해석값 0.830)이다. 한계가 어긋나면 구간 포함이 $\kappa^{-4}$를 따라 떨어진다(도해 3). 점 오차의 중앙값은 한계가 성립할 때 구간 상자 중심이 0.103 m, 가우스-뉴턴이 0.102 m로 비슷하다.

⑦ 라이브러리와의 대조(실행 2026-11-03). 스크립트는 robotics/fig-src/1.22-libcheck.py, 출력은 robotics/fig-src/data/1.22-libcheck-output.txt에 있다. 같은 식(⑴ $x-x$ $[1,2]$, ⑵ $x^2-2x$ $[0,3]$, ⑶ $(x-1)^2-1$ $[0,3]$, ⑷ 평균값 형식 $[0,3]$, ⑸ $x^2-2x$ $[1.5,2.5]$)을 정확한 자연 포함 함수(유리수 구간 산술)와 대조했다.

arb는 중점-반지름 표현이어서 폭이 큰 입력에서 자연 포함 함수가 대칭으로 넓어지고, 입력 $[1,2]$에서도 $x-x$의 반지름이 $1+2^{-29}$이다(반지름이 30비트 고정 정밀도라는 문서 문자열의 설명과 같은 규모이며 원인은 소스로 확인하지 못했다). 다음은 같은 위치추정 입력(한계 0.2 m, 분해능 0.02 m)에서 codac과 비교한 결과이다.

두 구현 모두 모든 경우에 참값을 포함했고, 좌표별 q-릴랙스 상자 포함은 무작위 2000회에서 codac.qinter와 모두 일치했다. 첫 수축 1회의 결과($x\in[3.09180,5.20000]$, $y\in[2.16544,4.61788]$)는 codac의 CtcInverse와 같았고, 중심 형식(평균값 형식)을 켜거나 꺼도 이 입력에서는 같았다(소스에서 기본값은 켜짐이다). codac의 pave는 안쪽 상자를 구분하지 않아 상자 수가 많다. 시간은 두 구현 모두 10~60 ms로 같은 자릿수였다(단일 실행, 환경 의존). codac의 Interval은 gaol(헤더 gaol/gaol_interval.h, 소스 확인) 기반이며, import codac 직후 FPU 반올림 모드가 최근접(0x0)에서 상향(0x800)으로 바뀌어 이후의 파이썬 float 연산이 상향 반올림되었다($1.0/3.0=0.33333333333333337$, 0.1을 열 번 더한 합 1.0000000000000002). 모드를 최근접·하향·영 방향으로 바꾸면 Interval(1.0)/Interval(3.0)을 포함해 시험한 세 연산 모두 실수 결과를 포함하지 못했다(sqrt는 호출 시 모드를 다시 상향으로 바꾼다). 구간 연산이 전역 상향 모드를 전제하는 것으로 보이나 원인은 소스로 확인하지 못했고 문서화 여부도 확인하지 못했다. 이 때문에 다른 계산과 한 프로세스에서 사용할 때는 순서에 유의해야 하며, 이 장의 대조 스크립트는 codac을 마지막에 import 한다.

견해: 이 책은 구간 방법을 확률 방법의 대체가 아니라, 오차 한계가 사양이나 교정 시험으로 뒷받침되는 센서에서 확률 방법과 병행하는 독립 검증으로 두는 것을 기본으로 본다. 근거는 위 예제에서 한계가 성립할 때 참값 포함이 500회 모두였으나(가우시안 $\sigma=\epsilon/3$에서도 0.996), 한계가 1.5배 어긋나면 0.186으로 떨어지고 그중 공집합으로 위반이 드러난 경우는 12.6%뿐이었다는 점이다. 한계의 근거가 약한 센서에서는 해 집합의 폭보다 한계의 검증이 먼저이다. 이 근거는 표지 4개의 한 기하이다.

1.22.6 설계 트레이드오프 — 오차 모델과 추정기의 선택

• ① 한계 오차와 구간 집합(SIVIA·수축자). 한계가 성립하면 참값 포함이 보장된다. 비용은 차원이 커질수록 급증하고(1.22.3.3의 $k^n$) 한계의 근거가 필요하다.
• ② 분포 가정과 가우스-뉴턴·칼만 필터(1.12·9.3). 계산이 가볍고 통계적 포함 확률을 준다. 분포 가정이 맞아야 하고 이상치에 취약하다.
• ③ 이상치 강건화. 구간 방법의 q-릴랙스, 확률 방법의 M-추정·RANSAC(9.12). 이상치 수 상한(구간)이나 손실의 임계값(확률)을 정해야 한다.

견해: 이상치 허용은 $q$를 크게 잡을수록 안전해지는 설정이 아니며, 2차원 거리 측정에서는 $m-q\ge3$이 되도록 정해야 한다고 본다. 근거는 환형 두 개의 교집합이 일반적으로 두 군데로 나뉜다는 기하와, 예제에서 $m-q=2$(표지 4개, $q=2$)는 면적 1.108 m²·연결 성분 수 중앙값 5로 정보를 잃은 반면 $m-q=4$(표지 6개, $q=2$)는 면적 0.101 m²를 유지했다는 점이다. 이 근거는 두 배치의 한 사례이다.

1.22.7 응용 축 비교

이 표는 이 책의 정리이며 장별 요구는 다르다.

1.22.8 관련 규격·프로토콜

IEEE 1788에는 간략판(Simplified)도 있다(제정 연도 (확인 필요)). 구간 해석 소프트웨어 사이의 상호운용 프로토콜과 해 집합의 교환 형식은 확인하지 못했고 (확인 필요), 오차 경계 보고의 안전 연계는 9.25가 다룬다.

1.22.9 관련 규제·인증 요구와의 연결

직접 적용되는 규제는 없다. 속도·위치 감시 같은 안전 기능(26.7)이 가정하는 위치 오차의 상한을 계산으로 증명하는 수단으로 사용할 수 있지만 안전 규격이 구간 해석을 요구하는지는 확인하지 못했다 (확인 필요). 안전 논증의 근거 형식은 26.13, 형식 방법은 26.14, 소프트웨어 안전·품질 표준은 26.20이 다룬다. 구간 연산 도구를 안전 관련 개발에 사용할 때의 도구 자격 평가는 이 장에서 다루지 않았고 26.20에 위임한다.

1.22.10 한계·유의점·미해결

• 한계 가정. 모든 보장은 오차 한계가 맞다는 전제에서 나온다. 한계가 어긋나면 해 집합이 비어 있지 않은 채 참값을 놓치는 경우가 많았다(⑥). 수치는 표지 4~6개의 한 기하에서 얻은 합성 입력이며(시드 고정), 실측 센서의 한계를 정하는 절차는 다루지 않았다. 면적의 기준은 열 단위 적분이며 분할 1000·4000·16000의 값이 $2\times10^{-8}$ 이내로 일치했다.
• 비용과 동적 시스템. 경계 상자 수와 평가 횟수는 분해능과 차원에 따라 늘어난다. 이 장은 2차원만 측정했고 3차원 이상의 비용은 측정하지 않았다 (추정: 지수적 증가). 상태 전파·시간 불확실성·래핑 효과의 완화는 구현하지 않았다.
• 방위각·초월 함수. 거리 측정만 구현했다. 방위각에는 정확도가 보장된 삼각 함수의 구간 계산이 필요하며, 이를 제공하는 라이브러리가 있는 것으로 알려져 있으나 이 장은 확인하지 않았다. 인용한 정리의 번호와 교과서 장 번호도 확인하지 못했다 (확인 필요).
• 반올림. 하위 정규수·오버플로·비표준 반올림 모드의 플랫폼은 시험하지 않았다. 반올림 모드를 전환하는 방식의 라이브러리는 스레드 안전하지 않다고 pyinterval의 소스가 밝힌다.
• 라이브러리. codac 2.1.2는 의존 패키지의 휠이 없어 --no-deps로 설치했고 그래픽 기능은 확인하지 않았으며, FPU 반올림 모드를 바꾸는 동작(⑦)을 문서에서 확인하지 못했다. pyinterval 1.2.0은 crlibm 확장의 빌드 오류로 초월 함수가 없다(Python 3.12.3). 원인 해결은 시도하지 않았다.

1.22.11 체크포인트·연구 질문

체크포인트:

1. 구간 산술의 곱셈·제곱·나눗셈 규칙을 적고 $[x]-[x]$가 0이 아닌 이유를 설명할 수 있는가.
2. 자연 포함 함수와 평균값 형식의 과대 평가 차수를 구분하고 근거를 설명할 수 있는가.
3. 거리 제약에 대한 HC4의 전방·후방 단계를 적을 수 있는가.
4. SIVIA의 세 판정과, 안쪽·바깥 면적이 참 면적을 사이에 두는 이유를 설명할 수 있는가.
5. q-릴랙스 교집합이 필요한 이유와 $q$를 키울 때의 비용을 설명할 수 있는가.
6. 바깥 반올림이 없으면 보장이 깨지는 예를 들고, 한계 가정이 어긋날 때 구간 방법과 가우시안 방법의 실패 형태를 비교할 수 있는가.

연구 질문(47.12에 수록한다):

• 거리·방위각을 함께 측정할 때 표지 배치와 $q$ 선택이 해 집합의 연결 성분 수와 면적에 주는 영향은 무엇인가.
• 오차 한계를 실측 데이터에서 근거 있게 정하는 방법(최댓값·사양·컨포멀 예측, 21.9)은 무엇이며 한계 위반을 어떻게 감시하는가.
• 3차원 이상의 상태(자세 포함)에서 수축자 전처리와 분리자가 비용을 얼마나 줄이는가.

1차 출처

• R. E. Moore, 『Interval Analysis』, Prentice-Hall, 1966 — 서지는 J. F. Traub의 서평(Science 158(3799), 365, 1967, doi:10.1126/science.158.3799.365)으로 확인, 본문 미확인.
• R. E. Moore, R. B. Kearfott, M. J. Cloud, 『Introduction to Interval Analysis』, SIAM, 2009(doi:10.1137/1.9780898717716) (확인 필요: 장 번호).
• L. Jaulin, M. Kieffer, O. Didrit, É. Walter, 『Applied Interval Analysis』, Springer, 2001(doi:10.1007/978-1-4471-0249-6) (확인 필요: 장 번호).
• L. Jaulin, E. Walter, 「Set inversion via interval analysis for nonlinear bounded-error estimation」, Automatica 29(4), 1053–1064, 1993(doi:10.1016/0005-1098(93)90106-4) — 서지만 확인.
• G. Chabert, L. Jaulin, 「Contractor programming」, Artificial Intelligence 173(11), 1079–1100, 2009(doi:10.1016/j.artint.2009.03.002) — 서지만 확인.
• L. Jaulin, 「Robust set-membership state estimation; application to underwater robotics」, Automatica 45(1), 202–206, 2009(doi:10.1016/j.automatica.2008.06.013) — 서지만 확인.
• L. Jaulin, 「A nonlinear set membership approach for the localization and map building of underwater robots」, IEEE Transactions on Robotics 25(1), 88–98, 2009(doi:10.1109/TRO.2008.2010358) — 서지만 확인.
• A. Neumaier, 『Interval Methods for Systems of Equations』, Cambridge University Press(Crossref 등록 연도 1991, doi:10.1017/CBO9780511526473) (확인 필요: 장 번호).
• E. Hansen, G. W. Walster 편, 『Global Optimization Using Interval Analysis』, CRC Press(Crossref 등록 2003, doi:10.1201/9780203026922) (확인 필요: 판·장).
• K. Marzullo, 「Tolerating failures of continuous-valued sensors」, ACM Transactions on Computer Systems 8(4), 284–304, 1990(doi:10.1145/128733.128735) — 서지만 확인.
• F. C. Schweppe, 「Recursive state estimation: unknown but bounded errors and system inputs」, IEEE Transactions on Automatic Control 13(1), 22–28, 1968(doi:10.1109/TAC.1968.1098790) — 서지만 확인.
• S. M. Rump, 「Verification methods: rigorous results using floating-point arithmetic」, Acta Numerica 19, 287–449, 2010(doi:10.1017/S096249291000005X) — 서지만 확인.
• S. Rohou, L. Jaulin, L. Mihaylova, F. Le Bars, S. M. Veres, 『Reliable Robot Localization』, Wiley, 2019(doi:10.1002/9781119680970) — 서지만 확인.

다음 장. 1.23은 이산 수학으로, 그래프 이론·조합 최적화·할당 문제(헝가리안 알고리즘)·외판원 문제(TSP)를 다룬다. 이 장의 분할과 한정은 조합 최적화의 정확해 탐색(분기 한정)에도 나타나는 구조이며, 1.23은 유한 집합 위의 할당과 방문 순서를 그래프로 정식화한다.