ミュラーの方法

ミュラー法は、f ( x ) = 0の形の方程式を解くための数値解法である根探索アルゴリズムです。これは、1956年にデイビッド・E・ミュラーによって初めて発表されました。

ミュラー法は、割線法の2次漸化式に類似した3次漸化式に従って進行します。割線法は、fのグラフ上の最後の2つの反復近似値に対応する2点を通る直線を構築し、各反復でその直線の根を次の近似値として使用しますが、対照的に、ミュラー法は、最後の3つの反復近似値に対応する3点を使用し、これらの3点を通る放物線を構築し、各反復でその放物線の根を次の近似値として使用します。

ミュラー法は、根の3つの初期近似値を使用します。${\displaystyle x_{0},x_{1}}$そして​${\displaystyle x_{2}}$⁠、そして次の近似値を決定します${\displaystyle x_{3}}$x軸と放物線の交点を考慮すると、${\displaystyle (x_{0},f(x_{0}))}$⁠、${\displaystyle (x_{1},f(x_{1}))}$そして​${\displaystyle (x_{2},f(x_{2}))}$⁠ .

二次多項式を考える $${\displaystyle P(x)=a(x-x_{2})^{2}+b(x-x_{2})+c,}$$

通過する${\displaystyle (x_{0},f(x_{0}))}$⁠、${\displaystyle (x_{1},f(x_{1}))}$そして​${\displaystyle (x_{2},f(x_{2}))}$表記を簡略化するために、差分を定義します。

$${\displaystyle h_{0}=x_{1}-x_{0},\quad h_{1}=x_{2}-x_{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つの点をそれぞれ代入すると${\displaystyle (x_{0},f(x_{0}))}$⁠、${\displaystyle (x_{1},f(x_{1}))}$そして${\displaystyle (x_{2},f(x_{2}))}$の中へ${\displaystyle P(x)}$そして同時に解く${\displaystyle a,b}$そして${\displaystyle c}$与える

$${\displaystyle a={\frac {\delta _{1}-\delta _{0}}{h_{1}+h_{0}}},\quad b=ah_{1}+\delta _{1},\quad c=f(x_{2}).}$$

次に二次方程式の解の公式を適用します。${\displaystyle P(x)}$決定する${\displaystyle x_{3}}$として

$${\displaystyle x_{3}-x_{2}={\frac {-2c}{b\pm {\sqrt {b^{2}-4ac}}}}.}$$

根号の前の符号は、${\displaystyle b}$次の反復が に最も近いことを保証する⁠${\displaystyle x_{2}}$⁠、

$${\displaystyle x_{3}=x_{2}-{\frac {2c}{b+\operatorname {sign} (b){\sqrt {b^{2}-4ac}}}}.}$$

一度${\displaystyle x_{3}}$が決定したら、このプロセスを繰り返します。分母に根号が含まれているため、前の反復がすべて実数であっても、反復が複素数になる可能性があることに注意してください。これは、実数から開始すれば反復が実数のままとなる割線法、Sidiの一般化割線法、ニュートン法などの他の根探索アルゴリズムとは対照的です。反復が複素数になることは、問題によっては利点（複素根を探している場合）にも欠点（すべての根が実数であることがわかっている場合）にもなり得ます。

この方法は、衝突検出などのシナリオに容易に適用でき、最も近いルートではなく、より小さいルートを置き換えることで、${\displaystyle \operatorname {sign} (b)}$と${\displaystyle \operatorname {sign} (-a)}$: $${\displaystyle x_{3}=x_{2}-{\frac {2c}{b-\operatorname {sign} (a){\sqrt {b^{2}-4ac}}}}.}$$

以下の擬似コードは、方程式f ( x ) = 0の根を近似するためのミュラー法を記述しています。このコードは推定値を返します。${\displaystyle x_{3}}$満たす​${\displaystyle |x_{3}-x_{2}|<\varepsilon }$⁠、そこで${\displaystyle \varepsilon }$はユーザーが指定する許容値です。

入力:関数f、初期近似値x0、x1、x2、許容誤差ε、最大反復回数Nmaxをn = 0 からNmaxまで繰り返すh0 ← x1 − x0 h1 ← x2 − x1 δ0 ← ( f ( x1 ) − f ( x0 )) / h0 δ1 ← ( f ( x2 ) − f ( x1 )) / h1 a ← ( δ1 − δ0 ) / ( h1 + h0 ) b ← a · h1 + δ1 c ← f ( x2 ) if b ≥ 0 then denominator ← b + sqrt( b ² − 4· a · c ) else denominator ← b − sqrt( b ² − 4· a · c ) end if x3 ← x2 − 2· c / denominator if | x3 − x2 | < ε then return x3 end if x0 ← x1 x1 ← x2 x2 ← x3 end for return x3

多項式の解を求めるとしよう $${\displaystyle f(x)=-x^{3}-x+7\,.}$$

初期推定値を用いたミュラー法の適用${\displaystyle x_{0}=1}$⁠、${\displaystyle x_{1}=2}$そして${\displaystyle x_{2}=3}$そして寛容さ$10⁻⁹$次のような近似値が得られます。

必要な許容誤差内で、ミュラー法は解を生成する。${\displaystyle 1.7392038612200968}$6回目の反復で。

初期推定値を変更することで、ミュラー法は複雑な解も生成できます。ミュラー法を再度適用しますが、初期推定値は⁠${\displaystyle x_{0}=-1}$⁠、${\displaystyle x_{1}=-2}$そして${\displaystyle x_{2}=-3}$そして寛容さ${\displaystyle 10^{-9}}$次のような近似値が得られます。

ミュラー法は、要求された許容誤差内で複素解を生成する。${\displaystyle -0.8696019306084998-1.8079332269621338i}$8回目の反復で。

実数値関数を仮定する${\displaystyle f(x)}$ルートは にあります${\displaystyle x=\alpha }$⁠。 $${\displaystyle e_{n}=x_{n}-\alpha }$$ のエラーを表す${\displaystyle n^{th}}$ミュラー法の反復。定義により、 $${\displaystyle e_{n+1}=Ke_{n}^{p}}$$ どこ${\displaystyle p}$は収束次数です。したがって、 $${\displaystyle e_{n}=Ke_{n-1}^{p}}$$ そして $${\displaystyle e_{n-1}=Ke_{n-2}^{p}}$$ これにより $${\displaystyle e_{n-1}\sim e_{n}^{1/p}}$$ そして $${\displaystyle e_{n-2}\sim e_{n}^{1/p^{2}}.}$$ 根元付近${\displaystyle x=\alpha }$テイラーの定理によれ ば、$${\displaystyle f(x)=f'(\alpha )(x-\alpha )+{\frac {f''(\alpha )}{2}}(x-\alpha )^{2}+R(x)}$$ どこ${\displaystyle R(x)}$は剰余項であり、次のように定義される。 $${\displaystyle R(x)={\frac {f'''(\xi )}{6}}(x-\alpha )^{3}}$$ 一部の人にとって${\displaystyle \xi }$間${\displaystyle x}$そして​${\displaystyle \alpha }$⁠。ミュラー法の3回の連続反復を用いて、${\displaystyle x=x_{n}}$⁠、${\displaystyle x=x_{n-1}}$そして${\displaystyle x=x_{n-2}}$ルートで評価すると

$${\displaystyle R(\alpha )=O(e_{n}e_{n-1}e_{n-2})}$$ または $${\displaystyle e_{n+1}=O(e_{n}e_{n-1}e_{n-2})}$$ 次の反復は、補間二次関数をゼロに設定することによって得られるため、漸近的には、 $${\displaystyle e_{n+1}=Ke_{n}e_{n-1}e_{n-2}.}$$ 使用 $${\displaystyle e_{n-1}\sim e_{n}^{1/p}}$$ そして $${\displaystyle e_{n-2}\sim e_{n}^{1/p^{2}}}$$ 与える $${\displaystyle e_{n+1}=Ke_{n}^{1+{\frac {1}{p}}+{\frac {1}{p^{2}}}}.}$$

定義により、 $${\displaystyle e_{n+1}=Ke_{n}^{p}}$$ 指数を等しくすると $${\displaystyle p=1+{\frac {1}{p}}+{\frac {1}{p^{2}}}}$$ これは次のように並べ替えることができます

$${\displaystyle p^{3}-p^{2}-p-1=0.}$$

この方程式を解くと、${\displaystyle p\approx 1.839}$したがって、ミュラー法の収束次数は、トリボナッチ数列の定数と正確に一致します。これは、割線法の約1.618（黄金比と正確に一致）や、ニュートン法の2と正確にます。つまり、割線法はミュラー法よりも反復あたりの進捗が少なく、ニュートン法の方が進捗が多いということです。

より正確には、${\displaystyle \alpha }$は単一の根を表します${\displaystyle f(x)}$そして${\displaystyle f'(\alpha )\neq 0}$そして${\displaystyle f(x)}$初期推定値が 3 回連続微分可能であれば、${\displaystyle x_{0}}$⁠、${\displaystyle x_{1}}$そして${\displaystyle x_{2}}$十分に近くで撮影されている${\displaystyle \alpha }$⁠、すると反復は以下を満たす $${\displaystyle \lim _{k\to \infty }{\frac {|x_{k}-\alpha |}{|x_{k-1}-\alpha |^{\mu }}}=\left|{\frac {f'''(\alpha )}{6f'(\alpha )}}\right|^{(\mu -1)/2}}$$

どこ${\displaystyle \mu \approx 1.84}$はの正の解です${\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で根 ξ に収束することを計算した。ここでμ _{m は}⁠の正の解である。${\displaystyle x^{m+1}-x^{m}-x^{m-1}-\dots -x-1=0}$⁠ .

m が無限大に近づくと、方程式の正の解は 2 に近づきます。ただし、m > 2 の場合、次数 3 以上の多項式の根を決定するのがはるかに難しいため、m = 1 または m = 2 の場合よりもこの方法ははるかに困難です。もう 1 つの問題は、m > 2の場合、p k、mのどの根_を次の近似x _kとして選択するかについての規定がないように見えることです。

これらの困難は、多項式p _{k , m}も使用するSidi の一般化割線法によって克服されます。この方法では、 p _{k , m} ( x ) = 0を解こうとする代わりに、次の近似値x _{k は}、 x _{k −1}におけるp _{k , m}の導関数の助けを借りて計算されます。

• ハレー法（3次収束）
• ハウスホルダー法には、ニュートン法、ハレー法、および高次収束法が含まれる。

• アトキンソン、ケンドール E. (1989). 『数値解析入門』第2版、第2.4節。ジョン・ワイリー・アンド・サンズ、ニューヨーク。ISBN 0-471-50023-2。
• Burden, RL および Faires, JD数値解析、第 4 版、77 ページ以降。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「第9.5.2節 ミュラー法」 . Numerical Recipes: The Art of Scientific Computing (第3 版). ニューヨーク: Cambridge University Press. 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 .