Introduction & Bisection Method

\(f \in C[a,b] \text{ and } f(a)f(b)<0\)
\(\{pn\}_{n=1}^{\inf}:\text{ by the bisection method}\)
Bisection method에 의해 구해지는 값을 수열로 표현해보자.

p를 실제 솔루션이라고 하면,
\(f(p)=0\)
\(|p_n-p| \le \frac{b-a}{2^n} \text{ when } n \ge 1\)

Proof

For each \(n \ge 1\)
\(b_n-a_n=\frac{1}{2^{n-1}}(b-a) \text{ and } p \in(a_n,b_n)\)
\(p_n=\frac{1}{2}(a_n+b_n)\)
\(|p_n-p| = |\frac{1}{2}(a_n+b_n)-p|\)

이 거리는 항상 \(a_n\)과 \(b_n\)사이의 거리의 반보다는 작다.
\(|p_n-p| \le \frac{1}{2}(b_n-a_n)=\frac{1}{2^n}(b-a)\)
\(\{pn\}_{n=1}^{\inf}\) converges to p.

Convergence Ratio

\(O(\frac{1}{2^n})\)

Example

[1,2] 구간에서 연속인 f(x)
\(f(x)=x^3+4x^2-10=0\)에 대해,
\(10^{-3}\)보다는 에러가 작았으면 한다.

초기조건
\(a_1=1,b_1=2\)

\(f(1)=-5,f(2)=14\)
\(f(1)f(2) \le 0\)

그럼 [1,2] 구간에서 해가 존재한다!

그럼 해는 구하면 되는데, 어느정도 iteration을 해야할까?
\(|p_n-p|=\frac{1}{2^n}(b_1-a_1)=2^{-n} \lt 10^{-3}\)

앙변에 log를 취하면,
\(log2^{-n} \lt log10^{-3}=-3\)
\(-nlog2 < -3\)
\(\therefore n \gt \frac{3}{log2} \approx 9.96\)

최소한 10번정도만 하면 된다.

Fixed Point Iteration

Newton’s Method

수렴하기 시작하면 아주 빠르게 수렴한다.