数值分析第六章解线性方程组的迭代法.ppt
数值分析Numerical Analysis,第六章解线性代数方程组的迭代法,郑州大学研究生课程（2011-2012学年第一学期）,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,第六章 解线性代数方程组的迭代法,6.1 引言6.2 几种常用的迭代格式6.3 迭代法的收敛性及误差估计6.4 判别收敛的几个常用条件6.5 迭代法收敛判定的应用举例,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.1 引言,线性方程组的数值解法有：直接法和迭代法。,直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；,迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.1 引言,当A为稀疏矩阵时，直接法将破坏矩阵A的稀疏性。,系数矩阵的分类第一类：低阶稠密方程组，即系数矩阵的阶数不高，含零元素很少，在线性代数等课程学习中通常见到的，都属这类方程组；第二类：高阶稀疏方程组，系数矩阵的阶数很高，如几百阶、甚至成千上万阶，其中零元素成片分布，数量上绝对占优。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,迭代法适用于解大型稀疏方程组,(万阶以上的方程组,系数矩阵中零元素占很大比例,而非零元按某种模式分布),问题:(1)如何构造迭代格式？(2)迭代格式是否收敛？(3)如何进行误差估计？,6.1 引言,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.1 引言,迭代法的基本思想 迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,设 非奇异，则线性方程组 有惟一解，经过变换构造出一个等价同解方程组将上式改写成迭代式,选定初始向量,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,如果向量序列 存在极限则称迭代法是收敛的，否则就是发散的。收敛时，在迭代公式中当 时，,则 故 是方程组 的解。对于给定的方程组可以构造各种迭代公式。并非全部收敛。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,雅可比(Jacobi)迭代格式,例 建立迭代格式求解方程组,方程组的精确解x*=(3,2,1)T。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,建立迭代公式,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,取初始向量进行迭代,可以逐步得出一个近似解的序列：（k=1,2,）直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第10次有计算结果表明，此迭代过程收敛于方程组的精确解x*=(3,2,1)T。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,考察一般的n元线性方程组,写成,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,若,分离出变量,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式（Jacobi迭代公式）,(k=0,1,2,),ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式（Jacobi迭代公式）,据此建立迭代公式,上式称为解方程组的Jacobi迭代公式。也称为 简单迭代法。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,雅可比迭代法的矩阵表示 设方程组 的系数矩阵A非奇异，且主对角元素，则可将A分裂成,记作 A=L+D+U,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,则 等价于,因为，则,这样便得到一个迭代公式,6.2 几种常用的迭代格式（Jacobi迭代公式）,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,其中,令,则有,（k=0,1,2）,称为雅可比迭代公式,B称为雅可比迭代矩阵,6.2 几种常用的迭代格式（Jacobi迭代公式）,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,雅可比迭代法的算法实现,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式（Jacobi迭代公式）,function X=jacobi(A,B,P,delta,max)%求解AX=B，A是非奇N阶方阵dleta是误差界，max是最大迭代次数N=length(B);for t=1:max for k=1:N X(k)=(B(k)-A(k,1:k-1,k+1:N)*P(1:k-1,k+1:N)/A(k,k);end err=abs(norm(X-P);if(errdelta)break;end endX=X;,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,高斯-塞德尔（Gauss-Seidel）迭代法,在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求 时用新分量 代替旧分量,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,Gauss-Seidel迭代法,(i=1,2,n k=0,1,2,),高斯-赛德尔迭代法的迭代法格式为：,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,GaussSeidel 迭代法的矩阵表示,将A分裂成A=L+D+U，则 等价于(L+D+U)x=b 于是,则高斯塞德尔迭代过程,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,GaussSeidel 迭代法的矩阵表示,因为,所以,故,则高斯-塞德尔迭代形式为：,令,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,高斯-塞德尔迭代法,高斯塞德尔迭代算法实现 高斯-塞德尔迭代算法的计算步骤与流程图与雅可比迭代法大致相同，只是一旦求出变元的某个新值 后,就改用新值 替代老值 进行这一步剩下的计算。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,function X=gseid(A,B,P,delta,max)%求解AX=B，A是非奇N阶方阵dleta是误差界，max是最大迭代次数N=length(B);for t=1:max for k=1:N if k=1 X(1)=(B(1)-A(1,2:N)*P(2:N)/A(1,1);elseif k=N X(N)=(B(N)-A(N,1:N-1)*(X(1:N-1)/A(N,N);else X(k)=(B(k)-A(k,1:k-1)*X(1:k-1)-A(k,k+1:N)*P(k+1:N)/A(k,k);end end err=abs(norm(X-P);if(errdelta)break;end end X=X;,高斯-塞德尔迭代法,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,例,，按高斯-塞德尔迭代公式,迭代7次，得，,用高斯-塞德尔迭代法解下面线性方程组,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,由此例可知，用高斯-塞德尔迭代法，雅可比迭代法解线性方程组(且取)均收敛.,而高斯-塞德尔迭代法比雅可比迭代法收敛较快(即取 相同，达到同样精度所需迭代次数较少).,但这结论只当 满足一定条件时才是对的.,且,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,超松弛迭代法（SOR方法）,使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛，但由于收敛速度缓慢，使计算量变得很大而失去使用价值。因此，迭代过程的加速具有重要意义。逐次超松弛迭代（Successive Over relaxatic Method，简称SOR方法）法，可以看作是带参数的高斯塞德尔迭代法，实质上是高斯-塞德尔迭代的一种加速方法。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,超松弛迭代法的基本思想 超松弛迭代法目的是为了提高迭代法的收敛速度，在高斯塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果 与高斯-塞德尔迭代方法的迭代值 适当加权平均，期望获得更好的近似值。是解大型稀疏矩阵方程组的有效方法之一，有着广泛的应用。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,SOR方法,用高斯塞德尔迭代法定义辅助量。,把 取为 与 的加权平均，即,合并表示为：,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,SOR方法,式中系数称为松弛因子，为了保证迭代过程收敛，要求0 2。当=1时，便为高斯-塞德尔迭代法。当0 1时，低松弛法；当1 2时称为超松弛法。但通常统称为超松弛法(SOR)。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,故,令,则超松弛迭代公式可写成,SOR迭代法的矩阵表示,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,显然对任何一个值,(D+L)非奇异,(因为假设)于是超松弛迭代公式为,(k=0,1,2,),ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,例,它的精确解为,取，迭代公式为,用SOR方法解方程组,解,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.2 几种常用的迭代格式,取，,取其他 值，迭代次数如下表.,第11次迭代结果为,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,从此例看到，松弛因子选择得好，会使SOR迭代法的收敛大大加速.本例中 是最佳松弛因子.,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,定义,设有矩阵序列 及,如果 个数列极限存在且有,则称 收敛于，,记为,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,例,且设，考查其极限.,解,由于，当 时，有,设有矩阵序列,所以,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,定理,设,则(零矩阵)的,充分必要条件是矩阵 的谱半径,（证明参见：关治，陈景良.数值计算方法,清华大学出版社，P410412）,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,矩阵的谱半径,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,定理 对给定方阵G,若,则 为非奇异矩阵,且,证:用反证法,若 为奇异矩阵,则存在非零向 量x,使,即有 由相容性条件得,由于,两端消去,有,与已知条件矛盾,假设不成立,命题得证。又由于 有,即,将G分别取成G和-G，再取范数,又已知，有,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.3 迭代法的收敛性及误差估计,对于给定的方程组可以构造成雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。对于方程组 经过等价变换构造出的等价方程组,在什么条件下迭代序列 收敛？,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,定理 迭代公式 收敛的充分必要条件是迭代矩阵G的谱半径证:必要性 设迭代公式收敛,当k时,则在迭代公式两端同时取极限得记,则 收敛于0(零向量),且有,于是,由于 可以是任意向量,故 收敛于0当且仅当 收敛于零矩阵，即当 时,所以必,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,充分性:设,则必存在正数,使则存在某种范数,使,则,所以,即。故 收敛于 0,收敛于 由此定理可知，不论是雅可比迭代法、高斯塞德尔迭代法还是超松弛迭代法，它们收敛的充要条件是其迭代矩阵的谱半径。,6.3 迭代法的收敛性及误差估计,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,定理(迭代法收敛的充分条件)若迭代矩阵G的一种范数,则迭代公式收敛,且有误差估计式,且有误差估计式,及,6.3 迭代法的收敛性及误差估计,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.3 迭代法的收敛性及误差估计,证:矩阵的谱半径不超过矩阵的任一种范数,已知,因此,根据定理可知迭代公式收敛,又因为,则det(I-G)0,I-G为非奇异矩阵,故xGxd有惟一解,即与迭代过程 相比较,有,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,两边取范数,6.3 迭代法的收敛性及误差估计,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.3 迭代法的收敛性及误差估计,由迭代格式，有,两边取范数，代入上式，得,证毕,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.3 迭代法的收敛性及误差估计,由定理知，当 时，其值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代（为给定的精度要求）作为控制迭代结束的条件,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.4 判别收敛的几个常用条件,迭代法收敛的判别条件：1.Jacobi迭代法（简单迭代法）的收敛判定。2.Gauss-Seidel迭代法的收敛判定。3.SOR迭代法的收敛判定。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,定理 设n阶方阵 为对角占优阵,则 它是非奇异的。证:因A为对角占优阵,其主对角元素的绝对值大 于同行其它元素绝对值之和,且主对角元素 全不为0,故对角阵 为非奇异。作矩阵,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.4 判别收敛的几个常用条件,利用对角占优知,知 非奇异,从而A非奇异,证毕 系数矩阵为对角占优阵的线性方程组称作对角占优方程组。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.4 判别收敛的几个常用条件,定理 对角占优线性方程组 的雅可比 迭代公式和高斯-赛德尔迭代公式均收敛。证:雅可比迭代公式的迭代矩阵为,由定理知,这时,再由定理知迭代收敛.再考察高斯-赛德尔迭代公式的迭代矩阵,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.4 判别收敛的几个常用条件,令，则有,即,写出分量形式有,设,而,由上式得,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.4 判别收敛的几个常用条件,由此整理得,利用对角占优条件知上式右端小于1,(如果右端大于1,则得出与对角占优条件矛盾的结果)故有,据定理知G-S法收敛,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,定理 当系数矩阵 A 为正定矩阵，高斯-塞德尔迭代收敛。,定理 松弛迭代收敛的必要条件是02,6.4 判别收敛的几个常用条件,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,定理 若A为对称正定矩阵时，则松弛迭代收敛的充要条件是.,定理 6.4.5(松弛法收敛的充分条件)如果系数矩阵A为严格对角占优，当松弛因子 时，松弛迭代法收敛。,6.4 判别收敛的几个常用条件,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.5 迭代法收敛判定的应用举例,例 已知线性方程组,考察用Jacobi迭代和G-S迭代求解时的收敛性解:雅可比迭代矩阵,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.5 迭代法收敛判定的应用举例,故Jacobi迭代收敛,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.5 迭代法收敛判定的应用举例,故高斯塞德尔迭代收敛。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.5 迭代法收敛判定的应用举例,例 设有迭代格式 X(k+1)=B X(k)+g(k=0,1,2）其中B=I-A,如果A和B的特征值全为正数，试证：该迭代格式收敛。分析:根据A，B和单位矩阵I之间的特征值的关系导出(B)1,从而说明迭代格式收敛。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.5 迭代法收敛判定的应用举例,证:因为B=I-A,故(B)=(I)-(A)=1-(A)(A)+(B)=1 由于已知(A)和(B)全为正数，故 0(B)1,从而(B)1 所以该迭代格式收敛。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.5 迭代法收敛判定的应用举例,例 设 方程组 写出解方程组的Jacobi迭代公式和迭代矩阵 并讨论迭代收敛的条件。写出解方程组的Gauss-Seidel迭代矩阵,并讨 论迭代收敛的条件。解 Jacobi迭代公式和Jacobi矩阵分别为,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.5 迭代法收敛判定的应用举例,当时 时,Jacobi矩阵GJ1,对初值x(0)均收敛,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,写出解方程组的Gauss-Seidel迭代矩阵，并讨论 迭代收敛的条件。解 Gauss-Seidel矩阵为,当时 时,Gauss-Seidel矩阵 Gs1,所以对任意初值x(0)均收敛。,6.5 迭代法收敛判定的应用举例,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,解：先计算迭代矩阵,例 讨论用雅可比迭代法和高斯-塞德尔迭代 法解线性方程组Ax=b的收敛性。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,求特征值,雅可比矩阵,(B)=1 用雅可比迭代法求解时，迭代过程不收敛,1=-1，2,3=1/2,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,求特征值,高斯-塞德尔迭代矩阵,(G1)=0.3536 1 用高斯-塞德尔迭代法求解时，迭代过程收敛,1=0,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,6.5 迭代法收敛判定的应用举例,求解AX=b,当取何值时迭代收敛？解:所给迭代公式的迭代矩阵为,例 给定线性方程组 AX=b 用迭代公式 X(K+1)=X(K)+(b-AX(K)(k=0,1,）,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,即 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迭代收敛,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,内容小结,本章介绍了解线性方程组 迭代法的一些基本理论和具体方法。迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。注意到在使用迭代法解方程组时，其迭代矩阵B和迭代向量f在计算过程中始终不变,迭代法具有循环的计算公式,方法简单，程序实现方便，它的优点是能充分利用系数的稀疏性,适宜解大型稀疏系数矩阵的方程组。,ISCM 2007,Beijing China,郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis,迭代法不存在误差累积问题。使用迭代法的关键问题是其收敛性与收敛速度，收敛性与迭代初值的选取无关，这是比一般非线性方程求根的优越之处。在实际计算中，判断一种迭代格式收敛性较麻烦，由于求迭代的谱半径时需要求特征值，当矩阵的阶数较大时，特征值不易求出，通常采用矩阵的任一种范数都小于1或对角占优来判断收敛性。有时也可边计算边观察其收敛性。如何加快迭代过程的收敛速度是一个很重要的问题，实用中更多的采用SOR法，选择适当的松驰因子有赖于实际经验。我们应针对不同的实际问题，采用适当的数值算法。,内容小结,
