[수치해석] Open Method : Simple Fixed-Point Iteration & The Newton-Raphson Method

Open Method

Bracketing method는 두 점 사이. Lower Bound와 Upper Bound 사이에서 근의 유무를 찾아냈습니다.

두 점을 이용해서 근을 탐색하였고 방법마다 속도의 차이는 있겠지만 반드시 근을 찾아냈습니다.

 

하지만 Open Methods는 하나의 점만으로 근을 찾아낼 수 있습니다.

Simple Fixed-Point Iteration방법과 Newton-Raphson 방법이 있습니다.

(a) Bisection / (b), (c) 한점에서 해를 찾아가는 과정의 Open method

---

방법 1) Simple Fixed-Point Iteration

하나의 점 ( 고정 점) 을 지나가는 함수에 대해서 조사하는 방법으로 만일 y = x와 교점이 없다면 이 방법을 사용할 수 없습니다.

다음과 같은 방법으로 y = x와 주어진 함수의 교점을 찾아낼 수 있도록 함수를 변형하는 것이 중요합니다.

시작점 c(i)를 잡았다면 f(c)의 값을 y = x 함수에 직교하도록 그어서 닿은 점을 c(i+1) 구합니다.

반복해서 c(i+1)의 값을 이용해 f(c(i+1))의 값을 구해 y = x 함수에 직교하도록 그어서 닿은 점을 c(i+2) 구합니다.

다음과 같은 과정을 반복하던 중 f(c(i)) = c(i)인 값이 Root가 되는 값입니다.

---

[예제]

[아래의 Solution] f(x)식을 우선 변형하여 접근합니다.

그래프를 그려보면 반복할 수록 근에 가까워지는지 또는 진동하거나 발산하는지 알 수 있다.

(a) (b) 의 경우, 근에 수렴하고 있지만,

(c) (d) 의 경우, 근에서 점점 멀어지고 있는 상황이다.

---

The Newton-Raphson Method

가장 널리 사용되고있는 Root-locating formulas

 

시작점 x(i)에서 직교하는 직선을 그어 x축과 만다는 점 x(i+1)를 구한다.

x(i+1)에서 직교하는 직선을 그어 x축과 만나는 점 x(i+2)를 구한다.

. . . . .(과정을 반복해서 근을 찾아간다). . . . . .

 

동일한 예제를 통해 이해해보자. 다음 함수의 근을 구해보자.

x(i)를 반복할수록 근에 가까워질 수 있는데

단, 4번 만에 실제 값에 가까워진 것을 알 수 있다.

Quadratic Convergence : 실제 값(참 값)에 해당하는 숫자가 과정을 거칠 때마다 2배씩 늘어나는 과정을 의미한다.

Quadratic Convergence

자료의 출처  [위키백과 : 뉴턴 방법]

 

그러나 언제나 하나의 방법이 모든 상황에서 최고의 방법이 될 수는 없다.

f(x) = x ^ 10 - 1 함수에 대한 근을 구하고자 할 때 시작점 x = 0.5에서 근을 구해보자.

실제 값( 참 값) x = 1에서 Iteration을 반복할수록 멀어지고 있음을 알 수 있다. 이처럼 뉴턴 방법 또한 항상 최적의 방법이 될 수 없고, 시작 값에 따라서 다른 결과를 마주할 수 있다.

(a), (b) Root 근처에 가지 못하고 헛돌고 있는 상황

(c) Root을 찾지 못하고 값이 많이 튀고 있는 상황

(d) Root가 없음을 알지 못하고 탐색 중인 상황

---

The Newton-Raphson Method를 사용해서 프로그래밍할 때 팁

1) 그래프에 점을 찍어가면서 상황을 관찰하기

2) 반복할 때 Iteration Max를 정해 부어서 Oscillating, Convergnet, Divergent solution을 방지할 수 있다.

3) f(x)에서 편미분 한 값이 0이 될 경우엔 더 이상 탐색하지 못하므로 이 상황에 대해 인지해야 한다.

---

요약

Open Method는 Bracketing Methods과는 달리 한 점을 이용해서 근을 구할 수 있으며

Newton-Raphson, Simple Fixed-Point 방법이 있다.

Simple Fixed-Point 방법의 경우 y = x 함수에 접점이 없다면 해를 구할 수 없고, 그래프를 그리며 plotting 과정을 통해 관찰하여 해에 근접하는지 발산하는지를 파악할 수 있다.

Newton-Raphson의 경우, 한 시작점에서 직교하는 접선을 이용하는 방식으로 시작 점에 따라서 근을 구할 수도 못 구할 수도 있다. 항상 Best인 방법은 없다.