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

第四章,线性方程组 迭代解法,第四章目录,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 阶方阵，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的点建立一一对应关系， 因此由点列的收敛概念及向量范数的等价性，可得 到向量序列的收敛概念。,定义1,向量序列与矩阵序列的极限（续）,n维点列收敛的一种等价描述是其对应坐标序列均 收敛，向量序列也有类似的结论。,定理1,矩阵序列的收敛概念及定理,定义2,完全类似地，可以定义矩阵序列的收敛：,与向量序列类似，也有：,定理2,2 雅可比（Jacobi）迭代法,设有n阶线性方程组：,简记为：,其系数矩阵A非奇异，不妨设aii 0 (1,2,n)可将上式 改写为等价方程组：,雅可比（Jacobi）迭代法（续）,也可写作为：,可简记为：,由此可建立迭代格式：,Jacobi迭代法定义,选取初始向量x(0)代入（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迭代格式为：,继续迭代下去，迭代结果见表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)。,高斯塞德尔(Gauss-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，以避免计算逆矩阵，在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时称 为超松驰法， = 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）,所以，方程组近似解为:,松驰因子的选取对收敛速度影响极大，如何选取使收敛速度加快，或达到最快？这是非常重要的，但又很困难，目前尚无可供实用的计算最佳松驰因子的办法，通常的作法是采用试算法：即从同一初值出发，选不同的松驰因子进行试算，迭代相同的次数，来比较残量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的任一种范数。即：,公式 的重要性说明,它之所以重要是因为：(A)难计算，而|A|、 |A|1 计算容易，并且对于任意正数 ，存在一种矩阵范数 很接近(A)，使得成立：,对任意n 阶方阵A，一般不存在矩阵范数使 (A) =|A| ，但若A为对称矩阵，则有：,下面的结论对建立迭代法的收敛条件十分重要 ：,定理3,定理3（续）,证明：,5.2 迭代法的收敛条件,证明：,定理4,由5.1 的结果，可以得到如下收敛定理 ：,迭代法的收敛条件（续1）,推论1,迭代法的收敛条件（续2）,定理4表明，迭代法收敛与否只决定于迭代矩阵 的谱半径，与初始向量及方程组的右端项无关。 对同一方程组，由于不同的迭代法其迭代矩阵不同，因此可能出现有的方法收敛，有的方法发散的情形。,两种迭代法举例,例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仅为充分条件。很多 情况下如例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为对称正定阵，松驰法收敛 0 2。,三种迭代法判定敛散性举例,解：可以总结，讨论迭代法的收敛性，应首先从A出发讨 论其是否具有主对角占优或对称正定性；其次对迭代法的 迭代阵讨论其是否有范数小于1；最后利用迭代阵的谱 半径讨论（这是充分必要条件）。,例5,例 5 (续）,对Jacobi迭代法，其迭代阵容易由A直接得到：,例6,解,Jacobi迭代阵为：,例6,G-S迭代阵为：,两点注释,两点注释（续）,注2：在利用迭代阵的范数判定收敛时（推论1），只要 迭代阵的范数小于1，即可判 定其收敛性，但当| |1时 ，则无法判定，还需利用谱半径作最后判定，并且，由 于不同的范数其值不同，可能会出现某一种范数小于1 但很接近于1（收敛）， 这时另一种范数可能会大于1 （无法判定）的情况，如设Ax = b，其中（见下）:,5.3 误差估计,定理5,定理5（续）,利用定理5 对例1，若给出=104，即要求各分量 的误差绝对值不超过104，则由于：,式（4-20） 常用于事后估计误差，即在实际计算时，利用相邻两次迭代值之差是否达到精度要求作为停机标准。,这表明需要迭代13次才能保证各分量绝对误差不超过10-4。,迭代改善法,无论是用直接法还是用迭代法求得病态方程组的计算解,当精度不理想时，,可以使用迭代改善的办法进行处理，即,使用迭代改善法,此法常用于解不十分严重病态的方程组。,迭代改善法：,（2）也可与直接法结合进行直接求解。,（1）可用于改善已求得的近似争的精度，,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)显然已具有四位有效数字,可计算,可继续求：,并由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)代入迭代 格式，可得向量序列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法,两个方程的情况，加深理解Newton法：,两个方程情况下的Newton法举例,Newton方程组 F(x)在x(0)处取值，F (x)在x(0)取值得：,同单个方程的Nweton法一样：解非线性方程组的Newton法： 收敛快，形式简单，格式固定。 但同时也：1. 对初值要求高； 2. 迭代一次，需计算n+n2个函数值及导数值； 3. 求解一个n阶非线性方程组，计算量较大。,6.2 最速下降法,这一小节只介绍大概算法，因为要用别的知识较多。,最速下降法（续）,因此 ，非线性方程组的求解可转化为求解最优化问题 （求(x)的最小值） 并且没有任何约束条件，称为无条件约束最优化问题。,求解此类问题的一种基本方法是最速下降法。 最速下降法的基本思想是： 从最优化问题的近似解x(k)出发，沿使函数(x)下 降最快的方向，寻找新的近似解x(k+1)