资源描述
,我们知道，凡是迭代法都有一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设计简单，适于自动计算，而且较直接法更少的计算量就可获得满意的解。因此，迭代法亦是求解线性方程组，尤其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。,第六章 解线性方程组的迭代法,1,6.1 迭代法的基本思想 迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值 ，按某种计算规则，不断地 对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。,2,设 非奇异， ，则线性方程组 有惟一解 ，经过变换构造出一个等价同解方程组 将上式改写成迭代式,选定初始向量 ,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法,3,如果 存在极限 则称迭代法是收敛的，否则就是发散的。 收敛时，在迭代公式 中当 时， , 则 , 故 是方程组 的解。 对于给定的方程组可以构造各种迭代公式。 并非全部收敛,4,例1 用迭代法求解线性方程组,解 构造方程组的等价方程组,据此建立迭代公式,取 计算得,迭代解离精确解 越来越远 迭代不收敛,5,6.2 雅可比与高斯-塞德尔迭代法 6.2.1 雅可比迭代法算法,例2 用雅可比迭代法求解方程组,解：从方程组的三个方程中分离出 和,建立迭代公式,6,取初始向量 进行迭代, 可以逐步得出一个近似解的序列： （k=1, 2, ） 直到求得的近似解能达到预先要求的精度， 则迭代过程终止，以最后得到的近似解作为线 性方程组的解。 当迭代到第10次有 计算结果表明，此迭代过程收敛于方程组的精 确解x*= (3, 2, 1)T。,7,考察一般的方程组，将n元线性方程组,写成,若 ,分离出变量,据此建立迭代公式,上式称为解方程组的Jacobi迭代公式。,8,6.2.2 雅可比迭代法的矩阵表示 设方程组 的系数矩阵A非奇异，且主对 角元素 ，则可将A分裂成,记作 A = D - L - U,9,则 等价于,即,因为 ，则,这样便得到一个迭代公式,令,则有,（k = 0,1,2）,称为雅可比迭代公式, B称为雅可比迭代矩阵,10,雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即,(k=0,1,2,),11,6.2.1 雅可比迭代法的算法实现,12, 6.2.2 高斯-塞德尔（Gauss-Seidel）迭代法 高斯-塞德尔迭代法的基本思想 在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求 时用新分量 代替旧分量 , 就得到高斯-赛德尔迭代法。其迭代法格式为：,(i=1,2,n k=0,1,2,),13,例3 用GaussSeidel 迭代格式解方程组,精确要求为=0.005,解 GaussSeidel 迭代格式为,取初始迭代向量 ,迭代结果为：,x* ,14,GaussSeidel 迭代法的矩阵表示 将A分裂成A =D-L-U，则 等价于 (D-L-U )x = b 于是,则高斯塞德尔迭代过程,因为 ,所以,则高斯-塞德尔迭代形式为：,故,令,15,定义：设 如果A的元素满足 称A为严格对角占优阵。 2.如果A的元素满足 且至少一个不等式严格成立，称A为弱对角占优阵。, 6.2.3 雅可比和高斯-塞德尔迭代收敛性,16,定义：设 如果存在置换矩阵P，使得 其中，A11为r阶方阵，A22为n-r阶方阵（ ）， 则称A为可约矩阵，否则称A为不可约矩阵。,17,定理9：设 如果 1）A为严格对角占优阵，则雅可比和高斯-塞德尔迭代法均收敛； 2）A为弱对角占优阵，且A为不可约矩阵，则雅可比和高斯-塞德尔迭代法均收敛。,定理10：设矩阵A对称，且,1）雅可比迭代法收敛的充要条件：A和2D-A均为正定矩阵，其中D=diag（A）； 2）高斯-塞德尔迭代法收敛的充分条件：A正定。,18, 6.3 超松弛迭代法（SOR方法） 使用迭代法的困难在于难以估计其计算 量。有时迭代过程虽然收敛，但由于收敛速 度缓慢，使计算量变得很大而失去使用价值 。因此，迭代过程的加速具有重要意义。逐 次超松弛迭代（Successive Over relaxatic Method，简称SOR方法）法，可以看作是带参数的高斯塞德尔迭代法，实质上是高斯-塞德尔迭代的一种加速方法。,19, 6.3.1超松弛迭代法的基本思想 超松弛迭代法目的是为了提高迭代法的收敛速度，在高斯塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果 与高斯-塞德尔迭代方法的迭代值 适当加权平均，期望获得更好的近似值 。是解大型稀疏矩阵方程组的有效方法之一，有着广泛的应用。 其具体计算公式如下：, 用高斯塞德尔迭代法定义辅助量。,20, 把 取为 与 的加权平均，即,合并表示为：,式中系数称为松弛因子，当=1时，便为高斯-塞德尔迭代法。为了保证迭代过程收敛，要求0 2。 当0 1时，低松弛法；当1 2时称为超松弛法。但通常统称为超松弛法(SOR)。,21, 6.3.2 超松弛迭代法的矩阵表示 设线性方程组 Ax=b 的系数矩阵A非奇异,且主对角元素 , 则将A分裂成A=d-L-U, 则超松弛迭代公式用矩阵表示为,或,故,显然对任何一个值,(D+L)非奇异, (因为假设 )于是超松弛迭代公式为,22,令,则超松弛迭代 公式可写成,23,例4 用SOR法求解线性方程组,取=1.46，要求,解：SOR迭代公式,k = 0,1,2,，,初值,该方程组的精确解 只需迭代20次便可达到精度要求,如果取=1(即高斯塞德尔迭代法)和同一初 值 ,要达到同样精度, 需要迭代110次,24, 6.3.2 迭代法的收敛性 我们知道, 对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。 对于方程组 经过等价变换构造出的等价方程组,在什么条件下迭代序列 收敛？,25,基本定理5 迭代公式 收敛 的充分必要条件是迭代矩阵G的谱半径 证:必要性 设迭代公式收敛,当k时, 则在迭代公式两端同时取极限得 记 ,则 收敛于0(零向量),且有,于是,由于 可以是任意向量,故 收敛于0当且仅 当 收敛于零矩阵，即当 时,于是,所以必有,26,充分性: 设 , 则必存在正数, 使 则存在某种范数 , 使 , ,则 , 所以 , 即 。故 收敛于 0, 收敛于 由此定理可知，不论是雅可比迭代法、高斯 塞德尔迭代法还是超松弛迭代法，它们收敛的 充要条件是其迭代矩阵的谱半径 。,事实上, 在例1中, 迭代矩阵G= ， 其特征多项式为 ,特征值为 -2，-3， , 所以迭代发散,27,定理6 (迭代法收敛的充分条件) 若迭代矩阵G的一种范数 ,则迭代公式 收敛,且有误差估计式,及,证: 矩阵的谱半径不超过矩阵的任一种范数,已知 ,因此 ,根据定理4.9可知迭代公式收敛,28,又因为 , 则det (I-G )0, I-G为非奇异矩阵, 故xGxd有惟一解 , 即 与迭代过程 相比较, 有 两边取范数,29,由迭代格式，有,两边取范数，代入上式，得,证毕,由定理知，当 时，其值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代 （为给定的精度要求）作为 控制迭代结束的条件,30,例5 已知线性方程组,考察用Jacobi迭代和G-S迭代求解时的收敛性 解: 雅可比迭代矩阵,故Jacobi迭代收敛,31, 将系数矩阵分解,则高斯-塞德尔迭代矩阵,故高斯塞德尔迭代收敛。,32,例：给出方程组 其中,问:分别利用Jacobi迭代法和Gauss-Seidel 迭代法是否收敛.,解：,对,33,而,即,所以，对,Jacobi方法收敛，G-S方法发散,同理，对于,其中,34,即得,而,35,则,36,37,定理12 对于线性方程组Ax=b，若A为对称正定矩阵，则当02时，SOR迭代收敛.,证明 只需证明1（其中为L的任一特征值）.,38,定理13 对于线性代数方程组Ax=b， 若A按行(或列)严格对角占优，或按行(或列)弱对角占优不可约；则当0w1时，SOR迭代收敛。,39,40,例6 设 ,证明, 求解方程组,的Jacobi迭代与G-S迭代同时收敛或发散,证:雅可比迭代矩阵,其谱半径,41,例6设 ,证明, 求解方程组,的Jacobi迭代与G-S迭代同时收敛或发散,证: G-S迭代矩阵,其谱半径,显然, 和 同时小于、等于或大于1,因而Jacobi迭代法与G-S迭代法具有相同的收敛性,42,例 7 考察用雅可比迭代法和高斯-塞德尔迭代 法解线性方程组Ax=b的收敛性，其中,解： 先计算迭代矩阵,43,求特征值,雅可比矩阵, ( B ) = 0 1 用雅可比迭代法求解时，迭代过程收敛,44,1=0,2 =2,3 =2 (G1)=21 用高斯-塞德尔迭代法求解时，迭代过程发散,高斯-塞德尔迭代矩阵,求特征值,45, Ax=b的系数矩阵按行严格对角占优,故高斯-塞德尔迭代收敛,例9 设有迭代格式 X(k+1)=B X(k) +g (k=0,1,2） 其中B=I-A, 如果A和B的特征值全为正数， 试证：该迭代格式收敛。 分析:根据A， B和单位矩阵I之间的特征值的关系导出()1, 从而说明迭代格式收敛。 证: 因为B=I-A, 故(B)= (I)- (A)=1 - (A) (A) + (B) = 1 由于已知(A) 和 (B)全为正数，故 0(B)1 ,从而 (B) 1 所以该迭代格式收敛。,46,当a1时,Jacobi矩阵GJ1,对初值x(0)均收敛,例10 设 方程组 写出解方程组的Jacobi迭代公式和迭代矩阵 并讨论迭代收敛的条件。 写出解方程组的Gauss-Seidel迭代矩阵,并讨 论迭代收敛的条件。 解 Jacobi迭代公式和Jacobi矩阵分别为,47,例 10设 方程组 写出解方程组的Gauss-Seidel迭代矩阵，并讨论 迭代收敛的条件。 解 Gauss-Seidel矩阵为,当时a1时, Gauss-Seidel矩阵 Gs1, 所以对任意初值x(0)均收敛。,也可用矩阵的谱半径p(GS)1来讨论,48,解： 先计算迭代矩阵,例11 讨论用雅可比迭代法和高斯-塞德尔迭代 法解线性方程组Ax=b的收敛性。,49,求特征值,雅可比矩阵, ( B ) = 1 用雅可比迭代法求解时，迭代过程不收敛,1 = - 1， 2,3 = 1/2,50,求特征值,高斯-塞德尔迭代矩阵, (G1) = 0.3536 1 用高斯-塞德尔迭代法求解时，迭代过程收敛,1=0,51,求解AX=b,当取何值时迭代收敛？ 解:所给迭代公式的迭代矩阵为,例12 给定线性方程组 AX= b 用迭代公式 X(K+1)=X(K)+(b-AX(K) (k=0,1,）,52,即 2-(2-5 )+1- 5 +4 2=0 2-(2-5 )+(1- )(1-4)=0 -(1-)- (1-4)=0 1=1- 2=1-4,(B)=max|1- |, |1-4|1,取0 1/2迭代收敛,53,本章小结 本章介绍了解线性方程组 迭代法的 一些基本理论和具体方法。迭代法是一种逐次逼 近的方法，即对任意给定的初始近似解向量，按 照某种方法逐步生成近似解序列，使解序列的极 限为方程组的解。注意到在使用迭代法 解方程组时，其迭代矩阵B和迭代向量f在计算过 程中始终不变,迭代法具有循环的计算公式,方法 简单，程序实现方便，它的优点是能充分利用系 数的稀疏性,适宜解大型稀疏系数矩阵的方程组。,54,迭代法不存在误差累积问题。使用迭代法的 关键问题是其收敛性与收敛速度，收敛性与迭代 初值的选取无关，这是比一般非线性方程求根的 优越之处。在实际计算中，判断一种迭代格式收 敛性较麻烦，由于求迭代的谱半径时需要求特征 值，当矩阵的阶数较大时，特征值不易求出，通 常采用矩阵的任一种范数都小于1或对角占优来判 断收敛性。有时也可边计算边观察其收敛性。如 何加快迭代过程的收敛速度是一个很重要的问题 ，实用中更多的采用SOR法，选择适当的松驰因子 有赖于实际经验。我们应针对不同的实际问题 ，采用适当的数值算法。,55,
展开阅读全文