뉴턴-랩슨법

1. 개요

뉴턴-랩슨법 Newton–Raphson Method
분야	수치해석 × 근 찾기
목적	비선형 방정식 f(x) = 0 의 근
수렴 차수	2차 (국소적 · 단순근)
수렴 상수	C = |f″(x*)| / 2|f′(x*)|
필요 정보	함수값 f 와 도함수 f′
다변수판	야코비안 선형계 풀이 반복

접선을 긋고, 그 접선이 만나는 x축 위 점으로 점프한다. 될 때까지.

뉴턴-랩슨법(Newton–Raphson method)은 비선형 방정식 $f(x)=0$의 근을 접선 근사를 반복 적용하여 찾아가는 수치해석 기법이다. 아이작 뉴턴과 조지프 랩슨이 17세기에 각각 정립했으며¹, 반복식은 다음과 같다.

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

간단해 보이는 이 한 줄이 시뮬레이션 세계의 뒤편에서 어마어마한 양의 일을 하고 있다. 비선형 구조해석의 평형 반복, SIMPLE 알고리즘 같은 CFD 압력-속도 연성, 암시적 시간 적분의 내부 방정식 풀이 등 “비선형 방정식을 풀어야 한다”는 상황이 나오면 십중팔구 뉴턴이 등장한다. 현대 수치 시뮬레이션의 숨은 일꾼이라 해도 과언이 아니다.

2. 반복식 유도

발상은 테일러 전개다. 근 근처에서 $f$를 1차까지 전개하면

$$f(x_{n+1}) \approx f(x_n) + f'(x_n)(x_{n+1} - x_n)$$

우리가 원하는 것은 $f(x_{n+1}) = 0$이므로, 이를 $x_{n+1}$에 대해 풀면

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

즉 뉴턴법은 매 스텝 “곡선을 접선으로 대신”하고, 그 접선이 x축과 만나는 지점으로 뛰어넘는 것을 반복한다. 곡선을 국소적으로 직선이라 우기는 뻔뻔함이 이 방법의 힘이자 약점이다. 버려진 꼬리항이 2차라는 사실(절단오차의 라그랑주 나머지항)이 뒤에 나오는 2차 수렴의 뿌리다.

3. 기하학적 의미: 접선

기하학적으로 뉴턴법은 접선 스케이팅이다. 현재 추정값 $x_n$에서 곡선에 접선을 긋는다. 그 접선이 x축과 만나는 점이 다음 추정값 $x_{n+1}$이 된다. 곡선이 완만하고 근처에 근이 있으면, 접선의 교점은 진짜 근에 놀랍도록 빠르게 다가간다.

뉴턴법은 곡선을 믿지 않는다. 오직 지금 이 순간의 접선만 믿는다. 그 신념이 통할 때는 마법 같지만, 배신당하면 우주 밖으로 튕겨 나간다.

이 접선 해석 덕분에 뉴턴법은 손으로 그림을 그려가며 이해하기 좋고, 왜 특정 상황에서 실패하는지도 그림으로 바로 보인다(후술).

4. 2차 수렴

뉴턴법의 최대 매력은 2차 수렴(quadratic convergence)이다. 근 $x^*$ 근처에서 오차 $e_n = x_n - x^*$가

$$|e_{n+1}| \approx C\, |e_n|^2, \qquad C = \frac{|f''(x^*)|}{2\,|f'(x^*)|}$$

로 줄어든다. 이게 무슨 뜻이냐면, 정답과 일치하는 유효숫자 자릿수가 매 스텝 대략 두 배로 늘어난다는 것이다. 오차가 $10^{-2}$였다면 다음엔 $10^{-4}$, 그다음엔 $10^{-8}$, 그다음엔 $10^{-16}$ — 서너 번 반복이면 배정밀도 한계에 도달한다. 이 무지막지한 속도가 뉴턴법이 근 찾기의 왕좌를 지키는 이유다.

수렴 상수 $C$가 곱해진다는 점은 실무에서 의미가 있다. $f'(x^*)$가 작은(= 곡선이 x축과 얕은 각으로 만나는) 문제나 $f''$가 큰 문제는 $C$가 커져, 2차 수렴이라도 처음 몇 스텝은 답답하게 기어간다. 반대로 $C$가 작으면 첫 스텝부터 자릿수가 훅 늘어난다.

4.1. 검산: 제곱근 2 구하기

$\sqrt{2}$를 찾는 문제, 즉 $f(x) = x^2 - 2$를 $x_0 = 1$에서 배정밀도로 돌린 실제 반복값이다. $f'(x^*) = 2\sqrt{2}$, $f''=2$ 이므로 이론적 수렴 상수는 $C = 2/(2 \cdot 2\sqrt{2}) = 1/(2\sqrt{2}) \approx 0.3536$이다.

반복 $n$	$x_n$	오차 크기	직전 오차 제곱 대비 비
1	1.5	8.58e-2	—
2	1.4166666666666667	2.45e-3	0.333
3	1.4142156862745099	2.12e-6	0.408
4	1.4142135623746899	1.60e-12	0.354
5	1.4142135623730951	0 (배정밀도 한계)	—

오차비가 이론값 0.354로 수렴하는 것이 보이고, 네 번째 반복에서 이미 12자리, 다섯 번째에서 배정밀도 전체를 확보한다. 2차 수렴이 “매 스텝 자릿수 2배”라는 주장의 구체적 증거다. 여기서 초기값을 $x_0 = 1$이 아니라 $x_0 = 10^6$로 주면 수렴하기는 하지만 처음 20스텝가량은 단순히 값을 반씩 줄이는 데 쓴다 — 멀리서는 1차, 가까이서는 2차라는 뉴턴법의 이중 인격이 여기서 드러난다.

5. 국소 수렴과 뉴턴-칸토로비치 조건

위의 2차 수렴은 국소적(local) 성질이다. 정리의 형태로 적으면, $x^*$가 단순근($f'(x^*) \ne 0$)이고 $f''$가 근 주변에서 연속(또는 $f'$가 립시츠 연속)이면, $x^*$를 포함하는 어떤 근방이 존재해 그 안에서 출발한 모든 초기값이 2차로 수렴한다. 거꾸로 말하면 “충분히 가까우면”이라는 단서가 정리 본문에 박혀 있고, 얼마나 가까워야 충분한지는 정리가 알려주지 않는다.

초기값에서 직접 확인할 수 있는 형태의 충분조건이 뉴턴-칸토로비치 정리(Newton–Kantorovich theorem)다. 다변수 문제 $\mathbf{F}(\mathbf{x}) = \mathbf{0}$에서 $\|\mathbf{J}(\mathbf{x}_0)^{-1}\| \le \beta$, 첫 스텝 크기 $\|\mathbf{J}(\mathbf{x}_0)^{-1}\mathbf{F}(\mathbf{x}_0)\| \le \eta$, 야코비안의 립시츠 상수 $\gamma$를 잡았을 때

$$h = \beta\gamma\eta \le \tfrac{1}{2}$$

이면 해가 존재하고 뉴턴 반복이 그 해로 수렴한다.² 이 조건은 “야코비안이 너무 특이하지 않고($\beta$ 유계), 첫 스텝이 너무 크지 않고($\eta$ 작음), 야코비안이 너무 급변하지 않으면($\gamma$ 작음) 된다”는 직관을 정량화한 것이다. 실무적 함의는 셋 중 통제 가능한 것이 보통 $\eta$뿐이라는 것 — 그래서 전역화 전략의 대부분이 첫 스텝을 짧게 자르는 방향으로 설계된다.

6. 다변수판과 야코비안

실제 시뮬레이션에서 푸는 것은 스칼라 방정식 하나가 아니라 미지수 수천~수백만 개의 연립 비선형 방정식 $\mathbf{F}(\mathbf{x}) = \mathbf{0}$이다. 이 경우 도함수 $f'$의 자리를 야코비안 행렬(Jacobian) $\mathbf{J}$가 대신한다.

$$\mathbf{J}(\mathbf{x}_n)\, \Delta \mathbf{x} = -\mathbf{F}(\mathbf{x}_n), \qquad \mathbf{x}_{n+1} = \mathbf{x}_n + \Delta \mathbf{x}$$

여기서 $J_{ij} = \partial F_i / \partial x_j$이다. 스칼라판에서 $f'$로 나누던 것이, 다변수판에서는 야코비안 선형계를 푸는 것으로 바뀐 셈. 역행렬을 구하지 않는다는 점이 중요하다 — $\mathbf{J}^{-1}$을 명시적으로 만드는 것은 희소행렬 구조를 통째로 버리는 짓이고, 실무 코드는 예외 없이 선형계를 직접법이나 크리로프 부분공간법으로 푼다.

문제는 이 선형계 풀이가 매 반복마다 등장한다는 것이라, 대형 문제에서는 야코비안을 만들고 푸는 비용이 전체 계산의 대부분을 잡아먹는다. 그래서 다음 변종들이 쓰인다.

• 수정 뉴턴법(modified Newton): 야코비안을 매 반복 새로 만들지 않고 몇 스텝 재활용한다. 수렴 차수는 떨어지지만 스텝당 비용이 급감해 총시간이 줄 수 있다. 암시적 시간 적분 코드가 기본으로 쓰는 전략.
• 준-뉴턴법(quasi-Newton): 야코비안(또는 헤시안)을 함수값 차이로 근사 갱신한다. BFGS·브로이든(Broyden) 계열이 대표.
• 뉴턴-크리로프법(Newton–Krylov): 야코비안을 행렬로 만들지 않고, 크리로프 반복이 필요로 하는 행렬-벡터 곱만 유한차분 방향미분으로 공급한다.

$$\mathbf{J}\mathbf{v} \approx \frac{\mathbf{F}(\mathbf{x} + \epsilon \mathbf{v}) - \mathbf{F}(\mathbf{x})}{\epsilon}$$

이 야코비안-프리(JFNK) 방식은 대규모 CFD·핵융합·복사수송 코드의 표준이 됐고, $\epsilon$ 선택이 반올림오차와 절단오차의 절충이라는 점까지 수치미분과 판박이다. 내부 크리로프 반복을 어디서 끊을지 정하는 아이젠슈타트-워커(Eisenstat–Walker) 규칙 같은 장치가 비정확 뉴턴법이라는 이름으로 여기 붙는다.³ 야코비안을 손으로 유도하기 싫으면 자동 미분으로 기계가 만들게 하는 것도 요즘은 평범한 선택이다.

7. 수렴 실패: 발산·진동·중근

뉴턴법은 빠르지만 성질이 사납다. 초기값을 잘못 주면 여러 방식으로 배신한다.

실패 유형	원인	증상
발산	초기값이 근에서 멀거나 곡률 심함	접선이 엉뚱한 곳으로 튕겨 무한대로
진동	두 점 사이를 접선이 왕복	같은 값 근처를 영원히 오감
정체	도함수가 0에 가까움	접선이 거의 수평, 다음 점이 폭발
느린 수렴	중근(다중근)	2차 수렴이 1차로 강등

특히 도함수가 0에 가까운 지점에 발을 디디면, 나눗셈이 폭발해 다음 추정값이 우주 밖으로 날아간다. 진동의 교과서적 예가 $f(x) = x^3 - 2x + 2$에 $x_0 = 0$을 주는 경우로, 반복이 $0 \to 1 \to 0 \to 1$을 영원히 왕복한다(주기 2 순환).

중근에서의 강등은 정량화된다. 근 $x^*$의 중복도가 $m$이면 뉴턴 반복은 2차가 아니라 수렴 인자 $(m-1)/m$의 1차 수렴이 된다. $f(x) = (x-1)^3$($m=3$), $x_0 = 1.5$로 돌린 실제 오차는 0.3333 → 0.2222 → 0.1481 → 0.0988 → 0.0658 로, 오차비가 정확히 $2/3$다. 이를 알고 있다면 처방도 명확하다. 중복도를 알 때는

$$x_{n+1} = x_n - m\,\frac{f(x_n)}{f'(x_n)}$$

로 스텝을 $m$배 늘리면 2차 수렴이 복구된다(위 3차 예제는 이 수정식으로 한 스텝에 정확히 근에 도달한다). 중복도를 모를 때는 $u = f/f'$에 뉴턴법을 적용하는 방법이 있다 — $u$는 중근을 단순근으로 바꾸기 때문이다. 대신 $f/f'$ 계산에 자리수 손실이 끼어들어 정확도 바닥이 올라간다는 대가를 치른다.⁴

8. 길들이기: 전역화 전략

이런 야생성을 통제하는 장치를 통칭 전역화(globalization)라 부른다. 뉴턴 방향은 그대로 두고 얼마나 갈지만 손대는 것이 공통 아이디어다.

• 감쇠 뉴턴 / 라인서치: 스텝을 $\mathbf{x} + \lambda \Delta\mathbf{x}$로 쓰고 $\|\mathbf{F}\|$가 충분히 줄어들 때까지 $\lambda$를 $1, \tfrac12, \tfrac14, \dots$로 줄인다(아르미호 백트래킹). 구조해석·CFD 솔버의 “relaxation factor”가 대개 이것이다.
• 신뢰 영역 방법: 모델을 믿을 반경을 정해 두고 그 안에서만 움직인다. 야코비안이 특이에 가까울 때 라인서치보다 견고하다.
• 하이브리드: 느리지만 안전한 이분법·브렌트법으로 근 근처까지 몰아넣은 뒤 마지막에 뉴턴으로 갈아탄다. 1차원 근 찾기 라이브러리의 표준 구성.
• 수치 연속법(continuation / 하중 증분): 문제를 매개변수 $t$로 연속 변형해 $t$를 조금씩 키우며, 앞 단계 해를 다음 단계 초기값으로 쓴다. 비선형 구조해석의 하중 증분과 CFD의 의사시간 전진(pseudo-transient)이 모두 이 범주다.

실무 조언은 하나로 요약된다. 뉴턴법의 품질은 반복식이 아니라 초기값과 전역화가 결정한다. 반복식은 이미 최적이고, 남은 자유도는 그 둘뿐이다.

9. 시뮬레이션에서의 활용

뉴턴-랩슨법은 비선형이 등장하는 거의 모든 시뮬레이션의 심장에 박혀 있다.

• 비선형 구조해석: 대변형·소성·접촉처럼 강성이 변위에 의존하는 문제는 하중을 증분으로 나눠 각 증분마다 뉴턴-랩슨 평형 반복을 돌린다. 유한요소 구조 코드의 “iteration” 카운터가 바로 이것이다.
• SIMPLE 알고리즘과 CFD: 비선형 대류항과 압력-속도 연성을 다루는 반복 과정에서 뉴턴형 갱신이 핵심 역할을 한다. 완전 결합(coupled) 솔버는 아예 전체 시스템에 뉴턴을 적용한다.
• 암시적 시간 적분: 강성 ODE를 룽게-쿠타법의 암시적 도식이나 BDF로 풀 때, 매 스텝 등장하는 비선형 방정식을 뉴턴법으로 푼다. 이때는 수렴 판정을 느슨하게 잡고 스텝을 줄이는 쪽이 이득이라, 보통 2~3반복에서 끊는다.
• 회로·소자 해석: SPICE 같은 회로 시뮬레이터는 다이오드·트랜지스터의 비선형 소자 방정식을 매 시점 뉴턴-랩슨으로 푼다. 지수함수 소자 모델이 쉽게 폭발하므로 전압 제한(limiting)·gmin 스테핑 같은 전역화가 필수다.
• 최적화: 경사하강법 계열에서 한 걸음 더 나간 2차 방법들이 결국 $\nabla f = 0$에 뉴턴법을 적용한 것이다. 가우스-뉴턴법·레벤버그-마쿼트도 같은 족보.

요컨대 “비선형 방정식을 반복으로 푼다”는 문구가 나오는 순간, 그 뒤에는 거의 항상 뉴턴이 있다. 빠르고, 우아하고, 가끔 발산하지만 — 그래도 대체할 것이 마땅치 않은, 수치 시뮬레이션의 국민 알고리즘이다.

10. 관련 문서

• 비선형 구조해석 · SIMPLE 알고리즘
• 준-뉴턴법 · 라인서치 · 신뢰 영역 방법
• 자코비안 행렬 · 자동 미분 · 수치미분
• 크리로프 부분공간법 · 전처리기
• 절단오차 · 부동소수점 연산 · 조건수
• 수치 연속법 · 바나흐 고정점 정리 · 이분법
• 룽게-쿠타법 · SPICE · 경사하강법 · 가우스-뉴턴법

11. Footnotes

1. 뉴턴의 원래 방법(1669, De analysi)은 사실 도함수를 명시적으로 쓰지 않고 다항식에 대해 항을 대입·정리하는 절차였고, 랩슨(1690)이 지금과 더 비슷한 반복 형태로 다듬었다. 미분 표기로 딱 떨어지게 정리한 것은 후대(주로 심프슨, 1740)의 공이라, 엄밀히는 지분이 셋 이상이다. 이름에 지분을 다 넣으면 “뉴턴-랩슨-심프슨법”이 되는데, 아무도 그렇게 부르지 않는다. ↩

2. 칸토로비치(L. V. Kantorovich)는 이 정리로 함수해석의 도구를 수치해석에 들여왔다. 정작 그가 노벨 경제학상(1975)을 받은 건 선형계획법 쪽 업적이다 — 자원배분을 최적화하다가 수렴 정리까지 남긴 셈. ↩

3. 비정확 뉴턴의 교훈은 “선형계를 정확히 풀 필요가 없다”는 것이다. 어차피 야코비안 자체가 근사인데 그 선형계를 12자리까지 푸는 것은 낭비다. 바깥 반복의 잔차 감소율에 맞춰 안쪽 허용오차를 느슨하게 잡는 것이 국룰이며, 이걸 안 하면 크리로프 반복에 시간을 갈아넣고도 총 반복 수는 그대로다. ↩

4. 뉴턴법의 초기값 민감성을 예술로 승화한 것이 뉴턴 프랙탈(Newton fractal)이다. 복소평면에서 어떤 근으로 수렴하는지 색칠하면, 근들의 경계가 무한히 복잡한 프랙탈 무늬를 이룬다. 발산하던 알고리즘도 잘 칠하면 미술관에 걸린다. ↩