[수치해석] Ch6. Open Method

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶Open Method

bracketing method (아래 그림 6.1a)

bracketing method와 다르게, open method는 x 하나만 있거나 또는 반드시 근을 괄호로 묶지 않는 두 개의 시작 값만 필요한 공식을 기반으로 한다. 

때때로 계산이 진행됨에 따라 근으로부터 분리되거나 멀어진다(아래 그림 6.1b). 

그러나, 개방형 방법들이 수렴될 때(아래 그림 6.1c), 그들은 보통 bracketing method보다 훨씬 더 빠르다.

728x90

▶Simple Fixed-Point Iteration

f(x) = 0

    → x = g(x)

x^2 - 2x + 3 = 0

    → x = (x^2 + 3) / 2

sinx = 0

    → x = sinx + x

첫 번째 수식으로 예를 들면

    → x = g(x)

    → xi+1 = g(xi)

    → approximate error : Ea = |(xi+1 - xi) / xi+1| * 100%

ex. f(x) = e^(-x) - x

    → x = e^(-x)

    → xi+1 = e^(-xi), x0 = 0

f(x) = e^(-x) - x

    → f1(x) = f2(x)

    → y1 = f1(x), y2 = f2(x)

 

그렇다면 항상 근을 찾아내는 가?

접선의 기울기의 절댓값 |g'(x)| < 1

    → error가 점차 감소한다. -> 근을 찾을 수 있다. (수렴)

|g'(x)| > 1

    → error가 점점 증가한다. -> 근을 찾을 수 없다. (발산)

기울기가 양수 → 계단식이다.

기울기가 음수 → 회전식이다.

def function_fixpt(x0, es, imax, iter, ea):
	xr = x0
    iter = 0
    whilt True:
    	xr_old = xr
        xr = g(xr_old)
        iter = iter + 1
        if xr != 0:
        	ea = abs((xr - xr_old) / xr) * 100
        if ea < es or iter >= imax:
        	break
	return xr

▶Newton-Raphson Method

• 모든 root-locating 공식 중에서 가장 널리 사용되는 것은 Newton-Raphson 방정식이다.

Problem Statement

    → f(x) = e^(-x) - x, 초기값 x0 = 0으로 둔다.

Solution

    → f'(x) = -e^(-x) - 1

    → xi+1 = xi - (e^(-xi) - xi) / (-e^(-xi) - 1)

아래 식을 보면 Ei+1 = O(Ei^2)인 것을 알 수 있다.

이는 올바른 소수 자릿수가 반복될 때마다 약 두 배가 된다는 것을 의미한다.

1/10배 -> 1/100배 -> 1/10000배 : 나눠지는 값이 단계를 거칠수록 제곱이 된다.

항상 완벽한 것은 아니다.

Problem Statement

    → f(x) = x^10 - 1을 예로 들어보자.

    → initial은 x = 0.5로 가정한다.

Solution

    → xi+1 = xi - (xi^10 - 1) / 10 * xi^9 

Newton-Raphson 방법이 낮은 수렴을 보이는 네 가지 경우이다.

그렇기에 그래프 형태를 파악하는 것이 매우 중요하다.

Newton-Raphson 방법은 몇 가지 추가 기능을 통합함으로써 개선될 것이다.

    → 프로그램에 플롯 루틴이 포함되어야 한다.

    → 계산이 끝날 때 최종 근 추정치는 항상 원래 함수 대입 결과가 0에 가까운지 계산해야 한다.

    → 근에서 멀리 떨어져 있는 동안 느린 수렴, 진동 수렴으로 인해 작은 εa가 발생할 수 있는 경우를 부분적으로 보호한다.

    → 무한히 지속될 수 있는 진동, 느린 수렴, 발산 솔루션으로부터 보호하는 반복 횟수의 상한이 포함되어야 한다.

    → 계산 중에 언제든지 f'(x)가 0이 될 수 있는 가능성을 고려해야 한다.

프로그램은 또한 첫 번째 도함수를 계산하기 위해 수정되어야 한다.
이는 사용자 정의 기능을 포함함으로써 간단히 달성될 수 있다.