1、第六节第六节 极小化方法极小化方法一、线性方程组的等价问题一、线性方程组的等价问题三、共轭斜量法三、共轭斜量法四、预条件共轭斜量法四、预条件共轭斜量法二、最速下降法二、最速下降法一、一、线性方程组的等价问题线性方程组的等价问题12121(),(,.,),(,.,)n nTTijnnAAxbAaRxxxxbb bb 设设对对称称正正定定，求求解解的的线线性性方方程程组组为为（）其其中中111(,)(,)2n nnnnijijiiijiRRxAx xb xa x xb x 对对应应的的二二次次函函数数:，称称为为模模函函数数，定定义义为为1 11 1 ()=（）2 22 2221212124,10
2、(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 12 2设设 =2 26 61 1()例例=2 2：）221212111062,42rxxxrxxx 111nnnijijiiijixax xb x 1 1()2 222,1()(),)(,)21(,)(,)(,)(,)(,)22()(
3、,)(,)42nx yRRxyA xyxyb xyAx xb xAx yb yAy yxAxb yAy y （2 2）对对一一切切（）(,)(,)xAx xb x 1 1()=2 2*,11()()(,)(,)(,)2211(,)(,)(,)221(),)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 设 对称正定，则=为解的充分必要条件是
4、：是二次函数的极小值点，即=定理3-17：*1*()()0()()()nxA bAxxxxxRxx 必必要要性性：设设=，由由上上式式及及 的的正正定定性性，所所以以有有证证，即即使使达达明明：到到最最小小。*1()()(),)2xxA xxxx*()()xxxxxAxbxAxb 充充 分分 性性：若若使使取取 极极 小小 值值，则则 有有g gr ra ad d=-=0 0，即即是是 方方 程程 组组的的 解解。xxx()=grad()=A-b ()()()()min()kkxxxx 求求二二次次函函数数极极小小值值点点的的一一般般方方法法是是：构构造造一一个个向向量量序序列列，使使(0)(
5、1)()()()(12,(0,1,.)kkkkkkxxxpk 可可以以采采取取以以下下方方法法：）任任取取一一个个初初始始向向量量，（）构构造造迭迭代代格格式式其其中中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 对对迭迭代代格格式式关关键键是是要要确确定
6、定搜搜索索方方向向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 k+1 1步步是是最最优优的的，即即：这这称称为为沿沿p p方方向向的的一一维维极极小小搜搜索索。是是局局部部极极小小。(
7、)(1)()()()()()()()()()()()1(),)(,)2kkkkkkkkkkpFxxpA xpxpb xp 对对确确定定的的搜搜索索方方向向，构构造造一一个个 的的函函数数()()()()()()2()()2()()()()()2()()()()()1(,)(,)(,)(,)2(,)2()(,)(,)2()(,)(,)2kkkkkkkkkkkkkkkkkkAxxb xAxpb pAppxAxb pAppxrpApp ()()()()()0,(,)(,)0kkkkFrpApp 令令即即：()()()()()()(,)(,)kkkkkkkkkrpxpApp 取取，是是()下下降降的的
8、极极小小值值点点，即即是是k kk k+1 1步步的的最最优优步步长长。()()()()(,)(,)kkkkrpApp 得得()()()(,)0,()kkFAppA 正正定定()()()()()(,)(,)kkkkFrpApp 二、最速下降法二、最速下降法).()(,)(,)()()(,)()0()0()0()0(xxxxnAxxxxx 负负梯梯度度方方向向球球面面的的这这就就是是正正交交于于椭椭减减小小最最快快的的方方向向出出发发先先找找一一个个使使从从维维空空间间的的一一个个椭椭球球面面它它是是正正定定因因为为的的等等值值面面是是的的极极小小点点出出发发寻寻找找从从xxxpxr (k k)
9、(k k)(k k)取取 模模 函函 数数()减减 少少 最最 快快 的的 方方 向向，即即:()的的 负负 梯梯 度度 方方 向向-g gr ra ad d()，-g gr ra ad d()=最最 速速 下下 降降 法法：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 x
10、xxxxx 1 12 2例例：设设 A A=2 26 61 1()=）2 2()=()=-9 9,(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容容
11、易易看看到到，()是是单单调调下下降降有有界界序序列列，它它存存在在极极限限，可可以以证证明明l li im m而而且且其其中中分分别别是是对对称称正正定定阵阵A A的的最最大大、最最小小特特征征值值，1()nkr 当当时时，收收敛敛是是很很慢慢的的，当当很很小小时时，因因舍舍入入误误差差的的影影响响，计计算算将将出出现现不不稳稳定定现现象象。三、共轭斜量法三、共轭斜量法(CG)(0)(1)(1)()()()()min()kkkkkpppxpxp 设设按按方方向向,.,已已进进行行k k次次一一维维搜搜索索，求求得得，下下一一步步就就是是确确定定，再再求求解解一一维维极极小小化化问问题题()(
12、)()()(,)7(,)kkkkkrpApp 可可得得（）(1)()()(1)(1)()()(8)(9)kkkkkkkkkxxprbAxrAp 下下一一个个近近似似解解和和对对应应的的剩剩余余向向量量是是(0)(1)(0)(1)()01kkkxxppp 不不失失一一般般性性地地设设=0 0，反反复复利利用用（8 8）有有+.+(0)(1)pp现现在在考考虑虑,.取取什什么么方方向向(0)(0)()kprp 设设=，一一般般k k1 1时时的的确确定定，我我们们不不但但希希望望使使(1)()()()min()(10)kkkxxp (0)()()(1),.,()min()(11)kkkx span
13、 pppxx 而而且且希希望望的的选选择择使使 (0)()()(0)(1),.,.,kkkxspan ppxypyspan ppR 若若，可可记记成成()()2()()()(,)()()()(,)(,)(12)2kkkkkxypyb pAy pApp 所所以以有有,y 为为了了把把极极小小化化问问题题分分离离为为对对 和和对对分分别别求求极极小小 令令 ()(0)(1)()(),)0,.,)0,0,1,.,1kkjkAy pyspan ppAppjk 令令（即即（()(0)()()(),.,)0,klijpppAppij nn如果k=1,2,.，每步都如此选择，则它们符合下面定义.A对称正定，
14、若R 中向量组满足（则称它为R 中的一个A共轭向量组，或称A正交定义3-3向量组。1 1、当当l l n n时时，不不含含零零向向量量的的A A共共轭轭向向量量组组线线性性无无关关；2 2、当当A A=I I时时，A A共共轭轭性性质质就就是是一一般般的的正正交交性性；3 3、给给了了一一组组线线性性无无关关的的向向量量，可可以以按按S Sc ch hm mi id dt t正正交交化化的的方方法法得得到到对对应应的的A A共共注注：轭轭向向量量组组。将将极极小小问问题题（1111）分分离离为为两两个个极极小小问问题题:(0)(1)(0)(1)()(),.,.()min()(11)kkky s
15、pan ppppxxy 取取是是A A共共轭轭的的，设设已已是是前前一一步步极极小小问问题题的的解解，即即 (0)()(1),.,()min()kkx span ppxx 2()()()()()()()(,)(,)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 ,故故（()(
16、)()()(,),(,)kkkkkb pxApp第第一一问问题题的的解解为为第第二二问问题题的的解解为为。()()()()()()()()()()()()(,)(,)(,)(,)(,)7(,)(,)kkkkkkkkkkkkkb pbAxprpb prpAppApp 与与（）相相同同():kp计计算算(0)(0)()(0)(1)()()(1)()()(1)1,.,(13)kkkkkkkkkprpppAprpprp 取取=，就就取取为为与与共共轭轭的的向向量量，这这样样的的向向量量不不是是唯唯一一的的，CGCG法法中中取取为为与与的的线线性性组组合合，设设()(1)()(1)(1)1()(1)(1
17、)(1)1()(1)1(1)(1)(,)(,)(,)(,)0(,)(14)(,)kkkkkkkkkkkkkkkkpAprpAprAppAprAppAp 利利用用，可可得得 ()kpA 可可以以证证明明这这样样得得到到的的向向量量序序列列是是一一个个共共轭轭向向量量组组.公式化简公式化简()()(1)()()()()(1)()()()()()(,)7(,)kkkkkkkkkkkkkkkkrprrApApprprpApp 由由（9 9）式式和和（）有有（，）（，）（，）=0 0()()()()(1)()()115kkkkkkkkrprrprr （，）（，）（，）（）()()()()()()()()
18、()(,)(,)716(,)(,)00.kkkkkkkkkkkrprrAppAppr 代代回回（）有有（）当当时时，()()()()()()()(,)0,(,)(,)0,ijijijkrrijApppApijpA 由（7）（16）定义的算法有如下性质（1）。即剩余向量构成一个正定理3-1交向量组。（2）。即为一个8共轭向量组。00 用用归归纳纳法法。由由（9 9）及及，的的证证明明：表表达达式式有有(0)(1)(0)(0)(0)0(0)(0)(0)(0)0rrrrrrrrr （，）（，-A-A）=（，）-（，A A）=0=0(1)(0)(1)(0)(0)0(1)(0)(0)(0)0(,)(,)
19、(,)(,)0pAprrArrArrAr (0)(0)pr=(0)(1)()(0)(1)()9kkrrrpppA 现现设设，互互相相正正交交，互互相相共共轭轭。则则对对k k+1 1，由由（）有有(1)()()()()()()()()(,)()()()kjkkjkjkjkkrrrAprrrApr ，()(1)1(1)(1)(,)14(,)kkkkkrAppAp （）(1)()()9kkkkrrAp （），()()(1)1(13)kkkkprp ()()()()(,)16(,)kkkkkrrApp （）(1)()()()()()()()()()(,)()()()()0kkkkkkkkkkkkrr
20、rrAprrrApp ，()()()()(1)()()1,(,)(,)(,)kkkkkkkkjkAprApppApp 若若()()()()(1)0 11(,)013kjjjjjkrrrpp j-1j-1若若，由由归归纳纳法法假假设设，有有，再再由由（）有有，=-,=-,得得()(1)1(1)(1)(,)14(,)kkkkkrAppAp （）(1)()()9kkkkrrAp （），()()(1)1(13)kkkkprp ()()()()(,)16(,)kkkkkrrApp （）(1)()()()()()()()()(1)()()()(1)(1)()0,1,.,1(,)(,)()()()(,)0k
21、jkkjkjkkkjjkkjkjkkkjjkrrrAprAprApppAppApprr j j-1 1j j-1 1对对，-，)+，由由归归纳纳法法假假设设就就有有。(1)(1)()(1)()()(1)()()()130kkkkkkkkkkkkppprpprppp 再再看看，由由（），（1414），有有（，A A）（，A A）=（，A A）（，A A）(1)()(1)()()(1)()()()kjkkjkkjkjkpprpprppp j=0,1,.,k-1j=0,1,.,k-1（，A A）（，A A）=（，A A）（，A A）(1)()(1)(kjjrrr -1 1j j=（，-）)=0 0.
22、证证毕毕()(1)1(1)(1)(,)14(,)kkkkkrAppAp （）(1)()()9kkkkrrAp （），()()(1)1(13)kkkkprp ()()()()(,)16(,)kkkkkrrApp （）公式化简公式化简(1)1()(1)(1)()()()()()(,()(,)(,)(,)kkkkkkkkkkkrrrrAppAppAp 1(1)(1)(1)(1)()()()()(,)(,)(,)(,)kkkkkkkkkrrrrpAprr (1)00.kkr 当当时时，(0)()(0)(0)(0)(0)()()()()(1)()()(1)()()(1)(1)()()(1)(1)():(
23、1)(2),(3)0,1,.,(,)(,)(,)(,)nkkkkkkkkkkkkkkkkkkkkkkCGxRrbAxprkrrAppxxprrAprrrrprp 算算法法，()*.kxx(k)(k)(k)在计算过程中，若遇r=0，或(p,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-
24、1 1)(2 2)实实际际计计算算中中，由由于于舍舍入入误误差差的的影影响响，n n步步内内得得不不到到准准确确解解，故故还还需需继继续续迭迭代代。一一般般因因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,()1TTTTTMCCAACACC
26、MCC CC CIcond A11()(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)()()()()
27、(1)()()(1)()()(1)(1)(1)(1)(1)()()(1),(2),(3)0,1,.,(,)(,)(,)(,:)nkkkkkkkkkkkkkkkkkkkkkxRrbAxMzrzpzkzrAppxxprrApzrzrrCGpzP 取取初初值值解解方方程程组组求求出出，令令解解组组算算法法方方程程M M(1)()(1)(1)(4),kkkkkzprx 直直到到输输出出。预优矩阵的选取预优矩阵的选取()1TkMCCMMz(k k)预预优优矩矩阵阵应应满满足足:（）是是对对称称正正定定的的矩矩阵阵；（2 2）方方程程组组=r r容容易易求求解解.下面介绍几种选取预优矩阵的方案下面介绍几种
28、选取预优矩阵的方案:1122(,.,)nnMdiag aaa（1 1）A A是是大大型型稀稀疏疏对对称称正正定定的的矩矩阵阵，取取111221221,1nnn nnnaaaaMaaa （2 2）取取A A的的三三条条对对角角线线构构成成的的三三对对角角阵阵 1/21/21/21/2(2)()(2)()TTTMSSORMCCCDL DCDDL （3 3）取取为为迭迭代代法法的的预预处处理理阵阵，111221221,11122,nnn nnnnnMJacobiAAAAAAAAAAMA （4 4）取取为为块块迭迭代代的的块块对对角角阵阵，500TijijALLRLRLAal（）不不完完全全C hol
29、 esky分C hol esky分解解的的预预优优矩矩阵阵不不完完全全C hol esky分C hol esky分解解就就是是将将A分A分解解成成其其中中 是是下下三三角角阵阵，称称为为剩剩余余矩矩阵阵。与与 有有相相同同的的稀稀疏疏性性，即即若若，。TMLL 取取TALL的的不不完完全全C C h ho ol l e es sk ky y分分解解是是。TALL。3102131001312013A 0032000003200000007321803282183038313RLRLLAT3102131001312013A Cho.ma=3,-1,0,2;-1,3,-1,0;0,-1,3,-1;2
30、,0,-1,3;sa=sparse(a);r=cholinc(sa,0)full(r)MATLAB调用格式调用格式:r=cholinc(sa,tol)或或 r=cholinc(sa,0)其中系数矩阵其中系数矩阵a必须用稀疏形式必须用稀疏形式 sa.预条件共轭斜量法预条件共轭斜量法MATLAB的三种调用格式的三种调用格式:1.不用预优矩阵的共轭斜量法不用预优矩阵的共轭斜量法 x=pcg(a,b,tol,kmax)2.用预优矩阵的共轭斜量法用预优矩阵的共轭斜量法 (1)x=pcg(a,b,tol,kmax,m)(2)r=chol(m)x=pcg(a,b,tol,kmax,r,r,x0)3.未给定预
31、优矩阵的共轭斜量法未给定预优矩阵的共轭斜量法 r=cholinc(sa,0)x=pcg(a,b,tol,kmax,r,r,x0)(1)()0kkrr 1 1.证证明明：对对于于最最速速下下降降法法，相相邻邻两两次次的的搜搜索索方方向向是是正正交交的的，即即（，）习题三习题三 P123-29P123-29，3030 121(1,1,1),(1,0,1),(0,1,1),TTTuuu 2.2.已已知知一一组组线线性性无无关关的的向向量量由由此此向向量量组组，按按SchmidtSchmidt正正交交化化方方法法，求求一一组组对对应应的的310310A A共共轭轭向向量量组组,其其中中A=131A=131013013
