版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
牛頓法牛頓法為求解非線方程的種經(jīng)典的迭方法,的收斂速度,有內(nèi)函數(shù)可直接使用。合著可以對(duì)其進(jìn)行用,求方程。牛頓迭代法(又稱為牛頓拉夫遜法(Newton-Raphsonmethod是牛頓17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法,其基本思想是利用目標(biāo)函數(shù)的二次展開,并將其極小化。牛頓法使用函數(shù)f前面幾項(xiàng)來尋方程f法是求方程根的重要方法之一,其最大優(yōu)點(diǎn)是在方程f具有平方收斂,而且該法還可以用來求方程的重根、復(fù)根,此時(shí)非線性收斂,但是可通過一些方法變成線性收斂。牛頓法的幾何解釋:方程
*
可解釋為曲線f焦點(diǎn)的橫坐標(biāo)。如下圖:設(shè)x是根*的某個(gè)近似值,過曲線yfx的P引切線,并k將該切線與x軸的交點(diǎn)橫坐標(biāo)牛頓法亦稱為切線法。2牛頓代公式:最下法()
k
作為x*的新的近似值。鑒于這種幾何背景,/
Tk2Tk2以負(fù)梯度方向作為極小化算法的下降方向,也稱為梯度法。設(shè)函數(shù)f近連續(xù)可微,且kk
由泰勒展開式:f
k
k
k
(*)k可知,若記xk
,則滿dk
T
g的方d是下降方向。當(dāng)k
取定后,d
T
g的值越小,
T
g的值越大,函數(shù)下降的越快。由不等式:
Tk
k
k
,故當(dāng)且僅時(shí)kkk
T
g最小,從而是最速下降k方向。最速下降法的迭代格式為:x
k
k
k
。k(牛法設(shè)f函數(shù),xR
n
,
2
fx附近用二次Taylor開近似f,f
s
s
12
sTfsqk
的二次近似。將上式右邊極小化,便得:x
x
2
f
x
x
,
這就是牛頓法的迭代公式。在這個(gè)公式里,步長因Gf也可kkkk寫成:
G
顯然,牛頓法也可以看成在橢球范數(shù)
下的最速下降法。G
事實(shí)上,對(duì)于,ks是極小化問題min
gs的解極小化問題依賴于所取的范數(shù)采l范數(shù)時(shí)s,所得方法為最速下降法。當(dāng)采用橢球范數(shù)kk
G
時(shí),s,所得方法即為牛頓法。k/
對(duì)于正定二次函數(shù)牛頓法一步即可達(dá)到最優(yōu)解而對(duì)于非二次函數(shù)牛頓法并不能保證有限次迭代求得最優(yōu)解,但由于目標(biāo)函數(shù)在極小點(diǎn)附近近似于二次函數(shù),故當(dāng)初始點(diǎn)靠近極小點(diǎn)時(shí),牛頓法的收斂速度一般是快的。牛法斂理設(shè)f2充分靠x*k
0
2
f矩G滿足Lipschitz條件,即存
,使得對(duì)所有i,j,有:Gij
x
Gij
y
xy,其矩Gk,牛頓迭代公式有意義,ij且所得序*,并且具有二階收斂速度。在實(shí)際求解中,當(dāng)初始點(diǎn)遠(yuǎn)離最優(yōu)解時(shí),Hesse矩不一定正定。牛頓方k向不一定是下降方向其收斂性不能保證這說明恒取步長因子為牛頓法是不合適的,應(yīng)該在牛頓法中采用某種一維搜索來確定步長因子。但是應(yīng)該強(qiáng)調(diào),僅當(dāng)步長因?yàn)椋?/p>
時(shí)牛頓法才是二階收斂的時(shí)牛頓法的迭代公式
,
x
k
xk
k
k其是一維搜索產(chǎn)生的步長因子。k帶步長因子牛頓法步1選取初始數(shù)據(jù),取初始點(diǎn)x,終止誤0
,k。步2計(jì)算。若kk
,停止迭代,輸出,否則進(jìn)行步3.k步3解方程組構(gòu)造牛頓方向,即Gd,求d。k步4進(jìn)行一維搜索,得kf
xkk
k
k令xk
xk
k
,k:k
轉(zhuǎn)步2/
f1x1f1x1牛頓法的計(jì)算步驟:步驟1
準(zhǔn)備
選定初始近似值,計(jì)算ff0
0
,f
'0
f
'
0
。步驟2
迭代
按公式:fx010'0
迭代一次,得新的近似值x,1ff'f'11步驟3
控制
如果x滿足11
,或f1
2
,則終止迭代,以x作為所求的1根;否則轉(zhuǎn)步驟4.此處1
,
2
是允許誤差,而:
當(dāng)時(shí);1011,當(dāng)x時(shí),其中C是取絕對(duì)誤差或相誤差的控制常數(shù),一般可C=1。步驟4
修改
如果迭代次數(shù)達(dá)到預(yù)先制定的次數(shù)N者f
'1
=0法失敗;否則f,f11
'1
f00
'0
繼續(xù)迭代。4牛頓法的進(jìn)在優(yōu)化問題的計(jì)算中牛頓迭代法是非線性方程求根中一種很實(shí)用的方法它具有簡單的迭代格式和較快的收斂速度,它二次收斂到單根,線性收斂到重根。數(shù)值計(jì)算中的經(jīng)典牛頓法面臨的主要問題是Hesse矩G不正定,這時(shí)候二次模型不一定有極k小點(diǎn),甚至沒有平穩(wěn)點(diǎn)。G不定時(shí),二次模型函數(shù)是無界的。和(出G非正定時(shí)用最速下降方Goldfeldk等人1966年)提出了一種修正方法,即使牛頓方向偏向最速下降方向。更k明確的說是將模型的Hesse矩改變GIvGIkkk正定。該算法的框架如下:給出初始點(diǎn)。第步迭代為:0/
k__kk__k(1)令I(lǐng)其中:kv,如G正定v否則。kkk(2)計(jì)G的Cholesky分解GDT。kk(3)G。k(4)xk
xk
k牛頓法的優(yōu)點(diǎn)是收斂快,缺點(diǎn)一是每步迭代要計(jì)算
f
'
,計(jì)算量較大且有時(shí)
'
難,二是初始近似值x只在根*0
附近才能保證收斂,如x給的不合適可能不收斂。0為克服這兩個(gè)缺點(diǎn),通??梢韵率鰞蓚€(gè)方法:(1)簡化牛頓法,也稱平行弦法。其迭代公式為,
k迭代函
(2)牛頓下山法:牛頓法的收斂性依賴于初始的選取。如x偏離所求根00*
較遠(yuǎn),則牛頓法可能發(fā)散。為防止迭代發(fā)散迭代過程再附加一項(xiàng)要求,即具有單調(diào)性:f
k
k
滿足這
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 臨潼汽車租賃合同模板
- 綜合整治合同模板
- 人造盆景市場環(huán)境與對(duì)策分析
- 教育培訓(xùn)合伙協(xié)議合同模板
- 醫(yī)用油紙相關(guān)項(xiàng)目實(shí)施方案
- 遼寧專升本計(jì)算機(jī)基礎(chǔ)26
- 電商拿貨合同模板
- 出口業(yè)務(wù)合同模板
- 租房養(yǎng)寵物合同模板
- 電增容合同模板
- 不銹鋼電梯門套施工合同
- 華為認(rèn)證智能協(xié)作中級(jí) HCIP-Collaboration H11-861考試題庫及答案
- 肖申克的救贖 電影劇本 中英對(duì)照
- 感冒清熱膠囊的藥理機(jī)制研究
- 2024華能海南昌江核電限公司應(yīng)屆高校畢業(yè)生招聘公開引進(jìn)高層次人才和急需緊缺人才筆試參考題庫(共500題)答案詳解版
- 24秋國家開放大學(xué)《計(jì)算機(jī)系統(tǒng)與維護(hù)》實(shí)驗(yàn)1-13參考答案
- 走進(jìn)民航智慧樹知到期末考試答案章節(jié)答案2024年中國民航大學(xué)
- 校服創(chuàng)意設(shè)計(jì)理念
- 2024年湖北交投宜昌高速公路運(yùn)營管理有限公司招聘筆試參考題庫含答案解析
- 中華民族共同體概論課件專家版7第七講 華夷一體與中華民族空前繁盛(隋唐五代時(shí)期)
- MOOC 創(chuàng)業(yè)風(fēng)險(xiǎn)識(shí)別與規(guī)避-中南財(cái)經(jīng)政法大學(xué) 中國大學(xué)慕課答案
評(píng)論
0/150
提交評(píng)論