Fixed-Point Iteration

• $a\leq x\leq b$ 안에 정의된 f(x)가 f(p)=0인 값이 있다고 할 때, p=g(p)인 함수를 설정

• fixed point(고정점) : $p\in [a,b]$인 범위에서 g(p)=p인 [a,b] 범위 내의 함수 g가 있다고 할 때, g는 [a,b] 내에 고정점 p를 갖고 있다고 한다.

• Bisectional Method를 통해 얻은 근사해 $f(p_n)=0$을 구했을 때, 고정점으로 변환 시 $p_{n+1}=g(p_n)$으로 변환할 수 있다(iteration)

  • 이 n값을 무한으로 보내면 $p=g(p)$로 극한값을 구할 수 있다.

• y=x와 y=g(x)의 교점이 없는 경우 고정점 p는 존재하지 않음

  • bisectional method : (근이 있다면) 반드시 수렴하나, 계산이 느림(횟수가 많음)
  • Fixed-point : 적절한 함수 g(x)를 찾아야 하나, 계산이 빠르다

• $[0,1]$에서 $g(x) = 3^{-x}$의 함수를 정의할 때, $g'(x) = -3^{-x}log3$이므로 g(x)는 [0, 1]의 범위에서 감소함을 알 수 있다.

  • 그렇기 때문에 함수 g(x)는 [0, 1]의 영역(x범위)에 [0, 1]의 치역(y범위)를 갖고, 그 범위 내에서 감소하기 때문에 fixed point를 갖게 됨을 알 수 있다.

• 함수의 분포에 따라 범위 내에서 fixed point는 여러개일 수 있다.

  • 범위 [a, b] 내에서 [a, b] 범위로 연속하는 함수 g는, 미분값의 절대값이 1보다 작으면 유일한 fixed point를 갖게 된다.

  • [a, b] 범위의 x에서 $|g'(x)| < 1$를 만족하면 g의 fixed point는 하나만 존재한다.

  • 증명 : fixed point가 하나가 아닐 경우

    • $|p-q|=|g(p)-g(q)|=|g'(\zeta)||p-q|$ ( 평균값 정리 )
      < |p-q| (위의 정의에 따라서) 이므로 모순

---

• ex. f(x) = x-cosx = 0일 때

  • f(x)에서 x = cos(x) >> x가 fixed point
  • $p_{n+1}=cos(p_n)$의 극한을 구할 때 수렴 확인 - 약 p=0.739일 때 p=cos(p)의 식을 만족

• ex2. $g\in C[a,b]$이고, 모든 $x\in [a,b]$에 대해 $g(x)\in [a,b]$일 때, 함수 g가 고정점을 [a,b] 내에 갖는지?

  • C[a,b] : [a,b] 범위에서 연속인 함수의 집합 (continuous)

  • 입력 - 출력이 모두 [a,b]의 범위에 있는 함수 g를 의미

  • case 1. g(a) = a, g(b) = b >> 고정점이 반드시 존재

  • case 2. case 1이 아닌 경우

    • h(x)=g(x) - x로 정의하면, h(a)h(b) < 0 으로 IVP 성립 : g(c)-c=0으로 fixed point 존재한다.

• ex3. $x^2-x-1$

  • case 1. $x=x^2-1$ : $g(x) = x^2-1$
  • case 2. $x^2=x+1\rarr x=\sqrt{x+1}$ : $g(x)=\sqrt{x+1}$
  • case 2.를 이용한 풀이 :
    • x=0일 때 g(x) 값 계산
    • g(x) = x인 $x_1$값 계산
    • $g(x_1)$ 계산 후 과정 반복
    • 오차가 일정 이하가 되는 지점에서 해 계산

---

• $x^2-x-1=0$
• case 1. $x^2 = x+1 \rarr g(x) = \sqrt{x+1}$
  • x=0에서 반복 시작
    • g(0) 계산값을 g(0)=x로 대입
    • 계산된 x값을 다시 g(x)에 대입
    • 해당 과정을 일정 오차 이하기 될때까지 반복
      

      

    • 미분 계산 : $g'(x)=\frac{1}{2\sqrt{x+1}}$ - x가 -3/4보다 클 때 미분값은 항상 1보다 작게 되어 하나의 fixed point만 존재
• case 2. $x^2 = x+1 \rarr g(x) = 1+1/x$
  • 미분 계산 : $g'(x)=-1/x^2$이므로 x>1일 때 항상 $|g'(x)|<1$
  • 고정점 계산
    • $p_0=1\rarr p_1 = 2$
    • $p_1=2\rarr p_2=1.5$
    • $p_2 = 1.5\rarr p_3=1.666...$
    • $p_3=1.666\rarr p_4 = 1.6$
      

      

    • 위 과정을 반복
• Contraction Rate
  • 계산된 fixed point에서 g(x)의 미분값
  • Contraction Rate가 작을수록 빠르게 수렴 = 정확한 해에 더 빠르게 도달

---

• $x^3+4x^2-10$을 fixed point form으로 변환시 가능한 변환 형태

  • $x=x-x^3-4x^2+10$

  • $x=\sqrt{10/x-4x}$

  • $x=\frac{1}{2}\sqrt{10-x^3}$

  • $x=\sqrt{\frac{10}{4+x}}$

  • $x=x-\frac{x^3+4x^2-10}{3x^2+8x}$

• 1은 발산, 2는 허수가 되어 fixed point 게산 불가
• 5번의 경우가 가장 빠르게 fixed point로 접근하나, 상식적으로 생각 가능한 경우는 아님

---

• fixed point eq.의 수렴 증명
  • unique한 fixed point의 존재 조건에 의해 $|g'(x)|\leq k<1$
  • 즉 n번째 fixed point에 대해 $|p_n-p|\leq k|p_{n-1}-p|$
    • 이 계산을 0번째 fixed point(초기값)까지 반복하면 $|p_n-p|\leq k^n|p_0-p|$
  • k가 1보다 작기 때문에 반복(n)을 무한히 반복하면 오차 $|p_n-p|$는 0으로 수렴
• Corollary to the convergence result
  • $n\geq1$인 n에 대해 $|p_{n+1}-p_n|=|g(p_n)-g(p_n-1)|\leq k|p_n-p_{n-1}|$
    $...\leq k^n|p_1-p_0|$
  • $m>n\geq1$일 때, $|p_m-p_n|=|p_m-p_{m-1}+p_{m-1}-p_{m-2}+...+p_{n+1}-p_n|$
    $...\leq k^{m-1}|p_1-p_0|+k^{m-2}|p_1-p_0|+...+k^n|p_1-p_0|$
    $...\leq k^n(1+k+k^2+...+k^{m-n-1})|p_1-p_0|$
  • m이 무한으로 갈 때 위 식이 무한등비수열의 합이므로, $|p-p_n|=\frac{k^n}{1-k}|p_1-p_0|$
  • $\therefore |p-p_n|=\frac{k^n}{1-k}|p_1-p_0|\leq\epsilon$의 식으로 반복 회수 계산 가능

Root finding problem

• $f(x)=0$의 식을 만족하는 함수 f에 대해 근(해)를 찾는 과정
  • 이 식을 함수 f의 영점(zero) 라고 함.

Bisectional Method

• 중간값 정리(Intermediate Value Theorem, IVT)
  • 함수 f(x)가 [a, b] 범위 내에 정의 (f는 연속)
  • $f(a)f(b) < 0$이면 그 범위 내에 $f(p)=0$인 p가 존재
• bisectional method
  • $a_1=a, b_1=b$로 정의, a-b 사이의 중간점 p를 이용
  • $p_1 = \frac{a_1+b_1}{2}$
  • $f(a_1)f(p_1), f(p_1)f(b_1)$ 종 IVP를 만족하는 구간에 대해 위 과정을 반복
  • 오차가 일정 이하가 될 때 해당 값을 근으로 설정
• 오차
  • 절대오차(absolute error) : $p_N - p_{N-1} < \epsilon$
  • 상대오차(reletive error) : $|p_N - p_{N-1}|/|p_N| < \epsilon$
• Bisection method의 convergence rate
  • 수렴의 빠르기
  • $|p_n-p|\leq\frac{b-a}{2^n}$
  • $\therefore$ bisection method는 $O(\frac{1}{2^n})$의 빠르기로 수렴
  • Error bound : Convergence rate를 이용한 반복 회수 예측
    • $|p_N-p|\leq2^{-N}(b-a)<\epsilon=10^{-m}$
    • $-Nlog2<-m\rarr N>\frac{m}{log2}$