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

會(huì)計(jì)學(xué)1ch一維搜索逼近法與求根法3逼近法3.1拋物線逼近法3.2三次插值法3.3牛頓法第2頁(yè)/共24頁(yè)第1頁(yè)/共24頁(yè)3.1拋物線逼近法3.1.1三點(diǎn)二次插值基本思想：利用插值函數(shù)逼近所需求解的目標(biāo)函數(shù)，把插值函數(shù)的極小點(diǎn)作為迭代點(diǎn)。初始三點(diǎn)的選取可以用進(jìn)退法得到。第3頁(yè)/共24頁(yè)第2頁(yè)/共24頁(yè)基本原理：第4頁(yè)/共24頁(yè)第3頁(yè)/共24頁(yè)第5頁(yè)/共24頁(yè)第4頁(yè)/共24頁(yè)第6頁(yè)/共24頁(yè)第5頁(yè)/共24頁(yè)3.1.2二點(diǎn)二次插值兩點(diǎn)的函數(shù)值加一點(diǎn)的導(dǎo)數(shù)值。如果函數(shù)可微并易于求出導(dǎo)函數(shù)時(shí)可以選用此方法。比較簡(jiǎn)單，不必預(yù)先確定上下界；不過(guò)函數(shù)如果單調(diào)時(shí)，得不到結(jié)果，需要限制迭代次數(shù)。第7頁(yè)/共24頁(yè)第6頁(yè)/共24頁(yè)第8頁(yè)/共24頁(yè)第7頁(yè)/共24頁(yè)兩點(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頁(yè)/共24頁(yè)第8頁(yè)/共24頁(yè)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頁(yè)/共24頁(yè)第9頁(yè)/共24頁(yè)3.3牛頓法基本原理算法框圖第11頁(yè)/共24頁(yè)第10頁(yè)/共24頁(yè)第12頁(yè)/共24頁(yè)第11頁(yè)/共24頁(yè)算法框圖初始λ,ε1,ε2〉0K=1停；解λk|f′(λk)|<ε1?|f″(λk)|>0?停；失敗k=k+1|λk+1-λk|<ε2?λk+1=λk–NYNYYN第13頁(yè)/共24頁(yè)第12頁(yè)/共24頁(yè)例子第14頁(yè)/共24頁(yè)第13頁(yè)/共24頁(yè)第15頁(yè)/共24頁(yè)第14頁(yè)/共24頁(yè)算法特點(diǎn)優(yōu)點(diǎn)：收斂速度較快，二階收斂。缺點(diǎn)：需要計(jì)算二階導(dǎo)數(shù)，計(jì)算量大；局部收斂，初始點(diǎn)選擇需要合適。第16頁(yè)/共24頁(yè)第15頁(yè)/共24頁(yè)4求根法4.1切線法4.2割線法第17頁(yè)/共24頁(yè)第16頁(yè)/共24頁(yè)4.1切線法基本思想:用切線逼近目標(biāo)函數(shù)導(dǎo)函數(shù)的曲線,把切線的零點(diǎn)作為目標(biāo)函數(shù)的駐點(diǎn)的估計(jì).第18頁(yè)/共24頁(yè)第17頁(yè)/共24頁(yè)基本原理第19頁(yè)/共24頁(yè)第18頁(yè)/共24頁(yè)算法特點(diǎn)優(yōu)點(diǎn)：步驟簡(jiǎn)單，收斂快，在相同的條件下比較少的迭代次數(shù)就能達(dá)到精度要求。缺點(diǎn)：用到二階導(dǎo)數(shù)，計(jì)算量大；初始點(diǎn)選擇需要合適。第20頁(yè)/共24頁(yè)第19頁(yè)/共24頁(yè)算法步驟第21頁(yè)/共24頁(yè)第20頁(yè)/共24頁(yè)4.2割線法基本思想:用割線逼近目標(biāo)函數(shù)的導(dǎo)函數(shù)的曲線,把割線的零點(diǎn)作為目標(biāo)函數(shù)的駐點(diǎn)的估計(jì).第22頁(yè)/共24頁(yè)第21頁(yè)/共24頁(yè)基本原理：第23頁(yè)/共24頁(yè)第22頁(yè)