[수치해석] 뉴턴법/뉴턴-랩슨법 정리

수치해석 뉴턴법/뉴턴-랩슨법 정리

방정식의 해를 구할 때 중고등학교 때는 근의공식과 조립제법을 이용해서 해를 구했었는데요. 정확해 해를 구할 수 없는 경우 해에 근접한 근사해를 찾아 구하는 방식 중 하나인 뉴턴법에 대해 알아보겠습니다.

근사해를 구하는 이유

대수적으로 모든 방정식의 해를 구하면 좋겠지만 안타깝게도 수학이란 세계에는 수많은 방정식이 있지만 해를 단번에 구할 수 있는 근의 공식은 4차까지밖에 없습니다. 5차 이상의 방정식은 근의 공식이 없기 때문에 인수분해가 잘 된다면 해를 구할 수 있겠으나 대개는 방정식의 해를 정확하게 구할 수가 없습니다.

근의공식이 없는 상황에서 정확한 해를 구하는 건 무모한 작업이기 때문에 정확한 해가 아니라 충분히 사용할만한 근사해를 구해서 오차범위 안에서 해라고 가정하고 사용하고 다음 작업으로 넘어가게 됩니다.

뉴턴법(뉴턴-랩슨법)

근사해를 구하는 방식 중에 하나인 뉴턴법은 초기값($x_0$)의 접선을 그어 x축에 만나는 점을 $x_1$로 두어 수열을 형성해 근사해를 찾는 방식입니다.

구하는 방식

{$x_n$} 수열을 만들건데 아래와 같은 방식으로 만듭니다.
$(x_0,y_0)$에서의 접선의 방정식을 구하면 다음과 같습니다.

$$y-y_0 = f'(x_0)(x-x_0)$$
x에 대해 정리하면,
$$x = x_0 - \frac{f(x_0)}{f'(x_0)} , f'(x_0)\neq 0$$
여기서, x를 $x_1$으로 정의합니다.
다시 말해,
$$x_1 = x_0-\frac{f(x_0)}{f'(x_0)}$$
이다. 위의 방법을 반복해 수열을 만든 것이 {$x_n$}입니다. 즉, $x_n$은 다음과 같습니다.
$$x_{n+1} =x_n-\frac{f(x_n)}{f'(x_n)} , f'(x_n)\neq0$$

예를 들어,
$f(x)=2x^2-5$이라 할때, $f'(x)=4x$입니다. $x_0=3$ 일때,
$$x_1 = 3-\frac{13}{12}=\frac{23}{12}$$
$$x_2 = \frac{23}{12}-\frac{\frac{169}{72}}{\frac{23}{3}} = \frac{889}{552}$$
위 계산을 반복해나갑니다.
아래와 같이 해(x축)에 근접해 갑니다.

그림을 보면 예상하겠지만 초기값이 무엇이냐에 따라 해를 찾을수도 못찾을수도 있습니다.

 

근사해로 실제 해 구하기

limit의 개념을 이용해 근사해($x_n$)를 수렴하는 a값이 해가 됩니다.
즉, $$lim_{n->\infty}x_n = a 이면, f(a)=0이다.$$
수렴값이 실제 해라고 봐도 무방합니다.

 

 

뉴턴법의 장단점

뉴턴법의 장점

1. 수렴 속도가 매우 빠르다.
2. 반복할수록 정밀한 해를 가진다.

뉴턴법의 단점

1. 초기값 설정을 제대로 하지 못하면 해를 구할 수 없다.
2. 미분값 계산을 해야 한다.

 

뉴턴법의 안 좋은 사례

1. 해를 결정할 수 없음(undefined)
   ex) $f(x)=xe^{-x}$ , $x_0$=2 일때, infinity로 빠져버립니다.
   
   
   
   근사해를 알수가 없습니다.
2. oscillation
   ex) $f(x) = x^3 -2x+2$, 초기값이 $x_0=0$이면 수열이 진동할 뿐 한쪽으로 수렴하지 않습니다. 다시 말해, 근사해를 정할수 없습니다.

좋은 초기값을 구하기 위해선

1. 직관이나 그래프 해석으로 선택합니다.
2. 이분법으로 근이 존재하는 구간 먼저 찾아서 초기값을 해당 구간에서 정합니다.
3. f(a)>0 or f(b)<0 이라면 a,b의 중간값을 $x_0$으로 잡습니다.
4. f'(x)값이 0에 가까운 구간은 피합니다. 순간기울기가 수평에 가까워지면 뉴턴법의 분모가 0에 가까워지므로 더이상 진행할 수 없게 됩니다.
5. 해가 여러 개인 경우, 문제의 특성을 잘 파악해 필요한 해만 얻을 수 있게 설정을 합니다. 정의역 파악을 잘 하면 불필요한 초기값은 제외하고 작업을 할 수 있습니다. 예를 들어, 시간에 대한 함수이면 음수인 해는 필요없으니 초기값을 양수에서만 설정합니다.

 

미분 자체가 어려운 함수인 경우

미분 가능하긴 하지만 미분을 구하기 어렵다면 [[secant method]]를 이용해 미분을 안 구하는 방법으로 시도해볼 수 있습니다.

뉴턴법의 $f'(x_n)$을 아래와 같이 바꿉니다.

$$f'(x_n)\approx f_n' = \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}$$
순간기울기를 평균기울기로 바꿔서 진행한다.

다음과 같이 된다.
$$x_{n+1} = x_n - \frac{(x_n-x_{n-1})f(x_n)}{f(x_n)-f(x_{n-1})}$$

그림에서 보듯이 접선이 아닌 평균기울기를 통해서 근사해를 찾아갑니다.

 

마치며

근사해를 구하는 방식은 많습니다. 각 장단점를 고려해서 구하고자 하는 방정식에 가장 적합한 방법을 사용한다면 효율적으로 근사해를 구할 수 있습니다.

 

함께보면 좋은글

 

[수치해석] Spline interpolation(스플라인 보간법)

 

 

[Python] 회귀(Regression)