数值分析课件ch06方程组迭代法

1、1第六章线性方程组的数值解法-迭代法2q 直接法得到的解是理论上准确的，但是计算量都是直接法得到的解是理论上准确的，但是计算量都是 n3 n3数量级，存储量为数量级，存储量为n2n2量级，这在量级，这在n n比较小的时候比较小的时候 还比较合适（还比较合适（n400n400）q 实际问题中，往往方程组的阶数很高，而且这些矩实际问题中，往往方程组的阶数很高，而且这些矩 阵阵( (系数矩阵系数矩阵) )往往是含有大量的往往是含有大量的0 0元素（元素（稀疏矩阵稀疏矩阵 方程组方程组）。直接法运算量将会很大并且大量占用计）。直接法运算量将会很大并且大量占用计 算机资源。算机资源。q 因此有必要引入一

2、类新的方法：因此有必要引入一类新的方法：迭代法迭代法。 引言引言3q q 迭代法的基本思想迭代法的基本思想 迭代法是解线性方程组的一种重要的实用方迭代法是解线性方程组的一种重要的实用方 法，特别适用于求解在实际中大量出现的，系法，特别适用于求解在实际中大量出现的，系 数矩阵为稀疏阵的大型线性方程组。数矩阵为稀疏阵的大型线性方程组。 迭代法的基本思想是去构成一个向量序列迭代法的基本思想是去构成一个向量序列 x x( (k k) ) ， 使其收敛至某个极限向量使其收敛至某个极限向量x x* * ，并且，并且x x* *就是要求解就是要求解 的方程组：的方程组：Ax = b Ax = b 的准确解。

3、的准确解。4迭代法的主要步骤迭代法的主要步骤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 表迭代次数表迭代次数。 nTnRxxxX002)0(10,5 如果按上述迭代公式所得到的向量序列如果按上述

4、迭代公式所得到的向量序列 x x( (k k) ) 收收敛于某个向量敛于某个向量x x* * , ,则则x x* * 就是方程组就是方程组 Ax =b Ax =b 的解，并称的解，并称此迭代法此迭代法收敛收敛。否则，就叫不收敛或发散。否则，就叫不收敛或发散。 迭代公式中的矩阵迭代公式中的矩阵B B ，称为，称为迭代矩阵迭代矩阵。 q 问题问题 l 迭代公式的建立迭代公式的建立l 迭代公式的收敛性迭代公式的收敛性l 收敛速度收敛速度l 误差估计误差估计6基本迭代公式基本迭代公式,0,AMNM把矩阵把矩阵 A A 分裂为分裂为()AxbMN xb则则11xMNxM b.xBxf记记 B = M-

5、-1N， f = M- -1b， 则则注注：选取选取M M阵，就得到解阵，就得到解 Ax=b Ax=b 的各种迭代法的各种迭代法. .7 本章重点介绍三个迭代法，即：本章重点介绍三个迭代法，即： l JacobiJacobi迭代法迭代法l Gauss-SeidelGauss-Seidel 迭代法迭代法l 超松弛迭代法（超松弛迭代法（SORSOR法）法）8Jacobi迭代法迭代法112213 31111221 123 322221 122,1111()1()1()nnnnnnnn nnnnxa xa xa xbaxa xa xa xbaxa xa xaxba由方程组由方程组AXAX= =b b的

6、第的第i i个方程解出个方程解出ix(1,2, )in得到一个同解方程组得到一个同解方程组q 9获得相应的迭代公式获得相应的迭代公式(1)( )( )( )11221331111(1)( )( )( )221 12332222(1)( )( )( )1 122,111()1()1()kkkknnkkkknnkkkknnnn nnnnnxa xa xa xbaxa xa xa xbaxa xa xaxbaJacobi迭代法迭代法取初始向量取初始向量(0)(0)(0)(0)12(,)TnXxxx称上式为雅可比迭称上式为雅可比迭JacobiJacobi迭代公式。迭代公式。10Jacobi迭代法的矩阵

7、形式迭代法的矩阵形式若记若记q 000000211221212211nnnnnnaaaUaaaLaaaD则有则有 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 11q 迭代矩阵迭代矩阵 Jacobi迭代法的特点迭代法的特点1()JBDLU1()JBDLUq 每迭代一次主要是计算一次矩阵乘向量每迭代一次主要是计算一次矩

8、阵乘向量 所以计算量为所以计算量为n n平方数量级。平方数量级。 )(kJxBq 计算过程中涉及到的中间变量计算过程中涉及到的中间变量 及及 , ,需要需要 两组工作单元两组工作单元x(n),y(n)x(n),y(n)来存储来存储. .q 计算过程中计算过程中, ,初始数据初始数据A A始终不变始终不变; ; )(kx)1( kx12问题：如何判断迭代终止？q 定理定理若迭代矩阵若迭代矩阵B B满足满足|B|B|1 1 则则)1()()(*1kkkXXBBXXq 此定理此定理给出了一个停止迭代的判别准则。给出了一个停止迭代的判别准则。)1()(kkXX13q 输入最大迭代次数输入最大迭代次数N

9、 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;end17高斯高斯塞德尔塞德尔( (Gauss-Seidel) )迭代法迭代法 q q 研究雅可比迭代法，我们发现在逐个求 的分量时， 当计算到 的分量时，当计算到 都已 经求得.设想一旦新分量代替旧分量，可能会加速收敛。 例如例如 (1)kX(1)kix(1)(1)11,kkixx

10、(1)( )( )( )13112121311111111(1)(1)( )( )23221213222222222kkkknnkkkknnaaabxxxxaaaaaaabxxxxaaaa 18)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax Gauss-

11、Seidel迭代法分量形式迭代法分量形式 19Gauss-Seidel迭代的矩阵形式迭代的矩阵形式bLDUxLDxbLDUxLDxbUxxLDbxULDbAxkk1)(1)1(11)()()()()()(作作 A 的另一个分裂：的另一个分裂：()ADLUq 迭代矩阵迭代矩阵 1GBDLU20例子例子1231231231023210152510 xxxxxxxxx(1)( )( )123(1)(1)( )213(1)(1)(1)3121(23)101(215)101(210)5kkkkkkkkkxxxxxxxxx解：解：相应的高斯相应的高斯- -赛德尔迭代公式为赛德尔迭代公式为21取迭代初值取迭

12、代初值(0)(0)(0)(0)123(,)(0,0,0)TTXxxx按此迭代公式进行迭代，计算结果为按此迭代公式进行迭代，计算结果为k( )1kx( )2kx( )3kx01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.999922迭代法的收敛性迭代法的收敛性 迭代法的收敛性迭代法的收敛性，是指方程组是指方程组bAx q 从任意初始向量从任意初始向量X X(0)(0)出发，由迭代算法出发，由迭代算法fBxxkk)()1(算出向量序列算出向量序列,)1()()2()1(

13、kkxxxx随着随着k k的增加而趋向于解向量的增加而趋向于解向量X X * *。q 记各次记各次误差向量误差向量)()1(1)0(0kkXXXXXX 23迭代法的收敛性迭代法的收敛性 q 迭代法的收敛性等价于误差向量序列迭代法的收敛性等价于误差向量序列,10k 随着随着k k的增加而的增加而趋向于零趋向于零。q 由由 x(k+1)=Bx(k)+f 及及 x*=Bx*+fk+1 =X(k+1)-X*=B（X(k)-X*） = = B k+1（X(0)-X)=B k+1 0 可推知可推知q x x( (k k) ) 的收敛性的收敛性 B Bk k 0 0 ( (k k ) ) 24迭代法的收敛性

14、定理迭代法的收敛性定理 q 定理定理 (充要条件判别法充要条件判别法)给定方程组给定方程组 X=BX+f则迭代公式则迭代公式(1)( )kkXBXf对任意初始向量对任意初始向量 ，都收敛的充要条件为，都收敛的充要条件为(0)nXR( )1B性质有关。性质有关。的的代矩阵代矩阵的取值无关，而只与迭的取值无关，而只与迭和和与与法收敛与否法收敛与否表明，线性方程组迭代表明，线性方程组迭代定理定理 1 . 3 )0(BfXq 25q 迭代法的收敛性定理迭代法的收敛性定理 定理定理 ( (充分条件判别法充分条件判别法) )给定方程组给定方程组 X=BX+f如果如果 ，则迭代公式，则迭代公式1B 1. 对

15、任意初始向量对任意初始向量 收敛。收敛。(0)nXR(1)( )kkXBXf2. 有如下估计有如下估计( )*( )(1)1,2,3,1kkkBXXXXkB26证明证明 111*( *)( *)kkkkkxxB xxB xxxx111| *| | |(| *| |)kkkkx xBx xxx11| *|1 |kkkBxxxxB27注注 q 由于此估计式，在实际计算中，用 | | X X (k+1) - (k+1) - X X (k) | (k) | 作为迭代终止条件是合理的。 q ( )(1)(0)*1kkBXXXXB进一步可以推知：由于( (B B) ) B B11，B越小，说明(B) 越小

16、，序列 X (k)收敛越快。28收敛速度收敛速度下面我们给出收敛速度的概念下面我们给出收敛速度的概念： 定义定义 R R( (B B)= -)= -lnln( (B B) )，称为迭代法的渐进，称为迭代法的渐进 收敛速度。收敛速度。q 由于由于Gauss-Seidel迭代法逐次用计算出来的新迭代法逐次用计算出来的新值代替旧值，所以在收敛的条件下，它要比值代替旧值，所以在收敛的条件下，它要比Jacobi迭代法收敛速度快。迭代法收敛速度快。29Jacobi Jacobi 和和Gauss-SeidelGauss-Seidel的收敛性的收敛性1.() 1 ()1 ;JGAXbJacobi Seidel

17、BB解解线线性性方方程程组组的的迭迭代代法法收收敛敛的的充充要要条条件件是是2. 1 1 JGAXbJacobi SeidelBB解解线线性性方方程程组组的的迭迭代代法法收收敛敛的的充充分分条条件件是是。 ULDBULDBGJ11, 其中其中301311211111123221222222313233333331230000nnJnnnnnnnnnnaaaaaaaaaaaaBaaaaaaaaaaaa注注 31525110101021011020JB对于前面的例子由迭代矩阵的特征方程由迭代矩阵的特征方程05211102121012311717,51010 因而雅可比迭代公式是收敛的。因而雅可比迭

18、代公式是收敛的。32注注 的特征值。因而可由此式求解等价于因此由于因为：可避开求逆矩阵的特征值法迭代阵求BULDBILDULDLDULDLDLDBILDULDB0)(det(0)det(0)det()(det()det()()()det()det()()( S-G 11111133直接用矩阵直接用矩阵A A判定敛散性判定敛散性q q 定义定义 如果矩阵如果矩阵A A满足条件满足条件(1,2, )(2)iiijj iaain则称则称A A是是严格对角占优阵严格对角占优阵(strictly diagonally dominant (strictly diagonally dominant matr

19、ix)matrix)；342100110114100141001410014BAA为按行按列为按行按列严格严格对角占优阵；对角占优阵；B为按行对角为按行对角占优阵。占优阵。实例实例(Example)(Example)35定理定理1 1 若若A A为为严格对角占优阵严格对角占优阵，则，则J Jacobiacobi 迭代法迭代法和和 G-SG-S迭代法迭代法收敛。收敛。 定理定理2 2 若若A A为为对称正定阵对称正定阵，则，则G-SG-S迭代法收敛迭代法收敛。 相关定理相关定理q q 36定理1的证明证 首先证明首先证明JacobiJacobi 迭代的收敛性。由迭代的收敛性。由nnnJnnnnn

20、nnnJabababfaaaaaaaaaaaaULDB22211121222222111111121,000)(易求ijnjiiijniJaaB,11max 由严格对角占优定义，得由严格对角占优定义，得 B BJ J 1, = detdet( ( ( (D-LD-L)-)-U U)=0 )=0 38 我们通过我们通过A A的严格对角占优性质去证明的严格对角占优性质去证明detdet( ( ( (D-D-L L)-)-U U)=0)=0的根的根 有性质有性质 | | |1 |1。用。用反证法反证法：假设：假设| | |1 |1，且由于，且由于A A的严格对角占优性质，有的严格对角占优性质，有 n

21、iaaaanijijijijnijjijii, 2 , 1,111, 1nnnnaaaaaaaaaULD21112221111111)(39是严格对角占优阵，所以它是非奇异的，即det(D-L)-U) 0与特征值满足det(D-L)-U) =0 矛盾。故 | |1即(BG) 11 时，称为时，称为超松弛算法超松弛算法，当，当11 时，时，称为称为亚松弛算法亚松弛算法。 目前，还没有自动选择因子的一般方法，实目前，还没有自动选择因子的一般方法，实际计算中，通常取（际计算中，通常取（0 0，2 2）区间内几个不同的）区间内几个不同的值进行试算，通过比较后，确定比较理想的松弛值进行试算，通过比较后，

22、确定比较理想的松弛因子因子。 46例例 用用SORSOR法求解线性方程组法求解线性方程组 243024410143034321xxx 取=1 ，即Gauss-Seidel迭代： 625. 05 . 725. 075. 0675. 0)1(2)1(3)(3)1(1)1(2)(2)1(1kkkkkkkxxxxxxx 取=1.25 ，即SOR迭代法： 5 . 725. 03125. 075. 93125. 025. 09375. 05 . 79375. 025. 0)(3)1(2)1(3)(3)(2)1(1)1(2)(2)(1)1(1kkkkkkkkkkxxxxxxxxxx47例例 迭代结果见表3.

23、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.0966863

24、43.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.000348648 迭代法若要精确到七位小数，迭代法若要精确到七位小数，u Gauss-SeidelGauss-Seidel迭代法需要迭代法需要3434次迭代

25、；次迭代；u 而用而用SORSOR迭代法迭代法( (=1.25)=1.25)，只需要，只需要1414次迭代。次迭代。 可见，若选好参数可见，若选好参数，SORSOR迭代法收敛速度会迭代法收敛速度会很快。很快。q 49SOR迭代的矩阵形式：迭代的矩阵形式：inijkjijijkjijiikikibxaxaaxx)(11)1()()1(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)+(D-L)-1b 记记 B=(D-L)-1 (1-)D+U 称为称为SORSOR法迭代矩阵法迭代矩阵。 50SOR迭代法的收敛性迭代法的收敛性q (1)SOR法收敛的充要条件是法收敛的充要条件是(B)1。(2)