0. Nonlinear equations

수치 해석에서는 초월 함수나 다항 함수 등의 root(혹은 zero; 근, 해)를 찾는 것이 매우 중요하다. 석사 전공이었던 편미분방정식의 수치 해를 FDM으로 근사하는 것에도 매 temporal step마다 매 grid에서 non-linear equation을 풀어야했다. 이번 글에서는 우선 Newton's method에 대해 상세하게 알아보자.

비선형 방정식은 다음과 같은 일반적인 꼴을 갖는다.

$f(x)=0\cdots(1)$

물론 $f$의 linearity의 여부에 관계없이 Newton's method는 모두 적용가능하다.

1. Newton's method의 특징

Newton's method는 매우 자주 쓰이는 root finding의 한 방법론으로 다음과 같은 장점을 갖는다.

• 수렴 차수가 2차이다. 즉, 수렴 속도가 빠르다.

그렇다. 2차는 다른 method와 비교하면 수렴 속도가 매우 빠르다. 하지만 다음과 같은 단점을 갖는다.

• 수렴 조건이 비교적 까다롭다.
• 잘 가다가 무한 loop에 빠질 때도 있다.
• 매 step마다 미분값을 계산해야 한다.

2. Newton's method 전개

Newton's method의 전개식에 대해 알아보자. 이에 대한 사전 배경지식으로 Taylor's expansion(혹은 Taylor's series)이 필요하다.

Preliminary 1. Taylor's expansion

$f(x+h)=f(x)+hf'(x)+\frac{h^2}{2!}f''(x)+\cdots\ \cdots$(2)

물론 이렇게 감히 간단히 쓰여질 식이 아니다. Taylor's expansion을 만족하기 위해서 $f$는 무한번 미분이 가능해야한다는 아주 강력한 조건이 필요하다. 이를 증명하기 위해서는 학부 해석학 지식이 필요하지만, 이번 글에서는 다루지 않겠다.

다시 Newton's method로 돌아가서 nonlinear equation (1)이 $\alpha$라는 root를 갖는다고 하자. 사실 정확히는 여러 roots 중 하나가 $\alpha$라고 하는 표현이 맞다.
이제 (2)를 활용하면 다음과 같이 된다.

$f(\alpha)=f(x_0)+(\alpha-x_0)f'(x_0) + \frac{(\alpha-x_0)^2}{2!}f''(x_0) + \cdots \cdots$ (3)

여기서 $\frac{(\alpha-x_0)^2}{2!}f''(x_0)+\cdots$항에 대해서 mean value theorem을 적용하면

$\frac{(\alpha-x_0)^2}{2!}f''(x_0)+\cdots=\frac{(\alpha-\eta)^2}{2!}f''(\eta)$ for some $\eta\in[x_0,\alpha]\cdots$(4)

가 된다. 위의 (4)항이 바로 Newton's method의 truncation error가 된다. (4)식에서 $(\alpha-\eta)^2f(\eta)$이라는 상수가 붙게 되는데 degree가 2이므로 수렴 차수가 2가 된다.이제 위의 (3)식에서 truncation error (4)는 당분간 고려하지 않겠다.

$f(\alpha)=0$이므로 (3)식을 정리하면

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

가 된다. 물론 truncation error (4)때문에 정확히 $\alpha$가 root가 되지 못하고 점차 root로 수렴하는데 이를 iteration 식으로 나타내면 Newton's method식이 다음과 같이 완성된다.

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

물론 공대나 컴퓨터공학에서는 Newton's method를 가르칠 때 그림으로 그리면서 접선의 root를 따라간다고 가르치지만 그림으로는 수렴 차수가 2인 것을 증명할 수가 없다. 따라서 수치해석학에서는 Taylor's expansion을 이용해 Newton's method를 전개하는 것을 선호한다.

Newton's method는 (5) 식이 충분히 수렴할 때 즉, 주어진 tolerance에 대해서 다음과 같은 식을 만족하면 iteration을 종료한다.

$|x_{n+1}-x_n|<tolerance \cdots$(6)

(6) 식을 만족하기만 하면 root인 $\alpha$와 $x_{n+1}$의 차이는 tolerance를 만족하게 된다. 이에 대한 증명은 metric이 정의된 공간에서 triangle inequality를 이용하면 지금은 기억이 안나지만 쉽게 증명할 수 있다.

앞서 말한대로 Newton's method는 수렴 조건이 까다롭다. 정확히는 기억이 안나지만 $f$가 Lipschitz condition을 만족해야하고 Taylor's expansion의 수렴 조건을 만족해야하는데 이 조건들이 생각보다 수치해석학에서는 까다로운 조건에 속한다. 또한 (5) 식에서 분모가 0이 될 때, 혹은 무한 진동이나 발산 같은 현상이 생각보다 자주 일어나게 된다.

또한 Newton's method의 장점에서 말한 수렴 속도가 빠르다는 것은 Newton's method 자체가 빠르다는 것을 의미하지는 않는다. iteration 자체를 적게 하는 것은 맞지만 매 step 마다 $f'(x_n)$을 구해야하는게 computational cost를 많이 먹는다. 이를 해결하기 위해 내가 속했던 연구실은 $f'(x_n)$을 처음의 $f'(x_0)$로 고정해서 매 iteration마다 미분을 하는 시간을 줄이는 simplified Newton's method를 이용하기도 했다.