매끄러운 곡선은 한 점 근처를 확대하면 직선(접선)처럼 보인다. 그래서 복잡한 함수값을 접선으로 어림하고(선형 근사), 방정식의 근은 “접선이 0이 되는 곳”으로 거듭 옮겨 가며 찾는다(뉴턴 방법). 뉴턴 방법은 근 근처에서 한 번 반복할 때마다 맞는 자릿수가 거의 두 배로 는다. 다만 출발점이 나쁘거나 기울기가 0에 가까우면 엉뚱한 곳으로 튀거나 끝없이 맴돈다.
예시로 보기
\(\sqrt{4.1}\)을 계산기 없이 어림한다. \(f(x) = \sqrt x\)는 \(x = 4\)에서 값 2, 기울기 \(f'(4) = \frac{1}{2\sqrt4} = \frac14\)다. 4에서 0.1만큼 가면 접선을 따라 \(0.1 \times \frac14 = 0.025\) 오른다.
\[\sqrt{4.1} \approx 2 + 0.025 = 2.025 \quad (\text{참값 } 2.02485\ldots,\ \text{오차 } 1.5 \times 10^{-4})\]뉴턴 방법은 이 생각을 근 찾기에 쓴다. \(x^2 = 2\)의 근을 찾을 때 지금의 추측 \(x_n\)에서 접선을 긋고, 접선이 0이 되는 곳을 다음 추측으로 삼는다.
\(x_0 = 1\)의 접선(파랑)이 가로축과 만나는 곳이 \(x_1 = 1.5\)이고, \(x_1\)의 접선(주황)이 만나는 곳이 \(x_2 \approx 1.41667\)이다. 두 번 만에 \(\sqrt2\)와 그림에서 구별되지 않을 만큼 붙는다1.
| \(n\) | \(x_n\) | 오차 \(\vert x_n - \sqrt2\vert\) |
|---|---|---|
| 0 | 1 | 0.41 |
| 1 | 1.5 | \(8.6 \times 10^{-2}\) |
| 2 | 1.41667 | \(2.5 \times 10^{-3}\) |
| 3 | 1.4142157 | \(2.1 \times 10^{-6}\) |
| 4 | 1.41421356237469 | \(1.6 \times 10^{-12}\) |
오차가 대략 제곱씩 줄어, 맞는 자릿수가 1, 2, 5, 11로 두 배씩 는다.
정의
\(f\)가 \(a\)에서 미분 가능하면 \(a\) 근처에서
\[f(x) \approx L(x) = f(a) + f'(a)(x - a)\]이다. \(L\)은 \(a\)에서의 접선이다2. 자주 쓰는 예: \(\sin x \approx x\), \(\ln(1 + x) \approx x\), \((1 + x)^n \approx 1 + nx\) (\(x\)가 작을 때).
입력: 미분 가능한 \(f\), 그 도함수 \(f'\), 출발점 \(x_0\), 허용 오차 \(\text{tol}\), 최대 반복 횟수.
출력: \(f(x) = 0\)의 근의 어림.
x ← x₀
반복 (최대 횟수까지):
f'(x) = 0이면 실패로 멈춘다
x_new ← x − f(x) / f'(x)
|x_new − x| ≤ tol이면 x_new를 돌려준다
x ← x_new
갱신식은 \(x_n\)에서의 접선 \(y = f(x_n) + f'(x_n)(x - x_n)\)이 0이 되는 \(x\)다3.
수렴 속도. 근 \(r\)에서 \(f'(r) \ne 0\)이고 \(f\)가 두 번 미분 가능하며 출발점이 충분히 가까우면, \(\vert x_{n+1} - r\vert \approx \frac{\vert f''(r)\vert }{2\vert f'(r)\vert }\,\vert x_n - r\vert ^2\)로 이차 수렴한다. [증명 스케치: \(f\)를 \(x_n\)에서 테일러 전개해 2차 항까지 쓰면 나온다(테일러 급수)] 같은 정밀도 \(10^{-12}\)까지 \(\sqrt2\)를 구할 때 이분법은 40번, 뉴턴 방법은 5번이다.
세로축이 로그 눈금이라 이분법은 곧은 직선으로 내려간다. 한 번에 같은 비율(절반)씩 줄기 때문이다. 뉴턴 방법은 걸음마다 기울기가 더 가팔라지며 꺾여 내려간다. 맞는 자릿수가 두 배씩 늘어서다1.
실패하는 경우.
- 기울기가 0인 점에 닿으면 나눌 수 없다(\(x^2 - 2\)를 \(x_0 = 0\)에서 시작).
- 맴돈다: \(f(x) = x^3 - 2x + 2\)를 \(x_0 = 0\)에서 시작하면 \(0 \to 1 \to 0 \to 1 \to \cdots\).
- 근에서 멀리 시작하면 다른 근으로 가거나 발산한다. 그래서 실무에서는 이분법으로 근을 가둔 뒤 뉴턴 방법으로 빠르게 다듬는 식으로 섞는다.
예제
\(\sqrt2\)를 뉴턴 방법으로 구하는 첫 두 걸음을 추적한다. \(f(x) = x^2 - 2\), \(f'(x) = 2x\)라 갱신식은 \(x - \frac{x^2 - 2}{2x} = \frac12\left(x + \frac2x\right)\)다(바빌로니아 방법).
- \(x_0 = 1\): \(\frac12(1 + 2) = 1.5\).
- \(x_1 = 1.5\): \(\frac12\left(1.5 + \frac{2}{1.5}\right) = \frac12(1.5 + 1.3333) = 1.41667\).
- 멈춤 판단: 이웃 값의 차가 0.083으로 아직 크니 계속한다.
활용
- 라이브러리 구현. 제곱근·나눗셈·역수는 뉴턴 방법으로 몇 번의 곱셈만에 전체 정밀도에 이른다. 오래된 3D 게임의 “빠른 역제곱근”은 비트 조작으로 얻은 첫 추측에 뉴턴 한 걸음을 더한 것이다4.
- 최적화. 최솟값에서는 \(f' = 0\)이므로 \(f'\)에 뉴턴 방법을 쓰면 \(x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}\)이다. 곡률(이계도함수)까지 써서 경사 하강법보다 적은 걸음으로 수렴한다(다변수는 헤세 행렬).
- 어림 계산. 성장률 \(r\)이 작을 때 \(\ln(1 + r) \approx r\)이라 두 배 시간이 약 \(0.693/r\)이다(로그 계산 예제 사다리의 72의 법칙).
연결
- 선수: 도함수의 활용과 최적화
- 비교: 이분법(느리지만 늘 수렴)과 뉴턴 방법(빠르지만 출발점에 민감). 수렴 속도의 말은 수열의 극한과 e.
- 이어지는 개념: 테일러 급수(오차 분석), 미분방정식과 오일러 방법(선형 근사로 한 걸음씩)
과목별 관점
수치해석 (2-2학기). 뉴턴-랩슨 방법을 근 찾기 알고리즘으로 정리한다. 시작값 \(x_0\)에서 \(f\)와 \(f'\)를 계산하고 \(x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}\)로 고친 뒤, 상대 오차 \(\vert \epsilon_a\vert = \left\vert \frac{x_{i+1} - x_i}{x_{i+1}}\right\vert \times 100\)이 허용 오차보다 작으면 멈춘다. 반복 횟수의 상한도 함께 둔다.
예: \(f(x) = e^{-x} - x\)를 \(x_0 = 0\)에서 시작해 풀면 \(x_i\)는 \(0.5\), \(0.566311003\), \(0.567143165\), \(0.567143290\)으로, 참 오차가 11.8%, 0.147%, 0.0000220%, \(10^{-8}\)% 미만으로 준다. 오차의 자릿수가 매번 대략 두 배로 는다.
장점은 수렴하면 빠르고 시작값이 하나뿐이라는 것이다. 단점은 천천히 수렴하거나, 근을 지나쳐 실패하거나, \(f'(x_i) = 0\)이면 0으로 나누게 된다는 것이다. \(f'\)을 계산하기 어려우면 두 점의 기울기로 바꾼 할선법을 쓰고, 연립방정식이면 다변수 뉴턴 방법을 쓴다.
확인 문제
C1 f(x) = x² − 2, x₀ = 1로 뉴턴 방법을 세 번 반복한 값 x₁, x₂, x₃를 구하라.
답: \(x_1 = 1.5\), \(x_2 = \frac{17}{12} \approx 1.41667\), \(x_3 = \frac{577}{408} \approx 1.4142157\).
C2 뉴턴 방법의 갱신식 x − f(x)/f′(x)가 하는 일을 한 문장으로 설명하라.
답: 지금 점에서 곡선을 접선으로 바꾸고, 그 접선이 0이 되는 곳으로 옮겨 간다.
C3 뉴턴 방법이 근에 수렴하지 않고 맴도는 예를 들고, 이런 실패에 대비해 구현에 무엇을 넣어야 하는지 쓰라.
답: \(f(x) = x^3 - 2x + 2\)를 \(x_0 = 0\)에서 시작하면 \(0, 1, 0, 1, \dots\)로 맴돈다. 최대 반복 횟수를 두고, 기울기가 0이면 멈추며, 필요하면 이분법으로 근을 가둔 구간 안에서만 뉴턴 걸음을 받아들인다.
C4 \(f(x) = e^{-x} - x\)에 뉴턴 방법을 \(x_0 = 1\)에서 한 번 적용하라.
답: \(f(1) = e^{-1} - 1 \approx -0.632121\), \(f'(1) = -e^{-1} - 1 \approx -1.367879\). \(x_1 = 1 - \frac{-0.632121}{-1.367879} \approx 1 - 0.462117 = 0.537883\)5.
-
10_linear-approx-newton_plot.py로 그렸고, 표의 \(x_n\)과 오차(\(8.6 \times 10^{-2}\)부터 \(1.6 \times 10^{-12}\)까지), 이분법이 40번에 구간 길이 \(10^{-12}\) 이하가 되는 것을 같은 코드로 확인했다. ↩ ↩2
-
OpenStax, Calculus Volume 1, 4.2절 “Linear Approximations and Differentials” ↩
-
OpenStax, Calculus Volume 1, 4.9절 “Newton’s Method”(실패하는 경우 포함) ↩
-
“빠른 역제곱근”(fast inverse square root)은 게임 Quake III Arena의 소스 코드로 알려진 기법이다. ↩
-
10_linear-approx-newton_verify.py로 확인했다. ↩