ハレー法

数値解析 において、ハレー法は、連続した2次導関数を持つ1つの実変数の関数に使用される根探索アルゴリズムです。エドモンド・ハレーは、現在彼の名前で呼ばれているこの方法を導入したイギリスの数学者および天文学者でした。

このアルゴリズムは、ハウスホルダー法の中ではニュートン法に次ぐ2番目のものである。ニュートン法と同様に、このアルゴリズムは根への近似値のシーケンスを反復的に生成し、根への収束率は3次である。この方法には多次元バージョンも存在する。^[1]

ハレー法は関数を線形近似するニュートン法やセカント法、あるいは関数を二次近似するミュラー法とは対照的に、関数の線形パデ近似の根を正確に求めます。^[2]

ハレー法は、非線形方程式f ( x ) = 0を解く数値アルゴリズムです。この場合、関数f は1 つの実変数の関数でなければなりません。この方法は、一連の反復処理で構成されます。

${\displaystyle x_{n+1}=x_{n}-{\frac {2f(x_{n})f'(x_{n})}{2{[f'(x_{n})]}^{2}-f(x_{n})f''(x_{n})}}}$

初期推測値x ₀から始まる。^[3]

fが 3 回連続的に微分可能な関数であり、a がfの零点であるがその導関数の零点ではない場合、 aの近傍において、反復x _{n は}次を満たします。

${\displaystyle |x_{n+1}-a|\leq K\cdot {|x_{n}-a|}^{3},{\text{ ある }}K>0 の場合。}$

これは、初期推定値が十分に近い場合、反復はゼロに収束し、収束は3次的であることを意味します。^[4]

次の代替定式化は、ハレー法とニュートン法の類似性を示しています。この式は1 回だけ計算され、簡略化できる 場合に特に便利です。${\displaystyle f(x_{n})/f'(x_{n})}$${\displaystyle f''(x_{n})/f'(x_{n})}$

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})-{\frac {f(x_{n})}{f'(x_{n})}}{\frac {f''(x_{n})}{2}}}}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\left[1-{\frac {f(x_{n})}{f'(x_{n})}}\cdot {\frac {f''(x_{n})}{2f'(x_{n})}}\right]^{-1}.}$

2 次導関数がゼロに非常に近い場合、ハレー法の反復はニュートン法の反復とほぼ同じになります。

機能について考える

${\displaystyle g(x)={\frac {f(x)}{\sqrt {|f'(x)|}}}.}$

fの任意の根r は、その導関数の根ではない場合、 gの根である(つまり、の場合)。また、 gの任意の根r は、 rにおけるfの導関数が無限大でない限り、fの根である。gにニュートン法を適用すると、次の式が得られる 。${\displaystyle g(r)=0}$${\displaystyle f(r)=0\neq {\sqrt {|f'(r)|}}}$

${\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}}$

と

${\displaystyle g'(x)={\frac {2[f'(x)]^{2}-f(x)f''(x)}{2f'(x){\sqrt {|f'(x)|}}}},}$

そして結果は次のようになる。f ′( c ) = 0 の場合、 g ( c )は未定義となるため、これをcに適用することはできないことに注意。 ^{[さらなる説明が必要]}

a はfの根であるが、その導関数の根ではないとします。また、 fの 3 次導関数が存在し、 aの近傍で連続しており、x _{n が}その近傍にあるとします。この場合、テイラーの定理は次のことを意味します。

${\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(x_{n})}{2}}(a-x_{n})^{2}+{\frac {f'''(\xi )}{6}}(a-x_{n})^{3}}$

そしてまた

${\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(\eta )}{2}}(a-x_{n})^{2},}$

ここで、ξ と η はaとx _{n の}間の数値です。最初の式に を掛け、2 番目の式を 回数引くと次のようになります。 ${\displaystyle 2f'(x_{n})}$${\displaystyle f''(x_{n})(a-x_{n})}$

${\displaystyle {\begin{aligned}0&=2f(x_{n})f'(x_{n})+2[f'(x_{n})]^{2}(a-x_{n})+f'(x_{n})f''(x_{n})(a-x_{n})^{2}+{\frac {f'(x_{n})f'''(\xi )}{3}}(a-x_{n})^{3}\\&\qquad -f(x_{n})f''(x_{n})(a-x_{n})-f'(x_{n})f''(x_{n})(a-x_{n})^{2}-{\frac {f''(x_{n})f''(\eta )}{2}}(a-x_{n})^{3}.\end{aligned}}}$

用語をキャンセルして再編成すると、次のようになります。 ${\displaystyle f'(x_{n})f''(x_{n})(a-x_{n})^{2}}$

${\displaystyle 0=2f(x_{n})f'(x_{n})+\left(2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})\right)(a-x_{n})+\left({\frac {f'(x_{n})f'''(\xi )}{3}}-{\frac {f''(x_{n})f''(\eta )}{2}}\right)(a-x_{n})^{3}.}$

2番目の項を左辺に置いて、

${\displaystyle 2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}$

取得するため：

${\displaystyle a-x_{n}={\frac {-2f(x_{n})f'(x_{n})}{2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}}-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{6(2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n}))}}(a-x_{n})^{3}.}$

したがって：

${\displaystyle a-x_{n+1}=-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{12[f'(x_{n})]^{2}-6f(x_{n})f''(x_{n})}}(a-x_{n})^{3}.}$

x _n → aのときの右側の係数の極限は次のとおりです。

${\displaystyle -{\frac {2f'(a)f'''(a)-3f''(a)f''(a)}{12[f'(a)]^{2}-6f(a)f''(a)}}.}$

K をこの絶対値より少し大きくすると、式の両辺の絶対値を取り、係数の絶対値をa付近の上限で置き換えると次の式が得られます。

${\displaystyle |a-x_{n+1}|\leq K|a-x_{n}|^{3}}$

それが証明されるべきことだった。

要約すると、

${\displaystyle \Delta x_{i+1}={\frac {3(f'')^{2}-2f'f'''}{12(f')^{2}}}(\Delta x_{i})^{3}+O[\Delta x_{i}]^{4},\qquad \Delta x_{i}\triangleq x_{i}-a.}$^[5]

ハレーは実際に2つの3次の根を求める方法を開発した。上記の除算のみを使用する方法はハレーの有理法と呼ばれる。2つ目の「無理数」法では平方根も使用する: ^{[6] [7] [8]}

${\displaystyle x_{n+1}=x_{n}-{\frac {f'(x_{n})-{\sqrt {[f'(x_{n})]^{2}-2f(x_{n})f''(x_{n})}}}{f''(x_{n})}}}$

^{この反復法は、分母が小さく、割り算が簡単であるという理由で、ハリー[7]}によって有理法よりも「当然好まれた」。2 つ目の利点は、有理法の誤差の約半分になる傾向があり、反復するほど利点が倍増することです。コンピューター上では、1 つの遅い演算 (除算と平方根) ではなく 2 つの遅い演算があるため、遅く見えるかもしれませんが、現代のコンピューターでは、命令パイプラインを介して分母の逆数を平方根と同時に計算できるため、各反復のレイテンシはほとんど変わりません。^{[8] : 24}

• Weisstein, Eric W.「ハレー法」。MathWorld。
• ニュートン法と高次反復、パスカル・セバとザビエル・グルドン、2001年（このサイトには、より見やすい数式表示のためのポストスクリプト版へのリンクがあります）