25-共轭梯度法PPT课件.ppt

?共轭梯度法的算法选取初值Fork=0,1,2,…,n计算计算如果，停止否则，计算进行下一次迭代*预备知识最速下降法共轭梯度法数值试验算例????*§2.5共轭梯度法标题添加点击此处输入相关文本内容点击此处输入相关文本内容总体概述点击此处输入相关文本内容标题添加点击此处输入相关文本内容(x,y)=(y,x);(tx,y)=t(x,y);(x+y,z)=(x,z)+(y,z);(x,x)≥0,且(x,x)=0?x=0;I方程组问题:Ax=b设A是n阶对称正定阵(Ax,y)=(x,Ay);(Ax，x)≥0,且(Ax,x)=0?x=02/16预备知识：内积的定义II极值问题:设,记(x,y)=xTy预备知识梯度:*Hessian矩阵:预备知识*费马引理:*注释:费马引理的价值在于将极值问题转化为方程的求解问题。初等变分原理一、与方程组等价的二次泛函问题思想共轭梯度法将求解方程组问题等价转化为一个二次泛函的极值问题。定义二次函数设为对称正定矩阵，其中定理(初等变分原理)设A=(aij)n×n为实对称正定矩阵,，则x是二次函数的极小值点?x是线性方程组Ax=b的解。*该性质说明：求解方程组的解等价于求上述二次函数的最小值。若则由极值的必要条件得迭代法构造思想：构造使得从瞎子下山到最优化方法*ScienceofBetter瞎子与计算机瞎子:能感觉到脚下的坡度(这是海拔函数在当前点的梯度值),但不知道山上其它点的任何情况计算机:计算目标函数在该点的信息(如函数值和梯度值),但不知道其它点的信息*2.5.2最速下降法?几何意义：等值线思想最速下降法是指每次沿着函数值下降最快的方向寻找最小值点。而函数值下降最快的方向是函数的负梯度方向?最速下降法实现过程：选取初始向量，由二次函数的基本性质?如果，则就是方程组的解；如果，则沿方向进行一维极小有哪些信誉好的足球投注网站：求使得达到最小值,则注意到令，从而完成第一次迭代。下面以为新的初值，重复上述过程。?最速下降法的算法:选取初值Fork=0,1,2,…若，停止否则，进行下一次循环有哪些信誉好的足球投注网站方向是正交的：缺陷：收敛速度慢！收敛速度？？？？？解：易验证系数矩阵是对称正定的.例：用最速下降法求解方程组:3xStep1计算最好+最好=最好?

方向(最速下降)(bestrk)步长(精确有哪些信誉好的足球投注网站)(best)是否最好?*设的特征值为,则由前述最速下降算法产生的序列满足其中。上述定理说明，当时最速下降法收敛非常慢。f(x1,x2)=100x12+x22最速下降法*f(x1,x2)=100x12+x22Barzilai-Borwein方法*最速下降法思想简单,但是收敛速度慢。本质上是因为负梯度方向函数下降快是局部性质。全局思想:局部思想:N维空间的任意向量可以由N个线性无关的向量线性表示。*3、共轭梯度法/*Conjugate-GradientMethod*/共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。Hestenes和Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，Fletcher和Reeves（1964）首先提