레머즈 알고리즘

수치해석 전자공학 마지막 수정: 2026-08-14 04:47:52

1. 개요[편집]

레머즈 알고리즘 Remez algorithm (Remez exchange)
목표	균등 노름 최소화 $\min_p \max_x \|f(x)-p(x)\|$
이론적 근거	체비쇼프 등리플(교대) 정리
최적 조건	차수 $n$ 다항식이면 부호가 교대하는 극값 $n+2$ 개
한 반복	기준점에서 선형계 풀기 → 새 극값으로 기준점 교체
수렴	매끄러운 $f$ 에 대해 2차 (전점 교환)
발표	Е. Я. Ремез (1934)
대표 응용	파크스-맥클렐런 FIR 설계 · libm 다항식 계수

최소자승은 평균적으로 잘 맞히고, 미니맥스는 최악의 순간에 진다는 것을 허락하지 않는다.

레머즈 알고리즘(Remez algorithm, 레머즈 교환 알고리즘)은 주어진 연속함수 $f$ 를 균등 노름(최대 오차) 기준으로 가장 잘 근사하는 다항식 또는 유리함수를 반복적으로 찾아내는 절차다. 즉

E_n(f) = \min_{p \in \mathcal{P}_n} \ \max_{x\in[a,b]} \bigl|f(x) - p(x)\bigr|

를 달성하는 $p^\star$ 를 구한다. 최소자승법이 오차 제곱의 적분을 줄이는 것과 달리 여기서는 한 점에서라도 크게 틀리면 지는 기준을 쓴다. 함수 라이브러리의 sin, exp 처럼 “이 구간 전체에서 오차가 $2^{-53}$ 이하임을 보증”해야 하는 자리, FIR 필터처럼 “저지대역 감쇠 60 dB 이상”이 스펙으로 박히는 자리에서는 평균이 아니라 최악값이 계약 조건이다.¹

핵심은 알고리즘 이전에 최적해가 어떻게 생겼는지를 완전히 아는 정리가 있다는 것이다. 그 정리 덕분에 “최적화 문제를 푼다”가 아니라 “최적해의 필요충분조건을 만족하는 점들을 찾는다”로 문제를 바꿀 수 있고, 그것이 레머즈 교환의 전부다.

2. 등리플 정리 — 최적해의 지문[편집]

체비쇼프 교대 정리(equioscillation theorem). $f \in C[a,b]$ 에 대해 $p^\star \in \mathcal{P}_n$ 이 최량 균등 근사일 필요충분조건은, 오차 $e = f - p^\star$ 가 $a \le x_0 < x_1 < \cdots < x_{n+1} \le b$ 인 점 $n+2$ 개에서 $e(x_i) = \sigma(-1)^i\|e\|_\infty$ ( $\sigma = \pm1$ ) 를 만족하는 것이다.

말로 풀면 오차 곡선이 최대 크기를 정확히 유지한 채 부호를 번갈아 $n+2$ 번 찍는다는 것이다. 최량 근사는 유일하다.

필요성의 직관이 좋다. 교대점이 $n+1$ 개 이하라면, 오차가 부호를 바꾸는 자리를 근으로 갖는 $n$ 차 이하 다항식 $q$ 를 만들 수 있고, $p^\star + \epsilon q$ 로 옮기면 모든 극값이 동시에 조금씩 줄어든다 — 최적이 아니었다는 뜻이다. 교대가 $n+2$ 번이면 자유도 $n+1$ 개로는 모든 극값을 동시에 누를 수 없다. 근사이론의 거의 모든 것이 이 세는 논증에서 나온다. 체비쇼프가 19세기 중반에 사실상 확립했고 엄밀한 증명과 유일성은 20세기 초에 정리됐다.

부산물로 하한도 공짜로 얻는다. 어떤 $p$ 에 대해 오차가 $n+2$ 개 점에서 부호만 교대하면(크기는 달라도 된다) 드 라 발레 푸생 부등식

\min_i |e(x_i)| \ \le\ E_n(f) \ \le\ \|e\|_\infty

가 성립한다. 좌변과 우변이 최량 오차를 위아래로 가두므로, 반복을 언제 멈출지에 대한 계산 가능한 정지 기준이 생긴다. 최적값을 모르는 채 최적성을 인증할 수 있다는 점에서 최적화 이론의 쌍대 하한과 같은 역할이다.

3. 교환 반복[편집]

절차는 정리를 그대로 코드로 옮긴 것이다.

기준점 초기화. $x_0 < \cdots < x_{n+1}$ 을 잡는다. 등간격은 나쁜 선택이고, 실무는 체비쇼프 극점(Chebyshev extreme points) $x_i = \cos(i\pi/(n+1))$ 로 시작한다.
선형계 풀기. 미지수 $a_0,\dots,a_n$ 과 스칼라 $h$ 에 대해
$\sum_{j=0}^{n} a_j \phi_j(x_i) + (-1)^i h = f(x_i), \qquad i = 0,\dots,n+1$
을 푼다. 식도 $n+2$ 개, 미지수도 $n+2$ 개다. 기저 $\{\phi_j\}$ 가 체비쇼프 계(Haar 조건)를 이루면 이 계는 항상 정칙이다. $|h|$ 가 현재 기준점에서의 등리플 크기다.
극값 재탐색. 새로 얻은 $p$ 로 오차 $e = f - p$ 의 국소 극값을 전 구간에서 전부 찾는다.
교환. 부호가 교대하도록 $n+2$ 개를 골라 새 기준점으로 삼되, 전역 최대점은 반드시 포함시킨다. 2로 돌아간다.

한 점만 바꾸는 원형(1차 알고리즘)은 선형 수렴이고, 모든 점을 한꺼번에 갈아 끼우는 2차 알고리즘은 매끄러운 $f$ 에 대해 2차 수렴한다. $|h|$ 는 반복마다 단조 증가하며 $E_n(f)$ 로 올라가고, $\|e\|_\infty$ 는 위에서 내려온다. 두 값이 만나면 끝. 보통 대여섯 번이면 배정도 정밀도에 도달한다.

수치적으로 조심할 곳은 두 군데다. 기저를 단항식 $1, x, x^2, \dots$ 으로 잡으면 안 된다 — 판데르몽드 계의 조건수가 지수로 폭발해서 $n \gtrsim 20$ 에서 답이 무의미해진다. 체비쇼프 다항식 기저를 쓰고 배리센트릭 형태로 평가하면 $n$ 이 수백이어도 멀쩡하다. 그리고 극값 탐색을 게을리하면 안 된다. 전역 최대를 놓치면 교환이 잘못된 방향으로 가고, 알고리즘은 발산 대신 엉뚱한 국소 등리플에 정착한다.

4. 그런데 대부분은 여기까지 안 온다[편집]

균등 최적을 정말로 구해야 하는 경우는 생각보다 드물다. 체비쇼프 다항식 노드에서의 보간만으로도 이미 최량에 로그 인자만큼만 뒤처지기 때문이다.

\|f - p_{\text{cheb}}\|_\infty \ \le\ \left(2 + \frac{2}{\pi}\log n\right) E_n(f)

$n = 1000$ 이어도 계수가 6 남짓이다. 최량 근사를 얻자고 반복을 돌려서 버는 것이 기껏 몇 배인데, 체비쇼프 보간은 고속 푸리에 변환 한 번으로 끝난다. 그래서 “일단 체비쇼프 계수를 뽑고, 정말 마지막 한 자리가 아쉬울 때만 레머즈”가 현실적인 국룰이다.² 파데 근사가 유리 근사 쪽에서 같은 역할을 하는 것도 같은 사정이다 — 대각 파데가 최량 유리 근사와 같은 지수 수렴 속도를 내므로 굳이 최적까지 갈 이유가 적다.

레머즈가 여전히 필수인 자리는 한 번 구해서 영원히 쓰는 계수다. libm의 초등함수 다항식, 하드웨어 IP의 계수 테이블, 표준으로 박제되는 필터 계수 — 설계 비용이 아무리 커도 실행 시간에 항 하나를 줄이면 그게 그대로 이득이다. 여기에는 반전이 하나 더 붙는다. 실수 최적 계수를 구해도 그것을 배정도로 반올림하는 순간 최적성이 깨지므로, 처음부터 표현 가능한 부동소수점 수 중에서 최적을 찾는 문제가 따로 있다. 이 문제는 격자점 위의 최적화라 격자 축소 기법으로 풀며, Sollya 의 fpminimax 가 대표 도구다.

5. 유리 근사 — 여기서부터 불안정하다[편집]

같은 이야기를 유리함수 $r = p/q$ ( $\deg p \le m$ , $\deg q \le n$ )로 확장할 수 있다. 교대 정리도 살아남아서, 퇴화하지 않은 경우 최량 유리 근사의 오차는 $m+n+2$ 개 점에서 등리플한다. 그런데 알고리즘은 훨씬 험해진다.

조건이 비선형이다. $f - p/q$ 를 다루는 대신 $fq - p$ 로 선형화하면 각 반복이 일반화 고유값 문제로 바뀌는데, 이 선형화가 원래 조건과 어긋나는 자리가 생긴다.
퇴화(degeneracy). 분자·분모가 공통인수를 갖거나 실질 차수가 떨어지면 교대점 개수가 줄고 표준 이론이 무너진다.
표현이 악조건이다. 계수로 유리함수를 나타내면 극점과 영점이 가까울 때 정보가 상쇄로 날아간다. 파데 근사의 프루아사르 이중항과 같은 병리다.

역사적으로 유리 레머즈는 “된다고 알려져 있지만 아무도 믿고 못 쓰는” 알고리즘이었다. 판을 바꾼 것이 배리센트릭 표현이다. 계수 대신 지지점·가중치로 유리함수를 적으면 극점 근처에서도 조건수가 유지되고, 그 위에서 레머즈 교환을 돌리면 차수 수십에서도 안정하게 수렴한다(2018년 Chebfun minimax 구현). 한 걸음 더 나가면 AAA 알고리즘 — 지지점을 탐욕적으로 하나씩 고르면서 나머지를 최소자승법으로 맞추는 방식이라 교대 정리를 아예 쓰지 않고, 최소자승 가중치를 반복 갱신하는 로슨 반복을 얹으면 거의 최량 균등 근사까지 도달한다. 함수의 절단면·극점 근처 근사, 축소차수모델, 비선형 고유값 문제의 유리 근사가 요즘 전부 이 계열로 갈아탔다.

6. 파크스-맥클렐런 — 신호처리로 간 레머즈[편집]

레머즈가 가장 널리 실행되는 곳은 아마 디지털 필터 설계일 것이다. 선형위상 FIR 필터의 주파수 응답은 대칭 계수 덕분에

H(\omega) = \sum_{k=0}^{M} b_k \cos(k\omega)

꼴로 쓰이고, $\cos(k\omega) = T_k(\cos\omega)$ 이므로 이것은 변수 $\cos\omega$ 에 대한 다항식이다. 즉 필터 설계가 그대로 다항식 균등 근사 문제가 되고 교대 정리가 통째로 적용된다. 파크스와 맥클렐런(1972)이 이 사실을 알아채고 레머즈 교환을 주파수 축 위에서 돌린 것이 파크스-맥클렐런 알고리즘이다. 결과는 통과대역과 저지대역에서 리플 크기가 각각 일정한 등리플 필터 — 같은 탭 수로 얻을 수 있는 최선이라는 뜻이다.

실무적 세부가 몇 가지 붙는다. 통과·저지대역의 리플 비를 다르게 하고 싶으면 오차에 가중함수 $W(\omega)$ 를 곱해 $W(\omega)(D(\omega)-H(\omega))$ 를 등리플로 만들면 되고, 천이대역은 근사 대상에서 아예 제외한다(“don’t care”). 그래서 파크스-맥클렐런의 입력은 대역 경계·목표 이득·가중치 목록이고, 출력은 탭 계수다. 윈도 함수 기반 설계가 “잘라내고 창으로 다듬는” 방식이라 최적성 보장이 없는 것과 대비된다.

설계법	기준	최적성	탭 수 대비 성능
창 함수법	절단 + 창	없음	보통
최소자승	오차의 $L^2$ 노름	$L^2$ 최적	대역 경계에서 오버슈트
파크스-맥클렐런	오차의 최댓값	균등 최적	최선

맥클렐런-파크스-라비너의 1973년 포트란 프로그램은 지금도 MATLAB firpm, SciPy signal.remez 로 살아 있다. 반세기 된 코드가 이름만 바꿔 돌아가는, 이 바닥에서 흔한 풍경이다.³

7. 최적화 이론에서 보면[편집]

균등 근사 문제는 사실 반무한 선형계획이다. $t$ 를 최소화하되 모든 $x \in [a,b]$ 에 대해 $-t \le f(x) - \sum_j a_j\phi_j(x) \le t$ 라는 제약을 거는 것이니, 변수는 유한 개인데 제약이 연속적으로 무한 개다. 이 관점에서 보면 레머즈 교환은 활성 제약 집합을 갈아 끼우는 절차, 즉 선형계획법의 심플렉스법과 같은 종류의 교환 알고리즘이다. 기준점 $n+2$ 개가 기저(basis)에 해당하고, 새 극값을 넣고 낡은 점을 빼는 것이 피벗이며, 드 라 발레 푸생 부등식이 쌍대 하한이다.

실제로 제약을 촘촘한 격자에서만 걸어 유한 LP로 푸는 것도 완전히 정당한 접근이고, 격자를 충분히 촘촘히 잡으면 답이 최적에 임의로 가까워진다. 차수가 아주 높거나 근사 대상 집합이 복잡해서 극값 탐색이 어려울 때 이쪽이 오히려 안전하다. 다만 격자 크기만큼 문제가 커지므로, 극값 구조를 쓸 수 있는 상황에서는 레머즈가 압도적으로 빠르다.

8. 관련 문서[편집]

한글 표기가 갈린다. 원 발음(Ремез)에 가까운 “레메즈”와 영어권 표기 Remez를 읽은 “레머즈”가 혼용되고, 신호처리 교과서는 대체로 전자, 근사이론 쪽은 후자를 쓰는 경향이 있다. 어느 쪽으로 검색해도 같은 알고리즘이 나오니 마음 편히 쓰면 된다. ↩
트레페텐의 Approximation Theory and Approximation Practice 가 이 논지를 아예 책 한 권으로 밀어붙인다. 요지는 “최량 근사는 아름답지만 실무에서는 체비쇼프로 충분하다”인데, 정작 같은 저자 그룹이 유리 최량 근사를 안정하게 계산하는 코드를 만들어 놓았다. 필요 없다고 말하면서 도구는 가장 좋은 걸 만들어 두는 것, 이 바닥의 오랜 전통이다. ↩
파크스-맥클렐런이 나오기 전 필터 설계는 창 함수를 고르고 탭 수를 늘려 가며 스펙을 맞추는 시행착오였다. 등리플 설계가 등장하면서 “이 스펙이면 탭 몇 개가 필요한가”를 근사식으로 미리 계산할 수 있게 됐고, 그 결과 필터 설계가 예술에서 견적서로 바뀌었다. 하드웨어 하는 사람에게는 탭 하나가 곱셈기 하나라서, 이 견적이 곧 실리콘 면적이다. ↩