数值分析读书笔记（3）求解线性代数方程组的迭代法

考虑方程组Ax=b，其中A属于nn维的矩阵空间，b和x属于n维向量空间，一般来说我们需要从这个隐式的方程组转变成显示的等价方程，一般具有形式 ,这样的方程为不动点方程，我们可以通过不断迭代，计算出等式右端然后赋值给变量x

对于Ax=b而言，如果我们简单取A=I-B，可以得到等价的x=Bx+b,从而构造迭代格式

需要注意的是，迭代法不一定会是收敛的，也就是说x不一定会收敛到某个值，这样并不是我们所希望的，故后面会讨论一下迭代法的收敛性，我们先来谈谈迭代法的构造，从迭代格式中可以看到，我们对矩阵A进行了一次分裂，分裂的格式显然不是唯一的，我们将采取A=M-N这样一种分裂方法，可以得到线性的不动点方程

不同的分裂法将使我们的B和f不一致，我们通常将A分裂成三个部分A=D-L-U，其中D为对角矩阵，L和U分别是下三角和上三角矩阵，这里需要注意一下符号的不同，L和U的元素都是原矩阵上三角和下三角元素符号的相反数

下面通过这样的一种分裂方式，我们介绍几种迭代形式，首先是 Jacobi迭代法（同步迭代）

注意到线性迭代中的M和N，在Jacobi迭代中，我们令M=D, N=L+U，构造出迭代格式，即

那么这样看就可以理解Jacobi迭代为什么是同步迭代了，因为所有的维度的x必须全部更新完成之后才可以进行下一步的迭代，由此我们介绍下一种迭代， Gauss-Seidel迭代（异步迭代）

在Gauss-Seidel迭代中，我们和上面对A进行同样的分裂方式，只不过在M，N的选取上做出了改变，我们令M=D-L，N=U，构造出迭代格式，即

在实际中，我们使用Jacobi迭代或者是Gauss-Seidel迭代都可能会出现不收敛或者收敛速度比较慢这样的情况，我们是不是可以试着去构造一种带参数的迭代方法，这样我们就能够利用参数的调整来实现对整个迭代方法调整已增加其收敛速度等，下面介绍 SOR(Successive over relaxation method)迭代

SOR迭代的基本思想是，在以求出第k个x值的基础上用Gauss-Seidel解出第k+1个x值，然后利用这k+1个x的值和第k个x的值的线性组合来的出更好的近似解

同样的我们利用和Jacobi，Gauss-Seidel迭代方法一样的分裂方法，对A进行分裂，注意到一种矩阵的记法

注意到等式右端的第一部分，即 ,这一部分其实就是之前的上一步的值

等式的第二部分就是类似Gauss-Seidel迭代得到的解然后乘上一个松弛因子（ ）

通过对上式进行化简，我们可以简单的得到

对于 这个矩阵我们知道，当 取任意值的时候，总为非奇异矩阵，也就是所总存在逆矩阵，所以上式可以继续化简（证明过程只需将矩阵的形式画出来，由于对角线元素不等于0，即可得证）

得到

所以我们可以根据上式建立起来SOR的迭代格式

其中，

我们利用上面的知识可以构造迭代格式来进行迭代，但是这里就出现一个问题，所有的迭代方法都是可行的吗？这里指的可行可能是收不收敛，收敛的快慢等等，所以我们有必要对其进行规范化，系统化的分析

先来看看一般的迭代格式

我们可以从n=0一直写到n=k+1，这样来看就有

我们必须研究矩阵 是否会变的越来越大，或者趋近于一个常数矩阵 ,以及 是否去趋近于

这里引入误差向量

只要误差向量趋近于0即可收敛，这里做个简单的计算

下面给出 收敛定理

这里直接给出这个收敛定理，并没有给出证明，具体的证明思路为利用Jordan标准型以及极限关系可以证明，后续等待补充

继续不加证明地给出一个定理

一般来说我们通过上述几个定理就可以通过计算矩阵的谱半径，也就是先计算最大的特征值，然后判断其是否大于1来判别一个基本迭代格式是否是收敛的，但是对于维度等级十分高的矩阵，我们可能得寻求一种较为简单的判别方法，下面我们不加证明地给出利用范数来判别的一个定理

对于迭代格式的收敛性我们已经讨论过了，下面给出误差的估计，主要是用来计算相应到达误差范围相应迭代次数的值，下面给出一个定理

该定理证明可以利用之前所介绍的 Banach引理 来证明

用上面的式子，可以求解出来精度 的迭代步数，令步数为k，B的范数为q，则有

首先我们来看看 对角占优矩阵 进行基本迭代法的收敛性

对角占优矩阵可以简单的划分成 严格对角占优 和 弱对角占优

我们直接不加证明的给出一个定理：

接下来，我们看一下另外一种特殊矩阵，即 对称正定矩阵

给出一个定理

同样的，我们对于Gauss-Seidel迭代也给出一个定理

对SOR的迭代格式，比较复杂，对于某些特定的矩阵有着一定规律，给出一个定理

由上述定理可以推出，方程组使用SOR方法收敛的一个必要条件

反过来，也有一个定理

A对称，存在正交阵Q，使得Q^TAQ=D是对角阵，不妨设D的第一个对角元是模最大的特征值。对任意的单位向量x，存在单位向量y，使得x=Qy，于是||Ax||^2=||QDQ^Tx||^2=||QDy||^2=||Dy||^2=d1^2y1^2+d2^2y2^2++dn^2y^n<=d1^2(y1^2++yn^2)=d1^2，因此||Ax||<=|d1|。同时，存在单位向量x，使得Ax=d1x，因此||Ax||=|d1|，于是由定义||A||=max(||x||=1)||Ax||=|d1|=A的谱半径。

证明：
记λ为矩阵A的模最大特征值（谱半径），x为其对应的右特征向量，那么：
x'A' × Ax = |λ|² × x'x => |λ| = ||Ax||₂/ ||x||₂<= ||A||₂即矩阵的模最大特征值（谱半径）小于等于矩阵的2范数，再由矩阵范数的等价性命题知，矩阵谱半径不是矩阵范数，证毕！

---