ch 一維搜索逼近法與求根法

會(huì)計(jì)學(xué)1ch一維搜索逼近法與求根法3逼近法3.1拋物線逼近法3.2三次插值法3.3牛頓法第2頁/共24頁第1頁/共24頁3.1拋物線逼近法3.1.1三點(diǎn)二次插值基本思想：利用插值函數(shù)逼近所需求解的目標(biāo)函數(shù)，把插值函數(shù)的極小點(diǎn)作為迭代點(diǎn)。初始三點(diǎn)的選取可以用進(jìn)退法得到。第3頁/共24頁第2頁/共24頁基本原理：第4頁/共24頁第3頁/共24頁第5頁/共24頁第4頁/共24頁第6頁/共24頁第5頁/共24頁3.1.2二點(diǎn)二次插值兩點(diǎn)的函數(shù)值加一點(diǎn)的導(dǎo)數(shù)值。如果函數(shù)可微并易于求出導(dǎo)函數(shù)時(shí)可以選用此方法。比較簡單，不必預(yù)先確定上下界；不過函數(shù)如果單調(diào)時(shí)，得不到結(jié)果，需要限制迭代次數(shù)。第7頁/共24頁第6頁/共24頁第8頁/共24頁第7頁/共24頁兩點(diǎn)二次插值法模型

初始點(diǎn)λ0

，λ1

，f0=f（λ0

）f1=f（λ1），f′0=λ0

ε>0

求|f’′0|<ε?f1≥φ0?λ0=f0=計(jì)算λ1=f1=停：解λ0

NYNY第9頁/共24頁第8頁/共24頁3.2三次插值法3.2.14點(diǎn)函數(shù)值3.2.23點(diǎn)函數(shù)值加1點(diǎn)導(dǎo)數(shù)值3.2.32點(diǎn)函數(shù)值加2點(diǎn)導(dǎo)數(shù)值第10頁/共24頁第9頁/共24頁3.3牛頓法基本原理算法框圖第11頁/共24頁第10頁/共24頁第12頁/共24頁第11頁/共24頁算法框圖初始λ,ε1,ε2〉0K=1停；解λk|f′(λk)|<ε1?|f″(λk)|>0?停；失敗k=k+1|λk+1-λk|<ε2?λk+1=λk–NYNYYN第13頁/共24頁第12頁/共24頁例子第14頁/共24頁第13頁/共24頁第15頁/共24頁第14頁/共24頁算法特點(diǎn)優(yōu)點(diǎn)：收斂速度較快，二階收斂。缺點(diǎn)：需要計(jì)算二階導(dǎo)數(shù)，計(jì)算量大；局部收斂，初始點(diǎn)選擇需要合適。第16頁/共24頁第15頁/共24頁4求根法4.1切線法4.2割線法第17頁/共24頁第16頁/共24頁4.1切線法基本思想:用切線逼近目標(biāo)函數(shù)導(dǎo)函數(shù)的曲線,把切線的零點(diǎn)作為目標(biāo)函數(shù)的駐點(diǎn)的估計(jì).第18頁/共24頁第17頁/共24頁基本原理第19頁/共24頁第18頁/共24頁算法特點(diǎn)優(yōu)點(diǎn)：步驟簡單，收斂快，在相同的條件下比較少的迭代次數(shù)就能達(dá)到精度要求。缺點(diǎn)：用到二階導(dǎo)數(shù)，計(jì)算量大；初始點(diǎn)選擇需要合適。第20頁/共24頁第19頁/共24頁算法步驟第21頁/共24頁第20頁/共24頁4.2割線法基本思想:用割線逼近目標(biāo)函數(shù)的導(dǎo)函數(shù)的曲線,把割線的零點(diǎn)作為目標(biāo)函數(shù)的駐點(diǎn)的估計(jì).第22頁/共24頁第21頁/共24頁基本原理：第23頁/共24頁第22頁