放物線補間

放物線補間（連続放物線補間、（れんぞく）ほうぶつせんほかん、）とは、連続なの（極大・）極小値を求める手法である。一変数関数では3つの異なる点、n 変数関数では 1+n(n+3)/2 個の点の放物線（二次多項式）の極値を保持し、各反復で最も前に求めた極値を新たな極値に置き換える。

 利点 
関数値のみを使用して極値に収束する場合のはおおよそ 1.325 である。この収束の速さは（直線探索のような）線形収束にとどまる方法よりも勝る。さらに関数の導関数の計算・近似する必要がないことから、放物線補間は導関数を求めるような（最急降下法・ニュートン法のような）手法の代わりに利用されている。

 欠点 
一方で放物線補間のみでは必ずしも（極値への）収束することが保証されていない。具体的には異なる3点が同一直線上に並んだ場合、新たに求めた放物線は退化して次の点を求めることができない。なおその関数の導関数を利用することができる場合は、ニュートン法を用いることで二次収束を示す。

 改良手法 
放物線補間と（黄金分割探索などの）堅牢性のある手法を交互に適用して新たな候補点を求めることで、収束の速さを保ったまま収束率を高めることができる。

 参考文献 

 関連項目 
  - 放物線によって極値でなく根を求める手法
 シンプソンの公式 - 放物線を用いて定積分を近似する

Category:数値解析
Category:最適化アルゴリズムとメソッド