Solving Nonlinear Equations 02- Newton Raphson Method

- 뉴턴법은 $f(x)=0$ 형태의 방정식에 대해서 수치해를 찾는 방법이다.

- 뉴턴법을 사용하기 위해서는 함수 $f(x)$가 연속이며 미분가능해야한다

Newton Method

1. 함수의 정의역내에서 임의의 $x_1$을 수치해로 설정한다.
2. $x_1$에 대하여 함수 $f(x)$를 미분하여 tangent line(일차함수)를 구한다.
3. tangent line이 $x$축과 만나는 지점을 다음 수치해 $x_2$로 설정한다.
4. 2~3과정을 충분한 수치해를 얻을 때까지 반복하여 수행한다.

- 위 과정을 수식으로 나타내면 다음과 같다.

첫번째 수치해 $x_1$에 대해 $f(x)$를 미분하여 기울기를 얻은 후 이를 tangent line(일차함수)로 나타내면

$$ y=f'(x_1)(x-x_1)+f(x_1) $$

두번째 수치해 $x_2$는 위에서 구한 tangent line이 $x$축과 만나는 지점($y=0)$이므로 다음과 같이 표현된다.

$$ 0=f'(x_1)(x_2-x_1)+f(x_1) $$

위의 식을 $x_2$에 대하여 정리하면

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

새로 찾은 수치해 $x_2$를 이용해 다음 수치해 $x_3$를 찾는다. 이 과정을 일반화하여 나타내면 다음과 같다.

$$ x_{i+1}=x_i-\frac{f(x_1)}{f'(x_1)} $$

 

- 뉴턴법은 테일러 전개를 통해서도 유도할 수 있다.

함수 $f(x)$를 $x_1$에 대하여 전개하면 다음과 같다.

$$ f(x)=f(x_1)+(x-x_1)f'(x_1)+\frac{1}{2!}(x-x_1)^2f''(x_1)+\cdots $$

$x_2$가 $x_1$근방에 존재할 때 위의 식 $f(x)=0$일때의 해이다. 따라서 다음과 같다.

$$ f(x_2)=0=f(x_1)+(x_2-x_1)f'(x_1)+\frac{1}{2!}(x_2-x_1)^2f''(x_1)+\cdots $$

1차항까지만 고려하여 수치해를 근사시켜 $x_2$에 대하여 나타내면 위의 식과 동일함을 알 수 있다.

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

---

언제까지 반복해야 하는가?

이상적으로는 방정식 $f(x)=0$을 만족하는 해 $x$를 찾는 것이다.

하지만 정확한 해석해는 수치해석적으로 찾기가 힘들다.

때문에 수치해석 알고리즘을 통해 반복적으로 해에 근사시켜 나갈 때 얼마나 해석해에 근접한 해를 찾을지 결정하는 것이 필요하다.

따라서 판단을 위한 기준이 필요한데 다음과 같다.

 

1. 추정상대오차(Estimated Relative Error)

상대오차는 새로 찾은 수치해와 이전의 수치해의 차이가 이전 수치해의 전체에서 얼마나 차지하느냐를 본다.

따라서 둘의 차이가 크지 않으면 추정상대오차는 작을 것이고, 이는 수치해가 해석해에 매우 근접하여 더이상 다가갈 거리가 얼마남지 않음을 의미한다.

따라서 사전에 설정한 값(specified value) $\epsilon$ 보다 추정상대오차가 작게 되면 이 해를 만족할만한 수치해로 볼 수 있다.

$$ \left|\frac{x_{i+1}-x_i}{x_i}\right|\le \epsilon $$

 

2. 공차(Tolearnce in $f(x)$)

방정식 $f(x)=0$의 해는 $x$축 선상에 있을 것이다. 따라서 해석해를 $x_A$라 했을 때 $f(x_A)=0$이다.

위의 특징을 이용하면 수치해가 해석해에 가까워질수록 수치해 $x_N$의 $f(x_N)$값은 0에 가까워 질것이다.

따라서 매우 작은 값 $\delta$보다 작은 거리만큼 떨어져 있다면 해당 수치해를 만족할만한 수치해로 볼 수 있다.

$$ |f(x_i)|\le \delta $$

---

뉴턴법 MATLAB

% fun: 주어진 x에 대해서 f(x)값을 계산하는 사용자 지정 함수
% fun_der: 주어진 x에 대해서 f'(x)값을 계산하는 사용자 지정 함수
% ini_X: 뉴턴법을 처음 시작할때 추정한 임의의 x값
% err: 사전에 설정한 허용오차값
% imax: 최대 반복횟수
% Xi: i번째 반복시 찾은 수치해
% num_X:수치해

for i=1:imax % 첫번째 반복부터 최대 반복문까지 for문 수행
    Xi=ini_X-fun(ini_X)/fun_der(ini_X); % 뉴턴법을 이용해 다음 수치해 찾기
    if abs((Xi-ini_X)/ini_X)<Err % 새로 찾은 수치해가 사전설정한 오류보다 적으면
        num_X=Xi; % 해당해를 수치해로 하고 
        break % 반복을 종료한다.
    end
    ini_X=Xi; % 그렇지 않으면 새로 찾은 해를 새로운 초기추정치로 하여 다음값을 찾는다.
end

if i == imax % 최대반복수행하여도 해를 찾지 못한경우
    fprintf('%i번의 반복동안 해를 찾을 수 없습니다.\\n',imax)
    num_X=('No answer');
end

---

Newton's method가 해에 수렴하지 않는 경우

해석해의 근방의 미분값 $f'(x)$값이 0에 수렴하지 않는 경우 수치해가 해석해에 수렴하지 않을 수 있다.

수치해가 발산하는 경우

---

Secant Method

Secant Method는 $f(x)=0$ 형태의 방정식의 해를 찾는 방법이다.

1. 이웃한 두점 $x_1,x_2$의 $f(x)$위의 점 $(x_1,f(x_1)),(x_2,f(x_2))$을 지나는 일차함수를 구한다.

2. 구한 일차함수가 $x$축과 만나는 지점을 $x_3$로 하여 $x_2,x_3$을 이용해 다음 수치해 $x_4$를 찾는다.

3. 위의 과정을 만족할만한 수치해를 찾을 때까지 반복적으로 수행한다.

 

Secant Method

- 위의 과정을 수식으로 나타내면 다음과 같다. 

이웃한 두점 $x_1,x_2$의 $f(x)$위의 점 $(x_1,f(x_1)),(x_2,f(x_2))$을 지나는 일차함수는

$$ y-f(x_1)=\frac{f(x_2)-f(x_1)}{x_2-x_1}(x-x_1) $$

일차함수가 $x$축과 만나는 지점($y=0$)이 $x_3$에 대해서 정리하면

$$ x_{3}=x_2-\frac{f(x_2)(x_{1}-x_2)}{f(x_{1})-f(x_2)} $$

위의 식을 일반화하여 나타내면 아래와 같다.

$$ x_{i+1}=x_i-\frac{f(x_i)(x_{i-1}-x_i)}{f(x_{i-1})-f(x_i)} $$

 

- Secant Method는 Newton's Method와 매우 유사하다.

뉴턴법은 각 점에서 미분값을 이용해 해당점에서의 접선을 통해 다음 수치해의 위치를 결정하지만

시컨트법은 이웃한 두점을 지나는 선을 통해 다음 수치해를 결정한다.

두 방법 모두 일차함수가 일차함수를 이용해 다음 수치해를 결정한다는 점에서 유사하다.

Secant Method를 Newton꼴로 표현하면 다음과 같다. 

$$ x_{i+1}=x_i-\frac{f(x_i)}{\frac{f(x_{i-1})-f(x_i)}{(x_{i-1}-x_i)}} $$