뮬러 방법

1. 개요

뮬러 방법 Muller's Method
푸는 것	스칼라 방정식 f(z) = 0, 복소근 포함
필요한 것	초기점 3개, 반복당 함수 평가 1회 (도함수 불필요)
수렴 차수	약 1.839 (t³ = t² + t + 1 의 실근)
제안	데이비드 뮬러, 1956
단골 용도	다항식의 복소근, 분산 관계의 복소 근 추적

할선법이 두 점으로 직선을 그었다면, 하나 더 써서 포물선을 긋는다. 그런데 포물선은 실수축을 안 만날 수도 있다. 뮬러는 그걸 버그가 아니라 기능으로 만들었다.

뮬러 방법(Muller’s method)은 직전 세 근사점 $(x_0,f_0)$, $(x_1,f_1)$, $(x_2,f_2)$ 를 지나는 이차 다항식을 만들고, 그 포물선의 두 근 중 $x_2$ 에 가까운 쪽을 다음 근사로 삼는 근 찾기 반복법이다. 할선법의 직선을 포물선으로 올린 일반화이고, 1956년 데이비드 뮬러가 초기 전자계산기로 다항식 근을 구하려고 제안했다.¹

포물선의 근은 판별식이 음수면 복소수가 된다. 그래서 뮬러 방법은 실수 초기점에서 출발해도 복소근으로 걸어 들어갈 수 있다. 이것이 역 이차 보간(같은 세 점을 쓰지만 $x$ 를 $y$ 의 함수로 맞춰 복소수 문제를 피한다)과 정반대의 설계 선택이다. 실수근 하나만 필요하면 귀찮은 성질이지만, 다항식의 모든 근이나 분산 관계의 복소 진동수를 찾을 때는 이게 핵심 장점이 된다.

2. 공식

최근 점 $x_2$ 를 중심으로 포물선을 쓴다. 차분몫으로

$$h_1 = x_1 - x_0,\quad h_2 = x_2 - x_1,\quad \delta_1 = \frac{f_1-f_0}{h_1},\quad \delta_2 = \frac{f_2-f_1}{h_2}$$ $$a = \frac{\delta_2-\delta_1}{h_2+h_1},\qquad b = a\,h_2 + \delta_2,\qquad c = f_2$$

라 두면 보간 포물선은 $p(x) = a(x-x_2)^2 + b(x-x_2) + c$ 다. 근은 근의 공식을 분자 유리화한 꼴로 쓴다.

$$x_3 = x_2 - \frac{2c}{\,b \pm \sqrt{b^2-4ac}\,}$$

부호는 분모의 절댓값이 커지는 쪽을 고른다. 그래야 $x_2$ 에 가까운 근이 선택되고, $b$ 와 제곱근이 비슷한 크기로 빼져 유효숫자가 날아가는 상쇄 오차도 피한다. 교과서 근의 공식 $(-b\pm\sqrt{\cdot})/2a$ 를 그대로 쓰면 $a\to0$(함수가 거의 직선)일 때 0으로 나누게 되는데, 이 꼴은 $a=0$ 에서 자연스럽게 할선 스텝 $x_2 - c/b$ 로 줄어든다.²

판별식 $b^2-4ac$ 가 음수면 복소 제곱근을 그냥 쓴다. 이후 모든 산술을 복소수로 하면 된다. 그 다음 $x_0 \leftarrow x_1$, $x_1 \leftarrow x_2$, $x_2 \leftarrow x_3$ 으로 밀고 $f(x_3)$ 하나만 새로 계산한다.

3. 수렴 차수 1.839

단순근 근처에서 오차는 대략

$$e_{k+1} \approx C\, e_k\, e_{k-1}\, e_{k-2},\qquad C = -\frac{f'''(r)}{6f'(r)}$$

를 만족한다(세 점 보간의 오차항이 세 오차의 곱으로 나온다). $|e_{k+1}| \sim |e_k|^p$ 를 넣으면 $p^3 = p^2 + p + 1$ 이고, 그 실근이

$$p \approx 1.8393$$

이다(이른바 트리보나치 상수). 할선법의 $p^2=p+1$, 즉 황금비 1.618이 두 점 곱에서 나오는 것과 똑같은 구조다.

반복당 새 함수 평가가 한 번이니 평가당 효율로도 1.839다. 뉴턴-랩슨법이 도함수 평가 비용을 $f$ 와 같다고 치면 평가당 $\sqrt2\approx1.414$, 할선법이 1.618이니, 평가당 효율 순위로는 뮬러가 이 셋 중 가장 위다. 같은 논리로 점을 더 쓰면 차수가 2에 다가가지만(네 점이면 1.928) 보간 다항식의 차수가 올라갈수록 근을 구하는 일 자체가 귀찮아지고 안정성이 나빠져서 실무는 세 점에서 멈춘다.

3.1. 검산 — 월리스의 삼차식

이분법·가위치법 문서와 같은 $f(x)=x^3-2x-5$ 에 초기점 $(2,\ 3,\ 2.5)$ 를 줬다.

반복	근사값	오차
1	2.0977237	$3.2\times10^{-3}$
2	2.0944435	$1.1\times10^{-4}$
3	2.094551494	$1.2\times10^{-8}$
4	2.0945514815423270	$4.4\times10^{-16}$

넷째 반복에 배정밀도 바닥(이웃한 부동소수점 한 칸)에 닿았다. 초기점 셋을 포함해 함수 평가 7회다. 같은 문제를 이분법은 41회, 원판 가위치법은 28회 썼다.

4. 실수에서 복소수로 걸어 들어가기

같은 삼차식은 실근 하나와 켤레 복소근 한 쌍 $-1.0472757\ldots \pm 1.1359399\ldots i$ 를 갖는다. 초기점을 실수 $(-1,\ 0,\ 1)$ 로 주면, 이 근방엔 실근이 없으니 첫 포물선부터 판별식이 음수가 되고 반복이 복소평면으로 빠져나간다.

반복	근사값
1	$-5$
2	$0.375 + 1.053i$
5	$-1.0327 + 1.3095i$
7	$-1.04700 + 1.13537i$
9	$-1.0472757407720 + 1.1359398890895i$

10번째에 위 복소근으로 기계 정밀도까지 붙었다. 첫 스텝이 $-5$ 로 크게 튄 데서 보듯, 근에서 먼 곳에서는 뉴턴-랩슨법처럼 방향을 잃을 수 있고 전역 수렴 보장은 없다. 하지만 실수 초기점 세 개만으로 복소근을 찾아냈다는 게 요점이다. 뉴턴법이나 할선법은 실수 초기점과 실계수 $f$ 로는 실수축을 절대 떠나지 못한다.

반대로 $f(x)=x^2+1$ 에 $(0,1,2)$ 를 주면 보간 포물선이 곧 $f$ 자신이라 한 번에 $\pm i$ 중 하나를 정확히 낸다. 이차식에서 뮬러가 정확하다는 건 할선법이 일차식에서 정확한 것과 같은 이야기다.

5. 다항식의 모든 근 — 디플레이션

뮬러 방법이 오래 살아남은 무대는 다항식의 근 전부를 구하는 일이다. 전형적인 흐름은 이렇다.

1. 뮬러로 근 $r_1$ 하나를 찾는다(복소수일 수 있다).
2. 합성 나눗셈으로 $p(x)/(x-r_1)$ 을 만들어 차수를 하나 내린다(디플레이션).
3. 줄어든 다항식에서 다음 근을 찾고, 반복한다.
4. 찾은 근들을 원래 다항식에 대고 뉴턴법이나 뮬러로 몇 번 더 다듬는다(polishing).

4단계가 빠지면 안 된다. 디플레이션은 근의 오차를 다음 몫다항식 계수에 그대로 전가하므로, 뒤에 찾는 근일수록 오차가 쌓인다. 관례적으로 절댓값이 작은 근부터 찾고 걷어 내는 게 안정적이다. 『Numerical Recipes』 같은 고전 교재가 뮬러를 다항식 근 절에서 라게르 방법과 나란히 소개하는 이유가 이것이다.

요즘 범용 다항식 근 계산은 대체로 동반 행렬의 고유값(NumPy roots, MATLAB roots)이나 젠킨스-트라우브 알고리즘으로 간다. QR 알고리즘이 모든 근을 한꺼번에, 안정적으로 내주기 때문이다. 뮬러가 여전히 쓸모 있는 곳은 $f$ 가 다항식이 아닌 경우다.

6. 비다항식 복소 근 — 분산 관계

시뮬레이션에서 복소근이 필요한 대표 상황은 선형 안정성 해석이다. 도파관·플라스마·유동 안정성 문제의 분산 관계 $D(\omega, k) = 0$ 은 대개 초월함수(베셀 함수, 플라스마 분산함수, 수치적으로 적분한 행렬식 등)라 다항식 도구를 못 쓴다. 근 $\omega = \omega_r + i\omega_i$ 의 허수부가 성장률이고, 이게 양수냐 음수냐가 곧 불안정성 판정이다.

이때 뮬러는 다음 이유로 손에 잘 맞는다.

• 도함수가 필요 없다. $D$ 한 번 계산이 행렬식이나 사격법 한 번이면 해석적 도함수는 사치다.
• 복소수를 자연스럽게 다룬다. 실수 진동수 근처의 초기점에서 출발해도 감쇠·성장 근으로 걸어 들어간다.
• 연속법과 궁합이 좋다. 파라미터 $k$ 를 조금씩 바꾸며 직전 세 $k$ 에서 찾은 근으로 다음 초기점을 외삽하면, 분지(branch) 하나를 길게 추적할 수 있다. 수치 연속법의 예측 단계를 대신하는 셈이다.

비선형 고유값 문제 $\det T(\lambda) = 0$ 에서 $\lambda$ 하나씩 잡아내는 데도 같은 이유로 쓰인다. 다만 근이 촘촘히 붙어 있으면 다른 근으로 건너뛰기 쉬우니, 찾은 근을 $D(\omega)/(\omega - \omega_1)$ 처럼 나눠 내는 암묵적 디플레이션을 함께 쓴다.³

7. 약점

• 초기점 셋이 필요하다. 하나만 알면 $x$, $x\pm h$ 처럼 인위적으로 만든다. 이 $h$ 가 너무 작으면 첫 포물선이 상쇄 오차투성이고, 너무 크면 엉뚱한 근으로 간다.
• 근을 가두지 않는다. 실수 구간에 근이 있다는 걸 알아도 반복이 구간 밖, 심지어 복소평면으로 나간다. 실수근을 안전하게 원하면 브렌트 방법이 맞다.
• 중복근에서 1차로 떨어진다. 할선법·뉴턴법과 같은 운명이다. 중복도를 알면 보정할 수 있지만 대개는 모른다.
• 세 점이 거의 같은 값이면 포물선이 퇴화한다. $h_1+h_2$ 로 나누는 곳에서 0 나누기를 막는 보호 코드가 필요하다.

8. 관련 문서

• 할선법 · 역 이차 보간 · 뉴턴-랩슨법 · 브렌트 방법 · 가위치법
• 라게르 방법 · 젠킨스-트라우브 알고리즘 · QR 알고리즘 · 보간과 근사
• 수치 연속법 · 사격법 · 스테펜센 방법

9. Footnotes

1. 같은 뮬러가 리드-뮬러 부호와 비동기 회로의 뮬러 C 소자에도 이름을 남겼다. 한 사람이 근 찾기·부호 이론·회로를 다 건드린 1950년대 전산 초창기다운 이력. ↩

2. 근의 공식을 “유리화한 꼴”로 쓰는 건 수치해석 1주차 국룰인데, 이차방정식 푸는 코드의 절반은 여전히 교과서 꼴로 짜여 있다. 상쇄 오차는 조용히 온다. ↩

3. 찾은 근으로 나눠 버리면 같은 근으로 다시 수렴할 일이 없다. 대신 나눈 근이 조금이라도 틀렸으면 그 근처에 가짜 극이 생긴다. 공짜 점심은 복소평면에도 없다. ↩