뉴턴법

접선을 타고 내려가 방정식의 근을 찾는 씬입니다. 반복할수록 맞는 자릿수가 두 배로 늘어납니다.

곡선에서 접선을 긋고 그 직선의 근을 다음 추측으로 삼습니다. 직선으로 곡선을 대신하는 단순한 아이디어입니다. 좋은 시작점에서는 놀랍게 빠르게 수렴합니다.

예를 들면, 🧑 친구가 숨긴 숫자를 맞힐 때 힌트로 다음 추측을 정하면, 맞는 자릿수가 매번 두 배씩 늘어요. 처음엔 어림없던 답이 몇 번 만에 정확해져요.

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

예제

x2−2=0x^2 - 2 = 0에 대한 뉴턴법이 바빌로니아법과 같음을 대수적으로 증명하세요.

x−x2−22x=x+2/x2x - \frac{x^2-2}{2x} = \frac{x + 2/x}{2}
x0=1x_0 = 1에서 시작 — 4번이면 2\sqrt{2}의 10자리 이상이 맞습니다.
증명 보기

  1. f(x)=x2−2f(x) = x^2 - 2, f′(x)=2xf'(x) = 2x이므로 뉴턴 점화식은 xn+1=xn−xn2−22xnx_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n}입니다.

  2. 통분하면 2xn2−xn2+22xn=xn+2/xn2\frac{2x_n^2 - x_n^2 + 2}{2x_n} = \frac{x_n + 2/x_n}{2}로, 정확히 바빌로니아 점화식입니다.

오차가 en+1≈f′′(x∗)2f′(x∗)en2e_{n+1} \approx \frac{f''(x^*)}{2f'(x^*)} e_n^2을 따르는 이유를 설명하세요. (아이디어 수준)

en+1≈C en2,C=f′′(x∗)2f′(x∗)e_{n+1} \approx C\,e_n^2, \quad C = \frac{f''(x^*)}{2f'(x^*)}
오차 비율 ∣en+1∣/en2≈0.354=1/(22)|e_{n+1}|/e_n^2 \approx 0.354 = 1/(2\sqrt{2})를 확인하세요.
힌트 보기

  1. 가정: ff는 x∗x^* 근처에서 C2C^2이고 x∗x^*는 단순근, 즉 f(x∗)=0f(x^*) = 0이고 f′(x∗)≠0f'(x^*) \ne 0입니다 (f′(x∗)=0f'(x^*) = 0이면 아래 비율 f′′(x∗)2f′(x∗)\frac{f''(x^*)}{2f'(x^*)}는 무의미합니다). 이 가정 아래 f(x∗)=0f(x^*) = 0인 근 근처에서 ff를 2차까지 테일러 전개하면 0=f(x∗)≈f(xn)+f′(xn)(x∗−xn)+f′′(x∗)2en20 = f(x^*) \approx f(x_n) + f'(x_n)(x^* - x_n) + \frac{f''(x^*)}{2}e_n^2입니다 (en=xn−x∗e_n = x_n - x^*).

  2. 뉴턴 단계 xn+1=xn−f(xn)/f′(xn)x_{n+1} = x_n - f(x_n)/f'(x_n)를 대입해 정리하면 en+1≈f′′(x∗)2f′(x∗)en2e_{n+1} \approx \frac{f''(x^*)}{2f'(x^*)}e_n^2을 얻습니다.

  3. 즉 오차가 제곱되므로 정확한 자릿수가 매 단계 두 배가 됩니다 — 2차 수렴입니다. 엄밀한 증명은 테일러 정리의 나머지 평가가 필요하므로 아이디어 수준에서만 봅니다.

f(x)=x3−2x+2f(x) = x^3 - 2x + 2, x0=0x_0 = 0에서 뉴턴법이 0→1→00 \to 1 \to 0으로 영원히 순환함을 직접 계산으로 보이세요.

x1=0−2−2=1,x2=1−11=0x_1 = 0 - \frac{2}{-2} = 1, \quad x_2 = 1 - \frac{1}{1} = 0
접선이 00과 11 사이를 영원히 왕복합니다 — 수렴하지 않습니다.
증명 보기

  1. f(0)=2f(0) = 2, f′(0)=−2f'(0) = -2이므로 x1=0−2−2=1x_1 = 0 - \frac{2}{-2} = 1입니다.

  2. f(1)=1f(1) = 1, f′(1)=1f'(1) = 1이므로 x2=1−11=0x_2 = 1 - \frac{1}{1} = 0입니다.

  3. x2=x0x_2 = x_0이므로 이후 0,1,0,1,…0, 1, 0, 1, \dots이 영원히 반복됩니다 — 뉴턴법은 항상 수렴하지 않습니다.

10. 미분