📂수치해석

넌리니어 시스템을 풀기 위한 뉴턴 메소드

메소드 ¹

$\mathbf{f} ( \mathbf{x} ) := \begin{bmatrix} f_{1}( \mathbf{x} ) \\ \vdots \\ f_{N} ( \mathbf{x} ) \end{bmatrix}$ 와 같은 다변수 함수 $\mathbf{f} : \mathbb{R}^{N} \to \mathbb{R}^{N}$ 가 $\mathbf{f} \in C^{2} \left( N ( \alpha ) \right)$ 이고 $\mathbf{f} ( \alpha ) = \mathbb{0}$, $\left[ D \mathbf{f} ( \alpha ) \right]^{-1}$ 이 존재한다고 하자. $\alpha$ 와 충분히 가까운 초기값 $\mathbf{x}_{0}$ 에 대해 $$ \mathbf{x}_{n+1} := \mathbf{x}_{n} - \left[ D \mathbf{f} ( \mathbf{x}_{n} ) \right]^{-1} f ( \mathbf{x}_{n} ) $$ 과 같이 정의된 수열 $\left\{ \mathbf{x}_{n} \right\}$ 은 $n \to \infty$ 일 때 $\alpha$ 로 쿼드러틱하게 수렴한다.

---

• $\mathbf{f} \in C^{2} \left( N ( \alpha ) \right)$ 이라는 것은 $\alpha$ 의 근방에서 $\mathbf{f}$ 가 두 번 미분가능하고 연속임을 의미한다.
• $D \mathbf{f}$ 는 $\mathbf{f}$ 의 자코비언을 나타낸다.

설명

모티브

$$ \begin{cases} x + \cos ( x - y ) = 0 \\ - y + \sin (x + y) = 0 \end{cases} $$ 예로써 위와 같은 문제가 있다고 하자. 리니어 시스템이라면야 선형대수의 툴을 써서 비교적 쉽게 답을 낼 수 있겠지만 넌리니어일 경우 이처럼 두 변수가 섞여있어서 풀이가 어렵다. 하지만 뉴턴 메소드는 수치적이긴 해도 잘만 풀어낸다.

뉴턴-랩슨 메소드의 일반화

뉴턴-랩슨 메소드는 그 자체의 속도가 굉장히 빠를 뿐만 아니라 넌리니어 시스템 $$ \begin{cases} f_{1}( x_{1} , \cdots , x_{N} ) = 0 \\ \vdots \\ f_{N}( x_{1} , \cdots , x_{N} ) = 0 \end{cases} $$ 을 풀 수 있는 범용성까지 갖추었다. 게다가 유도와 증명도 $1$차원에서 그냥 다차원으로 일반화할 뿐 기본적인 골자는 똑같다. 특히 $f : \mathbb{R} \to \mathbb{R}$ 이라고 하면 $\displaystyle \left[ D f ( \mathbf{x}_{n} ) \right]^{-1} = {{1} \over { f ' ( x_{n} ) }}$ 이 됨을 자연스럽게 알 수 있다. 이는 자코비언이 벡터함수의 미분계수와 같은 역할을 하기 때문이다.

요약하자면 이해하기 쉬운데 빠르고 풀 수 있는 문제가 많아서 아주 좋은 메소드다. 뉴턴 메소드를 구사할 줄 안다면 대부분의 분야에서 방정식을 푸는 가장 좋은 툴을 알고 있다고 생각해도 좋다.

구현

다음은 뉴턴 메소드를 R 코드로 구현한 것으로, 자코비언을 구하기 위해 numDeriv 패키지를 사용했다.

library(numDeriv)
 
Newton<-function(f,x0,tol=10^(-8)){
  while(sqrt(sum(f(x0)^2))>tol){
    x0 <- x0 - solve(jacobian(f,x0)) %*% f(x0)
  }
  return(c(x0))
}
 
f<-function(v){c(
  v[1]+cos(v[1]-v[2]),
  -v[2]+sin(v[1]+v[2])
)}
 
Newton(f,c(1,1))
f(c(-0.9980201,-0.9350821))

초기값 $(x_{0} , y_{0}) = (1,1)$ 에 대해 코드를 실행시키면 $\begin{cases} x + \cos ( x - y ) = 0 \\ - y + \sin (x + y) = 0 \end{cases}$ 의 근사해가 되는 $(-0.9980201 \cdots , -0.9350821 \cdots )$ 를 구해주는 것을 확인할 수 있다.

같이보기

• 1차원에서의 뉴턴-랩슨 메소드