나는 요근래 선형시스템에 대해 관심이 많았는데 이번에는 linear라는 조건을 해제하고 정말 equation의 해를 찾는다는 것에 대한 이야기를 해보고자 한다. Optimization과 마찬가지로 하나의 보장된 방법이랄 게 없다.

• function이라는 것은 input $x$를 받아서 output $y$를 반환하기만 하면 함수이다. 그것이 지금까지 알던 그 수학 공식일 수도 있지만 코드 몇천 줄로 구성되어 있어도 똑같이 function이다.
• equation의 root는 없을 수도 있고, 하나일 수도 있고, 유한개일 수도, 무한개일 수도 있다. 또 real number일 수도 complex number일 수도 있다.

🏁GOAL
How to find $x:f(x)=0$ for $f:\mathbb R^n \rightarrow \mathbb R^n$

multi variable vector valued function $f$에 대해 $f(x)=0$을 만족하는 $x$를 찾는 것을 목적으로 한다.

Iterative Method - Initial Guess & Stopping Criterion

root finding에는 iterative method가 이용된다.

iterative method는 항상 starting point (initial guess)를 필요로 하고 이 starting point를 잘 정하는게 중요하다. 잘못된 starting point에서 시작하는 경우 converge하지 않거나 잘못된 해를 찾을 수 있다.

시스템 특성을 잘 파악하든 뭘 하든간에 쓸 수 있는 조건을 모두 모아 근이 존재할 가능성이 높은 곳에서 start하는 것이 좋다.

Iterate를 평생 할 수는 없으니 언제 멈출지 결정하는 stopping criterion도 필요하다.

Newton-Raphson Method

equation의 root를 찾는 데 보장된 방법이랄 것은 없지만 그래도 아주 괜찮은 방법은 있다. 그게 Newton-Rapson Method이다. 단점이라면 $f(x)$와 $f^\prime(x)$를 이용하기 때문에 $f^\prime(x)$를 정의할 수 있어야 한다는 것이다. 위에서 말했듯이 functioin이라는 것은 입력과 그에 따른 출력만 분명히 정의되면 되고, 함수라는 것이 미분가능하다는 얘기는 아니다.

기본적으로 iteration method이기 때문에 update를 해 간다.

$x^{(k)}$가 있을 때 $x^{(k+1)}$로 어떻게 update할지가 문제고 variation이 많다.

iteration의 basic form은 아래와 같다.

$\alpha^{(k)}$는 step size, $\Delta x^{(k)}$는 update direction이다.

Exact Gradient Method

Newton Raphson Formula:
$x^{(k+1)}=x^{(k)} -{f(x^{(k)}) \over f^\prime(x^{(k)})}$

Taylor Series Expansion으로 $f(x^{(k+1)})=f(x^{(k)})$

Approximate Gradient Method - Secant Method

Nonlinear Equations

Newton Raphson Method

Variations

Approximation of the Jacobian

$f:\mathbb R\rightarrow\mathbb R$ 일 때 derivative를 이용하는 것처럼 지금 다루는 함수는 multi variable vector valued이기 때문에 같은 역할인 Jacobian을 이용한다.

Conjugate Gradient Method

Linear Algebra for Computing Zeros of Polynomials

Root Finding as Optimization

참고자료:
인하대 김광기 교수님의 수치해석 강의