共轭梯度法ppt课件

1、1第四章 共轭梯度法4.1 共轭方向法4.2 共轭梯度法 4.13共轭梯度法的收敛性2 4.1 4.1 共轭方向法 共轭方向法是介于最速下降法与牛顿法之间的一个方法。它仅需要利用一阶导数信息，它克服了最速下降法收敛慢的缺点，又避免了存储和计算牛顿法所需要的二阶导数信息。共轭方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题。最典型的共轭方向法是本章研究的共轭梯度法。3定义4.1.1：设G是nn的对称正定矩阵，d1、d2是n维非零向，如果d1TGd2=0，则称向量d1和d2是G-共轭的（或G-直交的）。类似的，设d1，d2dm是Rn中任一组非零向量，如果diTGdj

2、=0（ij），则称d1，d2dm是G-共轭的。 显然，如果d1，d2dm是G-宫二的，则它们是线性无关的。如果G=I，则共轭性等价于通常的直交性。注：如果G是单位矩阵，则dIT Gd2=0 dIT d2=0 d1 d2 共轭是正交的推广。4算法4.1.2（一般）共轭方向法给出x*的初始点x0;第一步：计算g0=g（x0）第二步：计算d0，使d0Tg00第三步：令k=0第四步：计算k和xk+1 ，使得 f（xk+kdk）=min f（xk+dk）， xk+1 =xk+kdk第五步：计算dk+1使得dk+1TGdj=0，j=0,1，k第六步：令k:=k+1，转第四步。共轭方向法的一个基本性质是：只

3、要执行精确线性搜索，就能得到二次终止性。这也就共轭方向法基本定理。5定理4.1.3 ：共轭方向法基本定理对于正定二次函数，共轭方向法至多经过n步精确线性搜索终止，且每一xi+1都是f（x）在x0和方向d0，di所张成的线性流形（如图4-1）中的极小值 如图4-16证明：因为G正定且共轭方向d0，d1，线性无关，所以只要证明对所有in-1，有 ，j=0，i，（即沿流形中的任何直线的斜率为零），就可得出定理的两个结论。事实上，由于 yk=gk+1-gk=G（xk+1-xk）=kGdk 所有当ji时， 图4-2（4.1.3） 0dj1gTi7在（4.1.3）中两项为零分别由精确线性搜索和共轭性得到。

4、当j=i时，直线由线性搜索可知： 从而（4.1.1)成立。 （ 4.1.4） 这个定理是所有共轭当想法的理论基础，所以说这个定理相当重要。这个定理表明，在精确线性搜索条件下，共轭方向法的梯度满足（4.1.1）如下图4-3 图4-3 共轭方向法的梯度满足（4.1.1） 01jTidg8 最后，我们还应该指出下面的事实所包含的共轭性的基本含义，设极小点可以写成一般点可以写成注意到二次函数可以写为：略去常数项d，有 dxxi1 - n0i*i0*dxxi1 -n0ii0 d-xG*21qxx-x*Txx-x*T-xG*21q*T T-GS*21S-9其中由于di共轭，所以其中， ，通过选择 ，i=0,1，n-1。即可使q（）极小化，这等价于在x-空间作精确线性搜索。因此，共轭性意味着G到一个新的（）-坐标系的对角变换在该坐标系中变量是互相分离的。于是，一个共