삼분법

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

삼분법(Trisection Method) 요약

주요 특징

• 삼분법은 유니모달 함수의 극점을 구하기 위해 사용.

• 구간을 균일하게 3개로 나누고, 삼등분점의 함숫값을 비교하여, 정답 가능성이 없는 구간 하나를 배제.

삼분법의 이해

삼분법은 특정 조건을 만족하는 함수의 최댓값 또는 최솟값을 구하기 위해 사용되며,

전체구간을 균일하게 3구간으로 쪼갠 뒤, 

그 중 정답 가능성이 없는 구간 하나를 찾아 배제하는 기법이다.

삼분법의 결과에 대해 또 다시 삼분법을 수행할 수 있으며,

함수의 극점은 점점 구간의 중점에 수렴한다.

수행할 때 마다, 최대오차는 2/3수준으로 줄어든다.

배제할 구간을 선택하는 기준은 3등분점의 함숫값 비교 (대소관계) 이다.

최댓값 예측

• f(m1) < f(m2) 이라면,  최댓값은 m1 이전 구간에 없다.

• f(m1) > f(m2) 이라면,  최댓값은 m2 이후 구간에 없다.

최솟값 예측

• f(m1) < f(m2) 이라면,  최솟값은 m2 이후 구간에 없다.
• f(m1) > f(m2) 이라면,  최솟값은 m1 이전 구간에 없다.

삼분법의 제약

삼분법을 적용하려는 함수는 다음 규칙을 만족해야 한다.

• 함수안에 극점(mode)이 하나(uni-)여야 한다.  → 유니모달(uni-modal) 함수  

삼분법이 추측범위를 2/3으로 줄이는 근거는,  삼등분 점의 함숫값 비교인데,

이러한 정보가 아무런 도움이 되지 않는 상황에서는, 그 근거가 없어지는 것 이다.

아래 함수처럼 여러개의 극점이 포함되어 있다면,

삼등분점을 비교하여 극점의 위치를 추측하는 것은 무의미하다.

삼분법과 미분

삼분법은 극점을 구하는 것이 주요 목표이므로,  도함수 f'(x)의 해를 푸는 것과 같지만

삼등분점의 함숫값을 기반으로 하기 때문에, 도함수와 관계없이 극값을 구할 수 있다.

즉, 미분이 까다롭거나 불가능한 함수에도 적용할 수 있다.

삼분법의 특징

• 함숫값 기반으로 극점을 구한다.   → 도함수를 구하지 않아도 된다.
• 정해진 횟수의 분할로 극점을 구한다.   → 시간복잡도 예측이 쉽다.

예제 # 초월함수의 극점구하기

미분이 까다로운 초월함수의 극점을 찾아보자.

사용된 그래프는 다음과 같으며, 

유니모달 제약을 만족하므로 삼분법을 적용할 수 있다.

단조함수와 삼분법

함수가 수평구간을 허용한다면, 최대값을 만족하는 x가 유일하지 않을 수 있으며,

이 때, 삼분법은 최대값을 만족하는 x들의 전체구간을 반환해야 한다.

이러한 이슈를 해결하는 방법에 대해서는

이미 여기에서 설명하였다.