라게르 방법

1. 개요

라게르 방법(Laguerre’s method)은 다항식의 근을 하나씩 찾는 3차 수렴 반복법으로, 매 걸음 $p$, $p'$, $p''$ 의 값을 써서 다음 근사를 정한다. 프랑스 수학자 에드몽 라게르(1834–1886)가 1880년 “모든 근이 실수인 대수방정식” 을 위해 제안했다. 그 조건 아래서는 어느 실수 출발점에서 시작해도 수렴한다는 드문 성질을 가지며, 복소 근이 섞여 있어도 실전에서 거의 실패하지 않아 『Numerical Recipes』 가 다항식 근 찾기의 대표 루틴으로 골랐다.

뉴턴-랩슨법이 $p$ 를 접선 하나로 근사하는 것과 달리, 라게르는 $p$ 의 근 배치 전체에 대한 가장 비관적인 모형을 세우고 그 모형을 정확히 푼다. 덕분에 출발점이 근에서 멀어도 걸음이 터무니없이 커지지 않는다. 그리고 공식에 제곱근이 들어 있어서, 실수에서 출발해도 필요하면 스스로 복소평면으로 걸어 나간다. 이 두 가지가 젠킨스-트라우브 알고리즘·뮬러 방법과 구별되는 개성이다.

2. 유도 — 비관적인 근 배치

차수 $n$ 다항식 $p(x)=c\prod_{i=1}^n(x-x_i)$ 의 로그미분을 두 번 취하면

$$G(x)\equiv\frac{p'(x)}{p(x)}=\sum_{i=1}^n\frac{1}{x-x_i},\qquad H(x)\equiv G(x)^2-\frac{p''(x)}{p(x)}=\sum_{i=1}^n\frac{1}{(x-x_i)^2}$$

이다. 여기서 대담한 가정을 한다: 찾으려는 근 $x_1$ 은 현재 점에서 거리 $a=x-x_1$ 에 있고, 나머지 $n-1$ 개 근은 모두 같은 거리 $b$ 에 있다. 그러면

$$G=\frac1a+\frac{n-1}{b},\qquad H=\frac1{a^2}+\frac{n-1}{b^2}$$

두 식에서 $b$ 를 소거하면 $a$ 에 대한 이차방정식이 나오고, 그 해가 라게르 걸음이다.

$$a=\frac{n}{G\pm\sqrt{(n-1)\,(nH-G^2)}},\qquad x_{\text{new}}=x-a$$

부호는 분모의 절댓값이 커지는 쪽을 고른다 — 그래야 걸음이 작아지고 가장 가까운 근으로 간다. $n=1$ 이면 그냥 뉴턴 걸음 $1/G$ 다.

가정이 비현실적인 것 같지만 이게 핵심이다. $n-1$ 개를 한 점에 몰아넣은 배치는 “현재 점에서 본 근 분포의 1·2차 모멘트” 를 맞추는 가장 단순한 모형이고, 실제 근 배치가 어떻든 $G$ 와 $H$ 는 정확히 계산된다. 근 하나가 압도적으로 가까우면 $a$ 가 거의 정확해지고, 그렇지 않아도 걸음 크기가 근들 사이 거리로 자동 제한된다.

2.1. 계산 비용

$p$, $p'$, $p''$ 는 호너 방법을 세 줄로 겹쳐 한 번에 구한다($O(n)$, 약 $6n$ 플롭). 반복당 평가가 뉴턴보다 조금 비싸지만 3차 수렴이라 반복 수가 적다. 계산 효율 지수($p^{1/m}$, $m$ 은 반복당 평가 수)로 따지면 뉴턴의 $2^{1/2}\approx1.41$ 대 라게르의 $3^{1/3}\approx1.44$ 로 비슷한데, 진짜 장점은 효율이 아니라 출발점을 덜 탄다는 데 있다.

3. 수렴 성질

• 단순근 근처: 3차. 오차가 매 걸음 대략 세제곱으로 준다.
• 중근: 1차. 중복도 $m$ 인 근에서는 3차성이 사라진다. 아래 검산에서 삼중근의 오차는 매 걸음 약 1/3 씩 줄었다. 뉴턴법도 중근에서 1차로 떨어지는 것과 같은 운명이다.
• 모든 근이 실수인 경우: 전역 수렴. 라게르가 원 논문에서 다룬 상황으로, 실수 출발점 $x$ 가 두 이웃 근 사이에 있으면 그 둘 중 하나로, 모든 근 바깥에 있으면 가장 바깥 근으로 단조롭게 수렴한다. 이때 $nH-G^2\ge0$ 이 보장돼(코시-슈바르츠 부등식) 제곱근이 실수로 남는다.
• 복소 근이 있는 경우. 전역 수렴 정리는 없고 드물게 순환 궤도에 갇힐 수 있다. 『Numerical Recipes』 의 laguer 는 정해진 반복마다 걸음을 일부러 엉뚱한 비율로 줄여 순환을 깨는 장치를 넣었다.¹

4. 검산

월리스의 삼차식 $p=x^3-2x-5$ (실근 $2.0945514815423265$, 복소근 $-1.0473\pm1.1359i$).

출발점	뉴턴	라게르
$x_0=2$	4번째에 수렴 (2.1 → 2.09457 → …)	2번째에 수렴 (2.0945610 → 2.0945514815423265)
$x_0=1$	—	3번째에 실근
$x_0=0$	$-2.5,\,-1.57,\,-0.50,\,-3.82,\,\dots$ 무한 방황	$-2.5$ 다음에 복소평면으로 나가 5번째에 $-1.04728+1.13594i$

$x_0=0$ 행이 라게르의 개성을 보여 준다. 실근 하나뿐인 실계수 삼차식에서 실수 반복인 뉴턴은 복소근 근처를 영원히 맴돌지만, 라게르는 두 번째 걸음에서 $nH-G^2<0$ 이 되자 제곱근이 허수가 되면서 복소근으로 곧장 갔다. 실계수 다항식의 복소근 한 쌍을 실수 연산만으로 찾고 싶다면 이게 오히려 번거로울 수 있다 — 그 경우는 이차 인수를 직접 찾는 베어스토 방법이나 젠킨스-트라우브의 실수판(RPOLY)이 낫다.

모든 근이 실수인 다항식 $p=\prod_{k=1}^{10}(x-k)$.

• $x_0=100$: $13.48 \to 10.51 \to 10.019 \to 10.0000022 \to 9.99999999999651$. 가장 바깥 근 10 으로 단조 수렴.
• $x_0=-50$: $-2.11 \to 0.553 \to 0.986 \to 0.99999918 \to 0.9999999999999997$. 반대쪽 바깥 근 1 로.

뉴턴법은 같은 출발점에서 근 사이 거리 대비 엄청 먼 곳부터 천천히 다가와 $x_0=100$ 에서 근 10 에 $10^{-9}$ 까지 붙는 데 37걸음이 걸렸다. 라게르는 “근 9개가 저쪽에 몰려 있다” 는 가정 덕에 첫 걸음에 근 범위 안으로 뛰어든다. 마지막 몇 걸음에서 $10^{-11}$ 근처를 맴도는 것은 이 다항식(윌킨슨 다항식의 작은 판) 계수가 반올림 오차에 민감한 탓으로, 알고리즘이 아니라 조건수의 한계다.

삼중근 $p=(x-1)^3(x+2)$, $x_0=3$: 오차 $0.46\to0.14\to0.045\to0.015\to0.0049\to\cdots$, 비율 약 1/3 로 1차 수렴. 중근이 의심되면 수렴 속도 자체가 진단 신호다.

5. 실전 — 수축과 다듬기

모든 근을 원하면 근 하나를 찾을 때마다 조립제법으로 $p(x)/(x-x_1)$ 을 만들어(수축, deflation) 차수를 줄이고 다시 라게르를 돌린다. 『Numerical Recipes』 의 zroots 가 이 구조이고, 두 가지 관례가 붙는다.

1. 작은 근부터. 라게르를 $x_0=0$ 에서 시작하면 대개 절댓값이 작은 근이 먼저 잡히는데, 수축은 작은 근부터 걷어낼 때 안정적이다(계수 오차가 덜 전파된다).
2. 원래 다항식으로 다듬기. 수축된 다항식에서 찾은 근은 누적 오차를 품으므로, 마지막에 원래 $p$ 로 라게르나 뉴턴을 한두 번 더 돌려 정밀도를 회복한다(polishing).

오늘날 “다항식 근 전부” 의 기본값은 동반 행렬의 고유값을 QR 알고리즘으로 구하는 방식(MATLAB·NumPy roots)이나, 모든 근을 동시에 갱신하는 에얼리히-애버스 계열(MPSolve)이다. 라게르는 그 사이에서 “근 몇 개만 필요하고, 출발점 정보가 없고, 코드는 짧아야 할 때” 의 선택지로 남았다. 라게르 걸음을 모든 근에 동시에 적용하는 동시 반복판(근 사이 상호작용 항을 $G$·$H$ 에 넣는 방식)도 연구돼 있다.²

6. 이름이 같은 다른 것들

같은 라게르의 이름은 직교다항식 쪽에서 더 자주 들린다 — 라게르 다항식 $L_n(x)$ 은 $[0,\infty)$ 에서 가중치 $e^{-x}$ 에 대한 직교다항식이고, 수소 원자 동경 파동함수와 가우스-라게르 구적에 등장한다. 근 찾기의 라게르 방법과는 수학적으로 아무 관계가 없다.³

7. 관련 문서

• 뉴턴-랩슨법 · 뮬러 방법 · 젠킨스-트라우브 알고리즘 · 할선법
• 호너 방법 · 동반 행렬 · QR 알고리즘 · 조건수
• 애버스 방법 · 베어스토 방법 · 다항식 수축

8. Footnotes

1. 『Numerical Recipes』 의 laguer 는 일정 반복마다 걸음에 미리 정한 분수(0.5, 0.25, 0.75, … 같은 목록)를 곱해 리밋 사이클을 깬다. 이론이 아니라 “일단 흔들어 보면 빠져나오더라” 에 기반한 장치인데, 수십 년 동안 잘 돌았다. 수렴은 신에게 맡기되 가끔 신을 흔들어 깨워야 한다. ↩

2. 판(Pan, 1997)의 SIAM Review 조사 논문은 4천 년 다항식 근 찾기 역사를 한 편에 정리한 명작이다. 바빌론 점토판의 제곱근에서 시작해 1990년대 최적 복잡도 알고리즘까지 간다. 라게르는 거기서 “실전에서 잘 되는데 이론이 덜 따라온” 범주에 들어 있다. ↩

3. 수치해석 수업에서 “라게르 다항식으로 라게르 방법을 돌리면 근이 나오나요?” 같은 질문이 매 학기 나온다. 나오긴 한다. 라게르 다항식은 근이 전부 양의 실수라서, 오히려 라게르 방법이 가장 잘 되는 부류다. 이름 덕분에 생긴 우연한 궁합. ↩