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

《3线性方程组的迭代解法.ppt》由会员分享，可在线阅读，更多相关《3线性方程组的迭代解法.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 线性方程组的迭代解法线性方程组的迭代解法 1 1 迭代法的一般形式迭代法的一般形式 设线性方程组设线性方程组 Ax=b的的系系数数矩矩阵阵A非非奇奇异异，从从而而有有一一组组唯唯一一的的解解。构构造造等等价价的的方方程组程组 1建立迭代公式。建立迭代公式。任任取取一一个个初初值值x(0)，由由迭迭代代公公式式产产生生x近近似似解解的的一一个个向向量量序序列列x(k)，若，若则有则有 即即 x*是是Ax=b的解。的解。注注1迭迭代代公公式式x(k+1)=Bx(k)+f 的的构构造造形形式式不不同同，就就可可得得到到不同的迭代法。不同的迭代法。2 定定义义3.1若若对对任任意意的的初

2、初值值x（0 0），迭迭代代公公式式 x(k+1)=Bx(k)+f 产产生生的的向向量量序序列列 x（k）均均收收敛敛，则则称称迭迭代代公公式式是是收收敛敛的的，否否则则称迭代公式是发散的。称称迭代公式是发散的。称B B为迭代矩阵。为迭代矩阵。注注3由由迭代法产生的向量序列迭代法产生的向量序列 的收敛终止条件常为的收敛终止条件常为 注注2 2 迭代法不需存储系数矩阵的零元素，特别适合求迭代法不需存储系数矩阵的零元素，特别适合求解零元素较多的稀疏矩阵。用直接解法求解时，一次消解零元素较多的稀疏矩阵。用直接解法求解时，一次消元就可能使系数阵丧失其稀疏性，不能充分利用其稀疏元就可能使系数阵丧失其稀疏

3、性，不能充分利用其稀疏的特点。的特点。3例例3.1 用迭代法求解方程组用迭代法求解方程组 42 几种常用的迭代公式几种常用的迭代公式 从三个方程中分别解出从三个方程中分别解出 取初值取初值x(0)=(0,0,0)T，得到迭代序列，得到迭代序列x(k)如下表如下表k 0123456789x102.50002.87503.13643.02403.00032.99382.99903.00023.0001x203.00002.36362.04551.94781.98402.00002.00262.00061.9999x303.00001.00000.971600.920401.00101.00391.

4、00310.999850.99988 方程组的准确解为方程组的准确解为 x=(3,2,1)=(3,2,1)T T，从上表的计算结果可看出，从上表的计算结果可看出，向量序列向量序列 x（k）收敛于方程组的准确解。收敛于方程组的准确解。5构造迭代格式为构造迭代格式为一般说来，对方程组一般说来，对方程组 6 6一、一、Jacobi方法（方法（简单迭代法）简单迭代法）并设并设从第从第i个方程解出个方程解出xi，得等价的方程组，得等价的方程组构造迭代公式为构造迭代公式为 这这种种迭迭代代格格式式称称为为JacobiJacobi迭迭代代法法，也也称称为为简简单单迭迭代代法法。记记 7得得JacobiJac

5、obi迭代法的矩阵形式为迭代法的矩阵形式为其中其中 8二、二、Gauss-Seidel 迭代法迭代法 在在例例1的的Jacobi 迭迭代代法法中中，可可以以看看出出，在在计计算算 时时，要要利用利用 ，但此时的，但此时的 已经计算出来了。可以利用已经计算出来了。可以利用 代替代替 。一般地，计算。一般地，计算 (ni2)时，可使用时，可使用 代代替替 (i p1)，这这样样收收敛敛会会快快一一些些，由由此此形形成成一一种种新新的的迭代法，称为迭代法，称为Gauss-Seidel迭代法。迭代法。例例3.2 用用Seidel迭代法计算例迭代法计算例1，并与例，并与例1 的结果作比较。的结果作比较。

6、解解 迭代公式为迭代公式为 9用它计算得到的序列用它计算得到的序列x(k)列表如下表列表如下表可见可见Gauss-Seidel迭代法比迭代法比Jacobi迭代法收敛要快一些。迭代法收敛要快一些。Seidel迭代法的迭代公式如下迭代法的迭代公式如下 10k0123456x102.50002.97733.00982.99982.99993.0000 x202.09092.02891.99681.99972.00012.0000 x301.22731.00410.99591.00021.00011.0000 Seidel 迭代法的矩阵迭代形式为迭代法的矩阵迭代形式为 Seidel 迭代法的矩阵形式迭

7、代公式迭代法的矩阵形式迭代公式 11注注1 Seidel 迭代法在用计算机计算时，只需一组内存单元。迭代法在用计算机计算时，只需一组内存单元。注注2 在在一一定定的的条条件件下下，Seidel 迭迭代代法法比比Jacobi迭迭代代法法收收敛敛的的速度快。速度快。算法算法 （Gauss-SeidelGauss-Seidel迭代法）迭代法）12三、逐次超松弛法三、逐次超松弛法(SOR方法方法)13 逐次超松弛法逐次超松弛法(Successive Over Relaxation Method)(Successive Over Relaxation Method)可看可看成是成是Gauss-Seide

8、lGauss-Seidel方法的加速，方法的加速，SeidelSeidel迭代法是迭代法是SORSOR方法的特例。方法的特例。将将SeidelSeidel方法的迭代公式方法的迭代公式改写为改写为记记则则为加快收敛，在增量为加快收敛，在增量 前加一个因子前加一个因子 ，得，得称此公式为逐次超松弛法称此公式为逐次超松弛法(SOR法法)。当当01211时，称为超松弛法。时，称为超松弛法。14故故SOR方法的矩阵形式迭代公式为方法的矩阵形式迭代公式为 15SORSOR方法的矩阵形式为方法的矩阵形式为例例3.3 用用Seidel 迭代法和取迭代法和取=1.45的的SOR法求解方程组法求解方程组解解 取初

9、值取初值x(0)=(1,1,1)T，精度，精度 用用Gauss-Seidel迭代法迭代有迭代法迭代有 16 达到同样的精度达到同样的精度Gauss-Seidel迭代法需要迭代迭代法需要迭代72步，而步，而取取=1.45的的SOR法只需要迭代法只需要迭代25步。由此可见选择适当的松步。由此可见选择适当的松弛因子，弛因子，SOR方法收敛速度明显加快。所以方法收敛速度明显加快。所以SOR方法常用方法常用来求解大型的线性方程组。来求解大型的线性方程组。准确值准确值x=(1,1,2)=(1,1,2)T T取取=1.45=1.45的的SORSOR法迭代法迭代2525步有步有 3 迭代法的收敛条件迭代法的收

10、敛条件设设，引进误差向量，引进误差向量有有 17定理定理3.1 对任意初始向量对任意初始向量x(0)和和f，由，由 产生产生的迭代序列的迭代序列x(k)收敛的充要条件是收敛的充要条件是(B)1.证证 1)必要性必要性 18基本基本定理定理 设设迭代格式迭代格式 收敛，则收敛，则由基本定理和结论（由基本定理和结论（2 2）可证。）可证。2)充分充分性性 定理定理3.1是充分必要条件，既能判别迭代法收敛性，也可以是充分必要条件，既能判别迭代法收敛性，也可以判别迭代法不收敛的情况。但由于判别迭代法不收敛的情况。但由于(B)的计算常常比解方程的计算常常比解方程组本身更困难。基本定理和定理组本身更困难。

11、基本定理和定理3.1可以看到，迭代法收敛与否可以看到，迭代法收敛与否与迭代矩阵与迭代矩阵B的性态有关，与初始向量的性态有关，与初始向量x(0)和右端向量和右端向量 f 无关。无关。由于由于(B)难于计算，而由结论难于计算，而由结论1又有又有(B)|B|，所以当，所以当|B|1时，必有时，必有 (B)1，于是得到，于是得到 19 定理定理3.2 若若|B|1，则由迭代格式，则由迭代格式x(k+1)=Bx(k)+f 和任意初始向和任意初始向量量x(0)产生的迭代序列产生的迭代序列x(k)收收 敛于准确解敛于准确解x*。且有误差估计。且有误差估计 20 定理定理3.2是迭代法收敛的充分条件，它只能判

12、别收敛的情况，是迭代法收敛的充分条件，它只能判别收敛的情况，当当|B|1时，不能由此断定迭代不收敛。常用时，不能由此断定迭代不收敛。常用|B|11 或或|B|1判别迭代法收敛。判别迭代法收敛。常用定理常用定理3.23.2中的结论（中的结论（1 1）来设置迭代终止的判别条件，即）来设置迭代终止的判别条件，即只要相邻两次的迭代结果之差达到误差精度时，迭代终止。只要相邻两次的迭代结果之差达到误差精度时，迭代终止。从定理从定理3.2中的结论（中的结论（2）可知，当）可知，当|B|的值越小，收敛就越快。的值越小，收敛就越快。也可以用也可以用|B B|的值的值来近似估计迭代的次数。来近似估计迭代的次数。在

13、计算出在计算出x(1)(1)时，就可时，就可估计出迭代次数估计出迭代次数k，不过估计偏保守，次数一般偏大。，不过估计偏保守，次数一般偏大。例例3.4 判别例判别例3.1和例和例3.2中的中的Jacobi迭代法和迭代法和Seidel迭代法的收敛迭代法的收敛性。如果取原点作为初始点，需要迭代多少次，能保证误差小性。如果取原点作为初始点，需要迭代多少次，能保证误差小于于10-6。解解 （1）Jacobi迭代法收敛。因为迭代法收敛。因为x0=(0,0,0),容易知道容易知道x1=(2.5,3,3).|x0-x1|=3.利用上述定理的第二个公式，可以得到利用上述定理的第二个公式，可以得到 21(2)Ga

14、uss-Seidel迭代法收敛迭代法收敛。类似的可以估计迭代的次数。类似的可以估计迭代的次数。22 由于由于 ，所以，所以Gauss-SeidelGauss-Seidel方法方法一般比一般比JacobiJacobi方法方法收敛快收敛快。例例3.5 判别方程组的判别方程组的Jacobi迭代法的收敛性。迭代法的收敛性。解解但但Jacobi迭代法收敛迭代法收敛 23定义定义3.23.2 若矩阵若矩阵 A=(=(aij)nn nn 满足满足 且至少成立严格不等式，则称且至少成立严格不等式，则称A是对角占优的。是对角占优的。24定义定义3.33.3 若矩阵若矩阵 A=(=(aij)nn nn 满足满足

15、则称则称A是严格对角占优的。是严格对角占优的。定义定义3.43.4 若矩阵若矩阵 A 通过行交换和相应的列交换，能够变成通过行交换和相应的列交换，能够变成 的的形形式式，其其中中 A11 和和 A22 为为方方阵阵，则则称称 A是是可可约约的的，否否则则称称 A 是是不可约的。不可约的。25所以解该方程组的所以解该方程组的Jacobi迭代法和迭代法和Seidel迭代法均收敛。迭代法均收敛。例例3.63.6对例对例3.13.1的方程组的方程组由于其系数矩阵由于其系数矩阵 是严格对角占优的，故是严格对角占优的，故定理定理3.33.3 （1 1）若矩阵）若矩阵A严格对角占优，则严格对角占优，则A非奇

16、异。非奇异。（2 2）若）若A A不可约，且具有对角占优，则不可约，且具有对角占优，则A A非奇异。非奇异。定定理理3.43.4 若若A 是是严严格格对对角角占占优优或或 A 是是不不可可约约对对角角占占优优，则则解解方程组方程组Ax=b的的JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法均收敛。迭代法均收敛。定理定理3.5 SOR方法收敛的必要条件是方法收敛的必要条件是02。26证明证明 定理定理3.6 如果如果A是实对称正定矩阵，且是实对称正定矩阵，且02，则，则SOR方法收敛方法收敛注注 由定理由定理6 6的结论，若的结论，若A A是实对称正

17、定矩阵，则是实对称正定矩阵，则Gauss-SeidelGauss-Seidel方法收敛，但方法收敛，但JacobiJacobi方法不一定收敛。方法不一定收敛。定理定理3.8 若若A是对称正定矩阵，且是三对角阵，则是对称正定矩阵，且是三对角阵，则最佳松弛因最佳松弛因子为子为 其中其中BJ是是Jacobi迭代法的迭代矩阵。迭代法的迭代矩阵。应用中常采取试算方法来确定应用中常采取试算方法来确定最佳松弛因子。最佳松弛因子。加速收敛的加速收敛的效果也随问题而有所改变。对有的问题，可加速很多倍，对有效果也随问题而有所改变。对有的问题，可加速很多倍，对有的问题则加速不明显的问题则加速不明显.27 最后提一下

18、关于松驰因子最后提一下关于松驰因子的选取，的选取，的选取将影响的选取将影响(B)的大小，使的大小，使(B)最小的最小的值称为最佳松弛因子，记为值称为最佳松弛因子，记为 opt。opt的选取是一个相当复杂和困难的问题，目前还没有的选取是一个相当复杂和困难的问题，目前还没有无完善的方法，只有针对一些特殊矩阵有部分结果。无完善的方法，只有针对一些特殊矩阵有部分结果。定理定理3.7 如果如果A严格对角占优矩阵，则当严格对角占优矩阵，则当011时时SORSOR方方法收敛。法收敛。所以所以Seidel迭代法及迭代法及SOR法法(0 2)都收敛，都收敛，但但A不是对角占不是对角占优阵，就无法判断优阵，就无法

19、判断Jacobi迭代法收敛性，只有改求迭代法收敛性，只有改求(BJ)。例例3.7 3.7 若方程组的系数阵为若方程组的系数阵为 解解 28试判断它对各种迭代法的收敛性试判断它对各种迭代法的收敛性.29所以对所以对Jacobi迭代法不收敛。迭代法不收敛。例例3.8 3.8 设有方程组为设有方程组为判别其判别其JacobiJacobi迭代法和迭代法和SeidelSeidel迭代法的收敛性。迭代法的收敛性。解解所以解方程组的所以解方程组的JacobiJacobi迭代法和迭代法和SeidelSeidel迭代法均不收敛。迭代法均不收敛。但交换方程组中两个方程的顺序得但交换方程组中两个方程的顺序得方程组的系数矩阵为方程组的系数矩阵为 是严格对角占优的矩阵，所以解新方程组的是严格对角占优的矩阵，所以解新方程组的JacobiJacobi迭代法迭代法和和SeidelSeidel迭代法均收敛。迭代法均收敛。30作业习题三，习题三，1，2，4，5，6,8