数值分析学习笔记--解线性方程组的迭代方法

不同p-范数下的单位球面

如有疏漏，敬请指正。

迭代法求解线性方程组$Ax=b$和不动点迭代求解非线性方程组很类似，拆分$A=N-P$，设$N$可逆，则有

$$X=N^{-1}PX+N^{-1}b$$

令$M=N^{-1}P,g=N^{-1}b,X=MX+g$，构造迭代关系式

$$X^{(k)}=MX^{(k-1)}+g$$

称$M$为迭代矩阵。

若迭代序列$\lbrace X^{(k)} \rbrace$收敛，设$\lbrace X^{(k-1)} \rbrace$的极限是$X^{\ast}$，可得

$$X^{\ast}=MX^{\ast}+g$$

$X^{\ast}$是方程组$Ax=b$的解，此时称迭代法收敛，否则称迭代法发散。

计算中，给定控制精度$\epsilon$，当$||Ax-b||< \epsilon$或者$||X^{(k)}-X^{(k-1)}||< \epsilon$时，停止迭代计算，取$X^{\ast}=X^{(k)}$。

由线性代数知识可知，$\lim_{k \to \infty}M^k = O$的充要条件是谱半径$\rho(M)<1$。如果$||M||_p$是矩阵$M$的范数，则总有$||M||_p \geq \rho(M)$。因此若$||M||_{p} < 1$，那么$M$必收敛，这是其充分条件。

可以看出，线性方程组的迭代收敛与否完全取决于迭代矩阵的性质，与迭代初始值的选取无关。

雅可比迭代法

对于n元线性方程组$Ax=b$

$$\begin{cases} a_{11}x_1+a_{12}x_2+ \cdots +a_{1n}x_n=b_1 \\ a_{21}x_1+a_{22}x_2+ \cdots +a_{2n}x_n=b_2 \\ \vdots \\ a_{n1}x_1+a_{n2}x_2+ \cdots +a_{nn}x_n=b_n \\ \end{cases}$$

设$\lbrace a_{ii} \neq 0,i=1,2, \cdots ,n \rbrace$，将上式中每个方程组$a_{ii}x_i$留在方程的左边，其余各项移到方程的右边，方程两边除以$a_{ii}$，构造迭代格式

$$\begin{cases} x_1^{(k+1)}=\frac{1}{a_{11}}(b_1-a_{12}x_2^{(k)}- \cdots -a_{1n}x_n^{(k)})\\ x_2^{(k+1)}=\frac{1}{a_{22}}(b_2-a_{21}x_1^{(k)}- \cdots -a_{2n}x_n^{(k)})\\ \vdots \\ x_n^{(k+1)}=\frac{1}{a_{nn}}(b_n-a_{n1}x_1^{(k)}- a_{n2}x_2^{(k)}- \cdots -a_{n,n-1}x_{n-1}^{(k)})\\ \end{cases}$$

以上迭代计算式称为简单迭代或雅可比迭代，初始向量可以任取。

雅可比迭代矩阵

令

$$D=diag \lbrace a_{11},a_{22} , \cdots ,a_{nn} \rbrace,AX=(D+A-D)X=b$$

得到等价方程组

$$DX=(D-A)X+b$$

设$D$可逆，有

$$X^{(k+1)}=D^{-1}(D-A)X^{(k)}+D^{-1}b$$

令

$$R=I-D^{-1}A,g=D^{-1}b$$

则有

$$X^{(k+1)}=RX^{(k)}+g$$

称$R$为雅可比迭代矩阵。

雅可比迭代的收敛条件

当迭代矩阵$R$的谱半径$\rho (R)=\max_{1 \leq i \leq n} \mid \lambda_i \mid < 1$时，迭代收敛，这是其充要条件。

迭代矩阵的某范数$|| R || < 1$时，迭代收敛，这是其充分条件。

设$M=(m_{ij})$是n阶复方阵，若对任意$i$都有$|m_{ii}| \geq \sum_{j \neq i}|m_{ij}|$，则$M$为行对角优，若有$|m_{ii}| > \sum_{j \neq i}|m_{ij}|$，则$M$为严格行对角优。同样的，若对任意$j$都有$|m_{jj}| \geq \sum_{i \neq j}|m_{ij}|$，则$M$为列对角优，若有$|m_{jj}| > \sum_{i \neq j}|m_{ij}|$，则$M$为严格列对角优。

对于雅可比迭代的收敛性，有以下理论结果

• 若$M$为严格对角优，则$M$可逆
• 当$A$为严格对角优时，雅可比迭代收敛

Gauss-Seidel迭代

在雅可比迭代中，已经在计算$x_i^{(k+1)}$前得到了$x_1^{(k+1)}, \cdots , x_{i-1}^{(k+1)}$的值，因此，不妨将已经算出的分量直接代入迭代式中，及时使用最新计算出的分量值，这被称为Gauss-Seidel迭代。

即使用$\lbrace x_1^{(k)},x_2^{(k)}, \cdots ,x_n^{(k)} \rbrace$计算$x_1^{(k+1)}$的值，用$\lbrace x_1^{(k+1)},x_2^{(k)}, \cdots ,x_n^{(k)} \rbrace$计算$x_2^{(k+1)}$的值，一直进行下去，直到计算出$x_n^{(k+1)}$。

构造迭代格式如下：

$$\begin{cases} x_1^{(k+1)}=\frac{1}{a_{11}}(b_1-a_{12}x_2^{(k)}- \cdots -a_{1n}x_n^{(k)})\\ x_2^{(k+1)}=\frac{1}{a_{22}}(b_2-a_{21}x_1^{(k+1)}- \cdots -a_{2n}x_n^{(k)})\\ \vdots \\ x_n^{(k+1)}=\frac{1}{a_{nn}}(b_n-a_{n1}x_1^{(k+1)}- a_{n2}x_2^{(k+1)}- \cdots -a_{n,n-1}x_{n-1}^{(k+1)})\\ \end{cases}$$

Gauss-Seidel迭代矩阵

设$A=D+L+U$，有

$$A= \begin{bmatrix} a_{11} & & & \\ & a_{22} & & \\ & & & \ddots & \\ & & & & a_{nn} \\ \end{bmatrix} +\begin{bmatrix} 0 & & & \\ a_{21} & 0 & & \\ \vdots & \vdots & \ddots & \\ a_{n1} & \cdots & a_{n,n-1} & 0 \\ \end{bmatrix} +\begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ & 0 & \cdots & a_{2n} \\ & & \ddots & \vdots \\ & & & 0\\ \end{bmatrix}$$

构造迭代格式

$$(D+L)X^{(k+1)}=-UX^{(k)}+b$$

有

$$X^{(k+1)}=-(D+L)^{-1}UX^{(k)}+(D+L)^{-1}b$$

令
$S=-(D+L)^{-1}U,f=(D+L)^{-1}b$
那么有

$$X^{(k+1)}=SX^{(k)}+f$$

称$S$为Gauss-Seidel迭代矩阵。

Gauss-Seidel迭代的收敛条件

关于Gauss-Seidel迭代的收敛条件，有如下结论：

• 当$A$严格对角优时，Gauss-Seidel迭代收敛
• 当$A$正定时，Gauss-Seidel迭代收敛

松弛迭代

设$A=D+L+U$，用矩阵表示Gauss-Seidel迭代形式为

$$X^{(k+1)}=-D^{-1}LX^{(k+1)}-D^{-1}UX^{(k)}+D^{-1}b$$

令

$$\tilde{L}=-D^{-1}L,\tilde{U}=-D^{-1}U,g=D^{-1}b$$

那么Gauss-Seidel迭代的计算公式为

$$X^{(k+1)}=\tilde{L}X^{(k+1)}+\tilde{U}X^{(k)}+g$$

对$X^{(k)}$和Gauss-Seidel迭代计算的$X^{(k+1)}$加权平均，得到的迭代格式为松弛迭代，$\omega$为松弛因子。

$$X^{(k+1)}=(1- \omega)X^{(k)}+\omega(\tilde{L}X^{(k+1)}+\tilde{U}X^{(k)}+g)$$

松弛迭代的迭代格式如下：

$$\begin{cases} x_1^{(k+1)}=(1-\omega)x_1^{(k)}+\omega(r_{12}x_2^{(k)}+r_{13}x_3^{(k)}+ \cdots +r_{1n}x_n^{(k)}+g_1)\\ x_2^{(k+1)}=(1-\omega)x_2^{(k)}+\omega(r_{21}x_1^{(k+1)}+r_{23}x_3^{(k)}+ \cdots +r_{2n}x_n^{(k)}+g_2) \\ \vdots \\ x_{n}^{(k+1)}=(1-\omega)x_n^{(k)}+\omega(r_{n1}x_1^{(k+1)}+r_{n2}x_2^{(k+1)}+ \cdots +r_{n,n-1}x_{n-1}^{(k+1)}+g_n) \\ \end{cases}$$

其中，$r_{ij}=-\frac{a_{ij}}{a_{ii}},g_i=\frac{b_i}{a_{ii}},r_{ii}=0$

松弛迭代矩阵

令

$$S_{\omega}=(I+\omega D^{-1}L)^{-1}[(1-\omega)I-\omega D^{-1}U]$$ $$f=\omega(I+\omega D^{-1}L)^{-1}D^{-1}b$$

则松弛因子为$\omega$的迭代矩阵为

$$X^{(k+1)}=S_{\omega}X^{(k)}+f$$