求解线性方程组的迭代解法.ppt

《求解线性方程组的迭代解法.ppt》由会员分享，可在线阅读，更多相关《求解线性方程组的迭代解法.ppt（65页珍藏版）》请在三一办公上搜索。

1、第四章,线性方程组迭代解法,第四章目录,1 向量序列与矩阵序列的极限2 Jacobi迭代法3 GaussSeidel迭代法4 松驰法5 迭代法的收敛条件及误差估计 5.1 矩阵的谱半径 5.2 迭代法的收敛条件 5.3 误差估计6 非线性方程组迭代法 6.1 Newton法 6.2 最速下降法,第四章 方程组的迭代解法概述,这一章讨论线性方程组的另一类解法迭代法，由于迭代法能充分避免系数矩阵中零元的存贮与计算，因此特别适用于求解系数矩阵阶数很高而零元素又很多（即大型稀疏）的线性方程组。解线性方程组的迭代法的基本思想与解方程的迭代法相似，首先将方程组Ax=b化为等价方程组x=Mx+g，其中M为n

2、 阶方阵，b=(b1,b2,bn)T，g Rn，任取初始向量x(0)Rn，代入迭代公式：,迭代解法概述(续）,产生向量序列x(k)，若此序列收敛于x*，则有x*=Mx*+g，即x*为原方程组的解。因此，可根据精度要求选择一个合适的x(k)（k充分大时）作为近似解，这就是解线性方程组的迭代法，上式称为迭代格式，M 称为迭代矩阵，若序列x(k)极限存在，称此迭代过程收敛，否则称为发散。,1 向量序列与矩阵序列的极限,与求解方程类似，需要讨论的问题是：如何建立迭代公式，向量序列的收敛条件是什么，若向量序列x(k)收敛，如何进行误差估计？,1 向量序列与矩阵序列的极限,由于Rn中的向量可与Rn的点建立

3、一一对应关系，因此由点列的收敛概念及向量范数的等价性，可得到向量序列的收敛概念。,定义1,向量序列与矩阵序列的极限（续）,n维点列收敛的一种等价描述是其对应坐标序列均收敛，向量序列也有类似的结论。,定理1,矩阵序列的收敛概念及定理,定义2,完全类似地，可以定义矩阵序列的收敛：,与向量序列类似，也有：,定理2,2 雅可比（Jacobi）迭代法,设有n阶线性方程组：,简记为：,其系数矩阵A非奇异，不妨设aii 0(1,2,n)可将上式改写为等价方程组：,雅可比（Jacobi）迭代法（续）,也可写作为：,可简记为：,由此可建立迭代格式：,Jacobi迭代法定义,选取初始向量x(0)代入（4-4）右端

4、，可得x(1)=Bx(0)+g，再将x(1)代入（4-4）右端，可得x(2)=Bx(1)+g，如此继续下去，就产生一个向量序列x(k)，按（4-2）或（4-3）格式迭代求解的方法称为雅可比（Jacobi）迭代法，又叫简单迭代法。迭代式（3-4）中的B 称为迭代矩阵，它可直接由（4-2）或（4-3）得到，也可用系数矩阵A来表示：,若将系数矩阵A分解为A=DLU，其中：,Jacobi迭代法定义（续）,式（4-5）为简单迭代法的矩阵形式。,Jacobi迭代法举例,用Jacobi迭代法求解线性方程组：,例1,解：由第一个方程解x1，第二个方程解x2，第三个方程解x3得Joacbi迭代格式为：,继续迭代

5、下去，迭代结果见表4-1：,取x(0)=(0,0,0)T代入迭代式（4-6）或（4-7）得：,Jacobi迭代法举例,迭代9次，得近似解x(9)=(10.9994,11.9994,12,9992)T，此方程组的准确解为x=(11,12,13)T，从表4-1可以看出，随着迭代次数的增加，迭代结果越来越接近精确解。,3 高斯塞德尔(Gauss-Seidel)迭代法,Jacobi迭代法的优点是公式简单，迭代矩阵容易得到，它又称为同时替换法：在每一步迭代计算过程中，计算x(k+1)时是用x(k)的全部分量代入求x(k+1)的全部分量。因此需同时保留两个近似解向量x(k)和x(k+1)。,高斯塞德尔(G

6、auss-Seidel)迭代法续1,Gauss-Seidel迭代法求解,例2 用Gauss-Seidel迭代法求解例1,解：Gauss-Seidel迭代格式为：,仍取x(0)=(0,0,0)T，计算结果见下表：,显然，用Gauss-Seidel 迭代法比Jacobi迭代法收敛快，这个结论在多数情况下是成立的，但也有Gauss-Seidel迭代比Jacuobi迭代收敛慢，甚至还有Jacobi迭代收敛，Gauss-Seidel迭代发散的情形。,求例2中的Gauss-Seidel法的迭代阵M的两种方法,求例2中的Gauss-Seidel法的迭代阵M的两种方法续1,方法2：可按代入法求M，以避免计算逆

7、矩阵，在Gauss-Seidel迭代式（4-10）中，第 二个式子中的以第一个式子代替。可将第二式右端上标都化为k（可以不管常数）：,求例2中的Gauss-Seidel法的迭代阵M的两种方法续2,由于（4-10）第一式及（4-11），（4-12）的右端上标均为k，即为同时替换迭代式，类似于Jacobi迭代法可直接由它们得迭代阵为：,4 松驰法,通过引入参数，在Gauss-Seidel法的基础上作适当修改，在不增加过多的计算量的条件下，可得到一种新的，收敛更快的迭代法。将Gauss-Seidel迭代格式（4-9）改写为：,松驰法（续）,通过选择适当的参数使此迭代格式收敛更快。称为松驰因子，1时称

8、为超松驰法，=1是Gauss-Seidel迭代，简称为SOR法（Successive Over-Relaxation）。,SOR法的迭代矩阵,将（4-13）代入（4-14）可得：,其矩阵形式为：,所以SOR法的迭代矩阵为：,用SOR法解线性方程组（例3）,例3 取=1.4,x(0)=(1,1,1)T，用SOR法解线性方程组,例 3（续1）,继续下去，计算结果如下：,例 3（续2）,所以，方程组近似解为:,松驰因子的选取对收敛速度影响极大，如何选取使收敛速度加快，或达到最快？这是非常重要的，但又很困难，目前尚无可供实用的计算最佳松驰因子的办法，通常的作法是采用试算法：即从同一初值出发，选不同的松

9、驰因子进行试算，迭代相同的次数，来比较残量r(k)=b Ax(k)的大小，选取使r(k)最小（各分量总体相差最小）的松驰因子。这样做较简单，但比较有效。,小结如下：,5 迭代法的收敛条件及误差估计,5.1 矩阵的谱半径,迭代法的收敛性与迭代矩阵的特征值有关：,设A为n阶方阵，i(i=1,2,，n)为A的特征值，称特征值模的最大值为矩阵A的谱半径，记为：,定义3,矩阵的谱半径（续）,矩阵的谱半径与范数之间有如下关系：设x为对应于特征值的A的特征向量，则由：,这个不等式对A的任何范数、任意特征值都成立，因此，可得矩阵A的谱半径与A的范数之间的一个重要关系：A的谱半径不超过A的任一种范数。即：,公式

10、 的重要性说明,它之所以重要是因为：(A)难计算，而|A|、|A|1计算容易，并且对于任意正数，存在一种矩阵范数很接近(A)，使得成立：,对任意n 阶方阵A，一般不存在矩阵范数使(A)=|A|，但若A为对称矩阵，则有：,下面的结论对建立迭代法的收敛条件十分重要：,定理3,定理3（续）,证明：,5.2 迭代法的收敛条件,证明：,定理4,由5.1 的结果，可以得到如下收敛定理：,迭代法的收敛条件（续1）,推论1,迭代法的收敛条件（续2）,定理4表明，迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及方程组的右端项无关。对同一方程组，由于不同的迭代法其迭代矩阵不同，因此可能出现有的方法收敛，有的方

11、法发散的情形。,两种迭代法举例,例4,讨论Jacobi迭代法与Gauss-Seidel迭代法的收敛性。,解：首先要求出迭代矩阵，然后利用推论1（充分条件）及定理4（充分必要条件）进行讨论。,对Jacobi迭代法：,例4（Jacobi迭代法续）,例4（G-S迭代法续）,对G-S迭代法：,两种迭代法说明,注1：对G-S法，为避免求逆阵可按下面两个方法：,两种迭代法说明（续）,注2：例4也说明0 2确实只是松驰法的必要条件，而非充分条件，因为G-S法即为=1的情形。,定理4虽然给出了判别迭代法收敛的充要条件，但实际使用时很不方便，因为求逆矩阵和特征值的难度并不亚于用直接法求解线性方程组。而推论1仅为

12、充分条件。很多情况下如例3，由推论1无法判别收敛性。下面对一些特殊的方程组，从方程组本身出发给出几个常用的判别条件，而不必求迭代阵的特征值或范数。,直接用矩阵A判定敛散性,定义4,直接用矩阵A判定敛散性（续）,为严格对角占优阵，Jacobi迭代法与G-S迭代法均收敛。,又如例3中，系数矩阵：,为非严格对角占优，但A为对称正定矩阵，且=1.4 松驰法收敛。,如例1中，线性方程组的系数矩阵：,设有线性方程组Ax=b，下列结论成立：1.若A为严格对角占优阵，则Jacobi迭代法与G-S法均收敛；2.若A为严格对角占优阵，0 1，则松驰法收敛；3.若A为对称正定矩阵，0 2，则松驰法收敛；若A为对称正

13、定阵，松驰法收敛 0 2。,三种迭代法判定敛散性举例,解：可以总结，讨论迭代法的收敛性，应首先从A出发讨论其是否具有主对角占优或对称正定性；其次对迭代法的迭代阵讨论其是否有范数小于1；最后利用迭代阵的谱半径讨论（这是充分必要条件）。,例5,例 5(续）,对Jacobi迭代法，其迭代阵容易由A直接得到：,例6,解,Jacobi迭代阵为：,例6,G-S迭代阵为：,两点注释,两点注释（续）,注2：在利用迭代阵的范数判定收敛时（推论1），只要迭代阵的范数小于1，即可判 定其收敛性，但当|1时，则无法判定，还需利用谱半径作最后判定，并且，由于不同的范数其值不同，可能会出现某一种范数小于1但很接近于1（收

14、敛），这时另一种范数可能会大于1（无法判定）的情况，如设Ax=b，其中（见下）:,5.3 误差估计,定理5,定理5（续）,利用定理5 对例1，若给出=104，即要求各分量的误差绝对值不超过104，则由于：,式（4-20）常用于事后估计误差，即在实际计算时，利用相邻两次迭代值之差是否达到精度要求作为停机标准。,这表明需要迭代13次才能保证各分量绝对误差不超过10-4。,迭代改善法,无论是用直接法还是用迭代法求得病态方程组的计算解,当精度不理想时，,可以使用迭代改善的办法进行处理，即,使用迭代改善法,此法常用于解不十分严重病态的方程组。,迭代改善法：,（2）也可与直接法结合进行直接求解。,（1）可

15、用于改善已求得的近似争的精度，,1.对Ax=b 用列主元消元法，分解法均可，分解法（选主元）最好。,即：,具体步骤为：,迭代改善法（续1）,2.求x(1)的修正量z(1)：先求,然后由,即可,的解。,而,就是近似解x(1)的改进解.,这是因为有：,3.可继续下去：再求,迭代改善法（续2）,例1：,与准确解,若用Gauss消元法求解（取五位有效数字）,比较，相差太远。,迭代改善法（续3）,若用迭代改善法：,K,迭代改善法（续4）,例2 Hilbert 阵,较准确的解为,若用列主元法求得近似解：,对x(1)用迭代改善法进行改进：先求,迭代改善法（续5）,用Doolittle分解法求解,x(3)显然

16、已具有四位有效数字,可计算,可继续求：,并由Dolittle分解法解,可得,6 非线性方程组的解法,非线性方程组的一般形式为：,这一节讨论它的求解方法，主要是迭代解法（因为除了极为特殊的非线性方程组以外，类似于线性方程组的直接解法几乎是不可能的），并且这里介绍的迭代解法都采用线性化的方法构成各种形式的迭代格式，只介绍方法，不讨论收敛性。,其中：xi是实变量，fi 是xi 的非线性实函数(i=1，2，n)可记为x=(x1，x2，xn)T，F(x)=(f1(x)，f2(x)，fn(x)T，上述方程组又可记为：F(x)=0,非线性方程组的解法（续）,选取一组初值x1(0)，x2(0)，xn(0)代入

17、迭代格式，可得向量序列x(k)，并且一般有，若x(k)收敛，只要gi连续，则收敛到原方程组的解（向量形式：x=g(x)，x(k+1)=g(x(k)）。,一般方法：将上述方程组改写等价形式：,下面主要介绍Newton法，只介绍基本方法。,此式可展为：,6.1 Newton法,按上述过程求F(x)=0的近似解的方法称为Newton法。,Newton法的具体做法,用Newton法具体做时：,每迭代一次，即要解一个线性方程组（即Newton方程组）,并且每次的系数矩阵F(x(k)不一样。可以证明：Newton法具有二阶收敛速度。控制结束：对预先给定的精度：,两个方程情况下的Newton法,两个方程的情

18、况，加深理解Newton法：,两个方程情况下的Newton法举例,Newton方程组 F(x)在x(0)处取值，F(x)在x(0)取值得：,同单个方程的Nweton法一样：解非线性方程组的Newton法：收敛快，形式简单，格式固定。但同时也：1.对初值要求高；2.迭代一次，需计算n+n2个函数值及导数值；3.求解一个n阶非线性方程组，计算量较大。,6.2 最速下降法,这一小节只介绍大概算法，因为要用别的知识较多。,最速下降法（续）,因此，非线性方程组的求解可转化为求解最优化问题（求(x)的最小值）并且没有任何约束条件，称为无条件约束最优化问题。,求解此类问题的一种基本方法是最速下降法。最速下降

19、法的基本思想是：从最优化问题的近似解x(k)出发，沿使函数(x)下降最快的方向，寻找新的近似解x(k+1)，这样继续下去，逐步逼近最优化问题解。,最速下降法的二维说明,以二维的情形看较容易接受：,最速下降法的二维说明（续）,最速下降法的二维说明续,而在一维搜索方法中：若()简单，就直接用一元函数极值方法求解。一般可用：对分搜索，Fibonacci搜索，黄金分割，插值法等。,用一维搜索任一种方法求出 后代入公式：,即得到第k+1次近似解。,上述整个过程就是求解(x1,x2)的最速下降法，最速下降法优点是计算简单，收敛性好，但收敛速度为线性，故收敛速度较慢，可与Newton法合用：先用最速下降法求一较好的近似值，再用Newton法。,对无约束最优化问题，还可用别的方法求解。,