数值分析方程组迭代法幻灯片.ppt

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

1、数值分析课件方程组迭代法数值分析课件方程组迭代法1第1页，共54页，编辑于2022年，星期六q 直接法得到的解是理论上准确的，但是计算量都是直接法得到的解是理论上准确的，但是计算量都是 n3 n3数量级，存储量为数量级，存储量为n2n2量级，这在量级，这在n n比较小的时候比较小的时候 还比较合适（还比较合适（n400n400）q 实际问题中，往往方程组的阶数很高，而且这些矩实际问题中，往往方程组的阶数很高，而且这些矩 阵阵(系数矩阵系数矩阵)往往是含有大量的往往是含有大量的0 0元素（元素（稀疏矩阵稀疏矩阵 方程组方程组）。直接法运算量将会很大并且大量占用计）。直接法运算量将会很大并且大量占

2、用计 算机资源。算机资源。q 因此有必要引入一类新的方法：因此有必要引入一类新的方法：迭代法迭代法。引言引言2第2页，共54页，编辑于2022年，星期六q q 迭代法的基本思想迭代法的基本思想 迭代法是解线性方程组的一种重要的实用方迭代法是解线性方程组的一种重要的实用方 法，特别适用于求解在实际中大量出现的，系法，特别适用于求解在实际中大量出现的，系 数矩阵为稀疏阵的大型线性方程组。数矩阵为稀疏阵的大型线性方程组。迭代法的基本思想是去构成一个向量序列迭代法的基本思想是去构成一个向量序列 x x(k k)，使其收敛至某个极限向量使其收敛至某个极限向量x x*，并且，并且x x*就是要求解就是要求

3、解 的方程组：的方程组：Ax=b Ax=b 的准确解。的准确解。3第3页，共54页，编辑于2022年，星期六迭代法的主要步骤迭代法的主要步骤The process of iterative methodThe process of iterative methodq 解线性方程组迭代法的主要步骤是解线性方程组迭代法的主要步骤是:l 把线性方程组把线性方程组Ax=bAx=b化成如下形式的同解方程组化成如下形式的同解方程组l x=Bx+f 给出初始向量给出初始向量 ,按迭按迭 代公式代公式 x(k+1)=Bx(k)+f (k=0,1,2,)进行计算进行计算,其中其中k k 表迭代次数表迭代次数。4

4、第4页，共54页，编辑于2022年，星期六 如果按上述迭代公式所得到的向量序列如果按上述迭代公式所得到的向量序列 x x(k k)收敛于收敛于某个向量某个向量x x*,则则x x*就是方程组就是方程组 Ax=b Ax=b 的解，并称此迭代法的解，并称此迭代法收敛收敛。否则，就叫不收敛或发散。否则，就叫不收敛或发散。迭代公式中的矩阵迭代公式中的矩阵B B，称为，称为迭代矩阵迭代矩阵。q 问题问题 l 迭代公式的建立迭代公式的建立l 迭代公式的收敛性迭代公式的收敛性l 收敛速度收敛速度l 误差估计误差估计5第5页，共54页，编辑于2022年，星期六基本迭代公式基本迭代公式把矩阵把矩阵 A A 分裂

5、为分裂为则则记记 B=M-1N，f=M-1b，则则注注：选取选取M M阵，就得到解阵，就得到解 Ax=b Ax=b 的各种迭代法的各种迭代法.6第6页，共54页，编辑于2022年，星期六 本章重点介绍三个迭代法，即：本章重点介绍三个迭代法，即：l JacobiJacobi迭代法迭代法l Gauss-SeidelGauss-Seidel 迭代法迭代法l 超松弛迭代法（超松弛迭代法（SORSOR法）法）7第7页，共54页，编辑于2022年，星期六Jacobi迭代法迭代法由方程组由方程组AXAX=b b的第的第i i个方程解出个方程解出得到一个同解方程组得到一个同解方程组q 8第8页，共54页，编辑

6、于2022年，星期六获得相应的迭代公式获得相应的迭代公式Jacobi迭代法迭代法取初始向量取初始向量称上式为雅可比迭称上式为雅可比迭JacobiJacobi迭代公式。迭代公式。9第9页，共54页，编辑于2022年，星期六Jacobi迭代法的矩阵形式迭代法的矩阵形式若记若记q 则有则有 A=D-L-U A=D-L-U 成立，矩阵形式为成立，矩阵形式为 Dx=（L+U)x+b 等式两边乘以等式两边乘以D D-1 1，得，得 x=D-1（L+U）x+D-1b 由此得到迭代公式由此得到迭代公式(The iterative scheme is:)x（k+1）=D-1（L+U）x（k）+D-1b 10第1

7、0页，共54页，编辑于2022年，星期六q 迭代矩阵迭代矩阵 Jacobi迭代法的特点迭代法的特点q 每迭代一次主要是计算一次矩阵乘向量每迭代一次主要是计算一次矩阵乘向量 所以计算量为所以计算量为n n平方数量级。平方数量级。q 计算过程中涉及到的中间变量计算过程中涉及到的中间变量 及及 ,需要需要 两组工作单元两组工作单元x(n),y(n)x(n),y(n)来存储来存储.q 计算过程中计算过程中,初始数据初始数据A A始终不变始终不变;11第11页，共54页，编辑于2022年，星期六问题：如何判断迭代终止？问题：如何判断迭代终止？q 定理定理若迭代矩阵若迭代矩阵B B满足满足|B|B|1 1

8、 则则q 此定理此定理给出了一个停止迭代的判别准则。给出了一个停止迭代的判别准则。12第12页，共54页，编辑于2022年，星期六q 输入最大迭代次数输入最大迭代次数N N，控制误差，控制误差以及迭代初值以及迭代初值 x=（x1，x2，xn）输出近似值输出近似值y=（y1，y2，yn）Jacobi迭代法的计算步骤迭代法的计算步骤l k=1；l l 如果如果|y-x|N N，算法失败。如果，算法失败。如果 k=1.0e6 x0=y;y=B*x0+f;n=n+1;end16第16页，共54页，编辑于2022年，星期六高斯高斯塞德尔塞德尔(Gauss-Seidel)迭代法迭代法 q JacobiJa

9、cobi迭代法迭代法迭代法迭代法的优点是公式简单，迭代矩阵容易得到，的优点是公式简单，迭代矩阵容易得到，称为称为同时替换法同时替换法：在每一步迭代计算过程中，计算：在每一步迭代计算过程中，计算 x x(k k+1)+1)时是用时是用x x(k k)的全部分量代入求的全部分量代入求x x(k+1)(k+1)的全部分量。的全部分量。q 研究雅可比迭代法，我们发现在逐个求 的分量时，当计算到 的分量时，当计算到 都已 经求得.设想一旦新分量代替旧分量，可能会加速收敛。例如例如 17第17页，共54页，编辑于2022年，星期六 Gauss-Seidel迭代法分量形式迭代法分量形式 18第18页，共54

10、页，编辑于2022年，星期六Gauss-Seidel迭代的矩阵形式迭代的矩阵形式作作 A 的另一个分裂：的另一个分裂：q 迭代矩阵迭代矩阵 19第19页，共54页，编辑于2022年，星期六例子例子解：解：相应的高斯相应的高斯-赛德尔迭代公式为赛德尔迭代公式为20第20页，共54页，编辑于2022年，星期六取迭代初值取迭代初值按此迭代公式进行迭代，计算结果为按此迭代公式进行迭代，计算结果为01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.999921第21页，共54页，

11、编辑于2022年，星期六迭代法的收敛性迭代法的收敛性 迭代法的收敛性迭代法的收敛性，是指方程组是指方程组q 从任意初始向量从任意初始向量X X(0)(0)出发，由迭代算法出发，由迭代算法算出向量序列算出向量序列随着随着k k的增加而趋向于解向量的增加而趋向于解向量X X*。q 记各次记各次误差向量误差向量22第22页，共54页，编辑于2022年，星期六迭代法的收敛性迭代法的收敛性 q 迭代法的收敛性等价于误差向量序列迭代法的收敛性等价于误差向量序列随着随着k k的增加而的增加而趋向于零趋向于零。q 由由 x(k+1)=Bx(k)+f 及及 x*=Bx*+fk+1=X(k+1)-X*=B（X(k

12、)-X*）=B k+1（X(0)-X)=B k+1 0 可推知可推知q x x(k k)的收敛性的收敛性 B Bk k 0 0 (k k)23第23页，共54页，编辑于2022年，星期六迭代法的收敛性定理迭代法的收敛性定理 q 定理定理(充要条件判别法充要条件判别法)给定方程组给定方程组 X=BX+f则迭代公式则迭代公式对任意初始向量对任意初始向量 ，都收敛的充要条件为，都收敛的充要条件为q 24第24页，共54页，编辑于2022年，星期六q 迭代法的收敛性定理迭代法的收敛性定理 定理定理 (充分条件判别法充分条件判别法)给定方程组给定方程组 X=BX+f如果如果 ，则迭代公式，则迭代公式1.

13、对任意初始向量对任意初始向量 收敛。收敛。2.有如下估计有如下估计25第25页，共54页，编辑于2022年，星期六证明证明 26第26页，共54页，编辑于2022年，星期六注注 q 由于此估计式，在实际计算中，用|X X(k+1)-(k+1)-X X(k)|(k)|作为迭代终止条件是合理的。q 进一步可以推知：由于(B B)B B11，B越小，说明(B)越小，序列 X(k)收敛越快。27第27页，共54页，编辑于2022年，星期六收敛速度收敛速度下面我们给出收敛速度的概念下面我们给出收敛速度的概念：定义定义 R R(B B)=-)=-lnln(B B)，称为迭代法的渐进，称为迭代法的渐进 收敛

14、速度。收敛速度。q 由于由于Gauss-Seidel迭代法逐次用计算出来的新值代替迭代法逐次用计算出来的新值代替旧值，所以在收敛的条件下，它要比旧值，所以在收敛的条件下，它要比Jacobi迭代法收敛速迭代法收敛速度快。度快。28第28页，共54页，编辑于2022年，星期六Jacobi Jacobi 和和Gauss-SeidelGauss-Seidel的收敛性的收敛性29第29页，共54页，编辑于2022年，星期六注注 30第30页，共54页，编辑于2022年，星期六对于前面的例子由迭代矩阵的特征方程由迭代矩阵的特征方程因而雅可比迭代公式是收敛的。因而雅可比迭代公式是收敛的。31第31页，共54

15、页，编辑于2022年，星期六注注 32第32页，共54页，编辑于2022年，星期六直接用矩阵直接用矩阵A A判定敛散性判定敛散性q 收敛性收敛性定理虽然给出了判别迭代法收敛的充要条件，但实际使用时很不方便，因为求逆矩阵和特征值的但实际使用时很不方便，因为求逆矩阵和特征值的 难度并不亚于用直接法求解线性方程组。难度并不亚于用直接法求解线性方程组。下面对一些特殊的方程组，从方程组本身出发给出几个常用下面对一些特殊的方程组，从方程组本身出发给出几个常用下面对一些特殊的方程组，从方程组本身出发给出几个常用下面对一些特殊的方程组，从方程组本身出发给出几个常用的判别条件，而不必求迭代阵的特征值或范数。的判

16、别条件，而不必求迭代阵的特征值或范数。的判别条件，而不必求迭代阵的特征值或范数。的判别条件，而不必求迭代阵的特征值或范数。q 定义定义 如果矩阵如果矩阵A A满足条件满足条件则称则称A A是是严格对角占优阵严格对角占优阵(strictly diagonally dominant(strictly diagonally dominant matrix)matrix)；33第33页，共54页，编辑于2022年，星期六A为按行按列为按行按列严格严格对角占优阵；对角占优阵；B为按行对角占优为按行对角占优阵。阵。实例实例(Example)(Example)34第34页，共54页，编辑于2022年，星期六

17、定理定理1 1 若若A A为为严格对角占优阵严格对角占优阵，则，则J Jacobiacobi 迭代法迭代法和和 G-SG-S迭代法迭代法收敛。收敛。定理定理2 2 若若A A为为对称正定阵对称正定阵，则，则G-SG-S迭代法收敛迭代法收敛。相关定理相关定理q q 可以总结，讨论迭代法的收敛性，应首先从可以总结，讨论迭代法的收敛性，应首先从可以总结，讨论迭代法的收敛性，应首先从可以总结，讨论迭代法的收敛性，应首先从A A出发讨出发讨出发讨出发讨论其是否具有主对角占优或对称正定性；其次对迭代论其是否具有主对角占优或对称正定性；其次对迭代论其是否具有主对角占优或对称正定性；其次对迭代论其是否具有主对

18、角占优或对称正定性；其次对迭代法的迭代阵讨论其是否有范数小于法的迭代阵讨论其是否有范数小于法的迭代阵讨论其是否有范数小于法的迭代阵讨论其是否有范数小于1 1；最后利用迭代；最后利用迭代阵的谱半径讨论（这是充分必要条件）。阵的谱半径讨论（这是充分必要条件）。阵的谱半径讨论（这是充分必要条件）。阵的谱半径讨论（这是充分必要条件）。35第35页，共54页，编辑于2022年，星期六定理定理1 1的证明的证明证 首先证明首先证明JacobiJacobi 迭代的收敛性。由迭代的收敛性。由易求 由严格对角占优定义，得由严格对角占优定义，得 B BJ J 1,=detdet(D-LD-L)-)-U U)=0)

19、=0 37第37页，共54页，编辑于2022年，星期六 我们通过我们通过A A的严格对角占优性质去证明的严格对角占优性质去证明detdet(D-LD-L)-)-U U)=0)=0的根的根 有性质有性质|1|1。用。用反证法反证法：假设：假设|1|1，且由于且由于A A的严格对角占优性质，有的严格对角占优性质，有 38第38页，共54页，编辑于2022年，星期六是严格对角占优阵，所以它是非奇异的，即是严格对角占优阵，所以它是非奇异的，即det(det(D-L)-U)(D-L)-U)0 0与特征值与特征值 满足满足det(det(D-L)-(D-L)-U)U)=0=0 矛盾。矛盾。故故|1|1即即

20、(B BG G)1)11 时，称为时，称为超松弛算法超松弛算法，当，当11 时，时，称为称为亚松弛算法亚松弛算法。目前，还没有自动选择因子的一般方法，实目前，还没有自动选择因子的一般方法，实际计算中，通常取（际计算中，通常取（0 0，2 2）区间内几个不同的）区间内几个不同的值进值进行试算，通过比较后，确定比较理想的松弛因子行试算，通过比较后，确定比较理想的松弛因子。45第45页，共54页，编辑于2022年，星期六例例 用用SORSOR法求解线性方程组法求解线性方程组 取=1，即Gauss-Seidel迭代：取=1.25，即SOR迭代法：46第46页，共54页，编辑于2022年，星期六例例 迭

21、代结果见表3.3。表3.3 Gauss-Seidel迭代法与SOR迭代法比较 Gauss-Seidel迭代法SOR迭代法(=1.25)kx1x2x3x1x2x301.00000001.00000001.00000001.00000001.00000001.000000015.25000003.1825000-5.04687506.31250003.9195313-6.650146523.14062503.8828125-5.02929692.62231453.9585266-4.600423833.08789063.9267587-5.01831053.13330274.0402646-5.0

22、96686343.05493163.9542236-5.01144102.95705124.0074838-4.973489753.03433233.9713898-5.00715263.00372114.0029250-5.005713563.02145773.9821186-5.00447032.99632764.0009262-4.998282273.01341103.9888241-5.00279403.00004984.0002586-5.000348647第47页，共54页，编辑于2022年，星期六 迭代法若要精确到七位小数，迭代法若要精确到七位小数，u Gauss-SeidelG

23、auss-Seidel迭代法需要迭代法需要3434次迭代；次迭代；u 而用而用SORSOR迭代法迭代法(=1.25)=1.25)，只需要，只需要1414次迭代。次迭代。可见，若选好参数可见，若选好参数，SORSOR迭代法收敛速度会很快。迭代法收敛速度会很快。q 48第48页，共54页，编辑于2022年，星期六SOR迭代的矩阵形式：迭代的矩阵形式：X(k+1)=(1-)X(k)+D-1(b+LX(k+1)+UX(k)DX(k+1)=(1-)DX(k)+(b+LX(k+1)+UX(k)）(D-L)X（k+1）=(1-)D+U X(k)+b解得解得 X(k+1)=(D-L)-1(1-)D+UX(k)

24、+(D-L)-1b 记记 B=(D-L)-1(1-)D+U 称为称为SORSOR法迭代矩阵法迭代矩阵。49第49页，共54页，编辑于2022年，星期六SOR迭代法的收敛性迭代法的收敛性q (1)SOR法收敛的充要条件是法收敛的充要条件是(B)1。(2)SOR法收敛的充分条件是法收敛的充分条件是|B|1。q 解线性方程组，解线性方程组，SORSOR法收敛的必要条件是法收敛的必要条件是|1-|1-|1|1，即，即 00 2 2。q 设设A AR Rn n n n对称正定，且对称正定，且 0022，则，则SORSOR法对任意法对任意的初始向量都收敛。的初始向量都收敛。50第50页，共54页，编辑于2

25、022年，星期六注注q 松驰因子松驰因子松驰因子松驰因子 的选取对收敛速度影响极大，如何选取的选取对收敛速度影响极大，如何选取的选取对收敛速度影响极大，如何选取的选取对收敛速度影响极大，如何选取 使收使收使收使收 敛速度加快，或达到最快？这是非常重要的，但又很困难。敛速度加快，或达到最快？这是非常重要的，但又很困难。敛速度加快，或达到最快？这是非常重要的，但又很困难。敛速度加快，或达到最快？这是非常重要的，但又很困难。q q目前尚无可供实用的计算最佳松驰因子的办法，通常的作目前尚无可供实用的计算最佳松驰因子的办法，通常的作目前尚无可供实用的计算最佳松驰因子的办法，通常的作目前尚无可供实用的计算

26、最佳松驰因子的办法，通常的作 法是采用试算法：即从同一初值出发，选不同的松驰因子法是采用试算法：即从同一初值出发，选不同的松驰因子法是采用试算法：即从同一初值出发，选不同的松驰因子法是采用试算法：即从同一初值出发，选不同的松驰因子 进行试算，进行试算，进行试算，进行试算，通过比较后，确定比较理想的松弛因子通过比较后，确定比较理想的松弛因子。这样做较简单，但比较有效。这样做较简单，但比较有效。这样做较简单，但比较有效。这样做较简单，但比较有效。q 对于一些特殊的方程组对于一些特殊的方程组 才能确定最优才能确定最优定理定理 设设A是对称正定的三对角矩阵，则是对称正定的三对角矩阵，则(BG)=(BJ)2 1，且且SOR法松弛因子法松弛因子的最优选择为的最优选择为 51第51页，共54页，编辑于2022年，星期六用用SOR方法解方程组方法解方程组 它的精确解为它的精确解为 52第52页，共54页，编辑于2022年，星期六 从此例看到，松弛因子选择得好，会使从此例看到，松弛因子选择得好，会使SOR迭代法的迭代法的收敛大大加速收敛大大加速.本例中本例中 是最佳松弛因子是最佳松弛因子.53第53页，共54页，编辑于2022年，星期六习题六习题六6.3,6.6,6.9,6.10,6.11,6.14,6.17,6.2254第54页，共54页，编辑于2022年，星期六