共轭方向法演讲PPT

共轭方向法2020/2/121主要内容一：共轭方向和共轭向量的概念二：共轭向量的几何意义和性质三：构造共轭方向法的原理和方法四：共轭方向法的迭代计算步骤五：求解非线性方程组的MATLAB程序实现和相关算法的比较2020/2/122nRXnRY0TAXYnn0TXY，满足如下关系：的对称正定阵，则称X和Y关于A共轭。注：若若两个非零向量其中，A为，X和Y称之为共轭方向。，则称X与Y正交。共轭是正交的推广。设A为对称正定矩阵，若有m个n维向量12,,...,mSSS满足0,TijAijSS则称这m个向量是A的共轭向量。注：若AI，则nn为正交向量。12,,...,mSSS一、共轭方向和共轭向量的概念共轭方向共轭向量2020/2/1230X0P()FX1X设从某点出发，沿方向进行搜索得到的极小点，有：1010()()0TTFXAXBPP0X’()FX2X设从某点出发，沿方向进行搜索得到的极小点2020()()0TTFXAXBPP(1)-(2)，可得：210()A0TXXP)(12XX0P所以，与是关于A共轭的。(1)(2)1()ABC2TTFXXXX()FXBAXXF)(（A为n维阶的对称正定阵）的梯度为：设目标函数为0P，有：二、共轭向量的几何意义和性质2020/2/124共轭方向法算法的构造基于如下几点：（1）n维正定二次函数依次沿n个相互共轭的方向作n次一维优化搜索可达最优点。（2）二维正定二次函数的等值线为同心椭圆族。（3）同心椭圆族的任意两平行切线的切点连线方向与该切线的方向，即为共轭方向。第1点是共轭方向法迭代模式的基础，第2、3点是共轭方向法构造共轭方向的方法依据。对于非二次型的目标函数，由于许多目标函数在极值点附近，都可以用二次函数作很好的近似，所以共轭方向法用于非二次的目标函数也有很好的效果。相关性质2020/2/125共轭向量的两个重要性质性质1.关于A共轭的向量组必为线性无关，共轭向量组中，共轭向量的个数最多等于维数n（矩阵A的维数为n）。2020/2/126原理：同心椭圆族的几何性质在任意两个同心椭圆上作两条相平行的切线l1,l2，则两切点的连线必过椭圆族的中心切线的方向S1与两切点连线的方向S2，就是一对共轭方向。正定二次二元函数(等值线为同心椭圆族)，经两次共轭方向搜索，就可搜索到极小点(椭圆中心)。2020/2/127•方法：以X0(1)为初始点，以S1为搜索方向作一维优化，•再以X0(2)为起点，用与S1相平行的方向作一维优化，则最优点，是直线l2与另一椭圆的切点X(2)。•以X(1)为起点，X(2)为终点的向量为：S2＝X(2)-X(1)，•S2的方向就是两切点连线的方向，因为l1与l2平行，因此S1与S2共轭。其最优点，就是直线l1与某一椭圆的切点X(1)，2020/2/128构造共轭方向数值方法的归纳用某一个不变的方向S1,以两个不同的初始点作两次一维优化，得到两个最优点。连接这两个最优点的连线方向S2就是与S1共轭的方向。对于n维问题，接着以S2为搜索方向，重复上述步骤就可得到与S2共轭的方向S3，反复迭代，即可求得n个相互共轭的方向。2020/2/129（1）置SS数组为n阶单位阵，迭代轮次k＝1。对于二维问题1001SS(2)i＝1ton做n次一维优化搜索，方向S取SS中的第i行数值，即sj＝ssi,j、j=1，…,n。(3)计算S(k)=Xn(k)-X0(k)(本轮初始点)以Xn(k)为起点，沿S(k)作一维优化，将其最优点作为X0(k+1)，(下一轮初始点)2020/2/1210(4)更新搜索方向向量组SSnjsssnjnisssskjjnji,,1,,1;1,,1)(,,1ji,(1)2)1(1s10sSSk=1时：(5)k=k+1，如果k＞n，转步骤(6)，否则转步骤(2)。2020/2/1211(5)k=k+1，如果k＞n，转步骤(6)，否则转步骤(2)。(6)检验终止准则，若满足则退出计算，若不满足，将当前最优点作为新的初始点，转步骤(1)重新再进行新的n次共轭方向的搜索计算。2020/2/1212五、求解非线性方程组的MATLAB程序实现和相关算法的比较)1()(T))()()1()(kTkkgkgkgg（迭代形式为其中，在共轭方向法中，2020/2/1213求解非线性方程组的MATLAB程序实现niikkxFxF12)()()()(整个计算流程为:在MATLAB中没有专门的函数实现共轭方向法求解非线性方程组，可以通过自定义F_ReevesGroundfun.m函数实现共轭方向法。2020/2/1214共轭方向法和阻尼牛顿法的比较牛顿阻尼法需要计算Hesse矩阵计算量很大，计算量很大。最速下降法有锯齿现像，收敛速度很慢，同一种非线性方程，最速下降法的迭代次数是共轭方向法的30多倍（见下面实例）共轭方向法和最速下降法的比较算法比较而且Hesse矩阵可能奇异，或者接近奇异；即使该矩阵是可逆的，它也未必是正定矩阵。此时，导出的牛顿法迭代格式的二次函数不一定有极小点，甚至没有驻点。2020/2/1215function[r,n]=FastDownGroudfun(F,x0,h,eps)%FastDownGroudfun.m为编写利用最速下降算法求非线性方程组的解的函数%F为非线性方程组%x0为给定的初始值%h为数值微分增量步%eps为解的精度%r为求得非线性方程组的一组解%n为迭代步数function[r,n]=F_ReevesGroundfun(F,x0,h,eps)%F_ReevesGroundfun为编写利用共轭方向算法求非线性方程组的解的函数%F为非线性方程组%x0为给定的初始值%h为数值微分增量步%eps为解的精度%r为求得非线性方程组的一组解%n为迭代步数Matlab相应程序的简单介绍2020/2/1216共轭方向法和最速下降法迭代次数的比较例：求解非线性方程组调用MATLAB程序，用最速下降法求解如下：迭代步数n=822020/2/1217共轭方向法和最速下降法迭代次数的比较例：求解非线性方程组调用MATLAB程序，用共轭方向法求解如下迭代步数n=3最速下降法的迭代步数是共轭方向法的将近27倍2020/2/1218一般目标函数在最优点附近呈现为二次函数，因此可以设想一个算法对于二次函数比较有效，就可能对一般函数也有较好效果。共轭方向法是在研究对称正定二次函数的基础上提出来的。共轭方向法收敛速度界于阻尼牛顿法和最速下降法之间，而且具有二次收敛性。共轭方向法的主要特点收敛速度所以说共轭方向法属于效果非常好而且又非常实用的方法。共轭方向法的现实基础2020/2/1219THEEND谢谢！2020/2/12202020/2/1221