迭代法适合求解大型稀疏线性方程组(阶数高，零元素多)。作为一种求解数值问题的通用方法，迭代法的基本思想是统一的，即利用设计好的迭代公式所产生的迭代序列逐步逼近精确解。

   设有线性方程组 $  \boldsymbol{A{}x}=\boldsymbol{b}$ (6.35)

其中$\boldsymbol{A}$ 非奇异，此时方程组(6.35) 有唯一解$\boldsymbol{x}^\ast$.

   将方程组  $(6.35)$ 变形为等价形式

           $  \boldsymbol{x}=\boldsymbol{B{}x}+\boldsymbol{f}$  (6.36)

 譬如取 $\boldsymbol{B}=\boldsymbol{I}-\boldsymbol{A}$ .

 从某一初始向量 $\boldsymbol{x}^{(0)}$ 出发，构造相应的迭代公式(格式)

$ \boldsymbol{x}^{(k+1)}=\boldsymbol{B{}x}^{(k)}+\boldsymbol{f},(k=0,1,2,\cdots.)$ (6.37)

    由此产生一向量序列 $\boldsymbol{x}^{(k)},(k=0,1,2,\cdots.)$ ，若对于任意的$\boldsymbol{x}^{(0)}$，相应的~$\boldsymbol{x}^{(k)}$ 的极限存在：$\lim\limits_{k\rightarrow \infty}\boldsymbol{x}^{(k)}=\widetilde{\boldsymbol{x}}$ ，则由$(6.37)$ 式可知~$\widetilde{\boldsymbol{x}}$ 是方程组~$(6.36)$ 的解(即~$(6.35)$ 的解)， 此时称迭代公式 $(6.37)$ 是收敛的，否则称迭代公式 $(6.37)$ 是发散的.在收敛的前提下，取足够大的 $k$，将 $\boldsymbol{x}^{(k)}$ 作为 $\boldsymbol{x}^{\ast}$ 的近似向量。这种求解方程组的方法称为迭代法，$\boldsymbol{B}$ 称为迭代矩阵。

迭代法的优点是不需要存储系数矩阵的零元素(从而适合大型稀疏方程组)且程序设计容易，主要的问题是收敛性问题。

一、Jacobi 迭代法

 Jacobi(雅可比) 迭代法是最简单的实用迭代方法，因而也称为简单迭代法。在方程组 (6.35) 中，令

$\begin{array}{c} \textbfsymbol{A}=\textbfsymbol{D}-\textbfsymbol{L}-\textbfsymbol{U} \\ =\begin{bmatrix} a_{11}\\ &a_{22}\\ &&\ddots\\ &&&a_{nn}\\ \end{bmatrix} -\begin{bmatrix} 0\\ -a_{21}&0\\ -a_{31}&-a_{32}&0\\ \vdots&\vdots&\vdots&\ddots\\ -a_{n1}&-a_{n2}&\cdots&-a_{n,n-1}&0\\ \end{bmatrix}\\ - \begin{bmatrix} 0&-a_{12}&-a_{13}&\cdots&-a_{1n}\\ & 0 &-a_{23}&\cdots&-a_{2n}\\ & &\ddots &\ddots&\vdots\\ & & &\ddots&-a_{n-1,n}\\ & & & &0\\ \end{bmatrix} \end{array}$

方程组 (6.35) 变形为

      $\begin{array}{c} (\textbfsymbol{D}-\textbfsymbol{L}-\textbfsymbol{U})\textbfsymbol{x} = \textbfsymbol{b}\Leftrightarrow \\ \textbfsymbol{D}\textbfsymbol{x} = (\textbfsymbol{L}+\textbfsymbol{U})\textbfsymbol{x} + \textbfsymbol{b} \Leftrightarrow \\ \textbfsymbol{x} = \textbfsymbol{D}^{-1}(\textbfsymbol{L}+\textbfsymbol{U})\textbfsymbol{x} + \textbfsymbol{D}^{-1}\textbfsymbol{b} \end{array}$

得 (6.36) 的形式，构造迭代公式如下：

          $\textbfsymbol{x}^{(k+1)} = \textbfsymbol{D}^{-1}(\textbfsymbol{L}+\textbfsymbol{U})\textbfsymbol{x}^{(k)} + \textbfsymbol{D}^{-1}\textbfsymbol{b},(k=0,1,2,\cdots.)$   (6.38)

这就是Jacobi迭代的矩阵形式，迭代矩阵为

        $\textbfsymbol{B}_J=\textbfsymbol{D}^{-1}(\textbfsymbol{L}+\textbfsymbol{U})=\textbfsymbol{D}^{-1}(\textbfsymbol{D}-\textbfsymbol{A})=\textbfsymbol{I}-\textbfsymbol{D}^{-1}\textbfsymbol{A}.$

注: (1)设近似值 $x^\ast = \pm \, 0.a_1a_2\cdots a_n\times 10^m$ 有 $n$ 的近似值有 $n$ 位效数字, 则其相对误差限为 $\cfrac{1}{2{}a_1}\times 10^{-n+1}$.

由

          $\textbfsymbol{D} \textbfsymbol{x}^{(k+1)} = (\textbfsymbol{L}+\textbfsymbol{U})\textbfsymbol{x}^{(k)} + \textbfsymbol{b},(k=0,1,2,\cdots.)$  (6.39)

可得

$x_i^{(k+1)} = \frac{1}{a_{i{}i}}\left(b_i-\sum\limits_{\substack{j=0\\j\ne i}}^n a_{i{}j}{}x_j^{(k)} \right),(i=1,2,\cdots,n.,k = 1,2,\cdots.) (6.40)$

其中 $\boldsymbol{x}^{(0)} = (x_1^{(0)},x_2^{(0)},\cdots,x_n^{(n)})$ 给定. 它相当于从第 $i$ 个方程解出 $x_i$, 再构造迭代格式.

J-迭代公式(6.38) 或 (6.40) 即为

    $\textbfsymbol{x}^{(k+1)} = \textbfsymbol{B}_J\textbfsymbol{x}^{(k)} + \textbfsymbol{f}$ (6.41)

其中

$\textbfsymbol{B}_J=\textbfsymbol{I}-\textbfsymbol{D}^{-1}\textbfsymbol{A}=\begin{bmatrix} 0 &-\frac{a_{12}}{a_{11}} &-\frac{a_{13}}{a_{11}} & \cdots &-\frac{a_{1n}}{a_{11}}\\ -\frac{a_{21}}{a_{22}}&0 &-\frac{a_{23}}{a_{22}}& \cdots &-\frac{a_{2n}}{a_{22}}\\ \vdots & \vdots & \vdots& &\vdots\\ -\frac{a_{n1}}{a_{nn}} &-\frac{a_{n2}}{a_{nn}}&-\frac{a_{n3}}{a_{nn}}&\cdots &0\\ \end{bmatrix}, \textbfsymbol{f}=\textbfsymbol{D}^{-1}\textbfsymbol{b}=\begin{bmatrix} -\frac{b_1}{a_{11}}\\ -\frac{b_{2}}{a_{22}}\\ \vdots\\ -\frac{b_{n}}{a_{nn}}\\ \end{bmatrix}.$

例 写出下面方程组的 J 迭代格式:

      $\begin{cases} 8x_1 - 3x_2 + 2x_3 = 20\\ 4x_1 + 11x_2 - x_3 = 33\\ 6x_1 + 3x_2 + 12 x_3 = 36\\ \end{cases}$

解: 分别从第 $i$ 个方程解出 $x_i$ (i = 1,2,3.), 得

        $\begin{cases} x_1 = \frac{1}{8}(20 + 3x_2 - 2x_3)\\ x_2 = \frac{1}{11}(33-4x_1 + x_3)\\ x_3 = \frac{1}{12}(36-6x_1 - 3x_2)\\ \end{cases}$

从而 $J$ 迭代格式

        $\begin{cases} x_1^{(k+1)} = \frac{1}{8}(20 + 3x_2^{(k)} - 2x_3^{(k)})\\ x_2^{(k+1)} = \frac{1}{11}(33-4x_1^{(k)} + x_3)^{(k)}\\ x_3^{(k+1)} = \frac{1}{12}(36-6x_1^{(k)} - 3x_2^{(k)})\\ \end{cases} ,(k=0,1,2,\cdots.) (6.42)$

使用MATLAB编写Jacobi迭代法的程序，看一下迭代的数值结果。

function [x, k] = LinJacobi(A,b,ep,it_max)

%  求线性方程组的Jacobi迭代法，调用格式为

%  [x, k] = LinJacobi(A,b,ep,it_max)

%  其中

%  A 为线性方程组的系数矩阵，b 为常数项，ep 为精度要求，默认为1e-5,

%  it_max 为最大迭代次数，默认为100

%  x 为线性方程组的解，k迭代次数

if nargin <4 it_max = 100; end;

if nargin <3 eps = 1e-5; end;

D = diag(A); L = - tril(A, -1);  U = - triu(A, 1);

if min(abs(D))<1e-10

   error('% 对角元素为0，计算失败！');

end

n = length(b); xk = zeros(n,1);  k=1;

B = D(L+U); f = Db;

while k<it_max

   xk1 = B*xk + f;

   if max(abs(xk1-xk))<ep    break;  end

   xk = xk1; k = k+1;

end

在命令窗口中输入

A = [8 -3 2;4 11 -1;6 3 12]; b = [20;33;36];

[x, k] = LinJacobi(A,b)

x =

3.0000

2.0000

1.0000

k =

14