[Numerical Analysis] 9. Jacobi Method, Gauss-Seidel Method

Numerical Methods

- Jacobi Method

- Causs-Seidel Method

 

Solving Large Linear Systems

- Global illumination (Radiosity) : not only direct illumination but also indirect illumination ( comming to other surface point not light source)

- Solve $B = (I - \rho F)^{-1}E$ : (E : light energe, B : individual color )

    - Need to solve for a large matrix

    - it takes too much time with conventional methods

 

Jacobi Method

- Iterative or approximate method (initial random guess)

- Solve a linear system $AX = B$

- Suppose a 3x3 matrix and nonzero diagonals

- reduce the error using equation

 

Ex) $\begin{matrix} 4x-y+z=7 \\ 4x-8y+z=-21 \\ -2x +y +5z = 15\end{matrix}$

$x = \frac{7+y-z}{4}$, $y = \frac{21+4x+z}{8}$, $z = \frac{15+2x-y}{5}$

True solution : (2, 4, 3)

- $P_0 = (x_0, y_0, z_0) = (1,2,2)$ -> random

  - $x_1 = 1.75$, $y_1 = 3.375$, $z_1 = 3.00$

-> repeat .... -> True solution 에 수렴함

 

- General formula : $x_i^{k+1} = \frac{1}{a_{ii}}(b_i - \sum_{j\neq i}a_{ij}x_j^k )$

- Convergence check : $\epsilon_i = | \frac{x_i^j - x_i^{j-1}}{x_i^j} < \epsilon_s$

 

Gauss-Seidel Method

- Speed up the convergence

- Use better approximations when possible

- $x_{k+1}$ is better approximation to $x$ than $x_k$

- $x_i^{k+1} = \frac{1}{a_{ii}} ( b_i - \sum_{j<i} a_{ij}x_j^{k+1} - \sum_{j>i} a_{ij}x_j^k )$

- 현재 iter 에서 이전에 계산한 변수를 가져다씀.

- $x_{k+1} = \frac{7 + y_k - z_k}{4}$ -> $ y_{k+1} = \frac{21 + 4x_{k+1} + z_k}{8}$ -> $z_{k+1} = \frac{15 + 2x_{k+1} - y_{k+1}}{5}$

 

 

Convergence

Sufficient condition for convergence

- Method always converge if the matrix A is diagonally dominant

- Row diagonal dominance : For each row, the absolute value of the diagonal term is greater than the sum of absolute values of other terms -> $|a_{ii}| > \sum_{i\neq j}|a_{ij}|$ -> we can chage order of row

 

Relaxation in Gauss-Seidel

Slight modification for improving convergence $x_i^{k+1} = \lambda x_i^{k+1} + (1-\lambda )x_i^k$, $0 < \lambda <2$

- if $\lambda =1$, no changes

- if $0 < \lambda < 1$, underrelaxation helps to make a nonconvergent system converge

- if $1 < \lambda < 2$, overrelaxation to accelerate to converge