[수치해석] 12. ODE Iterative Method

Jacobi Iterative Method

• 행렬 Ax=b를 풀 때
  • 초기 가정 $x^0$을 가정하고, $x^k$에 대해 k의 극한 계산
• Jacobi Iterative method
  • $x_i=\sum_{j=1,j\not ={i}}(-\frac{a_{ij}x_j}{a_{ii}})+\frac{b_i}{a_{ii}}$
  • 2x2 행렬에 대해, $\\a_{11}x_1+a_{12}x_2=b_1\\a_{21}x_1+a_{22}x_2=b_2$
  • 위 식에서 $\\x_1=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}x_2\\x_2=\frac{b_2}{a_{22}}-\frac{a_{21}}{a_{22}}x_1$
  • $x_1^{n+1}=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}x_2^n\\x_2^{n+1}=\frac{b_2}{a_{22}}-\frac{a_{21}}{a_{22}}x_1^n$
  • 계산된 해에 대해 $\frac{||x^k-x^{k-1}||_\infty}{||x^k||_\infty}$가 일정 오차 이하가 될 때까지 반복
• More general representation
  • 행렬 A를 $A=D-L-U$로 분리
    • D : 대각행렬 / L : Lower Triangle / U : Upper Triangle
  • $Ax=b$를 계산하면 $x=D^{-1}(L+U)x+D^{-1}b$, 즉 $x=Tx+c$꼴로 변환
  • $\rho(T)<1$ 혹은 $||T||_\infty$임을 증명하면 $x^k=Tx^{k-1}+c$가 수렴함을 증명할 수 있다.

Gauss-Seidel Method

• $x_1^{n+1}=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}x_2^n\\x_2^{n+1}=\frac{b_2}{a_{22}}-\frac{a_{21}}{a_{22}}x_1^{n+1}$

• $x^n=x$로 수렴하기 위한 조건

  • $T^nx^0$가 0으로 수렴
  • $S^nc$는 x로 수렴
  • 즉 $\rho(T)<1,\ ||T||_2<1,\ ||T||_\infty<1$중 하나를 만족
    • 앞으로 갈수록 sharp한 수렴, 계산은 복잡
  • 한 열에서 사용한 결과값을 바로 다음 열에 사용하므로 계산 시간이 줄어듬
  • $\begin{bmatrix} b1\\ b2 \end{bmatrix}=\begin{bmatrix} a_{11}\ 0\\ a_{21}\ a_{22} \end{bmatrix}+\begin{bmatrix} 0\ a_{12}\\ 0\ 0 \end{bmatrix}$

• $Dx^{n+1}=Lx^{n+1}+Ux^n+b$

  • D : A행렬의 대각선 원소 / L : L행렬 대각원소의 아랫부분 / U : L행렬 대각행렬의 윗부분

• $\rho(T)<1$일 때, $(I-T)^{-1}$을 만족

  • $S_n=(I-T)^{-1}=I+T+T^n+...+T^n$
  • $(I-T)S_n=I-T^{n+1}$
  • n이 발산하면 S는 I로 수렴

---

• fixed-point iteration 형태의 표현
  • $x^k=Tx^{k-1}+c$
  • jacobi iteration : $T_j=D^{-1}(L+U)$
  • gauss-seidel : $T_g=(D-L)^{-1}U$

Successive Over Relatxation(SOR)

• $x^{n+1}=(1-w)x^n+wx_g^{n+1}$
  • w : relaxation parameger
  • $w_g$ : gauss-seidel로 계산한 값
• Residual Vector
  • gauss-seidel method에서 $x^{n+1}=\frac{1}{a_{11}}[-a_{12}x_2^n+b_1]$
  • 즉 $a_{11}x_1=a_{11}x_1^{n+1}-a_{11}x_1^n\\=-a_{11}x_1^n-a_{12}x_2^n+b_1=r_1^n$으로 정의
  • residual form : $x^{n+1}=x^n+D^{-1}r^n$
  • SOR residual form : $x^{n+1}=x^n+wD^{-1}r^n\\x^{n+1}=(1-w)x^n+wD^{-1}(Lx^{n+1}+Ux^n)$