Root finding algorithme - Newton's method(Quadratic interpolation with 2nd derivative)
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다.
Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다.
이전 Newton's method 글에서 접선(tangent line)을 통해서 해를 찾는 방법을 얘기했습니다. 이 방법은 정확히는 x_0 에서의 Taylor series expansion 의 1차 함수까지만 전개한 함수를 사용해서 접선을 구한 것입니다.
x_0 에서의 Taylor series expansion 을 2차함수까지 전개를 하면 아래 그림의 빨간 convex function 처럼 원함수 f(x) 에 대한 2차 근사함수를 구할 수 있습니다. 이후의 원함수의 근을 찾는 과정은 1차 근사함수와 과정이 거의 유사합니다.
1) 2차 근사함수의 근을 찾고, 그 지점에서 다시 원함수에 대한 2차 근사함수를 계산하는 일을 반복하거나
2) 해당 2차 근사함수가 근이 없을 경우 아래 그림처럼 근사함수의 local minimum 을 찾아서 그 지점에서 다시 2차 근사함수를 계산하는 것을 반복하면 됩니다. 아래 그림에선 x_0 에서의 근사함수의 local minimum point x_1 에서 f(x_1) 을 계산한 뒤 x_1 에서의 Taylor series expansion 을 반복하고 있습니다.
출처: https://math.stackexchange.com/questions/609680/newtons-method-intuition
Taylor series expansion 을 더 높은 차수까지 전개할 수록 근사함수는 원함수에 더 가까운 형태가 됩니다. 그렇게 한다면 더 적은 계산으로 더 빠르게 원함수의 근을 찾는 것이 가능합니다.
이 방법 또한 단점이 존재하는데, 4차함수까지는 2차 함수의 근의 공식처럼 일반해를 찾는 방법이 알려져 있지만, 5차 함수부터는 근에 대한 일반형이 존재하지 않기 때문에 계속해서 Taylor series expansion 을 전개할 수 없습니다. 원함수가 수회 미분 가능해야 한다는 전제 조건 또한 단점이 될 수 있습니다. 원함수가 미분이 불가능하거나, 실제 경우에 미분 하는데 너무 많은 computing resource 를 잡아먹는 경우가 발생하기 때문입니다.
Lagrangian interpolation(라그랑주 보간법) 을 사용해서 근사함수와 local minimum 을 찾는 방법도 있습니다.
Lagrangian interpolation 은 다음 글에서 설명하겠습니다.
