14-02-01 Root finding

이 장에서는 root finding 문제에 Newton’s method를 적용해본다. 우리가 논하는 최적화 문제에서의 Newton’s method와 약간의 차이가 있으므로 이를 설명한다.[최적화 문제에서의 Newton’s method][root finding에서의 newton’s method]

Newton’s method for root finding

\(F:\mathbb{R}^{n}\rightarrow \mathbb{R}^{n}\)인 벡터 함수(vector function)가 있다고 하자. 또한, 이 함수의 근, 즉 함수값을 0으로 만드는 \(x\)값을 찾는 문제(root-finding)를 생각해보자.

\[\begin{align} F(x) = 0. \end{align}\]

이 문제는 초기값 \(x^{(0)}\)를 정한 뒤, 반복적으로 Newton’s method를 적용하여 해에 접근해갈 수 있다.

\[\begin{align} &\text{choose initial }x^{(0)}\in \mathbb{R}^{n},\\\\ &x^{(k)}=x^{(k-1)}-\nabla F(x^{(k-1)})^{-1}F(x^{(k-1)}), \qquad k=1,2,3,...\\\\ \end{align}\]

여기서 \(\nabla F(x^{(k-1)})\)은 \(x^{(k-1)}\)일때의 \(F\)의 Jacobian 행렬이다. Newton step인 \(x^{+}=x-\nabla F(x)^{-1}F(x)\)는 아래와 같이 F를 선형근사(linear approximation)함으로써 계산할 수 있다.

\[\begin{align} F(y)\approx F(x) + F^{'}(x)(y-x) = 0\\\\ y = x^{+}=x-F^{'}(x)^{-1}F(x). \end{align}\]

Newton’s method for optimization problem

Newton’s method를 아래와 같은 최적화 문제에 적용한다고 보면,

\[\begin{align} \min_{x} F(x) \end{align}\]

이는 목적함수 \(F(x)\)의 gradient, \(\nabla{F(x)}=0\), 즉 \(\nabla F(x)\)의 root finding 문제에 Newton’s method를 적용하는 것과 동일하다.

정리하면, 최적화 문제에서 주어진 함수 도함수의 근(\(\nabla F=0\))을 Newton’s method를 이용해서 찾는 것과 달리, 근을 찾는 문제는 함수 값 자체의 근(\(F=0\))을 Newton’s method를 이용해서 찾아야 하므로 각 문제에 대하여 Newton’s method의 x에 대한 update 식에서 미분항에 한 차수 차이가 발생한다.

Root finding example

\(F:\mathbb{R}\rightarrow\mathbb{R}\)이 다음과 같이 정의된다고 하자.

\[\begin{align} F(x)=x^{2}-2 \end{align}\]

\(x^{(0)}=1\)으로 정하고, pure Newton’s method를 적용하면 다음과 같다.

k(iteration 횟수)가 증가함에 따라 \(x\)가 근인 \(\sqrt 2\)에 가까워짐을 확인할 수 있다.