目录
第6章 线性方程组的迭代解法
graph LR A[迭代法] --> B[定常迭代法] A --> C[不定常迭代法] B-->D[雅可比Jacobi迭代法] B-->E[高斯赛德尔Gauss-Seidel迭代法] B-->F[超松弛SOR迭代法] C-->G[共轭梯度法] C-->H[广义极小残量法]1. 范数和条件数
线性方程组的解是一个向量 , 称为解向量. 近似解向量与精确解向量之差成为近似解的误差向量. 范数:衡量向量和矩阵大小的度量概念
1.1 向量和矩阵的范数
矩阵的 F 范数是向量 2 范数的直接推广 , 矩阵的 2 范数的计算是 \(A^T A\) 的谱半径的开方 , 所以又称为谱范数
对于矩阵A和向量x,如果满足:
\[\|Ax\|\leqslant\|A\|\cdot\|x\| \]则称向量范数和矩阵范数相容.常用的范数相容关系有:
\[\begin{gathered} \|Ax\|_{1}\leqslant \|A\|_1\cdot\|x\|_1, \\ \|Ax\|_{\infty}\leqslant \|A\|_\infty\cdot\|x\|_\infty, \\ \|Ax\|_{2}\leqslant \|A\|_{2}\cdot\|x\|_{2}, \\ \|Ax\|_{2}\leqslant \|A\|_{F}\cdot\|x\|_{2}. \end{gathered}\]1.2 条件数和扰动分析
对于线性方程组:
\[Ax=b \]解向量x由A,x决定.当A,b受到微小扰动时,对解x的扰动不一定也是微小的.无论方程组中的系数矩阵 A 有扰动 , 还是右端 b 有扰动 , 解 x 的相对误差除了受相应扰动的相对误差以外 , 还与 \(||A||*||A^{-1}||\) 的大小有关
对于一个确定的线性方程组 , 若系数矩阵A的条件数相对地小 , 就称方程组是良态的 ,矩阵为良态矩阵 ; 反之 , 条件数相对地大 , 就称方程组病态 , 矩阵为病态矩阵.
使用稳定方法求病态方程组的解,结果可能很差.
2. 基本迭代法
2.1 迭代法基本思路
对于线性方程组:
\[Ax=b \]其中,$A\in\mathbb{R}^{n\times n} \(,\)\boldsymbol{b}\in\mathbb{R}^n$ 已知,求解\(x\in\mathbb{R}^n\)
假定A以下分解,M为非奇异方阵:
\[A=M-N \]则有以下关系:
\[Mx=Nx+b 或者 x=Bx+g \]其中,\(B=M^{-1}N ， g=M^{-1}b.\) 从而可以建立迭代公式:
\[x^{(k+1)}=Bx^{(k)}+g\tag{1} \]给定初始向量 \(x^{(0)}\) ,进行迭代,就可以得向量序列 \({x^{(k)}}\) .若该序列收敛于一个确定的值 \(x^*\).则\(x^{*}=Bx^{*}+g\),也就是\(Ax^*=b\),\(x^*\)就是线性方程组的解.
初值\(x^{(0)}\)可以任意取,但一般取\(x^{(0)}=0\)或\(x^{(0)}=b\).
判断是否收敛的标准:
计算出\(x^{k+1}\)后,计算\(error=\frac{||b-A*x^{k+1}||}{||b||}\) ,若\(error\)小于某个给定的阈值,则认为迭代收敛.
以上就是解线性方程组的基本迭代解法
在公式(1)中,为了避免B,g中的求逆计算 , 我们可以按如下方式进行迭代:
\[Mx^{(k+1)}=Nx^{(k)}+b.\tag{2} \]只是,这就每次迭代就需要求解一个系数矩阵为 M 的线性方程组\(Mx^{(k+1)}=b'\).如果M矩阵具有特殊性质(对角阵,上三角阵等),这样的方程组易于求解.如:
\[A=D-L-U \]分别是对角矩阵、严格下三角矩阵和严格上三角矩阵:
\[\begin{gathered} D=\mathrm{diag}(a_{11},a_{22},\cdots,a_{nn}), \\ \boldsymbol{L}=-\begin{pmatrix}0&0&\cdots&0\\a_{21}&0&\cdots&0\\\vdots&\ddots&\ddots&\vdots\\a_{n1}&a_{n2}&\cdots&0\end{pmatrix}, \\ \boldsymbol{U}=-\left(\begin{matrix}{0}&{{a_{12}}}&{\cdots}&{{a_{1n}}}\\{\vdots}&{\ddots}&{\ddots}&{\vdots}\\{0}&{\ddots}&{\ddots}&{{a_{n-1,n}}}\\{0}&{0}&{\cdots}&{0}\\\end{matrix}\right), \end{gathered}\]下面介绍三种基本迭代解法：雅可比迭代法、高斯–赛德尔迭代法和SOR迭代法, 并对它们的适用性、收敛性质和收敛速度
2.2 雅可比迭代法
在公式(2)中,取\(M=D\),\(N=L+U\),就可以得到雅可比迭代法的迭代公式:
\[D\boldsymbol{x}^{(k+1)}=(\boldsymbol{L}+\boldsymbol{U})\boldsymbol{x}^{(k)}+\boldsymbol{b}.\tag{3} \]
2.3 高斯–赛德尔迭代法
高斯-赛德尔迭代法(简称GS迭代法)的迭代格式为:
\[Dx^{(k+1)}=Lx^{(k+1)}+Ux^{(k)}+b.\\(D-L)x^{(k+1)}=Ux^{(k)}+b. \]
2.4 超松弛 (SOR) 迭代法
GS 迭代格式可以改写成:
\[\begin{aligned}x^{(k+1)}&=D^{-1}(Lx^{(k+1)}+Ux^{(k)}+b)\\&=\boldsymbol{x}^{(k)}+\boldsymbol{D}^{-1}(\boldsymbol{L}\boldsymbol{x}^{(k+1)}+\boldsymbol{U}\boldsymbol{x}^{(k)}-\boldsymbol{D}\boldsymbol{x}^{(k)}+\boldsymbol{b}).\end{aligned} \]为了加快迭代的收敛速度 , 将上式等号右端的第二项\(D^{-1}(Lx^{(k+1)}+Ux^{(k)}-Dx^{(k)}+b).\)看成是修正量,引入超松弛因子\(omega\) , 并将修正量乘上\(omega\) , 得到修正后的迭代格式:
\[x^{(k+1)}=\boldsymbol{x}^{(k)}+\omega\boldsymbol{D}^{-1}(\boldsymbol{L}\boldsymbol{x}^{(k+1)}+\boldsymbol{U}\boldsymbol{x}^{(k)}-\boldsymbol{D}\boldsymbol{x}^{(k)}+\boldsymbol{b}),\\x^{(k+1)}=(\boldsymbol{D}-\omega\boldsymbol{L})^{-1}[(1-\omega)\boldsymbol{D}+\omega\boldsymbol{U}]\boldsymbol{x}^{(k)}+\omega(\boldsymbol{D}-\omega\boldsymbol{L})^{-1}\boldsymbol{b}. \]这就是逐次超松弛迭代法 , 简称SOR迭代法.
