[Numerical Analysis] Solution of Nonlinear Systems

• Nonlinear systems 의 해를 구하는 방법에 대하여 기술한 포스팅이다.
• 'Numerical Methods and Optimizaiton : An Introduction (Sergiy Butenko)' - chapter 4 를 참고하였다
• 이 포스팅은 이전 포스팅인 Solving Equation, Root Finding method에 이어지는 내용이므로 잘 이해가 가지 않으신다면 아래의 포스팅을 참고하길 바란다.

2021.07.02 - [[컴퓨터] 전산생물학/Modeling & Simulation] - [Numerical Analysis] Solving Equations, Root Finding Method

[Numerical Analysis] Solving Equations, Root Finding Method

 

 

이전 포스팅에서 single-variable equation 의 해를 Numeric 하게 구하는 방법을 알아보았다. 이번 포스팅에서는 이를 확장하여 n개의 식 과 n개의 variable을 가지는 형태의 해를 구하는 방법에 대하여 포스팅하겠다.

 

좀 더 수학적으로 표현을 하자면

이전과 같이 $F(x) = 0$ 을 구하는 방법에 대하여 이번엔 함수 $F$가 n 차원을 가지게 되므로 다음과 같이 표현된다.

$$F : \mathbb{R}^n \rightarrow \mathbb{R}^n$$

 

n개의 차원을 모두 나타내면 복잡하므로 쉬운 예시인 n = 2인 상황에서의 형태를 먼저 생각해보면 다음과 같다

$$\begin{cases} F_1(x,y) = 0  \\ F_2(x,y) = 0 \end{cases}$$

이 경우 해 $[x^*, y^*]^T$ 는 다음을 만족한다

$$F_1(x^*, y^*) = 0\ and\  F_2(x^*, y^*) = 0$$

 

1. Fixed Method for systems

이전 포스팅에서 기술했던 fixed method 를 적용하면 다음과 같다

$$f_1(x,y) = x-\alpha F_1(x,y),\\ f_2(x,y) = y - \alpha F_2(x,y)$$

와 같이 변환하면 $\alpha \neq 0$ 인 경우 아래와 같은 상황에서 $F_1$과 $F_2$의 해를 구할 수 있다.

$$\begin{cases} f_1(x,y) = x \\ f_2(x,y) = y \end{cases}$$

그 이유는 $f(x,y) = x\ or\ y$ 인 경우 $\alpha F(x,y) = 0$ 과 같아지기 때문이다.

 

이러한 변환을 이용하려 iteration을 다음과 같이 기술할 수 있다.

$$\begin{cases} x_{k+1} = f_1(x_k,y_k) \\ y_{k+1} = f_2(x_k, y_k) \end{cases}$$

 

2. Newton's method for systems

이번에는 newton method를 사용하여 시스템의 해를 구하는 방법을 알아보자

newton method 는 접점의 방정식을 Taylor approximation 을 통해 구하고 구해진 선 방정식의 x 축과 만나는점을 다음 iteration의 input으로 사용하는 방식임을 기억하면서 Taylor approximation을 다시 살펴보면 아래와 같다

$$f(x) \approx f(x_k) + f'(x_k)(x-x_k)$$

 

systems equation 에서는 first-order derivative ($f'(x_k)$) 표현하기 위하여 Jacobian matrix를 사용한다.

$$J_F(x,y) = \begin{bmatrix} \frac{\partial F_1(x,y)}{\partial x} & \frac{\partial F_1(x,y)}{\partial y} \\ \frac{\partial F_2(x,y)}{\partial x} & \frac{\partial F_2(x,y)}{\partial y} \end{bmatrix}$$

(위의 기호들이 익숙하지 않다면 다변수미적분학이나 선형대수학등의 교재를 참고하길 바란다)

 

Jacobian matrix를 systems equation에 적용시킨 Talyor approximation을 나타내면 다음과 같은 형태로 나타낼 수 있다

$$\begin{bmatrix} F_1(x_k,y_k) \\ F_2(x_k,y_k) \end{bmatrix} + \begin{bmatrix} \frac{\partial F_1(x_k,y_k)}{\partial x} & \frac{\partial F_1(x_k,y_k)}{\partial y} \\ \frac{\partial F_2(x_k,y_k)}{\partial x} & \frac{\partial F_2(x_k,y_k)}{\partial y} \end{bmatrix} \begin{bmatrix} x-x_k \\ y-y_k \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$$

 

Jacobian matrix를 inverse 하여 정리하여 주면 다음과 같은 iteration을 확인 할 수 있다.

$$\begin{bmatrix} x_{k+1} \\ y_{k+1} \end{bmatrix} = \begin{bmatrix} x_k \\ y_k \end{bmatrix} - \begin{bmatrix} \frac{\partial F_1(x_k,y_k)}{\partial x} & \frac{\partial F_1(x_k,y_k)}{\partial y} \\ \frac{\partial F_2(x_k,y_k)}{\partial x} & \frac{\partial F_2(x_k,y_k)}{\partial y} \end{bmatrix}^{-1} \begin{bmatrix} F_1(x_k,y_k) \\ F_2(x_k, y_k) \end{bmatrix}$$