《第四章线性代数方程组的迭代解法》由会员分享，可在线阅读，更多相关《第四章线性代数方程组的迭代解法（46页珍藏版）》请在金锄头文库上搜索。
1、 4.1引言 在第二章中我们知道，凡是迭代法都有一个收 敛问题，有时某种方法对一类方程组迭代收敛，而 对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设计简单，适 于自动计算，而且较直接法更少的计算量就可获得 满意的解。因此，迭代法亦是求解线性方程组，尤 其是求解具有大型稀疏矩阵的线性方程组的重要方 法之一。第四章第四章 解线性方程组的迭代法解线性方程组的迭代法Date1jkhh4.2 迭代法的基本思想迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值 ，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。Date2jkhh设
2、 非奇异， ，则线性方程组 有惟一解 ，经过变换构造出一个等价同解方程组将上式改写成迭代式选定初始向量 ,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法。Date3jkhh如果 存在极限则称迭代法是收敛的，否则就是发散的。收敛时，在迭代公式中当 时， , 则, 故 是方程组 的解。对于给定的方程组可以构造各种迭代公式，但并非全部收敛 。 Date4jkhh例4.1 用迭代法求解线性方程组 解 构造方程组的等价方程组据此建立迭代公式 取 计算得 迭代解离精确解 越来越远迭代不收敛 Date5jkhh4.3 雅可比（Jacobi）迭代法 4.3.1雅可比迭代法
3、算法构造 例4.2 用雅可比迭代法求解方程组 解：从方程组的三个方程中分离出 和 建立迭代公式 Date6jkhh取初始向量进行迭代, 可以逐步得出一个近似解的序列：（k=1, 2, ）直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第10次有计算结果表明，此迭代过程收敛于方程组的精确解x*= (3, 2, 1)T。 Date7jkhh考察一般的方程组，将n元线性方程组 写成 若 ,分离出变量 据此建立迭代公式 上式称为解方程组的Jacobi迭代公式。 Date8jkhh4.3.2 雅可比迭代法的矩阵表示 设方程组 的系数矩阵A非奇异，且主对
4、角元素 ，则可将A分裂成 记作 A = L + D + U Date9jkhh则 等价于即 因为 ，则这样便得到一个迭代公式令则有（k = 0,1,2）称为雅可比迭代公式, B称为雅可比迭代矩阵。Date10jkhh其中 在例4.2中,由迭代公式写出雅可比迭代矩阵为 Date11jkhh雅可比迭代矩阵表示法，主要是用来讨论其收敛 性，实际计算中，要用雅可比迭代法公式的分量 形式。即 (k=0,1,2,) Date12jkhh4.3.3 雅可比迭代法的算法实现 Date13jkhh4.4 高斯-塞德尔（Gauss-Seidel）迭代法4.4.1 高斯-塞德尔迭代法的基本思想在Jacobi迭代法中
5、，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求 时用新分量 代替旧分量 , 就得到高斯-赛德尔迭代法。其迭代法格式为： (i=1,2,n k=0,1,2,)Date14jkhh例4.3 用GaussSeidel 迭代格式解方程组 精确要求为=0.005 解 GaussSeidel 迭代格式为取初始迭代向量 ,迭代结果为：x* Date15jkhh4.4.2 GaussSeidel 迭代法的矩阵表示将A分裂成A =L+D+U，则 等价于 ( L+D+U )x = b 于是,则高斯塞德尔迭代过程 因为 ,所以 则高斯-塞德尔迭代形式为： 故 令 Date16jkhh4.
6、5 迭代法的收敛性我们知道, 对于给定的方程组可以构造成 简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式，但并非一定 收敛。现在分析它们的收敛性。对于方程组 经过等价变换构造出的等价方程组 在什么条件下迭代序列 收敛？先引入如下定理 Date17jkhh由此定理可知，不论是雅可比迭代法、还是高斯塞德尔迭代法，它们收敛的充要条件是其迭代矩阵 的谱半径 。 事实上, 在例4.1中, 迭代矩阵B= ，其特征多项式为,特征值为 -2，-3， , 所以迭代发散 。定理4.1 迭代公式 收敛 的充分必要条件是迭代矩阵B的谱半径Date18jkhh定理4.2 (迭代法收敛的充分条件) 若
7、迭代矩阵B的一种范数 ,则迭代公式收敛。由定理知，当 时，其值越小，迭代 收敛越快，在程序设计中通常用相邻两次迭代（为给定的精度要求）作为控制 迭代结束的条件。 Date19jkhh三种常用的向量范数：例 ：设 x=(1 , -4, 0, 2)T 求它的向量范数Date20jkhh三种常用的矩阵范数：例 ：设 A，求它的矩阵范数 Date21jkhh例4.5 已知线性方程组 考察用Jacobi迭代和G-S迭代求解时的收敛性。 解: 雅可比迭代矩阵 故Jacobi迭代收敛 Date22jkhh 将系数矩阵分解 则高斯-塞德尔迭代矩阵 故高斯塞德尔迭代收敛。 Date23jkhh定理4.3 设n阶
8、方阵 为对角占优阵, 则A非奇异。证: 因A为对角占优阵, 其主对角元素的绝对值大于同行其它元素绝对值之和, 且主对角元素全不为0, 故对角阵 为非奇异。作矩阵 Date24jkhh利用对角占优知 由定理4.1知 非奇异,从而A非奇异,证毕系数矩阵为对角占优阵的线性方程组称作对角占优方程组。 Date25jkhh定理4.4 对角占优线性方程组 的雅可比迭代公式和高斯-赛德尔迭代公式均收敛。证: 雅可比迭代公式的迭代矩阵为 由定理4.4知, 这时 , 再由定理4.3知迭代收敛 再考察高斯-赛德尔迭代公式的迭代矩阵 令 ，则有 即 写出分量形式有 Date26jkhh设 而 由上式得 由此整理得
9、利用对角占优条件知上式右端小于1,(如果右端大 于1, 则得出与对角占优条件矛盾的结果)故有据定理4.3知G-S收敛 Date27jkhh例4.6 设求解线性方程组 的雅可比迭代 求证当 1 用高斯-塞德尔迭代法求解时，迭代过程发散高斯-塞德尔迭代矩阵求特征值Date34jkhh Ax=b的系数矩阵按行严格对角占优,故高斯-塞德尔迭代收敛例4.10 设有迭代格式X(k+1)=B X(k) +g (k=0,1,2）其中B=I-A, 如果A和B的特征值全为正数，试证：该迭代格式收敛。 分析:根据A， B和单位矩阵I之间的特征值的 关系导出()1, 从而说明迭代格式收敛。 证: 因为B=I-A, 故
10、(B)= (I)- (A)=1 - (A)(A) + (B) = 1由于已知(A) 和 (B)全为正数，故0(B)1 ,从而 (B) 1所以该迭代格式收敛。Date35jkhh当时a1时,Jacobi矩阵GJ1,对初值x(0)均收敛例4.11 设 方程组 写出解方程组的Jacobi迭代公式和迭代矩阵并讨论迭代收敛的条件。写出解方程组的Gauss-Seidel迭代矩阵,并讨论迭代收敛的条件。解 Jacobi迭代公式和Jacobi矩阵分别为 Date36jkhh例4.11设 方程组 写出解方程组的Gauss-Seidel迭代矩阵，并讨论迭代收敛的条件。解 Gauss-Seidel矩阵为 当时a1时
11、, Gauss-Seidel矩阵 Gs1,所以对任意初值x(0)均收敛。也可用矩阵的谱半径 p(GS)1来讨论Date37jkhh解： 先计算迭代矩阵例4.12 讨论用雅可比迭代法和高斯-塞德尔迭代法解线性方程组Ax=b的收敛性。Date38jkhh求特征值雅可比矩阵 ( B ) = 1 用雅可比迭代法求解时，迭代过程不收敛1 = - 1， 2,3 = 1/2Date39jkhh求特征值高斯-塞德尔迭代矩阵 (G1) = 0.3536 1 用高斯-塞德尔迭代法求解时，迭代过程收敛1=0,Date40jkhh求解AX=b,当取何值时迭代收敛？ 解:所给迭代公式的迭代矩阵为例4.13 给定线性方程
12、组 AX= b用迭代公式X(K+1)=X(K)+(b-AX(K) (k=0,1,）Date41jkhh即 2-(2-5 )+1- 5 +4 2=02-(2-5 )+(1- )(1-4)=0 -(1-)- (1-4)=01=1- 2=1-4 (B)=max|1- |, |1-4|1取0 1/2迭代收敛Date42jkhh例4.14 设求解线性方程组Ax=b的简单迭代法x(k+1)=Bx(k)+g ( k=0,1, 2, )收敛, 求证: 对01, 迭代法x(k+1)=(1- )I+ Bx(k)+ g ( k=0,1, 2, )收敛。 证: 设C= (1- )I+ B, (C)和(B)分别为C和B
13、的特征值，则显然(C) =(1- )+ (B)因为01, (C) 是1和(B) 的加权平均, 且由迭代法x(k+1)=Bx(k)+g ( k=0,1, 2, ) 收敛知|(B)|1, 故|(C)|1, 从而(C)1, 即 x(k+1)=(1- )I+ Bx(k)+ g ( k=0,1, 2, ) 收敛k=0,1, Date43jkhh本章小结 本章介绍了解线性方程组 迭代法的 一些基本理论和具体方法。迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按 照某种方法逐步生成近似解序列，使解序列的极 限为方程组的解。注意到在使用迭代法解方程组时，其迭代矩阵B和迭代向量f在计算过 程中始终不变,迭代法具有循环的计算公式,方法 简单，程序实现方便，它的优点是能充分利用系 数的稀疏性,适宜解大型稀疏系数矩阵的方程组。 Date44jkhh迭代法不存在误差累积问题。使用迭代法的 关键问题是其收敛性与收敛速度，收敛性与迭代 初值的选取无关，这是比一般非线性方程求根的 优越之处。在实际计算中，判断一种迭代格式收 敛性较麻烦，由于求迭代的谱半径时需要求特征 值，当矩阵的阶
