Introduction & Bisection Method

비선형 방정식이 주어졌을 때 어떻게 답을 찾아낼 것인가에 대한 고민을 해보자.

이차방정식에 대해 중등교육과정에서 근의 공식(formula)을 사용했었다.

그러나, 훨씬 복잡한 고차식의 일반적인 경우는 근의 공식으로 풀 수 없다.

고차방정식이나, 초월함수 같은건 다루기 어렵다.

인수분해나 다른 수학적 이론으로 정확한 해를 찾기 힘들다면, 이러한 비선형방정식(nonlinear equation)에 대한 근사해를 찾는 법에 관한 얘기를 해보자.

가장 잘 알려져있는 세가지 방법을 소개한다.

Bisection Method
Fixed Point Iteration
Newton’s Method

Bisection Method

우리의 목적은 f(x)=0인 solution x를 찾는 것이다.

Bisection Method는 2분법을 의미한다.

먼저 함수가 연속이라는 가정을 하자.

생각하고자 하는 구간 [ a,b ]는 연속이다.

만약 f(a)와 f(b)의 곱이 음수라면 근사해는 [a,b] 사이에서 찾을 수 있다.

연속이면서, f(a), f(b)의 곱이 음수라는게 조건이다.

이분법이라는 건 이 a와 b를 계속해서 이분해 나가는 것이다.
\(\frac{a+b}{2}\)를 f에 넣어보고, 그 부호를 판단한다.

만약 a가 음수고 b가 양수라고 해보자. 이분한 부분이 양수라면 a와 이 점을 또 비교해보고, 음수라면 b와 비교한다.

또다시 중간점을 찾아서 같은 것을 반복하다보면 수렴하게 된다.

실제로는 완벽한 정답을 찾을 수 없으므로, tolerance를 줘서 일정 구간 안의 오차라면 stop한다.
또한 답을 시간 내에 찾을 수 없을 수도 있으므로 maximum number of iteration도 준다.

Fixed Point Iteration

What is Fixed Point?

어떤 함수를 가지고 있다고 하자.

g(x): a function
p: a fixed point for g(x), if g(p)=p

f(x)=x-g(x) 라고 한다면,
f(x)=0인 점을 찾는 것은, x-g(x)=0을 찾는 것과 같다.

즉, fixed point를 찾는다는 말은 f(x)라는 함수의 해를 찾는 것과 같다.

그렇다면 fixed point는 어떠한 조건하에서 존재하는가?
만약 존재한다면 하나만 존재하는가 여러개가 존재하는가?

만약 하나만 존재하면 훨씬 수월한 부분이 많다.

언제 fixed point가 존재하는가

Theorem
(a) \(g \in [a,b]\) and \(g(x) \in [a,b]\) for all \(x \in [a,b]\) then g has a fixed point in [a,b].

(a) 조건에서 fixed point는 존재한다.

언제 fixed point가 단 한개 존재하는가

Theorem
(b) If g’(x) on (a,b) \(\exists\) 0 < k < 1 with \(|g'(x)| <= k\) for all \(x \in (a,b)\) then fixed point is unique.

Proof
Aim: Find p s.t. g(p)=p
1) If g(a)=a then a is fixed point or g(b)=b then b is fixed point 2) If not, let h(x)=g(x)-x (두 연속인 함수의 합과 차는 연속), \(\because\) continuous on [a,b].
If
h(a) = g(a)-a > 0 (\(\because\) g(a) > a) and
h(b) = g(b)-b < 0 (\(\because\) g(b) < b)
h(b) < 0 < h(a) \(\exists\) p \(\in\)(a,b) s.t. h(p)=0
h(p)=g(p)-p=0
p: a fixed point for g(x)

Proof. Uniqueness

Calculus의 가장 중요한 정리중 하나가 평균값 정리(Mean Value Theorem)이다.
매우 활용도가 높다.

Newton’s Method

기울기와 x절편을 활용함.