放物線補間
 |
放物線補間（連続放物線補間、（れんぞく）ほうぶつせんほかん、英: (Successive) parabolic interpolation）とは、連続な単峰関数の（極大・）極小値を求める手法である。一変数関数では3つの異なる点、n 変数関数では 1+n(n+3)/2 個の点の放物線（二次多項式）の極値を保持し、各反復で最も前に求めた極値を新たな極値に置き換える。
利点
[編集]関数値のみを使用して極値に収束する場合の収束次数はおおよそ 1.325 である。この収束の速さは（直線探索のような）線形収束にとどまる方法よりも勝る。さらに関数の導関数の計算・近似する必要がないことから、放物線補間は導関数を求めるような（最急降下法・ニュートン法のような）手法の代わりに利用されている。
欠点
[編集]一方で放物線補間のみでは必ずしも（極値への）収束することが保証されていない。具体的には異なる3点が同一直線上に並んだ場合、新たに求めた放物線は退化して次の点を求めることができない。なおその関数の導関数を利用することができる場合は、ニュートン法を用いることで二次収束を示す。
改良手法
[編集]放物線補間と（黄金分割探索などの）堅牢性のある手法を交互に交互に適用して新たな候補点を求めることで、収束の速さを保ったまま収束率を高めることができる。
参考文献
[編集]Michael Heath (2002). Scientific Computing: An Introductory Survey (2nd ed.). New York: McGraw-Hill. ISBN 0-07-239910-4
