뉴턴의 방법과 오차해석 (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}$$
'물리 수학' 카테고리의 다른 글
에지워드 박스(Edgeworth box) 소개 - 하 (0) | 2017.12.24 |
---|---|
에지워드 박스(Edgeworth box) 소개 - 상 (4) | 2017.09.14 |
할선법과 오차(Secant method) (5) | 2017.09.10 |
곰셈과 함수에서 근삿값의 오차 (0) | 2017.09.09 |
차원 : 수학적 차원과 물리적 차원 (0) | 2017.09.08 |
라그랑주 승수법 풀이(Lagrange multiplier method) (7) | 2017.09.02 |
라그랑주 보간법(Lagrangian Interpolation) (11) | 2017.08.30 |