1. Error analysis of N-R method

• Newton Raphson method가 Quadratic convergence를 갖는 이유이다!

2. Error analysis of Secant Method

• 즉, f’(x)의 계산이 복잡하면, N-R method보다 더 효율적이다.
• Modified secant method
  • 기본적인 도함수의 정의를 사용하여 N-R method의 근사식을 수정해서 사용한다.

3. Multiple roots

• Bracketing methods는 중근들을 다룰 수 없다.
• Open methods는 중근들을 찾을 수 있다.
  • 하지만 많은 경우에 속도는 상당히 느리다.
  • f’(x) → 0은 문제를 일으킬 수 있다.(divide by zero)
  • f(x)는 항상 f’(x)보다 먼저 0에 도착한다.
    • 따라서, f(x)에 대한 제로 체크가 프로그램에 포함되어 있으면, f’(x)가 0에 도달하기 전에 계산을 종료할 수 있다.
  • u(x) = f(x)/f’(x)를 사용하는 방법도 있다.

4. Polynomial evaluation

• Bad method
  • p = c[0] + c[1] x + c[2] x x + c[3] x x x + c[4] x x x x;
• Worst method
  • p= c[0] + c[1] x + c[2] pow(x, 2.0) + c[3] pow(x, 3.0) + c[4] pow(x, 4.0);
  • pow는 부동 소수점 연산을 수행하므로 round off 오차가 발생할 수 있다.
• Best method

  • p = c[0] + x (c[1] + x(c[2] + x (c[3] + xc[4])));

    or

  • p = (((c[4] x + c[3]) x + c[2] ) x + c[1]) x + c[0];

5. Polynomial differentiation

• dp는 미분한 값

6. N-th derivations

7. Polynomial deflation

• Multiplication by (x-a) (x-a를 곱하는 것)

c[n] = c[n-1];
for (j = n-1 ; j>=1; j--) c[j] = c[j-1] - c[j] * a;
c[0] *= (-a);

• Synthetic division by (x-a) (조립제법)

rem = c[n];
c[n] = 0.0;
for (i = n-1; i>=0; i--){
	swap = c[i];
	c[i] = rem;
	rem = swap + rem * a;
}

1) Bairstow’s method

• Deflation method (높은 차수의 다항식을 낮은 차수의 다항식으로 줄이는 것)

• b0과 b1이 되는, r과 s를 찾는다.
• synthetic division을 사용하여 효율적인 방법이 있다.
• r,s 값에 대한 초기 추측이 매우 중요하다.
• 복소수(허수) 해도 구할 수 있다.
• 근을 더 정확하게 평가하는 “root polishing”에 적합하다.
• In Numerical Recipes in C
  • void qroot();

a) Basic Concept

• polynomial의 근을 결정하는 것 : polynomial을 x-t로 나눈다.

• remainder R = b0, 이며 각 계수들은 다음과 같은 관계를 가진다.

• 만약 t가 original polynomial의 근이라면, 나머지 b0은 0이여야 한다.

b) Evaluation of complex roots

• polynomial을 quadratic factor x^2 - rx- s으로 나눈다.

• 이때, normal synthetic division을 사용해여, Remainder R = b1(x-r) b0를 얻을 수 있다.
• 이전과 마찬가지로 계수들은 다음과 같은 관계를 갖는다.

c) Taylor series

• b0과 b1이 r, s로 이루어진 함수이기에, Taylor series를 사용하여 전개할 수 있다.

• 우리의 목적은 b0과 b1을 0에 가깝게 만드는 것이 목적이기에, 식을 전개 하면 이와 같은 식을 얻을 수 있고, 이 방정식을 풀면 r의 변화량과 s의 변화량을 얻을 수 있다.
• 이 값을 토대로 초기 r, s값을 더 정확하게 설정 할 수 있다.

d) Taylor series

• 각 단계에서 r과 s의 오차는 이와 같다.
  

• 이 두 오차 추정값이 사전에 정해진 기준보다 작이지면, 근의 값을 근의 공식을 사용하여 결정 할 수 있다.
  

• 여기서, 3가지 가능성이 존재한다.
  1. 몫이 3차 다항식 이상이다. → 반복적으로 몫을 축소한다.
  2. 몫이 2차 다항식이다 → 근을 구한다.
  3. 몫이 1차 다항식이다. → 근을 구한다.

2) Laguerre method

• Deflation method
• Algorithm은 다음과 같다.

• 시작점(초기 추정값)에서 시작한다.
• 위의 공식을 사용하면 추정 값 x1을 얻을 수 있다.
• 만약, 근을 찾는다면 원래 다항식을 해당 근으로 나누어서 더 낮은 차수의 다항식을 얻는다.
• Laguerre method도 복소수 근을 찾을 수 있다.

3) Application of Root Finding: Electric circuit design

• Problem: Find the proper R to dissipate energy to 1% at a specified rate(t = 0.05s), given L = 5H, C = 10^-4F.
• Solution:

• Reasonable initial range for R:
  • 0 < R < 400
• To achieve r.e. of 10-4%