뉴턴법

뉴턴법은 $f(r) = 0$을 만족하는 수 r, 즉 f의 근을 한 단계를 반복해 근사합니다. 현재 추정값 $x_n$에서 그래프의 $(x_n, f(x_n))$ 지점에 접선을 그으면 $L(x) = f(x_n) + f'(x_n)(x - x_n)$입니다. $x_n$ 근처에서 접선은 곡선과 가깝게 유지되므로, 접선이 x축과 만나는 위치는 곡선의 교점을 더 잘 추정합니다. $L(x) = 0$을 풀면 다음 추정값을 얻습니다. 그래프의 각 단계는 $x_n$에서 희미한 점선을 따라 곡선으로 간 뒤, 접선을 따라 축으로 갑니다.

오차를 $e_n = x_n - r$이라고 합시다. r이 단순근이고($f'(r) \ne 0$), f의 이계도함수가 연속이면 $x_n$이 r에 가까워질 때 단계의 테일러 전개는 $e_{n+1} \approx \frac{f''(r)}{2f'(r)}\,e_n^2$를 줍니다. 오차를 제곱하면 정확한 자릿수가 대략 두 배가 됩니다. x² − 2를 x₀ = 1에서 시작하면 오차는 0.086, 0.0025, 2.1 × 10⁻⁶, 1.6 × 10⁻¹²이고, 표시값은 $e_n/e_{n-1}^2$이 $1/(2\sqrt2) \approx 0.354$에 가까워지는 것을 보여줍니다. 근에서 멀리 떨어져 있으면 이런 보장은 없습니다. $f''(r) = 0$이면 이차항이 사라져 더 빨라집니다. arctan x의 오차는 약 $-\tfrac23 e_n^3$로, 단계마다 이전 오차의 세제곱에 비례합니다.

다음 단계에는 $f'(x_n) \ne 0$이 필요합니다. 수평인 접선은 축과 만나지 않고, 거의 수평인 접선은 축과 멀리서 만납니다. x² − 2를 0.1에서 시작하면 첫 단계는 10.05에 닿습니다. 멀리 벗어나지 않아도 방법이 실패할 수 있습니다. x³ − 2x + 2에서 0의 접선은 1에 닿고, 1의 접선은 다시 0에 닿으며, 0에 가까운 시작점도 이 주기로 끌려갑니다. 수열은 유계이지만 극한이 없습니다. arctan x에는 $2\alpha = (1 + \alpha^2)\arctan\alpha$을 만족하는 경계 α ≈ 1.3917이 있습니다. |x₀| < α인 시작점은 수렴하고, 경계 밖의 시작점은 매번 반대쪽의 더 먼 점에 닿습니다. ‘모든 시작점’은 각 시작점의 결과에 따라 x축을 색칠합니다. x³ − 2x + 2에서는 [−3, 3]의 약 5분의 1이 주기로 들어가며, 접선이 수평인 $\pm\sqrt{2/3}$ 쪽으로 몰리는 좁은 띠도 포함됩니다. 복소수에서 시작하면 이 띠들은 뉴턴 프랙털이 됩니다.

중근에서는 $f'(r) = 0$도 성립하여 이차 수렴이 사라집니다. $(x - 1)^2$의 단계는 정확히 $x_{n+1} = (x_n + 1)/2$이므로 오차가 단계마다 절반이 됩니다. 이는 선형 수렴으로, 정확한 소수 자릿수가 하나 늘 때마다 약 3.3단계가 필요합니다. 중복도가 m인 근의 근처에서 비율 $e_{n+1}/e_n$은 $(m - 1)/m$로 갑니다.