牛頓法與修正牛頓法PPT學(xué)習(xí)教案

1、會計學(xué)1牛頓法與修正牛頓法牛頓法與修正牛頓法牛頓法和修正牛頓法第1頁/共17頁第2頁/共17頁2、基本思想 在求目標(biāo)函數(shù) 的極小值時，先將它在 點附近展開成泰勒級數(shù)的二次函數(shù)式，然后求出函數(shù)的極小值點，并以此點作為欲求目標(biāo)函數(shù)的極小值點 的一次近似值。 設(shè)目標(biāo)函數(shù)是連續(xù)二階可微的，將函數(shù)在點 按泰勒級數(shù)展開，并取到二次項：)(kx)()(21 )()()()()()()()()()()()(kkTkkTkkkxxxHxxxxxfxfxxf)(xf)(kx*x第3頁/共17頁對x求導(dǎo)，其極值點必滿足一階導(dǎo)數(shù)為零，所以，得到 式中， 為Hessian矩陣的逆矩陣。 0)()()()()()()(k

2、kkxHxxxfxxfx)()()(1)()(minkkkxfxHxx1)()(kxH 1 第4頁/共17頁( )f x(1)( )()1( )()()kkKkxxH xf xminx( )f x(f x）)kx（( )x( 1 )kx( )f x( )H x( )kx( )f x2第5頁/共17頁)()()()1(kkkksxx)()()(1)()(kTkkxfxHs1)(k 2)()()1()(1)()()()(kkkkkksxxxfxHs牛頓法的迭代算式其中 稱為牛頓方向。)(kS第6頁/共17頁3、迭代步驟 一 給定初始點 ，計算精度，令k=0； 二 計算 點的梯度 、 及其逆矩陣 。

3、 三 構(gòu)造搜索方向)0(x)(kx)()(kxf)()(kxH1)()(kxH)()()(1)()(kkkxfxHs第7頁/共17頁 四四 沿沿 方向進(jìn)行一維搜索，得迭代點方向進(jìn)行一維搜索，得迭代點 五五 收斂判斷：收斂判斷：若若 ，則，則 為近似最優(yōu)點，迭代停為近似最優(yōu)點，迭代停止，止， 輸出最優(yōu)解輸出最優(yōu)解 和和 終止計算。終止計算。若不滿足，令若不滿足，令k=k+1，轉(zhuǎn)第二步繼續(xù)迭代。，轉(zhuǎn)第二步繼續(xù)迭代。)(ks)()()1(kkksxx)()1(kxf)1( kx)1(minkxx)()()1(minkxfxf)()1(kxf)1(minkxx)()1(kxf)()()1(minkxf

4、xf)1(minkxx)()1(kxf第8頁/共17頁例： 用牛頓法求函數(shù) 的極小值。60410)(21212221xxxxxxxf解：(1)取初始點(2)計算牛頓方向00)0(x41042102)()0(1221xxxxxxxf第9頁/共17頁2112)(222122212212)0(xfxxfxxfxfxH211231)(1)0(xH68182431410211231 )()()0(1)0()0(xfxHs故(3)極小值8)(min6868*100)0()0()0(1xfsxx第10頁/共17頁4、優(yōu)缺點 數(shù)學(xué)分析表明，牛頓法具有很好的局部收斂性質(zhì)，對二次函數(shù)來說，僅一步就達(dá)到優(yōu)化點， 但

5、對一般函數(shù)來說，在一定條件下，當(dāng)初始點的選取充分接近目標(biāo)函數(shù)的極小點時，有很快的收斂速度，但若初始點選取離最小點比較遠(yuǎn)，就難保證收斂； 牛頓法必須求一階、二階導(dǎo)數(shù)及求逆陣，這對較復(fù)雜的目標(biāo)函數(shù)來說，是較困難的。第11頁/共17頁)()()()1(kkxfxfkx2第12頁/共17頁 3)()()(1)()()()1(kkkkkxfxHxx)(k)()()(1)()(kkkxfxHs第13頁/共17頁22122210422)(. 1 . 0,) 1, 1 (xxxxxxfx()(2121211)(;24)(4222)(;42422)()0(1)0()0(1)0()0()0(2121xfxHsxHxfxHxxxxxf第14頁/共17頁1012)31 (2)1 (6)1 (4)31 (6)()()31 (4)1)(31 (2)1 (2)31 ()(131131122)1()0()0()1(xfsxx8)(241