6.6.0 总论
在用直接法解线性方程组时要对系数矩阵不断变换，如果方程组的阶数很高,则运算量将会很大
因此，寻求更经济、适用的数值解法
- 标准形式：
- 变形为的标准迭代方程：
- 然后建立一个初始向量x⁽⁰⁾求下个方程值，由公式：
- 构造向量序列{x⁽ᵏ⁾}，如果向量序列{x⁽ᵏ⁾}满足：
则称此迭代收敛。
- 第k次迭代误差：
用迭代解方程组的关键1：就是如何构造迭代格式
由此，不同的大佬提出了不同的方法：
- 雅可比(Jacobi)迭代法
- 高斯-赛德尔(Gauss-Seidel)迭代法
- 逐次松弛迭代法
用迭代解方程组的关键2：由此迭代产生的向量序列{x⁽ᵏ⁾}的收敛性件什么？
6.6.1 雅可比迭代法的基本思想
方法步骤
对于线性方程组 AX = b，其中：
将每个方程改写为：
迭代公式
取定初始向量：
第k+1次迭代的计算公式为：
收敛条件
同样，和解非线性方程组的一半迭代法一样，这种迭代的方法收敛是有条件的；在向量中，这要求向量中每一个元素的迭代都逼近其真值点
- 系数矩阵A必须对角占优
对角占优是指矩阵中每个对角线元素的绝对值大于该行其他所有元素绝对值之和。具体来说：
对于n阶矩阵A=(aij)，如果满足：
则称矩阵A是对角占优的。
- 迭代矩阵的谱半径小于1谱半径
算法特点
- 优点：算法简单，易于理解和实现
- 缺点：收敛速度可能较慢
- 适用于大型稀疏矩阵方程组
在实际应用中，需要设定合适的迭代初值和收敛判断准则，以保证计算的准确性和效率。
精度要求（迭代停止条件）
对于迭代精度要求，可以用无穷范数表示为：
其中ε为给定的精度要求。当相邻两次迭代结果的误差小于ε时，认为迭代符合精度要求
结合范数的含义，上式等价于：在向量的任何一个维度上的误差都小于 ，才认为迭代符合精度要求
矩阵形式
雅可比迭代法可以用矩阵形式表示。将系数矩阵A分解为：
其中：
- D为A的对角矩阵
- L为A的严格下三角矩阵（对角线以下的元素）
- U为A的严格上三角矩阵（对角线以上的元素）
则迭代公式可以写为：
迭代矩阵为：
收敛的充分条件是迭代矩阵的谱半径小于1：
例. 用Jacobi迭代法求解方程组：
解：按迭代公式，得雅可比迭代格式：
取，令
迭代计算结果：
- ，
- ，
6.6.2 高斯-赛德尔迭代法
高斯-赛德尔迭代法是对雅可比迭代法的一种改进。其主要思想是在计算第i个分量时，立即使用已经计算出的新值，而不是像雅可比迭代法那样等到下一次迭代才使用。
也因此，雅可比迭代法称为整体代换法、同时代换法、简单代换法……
理念：迭代时要用最新的数据，最全的数据
迭代公式
对于同样的线性方程组，高斯-赛德尔迭代法的计算公式为：
其实就是算出来的数据立即用进去（），下标比i小的，上标也是k+1
与雅可比迭代法的区别
- 计算新的分量时，立即使用已经计算出的新值（x⁽ᵏ⁺¹⁾）
- 通常收敛速度比雅可比迭代法更快
- 占用存储空间更少，因为可以直接在原向量上更新
收敛条件
高斯-赛德尔迭代法的收敛条件与雅可比迭代法类似：
- 系数矩阵A为对角占优矩阵
- 迭代矩阵谱半径小于1
高斯-赛德尔迭代法的矩阵形式
同样将系数矩阵A分解为：
其中D、L、U的含义与雅可比迭代法相同。
首先给出递推方程：
通过移项和重组，得到标准迭代格式：
记：
最终得到高斯-赛德尔迭代的标准形式：
迭代矩阵为：
收敛的充分条件是迭代矩阵的谱半径小于1：
与雅可比迭代法相比，高斯-赛德尔迭代法的迭代矩阵形式反映了它在计算过程中立即使用新值的特点，这体现在(D + L)项的处理上。
6.6.3 逐次超松弛迭代法（SOR法）
逐次超松弛迭代法（SOR法）是在高斯-赛德尔迭代法的基础上引入松弛因子ω的改进方法。其基本思想是通过选择适当的松弛因子来加快收敛速度。
迭代公式
SOR法的迭代公式为：
公式可以记忆为：
原高斯赛德尔表达式×ω+高斯-赛德尔上一轮求得的结果×（1-ω）
其中：
- ω为松弛因子，0 < ω < 2
- 当ω = 1时，SOR法就是高斯-赛德尔迭代法
- 当0 < ω < 1时，称为低松弛迭代法
- 当1 < ω < 2时，称为超松弛迭代法
矩阵形式
SOR法的矩阵形式为：
迭代矩阵为：
特点与应用
- 通过选择适当的松弛因子ω可以加快收敛速度
- 最优松弛因子的选择依赖于具体问题
- 当系数矩阵为对称正定时，收敛的必要条件是0 < ω < 2
6.6.4 迭代法的收敛性
谱半径
谱半径是一个矩阵所有特征值的绝对值的最大值。对于矩阵A，其谱半径ρ(A)定义为：
其中λᵢ是矩阵A的特征值。
在迭代法中，谱半径是判断迭代收敛性的重要指标。当迭代矩阵的谱半径小于1时，迭代序列必定收敛。
定理 迭代法基本定理
对于一个线性迭代格式：
其中B为迭代矩阵，对于任意初值X⁽⁰⁾，迭代序列{X⁽ᵏ⁾}收敛的充要条件是：
即迭代矩阵B的谱半径小于1。这是判断迭代法收敛性的基本准则。
- 当ρ(B) < 1时，对任意初值X⁽⁰⁾，迭代序列必定收敛到方程组的唯一解
- 当ρ(B) ≥ 1时，存在某些初值X⁽⁰⁾，使得迭代序列发散
三种迭代法的收敛条件比较
设A = D + L + U，其中D为对角矩阵，L为下三角矩阵，U为上三角矩阵。三种迭代法的收敛充要条件如下：
1. 雅可比迭代法
迭代矩阵：
- 收敛充要条件：
2. 高斯赛德尔迭代法
迭代矩阵：
- 收敛充要条件：
3. SOR迭代法
迭代矩阵：
- 收敛充要条件：
对于这三种方法，当它们都收敛时，通常有：
- SOR法（最优ω） > 高斯赛德尔法 > 雅可比迭代法（收敛速度的比较）
严格对角占优矩阵的收敛性定理
严格对角占优条件下，雅可比、高斯赛德尔均收敛
对于矩阵A=(aᵢⱼ)，如果满足：
则称A为严格对角占优矩阵。对于严格对角占优矩阵，有以下重要定理：
雅可比迭代法收敛定理
如果A是严格对角占优矩阵，则雅可比迭代法必定收敛。此时：
高斯赛德尔迭代法收敛定理
如果A是严格对角占优矩阵，则高斯赛德尔迭代法必定收敛。更进一步的，有：
严格对角占优的条件下，高斯赛德尔迭代法的收敛速度不慢于雅可比迭代法。
SOR法的收敛
对于SOR迭代法的收敛性，与松弛因子ω的选择密切相关：
- 当0 < ω < 2时，若A为对称正定矩阵，SOR法收敛
- 当ω = 1时，SOR法退化为高斯赛德尔迭代法
- 当ω > 2时，SOR法一定发散
- 反之，若SOR法收敛，则必有0 < ω < 2
正定矩阵
结论：如果满足以下条件：
1. A为对称正定矩阵
2. 松弛因子ω ∈ (0,2)
则SOR迭代法必定收敛。
最优松弛因子
- 对于最优松弛因子ωopt：
- ωopt的值通常在1到2之间
- 当ω = ωopt时，SOR法具有最快的收敛速度
- 最优松弛因子的确定往往需要通过实践或理论分析来获得
这表明当选择最优松弛因子时，SOR法的收敛速度优于高斯赛德尔法和雅可比迭代法。
总结：迭代法收敛性判据
1. 一般性判据
- 迭代矩阵B的谱半径 是迭代收敛的充要条件
2. 各种迭代法的具体判据
- 雅可比迭代法：
- 要求，其中
- 高斯赛德尔迭代法：
- 要求，其中
- SOR迭代法：
- 要求，其中
- 松弛因子必须在范围内
3. 特殊条件下的收敛性
- 严格对角占优矩阵：
- 雅可比迭代法必定收敛
- 高斯赛德尔迭代法必定收敛，且收敛速度不慢于雅可比法
- 对称正定矩阵：
- 当时，SOR法必定收敛
4. 收敛速度比较
- 当收敛时，速度关系为： SOR法(最优) > 高斯赛德尔法 > 雅可比迭代法
此处的收敛均指全局收敛，也就是对任意初始向量迭代法均收敛
