Dark Hypernova
Science and Fiction

A Basic Jacobi Iteration Procedure

回顾

我们要解决的问题是

为什么要解决这个问题呢?因为我们可以把一些问题转换成这类线性问题,例如我们可以把 $\nabla^2 \psi = \omega$ 通过离散化等方法来转换成上面的矩阵方程。

总结我们之前学过的方法,共有

  • Euler
  • RK
  • Adams
  • Shooting method
  • Finite difference discretization

然后离散化之后,我们需要解决$\mathbf A x = b$的问题,然后我们已经有了下面的方法

  • Gaussian Elimination
  • LU Decomposition

然后我们下面要学的是

  • Jacobi Iteration
  • Gauss-Seidel

两种。

Jacobi Iteration

我们来看一个例子:

我们可以对这些式子变形:

Done! 我们已经解出来啦。

等等,这些解里面有未知数啊?没问题,我们可以这样做。

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

这样不断迭代,就可以得到最终的解了。

我绘制了这个例子中,进行十次迭代的过程。横轴表示迭代的次数,纵轴表示x,y, z 的结果。

Jacobi Iteration

对于的列表是

\{\{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\}\}

在多次迭代之后,三个解都收敛了。实际上这三个收敛的结果就是x,y,z对于的解,即2,3,3。

收敛性

在高兴之余,我们可以考虑这样一种情况,即我们把三个方程的顺序换一下。

然后我们发现有的情况迭代的结果居然不收敛了。

这是为什么呢?这是因为 Jacobi Iteration 需要方程满足 SDD, Strict diagonal dominace 条件:

如果 $\vert a_{kk} \vert > \sum\limits_{j=1,j\neq k} \vert a_{kj} \vert$,那么我们就说这个矩阵是 SDD 的。

如果一个矩阵是 SDD 的,那么可以确保 Jacobi Iteration 的方法得到的结果是收敛的,不管初始的猜测有多坏。

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

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

更快的方法

我们上面的方法把迭代式子写出来,是

但是,我们返回来想想,我们为什么不立刻就使用我们已经得到的 $x_{K+1}$ 呢?这样会更快么?大致是更快的。

总结

解线性方程的方法

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

By OctoMiao

Last updated