Chapt-6.解线性代数方程组的迭代法
解线性代数方程组的直接方法需要对系数矩阵分解，不能保持$A$的稀疏性，处理大型稀疏矩阵计算量大；迭代法充分利用了矩阵的稀疏性，有效控制计算量
简单迭代法（Jacobi迭代）
-
通过移项，将方程组 $AX=b$变成下面的等价方程组
\[\left\{ \begin{aligned} &x_1=\qquad b_{12}x_2 + b_{13}x_3 + \cdots \qquad b_{1n}x_n + g_1 \\ &x_1=b_{21}x_1 \qquad +b_{23}x_3 + \cdots \qquad b_{2n}x_n + g_n \\ &\vdots \\ &x_1=b_{n1}x_1 + b_{n2}x_2 + b_{n3}x_3 \cdots \qquad \qquad + g_n \\ \end{aligned} \right. \\ 其中 \\ \left\{ \begin{aligned} &b_{ij}=-\frac{a_ij}{a_ii} \quad(i\ne j) \\ &b_{ii}=0 \\ &g_i=\frac{b_i}{a_{ii}} \end{aligned} \right.\] -
矩阵形式表示为
\[B=\begin{bmatrix} 0 & b_{12} & \cdots & b_{1n} \\ b_{21} & 0 & \cdots & b_{2n} \\ \vdots & \vdots & & \vdots \\ b_{n1} & b_{n2} & \cdots & 0 \\ \end{bmatrix} , D=\begin{bmatrix} a_{11} & & & \\ & a_{22} & & \\ & & \ddots & \\ & & & a_{nn} \\ \end{bmatrix} , g=\begin{bmatrix} g_1\\ g_2\\ \vdots\\ g_n \end{bmatrix} \\ \because B=D^{-1}(D-A)=I-D^{-1}A \\ g=D^{-1}b \\ \therefore X=BX+g\] -
雅可比迭代公式
\[X^{(k+1)}=BX^k+g\] -
收敛条件：$\vert X-Y\vert <\varepsilon$
Seidel迭代法
Seidel迭代法是对Jacobi迭代法的加速，在迭代计算$x_i^{(k)}$时，使用之前计算好的序列${x_0^{(k)},\cdots,x_{i-1}^{(k)}}$
-
将迭代矩阵$B=(b_{ij})_{n\times n}$分解为$B=L+U$，其中
\[L=\begin{bmatrix} 0 & & & \\ b_{21} & 0 & & \\ \vdots & \vdots & \ddots & \\ b_{n1} & b_{n2} & \cdots & 0 \\ \end{bmatrix} , U=\begin{bmatrix} 0 & b_{12} & \cdots & b_{1n} \\ & 0 & \cdots & b_{2n} \\ & & \ddots & \vdots \\ & & & 0 \\ \end{bmatrix}\] -
Seidel迭代公式
\[X^{(k+1)}=LX^{(k+1)}+UX^{(k)}+g\]
松弛法（SOR迭代）
松弛法迭代是对Seidel迭代法的加速，Seidel迭代法是松弛法的特例，使用之前计算好的$x_i^{(k)}$
-
松弛法迭代公式
\(X^{(k+1)}=(1-\omega)X^{(k)}+\omega(LX^{(k+1)}+UX^{(k)}+g)\) $\omega$是松弛因子，大于1称为超松弛，小于1称为低松弛
迭代法收敛性理论
-
一般迭代法收敛定理：对于任何初始向量$X^{(0)}$和常数项$f$，迭代公式$X^{(k+1)}=MX^{(k)}+f$，向量序列收敛的充分必要条件是迭代矩阵$M$的谱半径$\rho(M)<1$
-
使用到的定理：$\lim\limits_{k\rightarrow \infty}M^k=0\Longleftrightarrow \rho(M)<1$
-
必要性证明：
\[序列收敛到X^*，则有X^*=MX^*+f \\ \varepsilon_k=X^{(k)}-X^*=M(X^{(k-1)}-X^*)=\cdots=M^k\varepsilon_0 \\ \because序列收敛\\ \therefore \lim\limits_{k\rightarrow\infty}\varepsilon_k =0 =\lim\limits_{k\rightarrow\infty}M^k\varepsilon_0 \\ \therefore \lim\limits_{k\rightarrow \infty}M^k=0，推出\rho(M)<1\] -
充分性证明：
若 $\rho(M)<1$，则1不是 $M$的特征值且 $I-M$非奇异，方程组 $(I-M)X=f$有唯一解，记作 $X^*$，递推式 $\varepsilon_k=M^k\varepsilon_0$仍然成立
\[\because \rho(M)<1 \therefore \lim\limits_{k\rightarrow \infty}M^k=0 \\ \therefore \lim\limits_{k\rightarrow\infty}\varepsilon_k =\lim\limits_{k\rightarrow\infty}M^k\varepsilon_0 =0\\ 即\lim X^{(k)}\rightarrow \lim X^*\]
-
-
定理：若迭代矩阵$M$的范数$\vert M\vert =q<1$，则迭代公式$X^{(k+1)}=MX^{(k)}+f$对任何初始向量$X^{(0)}$一定收敛，且
\[\vert X^{(k)}-X^*\vert \le\frac{q}{1-q}\vert X^{(k)}-X^{(k-1)}\vert \le\frac{q^k}{1-q}\vert X^{(1)}-X^{(0)}\vert\]-
证明第一个推论：
\[\because \rho(M)\le\vert M\vert 且\vert M\vert <1 \therefore \rho(M)<1\\\]由上一个定理推出该迭代公式对任何初始向量收敛
-
证明第二个推论：
$$ \vert X^{(k)}-X^\vert =\vert X^{(k)}-X^{(k+1)}+X^{(k+1)}-X^\vert
\le\vert M\vert \cdot\vert X^{(k-1)}-X^{(k)}+X^{(k)}-X^\vert
由三角不等式进一步推导
\le p\vert X^{(k)}-X^{(k-1)}\vert +p\vert X^{(k)}-X^\vert
移项后得到
\vert X^{(k)}-X^*\vert \le\frac{q}{1-q}\vert X^{(k)}-X^{(k-1)}\vert$$ 递推继续证明
\[\because \vert X^{(k)}-X^{(k-1)}\vert =\vert MX^{(k-1)}+f-MX^{(k-2)}-f\vert \\ \le \vert M\vert \cdot\vert X^{(k-1)}-X^{(k-2)}\vert \\ \therefore \frac{q}{1-q}\vert X^{(k)}-X^{(k-1)}\vert \le\frac{q^k}{1-q}\vert X^{(1)}-X^{(0)}\vert\]
-
迭代矩阵谱半径和系数矩阵A的关系
-
Jacobi迭代收敛的充要条件是下列行列式的所有根的绝对值小于1
\[\begin{vmatrix} \lambda a_{11} & a_{12} & \cdots & a_{1n} \\ a_{12} & \lambda a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & \lambda a_{nn} \\ \end{vmatrix}=0\]推导：对迭代矩阵$B$收敛的充要条件是$\rho(B)<1$，所以需要先求解$B$的特征值
\[\because BX=\lambda X \therefore (\lambda I-B)X=0 \\ 即求解行列式\vert \lambda I-B\vert =0 \\ \because B=D^{-1}(D-A) \\ \vert \lambda I-D^{-1}(D-A)\vert =0 \\ \vert D^{-1}\vert \cdot\vert \lambda D-(D-A)\vert =0 \quad 又 \because \vert D^{-1}\vert \ne0 \\ \therefore \vert \lambda D+(A-D)\vert =0\] -
Sidel迭代的充要条件是下列行列式的所有根的绝对值小于1
\[\begin{vmatrix} \lambda a_{11} & a_{12} & \cdots & a_{1n} \\ \lambda a_{12} & \lambda a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \lambda a_{n1} & \lambda a_{n2} & \cdots & \lambda a_{nn} \\ \end{vmatrix}=0\]推导：
\[(\lambda I-B)X=0\\ \because B=(I-L)^{-1}U\\ \therefore \vert \lambda I-(I-L)^{-1}U\vert =0 \\ \vert \lambda (I-L)^{-1}(I-L)-(I-L)^{-1}U\vert =0 \\ \vert \lambda (I-L)-U\vert =0 \\ \vert \lambda D - \lambda DL -DU\vert =0\] -
松弛迭代的充要条件是下列行列式的所有根的绝对值小于1
\[\begin{vmatrix} (\lambda+\omega-1) a_{11} & a_{12} & \cdots & a_{1n} \\ \omega\lambda a_{12} & (\lambda+\omega-1) a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \omega\lambda a_{n1} & \omega\lambda a_{n2} & \cdots & (\lambda+\omega-1) a_{nn} \\ \end{vmatrix}=0\] -
方阵不可约定义：矩阵$A$不能通过行交换和相应的列交换变成$\begin{bmatrix}A_{11} & A_{12} \ 0 & A_{22} \end{bmatrix}$，其中$A_{11},A_{22}$为方阵
-
矩阵$A$强对角占优定义：$A=(a_{ij}){n\times n}$，满足$\vert a{ii}\vert \ge\sum\limits_{j\ne i}\vert a_{ij}\vert $，且至少有一个$i$值使得前面的不等式严格成立，则称$A$具有对角优势（弱对角占优）；如果所有$i$对不等式严格成立，则称$A$强对角占优
- 定理：$A$强对角占优，或者$A$弱对角占优但不可约，则$\det A\ne 0$
- 定理：$A$不可约的充要条件是$A$的邻接图是一个强连通图
-
定理：若$A$是强对角占优，或者$A$弱对角占优且不可约，则
- Jacobi迭代、Seidel迭代一定收敛
- 若松弛因子$\omega$满足$0< \omega\le 1$，则松弛迭代一定收敛
定理分析：
反证法，不收敛则存在特征值大于1，推出$\det$强对角占优，由定理的$\det$不为零，矛盾
-
Jacobi如果不收敛，则存在$\vert \lambda_0\vert \ge 1$，且满足 \(\begin{vmatrix} \lambda_0 a_{11} & a_{12} & \cdots & a_{1n} \\ \lambda_0 a_{12} & \lambda_0 a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \lambda_0 a_{n1} & \lambda_0 a_{n2} & \cdots & \lambda_0 a_{nn} \\ \end{vmatrix}=0\) 因为$\vert \lambda_0\vert a_{ii}\vert \ge \vert a_{ii}\vert \ge \sum\limits_{j\ne i}\vert a_{ij}\vert $，即上面的行列式强对角占优，行列式不为零（前面的定理），矛盾；Seidel类似
-
松弛法类似，因为$\lambda_0\ge 1且0\le \omega\le 1$，推出$\lambda_0+\omega-1\ge \omega且\lambda_0(1-\omega)\ge (1-\omega)$，推出$\lambda+\omega-1\ge\omega\lambda$
-
定理：松弛法收敛的必要条件是$0<\omega< 2$
定理：若矩阵$A$对称正定，且有$0<\omega<2$，则松弛法收敛
定理：设分块对角阵$A$且$a_{ii}\ne 0$，Jacobi迭代的迭代矩阵$B$的特征值为实值且$0<\rho(B)<1$，则：当$0<\omega<2$时，松弛法收敛，最优松弛因子$\omega_{opt}=\frac{2}{1+\sqrt{1-\rho^2(B)}}$
例题
-
设$B\in R^{n\times n},\rho(B)>1$，但$B$有一个特征值满足$\vert \lambda\vert <1$，证明存在初始向量$x^{(0)}$，使得简单迭代式收敛 \(\varepsilon^{(k)}=\vert x^{(k)}-x^*\vert =\vert Bx^{(k-1)}-Bx^*\vert \\ =\vert B(x^{(k-1)}-x^*)\vert = \vert B^k(x^{(0)}-x^*)\vert \\ 只需要证明存在\vert \lambda\vert <1时，存在\vert B\vert <1 \\ \because By=\lambda y \therefore B^ky=\lambda^ky \\ \lim\limits_{k\rightarrow\infty}\vert B^ky\vert = \lim\limits_{k\rightarrow\infty}\vert \lambda^ky\vert =0 \\ \therefore 存在x^{(0)}=y+x^*使得迭代式关于它收敛 \\ 初始向量和特征向量y有关\)
-
设$A\in R^{(n\times n)}$对称正定，其最小和最大特征值分别是$\lambda_1,\lambda_2$，证明迭代法$X^{(k+1)}=X^{(k)}+\alpha(b-AX^{(k)})$收敛的充要条件是$0<\alpha<\frac{2}{\lambda_n}$，并求使得迭代举证谱半径最小的参数取值 \(X^{(k+1)}=(I-\alpha A)X^{(k)}+\alpha b \\ \rho(I-\alpha A)<1 \\\)