뉴턴의 방법과 오차해석 (Newton's method)

방정식을 풀지 않고, 근이 대략 어느 정도 숫자인지 추정하는 방법이 있습니다. 그중에서 뉴턴의 방법(Newton's method)을 소개하려고 합니다. 뉴턴 방법은 어떤 점에서 함숫값과 기울기를 알 때, 그 함수를 일차함수라고 생각하고 근을 구하는 과정입니다.

이미지 출처 : https://en.wikipedia.org/wiki/Newton%27s_method

기본아이디어

1. $f=0$의 근으로 적당한 수($x_0$)를 찍는다.

2. $(x_0 , f(x_0))$에서 점선의 방정식을 구한다.

3. 그 접선의 방정식의 근을 $x_1$이라 한다.

4. 다시 $(x_1 , f(x_1))$에서 점선의 방정식을 구하고, 그 시행을 반복한다.

5. 수열 $x_n$은 방정식 $f=0$의 근으로 수렴할 것이다.

점화식

$(x_n, f(x_n))$을 지나고, 기울기가 $f'(x_n)$인 직선의 방정식은 다음과 같다.

$$ y= f(x_n)+f'(x_n)(x-x_n)  \tag1$$

(1) 식은 1차 테일러 다항식과 같다. 따라서 이 방법은 함수 f를 1차 테일러 다항식으로 근사시킨 후 근을 찾는 이라 생각할 수 있다. 이 방정식의 근을 $x_{n+1}$이라 하자. (1) 식에 $(x_{n+1},0)$을 대입하여 정리한다.

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

오차해석

수열 $x_{n}$이 얼마나 빠르게 f의 근으로 수렴하는지는 알아보자. 함수의 근을 a라고 하자.

$$f(a) = f(x_n)+(a-x_n)f'(x_n)+\frac{1}{2}(a-x_n)^2 f''(x_n) \tag3$$

(3) 식은 f(a)를 $x_n$근처에서 2차 테일러 다항식으로 근사한 것이다. 

(3) 식에 $f(a)=0$을 대입하고, 양변을 $f'(x_n)$으로 나눈다. 

$$ 0 = \frac{f(x_n)}{f'(x_n)}+(a-x_n)+\frac{f''(x_n)}{2 f'(x_n)}(a-x_n)^2 \tag4$$

(4) 식에 (2) 식(점화식)을 더하여 정리한다.

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

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

뉴턴방법의 오차를 $\varepsilon_n = a -x_n$라고 할 때, (6) 식은 다음과 같다. 

$$\varepsilon_{n+1} = \left[ \frac{-f''(x_n)}{2 f'(x_n)} \right] {\varepsilon_n}^2 \tag7$$

뉴턴방법을 시행할수록 오차가 제곱에 비례해서 줄어드는 것을 알 수 있다. 그런데 시작점($x_0$)을 잘못 정하면 오차가 제곱에 비례해서 커질 수도 있다. 뉴턴방법이 근으로 제대로 수렴할 조건에 대해 알아보자.

수렴 조건

$$\frac{-f''(x_n)}{2 f'(x_n)} \approx \frac{-f''(a)}{2 f'(a)} \equiv M \tag8$$

(7)식의 양변에 M을 곱하여 정리하면 언제 오차가 감소하는지 알 수 있다.

$$ \varepsilon_{n+1} \approx M{\varepsilon_n}^2$$

$$ M \varepsilon_{n+1} \approx \left[ M\varepsilon_n \right] ^2 \tag9 $$

모든 반복항이 (8) 식과 같이 a에 가깝다면, (9) 식을 점화식으로 사용하여 $a - x_n$이 수렴하기 위한 필요조건을 알 수 있다. 

$$ M \varepsilon_n \approx \left[ M\varepsilon_{n-1} \right] ^2  \approx \left[ M\varepsilon_{n-2} \right] ^{2^2}  \approx \left[ M\varepsilon_{n-3} \right] ^{2^3} $$

$$ M\varepsilon_{n} \approx \left[ M\varepsilon_{0} \right] ^{2^n}$$

$ \left| M\varepsilon_{0} \right| < 1 $, $ \left| M(a-x_0) \right| < 1 $

$$ | a-x_0 | < \frac{1}{|M|} = \left| \frac{2f'(a)}{ f''(a)} \right| \tag{10}$$

마치며

뉴턴 방법의 사용법과 오차해석에 대해 살펴봤습니다. 뉴턴 방법의 가장 큰 장점은 오차가 제곱에 비례해서 줄어들기 때문에 시행을 몇 번만 해도 매우 빠른 속도로 수렴한다는 것입니다. 뉴턴 방법의 단점은 도함수를 알고 있어야 한다는 것입니다. 컴퓨터로 코딩을 한다면, 루프(Loop)를 조금만 돌려도 되는 장점을 가진 대신, 미분하느라 루프를 한 바퀴를 도는 데 시간이 오래 걸리는 단점을 가졌다고 할 수 있습니다. 방정식의 근이 여러개가 있을 때는 초기값에 따라 하나의 근으로만 수렴하게 되니 주의해야합니다. 다음 글은 뉴턴 방법과 유사한 아이디어를 사용하지만, 미분하지 않는 할선 방법(secant method)에 대해 소개하려고 합니다. 긴 글 읽어주셔서 감사합니다.