[수치해석] Ch5_2. Roots of Equations - False Position Method

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

▶False-Position Method

• 비록 bisection이 근을 결정하는 데 완벽하게 유효한 기술이지만, "brute-force" 접근법은 상대적으로 비효율적이다.
• bisection의 단점은 xl에서 xu까지의 간격을 같은 반으로 나눌 때 f(xl)와 f(xu)의 크기를 고려하지 않는다는 것이다.
• 예를 들어, f(xl)가 f(xu)보다 0에 훨씬 가깝다면, 루트는 xu보다 xl에 더 가까울 가능성이 높다.

false-position method 사용 방식

• step 1
  • 근이 있다고 추측되는 lower xl과 upper xu를 범위로 지정한다.
  • f(xl) * f(xu) < 0을 만족해야 한다.
• step 2
  • (xl, f(xl))과 (xu, f(xu)) 두 점을 이은 선분이 x축과 만나는 지점을 xr로 둡니다.
  • xr = xu - (f(xu) * (xl - xu))) / (f(xl) - f(xu))
• 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이다.

 

false-position method가 bisection보다 대체적으로 빠르다.
하지만, 모든 경우에서 다 그런 것은 아니다.

• ex. f(x) = x^10 - 1 (급격히 증가하는 그래프)
• root of between x = 0 and 1.3

 

▶Modified False-Position Method

• xl, xu 중에서 xr로 바뀌는 곳이 있을 것이다.
• 바뀌는 값이 아닌 다른 쪽을 xa라고 두고, (xa, f(xa))의 좌표를 (xa, f(xa)/2)로 두고 step을 진행한다.
• 1/2로 처리해주는 기준은 같은 쪽으로만 2번 이상 연속으로 xr로 바뀔 때 처리해준다.
• 그 방식이 modified false-position method이다.

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

• 이 알고리즘의 효과는 f(x) = x^10 - 1에 적용함으로써 입증할 수 있다. 
• 0.01%의 정지 기준을 사용할 경우, bisection과  표준 false position method 방법은 각각 14회, 39회 반복한다. 
• 대조적으로, modified false position method은 12회 반복할 것이다.