计算方法 5 解线性方程组的迭代法

11()()xIAxbAxbMNxbMxNxbxMNxMb方程组：第五章解线性代数方程组的迭代法–适用于求解大型稀疏方程组的解解线性代数方程组：,nnnARbRAxb其中，矩阵,.(0)()()**{},.给定一初始向量，按照一定的计算格式，构造一个向量序列当时，使是的解kkxxxxxAxb迭代法的基本思想：需考虑如下几个问题：1.如何选取初始向量？初始向量任选.2.如何构造迭代序列？3.迭代序列是否收敛？在什么条件下收敛？4.若收敛，收敛速度如何？并给出定量的刻画.5.讨论近似解的误差估计.1.Jacobi迭代法BfBf同解构造AxbxBxf可统一地表示成即：①②简单迭代法的基本思想:是构造不动点方程，以求得近似根。1,1,,.niijjijxBxfxbxfin构造迭代格式(0)(1)()(1)()1,,0,1,1,,.任取初始向量给出迭代格式nkkkkiijjijxxBxfxbxfkin此迭代格式称为Jacobi迭代格式（或简单迭代法），称B为Jacobi迭代矩阵.迭代格式的收敛性()()*{},lim..若由迭代格式产生的向量序列收敛即则，否则kkkxxx称迭代格式收敛称为发散***(1)*()*.,0,1,假设为方程组的精确解，即再与迭代格式相减，得kkxxBxfxxBxxk2(1)*1(0)*kkBxxBxx于是(1)*1(0)*00kkxxBxx10kB1()B可证明：lim0kkB1.各分量的计算顺序无关。2.迭代格式仅有前后两步有关。3.新的近似解是已知近似解的线性函数。(0)()1fxB对任意右端项和初始向量，迭代格式收敛.定理1.1.收敛速度的定量刻画*()*()(1)()*(1)(0)||||1||||||||||||1||||||||||||||||1||||kkkkkBxBxxxxBBxxxxB若，则迭代格式收敛于问题的解，且有误差估计的前或的定理1.2.（误差事后估计）（误差事估计）()||||BB根据系数矩阵的特点，给出判断收敛的几个常用条件：1.若A是严格对角占优阵，则Jacobi迭代收敛.2.若A是对称正定阵，2D-A也是对称正定阵，则Jacobi迭代格式收敛.若A是对称正定阵，2D-A是非对称正定阵，则Jacobi迭代格式不收敛.2.Gauss-Seidel迭代法–可看作Jacobi迭代的一种改进T(0)(0)(0)1,,,任取初始向量和Jacobi迭代格式nxxx(1)(0)(0)(0)1122(1)(0)(0)(0)1122(1)(0)(0)(0)1122(1)(0)(0)(0)(0)112211111122222333331nnnnnnnnnnnnnnnnxbxbxbxfxbxbxbxfxbxbxbxfxbxbxbxbxf(1)()(1)()11,,.0,1,，nkkkkiijjijxbxfxBxfink(1)(0)*111(1)(0)11.假设迭代格式收敛，则比更接近第二行：xxxxx类似地进行下去(1)(0)(0)(0)1122(1)()(0)(0)1122(1)()()()(0)11211111222221112111nnnnnnnnnnnnnnxbxbxbxfxbxbxbxfxbxbxbxbxf11;0kk得到迭代格式！构造迭代格式(1)x(1)()()()1122(1)(1)()()1122(1)(1)(1)()()112231111122222333332(1(113)1kkkknnkkkknnkkkkknnkknnxbxbxbxfxbxbxbxfxbxbxbxbxfxbx)(1)(1)()2211kkknnnnnnnnbxbxbxf矩阵格式：B=L+U,方程组x=Bx+fx=Lx+Ux+b(1)(1)()kkkxLxUxf(1)(1)()(1)()(1)1()1()()()kkkkkkkxLxUxfILxUxfxILUxILf此迭代格式称为Gauss-Seidel迭代格式。注意到，这表明：Gauss-Seidel迭代实际上是Jacobi迭代!上面的迭代矩阵被称为G-S迭代法的迭代矩阵.迭代格式的收敛性(1)(1)()(1)()(1)1()1()()()kkkkkkkDxLxUxbDLxUxbxDLUxDLb若方程组为：Ax=b.则令A=D-L-U,于是(0)11()1,()().fxGGILUGDLU对任意右端项和初始向量，迭代格式收敛其中或者定理2.1.*||||1.-G-SGx若，则迭代格式收敛于问题的解当使用范数时，迭代法比Jacobi迭代法收敛得快些.定理2.2.根据系数矩阵的特点，给出判断收敛的几个常用条件：1.若A是严格对角占优阵，则G-S迭代收敛.2.若A是对称正定阵，则G-S迭代格式收敛.3.SOR迭代法–解大型稀疏矩阵方程组的有效方法(1)1(1)1()1(1)()(1)()G-S,=+kkkkkkkxDLxDUxDbxxxxxx迭代格式为:令则有(1)(),=+kkxxx若在“修正项”的前面加一个参数则得到SOR法的计算格式(1)()kkxxx可看成在上加“修正项”而得到！()(+1)()()(+1)()1(1)1()1=+-=1-+=1-+kkkkkkkkxxxxxxDLxDUxDb解得(+1)()()=1-+kkDLxDUxb(+1)1()1=()1-()kkxDLDUxDLb011称为，称的迭代为；称的迭代为低松松弛法弛因子超松弛法.Bf构造迭代格式Ax=b,其中A=D-L-U.迭代格式的收敛性(0)*()1.||||.1fxGGx对任意右端项和初始向量，迭代格式收敛若，则迭代格式收敛于问题的解定理3.0.根据系数矩阵的特点，给出判断收敛的几个常用条件：1.若A是对称正定阵，则SOR迭代格式对是收敛的.2.若A是严格对角占优的，且松弛因子，则SOR收敛.02.SOR迭代格式收敛的必要条件是满足：定理3.1.02014.最速下降法与共轭梯度法–解对称正定线性方程组的方法最速下降法与共轭梯度法，是求最优化问题的重要方法.在此，使用它们解线性方程组。途径：求解线性方程组问题等价地转化成求极值问题！1()(,)(,)2FxAxxbx考察二次函数：的极小值问题.=Axb线性方程组：和之间的关系**1min()(,)(,).2nxRAxFxAxxbxxAxb是极值问题的解是的解设为对称正定矩阵，则下列两个问题.1等4价定理***()(),()()=0()=0()FxxFxxFxx若于取极小值，则于取极小值；，若于取极小值，则于取极小值.设引理反之求极小值的数值方法：(0)xP(1)(0)0(1)(0)P()()xxfxfx使得*x如此不断地修正下去初始点两个关键步骤：1.如何选取搜索方向P？2.如何确定搜索步长λ？1)最速下降法或梯度法最速下降法：每步选择的搜索方向P都是F(x)的负梯度方向！1()(,)(,)2122dFxAxxbxdxAxbbAxrbAx记为=如何选择搜索方向？()kFx()kFx函数值下降最快的方向函数值增加最快的方向函数值下降区域kx函数值上升区域r几个常用的梯度公式1.f(x)=C（常数）,则▽f(x)=0。2.f(x)=bTx,则▽f(x)=b；3.▽(xTx)=2x;4.若A是实对称方阵,则有▽(xTAx)=2Ax；1847年,Cauchy提出最速下降法的迭代公式推导：(0)(0)(0)(0)(0)(0)(1)(0)(0)0(1)(0)(0)(0)(0)0,()()()min()min()xFxxrbAxxrxxrFxFxrFxr选取初始点计算在点的负梯度=，在直线上寻求一点，使得利用极值的必要条件，我们有2(0)(0)(0)(0)(0)()()(,)(,)2ddFxAxbrArrdd2(0)(0)(0)(0)(0)()()(,)(,)2FxAxbrArr2(0)(0)(0)(0)(0)()(,)(,)2dFxrrArrd(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()ddFxrFxrr前后两步迭代的搜索方向是相互正交的!重复上述过程，可得最速下降法计算公式：()()kkrbAx=()()()()(,)(,)kkkkkrrArr(1)()()kkkkxxr梯度法算法步骤：(0)1.,0,0nxRk给定初始点允许误差令。()()2.();kkrFx计算搜索方向()()3.||||,kkkrx若则，为所求极值点；否则，求最优步长停止计算()()()()()min().kkkkkFxrFxr使得(1)()()4.,:1,2kkkkxxrkk令令转。锯齿现象(0)x*x等高线最速下降法具有算法简单，对初始点没有特别要求，具有全局收敛性，但收敛速度不理想（其收敛速度是线性的）.注：最速下降方向反映了F(x)在点xk处的局部性质，即它只是F(x)局部下降最快的方向.但从整体上看下降路径却经历了不少弯路（折线），因此使收敛速度大大减慢！当接近最优解时，收敛很慢！(0)(0)(0)(0)(0)dd0()ddFxrFxrr=0(0)r(1)r(2)r(1)x(2)x2)共轭梯度法()(1)kkPP把和相结合，利用已知迭代点处的梯度方向构造一组共轭方向，.共轭性最速下降方即前后两步的搜索方向、是A-正交的向定义共轭。关于和，则称若有AddAddT21210，和中的两个非零向量的对称正定矩阵，对于是设21ddRnnAn如何选择搜索方向？注：002121dddIdTT21ddA-共轭是正交的推广.是单位矩阵，则如果A共轭梯度法的迭代公式推导：：与最速下降法相同，即第一步(0)(0)(0)PrbAx=(0)(0)0(0)(0)(,)(,)PPAPP(1)(0)(0)0xxP以共轭方向作为搜索方向1952年,Hesteness和Stiefel为了解线性方程组而提出的()()()()()()()(1)11(),0,=,,0.kkkkkkkkkkPrPxrrbAxPAP：设已求得点若令则下一个搜索方向定义为，并使得第二步()(1)()(1)(1)(1)1()(1)1(1)(1),,,,,kkkkkkkkkkkkPAPrAPPAPrAPPAP0()()()()()().minkkkkkkkkxPFxPFxP：已知迭代点和搜索方向，确定搜索步长即求解第三步2()()()()()()(,)(,mi)2nkkkkkFxAxbPAPP2()