数值分析(09)解线性方程组的极小化方法

数值分析数值分析第六节极小化方法一、线性方程组的等价问题三、共轭斜量法四、预条件共轭斜量法二、最速下降法数值分析数值分析一、线性方程组的等价问题12121(),(,,...,),(,,...,)nnTTijnnAAxbAaRxxxxbbbb设对称正定，求解的线性方程组为（）其中111(,)(,)2nnnnnijijiiijiRRxAxxbxaxxbx对应的二次函数:，称为模函数，定义为11()=（）22221212124,10(64)(410bxxxxxxx12设A=261()=例2：）数值分析数值分析13nxRxxAxbr有如下性质：（）对一切，有()=grad()=-（）11,1,2,...,()nijjiijiTnaxbrinxgradxAxbrxx证：221212124,10(64)(410Abxxxxxxx12设=261()例=2：）221212111062,42rxxxrxxx111nnnijijiiijixaxxbx1()2数值分析数值分析22,,1()((),)(,)21(,)(,)(,)(,)(,)22()(,)(,)42nxyRRxyAxyxybxyAxxbxAxybyAyyxAxbyAyy（2）对一切（）(,)(,)xAxxbx1()=2数值分析数值分析********,11()()(,)(,)(,)2211(,)(,)(,)221((),)52nxRxxAxxbxAxxAxxAxxAxxAxxxx对一切有（）*1*1**11()(,)(,)22xAbAxbxbAbAxx（3）设=为的解,则****(,)(,)xAxxbx1()=2数值分析数值分析*1**1*()()min()nxRAxAbAxbxxxAbxx设对称正定，则=为解的充分必要条件是：是二次函数的极小值点，即=定理3-17：*1***()()0()()()nxAbAxxxxxRxx必要性：设=，由上式及的正定性，所以有证，，即使达明：到最小。***1()()((),)2xxAxxxx****()()xxxxxAxbxAxb充分性：若使取极小值，则有grad=-=0，即是方程组的解。xxx()=grad()=A-b数值分析数值分析()()()()min()kkxxxx求二次函数极小值点的一般方法是：构造一个向量序列，使(0)(1)()()()(12,(0,1,...)kkkkkkxxxpk可以采取以下方法：）任取一个初始向量，（）构造迭代格式其中p是搜索方向，是搜索步长，()(1)()()()()*()()()()()min()nkkkkkkkkxRxxpxxxx（3）选择p和使得则当k时，有数值分析数值分析()(1)(4)kkxxx(k)(k)给出误差限，直到或rb-A迭代终止。数值分析数值分析(1)()()(),(0,1,...)kkkkkkxxpk对迭代格式关键是要确定搜索方向p和搜索步长。()()()kkkxxx（1）确定搜索方向p最速下降法：p取为模函数()减少最快的方向，即:()的负梯度方向-grad(()).共轭斜量法：取A-共轭方向p。(1)()()()()()(1)()()min()()kkkkkkkkkkxxpxpx（2）确定搜索步长确定使得从k步到k+1步是最优的，即：这称为沿p方向的一维极小搜索。是局部极小。数值分析数值分析()(1)()()()()()()()()()()()1((),)(,)2kkkkkkkkkkpFxxpAxpxpbxp对确定的搜索方向，构造一个的函数()()()()()()2()()2()()()()()2()()()()()1(,)(,)(,)(,)2(,)2()(,)(,)2()(,)(,)2kkkkkkkkkkkkkkkkkkAxxbxAxpbpAppxAxbpAppxrpApp()()()()'()0,(,)(,)0kkkkFrpApp令即：数值分析数值分析()()()()()()(,)(,)kkkkkkkkkrpxpApp取，是()下降的极小值点，即是kk+1步的最优步长。()()()()(,)(,)kkkkrpApp得()()''()(,)0,()kkFAppA正定()()()()'()(,)(,)kkkkFrpApp数值分析数值分析二、最速下降法).()(,)(,,,)()()(,)()0()0()0()0(xxxxnAxxxxx负梯度方向球面的这就是正交于椭减小最快的方向出发先找一个使从维空间的一个椭球面它是正定因为的等值面是的极小点出发寻找从xxxpxr(k)(k)(k)取模函数()减少最快的方向，即:()的负梯度方向-grad(())，-grad(())=最速下降法：p(k)数值分析数值分析clear;x=-18:0.5:18;y=x';X=ones(size(y))*x;Y=y*ones(size(x));Z=0.5*(X.^2+6*Y.^2+4*X.*Y)-(4*X+10*Y);meshc(Z);colormap(hot)xlabel('x'),ylabel('y'),zlabel('z')*x221212124,10(64)(4102*min*1bxxxxxxxxxx12例：设A=261()=）2()=()=-9,数值分析数值分析(0)()()()()()()(1)()()(1)()0,1,2,....(,)(,)(3)nkkkkkkkkkkkkkxRkrbAxrrArrxxrxx最速下降算法：(1)选取(2)对当时，终止迭代。(1)()06kkrr不难验证，相邻两次的搜索方向是正交的，即（，）（）()()()()(,)(,)kkkkrpApp得数值分析数值分析()1()(0)11112***,(,)kkknAAnnAxxxAbxxxxuAuu(k)k容易看到，()是单调下降有界序列，它存在极限，可以证明lim而且其中分别是对称正定阵A的最大、最小特征值，1()nkr当时，收敛是很慢的，当很小时，因舍入误差的影响，计算将出现不稳定现象。数值分析数值分析三、共轭斜量法(CG)(0)(1)(1)()()()()min()kkkkkpppxpxp设按方向,,...,已进行k次一维搜索，求得，下一步就是确定，再求解一维极小化问题()()()()(,)7(,)kkkkkrpApp可得（）(1)()()(1)(1)()()(8)(9)kkkkkkkkkxxprbAxrAp下一个近似解和对应的剩余向量是(0)(1)(0)(1)()01kkkxxppp不失一般性地设=0，反复利用（8）有+...+数值分析数值分析(0)(1)pp现在考虑,,...取什么方向(0)(0)()kprp设=，一般k1时的确定，我们不但希望使(1)()()()min()(10)kkkxxp(0)()()(1),...,()min()(11)kkkxspanpppxx而且希望的选择使(0)()()(0)(1),...,,,...,,kkkxspanppxypyspanppR若，可记成()()2()()()(,)()()()(,)(,)(12)2kkkkkxypybpAypApp所以有,y为了把极小化问题分离为对和对分别求极小令数值分析数值分析()(0)(1)()(),)0,,...,,)0,0,1,...,1kkjkAypyspanppAppjk令（即（()(0)()()(),...,,)0,klijpppAppijnn如果k=1,2,...，每步都如此选择，则它们符合下面定义.A对称正定，若R中向量组满足（则称它为R中的一个A共轭向量组，或称A正交定义3-3向量组。1、当ln时，不含零向量的A共轭向量组线性无关；2、当A=I时，A共轭性质就是一般的正交性；3、给了一组线性无关的向量，可以按Schmidt正交化的方法得到对应的A共注：轭向量组。数值分析数值分析将极小问题（11）分离为两个极小问题:(0)(1)(0)(1)()(),...,,,...()min()(11)kkkyspanppppxxy取是A共轭的，设已是前一步极小问题的解，即(0)()(1),...,()min()kkxspanppxx2()()()()()()()(,)(,)2kkkkxypybpApp由（12），()()(0)(1),)0,,...,kkkpAypyspanpp而使（(0)()(0)(1)(),,...,2()()(),...,min()min()min()min(,)(,)2kkkyxspanppkkkyspanppxypyAppbp数值分析数值分析()(0)(1)()(),...,,)0,kkkkxspanppAxp,故（()()()()(,),(,)kkkkkbpxApp第一问题的解为第二问题的解为。()()()()()()()()()()()()(,)(,)(,)(,)(,)7(,)(,)kkkkkkkkkkkkkbpbAxprpbprpAppApp与（）相同数值分析数值分析():kp计算(0)(0)()(0)(1)()()(1)()()(1)1,...,(13)kkkkkkkkkprpppAprpprp取=，就取为与共轭的向量，这样的向量不是唯一的，CG法中取为与的线性组合，设()(1)()(1)(1)1()(1)(1)(1)1()(1)1(1)(1)(,)(,)(,)(,)0(,)(14)(,)kkkkkkkkkkkkkkkkpAprpAprAppAprAppAp利用，可得()kpA可以证明这样得到的向量序列是一个共轭向量组.数值分析数值分析公式化简()()(1)()()()()(1)()()()()()(,)7(,)kkkkkkkkkkkkkkkkrprrApApprprpApp由（9）式和（）有（，）（，）（，）=0()()()()(1)()()115kkkkkkkkrprrprr（，）（，）（，）（）()()()()()()()()()(,)(,)716(,)(,)00.kkkkkkkkkkkrprrAppAppr代回（）有（）当时，()()()()()()()(,)0,(,)(,)0,ijijijkrrijApppApijpA由（7）——（16）定义的算法有如下性质（1）。即剩余向量构成一个正定理3-1交向量组。（2）。即为一个8共轭向量组。数值分析数值分析00用归纳法。由（9）及，的证明：表达式有(0)(1)(0)(0)(0)0(0)(0)(0)(0)0rrrrrrrrr（，）（，-A）=（，）-（，A）=0(1)(0)