이뢄 탐색을 톡해 ν•¨μˆ˜μ˜ ν•΄λ₯Ό μ°Ύμ•„κ°€λŠ” 방법에 λŒ€ν•΄

3 minute read

μˆ˜ν•™κ³Ό λ³΅μˆ˜μ „κ³΅μ„ μœ„ν•΄ μ‘Έμ—… λ§ˆμ§€λ§‰ 학기에 β€œμˆ˜μΉ˜ν•΄μ„κ°œλ‘ β€ μˆ˜μ—…μ„ λ“£κ²Œ λ˜μ—ˆμŠ΅λ‹ˆλ‹€. μˆ˜ν•™κ³Ό μ‘Έμ—…μ‹œν—˜λ„ 겸사겸사 μ€€λΉ„ν•  κ²Έ ν™”μ΄νŒ… ν•΄λ΄…μ‹œλ‹€!! 전체 ν¬μŠ€νŠΈλŠ” β€œ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μžλ¦¬κΉŒμ§€ 정확함.


맺음말

μ΄μ–΄μ§€λŠ” ν¬μŠ€νŠΈμ—μ„œλŠ” λ‹€λ₯Έ μ ‘κ·Ό 방법듀을 μ‚΄νŽ΄λ΄…λ‹ˆλ‹€.