计算方法5解线性方程组的迭代法.课件.ppt

1、11()()xIA x bAxbMN xbMxNx bxM NxM b 方方程程组组：第五章 解线性代数方程组的迭代法 适用于求解大型稀疏方程组的解解线性代数方程组解线性代数方程组：,n nnARbRAxb 其其中中，矩矩阵阵,.,.(0)()()*,.给定一初始向量，按照一定的计算格式，构造一个向量序列当时，使 是的解kkxxxxxAxb 迭迭代代法法的的基基本本思思想想：需考虑如下几个问题：需考虑如下几个问题：1.1.如何选取初始向量？如何选取初始向量？初始向量任选初始向量任选.2.2.如何构造迭代序列？如何构造迭代序列？3.3.迭代序列是否收敛？在什么条件下收敛？迭代序列是否收敛？在什么

2、条件下收敛？4.4.若收敛，收敛速度如何？并给出定量的刻画若收敛，收敛速度如何？并给出定量的刻画.5.5.讨论近似解的误差估计讨论近似解的误差估计.1.Jacobi1.Jacobi迭代法迭代法BfBf同解构造同解构造 AxbxBxf 可可统统一一地地表表示示成成即即：简单迭代法的基本思想简单迭代法的基本思想:是构造不动点方程，以求得近似根。第1页，共18页。1,1,.niijjijxBxfxb xf in 构造迭代格式构造迭代格式(0)(1)()(1)()1,0,1,1,.任取初始向量给出迭代格式nkkkkiijjijxxBxfxb xfkin 此迭代格式此迭代格式称为称为JacobiJaco

3、bi迭代迭代格式格式（或简单迭代法），（或简单迭代法），称称B B为为JacobiJacobi迭代矩阵迭代矩阵.迭代格式的收敛性迭代格式的收敛性()()*,lim.若由迭代格式产生的向量序列收敛 即则，否则kkkxxx 称称迭迭代代格格式式收收敛敛称称为为发发散散 *(1)*()*.,0,1,假设 为方程组的精确解，即再与迭代格式相减，得kkxxBxfxxB xxk 2(1)*1(0)*kkBxxBxx 于是于是 (1)*1(0)*0 0kkxxBxx 1 0kB 1()B 可证明：可证明：lim0kkB 1.1.各分量的计算顺序无关。各分量的计算顺序无关。2.2.迭代格式仅有前后两步有关。迭

4、代格式仅有前后两步有关。3.3.新的近似解是已知近似解的线性函数。新的近似解是已知近似解的线性函数。第2页，共18页。(0)()1 fxB对任意右端项 和初始向量，迭代格式收敛.定定理理1 1.1 1.收敛速度的定量刻画收敛速度的定量刻画*()*()(1)()*(1)(0)|1|1|1|kkkkkBxBxxxxBBxxxxB若，则迭代格式收敛于问题的解，且有误差估计的前或的定定理理1 1.2 2.（误误差差事事后后估估计计）（误误差差事事估估计计）()|BB 根据系数矩阵的特点，给出根据系数矩阵的特点，给出判断收敛的几个常用条件：判断收敛的几个常用条件：1.1.若若A A是严格对角占优阵，则是

5、严格对角占优阵，则JacobiJacobi迭代收敛迭代收敛.2.2.若若A A是对称正定阵，是对称正定阵，2D-A2D-A也是对称正定阵，则也是对称正定阵，则JacobiJacobi迭代格式收敛迭代格式收敛.若若A A是对称正定阵，是对称正定阵，2D-A2D-A是非对称正定阵，则是非对称正定阵，则JacobiJacobi迭代格式不收敛迭代格式不收敛.第3页，共18页。2.Gauss-Seidel2.Gauss-Seidel迭代法迭代法 可看作可看作JacobiJacobi迭代的一种改进迭代的一种改进 T(0)(0)(0)1,任取初始向量和Jacobi迭代格式nxxx(1)(0)(0)(0)11

6、22(1)(0)(0)(0)1122(1)(0)(0)(0)1122(1)(0)(0)(0)(0)112211111122222333331 nnnnnnnnnnnnnnnnxb xb xb xfxb xb xb xfxb xb xb xfxb xb xbxb xf (1)()(1)()11,.0,1,，nkkkkiijjijxb xfxBxfin k (1)(0)*111(1)(0)11.假设迭代格式收敛，则比更接近第二行：xxxxx类类似似地地进进行行下下去去(1)(0)(0)(0)1 122(1)()(0)(0)1 122(1)()()()(0)1 1211111222221112111

7、 nnnnnnn nn nnnn nxb xb xb xfxb xb xb xfxb xb xbxb xf 11;0kk 得得到到迭迭代代格格式式！构造迭代格式构造迭代格式(1)x第4页，共18页。(1)()()()1122(1)(1)()()1122(1)(1)(1)()()112231111122222333332(1(113)1 kkkknnkkkknnkkkkknnkknnxb xb xb xfxb xb xb xfxb xb xb xb xfxb x )(1)(1)()2211 kkknnnnnnnnb xbxb xf 矩阵格式：矩阵格式：B=L+U,B=L+U,方程组方程组x=Bx

8、+f x=Lx+Ux+bx=Bx+f x=Lx+Ux+b(1)(1)()kkkxLxUxf(1)(1)()(1)()(1)1()1()()()kkkkkkkxLxUxfI L xUxfxI L UxI Lf此迭代格式此迭代格式称为称为Gauss-Seidel迭代格式迭代格式。注意到，。注意到，这表明：这表明：Gauss-Seidel迭代迭代实际上是实际上是Jacobi迭代迭代!上面的迭代矩阵上面的迭代矩阵被称为被称为G-S迭代法的迭代矩阵迭代法的迭代矩阵.第5页，共18页。迭代格式的收敛性迭代格式的收敛性(1)(1)()(1)()(1)1()1()()()kkkkkkkDxLxUxbD L x

9、UxbxD L UxD L b 若方程组为：若方程组为：Ax=b.则令则令A=D-L-U,于是于是(0)11()1,()().fxGGILUGDLU对任意右端项 和初始向量，迭代格式收敛其中或者 定定理理2 2.1 1.*|1.-G-SGx若，则迭代格式收敛于问题的解 当使用范数时，迭代法比Jacobi迭代法收敛得快些.定定理理2 2.2 2.根据系数矩阵的特点，给出根据系数矩阵的特点，给出判断收敛的几个常用条件：判断收敛的几个常用条件：1.1.若若A A是严格对角占优阵，则是严格对角占优阵，则G-SG-S迭代收敛迭代收敛.2.2.若若A A是对称正定阵，则是对称正定阵，则G-SG-S迭代格式

10、收敛迭代格式收敛.第6页，共18页。3.SOR3.SOR迭代法迭代法 解大型稀疏矩阵方程组的有效方法解大型稀疏矩阵方程组的有效方法(1)1(1)1()1(1)()(1)()G-S ,=+kkkkkkkxD LxD UxD bxxxxxx 迭代格式为:令则有(1)(),=+kkxxx若在“修正项”的前面加一个参数则得到SOR法的计算格式(1)()kkxxx可可看看成成在在上上加加“修修正正项项”而而得得到到！()(+1)()()(+1)()1(1)1()1=+-=1-+=1-+kkkkkkkkxxxxxxD LxD UxD b解得解得(+1)()()=1-+kkDL xDU xb(+1)1()1

11、=()1-()kkxDLDU xDLb011称为，称的迭代为；称的迭代为低低松松松松弛弛法法弛弛因因子子超超松松弛弛法法.Bf构造迭代格式构造迭代格式A Ax x=b b,其其中中A A=D D-L L-U U.第7页，共18页。迭代格式的收敛性迭代格式的收敛性(0)*()1.|.1fxGGx对任意右端项 和初始向量，迭代格式收敛若，则迭代格式收敛于问题的解定定理理3 3.0 0.根据系数矩阵的特点，给出根据系数矩阵的特点，给出判断收敛的几个常用条件：判断收敛的几个常用条件：1.1.若若A A是对称正定阵，则是对称正定阵，则SORSOR迭代格式对迭代格式对 是收敛的是收敛的.2.2.若若A A

12、是严格对角占优的，且松弛因子是严格对角占优的，且松弛因子 ，则，则SORSOR收敛收敛.02.SOR迭代格式收敛的必要条件是 满足：定定理理3 3.1 1.0201第8页，共18页。4.4.最速下降法与共轭梯度法最速下降法与共轭梯度法 解对称正定线性方程组的方法解对称正定线性方程组的方法最速下降法与共轭梯度法，是求最优化问题的重要方法最速下降法与共轭梯度法，是求最优化问题的重要方法.在此，使用它们解线性在此，使用它们解线性方程组。方程组。途径：途径：求解线性方程组问题求解线性方程组问题等价地转等价地转化成化成求极值问题！求极值问题！1()(,)(,)2F xAx xb x考察二次函数：的极小值

13、问题.=Ax b线性方程组：和和之间的关系之间的关系*1min()(,)(,).2nx RAxF xAx xb xxAxb是极值问题的解是的解 设设 为为对对称称正正定定矩矩阵阵，则则下下列列两两个个问问题题.1 1等等4 4价价定定理理*()(),()()=0()=0()F xxF xxF xx 若于 取极小值，则于取极小值；，若于取极小值，则于 取极小值.设设引引理理反反之之求极小值的数值方法：求极小值的数值方法：(0)xP(1)(0)0(1)(0)P()()xxf xf x使使得得*x如此不断地如此不断地修正下去修正下去初始点初始点两个关键步骤：两个关键步骤：1.如何选取搜索方向如何选取

14、搜索方向P？2.如何确定搜索步长如何确定搜索步长？第9页，共18页。1)1)最速下降法最速下降法或梯度法或梯度法最速下降法：最速下降法：每步选择的搜索方向每步选择的搜索方向P都是都是F(x)的的负梯度方向！负梯度方向！1()(,)(,)2122dF xAx xb xdxAxbbAx rbAx 记记为为 =如何选择搜索方向？如何选择搜索方向？()kF x()kF x函函数数值值下下降降最最快快的的方方向向函函数数值值增增加加最最快快的的方方向向函数值下降区域kx函数值上升区域r 几个常用的梯度公式几个常用的梯度公式1.f(x)=C（常数）（常数）,则则 f(x)=0。2.f(x)=bTx,则则

15、f(x)=b；3.(xTx)=2x;4.若若A是实对称方阵是实对称方阵,则有则有(xTAx)=2Ax；1847年,Cauchy提出第10页，共18页。最速下降法的迭代公式推导：最速下降法的迭代公式推导：(0)(0)(0)(0)(0)(0)(1)(0)(0)0(1)(0)(0)(0)(0)0,()()()min()min()xF xxrbAxxrxxrF xF xrF xr 选取初始点计算在点的负梯度=，在直线上寻求一点，使得利用极值的必要条件，我们有利用极值的必要条件，我们有2(0)(0)(0)(0)(0)()()(,)(,)2ddF xAxb rArrdd 2(0)(0)(0)(0)(0)(

16、)()(,)(,)2F xAxbrArr 2(0)(0)(0)(0)(0)()(,)(,)2dF xrrArrd(0)(0)(0)(0)(,)(,)rrArr(0)(0)(0)(0)(,)(,)rrArr于是有于是有(0)(0);rbAx=(0)(0)0(0)(0)(,);(,)rrArr(1)(0)(0)0.xxr(0)(0)(0)(0)(0)dd()ddF xrF xrr 前后两步迭代前后两步迭代的搜索方向是的搜索方向是相互正交的相互正交的!第11页，共18页。重复上述过程，可得最速下降法计算公式：重复上述过程，可得最速下降法计算公式：()()kkrbAx=()()()()(,)(,)kk

17、kkkrrArr(1)()()kkkkxxr梯度法算法步骤：梯度法算法步骤：(0)1.,0,0nxRk给定初始点允许误差令。()()2.();kkrF x 计算搜索方向()()3.|,kkkrx若则，为所求极值点；否则，求最优步长停停止止计计算算()()()()()min().kkkkkF xrF xr使得(1)()()4.,:1,2kkkkxxrkk令令转。第12页，共18页。锯齿现象锯齿现象(0 0)x x*x等高线等高线最速下降法具有算法简单，对初始点没有特别要求，具有全局收敛性，但收敛最速下降法具有算法简单，对初始点没有特别要求，具有全局收敛性，但收敛速度不理想（其收敛速度是速度不理想

18、（其收敛速度是线性的线性的）.注：注：最速下降方向反映了F(x)在点xk处的局部性质局部性质，即它只是F(x)局部下降最快的方向.但从整体上看从整体上看下降路径却经历了不少弯路（折线），因此使收敛速度大大减慢！当接近最优解时，收敛很慢！(0)(0)(0)(0)(0)dd0()ddF xrF xrr=0 0(0)r(1)r(2)r(1)(1)x x(2 2)x x第13页，共18页。2)2)共轭梯度法共轭梯度法()(1)kkPP把和相结合，利用已知迭代点处的梯度方向构造一组共轭方向，.共共轭轭性性 最最速速下下降降方方即即前前后后两两步步的的搜搜索索方方向向、是是A A-正正交交的的向向定定义义

19、共轭。共轭。关于关于和和，则称，则称若有若有AddAddT21210，和和中的两个非零向量中的两个非零向量的对称正定矩阵，对于的对称正定矩阵，对于是是设设21ddRnnAn 如何选择搜索方向？如何选择搜索方向？注注：002121 dddIdTT21dd A-共轭是正交的推广共轭是正交的推广.是是单单位位矩矩阵阵，则则如如果果 A共轭梯度法的迭代公式推导：共轭梯度法的迭代公式推导：与最速下降法相同，即第第一一步步(0)(0)(0)PrbAx=(0)(0)0(0)(0)(,)(,)PPAPP(1)(0)(0)0 xxP以共轭方向作为搜索方向以共轭方向作为搜索方向1952年,Hesteness和St

20、iefel为了解线性方程组而提出的第14页，共18页。()()()()()()()(1)11(),0,=,0.kkkkkkkkkkPrPxrrbAxPAP：设已求得点若令则下一个搜索方向定义为，并使得第第二二步步()(1)()(1)(1)(1)1()(1)1(1)(1),kkkkkkkkkkkkPAPrAPPAPrAPPAP0()()()()()().minkkkkkkkkxPF xPF xP：已知迭代点和搜索方向，确定搜索步长即求解第第三三步步2()()()()()()(,)(,mi)2nkkkkkF xAxbPAPP2()()()()()m()(,)(n)2i,kkkkkF xrPAPP(

21、)()()()(,)(,)kkkkkrPAPP利用极值的必要条件，可得利用极值的必要条件，可得因为每一个共轭方向都依赖于迭代点处因为每一个共轭方向都依赖于迭代点处的负梯度，故称之为共轭梯度法的负梯度，故称之为共轭梯度法.第15页，共18页。*x等值线等值线当接近最优解时，收敛很慢！图示：图示：共轭梯度法的搜索方向共轭梯度法的搜索方向(0)(0)x x(2)(2)x x(1)(1)x x*x(0)(0)x x(1)(1)x x(2)(2)x x克服了最速下降法的锯齿现象!(0)(0)P P(1)(1)P P(2)(2)P P(3)(3)x x(3)(3)x x(0)(0)r r(1)(1)r r

22、(2 2)r r第16页，共18页。共轭梯度法算法步骤：共轭梯度法算法步骤：(0)(0)(0)(0)(1)()()()()(1)()()(1)(1)1.,0,02.(),|()|,()min().4.(),|()|nkkkkkkkkkkkkkxRkPf xf xxF xPF xPxxPf xf x 给定初始点允许误差令。计算若，.3.求最优步长和使得 令计算若，.5.构造共轭迭迭代代终终止止迭迭代代终终止止()(1)(1)(1)()()(),()(),:1,3.(,)kkkkkkkkkAPf xPf xPkkAPP 方向.令令转第17页，共18页。1.1.假设假设在计算过程中在计算过程中没有误差没有误差，则，则至多用至多用n n步步就能得到方程组的准确解，即就能得到方程组的准确解，即具有二具有二次终止性次终止性2.2.克服了最速下降法的锯齿现象克服了最速下降法的锯齿现象，一种有效的算法，一种有效的算法.3.3.算法简单，易于编程，无需计算二阶导数，存储空间小等优点算法简单，易于编程，无需计算二阶导数，存储空间小等优点优点：优点：第18页，共18页。