Bisection Method
์ํ๊ณผ ๋ณต์์ ๊ณต์ ์ํด ์กธ์ ๋ง์ง๋ง ํ๊ธฐ์ โ์์นํด์๊ฐ๋ก โ ์์ ์ ๋ฃ๊ฒ ๋์์ต๋๋ค. ์ํ๊ณผ ์กธ์ ์ํ๋ ๊ฒธ์ฌ๊ฒธ์ฌ ์ค๋นํ ๊ฒธ ํ์ดํ ํด๋ด ์๋ค!! ์ ์ฒด ํฌ์คํธ๋ โNumerical Analysisโ์์ ํ์ธํ ์ ์์ต๋๋ค.
๋น์ ํ ๋ฐฉ์ ์ $f(x) = 0$์ ๊ทผ์ ์ฐพ๊ธฐ ์ํ ์์น์ ๋ฐฉ๋ฒ ์ ๋๋ค. ํน์ ๊ตฌ๊ฐ์์ ํจ์ ๋ถํธ ๋ณํ๋ฅผ ์ด์ฉํด ๊ทผ์ด ์กด์ฌ ๊ฐ๋ฅํ ๋ฒ์๋ฅผ ์ ์ง์ ์ผ๋ก ์ขํ๋๊ฐ๋๋ค.
ํน์ง
ํด๋ฅผ ์ฐพ๊ธฐ ์ํด์ ํฐ ์์ด๋์ด๊ฐ ํ์ํ์ง๋ ์์ผ๋ฉฐ ์ง๊ด์ ์ ๋๋ค.
ํ์ง๋ง, ๋ช๊ฐ์ง ๋จ์ ์ด ์กด์ฌํ๋๋ฐ, ์๋ ด ์๋๊ฐ ๋ค๋ฅธ ์์น์ ๋ฐฉ๋ฒ์ ๋นํด ๋๋ฆฝ๋๋ค. ๋ค์์ ๋ค๋ฃจ๊ฒ ์ง๋ง, Bisection Method์ ์๋ ด ์๋๋ โ์ ํ ์๋ ด(Linear Convergence)โ์ด๊ณ , $O(c^n)$์ผ๋ก ํํ ํฉ๋๋ค. ๋ฐ๋ฉด์ โ๋ดํด-๋ฉ์จ๋ฒโ(์์ง ์ ๋ค๋ฃธ)์ โ์ด์ฐจ ์๋ ด(Quadratic Convergence)โ์ ์๋๋ก ์๋ ด ํฉ๋๋ค. ์ด๋ฐ ๊ด์ ์์ Bisection Method์ ์๋ ด์ด ๋๋ฆฌ๋ค๊ณ ํํํ๋ ๊ฒ ์ ๋๋ค.
Error Bound
Supp. that $f \in C[a, b]$ and $f(a)f(b) < 0$.
The Bisection method generates a sequence $\left\{ p_n \right\}_{n=1}^{\infty}$ approximating a zero $r$ of $f$ with
\[\| p_n - r \| \le \frac{b-a}{2^n}, \quad n \ge 1\]์ด ๋ช ์ ๋ Bisection Method๋กค $n$๋ฒ ์ํ ํ์ ๋์ ์ค์ฐจ์ ์ํ์ ๋ํด ๋ณด์ฅ ํฉ๋๋ค. ์ค์ฐจ์ ์ํ์ $(b-a)/2^n$ ์ ๋๋ค.
Rate of Convergence
Supp. $\left\{ \beta \right\}_{n=1}^{\infty}$ is a sequence known to converge to zero,
and $\left\{ \alpha_n \right\}_{n=1}^{\infty}$ converges to a number $\alpha$.
If there exists a positive constant $K$ s.t. for large $n$,
\[\| \alpha_n - a \| \le K \| \beta_n \|\]then we say that $\left\{ \alpha_n \right\}_{n=1}^{\infty}$ converges to $\alpha$ with โrate of converge $O(\beta_n)$โ.
Note
By Error Bound of Bisection method,
\[\| p_n - r \| \le \frac{b-a}{2^n}, \quad n \ge 1\]then $p_n - r = O(1/2^n)$. So, we say the sequence $\left\{ p_n \right\}_{n=1}^{\infty}$ converges to $r$ with rate of convergence $O(1/2^n)$.
Correctness
A solution is โcorrect within $p$-decimal placesโ,
if the error is less than $0.5 \times 10^{-p}$.
๊ทผ์ฌ๊ฐ $x_n$๊ณผ ์ฐธ๊ฐ $x$๋ฅผ $p$๋ฒ์งธ ์๋ฆฌ๊น์ง ๋ฐ์ฌ๋ฆผ ํ์ ๋ ๊ฐ์ ๊ฐ์ด ๋์ค๋ฉด, ๊ทธ ๊ทผ์ฌ๊ฐ์ ์์์ $p$์๋ฆฌ๊น์ง ์ ํํ๋ค๊ณ ํํํฉ๋๋ค.
์๋ฅผ ๋ค์ด, $\pi$์ ๊ทผ์ฌ๊ฐ
- ์ฐธ๊ฐ: $\pi \approx 3.141592$
- ๊ทผ์ฌ๊ฐ: $x_n = 3.1415$
๊ทธ๋ฆฌ๊ณ ๋ ๊ฐ์ 3๋ฒ์งธ ์๋ฆฌ๊น์ง ๋ฐ์ฌ๋ฆผ ํ๋ฉด
- ์ฐธ๊ฐ: $\pi \approx 3.141592 \rightarrow 3.142$
- ๊ทผ์ฌ๊ฐ: $x_n = 3.1415 \rightarrow 3.142$
๋ฐ๋ผ์ ๋ ๊ฐ์ด ๊ฐ์ผ๋ฏ๋ก ๊ทผ์ฌ๊ฐ์ ์ฐธ๊ฐ๊ณผ ์์์ 3์๋ฆฌ๊น์ง ์ ํํจ.