A Basic Jacobi Iteration Procedure

回顾

$\mathbf A x = b$

• Euler
• RK
• Shooting method
• Finite difference discretization

• Gaussian Elimination
• LU Decomposition

• Jacobi Iteration
• Gauss-Seidel

Jacobi Iteration

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

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

Done! 我们已经解出来啦。

1. 首先猜测一组 x, y, z 的解
2. 把这组解代入右边获得新的一组解
3. 把新的解代入右边再获得新的解

\{\{1, 1.75, 1.7625, 1.9625, 1.99062, 1.99109, 1.99859, 1.99965, 1.99967, 1.99995, 1.99999\}, \{1, 3.25, 3.9, 3.8875, 3.97188, 3.99625, 3.99578, 3.99895, 3.99986, 3.99984, 3.99996\}, \{1, 3.2, 3.05, 2.925, 3.0075, 3.00188, 2.99719, 3.00028, 3.00007, 2.99989, 3.00001\}\}


$O(N\cdot K\cdot ?)$

K 是迭代的次数，N 是维数。另外这个还跟矩阵里面与多少相邻的有关。

更快的方法

$\begin{eqnarray} x_{K+1} = \frac{7 + y_K -z_K }{ 4 } \\ y_{K+1} = \frac{21 + 4 x_K + z_K }{ 8 } \\ z_{K+1} = \frac{15 + 2 x_K - y_K }{ 5 } \end{eqnarray}$

总结

• Gaussian Elimination
• LU Decomposition
• Jacobi Iteration
• Gauss-Seidel

By OctoMiao

Last updated