3 minute read

์ˆ˜ํ•™๊ณผ ๋ณต์ˆ˜์ „๊ณต์„ ์œ„ํ•ด ์กธ์—… ๋งˆ์ง€๋ง‰ ํ•™๊ธฐ์— โ€œ์ˆ˜์น˜ํ•ด์„๊ฐœ๋ก โ€ ์ˆ˜์—…์„ ๋“ฃ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ์ˆ˜ํ•™๊ณผ ์กธ์—…์‹œํ—˜๋„ ๊ฒธ์‚ฌ๊ฒธ์‚ฌ ์ค€๋น„ํ•  ๊ฒธ ํ™”์ดํŒ… ํ•ด๋ด…์‹œ๋‹ค!! ์ „์ฒด ํฌ์ŠคํŠธ๋Š” โ€œ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์ž๋ฆฌ๊นŒ์ง€ ์ •ํ™•ํ•จ.