高中生旷课上网保证书

线性代数方程组的迭代解法对于大型方程组，常用迭代法求解。迭代法与直接法不同，它不能通过有限次的算术运算求得方程组的精确解，而是通过逐步迭代逼近方程组的精确解。但在使用迭代法时，必须考虑收敛性的问题。迭代法较直接法有较明显的优点：程序设计简单，存储量和计算量少等，迭代法其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。第1页/共53页3.2迭代法的一般迭代格式迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。第2页/共53页设非奇异，，则线性方程组有惟一解，经过变换构造出一个等价同解方程组将上式改写成迭代式选定初始向量,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法第3页/共53页如果存在极限则称迭代法是收敛的，否则就是发散的。收敛时，在迭代公式中当时，,则,故是方程组的解。第4页/共53页利用迭代法求解线性方程组需注意的几个问题：1、迭代格式的构造2、迭代格式的敛散性判定3、迭代格式的收敛速度第5页/共53页例3.2.1用迭代法求解线性方程组解构造方程组的等价方程组据此建立迭代公式取计算得迭代解离精确解越来越远迭代不收敛第6页/共53页3.3雅可比迭代法设方程组的系数矩阵A非奇异，且主对角元素，则可将A分裂成记作A=D-L-U第7页/共53页则等价于即因为，则这样便得到迭代公式令则有（k=0,1,2…）称为雅可比迭代公式,J称为雅可比迭代矩阵第8页/共53页雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即第9页/共53页Jacobi迭代法的算法第10页/共53页3.3雅可比迭代法的算法第11页/共53页第12页/共53页3.4高斯-塞德尔（Gauss-Seidel）迭代法3.4.1高斯-塞德尔迭代法的基本思想在Jacobi迭代法中，每次迭代只用到前一次的迭代值。若每次迭代充分利用当前最新的迭代值，即在求时用新分量代替旧分量,就得到高斯-赛德尔迭代法。其迭代法格式为：(i=1,2,…,nk=0,1,2,…)第13页/共53页第14页/共53页3.4.2Gauss—Seidel迭代法的矩阵表示　　将A分裂成A=D-L-U，则等价于于是,则高斯—塞德尔迭代可表示为因为,所以则高斯-塞德尔迭代格式为：则有于是有迭代格式令第15页/共53页3.4.3高斯—塞德尔迭代算法实现高斯-塞德尔迭代算法的计算步骤与流程图与雅可比迭代法大致相同，只是一旦求出变元的某个新值后,就改用新值替代老值进行这一步剩下的计算。第16页/共53页Gauss-Seidel迭代法的算法第17页/共53页第18页/共53页3.5逐次超松弛迭代法（SOR方法）使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛，但由于收敛速度缓慢，使计算量变得很大而失去使用价值。因此，迭代过程的加速具有重要意义。逐次超松弛迭代（Successive-over-relaxation）法，可以看作是带参数的高斯—塞德尔迭代法，实质上是高斯-塞德尔迭代的一种加速方法。第19页/共53页3.5.1超松弛迭代法的基本思想超松弛迭代法目的是为了提高迭代法的收敛速度，在高斯—塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果与高斯-塞德尔迭代方法的迭代值适当加权平均，期望获得更好的近似值。是解大型稀疏矩阵方程组的有效方法之一，有着广泛的应用。其具体计算公式如下：⑴　用高斯—塞德尔迭代法定义辅助量。第20页/共53页⑵　把取为与的加权平均，即合并表示为：式中系数ω称为松弛因子，当ω=1时，便为高斯-塞德尔迭代法。为了保证迭代过程收敛，要求0<ω<2。当0<ω<1时，低松弛法；当1<ω<2时称为超松弛法。但通常统称为超松弛法(SOR)。第21页/共53页3.5.2超松弛迭代法的矩阵表示设线性方程组的系数矩阵A非奇异,且主对角元素,则将A分裂成A=D-L-U,则超松弛迭代公式用矩阵表示为或故显然对任何一个ω值,(D-ωL)非奇异,(因为假设)于是超松弛迭代公式为第22页/共53页例4.4用SOR法求解线性方程组取ω=1.46，要求解：SOR迭代公式k=0,1,2,…，初值该方程组的精确解只需迭代20次便可达到精度要求如果取ω=1(即高斯—塞德尔迭代法)和同一初值,要达到同样精度,需要迭代110次第23页/共53页3.6迭代法的收敛性我们知道,对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。对于方程组经过等价变换构造出的等价方程组在什么条件下迭代序列收敛？先引入如下定理第24页/共53页定理3.1对给定方阵G,若,则为非奇异矩阵,且P44Th2.6.10证:用反证法,若为奇异矩阵,则存在非零向量x,使,即有由相容性条件得由于,两端消去,有,与已知条件矛盾,假设不成立,命题得证。又由于有即将G分别取成G和-G，再取范数又已知，有第25页/共53页定理3.2迭代公式收敛的充分必要条件是迭代矩阵G的谱半径证:必要性设迭代公式收敛,当k→∞时,则在迭代公式两端同时取极限得记,则收敛于0(零向量),且有于是由于可以是任意向量,故收敛于0当且仅当收敛于零矩阵，即当时于是所以必有第26页/共53页充分性设,则必存在正数ε,使则存在某种范数,使,P45Th2.6.11,则,所以,即。故收敛于0,收敛于由此定理可知，不论是雅可比迭代法、高斯—塞德尔迭代法还是超松弛迭代法，它们收敛的充要条件是其迭代矩阵的谱半径。事实上,在例3.2.1中,迭代矩阵G=，其特征多项式为特征值为-2，-3，,所以迭代发散证毕第27页/共53页定理3.3(迭代法收敛的充分条件)若迭代矩阵G的一种范数,则迭代公式收敛,且有误差估计式,且有误差估计式及证:矩阵的谱半径不超过矩阵的任一种范数,已知,因此,根据定理3.2可知迭代公式收敛第28页/共53页又因为,则det(I-G)≠0,I-G为非奇异矩阵,故x＝Gx＋d有惟一解,即与迭代过程相比较,有两边取范数∴第29页/共53页由迭代格式，有两边取范数，代入上式，得证毕由定理知，当时，其值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代（ε为给定的精度要求）作为控制迭代结束的条件第30页/共53页例3.6.1已知线性方程组考察用Jacobi迭代和G-S迭代求解时的收敛性解:做矩阵分解第31页/共53页(1)Jacobi迭代矩阵故Jacobi迭代收敛(2)G-S迭代矩阵故G-S迭代收敛第32页/共53页第33页/共53页定理3.4设n阶方阵为对角占优阵,则非奇P53引理3.1.1证:因A为对角占优阵,其主对角元素的绝对值大于同行其它元素绝对值之和,且主对角元素全不为0,故对角阵为非奇异。作矩阵第34页/共53页利用对角占优知由定理3.1知非奇异,从而A非奇异,证毕系数矩阵为对角占优阵的线性方程组称作对角占优方程组。第35页/共53页定理3.5对角占优线性方程组的雅可比迭代公式和高斯-赛德尔迭代公式均收敛。证:雅可比迭代公式的迭代矩阵为由定理3.4知,这时,再由定理3.3知迭代收敛再考察高斯-赛德尔迭代公式的迭代矩阵令，则有于是,写出分量形式有变形得第36页/共53页设而由上式得由此整理得利用对角占优条件知上式右端小于1,(如果右端大于1,则得出与对角占优条件矛盾的结果)故有据定理3.3知G-S收敛第37页/共53页例3.6.2设求解线性方程组的雅可比迭代求证当<1时,相应的高斯-塞德尔迭代收敛证:由于B是雅可比迭代的迭代矩阵,故有又<1,故有则∴系数矩阵为对角占优阵,故G-S迭代收敛第38页/共53页第39页/共53页第40页/共53页例3.6.3设,证明,求解方程组的Jacobi迭代与G-S迭代同时收敛或发散证:Jacobi迭代矩阵其谱半径第41页/共53页G-S迭代矩阵显然,和同时小于、等于或大于1,因而Jacobi迭代法与G-S迭代法具有相同的收敛性其谱半径第42页/共53页例3.6.4考察用雅可比迭代法和高斯-塞德尔迭代法解线性方程组Ax=b的收敛性，其中解：显然,该线性方程组的系数矩阵为严格对角占优矩阵，所以Jacobi迭代法和G-S迭代法均收敛。第43页/共53页例3.6.5考察用雅可比迭代法和高斯-塞德尔迭代法解线性方程组Ax=b的收敛性，其中解：易知，该线性方程组的系数矩阵为对称正定阵，故G-S迭代法均收敛。Jacobi迭代矩阵为，故Jacobi迭代法发散。第44页/共53页∴Ax=b的系数矩阵按行严格对角占优,故高斯-塞德尔迭代收敛例3.6.6设有迭代格式X(k+1)=BX(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所以该迭代格式收敛。第45页/共53页例3.6.7讨论用雅可比迭代法和高斯-塞德尔迭代法解下述线性方程组的收敛性。第46页/共53页求特征值雅可比矩阵(B)=1∴用雅可比迭代法求解时，迭代过程不收敛1=-1，2,3=1/2第47页/共53页求特征值高斯-塞德尔迭代矩阵(G1)=0.3536<1∴用高斯-塞德尔迭代法求解时，迭代过程收敛1=0,第48页/共53页求解AX=b,当取何值时迭代收敛？解:所给迭代公式的迭代矩阵为例3.6.8给定线性方程组AX=b用迭代公式X(K+1)=X(K)+(b-AX(K))(k=0,1,…）第49页/共53页即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迭代收敛第50页/共53页本章小结本章介绍了解线性方程组迭代法的一些基本理论和具体方法。迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。注意到在使用迭代法解方程组时，其迭代矩阵B和迭代向量f在计算过程中始终不变，迭代法具有循环的计算公式，方法简单，程序实现方便，它的优点是能充分利用系数的稀疏性，适宜解大型稀疏系数矩阵的方程组。第51页/共53页使用迭代法解线性方程组的关键问题是其收敛性与收敛速度，而收敛性与迭代初值的选取无关。在实际计算中，判断一种迭代格式收敛性较麻烦，由于求迭代的谱半径时需要求特征值，当矩阵的阶数较大时，特征值不易求出，通常采用矩阵的任一种范数都小于1或对角占优或对称正定性来判断收敛性。有时也可边计算边观察其收敛性。如何加快迭代过程的收敛速度是一个很重要的问题，实用中更多的采用SOR法，选择适当的松驰因子ω有赖于实际经验。我们应针对不同的实际问题，采用适当的数值算法。第52页/共53页