[수리통계학] [4.3] Confidence Intervals for Parameters of Discrete Distributions

1. Introduction

- 이번 챕터에서는 다 정리하진 않을것이고, Bisection Algorithm만 다루겠습니다.

 

2. Bisection Algorithm

- Bisection Algorithms은 연속적인 1차원 함수의 root를 찾는 방법 중 하나이다.

- 특정 구간에서 함수 값이 0이 되는 점을 찾는 numerical approximation method이다.

 

2.1. 개념

- Bisection Algorithm은 다음과 같은 조건을 만족하는 continuous function에 적용가능하다.

-- 특정 구간 [a,b]에서 함수 f(x)의 부호가 변할 때, 즉 f(a)와 f(b)가 서로 다른 부호를 가질 때 적용 가능하다.

---> 즉, f(a)f(b) < 0이면, 중간에 최소한 하나의 root가 존재하게 된다.

-- Bisection Algorithm은 해당 구간 [a,b]를 절반으로 나누면서 점진적으로 근을 찾게 된다.

 

2.2. 알고리즘 과정

- 먼저, 시작 구간 [a,b]를 선택하고, f(a)와 f(b)의 부호가 다름을 확인한다.

- f(a) * f(b) < 0 을 확인한다.

 

- 중간점 c를 계산한다.

-->  c = (a+b) / 2

 

- 근이 포함되어 있는 구간을 선택한다.

-- f(c) = 0이면 c가 근이므로 종료

-- f(a)*f(c) <0이면, 새로운 구간[a,c]로 설정한다.

-- 그렇지 않으면, 새로운 구간 [c,b]를 설정한다.

 

- 이 과정을 계속 반복한다. (|b-a| < epsilon 까지)