算法的收斂性和收斂速度的定義式課件

5.2.1函數的方向導數和梯度1、函數的方向導數實例：一塊長方形的金屬板，四個頂點的坐標是(1,1)，(5,1)，(1,3)，(5,3)。在坐標原點處有一個火焰，它使金屬板受熱。假定板上任意一點處的溫度與該點到原點的距離成反比。在(3,2)處有一個螞蟻，問這只螞蟻應沿什么方向爬行才能最快到達較涼快的地點？

問題的實質：應沿由熱變冷變化最劇烈的方向（即梯度方向）爬行．西南科技大學網絡教育系列課程

討論函數在一點P沿某一方向的變化率問題．（如圖）。引射線內有定義，自點的某一鄰域在點設函數lPPUyxP)(),(),(,).(p/UP/lyyxxPlxD+D+/上的另一點且為并設為的轉角軸正向到射線設j1）方向導數的定義當沿著趨于時，是否存在？且考慮}0,1{1=er依定義，函數),(yxf在點P沿著x軸正向、y軸正向}1,0{2=er的方向導數分別為yxff,；沿著x軸負向、y軸負向的方向導數是

yxff--,.的方向導數。沿方向則稱這極限為函數在點在，時，如果此比的極限存趨于沿著當之比值，兩點間的距離與函數的增量定義lPP/lPyxP/PD+D=22)()(r記為證明由于函數可微，則增量可表示為兩邊同除以得到2）方向導數的計算

定理

如果函數),(yxfz=在點),(yxP是可微分的，那么函數在該點沿任意方向L的方向導數都存在，且有

，

其中j為x軸到方向L的轉角。故有方向導數對于三元函數),,(zyxfu=，它在空間一點),,(zyxP沿著方向L的方向導數

，可定義為推廣可得三元函數方向導數的定義其中

同理：當函數在此點可微時，那末函數在該點沿任意方向L的方向導數都存在，且有設方向L的方向角為gba,,推導出n元函數f(x)在點X(k)處沿任意給定方向S的方向導數表達式為：西南科技大學網絡教育系列課程2、梯度1）梯度的定義

函數在點X(k)的梯度是由函數在該點的各個一階偏導數組成的向量。2）梯度的表達式

西南科技大學網絡教育系列課程

函數在某點的梯度是這樣一個向量，它的方向與取得最大方向導數的方向一致,而它的模為方向導數的最大值。梯度的模為結論x軸到梯度的轉角的正切為當不為零時，在幾何上表示一個曲面曲面被平面所截得所得曲線在xoy面上投影如圖等高線梯度為等高線上的法向量

3、方向導數和梯度的關系根據矢量代數的概念，方向導數的表達式可寫成：西南科技大學網絡教育系列課程由上式表明：函數在某點沿方向S的方向導數等于該點的梯度在方向身上的投影。見下圖。西南科技大學網絡教育系列課程當方向S與梯度的夾角為零時，方向導數達到最大值，即

從圖中可以看出：當方向S與點X(k)的梯度相垂直時，函數在該點沿S的方向導數等于零，即

當方向S與梯度方向的夾角為銳角時有：

當方向S與梯度方向的夾角為鈍角時有：

西南科技大學網絡教育系列課程這說明，與梯度成銳角的方向是函數值上升的方向，而與梯度成鈍角的方向則是函數值下降的方向。

西南科技大學網絡教育系列課程綜上所述，函數的梯度具有以下性質(1)函數在一點的梯度是一個向量。梯度的方向是該點函數值上升得最快的方向，梯度的大小就是它的模長。(2)一點的梯度方向為過該點的等值線或等值面的切線或切平面相垂直的方向，或者說是該點等值線或等值面的法線方向。(3)梯度是函數在一點鄰域內局部性態(tài)的描述。在一點上升得快的方向，離開該領域后就不一定上升得快，甚至可能下降。西南科技大學網絡教育系列課程例1求函數f(X)＝(x1－2)2十(x2－1)2在點X(1)＝[3,2]T和X(2)＝[2,2]T的梯度并作圖表示。解：根據定義，梯度為則西南科技大學網絡教育系列課程解：梯度的模為：單位梯度的向量為：西南科技大學網絡教育系列課程在設計平面x1ox2內標出點(2,2)和點(0,2)，并將此兩點分別與原點相連得到向量[2,2]T和[0,2]T。將這兩個向量各自平移至點X(1)和X(2)，所得新的向量就是點X(1)和X(2)的梯度。圖5.11例1的梯度西南科技大學網絡教育系列課程5.2.1函數的方向導數和梯度例題2一般二元二次函數的矩陣式為

，其中

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+3x12+3x22-9x1在點X(1)=[1,1]T簡化成線性函數和二次函數。解：(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階主子式<0

則矩陣H是負定的。西南科技大學網絡教育系列課程5.2.3二次函數3、極值條件1）多元函數在點X(k)取得極小值的條件是：函數在該點的梯度為零，二階導數矩陣為正定。即2）多元函數在點X(k)取得極大值的條件是：函數在該點的梯度為零，二階導數矩陣為負定。即西南科技大學網絡教育系列課程5.2.3二次函數例5：試求f(x1,x2)＝2x12-8x1+2x22-4x2+20的極值及極值點。解：由極值點存在的必要條件得駐點X*=[2，1]T,在X*點海森矩陣為：

西南科技大學網絡教育系列課程5.2.3二次函數由于其各階主子行列式為可知在X*點海森矩陣正定的，∴X*為極小點，其極小值為：西南科技大學網絡教育系列課程5.2.4下降迭代算法多變量、多約束的非線性優(yōu)化問題，通常采用數值迭代求解，對于極小化問題，這種方法就是下降迭代算法。1、下降迭代法的定義按照某一迭代格式，從一個初始點X(0)出發(fā)逐步產生一個點列

X(0)、X(1)、X(2)、…、X(k)、X(k+1)、…若該點列對應的目標函數值呈下降趨勢

f(X(0))>f(X(1))>f(X(2))

…>f(X(k))>

f(X(k+1))…并且該點列對應的極限就是目標函數的極小點X*，則構成此點列的方法就是優(yōu)化問題的一種數值解法，稱為下降迭代算法。西南科技大學網絡教育系列課程5.2.4下降迭代算法2、下降迭代算法的基本格式下降迭代算法的基本格式如下：西南科技大學網絡教育系列課程(1)下降迭代算法構成的基本步驟：1）給定一個初始點X(0)和收斂精度ε2）選取一個搜索方向S(k)3）確定步長因子ak，按上式得到新的迭代點4）收斂判斷：若X(k+1)滿足收斂精度，則以X(k+1)作為最優(yōu)點，終止計算；否則，以X(k+1)作為新的起點，轉2）進行下一輪迭代。5.2.4下降迭代算法(2)下降迭代算法的構成需要解決的三個基本問題1）選擇搜索方向。不同的搜索方向，構成不同的下降迭代算法。在每一類下降迭代法中包含兩個關鍵步驟：得到迭代點后，如何選擇搜索方向；在確定搜索方向后，如何進行一維搜索。（在下一節(jié)作詳細說明）2）確定步長因子。（在下一節(jié)作詳細說明）一般通過一維搜索法取得最優(yōu)步長因子。3）給定收斂準則。用以判斷迭代點是否能夠作為近似的最優(yōu)點。

西南科技大學網絡教育系列課程5.2.4下降迭代算法3、算法的收斂性與收斂準則1)算法的收斂性當迭代算法產生的點列滿足

時，稱該點列收斂于極不點X*

，即稱此下降迭代算法具有收斂性。

算法的收斂性和收斂速度的定義式：西南科技大學網絡教育系列課程5.2.4下降迭代算法當β=1時，稱