브로이던 방법

1. 개요

브로이던 방법 Broyden's Method
고안	찰스 G. 브로이던 (Charles G. Broyden, 1965)
푸는 것	비선형 연립방정식 F(x) = 0
핵심	야코비안을 할선 조건을 만족하는 랭크-1 갱신으로 근사
반복당 비용	함수 평가 1회 + O(n2) (뉴턴은 야코비안 + O(n3))
수렴	국소 초선형 (2차 아님)
변종	좋은(1형) · 나쁜(2형) 브로이던, 수정 브로이던 혼합

야코비안을 매번 새로 사지 말고, 지난 걸 고쳐 쓰자. 한 방향만.

브로이던 방법(Broyden’s method)은 비선형 연립방정식 $\mathbf F(\mathbf x) = \mathbf 0$ 을 풀 때 뉴턴-랩슨법의 자코비안 행렬을 매 반복 새로 계산하는 대신, 직전 스텝에서 관측한 함수값 변화와 일치하도록 근사 야코비안을 랭크-1 행렬로 고쳐 나가는 준뉴턴 기법이다. 1965년 영국의 수치해석가 찰스 브로이던이 발표했고, 1차원 할선법을 다변수로 옮긴 가장 자연스러운 일반화로 꼽힌다.

준-뉴턴법 문서는 최적화 쪽(BFGS·L-BFGS)을 중심으로 할선 조건 계열 전반을 소개한다. 이 문서는 그 뿌리인 방정식 풀이용 브로이던 갱신만 판다 — 최소 변경 원리, 셔먼-모리슨으로 역행렬을 직접 갱신하는 트릭, 초선형 수렴의 정확한 의미, 그리고 의외로 큰 응용처인 밀도 범함수 이론의 자기일관 계산까지.

2. 할선 조건과 최소 변경 원리

뉴턴법의 스텝은 $J(\mathbf x_k)\,\mathbf s_k = -\mathbf F(\mathbf x_k)$ 로 정해진다. 브로이던 방법은 $J$ 대신 근사 $B_k$ 를 쓴다. 스텝을 밟고 나면 두 가지를 관측한다.

$$\mathbf s_k = \mathbf x_{k+1} - \mathbf x_k, \qquad \mathbf y_k = \mathbf F(\mathbf x_{k+1}) - \mathbf F(\mathbf x_k).$$

새 근사가 이 관측과 맞으려면 할선 조건 $B_{k+1}\mathbf s_k = \mathbf y_k$ 를 만족해야 한다. 그런데 $n$ 차원에서 이 조건은 식이 $n$ 개, 미지수가 $n^2$ 개라 해가 무수히 많다. 브로이던은 그중 기존 $B_k$ 에서 가장 덜 바뀌는 것을 골랐다.

$$B_{k+1} = \arg\min_{B\,\mathbf s_k = \mathbf y_k} \|B - B_k\|_F \quad\Longrightarrow\quad B_{k+1} = B_k + \frac{(\mathbf y_k - B_k\mathbf s_k)\,\mathbf s_k^{\mathsf T}}{\mathbf s_k^{\mathsf T}\mathbf s_k}.$$

해석이 깔끔하다. $\mathbf s_k$ 방향으로는 관측값에 맞추고, $\mathbf s_k$ 와 직교하는 모든 방향 $\mathbf z$ ($\mathbf z^{\mathsf T}\mathbf s_k = 0$) 에 대해서는 $B_{k+1}\mathbf z = B_k\mathbf z$ 로 아무것도 안 바꾼다. 정보가 없는 방향은 건드리지 않는다는 원칙이다. 이 형태를 흔히 좋은 브로이던(good Broyden, 1형)이라 부른다.

3. 역행렬을 직접 갱신하기

$B_{k+1}$ 을 갱신해도 매번 선형계 $B\mathbf s = -\mathbf F$ 를 풀어야 하면 $O(n^3)$ 이 남는다. 랭크-1 갱신의 역행렬은 셔먼-모리슨 공식으로 닫힌꼴이 있으므로, $H_k = B_k^{-1}$ 을 직접 들고 다니면 된다.

$$H_{k+1} = H_k + \frac{(\mathbf s_k - H_k\mathbf y_k)\,\mathbf s_k^{\mathsf T} H_k}{\mathbf s_k^{\mathsf T} H_k \mathbf y_k}.$$

이제 스텝은 행렬-벡터 곱 $\mathbf s_k = -H_k \mathbf F(\mathbf x_k)$ 하나다. 반복당 비용이 함수 평가 1회 + $O(n^2)$ 로 떨어진다. 뉴턴법은 수치미분으로 야코비안을 만들면 함수 평가가 $n+1$ 회, 분해가 $O(n^3)$ 이다. 함수 평가가 비싼(예: 내부에 시뮬레이션이 통째로 들어 있는) 문제에서 이 차이가 결정적이다.

역행렬 쪽에서 최소 변경을 하면 다른 공식이 나온다.

$$H_{k+1} = H_k + \frac{(\mathbf s_k - H_k\mathbf y_k)\,\mathbf y_k^{\mathsf T}}{\mathbf y_k^{\mathsf T}\mathbf y_k}.$$

이게 나쁜 브로이던(bad Broyden, 2형)이다. 브로이던 본인이 1965년 논문에서 두 갱신을 모두 제시했고, 첫 번째가 실험에서 더 잘 돼서 “좋은” 쪽이 됐다.¹ 다만 이름과 달리 나쁜 브로이던이 더 잘 듣는 문제도 꽤 있고, SciPy는 둘을 broyden1·broyden2로 나란히 제공한다.

4. 초선형 수렴의 정확한 의미

브로이던 방법은 해 근처에서 초선형(superlinear) 수렴한다. 즉 $\|\mathbf x_{k+1} - \mathbf x^*\| / \|\mathbf x_k - \mathbf x^*\| \to 0$ 이지만, 뉴턴의 2차 수렴은 아니다. 데니스와 모레(1974)는 이것을 정확히 특징지었다.²

$$\lim_{k\to\infty} \frac{\|(B_k - J(\mathbf x^*))\,\mathbf s_k\|}{\|\mathbf s_k\|} = 0 \iff \text{초선형 수렴}.$$

중요한 점은 $B_k$ 가 진짜 야코비안으로 수렴할 필요가 없다는 것이다. 실제로 브로이던의 $B_k$ 는 대개 $J(\mathbf x^*)$ 로 수렴하지 않는다. 스텝 방향 $\mathbf s_k$ 위에서만 맞으면 충분하다. “야코비안을 근사한다”는 설명이 사실 반쯤만 맞는 이유다 — 근사하는 건 스텝이 실제로 지나가는 방향의 야코비안 작용이다.

선형 문제 $A\mathbf x = \mathbf b$ 에 적용하면 더 강한 결과가 있다. 게이(1979)는 갱신이 잘 정의되는 한(분모가 0이 되지 않는 한) 브로이던 방법이 최대 $2n$ 스텝 안에 정확히 끝난다는 것을 보였다.³ 비선형 문제에서는 이로부터 $2n$ 스텝 단위의 2차 수렴이 따라 나온다.

5. 검산 — 뉴턴과 나란히

$\mathbf F(x, y) = (x^2 + y^2 - 4,\; e^x + y - 1)$ 을 $(1, -1.5)$ 에서 출발해 풀었다. 해는 $(1.00417, -1.72964)$ 다. 브로이던은 $B_0 = J(\mathbf x_0)$ 로 시작했다.

반복	뉴턴 $\lVert F\rVert$	좋은 브로이던	나쁜 브로이던
0	7.8e-1	7.8e-1	7.8e-1
1	6.0e-2	6.0e-2	6.0e-2
2	2.3e-4	3.4e-3	3.0e-3
3	3.4e-9	1.5e-5	1.7e-5
4	9.9e-16	3.5e-8	7.1e-8
5		2.7e-10	7.5e-10
6		2.0e-13	5.6e-13

첫 스텝은 $B_0 = J$ 라서 셋이 똑같다. 그 뒤 뉴턴은 지수가 매번 두 배가 되는 2차 수렴, 브로이던은 비율이 계속 줄어드는 초선형 수렴의 전형을 보인다. 반복 수는 6 대 4로 브로이던이 많지만, 뉴턴이 매 반복 야코비안을 새로 만든 것과 달리 브로이던은 첫 야코비안 이후 함수 평가 1회씩만 썼다.

선형 검산도 했다. 무작위 $6 \times 6$ 선형계를 $B_0 = 3I$ 로 시작하자 정확히 12스텝($= 2n$)에 잔차 $2.5\times10^{-16}$ 로 끝났다. 게이의 상한이 그대로 찍혔다.

6. 실무 — 초기값, 전역화, 그리고 DFT

초기 $B_0$. 유한차분 야코비안을 한 번 계산해 쓰는 것이 가장 안전하다. 항등행렬의 스칼라배 $B_0 = \beta I$ 도 흔한데, 이 경우 첫 몇 스텝은 사실상 고정점 반복이라 수렴이 느리게 시작한다.

전역화. 국소 수렴만 보장되므로 멀리서 출발하면 뉴턴-랩슨법과 같은 장치 — 선탐색, 신뢰 영역 방법 — 가 필요하다. 다만 브로이던 스텝은 $\|\mathbf F\|^2$ 의 하강 방향이라는 보장이 없어 선탐색이 실패할 수 있다. 그때는 야코비안을 다시 계산해 $B$ 를 리셋하는 게 국룰이다.

메모리. $n$ 이 크면 $n \times n$ 밀집 행렬 $H_k$ 를 들 수 없다. 대신 $H_0$ 와 갱신 벡터 쌍 $(\mathbf s_i, \ldots)$ 만 저장해 곱을 그때그때 재구성하는 제한 메모리 판을 쓴다. 최근 $m$ 개만 남기면 메모리가 $O(mn)$ 이다.

자기일관장(SCF) 혼합. 브로이던의 가장 큰 현역 무대는 의외로 전자구조 계산이다. 밀도 범함수 이론의 자기일관장(SCF) 반복은 입력 밀도 $\rho_{\text{in}}$ 을 넣어 출력 밀도 $\rho_{\text{out}}$ 을 얻고, $\rho_{\text{out}} - \rho_{\text{in}} = 0$ 을 푸는 고정점 문제다. 이 잔차 함수에 브로이던을 적용한 것이 브로이던 혼합이고, 존슨(1988)의 수정 브로이던 방법은 VASP·Quantum ESPRESSO 같은 평면파 DFT 코드의 기본 전하 밀도 혼합기 바탕이 됐다.⁴ 팡·사드(2009)는 이 계열과 앤더슨 가속(앤더슨 혼합, DIIS)이 모두 다중 할선(multisecant) 갱신의 변종이라는 것을 보여 하나의 틀로 묶었다.

큰 문제의 대안. 함수 평가가 싸고 야코비안-벡터 곱만 근사할 수 있다면 뉴턴-크리로프법(JFNK)이 보통 더 낫다. 브로이던은 반복 사이에 정보를 누적하고, JFNK는 매 반복 그 자리에서 크리로프 부분공간을 새로 탐색한다. 함수 평가가 극단적으로 비싸면 누적 쪽이, 문제가 크고 전처리기가 있으면 탐색 쪽이 이긴다.

7. 관련 문서

• 준-뉴턴법 · 뉴턴-랩슨법 · 자코비안 행렬 · 뉴턴-크리로프법
• 할선법 · 셔먼-모리슨 공식 · 고정점 반복 · 앤더슨 가속
• 수치미분 · 신뢰 영역 방법 · 가우스-뉴턴법
• 밀도 범함수 이론 · 하트리-폭 방법

8. Footnotes

1. “좋은”과 “나쁜”이라는 이름은 브로이던 1965년 실험 결과에서 붙은 별명이 굳은 것이다. 수치해석 역사에서 이름이 성능 평가를 고정해 버린 대표 사례라, 나쁜 브로이던 입장에서는 꽤 억울하다. ↩

2. 이 결과가 준뉴턴 수렴 이론의 대부분을 떠받친다. BFGS·DFP의 초선형 수렴 증명도 결국 “데니스-모레 조건을 만족함을 보인다”로 귀결된다. ↩

3. 선형계를 $2n$ 스텝에 정확히 푼다는 건 켤레기울기법의 $n$ 스텝보다 느리다. 브로이던을 선형 솔버로 쓰라는 얘기가 아니라, 갱신이 정보를 버리지 않고 쌓는다는 증거로 읽는 게 맞다. ↩

4. 그래서 계산화학 하는 사람에게 “브로이던”은 근 찾기 알고리즘이 아니라 입력 파일의 혼합 옵션 이름이다. 같은 알고리즘이 분야마다 다른 얼굴로 산다. ↩