工程数学(10)解线性方程组的极小化方法

1、工程数学工程数学工程数学工程数学第六节第六节 极小化方法极小化方法一、与线性方程组等价的变分问题一、与线性方程组等价的变分问题三、共轭斜量法三、共轭斜量法(共轭梯度法共轭梯度法)四、预条件共轭斜量法四、预条件共轭斜量法二、最速下降法二、最速下降法工程数学工程数学工程数学工程数学一、与线性方程组等价的变分问题一、与线性方程组等价的变分问题12121(),(,.,) ,(,.,)n nTTijnnAAxbAaRxxxxbb bb 设设对对称称正正定定，求求解解的的线线性性方方程程组组为为（ ）其其中中111(,)( ,)2n nnnnijijiiijiRRxAx xb xa x xb x 对对应应

2、的的二二次次函函数数 : : ，称称为为模模函函数数，定定义义为为1 11 1 ( ( ) )= =（ ）2 22 2221212124,10(64)(410bxxxxxxx 1 12 2设设 A A = =2 26 61 1( ( ) )= =例例2 2：）工程数学工程数学工程数学工程数学13nxRxxAx br 有有如如下下性性质质：（ ）对对一一切切，有有( ( ) )= =g gr ra ad d ( ( ) )= =- -（ ）11,1,2,.,( )nijjiijiTna xbrinxgradxAxbrxx 证证：221212124,10(64)(410Abxxxx xxx 1 1

3、2 2设设 = =2 26 61 1( ( ) )例例= =2 2：）221212111062,42rxxxrxxx 111nnnijijiiijixa x xb x 1 1( () )2 2工程数学工程数学工程数学工程数学22,1()(),)( ,)21(,)( ,)(,)( ,)(,)22( )(,)(,)42nx yRRxyA xyxyb xyAx xb xAx yb yAy yxAxb yAy y （2 2）对对一一切切（ ）(,)( ,)xAx xb x 1 1( ( ) )= =2 2工程数学工程数学工程数学工程数学*,11( )()(,)( ,)(,)2211(,)(,)(,)2

4、21(),)52nxRxxAx xb xAxxAx xAxxAxxA xxxx 对对一一切切有有（ ）*1*1*11()( ,)(,)22xA bAxbxb A bAxx （3 3）设设= =为为的的解解, ,则则*(,)( ,)xAxxb x 1 1( () )= =2 2工程数学工程数学工程数学工程数学*1*1*( )()min( )nxRAxA bAxbxxxA bxx 设设 对对称称正正定定，则则= =为为解解的的充充分分必必要要条条件件是是：是是二二次次函函数数的的极极小小值值点点，即即= =定定理理：*1*( )()0()( )( )nxA bAxxxxxRxx 必必要要性性：设设

5、= =，由由上上式式及及 的的正正定定性性，所所以以有有证证，即即使使达达明明：到到最最小小。*1( )()(),)2xxA xxxx*()()xxxxxAxbxAxb 充充 分分 性性 ： 若若使使取取 极极 小小 值值 ， 则则 有有g gr ra ad d= =- - = =0 0，即即是是 方方 程程 组组的的 解解 。xxx ( )=grad ( )=A -b工程数学工程数学工程数学工程数学 ()()( )()min( )kkxxxx 求求二二次次函函数数极极小小值值点点的的一一般般方方法法是是：构构造造一一个个向向量量序序列列，使使(0)(1)()()()(12,(0,1,.)kk

6、kkkkxxxpk 可可以以采采取取以以下下方方法法：）任任取取一一个个初初始始向向量量，（ ）构构造造迭迭代代格格式式其其中中p p是是搜搜索索方方向向，是是搜搜索索步步长长，( )(1)( )( )( )( )*()()()()()min ( )nkkkkkkkkx Rxxpxxxx （3 3）选选择择p p和和使使得得则则当当k k时时，有有工程数学工程数学工程数学工程数学( )(1)(4)kkxxx (k)(k)(k)(k)给给出出误误差差限限 ，直直到到 或 或 rb-Arb-A迭迭代代终终止止。工程数学工程数学工程数学工程数学(1)()()(),(0,1,.)kkkkkkxxpk

7、对对迭迭代代格格式式关关键键是是要要确确定定搜搜索索方方向向p p和和搜搜索索步步长长。()()()kkkxxx （1 1）确确定定搜搜索索方方向向p p最最速速下下降降法法：p p取取为为模模函函数数( ( ) )减减少少最最快快的的方方向向，即即: : ( ( ) )的的负负梯梯度度方方向向- - g gr ra ad d( ( ( ( ) ) ). .共共轭轭斜斜量量法法：取取A A - - 共共轭轭方方向向p p。(1)( )( )( )( )( )(1)()()min ()()kkkkkkkkkkxxpxpx （2 2）确确定定搜搜索索步步长长确确定定使使得得从从k k步步到到k+1

8、k+1步步是是最最优优的的，即即：这这称称为为沿沿p p方方向向的的一一维维极极小小搜搜索索。是是局局部部极极小小。工程数学工程数学工程数学工程数学( )(1)( )( )( )( )( )( )( )( )( )()()1( (),)( ,)2kkkkkkkkkkpFxxpA xpxpb xp 对对确确定定的的搜搜索索方方向向，构构造造一一个个 的的函函数数()()()()()()2()()2()()()()()2()()()()()1(,)( ,)(,)( ,)2(,)2()(,)(,)2()(,)(,)2kkkkkkkkkkkkkkkkkkAxxb xAxpb pAppxAxb pApp

9、xrpApp ()()()()()0,(,)(,)0kkkkFrpApp 令令即即：工程数学工程数学工程数学工程数学()()()()()()(,)(,)kkkkkkkkkrpxpApp 取取，是是 ( () )下下降降的的极极小小值值点点，即即是是k kk k+ +1 1步步的的最最优优步步长长。( )( )( )( )(,)(,)kkkkrpApp 得得()()()(,)0,()kkFAppA 正正定定()()()()()(,)(,)kkkkFrpApp 工程数学工程数学工程数学工程数学二、最速下降法二、最速下降法).()(,)(,)()()(,)()0()0()0()0(xxxxnAxxx

10、xx 负梯度方向负梯度方向球面的球面的这就是正交于椭这就是正交于椭减小最快的方向减小最快的方向出发先找一个使出发先找一个使从从维空间的一个椭球面维空间的一个椭球面它是它是正定正定因为因为的等值面的等值面是是的极小点的极小点出发寻找出发寻找从从xxxpxr ( (k k) )( (k k) )( (k k) )取取 模模 函函 数数( ( ) )减减 少少 最最 快快 的的 方方 向向 ，即即 : : ( ( ) )的的 负负 梯梯 度度 方方 向向 - - g gr ra ad d( ( ( ( ) ) )，- - g gr ra ad d( ( ( () ) )= =最最 速速 下下 降降

11、法法 ：p( (k 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) *x221212124,10(64)(4102*m in*1bxxxx xxxxxx 1 12 2例例 ： 设设 A A= =2 26 61 1( () )= =）2 2( () )= =( () )= =- -9 9, ,工程数学工程数学工程数学

12、工程数学(0)()()()()()()(1)()()(1)()0,1,2,.(,)(,)(3)nkkkkkkkkkkkkkxRkrbAxrrArrxxrxx 最最速速下下降降算算法法：( (1 1) )选选取取( (2 2) )对对当当时时，终终止止迭迭代代。(1)()06kkrr 不不难难验验证证，相相邻邻两两次次的的搜搜索索方方向向是是正正交交的的，即即（，）（ ）( )( )( )( )(,)(,)kkkkrpApp得工程数学工程数学工程数学工程数学 ()1()(0)11112*,(,)kkknAAnnAxxxA bxxxxuAu u ( (k k) )k k容容易易看看到到， ( ()

13、 ) 是是单单调调下下降降有有界界序序列列，它它存存在在极极限限，可可以以证证明明l li im m而而且且其其中中分分别别是是对对称称正正定定阵阵A A的的最最大大、最最小小特特征征值值，1( )nkr当当时时，收收敛敛是是很很慢慢的的，当当很很小小时时，因因舍舍入入误误差差的的影影响响，计计算算将将出出现现不不稳稳定定现现象象。工程数学工程数学工程数学工程数学三、共轭斜量法三、共轭斜量法 (CG) (共轭梯度法共轭梯度法) (0)(1)(1)()()()()min()kkkkkpppxpxp 设设按按方方向向, , , . . . . . . , ,已已进进行行k k次次一一维维搜搜索索，

14、求求得得，下下一一步步就就是是确确定定，再再求求解解一一维维极极小小化化问问题题()()()()(,)7(,)kkkkkrpApp 可可得得（ ）(1)( )( )(1)(1)( )( )(8)(9)kkkkkkkkkxxprbAxrAp 下下一一个个近近似似解解和和对对应应的的剩剩余余向向量量是是(0)(1)(0)(1)( )01kkkxxppp 不不失失一一般般性性地地设设=0=0，反反复复利利用用（8 8）有有+.+.+工程数学工程数学工程数学工程数学(0)(1)pp现现在在考考虑虑, . . . 取, . . . 取什什么么方方向向(0)(0)( )kprp 设设= =，一一般般k1k

15、1时时的的确确定定，我我们们不不但但希希望望使使(1)( )( )()min ()(10)kkkxxp (0)()( )(1),.,()min( )(11)kkkx span pppxx 而而且且希希望望的的选选择择使使 (0)( )( )(0)(1),.,.,kkkxspan ppxypyspan ppR 若若，可可记记成成( )( )2( )( )( )(,)( )()( )( ,)(,)(12)2kkkkkxypyb pAy pApp 所所以以有有,y 为为了了把把极极小小化化问问题题分分离离为为对对 和和对对分分别别求求极极小小 令令工程数学工程数学工程数学工程数学 ( )(0)(1)

16、( )( ),)0,.,)0,0,1,.,1kkjkAy pyspan ppAppjk 令令（即即（ ( )(0)( )( )( ),.,)0,klijpppAppijn nn n如如果果k=1,2,.k=1,2,.，每每步步都都如如此此选选择择，则则它它们们符符合合下下面面定定义义. .A A对对称称正正定定，若若R R 中中向向量量组组满满足足（则则称称它它为为R R 中中的的一一个个A A共共轭轭向向量量组组，或或称称A A定定义义正正交交向向量量组组。 1 1、当当lnln时时，不不含含零零向向量量的的A A共共轭轭向向量量组组线线性性无无关关；2 2、当当A=IA=I时时，A A共共

17、轭轭性性质质就就是是一一般般的的正正交交性性；3 3、给给了了一一组组线线性性无无关关的的向向量量，可可以以按按SchmidtSchmidt正正交交化化的的方方法法得得到到对对应应的的A A共共注注：轭轭向向量量组组。工程数学工程数学工程数学工程数学将将极极小小问问题题（1111）分分离离为为两两个个极极小小问问题题: : (0)(1)(0)(1)( )( ),.,.()min( )(11)kkky span ppppxxy 取取是是A A共共轭轭的的，设设已已是是前前一一步步极极小小问问题题的的解解，即即 (0)( )(1),.,()min( )kkx span ppxx 2( )( )(

18、)( )( )()( )( ,)(,)2kkkkxypyb pApp 由由（1 12 2）， ( )( )(0)(1),)0,.,kkkpAy pyspan pp 而而使使（ (0)()(0)(1)( ),.,2( )( )( ),.,min( )min ()min( )min(,)( ,)2kkkyx span ppkkky span ppxypyAppb p 工程数学工程数学工程数学工程数学 ( )(0)(1)( )( ),.,)0,kkkkxspan ppAxp , ,故故（( )( )( )( )( ,),(,)kkkkkb pxApp第第一一问问题题的的解解为为第第二二问问题题的的解

19、解为为。( )( )( )( )( )( )( )( )( )( )( )( )( ,)(,)(,)( ,)(,)7(,)(,)kkkkkkkkkkkkkb pbAxprpb prpAppApp与与（ ）相相同同工程数学工程数学工程数学工程数学( ):kp计计算算(0)(0)( )(0)(1)( )( )(1)( )( )(1)1,.,(13)kkkkkkkkkprpppAprpprp 取取= =，就就取取为为与与共共轭轭的的向向量量，这这样样的的向向量量不不是是唯唯一一的的，CGCG法法中中取取为为与与的的线线性性组组合合，设设( )(1)( )(1)(1)1( )(1)(1)(1)1( )

20、(1)1(1)(1)(,)(,)(,)(,)0(,)(14)(,)kkkkkkkkkkkkkkkkpAprpAprAppAprAppAp 利利用用，可可得得 ( )kpA 可可以以证证明明这这样样得得到到的的向向量量序序列列是是一一个个共共轭轭向向量量组组. .工程数学工程数学工程数学工程数学公式化简公式化简( )( )(1)( )( )( )( )(1)( )( )( )( )( )(,)7(,)kkkkkkkkkkkkkkkkrprrApApprprpApp 由由（9 9）式式和和（ ）有有（，）（，）（，）=0=0( )( )( )( )(1)( )( )115kkkkkkkkrprrp

21、rr （，）（，）（，）（ ）()()()()()()()()()(,)(,)716(,)(,)00.kkkkkkkkkkkrprrAppAppr 代代回回（ ）有有（）当当时时， ( )( )( )( )( )( )()(,)0,(,)(,)0,ijijijkrrijApppApijpA 由由（7 7）（1 16 6）定定义义的的算算法法有有如如下下性性质质（1 1）。即即剩剩余余向向量量构构成成一一个个正正交交向向量量组组。（2 2）。即即为为一一个个共共轭轭定定理理向向量量组组。工程数学工程数学工程数学工程数学公式化简公式化简(1)1( )(1)(1)( )( )( )( )( )(,(

22、)(,)(,)(,)kkkkkkkkkkkrrrrAppAppAp 1(1)(1)(1)(1)( )( )( )( )(,)(,)(,)(,)kkkkkkkkkrrrrpAprr (1)00.kkr 当当时时，工程数学工程数学工程数学工程数学(0)()(0)(0)(0)(0)()()()()(1)()()(1)()()(1)(1)()()(1)(1)():(1)(2),(3)0,1,.,(,)(,)(,)(,)nkkkkkkkkkkkkkkkkkkkkkkCGxRrbAxprkrrAppxxprrAprrrrprp 算算法法，()*.kxx (k)(k)(k)在计算过程中，若遇r=0，或(p,

23、Ap)=0时，计算终止,工程数学工程数学工程数学工程数学()*.kxx n n( (0 0) )( (1 1) )( (n n) )( (k k) )( (1 1) ) 剩剩余余向向量量相相互互正正交交，而而R R 中中至至多多有有n n个个相相互互正正交交的的非非零零向向量量，所所以以r r, ,r r, ,. . . ., ,r r 中中至至少少有有一一个个向向量量为为零零。若若r r= =0 0，则则注注：()(0).nxx ( (0 0) )( (1 1) )( (n n- -1 1) )( (2 2) )实实际际计计算算中中，由由于于舍舍入入误误差差的的影影响响，n n步步内内得得不

24、不到到准准确确解解，故故还还需需继继续续迭迭代代。一一般般因因p p, ,p p, ,. . . ., ,p p是是一一组组A A- -共共轭轭向向量量组组，继继续续迭迭代代时时，要要取取2()(0)2()1*2*()1kkAAcond Axxxxcond A ( (3 3) )由由误误差差估估计计式式当当A A的的条条件件数数很很小小时时，共共轭轭斜斜量量法法收收敛敛很很快快，但但当当A A是是病病态态严严重重的的矩矩阵阵时时，共共轭轭斜斜量量法法收收敛敛速速度度很很慢慢。可可采采用用预预处处理理技技术术，降降低低A A的的条条件件数数。工程数学工程数学工程数学工程数学四、预条件共轭斜量法四

25、、预条件共轭斜量法(PCG)- -1 1- -T T寻寻找找一一个个非非奇奇异异矩矩阵阵C C，使使A A= =C C A AC C 的的条条件件数数比比原原系系数数矩矩阵阵A A的的条条件件数数得得到到改改善善. .1111,TTTTAxbCACC xC bAxbACACbC b xC x其其中中，1TCCxb 2 2令令M M= =称称为为预预优优矩矩阵阵，当当M M接接近近A A时时， A A接接近近单单位位阵阵，c co on nd d( (A A) ) 接接近近 ，对对A A用用共共轭轭斜斜量量法法求求解解，可可达达到到加加速速的的目目的的。1112,( )1TTTTTMCCAACA

26、CCMCC CC CIcond A工程数学工程数学工程数学工程数学11()(0)()(0)(0)(0)(0)()()()()(1)()()(1)()()1,2,(1)(2),(3)0,1,.,(,)(,)TknkkkkkkkkkkkkkACACbCbAxbxxRrbAxprkrrA ppxxprrA p 、计计算算、解解得得，(1)(1)()()(1)(1)()()()(,)(,)3.kkkkkkkkkkkTrrrrprpxCx 、预条件共轭斜量法预条件共轭斜量法 实际计算，可通过变实际计算，可通过变换，转化成用原方程组换，转化成用原方程组的量来计算的量来计算。工程数学工程数学工程数学工程数学(0)()(0)(0)(0)(0)(0)(0)(0)()()