算法的收敛性和收敛速度的定义式课件

5.2.1函数的函数的方向导数和梯度和梯度1、函数的方向导数、函数的方向导数 实例：一块长方形的金属板，四个顶点的坐实例：一块长方形的金属板，四个顶点的坐标是标是(1,1)，(5,1)，(1,3)，(5,3)。在坐标原点。在坐标原点处有一个火焰，它使金属板受热。假定板上任意处有一个火焰，它使金属板受热。假定板上任意一点处的温度与该点到原点的距离成反比。在一点处的温度与该点到原点的距离成反比。在(3,2)处有一个蚂蚁，问这只蚂蚁应沿什么方向处有一个蚂蚁，问这只蚂蚁应沿什么方向爬行才能最快到达较凉快的地点？爬行才能最快到达较凉快的地点？问题的实质问题的实质：应沿由热变冷变化最剧烈的方：应沿由热变冷变化最剧烈的方向（即梯度方向）爬行向（即梯度方向）爬行西西南南科科技技大大学学网网络络教教育育系系列列课课程程 讨论函数讨论函数 在一点在一点P沿某一方向沿某一方向的变化率问题的变化率问题（如图）（如图）。引射线引射线内有定义，自点内有定义，自点的某一邻域的某一邻域在点在点设函数设函数lPPUyxP)(),(),(,).(p/UP/lyyxxPlxD D+D D+/上的另一点且上的另一点且为为并设并设为为的转角的转角轴正向到射线轴正向到射线设设j j1 1）方向导数方向导数的定义的定义当当 沿着沿着 趋于趋于 时，时，是否存在？是否存在？且且考虑考虑0,11=err依定义，函数依定义，函数),(yxf在点在点P沿着沿着x轴正向轴正向、y轴正向轴正向1,02=err的方向导数分别为的方向导数分别为yxff,；沿着沿着x轴负向、轴负向、y轴负向的方向导数是轴负向的方向导数是 yxff-,.的的方向导数方向导数。沿方向沿方向则称这极限为函数在点则称这极限为函数在点在，在，时，如果此比的极限存时，如果此比的极限存趋于趋于沿着沿着当当之比值，之比值，两点间的距离两点间的距离与与函数的增量函数的增量定义定义lPP/lPyxP/P D D+D D=22)()(r r记为记为证明由于函数可微，则增量可表示为由于函数可微，则增量可表示为两边同除以两边同除以得到得到2）方向导数的计算 定理如果函数),(yxfz=在点),(yxP是可微分的，那么函数在该点沿任意方向L L的的方向导数都存在，且有 ，其中j j为x轴到方向L L的转角。故有方向导数故有方向导数对于三元函数对于三元函数),(zyxfu=，它在空间一点，它在空间一点),(zyxP沿着方向沿着方向L的方向导数的方向导数，可定义，可定义为为推广可得三元函数方向导数的定义推广可得三元函数方向导数的定义其中其中 同理：当函数在此点可微时，那末函数在该点同理：当函数在此点可微时，那末函数在该点沿任意方向沿任意方向L的方向导数都存在，且有的方向导数都存在，且有设方向设方向L的方向角为的方向角为g gb ba a,推推导导出出n元元函函数数f(x)在在点点X(k)处处沿沿任任意意给给定定方方向向S的方向导数的方向导数 表达式为表达式为：西西南南科科技技大大学学网网络络教教育育系系列列课课程程2、梯度梯度1）梯度的定义）梯度的定义 函数在点函数在点X(k)的梯度是由函数在该点的各个的梯度是由函数在该点的各个一阶偏导数组成的向量一阶偏导数组成的向量。2）梯度的表达式）梯度的表达式 西西南南科科技技大大学学网网络络教教育育系系列列课课程程 函数在某点的函数在某点的梯度梯度是这样一个向量，它的是这样一个向量，它的方向方向与取得与取得最大方向导数的方向一致最大方向导数的方向一致,而它的而它的模模为为方向导数的最大值方向导数的最大值。梯度的模为。梯度的模为结论结论x 轴到梯度的转角的正切为轴到梯度的转角的正切为当当不为零时，不为零时，在几何上在几何上 表示一个曲面表示一个曲面曲面被平面曲面被平面 所截得所截得所得曲线在所得曲线在xoyxoy面上投影如图面上投影如图等高线等高线梯度为等高线上的法向量梯度为等高线上的法向量 3、方向导数和梯度的关系、方向导数和梯度的关系 根根据据矢矢量量代代数数的的概概念念，方方向向导导数数的的表表达达式式可可写写成：成：西西南南科科技技大大学学网网络络教教育育系系列列课课程程 由上式表明：函数在某点沿方向由上式表明：函数在某点沿方向S的的方向导数方向导数等于等于该点的梯度在方向身上的投影该点的梯度在方向身上的投影。见下图。见下图。西西南南科科技技大大学学网网络络教教育育系系列列课课程程当方向当方向S与梯度的与梯度的夹角为零时，方向夹角为零时，方向导数达到最大值，导数达到最大值，即即 从图中可以看出：从图中可以看出：当当方向方向S与点与点X(k)的梯度相垂直的梯度相垂直时，函数在该时，函数在该点沿点沿S的方向导数等于零，即的方向导数等于零，即 当方向当方向S与梯度方向的夹角为锐角时有：与梯度方向的夹角为锐角时有：当方向当方向S与梯度方向的夹角为钝角时有：与梯度方向的夹角为钝角时有：西西南南科科技技大大学学网网络络教教育育系系列列课课程程 这说明，与梯度成锐角的方向是函数值上升这说明，与梯度成锐角的方向是函数值上升的方向，而与梯度成钝角的方向则是函数值下降的方向，而与梯度成钝角的方向则是函数值下降的方向。的方向。西西南南科科技技大大学学网网络络教教育育系系列列课课程程综上所述，函数的梯度具有以下性质综上所述，函数的梯度具有以下性质 (1)函函数数在在一一点点的的梯梯度度是是一一个个向向量量。梯梯度度的的方方向向是是该该点点函函数数值值上上升升得得最最快快的的方方向向，梯梯度度的的大大小小就就是是它的模长它的模长。(2)一一点点的的梯梯度度方方向向为为过过该该点点的的等等值值线线或或等等值值面面的的切切线线或或切切平平面面相相垂垂直直的的方方向向，或或者者说说是是该该点点等等值值线或等值面的法线方向线或等值面的法线方向。(3)梯梯度度是是函函数数在在一一点点邻邻域域内内局局部部性性态态的的描描述述。在在一一点点上上升升得得快快的的方方向向，离离开开该该领领域域后后就就不不一一定定上上升得快，甚至可能下降。升得快，甚至可能下降。西西南南科科技技大大学学网网络络教教育育系系列列课课程程例例1 求求函函数数f(X)(x12)2十十(x21)2在在点点X(1)3,2T和和X(2)2,2 T的梯度并作图表示。的梯度并作图表示。解：根据定义，梯度为解：根据定义，梯度为则则西西南南科科技技大大学学网网络络教教育育系系列列课课程程解：梯度的模为：解：梯度的模为：单位梯度的向量为单位梯度的向量为：西西南南科科技技大大学学网网络络教教育育系系列列课课程程在设计平面在设计平面x1ox2内内标出点标出点(2,2)和点和点(0,2)，并将此两点并将此两点分别与原点相连得分别与原点相连得到向量到向量2,2T和和0,2T。将这两个将这两个向量各自平移至点向量各自平移至点X(1)和和X(2)，所得新所得新的向量就是点的向量就是点X(1)和和X(2)的梯度。的梯度。图图5.11 例例1的梯度的梯度西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.1 函数的方向导数和梯度例题例题2 一般二元二次函数的矩阵式为一般二元二次函数的矩阵式为，其中 C C为常数，求梯度为常数，求梯度 。西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.1 函数的方向导数和梯度 解：将二元二次函数的矩阵式展开解：将二元二次函数的矩阵式展开其中其中 ，于是梯度为，于是梯度为 西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.1 函数的方向导数和梯度 即即 同理，推广到同理，推广到n元二次函数，则一般元二次函数，则一般n元元二次函数梯度的矩阵表达式为二次函数梯度的矩阵表达式为 西西南南科科技技大大学学网网络络教教育育系系列列课课程程式中式中5.2.2 多元函数的泰勒展开 由高等数学知、一元函数由高等数学知、一元函数f(x)着在点着在点xk的邻域的邻域内内n阶可导，则函数可在该点的邻域内作如下泰勒展阶可导，则函数可在该点的邻域内作如下泰勒展开：开：多元函数多元函数f(x)在在xk点也可以作泰勒点也可以作泰勒(Taylor)展展开开,其展开式一般取三项其展开式一般取三项,其形式与一次函数的形式其形式与一次函数的形式的前三项是相似的的前三项是相似的.西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.2 多元函数的泰勒展开写成矩阵形式：写成矩阵形式：式中式中称为称为f(x)的海森的海森(Hessian)矩阵矩阵，常用常用H(x)表示表示。西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.2 多元函数的泰勒展开例例3 一般二元二次函数一般二元二次函数 ，求，求H(X)。解：解：西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.2 多元函数的泰勒展开西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.2 多元函数的泰勒展开 例例4 用用泰泰勒勒展展开开的的方方法法将将函函数数f(X)x13-x23+3 x12+3 x22-9x1在在点点X(1)=1,1T简简化化成成线线性性函函数数和和二次函数。二次函数。解：解：(1)求函数在点求函数在点X(1)的函数值、梯度为：的函数值、梯度为：西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.2 多元函数的泰勒展开(2)求得二阶导数矩阵为：求得二阶导数矩阵为：而且而且代入线性泰勒展开式得简化的线性函数：代入线性泰勒展开式得简化的线性函数：西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.2 多元函数的泰勒展开(3)得到泰勒展开式的二次项为：得到泰勒展开式的二次项为：代入泰勒展开式得简化的二次函数：代入泰勒展开式得简化的二次函数：西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.3 二次函数1、二次函数的表达式、二次函数的表达式 二次函数是最简单的非线性函数，可以写成以下向量二次函数是最简单的非线性函数，可以写成以下向量形式：形式：2、正定与负定的判断、正定与负定的判断1）如果）如果矩阵矩阵H的各阶主子式均大于零的各阶主子式均大于零，即，即 一阶主子式一阶主子式 二阶主子式二阶主子式 n阶主子式阶主子式0 则矩阵则矩阵H是是正定的正定的。西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.3 二次函数2）如果）如果矩阵矩阵H的各阶主子式正负相间的各阶主子式正负相间，即，即 一阶主子式一阶主子式 二阶主子式二阶主子式 n阶主子式阶主子式f(X(1)f(X(2)f(X(k)f(X(k+1)并且该点列对应的极限就是目标函数的极小点并且该点列对应的极限就是目标函数的极小点X*，则构成此点列的方法就是优化问题的一种数值解法，则构成此点列的方法就是优化问题的一种数值解法，称为称为下降迭代算法下降迭代算法。西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.4 下降迭代算法2、下降迭代算法的基本格式、下降迭代算法的基本格式 下降迭代算法的基本格式如下：下降迭代算法的基本格式如下：西西南南科科技技大大学学网网络络教教育育系系列列课课程程(1)下降迭代算法构成的基本步骤：下降迭代算法构成的基本步骤：1）给定一个初始点）给定一个初始点X(0)和和收敛收敛精度精度2）选取一个搜索方向）选取一个搜索方向S(k)3）确定步长因子）确定步长因子ak，按上式得到新的迭代点，按上式得到新的迭代点4）收敛收敛判断：若判断：若X(k+1)满足满足收敛收敛精度，则以精度，则以X(k+1)作为最优点，终止计算；否则，以作为最优点，终止计算；否则，以X(k+1)作为新的作为新的起点，转起点，转2）进行下一轮迭代。）进行下一轮迭代。5.2.4 下降迭代算法(2)下降迭代算法的构成需要解决的三个基本问题下降迭代算法的构成需要解决的三个基本问题1）选择搜索方向选择搜索方向。不同的搜索方向，构成不同的下降迭代算法。不同的搜索方向，构成不同的下降迭代算法。在每一类下降迭代法中包含两个关键步骤：在每一类下降迭代法中包含两个关键步骤：得到迭得到迭代点代点 后，如何选择搜索方向后，如何选择搜索方向；在确定搜索方向后，；在确定搜索方向后，如何进行一维搜索。（在下一节作详细说明）如何进行一维搜索。（在下一节作详细说明）2）确定步长因子确定步长因子。（在下一节作详细说明）（在下一节作详细说明）一般通过一维搜索法取得最优步长因子。一般通过一维搜索法取得最优步长因子。3）给定收敛准则给定收敛准则。用以判断迭代点是否能够作为近似的最优点。用以判断迭代点是否能够作为近似的最优点。西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.4 下降迭代算法3、算法的收敛性与收敛准则、算法的收敛性与收敛准则1)算法的收敛性算法的收敛性 当迭代算法产生的点列满足当迭代算法产生的点列满足 时，称该点列收敛于极不点时，称该点列收敛于极不点X*，即称此，即称此下降迭代算下降迭代算法具有收敛性法具有收敛性。算法的收敛性和收敛速度的定义式：算法的收敛性和收敛速度的定义式：西西南南科科技技大大学学网网络络教教育育系系列列课课程程5.2.4 下降迭代算法 当当=1时，称算法具有线性收敛性，或者说算时，称算法具有线性收敛性，或者说算法具有线性收敛速度。法具有线性收敛速度。当当=2时，称算法具有二次收敛性。时，称算法具有二次收敛性。当当12时，称算法具有超线性收敛性。时，称算法具有超线性收敛性。西西南南科科技技大大学学网网络络教教育育系系列列课课程程最差最差最好最好其次其次2）算法的收敛准则）算法的收敛准则 判断迭代点与精确解近似程度的方法称为判断迭代点与精确解近似程度的方法称为收敛收敛准则准则。(1)点距准则：相邻点距准则：相邻两迭代点的距离两迭代点的距离来判断。来判断。5.2.4 下降迭代算法(2)值差准则：相邻值差准则：相邻两迭代点的函数值之差两迭代点的函数值之差来判断来判断西西南南科科技技大大学学网网络络教教育育系系列列课课程程(3)梯度准则：梯度准则：梯度的模长梯度的模长判断判断