Solving Nonlinear Equations 05 - Newton's Method for Solving a System of Nonlinear Equations

방정식의 해→ 해당 방정식을 그래프로 그렸을 때 해는 그래프상에 위치한다.

시스템의 해→ 시스템을 구성하는 방정식들을 그래프로 그렸을 때, 해는 모든 그래프상에 위치한다.

즉 해당 방정식들의 그래프들이 교차하는 지점이 해당 시스템의 해이다.

 

- 비선형 시스템에서 해 찾기

2개의 미지수를 갖는 2개의 비선형 방정식 시스템은 다음과 같이 표현된다.

$$ f_1(x,y)=0\\f_2(x,y)=0 $$

만약 $x_2,y_2$가 위의 시스템의 해이고 임의로 추정한 $x_1,y_1$이 해에 충분히 가까이 있다고 생각해보자.

위의 조건이 만족한다면 찾고 있는 시스템의 해 $x_2,y_2$에서의 함수 값 $f_1(x_2,y_2),f_2(x_2,y_2)$를

Taylor series expansion을 통해 임의로 추정한 $x_1,y_1$에 대하여 표현할 수 있게 된다.

$$ f_1(x_2,y_2)=\\f_1(x_1,y_1)+f_{1x}(x_1,y_1)(x_2-x_1)+f_{1y}(x_1,y_1)(y_2-y_1)+\\\frac{1}{2!}\{f_{1xx}(x_1,y_1)(x_2-x_1)^2+f_{1yy}(x_1,y_1)(y_2-y_1)^2+\\2f_{1xy}(x_1,y_1)(x_2-x_1)(y_2-y_1)\}+\cdots $$

$$ f_2(x_2,y_2)=\\f_2(x_1,y_1)+f_{2x}(x_1,y_1)(x_2-x_1)+f_{2y}(x_1,y_1)(y_2-y_1)+\\\frac{1}{2!}\{f_{2xx}(x_1,y_1)(x_2-x_1)^2+f_{2yy}(x_1,y_1)(y_2-y_1)^2+\\2f_{2xy}(x_1,y_1)(x_2-x_1)(y_2-y_1)\}+\cdots $$

$$ f_{xy}=f_{yx} $$

근사를 위해 위의 식에서 2차항 이상을 무시한다.

$(x_2,y_2)$가 시스템의 해임으로 $f_1(x_2,y_2)=0,f_2(x_2,y_2)=0$이다.

$x_2-x_1=\Delta x,y_2-y_1=\Delta y$ 로 나타내면 위의 식은 아래와 같이 단순화 된다.

$$ \frac{\partial f_1}{\partial x}{x_1,y_1}\Delta x+\frac{\partial f_1}{\partial y}{x_1,y_1}\Delta y=-f_1(x_1,y_1) $$

$$ \frac{\partial f_2}{\partial x}{x_1,y_1}\Delta x+\frac{\partial f_2}{\partial y}{x_1,y_1}\Delta y=-f_2(x_1,y_1) $$

이제 위의 식에서 $\Delta x, \Delta y$항을 제외한 모든 항을 알고 있는 2차 선형연립방정식이다.

선형연립방정식을 풀어서 찾은 $\Delta x, \Delta y$은 시스템의 해 $x_2,y_2$와 추정한 $x_1,y_1$의 차이임으로 시스템의 해를 구할 수 있게 된다.

 

테일러 근사를 이용하였기 때문에 $\Delta x, \Delta y$가 정확히 $x_2,y_2$와 $x_1,y_1$의 차이가 아니지만 $x_1,y_1$에 $\Delta x,\Delta y$를 더하게 되면 $x_1,y_1$이 $x_2,y_2$에 가까워 질것이다. 새롭게 찾은 $x_1+\Delta x,y_1+\Delta y$ 를 새로운 $x_1,y_1$으로 하여 위의 과정을 반복적으로 수행하게 되면 만족할만한 수치해를 얻을 수 있게 된다.

 

- 어떻게 $\Delta x와 \Delta y$를 찾을까?

선형 연립방정식의 해를 구하기 위해서 Crammer’s Rule을 이용한다.

$n$개의 미지수 $x_1,x_2,\cdots,x_n$을 가진 $n$개의 선형연립장정식을 나타내면 아래와 같다.

$$ a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1\\a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2\\\vdots\\a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n=b_n $$

위의 선형 연립 방정식 시스템을 행렬을 이용해 나타내면

$$ \begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\cdots&\cdots&\cdots&\cdots\\a_{n1}&a_{n2}&\cdots&a_{nn}\end{bmatrix}\begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix}=\begin{bmatrix}b_1\\b_2\\\vdots\\b_n\end{bmatrix} $$

$$ [a][x]=[b] $$

Crammer’s Rule을 이용해서 미지수 $x_2$를 구하기 위해서는 다음과 같은 과정을 따른다.

1. $[a]$의 두번째열을 $[b]$로 바꾸어 준다.

$$ a'_2=\begin{bmatrix}a_{11}&b_{12}&\cdots&a_{1n}\\a_{21}&b_{22}&\cdots&a_{2n}\\\cdots&\cdots&\cdots&\cdots\\a_{n1}&b_{n2}&\cdots&a_{nn}\end{bmatrix} $$

1. 위에 새롭게 만든 계수행렬의 행렬값을 원래의 계수행렬의 행렬값으로 나누어 준다.

$$ x_2=\frac{det(a'_2)}{det(a)} $$

위의 식을 일반화하면

$$ x_j=\frac{det(a'_j)}{det(a)}\,\,\,for\,\,\,j=1,2,\cdots,n $$

Jacobian

---

$$ \frac{\partial f_1}{\partial x}{x_1,y_1}\Delta x+\frac{\partial f_1}{\partial y}{x_1,y_1}\Delta y=-f_1(x_1,y_1) $$

$$ \frac{\partial f_2}{\partial x}{x_1,y_1}\Delta x+\frac{\partial f_2}{\partial y}{x_1,y_1}\Delta y=-f_2(x_1,y_1) $$

선형연립방정식을 Crammer’s Rule을 이용하기 위해 행렬의 형태로 바꾸면 다음과 같다.

$$ \begin{bmatrix}\frac{\partial f_1}{\partial x}{x_1y_1}&\frac{\partial f_1}{\partial y}{x_1y_1}\\\frac{\partial f_2}{\partial x}{x_1y_1}&\frac{\partial f_2}{\partial y}{x_1y_1}\end{bmatrix}\begin{bmatrix}\Delta x\\\Delta y\end{bmatrix}=\begin{bmatrix}-f_1(x_1,y_1)\\-f_2(x_1,y_1)\end{bmatrix} $$

Crammer’s Rule을 이용해서 $\Delta x$를 구하면

$$ a'{\Delta x}=\begin{bmatrix}-f_1(x_1,y_1)&\frac{\partial f_1}{\partial y}{x_1y_1}\\-f_2(x_1,y_1)&\frac{\partial f_2}{\partial y}_{x_1y_1}\end{bmatrix} $$

$$ \Delta x=\frac{det(a'_{\Delta x})}{{det (a)}} $$

$$ \Delta x=\frac{-f_1(x_1,y_1) \frac{\partial f_1}{\partial y}{x_1y_1}+f_2(x_1,y_1) \frac{\partial f_1}{\partial y}{x_1y_1}}{J(f_1(x_1,y_1),f_2(x_1,y_1))} $$

같은 방식으로 $\Delta y$를 구하면

$$ \Delta y=\frac{-f_2(x_1,y_1) \frac{\partial f_1}{\partial x}{x_1y_1}+f_1(x_1,y_1) \frac{\partial f_1}{\partial x}{x_1y_1}}{J(f_1(x_1,y_1),f_2(x_1,y_1))} $$

---

뉴턴법을 이용한 $n$개의 비선형방정식 시스템 풀이 일반화

$n$개의 미지수를 가진 $n$개의 비선형연립방정식 시스템은 다음과 같은 형태를 가진다.

$$ f_1(x_1,x_2,\cdots,x_n)=0\\f_2(x_1,x_2,\cdots,x_n)=0\\\vdots\\f_n(x_1,x_2,\cdots,x_n)=0 $$

각 미지수의 $i$번째 수치해들 $x_{1,i},x_{2,i},\cdots,x_{n,i}$를 구하기 위해 $\Delta x_1, \Delta x_2, \cdots,\Delta x_n$을 구해야한다.

$$ \begin{bmatrix}\frac{\partial f_1}{\partial x_1}&\frac{\partial f_1}{\partial x_2}&\cdots&\frac{\partial f_1}{\partial x_n}\\\frac{\partial f_2}{\partial x_1}&\frac{\partial f_2}{\partial x_2}&\cdots&\frac{\partial f_2}{\partial x_n}\\\vdots&\vdots&\ddots&\vdots\\\frac{\partial f_n}{\partial x_1}&\frac{\partial f_n}{\partial x_2}&\cdots&\frac{\partial f_n}{\partial x_n}\end{bmatrix}\begin{bmatrix}\Delta x_1\\\Delta x_2\\\vdots\\\Delta x_n\end{bmatrix}=\begin{bmatrix}-f_1\\-f_2\\\vdots\\-f_n\end{bmatrix} $$

 

$$ x_{1,i+1}=x_{1,i}+\Delta x_1\\x_{2,i+1}=x_{2,i}+\Delta x_2\\\vdots\\x_{n,i+1}=x_{n,i}+\Delta x_n $$

 

- 뉴턴법을 이용하기 위해 충족해야하는 조건

1. 비선형함수 $f_1,f_2,\cdots,f_n$와 이들의 미분형이 해의 근방에서 반드시 연속이며 정의 되어야한다.
2. 해의 근방에서 $J(f_1,f_2,\cdots,f_n)\ne0$
3. 초기추정치가 충분히 해와 가까워야한다.