相关链接：《线性方程组的类型及求解》（目录），《线性方程组的类型及求解》（一），《线性方程组的类型及求解》（二），《线性方程组的类型及求解》（三），《线性方程组的类型及求解》（四）
2. 理解：(1) 找初始点也是比较讲究的，先大概判断要用不动点迭代解的这个方程的零点区间（当然越是越小越好），然后就可以从这个区间里取初始点了，比如区间两端或中点，参见【2】P44的习题7；(2) 如果能够大致判断方程组的根在哪些点附近时，就能够更好地判断构造出来的迭代格式的收敛性了，参见【2】P44的习题8，判断收敛性时，我们不仅要关注是否收敛（用
![]() 时除了
![]() ，不要忘了还有
![]() 哟），还应该关注其收敛速度；(3) 迭代法不仅可以直接用于求解方程，还可以将一些含变量的表达式，比如
![]() 等，构造方程组进而求其迭代公式，从而解出变量不同取值下的值，参见【2】P44的习题6和9；(4) 可以用极限的证明，即有界单调，从理论上求出不动点，参见【2】P43的习题4，理论上求解时还应注意使用配方等变形技巧，参见【2】P44的习题10。
2.2 Jacobi迭代法
2.2.1 迭代格式
代数格式：
![]()
矩阵格式：
![]()
![]()
1. 注意：要区分开系数矩阵和迭代矩阵：
![]() 为系数矩阵，
![]() 为迭代矩阵。而整个后面的式子
![]() 记作
![]() ，称为迭代格式。
2.2.2 收敛性
(1) 充分必要条件1：
![]() 。（【2】P82证明）
(2) 充分必要条件:2：谱半径
![]() （充要条件）。（【2】P83证明）
(3) 充分条件1：
![]() 。（因为
![]() ，范数比谱半径好算）
(4) 充分条件2：若
![]() 是严格对角占优矩阵，则迭代收敛。（【2】P86证明，注意这里是系数矩阵啦~）
1. 注意：(1) 要会判断何时该用充要条件或充分条件，如果是让求使得迭代格式收敛的参数范围时，就必须得用充要条件了，因为充分条件只能根据已知参数去推出是否收敛（【2】P102页的习题4）；(2) 在科学工程计算中，实际求解的线性方程组的系数矩阵往往都具有某种特殊性质，我们可以从系数矩阵本身得出收敛条件，而不必求迭代矩阵及其特征值或范数。换言之，先用充分条件判断，如果满足充分条件则直接秒解，如果不满足，因为是充分条件，所以还不能否认，因此继续用其他充分条件，充分条件用完了后再祭出王牌充要条件去判断。
2.2.3 终止准则
若
![]() ，则对于迭代格式
![]() 有：
![]() 其中
![]() 为方程组
![]() 的精确解。（【2】P85证明，类比2.1迭代思想中的不动点迭代）
2.3 Gauss-Seidel迭代法
2.3.1 迭代格式
代数格式：
![]()
矩阵格式：
![]()
1. 注意：Jacobi迭代法更加简单实用，Gauss-Seidel迭代法常用于收敛速度分析。如果系数矩阵稀疏度为k，迭代法每次迭代花费O(kn)阶运算。
2. 编程：Jacobi迭代法和Gauss-Seidel迭代法的算法形式可参见【2】P81页，便于编程实现。
2.3.2 收敛性
(1)~(4) 同2.2.2
(5) 充分条件3：若
![]() 是对称正定矩阵，则迭代收敛。（【2】P87证明）
2.3.3 终止准则
同2.2.3
2.4 SOR迭代法
全名为“逐次超松驰迭代法(Successive Over Relaxation) ”，它是对Gauss-Seidel迭代法的推广和加速。
2.4.1 迭代格式
令
![]()
利用松弛技术
![]()
得到
![]()
1. 关于
![]() ：松弛因子为1时迭代法是GS迭代法；松弛因子大于1时, 称为逐次超松弛方法；松弛因子小于1时, 称为逐次欠松弛方法。 （【2】P102的习题7）
2.4.2 收敛性
(1) 充要条件：
![]() ，
![]() 为迭代矩阵。
(2) 必要条件：
![]() 。（【2】P90证明）
(3) 若
![]() 为严格对角占优矩阵，则当
![]() 时，SOR迭代收敛。
(4) 若
![]() 是对称正定矩阵，则当
![]() 时，SOR迭代收敛。（【2】P90证明）
（【2】P102的习题 6,7,8）
三. M-P广义逆求相容方程的最小范数解
有的相容方程往往其解不唯一，而在一些实际问题中，需要在多个解中寻求满足某种条件的解。
(1) 范数解的通解为
![]()
(2) 最小范数解为
![]() （【1】P233的习题20）
1. 基本概念：
![]() （不要求满秩），
![]() ,有：(a)
![]() ; (b)
![]() ; (c)
![]() ; (d)
![]() 。满足(a)则称
![]() 为广义逆矩阵
![]() ，
![]() 不唯一；同时满足(a)和(b)则称
![]() 为自反广义逆矩阵
![]() ，
![]() 不唯一；同时满足4个条件则称
![]() 为M-P广义逆矩阵
![]() ，
![]() 唯一。
2. 计算
![]() 的方法主要有以下两个：
(a) 最大值秩分解求
![]() ：如果
![]() 的最大秩分解为
![]() ，那么
![]() ，其中
![]() 。此外特别注意的是，若
![]() 是行满秩矩阵，则
![]() ，若
![]() 是列满秩矩阵，则
![]() ，所以先判断类型。（【1】P207的例1）
(b) 奇异值分解求
![]() ：
![]() ，其中
![]() ，
![]() 是
![]() 的
![]() 个非零特征值，
![]() ，
![]() 是
![]() 对应于
![]() 的单位正交的特征向量组。（【1】P209证明）（【1】P210的例2）
现在开始讨论不相容线性方程组的解法。 在许多实际问题中，如数据处理、与正态分布有关的统计问题等涉及的线性方程组往往是不相容的。
四. 最小二乘解法
4.1 模型
可以将原不相容方程组
![]() 转换为正规方程组
![]() 来求解。
1. 思想：首先构造原不相容方程组的最小二乘解
![]() ，从而将原问题转换为求残差二范数最小的优化问题（注意此处用
![]() 是因为即便在
![]() 后带上常数，但关心的最小值点不变，如果使用
![]() 则会改变最小值）； 再令
![]() （这是技巧，对于矩阵，要构造“平方”则用转置来乘），展开得
![]() （注意化简过程中，
![]() ，因为等式两边结果都是一个数）； 接着对上式求梯度
![]() （技巧：类比代数
![]() ，对于矩阵情形
![]() ）。 最后得到原不相容（超定）方程的正规方程形式：
![]() 。 该模型的价值在于可以直接根据具体问题写出最终的求解形式。
2. 注意：值得注意的是，这实质是一个优化问题，因此最小二乘解并不是不相容方程组的解。
4.2 定理
(1) 不相容方程的最小二乘解总是存在的。（PPT14的P18证明）
4.3 应用场景
在统计学中，根据实验样本进行数据拟合时往往会求解超定方程。在许多实际问题中，由于变量和变量之间的关系比较复杂，需要考虑问题背景所涉及的数学模型，观察数据散点的分布，选取不同函数做实验，以获得比较成功的数据拟合。下面介绍几种拟合函数：
(1)
![]()
(2)
![]()
(3)
![]()
(4)
![]() （线性化处理后为
![]() ）（PPT14例题1）
(5)
![]() （PPT14例题2）
1. 理解：这里做的目的就是要构造出原不相容方程，因为实际中我们得到的都是些离散的统计数据点，然后用来预测之类的。说到预测，那肯定要有个函数咯，所以要先根据经验把拟合函数设定出来，然后就可以代入已经得到的这些系数点得到方程组，一般情况下方程组的个数会很多的，即不相容方程组，因此就要用最小二乘法来解。此时实际上我们要求的是系数矩阵，而不是变量了，但方法都一样的，变变形即可。（【2】P159的习题2和3）
五. M-P广义逆求不相容方程的最佳逼近解
一般来说，不相容方程的最小二乘解是不唯一的。对于不相容方程组
![]() ：
(1) 最小二乘解的通解为
![]() （【1】P225证明）
(2) 最佳最小二乘解（最佳逼近解）为
![]() （【1】P226的例1）
1. 拓展：设矩阵方程
![]() ，其中
![]() ，则
![]() 是该矩阵方程的最佳逼近解。
2. 注意：其实和M-P广义逆求相容方程组的最小范数解是一个思想和解法，只不过所得解的叫法不同罢了。
|