[수치해석] 01. Finding Roots

방정식에서 근을 찾기위해 (estimate)하기위한 방법을 배운다.

 

estimation 시에 에러를 표기하는 방법

1.  Accuracy : 정확함, 오차 평균

2.  Precision : 정교함, 오차 편차

에러의 종류

1. True error  :  ( 실제 값 ) - ( 추측 값 )

2. Absolute error  :  true error의 절대값

3. True fractional relative error  :  ( true error ) / ( 실제 값 )

    측정하려는 값의 범위에 맞게 error를 보정해준다. ( normalizing )

    ex) tree error가 1일 때, 실제 값이 10이냐, 100이냐에 따라 1의 의미가 다르다. (0.1% 에러 혹은 0.01%에러)

4. Relative error  :  true fractional relative error를 %로 표현한 값이다.

 

 

근을 구하는 방법

근(root)란 방정식을 성립하게 하는 값을 말한다.

1차 2차 방정식이라면, 근의공식 등을 이용하여 쉽게 구할 수 있지만 고차원 방정식은 인수분해(factorization)를 통해 구하기도 어렵다.

때문에, Graphical Methods를 통해 대략적인 그래프의 모양과 근의 존재여부를 파악 후 근을 구한다.

 

1. Lower bound, upper bound 를 이용하여 근 찾기

 

Bracket

함수가 연속적일 때, x_l, x_n을 잡아서 f(x_l)과 f(x_n)의 부호가 다르다면 근이 존재한다고 하는 방법이다.

구간을 나누어 그 구간 안에 근이 있는지 없는지 판단하고, 근이 존재한다고 생각되는 구간의 크기(interval)를 좁혀나가며 근을 찾는다.

이러한 방법은 쉽고 간단하지만, 두가지 단점이 있다.

(1) 근들이 몰려있거나 interval이 크면 근을 발견하지 못할 수 있다.

(2) 중근이나, 두개 이상의 근을 찾을 수 없다.(es. 근이 3개라 해도, 근의 존재만 알 수 있고, 3개인지는 알 수 없다.)

 

Bracket을 위해 interval을 줄여나가는 방법은 두가지가 있다.

 

A. Bisection

구간을 절반씩 줄여가며 원하는 오차범위 안에 들어오면 구간의 중간값을 근으로 estimate한다.

이는 초기 interval의 크기와 몇번이 반복되는지에 영향을 받고, 절반씩 줄어들기 때문에, absolute error가 2ⁿ씩 감소한다.

오차범위 안에 들어오면 근 찾기를 멈춰준다.(stop condition)

 

B. False position

 

현재 함수값들을 직선으로 이어 나온 점을 새로운 x값으로 정한다.

f(x_r)이 음수면 x_r이 x_l이 되어 다시 과정을 반복한다.

f(x_r)이 양수면 x_r이 x_u가 되어 다시 과정을 반복한다.

결국 x_r이 점차 근으로 가게된다.

False position이 Bisection보다 대체로 효율이 좋지만, 함수에 따라 Bisection이 더 좋은 경우도 있다. (ex. f(x) = x¹⁰-1)

 

 

 

2. 근이라 생각되는 initial 하나의 값을 바꾸어가며 근을 찾는다.

 

Newton-Raphson method

f(x)가 연속적이고 미분 가능한 함수라 할 때, (x, f(x))에서 접선을 그어 나온 해가 다음 x가 된다.

x가 더이상 변하지 않는 다면 (일정 구간에 머문다면) 그 수렴값이 곧 근을 estimate한 값이 된다.

x_i+1을 구해보면 변화량이 기울기에 반비례하고 함수값에 비례하기 때문에 빠르게 근에 해당하는 값으로 수렴한다.

위와같은 방법으로 다음 x를 one step에 구할 수 있다.

 

오차범위안에 들어오면 근 찾기를 멈추면 된다.(stop condition)

 

장단점

장점   : 빠르게 수렴하고, 원하는 값을 많이 비슷하게 찾을 수 있다.

단점   : 몇몇 그래프들은 수렴하지 않아 근을 찾기 불가능하다. 때문에 그래프의 모양을 보고 근이 있을법한 initial 개수를 미리 구해야된다.

(a)(b)(c)같은 경우, 변곡구간이 있어 근을 찾기 어렵고 (d)같은 경우는 기울기가 x축과 평행하여 근을 찾을 수 없으므로 값의 인위적인 변형이 필요하다.

 

 

 

Secant method

 

Newton-Raphson과 비슷하지만 미분값을 직접 구할 수 없을 때 이 방법을 사용한다.(기울기를 approximation)

사실 상, initial x값이 하나가 아니라 두개가 되어야된다. (아주 가까운 거리의 x값 두 개, 기울기를 구하기 위해서)

 

 

 

comments

 

- 정확한 해를 찾기 위해 적절한 interval을 사용해야된다. (작을수록 정확하지만, 반복수가 많아진다.)

- newton-raphson 방법 같은경우, 적절한 initial x값을 구하는 것이 중요하다. 다만, 정확한 initial x값을 구하기란 불가능하므로 (정확한 initial x란 실제 그 근을 의미한다.) 그래프를 그려, 근에 가까운 값을 initial x로 잡는것이 좋다. (computingskillset.com/solving-equations/how-to-find-the-initial-guess-in-newtons-method/) 

- 이러한 방법 뿐만 아니라 여러 방법이 있고, 함수 모양에 따라 적절한 방법을 선택하여야된다.