[Calculus] [2-6] Newton’s Method (and Chaos)

 

0. Introduction

이번 섹션에서는 방정식의 해를 미분을 이용해서 찾는 방법,
바로 뉴턴 방법(Newton’s method) 를 다룬다.

우리가 풀고 싶은 문제는 항상 이런 형태다:

$$
f(x) = 0
$$

• 이 방정식의 해 $x^*$ 는 그래프 $y = f(x)$ 가
  x축과 만나는 점의 x좌표
• 즉, “그래프가 x축을 가로지르는 지점”이다.

뉴턴 방법의 핵심 아이디어는:

“현재 점에서의 접선(tangent line) 을 이용해서
다음 해의 후보를 예측하고, 이걸 반복해서 해에 가까이 간다.”

이번 포스팅에서 정리할 내용은:

• 접선/선형근사에서 뉴턴 공식이 어떻게 나오는지
• 뉴턴 방법의 일반적인 알고리즘
• 제곱 수렴(quadratic convergence): 왜 이렇게 빠른지
• 잘못 쓰면 어떻게 망가지는지 (발산, 진동, 심지어 ‘카오스’ 느낌까지)
• 실전에서 뉴턴 방법을 쓸 때 주의할 점

 

---

1. 접선과 선형 근사에서 뉴턴 공식까지

우리가 풀고 싶은 것은

$$
f(x) = 0
$$

이고, 해를 $x^*$ 라고 쓰자.
그래프 상으로는 $y=f(x)$ 가 x축과 만나는 점에서의 x좌표다.

하지만 $x^*$ 를 정확히 모른다고 치고,
어느 정도 “괜찮은” 초기 추측값 $x_0$ 를 하나 잡았다고 하자.

이제 $x_0$ 근처에서 $f(x)$ 를 직선(접선) 하나로 근사해보자.
$y = f(x)$ 의 $x_0$ 에서의 접선 방정식은 (선형 근사)

$$
f(x) \approx f(x_0) + f'(x_0)(x - x_0)
$$

이다.

우리가 정말 원하는 것은 $f(x) = 0$ 인 지점이니까,
위의 근사식에서 왼쪽을 0으로 놓고 $x$ 를 풀어보면:

$$
0 \approx f(x_0) + f'(x_0)(x_1 - x_0)
$$

이 식을 $x_1$ 에 대해 정리하면

$$
x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}
$$

이 된다.

이게 바로 뉴턴 방법의 한 단계(Newton update) 다.

• $x_0$ 에서 곡선에 그은 접선이
  x축과 만나는 점의 x좌표가 다음 추측 $x_1$
• 이 과정을 계속 반복하면 $x_1, x_2, x_3, \dots$ 가
  실제 해 $x^*$ 에 가까워지길 기대하는 것

---

2. Newton’s Method 알고리즘

위에서 구한 공식을 일반화하면,
$n$번째 추측 $x_n$ 에서 다음 추측 $x_{n+1}$ 은

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

이 된다.

요약하면 뉴턴 방법은 이렇게 동작한다:

1. 초기값 $x_0$ 를 정한다. (어느 정도 해에 가까운 값이면 좋다)
2. 반복해서
   $$
   x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}
   $$
   를 계산한다.
3. $|x_{n+1} - x_n|$ 이 충분히 작아지면,
   “이제 해에 충분히 가까워졌다”고 보고 종료한다.

중요한 전제 조건:

• $f'(x_n) \neq 0$ 이어야 한다. (접선이 수평이면 x축과 만나지 않음)
• $x_0$ 가 해에 너무 멀리 있으면, 오히려 발산하거나 진동할 수 있다.

---

3. 예제 1 — $\sqrt{b}$ 를 빠르게 구하는 뉴턴 방법

고전적인 예제: $b > 0$ 에 대해 $\sqrt{b}$ 를 구하고 싶다고 하자.

해는 방정식

$$
x^2 - b = 0
$$

의 양의 해이므로, 우리는

• $f(x) = x^2 - b$
• $f'(x) = 2x$

에 뉴턴 방법을 적용하면 된다.

뉴턴 업데이트:

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

이를 정리하면

$$
x_{n+1}
= \frac{2x_n^2 - (x_n^2 - b)}{2x_n}
= \frac{x_n^2 + b}{2x_n}
= \frac{1}{2}\left(x_n + \frac{b}{x_n}\right)
$$

결론:

$$x_{n+1} = \dfrac{1}{2}\left(x_n + \dfrac{b}{x_n}\right)$$
는 $\sqrt{b}$ 를 구하기 위한 뉴턴 방법 업데이트이다.

이 공식은 고대 바빌로니아인들이 이미 사용한 제곱근 알고리즘으로도 유명하다.

 

실제 예를 하나 들어보면, $b = 2$ 일 때

• $x_0 = 1$ 로 시작
• $x_1 = \dfrac{1}{2}(1 + \dfrac{2}{1}) = \dfrac{3}{2} = 1.5$
• $x_2 = \dfrac{1}{2}\left(1.5 + \dfrac{2}{1.5}\right) = \dfrac{1}{2}(1.5 + 1.\overline{3}) \approx 1.4167$
• $x_3$ 부터는 거의 $\sqrt{2} \approx 1.4142$ 와 같아진다.

몇 번 안 했는데도 소수점 네 자리까지 붙는 걸 볼 수 있다.
이게 바로 제곱 수렴(quadratic convergence) 의 힘이다.

---

4. 수렴 속도: 왜 이렇게 빨리 모이나? (오차 제곱)

간단한 아이디어만 정리해 보자.

• 실제 해를 $x^*$ 라고 두고,
• $e_n = x_n - x^*$ 를 “$n$번째 오차”라고 하자.

뉴턴 방법이 잘 작동하는 상황(해가 단순근, $f'(x^*) \neq 0$)에서는
테일러 전개를 이용하면 대략

$$
e_{n+1} \approx C , e_n^2
$$

라는 관계가 나온다. (상수 $C$ 는 $f''(x^*)$ 등에서 나온 값)

이 말은:

• 오차가 매 단계마다 제곱 수준으로 줄어든다는 뜻
• 예를 들어 $e_n \approx 10^{-2}$ 라면
  다음엔 대략 $10^{-4}$, 그 다음엔 $10^{-8}$ 정도로 줄어든다.

그래서

“처음만 적당히 잘 잡으면, 뉴턴 방법은 굉장히 빠르게 수렴한다”

는 것이 이론적으로도, 실전 계산기/컴퓨터에서도 모두 사실이다.

---

5. 잘 안 되는 경우들 — 발산과 진동

하지만 항상 이렇게 예쁘게 되지는 않는다.
뉴턴 방법도 다음과 같은 경우에는 문제를 일으킨다.

1. $f'(x_n)$ 이 0에 가까운 경우
   • 분모가 작으니 $\dfrac{f(x_n)}{f'(x_n)}$ 가 엄청 커지고
   • $x_{n+1}$ 이 한 번에 멀리 튀어나가 버릴 수 있다.
   • 이후 다시 돌아오지 못하면 발산.
2. 해가 실수가 아닌 경우
   • 예: $x^2 + 1 = 0$ 의 해는 $x = \pm i$ (복소수)
   • 실수 축에서만 뉴턴 방법을 돌리면,
     그래프 $y = x^2 + 1$ 는 x축을 전혀 만나지 않으므로
     접선을 따라가도 x축을 만날 실제 해가 없다.
   • 이 경우 뉴턴 방법은 실수축에서
     앞뒤로 왔다갔다 하며 수렴하지 않을 수 있다.
3. 시작점 $x_0$ 가 해에서 너무 먼 경우
   • 접선은 항상 “지역 정보”이기 때문에,
     멀리서 시작하면 완전 엉뚱한 곳으로 튈 수 있다.
   • 특히 함수가 비선형적으로 크게 휘어질수록 더 민감해진다.

 

MIT 노트에서도 이런 “망가지기 쉬운 예제”를 일부러 보여주면서:

뉴턴 방법은 좋은 함수 + 괜찮은 초기값 이라는 전제가 있을 때
강력한 도구다.

라는 메시지를 강조한다.

---

6. Newton’s Method와 Chaos — 왜 ‘카오스’라는 말을 쓸까?

뉴턴 방법을 이렇게 쓸 수도 있다:

• $N(x) = x - \dfrac{f(x)}{f'(x)}$ 라는 함수를 하나 정의하고
• 단순히
  $$
  x_{n+1} = N(x_n)
  $$
  이라는 점화식(동역학 시스템) 으로 보는 것

이 관점에서 보면 뉴턴 방법은

“Newton map $N(x)$ 를 반복해서 적용하는 과정”

이다.

여기서 흥미로운 일이 벌어진다:

• 어떤 함수에서는 $N(x)$ 의 반복이
  서로 다른 해(여러 근)에 대해 여러 개의 “끌어당기는 영역(basin of attraction)” 을 만든다.
• 출발점 $x_0$ 가 조금만 달라도
  완전히 다른 해로 수렴할 수 있다.
• 특히 복소수 평면에서 살펴보면,
  서로 다른 해의 basin 경계가 믿을 수 없을 정도로 복잡한 프랙털(fractal) 구조를 보인다.
  이것을 Newton fractal 이라고 부른다.

이런 이유로 MIT 노트 제목에도 “(and Chaos)” 가 붙어 있다.

• 한쪽 관점: 뉴턴 방법은 빠르고 안정적인 수치해석 도구
• 다른 관점: 뉴턴 방법은 $x_{n+1} = N(x_n)$ 이라는
  비선형 동역학 시스템의 예이며,
  적절한 함수와 초기값에서 카오스적(chaotic) 거동을 보일 수 있다.

실제로는,

• “실전 수치해석”에서는
  좋은 함수 + 좋은 초기값만 골라 쓰기 때문에
  이런 혼란스러운 모습은 잘 안 본다.
• “동역학/카오스 이론”에서는
  뉴턴 방법을 “간단하지만 혼돈을 보여주는 예제”로 사용한다.

---