11线性方程组的迭代法-雅可比、高斯塞德尔和超松弛迭代PPT课件.ppt

§6.1迭代法的基本思想
迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值，按某种计算规则，不断地
对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。
设非奇异，，则线性方程组
有惟一解，经过变换构造出一个等价同解方程组
将上式改写成迭代式如果
存在极限
则称迭代法是收敛的，否则就是发散的。
收敛时，在迭代公式

中当时，,则
,故是方程组的解。
对于给定的方程组可以构造各种迭代公式。
并非全部收敛例1用迭代法求解线性方程组§6.2雅可比与高斯-塞德尔迭代法
§6.2.1雅可比迭代法算法取初始向量
进行迭代,可以逐步得出一个近似解的序列：
（k=1,2,…）
直到求得的近似解能达到预先要求的精度，
则迭代过程终止，以最后得到的近似解作为线
性方程组的解。
当迭代到第10次有

计算结果表明，此迭代过程收敛于方程组的精
确解x*=(3,2,1)T。考察一般的方程组，将n元线性方程组§6.2.2雅可比迭代法的矩阵表示
设方程组的系数矩阵A非奇异，且主对
角元素，则可将A分裂成则等价于雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即6.2.1雅可比迭代法的算法实现§6.2.2高斯-塞德尔（Gauss-Seidel）迭代法
高斯-塞德尔迭代法的基本思想
在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求时用新分量
代替旧分量,就得到高斯-赛德尔迭代法。其迭代法格式为：例3用GaussSeidel迭代格式解方程组Gauss—Seidel迭代法的矩阵表示
将A分裂成A=D-L-U，则等价于
(D-L-U)x=b
于是,则高斯—塞德尔迭代过程定义：设

如果A的元素满足

称A为严格对角占优阵。

2.如果A的元素满足

且至少一个不等式严格成立，称A为弱对角占优阵。
定义：设

如果存在置换矩阵P，使得

其中，A11为r阶方阵，A22为n-r阶方阵（），
则称A为可约矩阵，否则称A为不可约矩阵。

定理9：设如果
1）A为严格对角占优阵，则雅可比和高斯-塞德尔迭代法均收敛；
2）A为弱对角占优阵，且A为不可约矩阵，则雅可比和高斯-塞德尔迭代法均收敛。§6.3超松弛迭代法（SOR方法）
使用迭代法的困难在于难以估计其计算
量。有时迭代过程虽然收敛，但由于收敛速
度缓慢，使计算量变得很大而失去使用价值
。因此，迭代过程的加速具有重要意义。逐
次超松弛迭代（SuccessiveOverrelaxaticMethod，简称SOR方法）法，可以看作是带参数的高斯—塞德尔迭代法，实质上是高斯-塞德尔迭代的一种加速方法。§6.3.1超松弛迭代法的基本思想
超松弛迭代法目的是为了提高迭代法的收敛速度，在高斯—塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果与高斯-塞德尔迭代方法的迭代值适当加权平均，期望获得更好的近似值。是解大型稀疏矩阵方程组的有效方法之一，有着广泛的应用。
其具体计算公式如下：⑵把取为与的加权平均，即§6.3.2超松弛迭代法的矩阵表示
设线性方程组Ax=b的系数矩阵A非奇异,且主对角元素,则将A分裂成A=d-L-U,则超松弛迭代公式用矩阵表示为
令例4用SOR法求解线性方程组§6.3.2迭代法的收敛性
我们知道,对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。
对于方程组
经过等价变换构造出的等价方程组基本定理5迭代公式收敛
的充分必要条件是迭代矩阵G的谱半径
证:必要性设迭代公式收敛,当k→∞时,
则在迭代公式两端同时取极限得
记,则收敛于0(零向量),且有充分性:设,则必存在正数ε,使
则存在某种范数,使,
,则,所以
,即。故收敛于0,
收敛于
由此定理可知，不论是雅可比迭代法、高斯—
塞德尔迭代法还是超松弛迭代法，它们收敛的
充要条件是其迭代矩阵的谱半径。定理6(迭代法收敛的充分条件)
若迭代矩阵G的一种范数,则迭代公式

收敛,且有误差估计式又因为,则det(I-G)≠0,I-G为非奇异矩阵,
故x＝Gx＋d有惟一解,即
与迭代过程相比较,有

两边取范数由迭代格式，有例5已知线性方程组⑵将系数矩阵分解而则37定理12对于线性方程组Ax=b，若A为对称正定矩阵，则当0<ω<2时，SOR迭代收敛.
定理13对于线性代数方程组Ax=b，若A按行(或列)严格对角占优，或按行(或列)弱对角占优不可约；则当0<w≤1时，SOR迭代收敛。40例6设,证明,求解方程组例6设,证明,求解方程组迭代法不存在误差累积问题。使用迭代法的
关键问题是其收敛性与收敛速度，收敛性与迭代
初值的选取无关，这是