Algorithm for finding roots of a function
ミュラー法は、 解を求めるアルゴリズム であり 、 形式 f ( x ) = 0 の方程式を解く 数値 手法です。1956 年に David E. Muller によって初めて発表されました。
ミュラー法は、 セカント法 の2次漸化式に類似した3 次漸化式 に従って進行します。セカント法では、 f のグラフ上で、最後の2回の反復近似値に対応する2点を通る直線を作成し、反復ごとにその直線の根を次の近似値として使用します。一方、ミュラー法では、最後の3回の反復近似値に対応する3点を使用し、これらの3点を通る 放物線 を作成し、反復ごとにその放物線の根を次の近似値として使用します。
導出 ミュラー法では、 根の3つの初期近似値、およびを使用し 、 x軸と 、、 およびを通る放物線との交点を考慮して 次の近似値を決定します x 0 , x 1 {\displaystyle x_{0},x_{1}} x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} ( x 0 , f ( x 0 ) ) {\displaystyle (x_{0},f(x_{0}))} ( x 1 , f ( x 1 ) ) {\displaystyle (x_{1},f(x_{1}))} ( x 2 , f ( x 2 ) ) {\displaystyle (x_{2},f(x_{2}))}
二次多項式を考える
P ( x ) = a ( x − x 2 ) 2 + b ( x − x 2 ) + c , {\displaystyle P(x)=a(x-x_{2})^{2}+b(x-x_{2})+c,} 1
、 および を通過します 。違いを定義してください ( x 0 , f ( x 0 ) ) {\displaystyle (x_{0},f(x_{0}))} ( x 1 , f ( x 1 ) ) {\displaystyle (x_{1},f(x_{1}))} ( x 2 , f ( x 2 ) ) {\displaystyle (x_{2},f(x_{2}))}
h 0 = x 1 − x 0 , h 1 = x 2 − x 1 {\displaystyle h_{0}=x_{1}-x_{0},\quad h_{1}=x_{2}-x_{1}}
そして δ 0 = f ( x 1 ) − f ( x 0 ) h 0 , δ 1 = f ( x 2 ) − f ( x 1 ) h 1 . {\displaystyle \delta _{0}={\frac {f(x_{1})-f(x_{0})}{h_{0}}},\quad \delta _{1}={\frac {f(x_{2})-f(x_{1})}{h_{1}}}.}
3つの点 、 をそれぞれ 式( 1 )に代入し、同時にとを解く と 、 ( x 0 , f ( x 0 ) ) {\displaystyle (x_{0},f(x_{0}))} ( x 1 , f ( x 1 ) ) {\displaystyle (x_{1},f(x_{1}))} ( x 2 , f ( x 2 ) ) {\displaystyle (x_{2},f(x_{2}))} a , b {\displaystyle a,b} c {\displaystyle c}
a = δ 1 − δ 0 h 1 + h 0 , b = a h 1 + δ 1 , c = f ( x 2 ) {\displaystyle a={\frac {\delta _{1}-\delta _{0}}{h_{1}+h_{0}}},\quad b=ah_{1}+\delta _{1},\quad c=f(x_{2})}
次に、この二次方程式の公式を（ １ ）に適用して、 次のように
決定する。 x 3 {\displaystyle x_{3}}
x 3 − x 2 = − 2 c b ± b 2 − 4 a c . {\displaystyle x_{3}-x_{2}={\frac {-2c}{b\pm {\sqrt {b^{2}-4ac}}}}.} 根号の前の符号は の符号と一致するように選択され、 次の反復が に最も近くなることを保証する 。 b {\displaystyle b} x 2 {\displaystyle x_{2}}
x 3 = x 2 − 2 c b + sign ( b ) b 2 − 4 a c . {\displaystyle x_{3}=x_{2}-{\frac {2c}{b+\operatorname {sign} (b){\sqrt {b^{2}-4ac}}}}.} が決定されると 、このプロセスが繰り返されます。分母の根号表現のため、前の反復がすべて実数であっても、反復は複素数になる可能性があることに注意してください。これは、実数から開始した場合、反復が実数のままになる セカント法 、 シディの一般化セカント法、 ニュートン法 などの他の根探索アルゴリズムと は対照的です。反復が複素数であることは、問題によっては利点（複素根を探している場合）または欠点（すべての根が実数であることがわかっている場合）になる可能性があります。 x 3 {\displaystyle x_{3}}
この方法は、衝突検出など、最も近いルートではなく、 を に置き換えることでより小さいルートが重要になるシナリオに簡単に採用できます 。 sign ( b ) {\displaystyle \operatorname {sign} (b)} sign ( − a ) {\displaystyle \operatorname {sign} (-a)}
x 3 = x 2 − 2 c b − sign ( a ) b 2 − 4 a c . {\displaystyle x_{3}=x_{2}-{\frac {2c}{b-\operatorname {sign} (a){\sqrt {b^{2}-4ac}}}}.}
収束速度 良好な関数の場合、 ミュラー法の 収束次数は約1.839で、 トリボナッチ定数と正確に一致します。これは、 セカント法 では約1.618で、 黄金比 と正確に一致し、 ニュートン法 ではちょうど2です 。したがって、セカント法はミュラー法よりも反復あたりの進歩が少なく、ニュートン法はより進歩します
より正確には、ξがf の単根を表す場合 （つまり f (ξ) = 0かつ f '(ξ) ≠ 0）、 f は3回連続微分可能であり、初期推定値 x 0 、 x 1 、 x 2 がξに十分近い値とされると、反復は
lim k → ∞ | x k − ξ | | x k − 1 − ξ | μ = | f ‴ ( ξ ) 6 f ′ ( ξ ) | ( μ − 1 ) / 2 , {\displaystyle \lim _{k\to \infty }{\frac {|x_{k}-\xi |}{|x_{k-1}-\xi |^{\mu }}}=\left|{\frac {f'''(\xi )}{6f'(\xi )}}\right|^{(\mu -1)/2},} ここで、μ ≈ 1.84 は 、トリボナッチ定数の定義式である の正の解です。 x 3 − x 2 − x − 1 = 0 {\displaystyle x^{3}-x^{2}-x-1=0}
ミュラー法は、各反復で 得られた最後の 3 つの点 f ( x k -1 )、 f ( x k -2 )、 f ( x k -3 ) に放物線、つまり 2 次 多項式を当てはめます。これを一般化して、 k 番目 の 反復で最後の m +1 点に m次多項式 p k,m ( x )を当てはめることができます。 この表記法では、 放物線 y k はp k ,2 と表されます。次数 m は 1 以上でなければなりません。次の近似値 x k は、 p k,m の根の 1 つ、つまり p k,m ( x )=0の解の 1 つになります 。 m =1 とするとセカント法になり、 m =2 とするとミュラー法になります。
ミュラーは、このように生成されたシーケンス { x k } は、 の 正の解で あるμ m の順序で根 ξ に収束することを計算しました 。 x m + 1 − x m − x m − 1 − ⋯ − x − 1 = 0 {\displaystyle x^{m+1}-x^{m}-x^{m-1}-\dots -x-1=0}
mが無限大に近づくにつれて、方程式の正解は2に近づきます。しかし、この方法はm >2の場合、m = 1またはm = 2の場合よりもはるかに困難です 。これは、3次以上の多項式の根を求めるのがはるかに難しいためです。もう一つの問題は、m > 2 の 場合 、 p k ,m のどの根を次の近似値 x k として選ぶべきかという明確な規定がないように見えることです 。
これらの困難は、多項式 p k,m を用いるシディの一般化正割法 によって克服されます。この方法では、 p k,m ( x )=0を解く代わりに、 p k,m のx k -1 における 導関数を用いて 次の近似値 x k を計算します。
参照
参考文献
アトキンソン、ケンドール・E. (1989). 数値解析入門 、第2版、セクション2.4. John Wiley & Sons、ニューヨーク. ISBN 0-471-50023-2 。 Burden, RLおよびFaires, JD著 『数値解析 』第4版、77ページ以降 Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「セクション9.5.2. Muller法」. 数値計算レシピ：科学計算の芸術 （第3版）. ニューヨーク：ケンブリッジ大学出版局. ISBN 978-0-521-88068-8 。
参考文献 大域収束を伴うブラケティング法の変種： Costabile, F.; Gualtieri, MI; Luceri, R. (2006年3月). 「Muller法の修正」. Calcolo . 43 (1): 39– 50. doi :10.1007/s10092-006-0113-9. S2CID 124772103
