[수치해석] Ch5_1. Roots of Equations - Bisection Method

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

▶Roots of Equations

방정식의 근을 구하는 가장 심플한 방법 : Trial and Error (시행착오)-> 비효율적이고 엔지니어링 관행의 요구 사항에 적합하지 않다.

 

정의에 따르면, y = f(x)가 주어진 함수는 fi = i차 다항식 x인 형태로 표현될 수 있다면 algebraic이다.(algebraic function : 대수 함수)
다항식은 일반적으로 n = 다항식의 순서와 a의 = 상수로 표현되는 대수 함수의 단순한 클래스이다.

 

대수 함수 (algebraic function)f2(x) = 1 - 2.37x + 7.5x^2f6(x) = 5x^2 - x^3 + 7x^6초월함수 (transcendental function)f(x) = lnx^2 - 1f(x) = e^(-0.2x) * sin(3x - 0.5)

 

초월함수는 대수 함수가 아니다.
여기에는 삼각함수, 지수함수, 로그함수 및 덜 친숙한 기타 함수가 포함된다.

 

chapter 5, 6에서는 algebraic과 transcendental에 대해서 한다.chapter 7에서는 real, complex root에 대해서 책에서 다루고 있다.

728x90

▶Roots of Equations in Engineering

• 앞에서 낙하산 비행사의 속도에 대해서 했다.
  • v = g * m * (1 - e^(-c * t / m)) / c
• 속도(v)가 명시적이기 때문에(즉, 왼쪽에서 따로 있다), 매개변수(c & m)와 시간(t)을 고려할 때 v를 계산하는 것은 쉽다.
• 그러나 질량(m)의 낙하산이 시간(t)에서 특정 속도를 갖도록 항력 계수(c)를 계산하고 싶다고 가정해 보자.
• c에 대한 방정식을 대수적으로 푸는 것은 불가능하다!
• 하지만 방정식을 근원 문제로 다시 표현할 수 있다.
  • f(c) = (g * m * (1 - e^(-c * t / m)) / c) - v
• 원하는 c 값은 f(c) = 0이 되는 값이다.

적당한 값을 계속해서 대입해보면 12~16 사이에 근이 있는 것을 알 수 있다.

▶Bracketing Methods (two point methods for finding roots)

• 루트에 대한 두 가지 초기 추측이 필요하다.
• 이러한 추측은 "bracket" 또는 루트 양쪽에 있어야 한다.
• 실수 및 연속 함수의 한 근인 f(x)=0이 x = xl 및 x = xu로 제한된다면,
  • f(xl) * f(xu) < 0
• 아래 그림과 같은 경우에는 적용하기 힘들 수 있다.

 

▶Bisect Method

• Bisect method의 세 단계
• step 1
  • 근이 있다고 추측되는 lower xl과 upper xu를 범위로 지정한다.
  • f(xl) * f(xu) < 0을 만족해야 한다.
• step 2
  • xr을 xl과 xu의 중간 값으로 설정한다. 
  • xr = (xl + xu) / 2
• step 3
  • a) f(xl) * f(xr) < 0이라면(xl과 xr을 반대에 위치하기에), xu = xr로 바꾸고 step 2로 돌아간다.
  • b) f(xl) * f(xr) > 0이라면(xl과 xr을 같은 쪽에 위치하기에), xl = xr로 바꾸고 step 2로 돌아간다.
  • c) f(xl) * f(xr) = 0이라면, 근은 xr이다.

추정 오차 구하는 방법 / 추정 오차와 실제 오차 비교

def function_bisect(xl, xu, es, imax, xr, iter, ea):
	iter = 0
    while True:
    	xr_old = xr
        xr = (xl + xu) / 2
        iter = iter + 1
        if xr != 0:
        	ea = (abs(xr - xr_old) / xr) * 100
        test = f(xl) * f(xr)
        if test < 0: # 다른 방향
        	xu = xr
        elif test > 0: # 같은 방향
        	xl = xr
        else:
        	ea = 0
       	if ea < es or iter > imax:
        	break
	return xr

이때는 반복할 때마다 f(xl)과 f(xr)을 구해줘야 한다.

(f는 값을 구해주는 함수이다. 따로 구현하지는 않았다)

while문안에 다른 함수 호출이 2개나 들어가게 된다.

조금 더 효율적을 바꾼 코드도 있다.

def function_bisect(xl, xu, es, imax, xr, iter, ea):
	iter = 0
    fl = f(xl)
    while True:
    	xr_old = xr
        xr = (xl + xu) / 2
        fr = f(xr)
        iter = iter + 1
        if xr != 0:
        	ea = (abs(xr - xr_old) / xr) * 100
        test = fl * fr
        if test < 0: # 다른 방향
        	xu = xr
        elif test > 0: # 같은 방향
        	fl = fr
        else:
        	ea = 0
       	if ea < es or iter > imax:
        	break
	return xr

while문 밖에서 f(xl)을 한번 해주고, while문 안에서는 f(xr)만 구해주어서 빠르게 바꾸어줬다.

xl = xr 대신 fl = fr을 사용해주었다.