NA-rootfinding(1)

1. General procedure of root finding

• Step 1. 대략적인 초기 값을 찾는다.
  • graphical method
    • 그래프를 그려서 함수의 해를 시각적으로 확인하는 방법
  • incremental search
    • 함수의 값을 일정 간격으로 계산하며 해를 찾는 방법
  • experience
    • 과거의 데이터나 경험을 통해 초기 해를 추정하는 방법
  • solution of a simplified model
    • 복잡한 문제를 단순화하여 그 해를 초기 추정값으로 사용하는 방법
• Step 2. 정확한 답을 찾는다.
  • Bracketing method
    • 해가 있는 구간을 좁혀나가면서 해를 찾는 방법
    • 이 방법은 해가 있는 구간을 확신할 수 있다.
  • Open method
    • 초기 추정값만을 사용하여 해를 찾는다.
    • bracketing 보다 더 빠르게 수렴 할 수 있지만 항상 해를 보장하지는 않는다.

2. Initial step

1) Finding a rough approximation (Graphical method)

2) Incremental search

• 구간 [x, dx]내에서의 부호 변화를 감지한다.
  • 변화가 있다면, → solution이 존재한다.
  • Difficulty
    • dx를 너무 작게 설정 하면 많은 검색을 해야하므로 시간이 오래 걸리고, 너무 크게 선택한다면 중간에 있는 해를 놓칠 수 있다.
    • Multiple roots
      • 다중 근을 놓칠 가능성이 있다.
        • 이때, 양 끝점에서의 미분을 확인하여 부호가 다르다면, 구간 안에 극대 혹은 극소가 존재하는 것이기에 중근을 찾는 단서가 될 수 있다.
• Incremental search는 solution을 찾는 초기 단계에 위치 해야 한다.

3. Bracketing method

• 가정: 주어진 구간 [a, b]에 답이 무조건 있을 것이다.
• Key idea: 구간을 점차 점차 줄인다.
• Merit: 정확한 값에 수렴 할 수 있다.

1) Bisection method

• Half interval method or Bolzano method라고도 불린다.
• 원리는 f(x1)f(x2) < 0 라면 [x1, x2]에 해가 존재한다는 것이다.

• 한번 iterate 할 때 마다 구간을 절반으로 줄인다.
  • xr = (xl + xu) / 2
  • if f(xl)f(xr) < 0, xu = xr,
  • if f(xl)f(xr) > 0, xl = xr

• 간단하다,
• n번째 반복에서 최대 오차는 (초기구간 / 2^n)보다 작다.
• 수렴 속도가 느리다.
• 다중 근을 처리 할 수 없다.

2) Linear interpolation method

• Falses position method라고도 불린다.

• 초기 두 점, x0과 x1을 선택한다. 해당 두 점을 연결하는 직선을 만들어 새로운 pn+1을 정의한다.

$p_n+_1 = a_n - f(a_n)(b_n-a_n)/f(b_n)-f(a_n)$

• if, f(an)f(pn+1) < 0, 이라면 an+1 = an, bn+1 = pn+1
• if f(an)f(pn+1) > 0, 이라면 an+1 = pn+1, bn+1 = bn

3) Convergence speed

• False position (Linear interpolation)은 Bisection 보다 빠르다.
• 수렴 속도는 curvature(곡률)에 영향 받는다. (어떨때는 극도로 느릴 수 있다. → Modified linear interpolation method
  

4) Modified linear interpolation

• 원래의 linear interpolation은 잘못된 곡률을 가진다면 수렴 속도가 상당히 느리다.
• 그렇기 때문에, 함수 자체에 상수로 나누어 주어서 곡률을 변화시키는 방법이 존재한다.

4. Open method

• Idea: 임의의 시작점에서 정규적인 반복을 통해서 root를 찾는다.
• Risk: 발산의 위험이 있다. (초기 값에 영향을 받는다.)
• Merit: Bracketing method들보다 더 빠른 수렴 속도를 갖는다.

1) Newton-Raphson method

• 즉, 초기 추정 값 x0을 선택한다. 해당 값 x0에서 접선을 그어, 다음 x1을 구한다.
• x1에서 접선을 그어 x2를 구한다.
• 빠른 수렴 속도를 가진다 - quadratic convergence (제곱에 비례한다.)
• 만약에 도함수 계산이 복잡하다면 효과적이지 않다.
  • 도함수가 불연속적이거나, 도함수가 0인 경우에도 실패할 수 있다.
• 초기 예측이 중요하게 작용한다.
• 다양한 발산 방법이 존재한다.

2) Secant method

• 즉, 두 근사값에서의 함수 값에 대한 직선을 그어, 이 직선이 x축과 교차하는 점을 다음 근사값으로 사용하는 것이다.
• Linear interpolation과 비슷한 복잡도를 가진다.
  • 둘 다, 두 점 사이의 직선을 사용하여 근을 찾는 방식이기에
  • update rule만 다르다.
    • Linear interpolation은 두 점(이때 한 점은 x축과의 교점)에서의 함수 값들을 곱한 부호에 따라 업데이트 하고,
    • Secant는 두 점 사이의 직선의 x절편이 다음 근사값이 되는 것이다.

• 하지만, linear interpolation보다 더 빠른 수렴 속도를 가진다.
• Newton-Raphson method보다 더 안정적이다.
  • 도함수의 값을 필요로 하지 않아서, 도함수를 알기 어려운 상황에서 유용하게 사용된다.

3) Comparision: Convergence speed

• Newton-Raphson method는 Qudratic conversion을 갖기에 가장 빠르다!

4) Fixed point iteration

• 원리
  • f(x) = 0 → x = g(x)
• Iteration rule

• Convergent
  • 만약 |xn+1-xn|가 충분이 작다면 반복을 멈춘다.
• Fixed point iteration으로 모든 함수의 근을 찾을 수 있는 것이 아니다.

5) Muller method

• Secant method의 확장한 버젼이다.
• 빠른 수렴 속도를 갖는다.

• 순서
  1. 세 개의 시작점 x0, x1, x2를 선택한다.
  2. 이 세점을 통해 2차 다항식을 구성한다.
  3. 이 다항식의 근을 계산해서 새로운 근사값을 얻는다.
  4. x0을 버리고 새로운 근사 값을 통해 2차 다항식을 구성한다.
• Muller의 방법은 복소수 근도 찾을 수 있다. 하지만, 다른 open method와 마찬가지로 수렴성을 보장하지는 않는다.

sgn은 부호 확인 함수이다.

5. Error analysis

• Linear convergence

• Quadratic convergence

6. Accelerating convergence

• Aitken’s Δ^2 method
  • iterative method의 수렴 속도를 가속화하는데 사용되는 간단한 기법이다.
  • 주어진 반복 선형적인 수열의 새로운 수열을 생성하여 더 빠르게 수렴하는 것이다.

7. Fail-safe methods

• Newton과 Bisection의 결합이다.

  • if(out of bound || small update by Newton) then update by Bisection method

    → rtsafe.c in NR in C

• Ridder’s method (good performance) → zriddr.c in NR in C
  

8. Summary