Bisection Method
μνκ³Ό 볡μμ 곡μ μν΄ μ‘Έμ λ§μ§λ§ νκΈ°μ βμμΉν΄μκ°λ‘ β μμ μ λ£κ² λμμ΅λλ€. μνκ³Ό μ‘Έμ μνλ κ²Έμ¬κ²Έμ¬ μ€λΉν κ²Έ νμ΄ν ν΄λ΄ μλ€!! μ 체 ν¬μ€νΈλ βNumerical Analysisβμμ νμΈν μ μμ΅λλ€.
Bisection Method
λΉμ ν λ°©μ μ $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μ리κΉμ§ μ νν¨.
λ§Ίμλ§
μ΄μ΄μ§λ ν¬μ€νΈμμλ λ€λ₯Έ μ κ·Ό λ°©λ²λ€μ μ΄ν΄λ΄ λλ€.