Class of mathematical root-finding algorithm
数学 、特に 数値解析 において 、 ハウスホルダー法は 、ある階数 d + 1までの連続導関数を持つ実変数1変数関数に用いられる 求根アルゴリズム の一種です。これらの方法はそれぞれ、 階数 と呼ばれる数値 d によって特徴付けられます 。このアルゴリズムは反復的であり、 収束階数は d + 1 です。
これらの方法は、アメリカの数学者 アルストン・スコット・ハウスホルダーにちなんで名付けられました。d = 1 の場合は ニュートン法、 d = 2 の場合は ハレー法 に相当し ます 。
方法 ハウスホルダー法は、方程式 f ( x ) = 0 を解く数値アルゴリズムです。この場合、関数 f は1つの実変数の関数でなければなりません。この方法は、一連の反復計算から構成されます。
x n + 1 = x n + d ( 1 / f ) ( d − 1 ) ( x n ) ( 1 / f ) ( d ) ( x n ) {\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}
初期推測値 x 0 から始まる。
f が d + 1 回連続的に 微分可能な関数 であり、 aが f の零点であるがその導関数の零点ではない 場合、 a の近傍において 、反復 x n は次式を満たす: [ 引用が必要 ]
| x n + 1 − a | ≤ K ⋅ | x n − a | d + 1 , {\displaystyle |x_{n+1}-a|\leq K\cdot {|x_{n}-a|}^{d+1},} 一部の人にとって K > 0. {\displaystyle K>0.}
これは、初期推定値が十分に近い場合、反復はゼロに収束し、その収束は d + 1 次以上であることを意味します。さらに、 に十分近い場合 、 ある に対して と なることがよくあります 。特に、 x n + 1 − a ≈ C ( x n − a ) d + 1 {\displaystyle x_{n+1}-a\approx C(x_{n}-a)^{d+1}} C ≠ 0 {\displaystyle C\neq 0}
d + 1 が偶数で C > 0 の場合、 a への収束は a より大きい値からになります 。 d + 1 が偶数で C < 0 の場合、 a への収束は a 未満の値からになります 。 d + 1 が奇数で C > 0 の場合、 a への収束は 開始側からになります。 d + 1 が奇数で C < 0 の場合、 a への収束は 交互に行われます。 これらの手法は収束順序が優れているにもかかわらず、大きなd に対する計算量の増加に見合った精度の向上が得られないため、広く利用されていない 。 オストロフスキー指数は、 反復回数ではなく関数評価回数における誤差の減少を表す。
多項式の場合、ホーナー法 を用いて x n における f の 最初の d導関数を評価するには、 d + 1 回 の多項式評価が必要です 。 n回の反復で n ( d + 1 ) 回の評価を 行うと、誤差指数は ( d + 1) n となるため、1回の関数評価の指数は 、 d = 1、2、3、4 の場合に数値的に 1.4142 、 1.4422 、 1.4142 、 1.3797 となり、それ以降は低下します。この基準によれば、 d =2 の 場合（ ハレー法）が d の最適値です 。 d + 1 d + 1 {\displaystyle {\sqrt[{d+1}]{d+1}}} 一般関数の場合、自動微分法 のテイラー演算を用いた導関数評価は、 ( d + 1)( d + 2)/2回の 関数評価に相当する 。したがって、1回の関数評価で誤差は の指数だけ減少する。 これは ニュートン法では 、 ハレー法では であり、高階法では 1 または線形収束に近づく。 d + 1 ( d + 1 ) ( d + 2 ) 2 {\displaystyle {\sqrt[{\frac {(d+1)(d+2)}{2}}]{d+1}}} 2 3 ≈ 1.2599 {\displaystyle {\sqrt[{3}]{2}}\approx 1.2599} 3 6 ≈ 1.2009 {\displaystyle {\sqrt[{6}]{3}}\approx 1.2009}
モチベーション
最初のアプローチ fが a の近傍で解析的で 、 f ( a ) = 0 で あるとします 。すると、 fは a で テイラー級数 を持ち 、その 定数項 はゼロになります。この定数項がゼロなので、関数 f ( x ) / ( x − a )は a でテイラー級数を持ち、 f ′ ( a ) ≠ 0 の とき 、その定数項はゼロになりません。その定数項がゼロでないため、逆数 ( x − a ) / f ( x )は a でテイラー級数を持ち 、と書き、 その定数項 c 0 はゼロになりません。そのテイラー級数を使用して、次のように書くことができます。 d 次導関数
を計算すると、 k = 1, ..., d の項は、 大文字の O 表記 を使用して、 都合よく消えること
に注意してください。したがって、 x = x n に追加して、 a により近い x n +1 の値を取得する 補正項は 、次
のようになります。 したがって、は になります 。 ∑ k = 0 ∞ c k ( x − a ) k k ! {\displaystyle \sum _{k=0}^{\infty }{\frac {c_{k}(x-a)^{k}}{k!}}} 1 f = c 0 x − a + ∑ k = 1 ∞ c k ( x − a ) k − 1 k ( k − 1 ) ! . {\displaystyle {\frac {1}{f}}={\frac {c_{0}}{x-a}}+\sum _{k=1}^{\infty }{\frac {c_{k}(x-a)^{k-1}}{k~(k-1)!}}\,.} ( 1 f ) ( d ) = ( − 1 ) d d ! c 0 ( x − a ) d + 1 + ∑ k = d + 1 ∞ c k ( x − a ) k − d − 1 k ( k − d − 1 ) ! {\displaystyle \left({\frac {1}{f}}\right)^{(d)}={\frac {(-1)^{d}d!~c_{0}}{(x-a)^{d+1}}}+\sum _{k=d+1}^{\infty }{\frac {c_{k}(x-a)^{k-d-1}}{k~(k-d-1)!}}} = ( − 1 ) d d ! c 0 ( x − a ) d + 1 ( 1 + 1 ( − 1 ) d d ! c 0 ∑ k = d + 1 ∞ c k ( x − a ) k k ( k − d − 1 ) ! ) {\displaystyle ={\frac {(-1)^{d}d!~c_{0}}{(x-a)^{d+1}}}\left(1+{\frac {1}{(-1)^{d}d!~c_{0}}}\sum _{k=d+1}^{\infty }{\frac {c_{k}(x-a)^{k}}{k~(k-d-1)!}}\right)} = ( − 1 ) d d ! c 0 ( x − a ) d + 1 ( 1 + O ( ( x − a ) d + 1 ) ) , {\displaystyle ={\frac {(-1)^{d}d!~c_{0}}{(x-a)^{d+1}}}\left(1+{\mathcal {O}}\left((x-a)^{d+1}\right)\right)\,,} d ( 1 / f ) ( d − 1 ) ( 1 / f ) ( d ) = d ( − 1 ) d − 1 ( d − 1 ) ! c 0 ( − 1 ) d d ! c 0 ( x − a ) ( 1 + O ( ( x − a ) d ) 1 + O ( ( x − a ) d + 1 ) ) {\displaystyle d~{\frac {(1/f)^{(d-1)}}{(1/f)^{(d)}}}=d~{\frac {(-1)^{d-1}(d-1)!~c_{0}}{(-1)^{d}d!~c_{0}}}(x-a)\left({\frac {1+{\mathcal {O}}\left((x-a)^{d}\right)}{1+{\mathcal {O}}\left((x-a)^{d+1}\right)}}\right)} = − ( ( x − a ) + O ( ( x − a ) d + 1 ) ) . {\displaystyle =-\left((x-a)+{\mathcal {O}}\left((x-a)^{d+1}\right)\right)\,.} x + d ( 1 / f ) ( d − 1 ) ( 1 / f ) ( d ) {\displaystyle x+d~{\frac {(1/f)^{(d-1)}}{(1/f)^{(d)}}}} a + O ( ( x − a ) d ) {\displaystyle a+{\mathcal {O}}\left((x-a)^{d}\right)}
2番目のアプローチ x = a が単根である とする。すると、 x = a の 近傍において、 (1/ f )( x )は 有理型関数 となる。 テイラー展開 : が
、 f の他のどの零点よりも a に近い 点 b の周りにあると仮定する 。 ケーニッヒの定理 により、次式が成立する。 ( 1 / f ) ( x ) = ∑ d = 0 ∞ ( 1 / f ) ( d ) ( b ) d ! ( x − b ) d {\displaystyle (1/f)(x)=\sum _{d=0}^{\infty }{\frac {(1/f)^{(d)}(b)}{d!}}(x-b)^{d}} a − b = lim d → ∞ ( 1 / f ) ( d − 1 ) ( b ) ( d − 1 ) ! ( 1 / f ) ( d ) ( b ) d ! = d ( 1 / f ) ( d − 1 ) ( b ) ( 1 / f ) ( d ) ( b ) . {\displaystyle a-b=\lim _{d\rightarrow \infty }{\frac {\frac {(1/f)^{(d-1)}(b)}{(d-1)!}}{\frac {(1/f)^{(d)}(b)}{d!}}}=d{\frac {(1/f)^{(d-1)}(b)}{(1/f)^{(d)}(b)}}.}
これらは、ハウスホルダー反復法が収束性の高い反復法である可能性を示唆しています。収束の実際の証明もこれらの考えに基づいています。
低次の方法 1次のハウスホルダー法は、次の理由から ニュートン法と まったく同じです。 x n + 1 = x n + 1 ( 1 / f ) ( x n ) ( 1 / f ) ( 1 ) ( x n ) = x n + 1 f ( x n ) ⋅ ( − f ′ ( x n ) f ( x n ) 2 ) − 1 = x n − f ( x n ) f ′ ( x n ) . {\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+1\,{\frac {\left(1/f\right)(x_{n})}{\left(1/f\right)^{(1)}(x_{n})}}\\[.7em]=&x_{n}+{\frac {1}{f(x_{n})}}\cdot \left({\frac {-f'(x_{n})}{f(x_{n})^{2}}}\right)^{-1}\\[.7em]=&x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.\end{array}}}
2次のハウスホルダー法では 、恒等式とが となるため、 ハレー 法 が 得られます。
最後の行は、 点 におけるニュートン反復法の更新です 。この行は、単純なニュートン法との違いを示すために追加されました。 ( 1 / f ) ′ ( x ) = − f ′ ( x ) f ( x ) 2 {\displaystyle \textstyle (1/f)'(x)=-{\frac {f'(x)}{f(x)^{2}}}\ } ( 1 / f ) ″ ( x ) = − f ″ ( x ) f ( x ) 2 + 2 f ′ ( x ) 2 f ( x ) 3 {\displaystyle \textstyle \ (1/f)''(x)=-{\frac {f''(x)}{f(x)^{2}}}+2{\frac {f'(x)^{2}}{f(x)^{3}}}} x n + 1 = x n + 2 ( 1 / f ) ′ ( x n ) ( 1 / f ) ″ ( x n ) = x n + − 2 f ( x n ) f ′ ( x n ) − f ( x n ) f ″ ( x n ) + 2 f ′ ( x n ) 2 = x n − f ( x n ) f ′ ( x n ) f ′ ( x n ) 2 − 1 2 f ( x n ) f ″ ( x n ) = x n + h n 1 1 + 1 2 ( f ″ / f ′ ) ( x n ) h n . {\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+2\,{\frac {\left(1/f\right)'(x_{n})}{\left(1/f\right)''(x_{n})}}\\[1em]=&x_{n}+{\frac {-2f(x_{n})\,f'(x_{n})}{-f(x_{n})f''(x_{n})+2f'(x_{n})^{2}}}\\[1em]=&x_{n}-{\frac {f(x_{n})f'(x_{n})}{f'(x_{n})^{2}-{\tfrac {1}{2}}f(x_{n})f''(x_{n})}}\\[1em]=&x_{n}+h_{n}\;{\frac {1}{1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}}.\end{array}}} h n = − f ( x n ) f ′ ( x n ) {\displaystyle h_{n}=-{\tfrac {f(x_{n})}{f'(x_{n})}}} x n {\displaystyle x_{n}}
3 次法は、 1/ f の 3 次導関数の恒等式から得られ 、式は 次のようになります。 ( 1 / f ) ‴ ( x ) = − f ‴ ( x ) f ( x ) 2 + 6 f ′ ( x ) f ″ ( x ) f ( x ) 3 − 6 f ′ ( x ) 3 f ( x ) 4 {\displaystyle \textstyle (1/f)'''(x)=-{\frac {f'''(x)}{f(x)^{2}}}+6{\frac {f'(x)\,f''(x)}{f(x)^{3}}}-6{\frac {f'(x)^{3}}{f(x)^{4}}}} x n + 1 = x n + 3 ( 1 / f ) ″ ( x n ) ( 1 / f ) ‴ ( x n ) = x n − 6 f ( x n ) f ′ ( x n ) 2 − 3 f ( x n ) 2 f ″ ( x n ) 6 f ′ ( x n ) 3 − 6 f ( x n ) f ′ ( x n ) f ″ ( x n ) + f ( x n ) 2 f ‴ ( x n ) = x n + h n 1 + 1 2 ( f ″ / f ′ ) ( x n ) h n 1 + ( f ″ / f ′ ) ( x n ) h n + 1 6 ( f ‴ / f ′ ) ( x n ) h n 2 {\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+3\,{\frac {\left(1/f\right)''(x_{n})}{\left(1/f\right)'''(x_{n})}}\\[1em]=&x_{n}-{\frac {6f(x_{n})\,f'(x_{n})^{2}-3f(x_{n})^{2}f''(x_{n})}{6f'(x_{n})^{3}-6f(x_{n})f'(x_{n})\,f''(x_{n})+f(x_{n})^{2}\,f'''(x_{n})}}\\[1em]=&x_{n}+h_{n}{\frac {1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}{1+(f''/f')(x_{n})\,h_{n}+{\frac {1}{6}}(f'''/f')(x_{n})\,h_{n}^{2}}}\end{array}}}
例 ニュートンがニュートン・ラプソン・シンプソン法で最初に解いた問題は、多項式方程式 でした 。彼は、2 に近い解が存在するはずであることを観察しました。y = x + 2 を 置き換えると、方程式は になります 。逆関数のテイラー級数は で始まります 。x = 0 において様々な次数のハウスホルダー法を適用した結果は、 後者のべき級数の隣接する係数を除算することによっても得られます 。 最初の次数については、1 回の反復ステップだけで次の値が得られます。例えば、3 次の場合では です 。 y 3 − 2 y − 5 = 0 {\displaystyle y^{3}-2y-5=0} 0 = f ( x ) = − 1 + 10 x + 6 x 2 + x 3 {\displaystyle 0=f(x)=-1+10x+6x^{2}+x^{3}} 1 / f ( x ) = − 1 − 10 x − 106 x 2 − 1121 x 3 − 11856 x 4 − 125392 x 5 − 1326177 x 6 − 14025978 x 7 − 148342234 x 8 − 1568904385 x 9 − 16593123232 x 10 + O ( x 11 ) {\displaystyle {\begin{array}{rl}1/f(x)=&-1-10\,x-106\,x^{2}-1121\,x^{3}-11856\,x^{4}-125392\,x^{5}\\&-1326177\,x^{6}-14025978\,x^{7}-148342234\,x^{8}-1568904385\,x^{9}\\&-16593123232\,x^{10}+O(x^{11})\end{array}}} x 1 = 0.0 + 106 / 1121 = 0.09455842997324 {\displaystyle x_{1}=0.0+106/1121=0.09455842997324}
d × 1 1 0.1 00000000000000000000000000000000 2 0.094 339622641509433962264150943396 3 0.09455 8429973238180196253345227475 4 0.094551 282051282051282051282051282 5 0.09455148 6538216154140615031261962 6 0.094551481 438752142436492263099118 7 0.09455148154 3746895938379484125812 8 0.0945514815423 36756233561913325371 9 0.09455148154232 4837086869382419375 10 0.094551481542326 678478801765822985
ご覧のとおり、 各位 d に はd 桁 強 の正しい小数点 以下 桁 数 が あり
ます 。 正解の 最初 の 100 桁 は 、 0.09455、14815、42326、59148、23865、40579、30296、38573、06105、62823、91803、04128、52904、53121、89983、48366、71462、67281、77715、77578 です 。
最低次の値 を計算してみましょう。 x 2 , x 3 , x 4 {\displaystyle x_{2},x_{3},x_{4}}
f = − 1 + 10 x + 6 x 2 + x 3 {\displaystyle f=-1+10x+6x^{2}+x^{3}} f ′ = 10 + 12 x + 3 x 2 {\displaystyle f^{\prime }=10+12x+3x^{2}} f ′ ′ = 12 + 6 x {\displaystyle f^{\prime \prime }=12+6x} f ′ ′ ′ = 6 {\displaystyle f^{\prime \prime \prime }=6}
そして次の関係を用いると、
1次注文; x i + 1 = x i − f ( x i ) / f ′ ( x i ) {\displaystyle x_{i+1}=x_{i}-f(x_{i})/f^{\prime }(x_{i})} 2番目の順序; x i + 1 = x i − 2 f f ′ / ( 2 f ′ 2 − f f ′ ′ ) {\displaystyle x_{i+1}=x_{i}-2ff^{\prime }/(2{f^{\prime }}^{2}-ff^{\prime \prime })} 3番目の順序; x i + 1 = x i − ( 6 f f ′ 2 − 3 f 2 f ′ ′ ) / ( 6 f ′ 3 − 6 f f ′ f ′ ′ + f 2 f ′ ′ ′ ) {\displaystyle x_{i+1}=x_{i}-(6f{f^{\prime }}^{2}-3f^{2}f^{\prime \prime })/(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })} × 1位（ニュートン） 2番目（ハレー） 3番目の注文 4番目の注文 × 1 0. 100000000000000000000000000000000 0.094 339622641509433962264150943395 0.09455 8429973238180196253345227475 0.094551 28205128 × 2 0.0945 68121104185218165627782724844 0.09455148154 0164214717107966227500 0.094551481542326591482 567319958483 × 3 0.094551481 698199302883823703544266 0.094551481542326591482386540579303 0.094551481542326591482386540579303 × 4 0.0945514815423265914 96064847153714 0.094551481542326591482386540579303 0.094551481542326591482386540579303 × 5 0.094551481542326591482386540579303 × 6 0.094551481542326591482386540579303
導出 ハウスホルダー法の正確な導出は、関数の d + 1次 の パデ近似から始まる。ここでは、線形 分子 を持つ近似式 が選択される。これが完了すると、次の近似の更新は、分子の唯一の零点を計算することによって得られる。
パデ近似は という形式を持ちます。 有理関数は でゼロを持ちます 。 f ( x + h ) = a 0 + h b 0 + b 1 h + ⋯ + b d − 1 h d − 1 + O ( h d + 1 ) . {\displaystyle f(x+h)={\frac {a_{0}+h}{b_{0}+b_{1}h+\cdots +b_{d-1}h^{d-1}}}+O(h^{d+1}).} h = − a 0 {\displaystyle h=-a_{0}}
d 次のテイラー多項式が 関数 fに依存する d + 1 個 の係数を持つのと同様に 、パデ近似も f とその導関数に依存する d + 1 個の係数を持ちます。より正確には、任意のパデ近似において、分子と分母の多項式の次数は近似式の位数に加算される必要があります。したがって、が 成立する必要があります。 b d = 0 {\displaystyle b_{d}=0}
ユークリッドの互除法 を用いて、 f のテイラー多項式からパデ近似を求めることもできます。しかし、 1/ f のテイラー多項式から始める方が短く、与えられた式に直接到達します。 は目的の有理関数の逆関数に等しくなければならない ため
、 を のべき乗で乗じると、 式
が得られます 。 ( 1 / f ) ( x + h ) = ( 1 / f ) ( x ) + ( 1 / f ) ′ ( x ) h + ⋯ + ( 1 / f ) ( d − 1 ) ( x ) h d − 1 ( d − 1 ) ! + ( 1 / f ) ( d ) ( x ) h d d ! + O ( h d + 1 ) {\displaystyle (1/f)(x+h)=(1/f)(x)+(1/f)'(x)h+\cdots +(1/f)^{(d-1)}(x){\frac {h^{d-1}}{(d-1)!}}+(1/f)^{(d)}(x){\frac {h^{d}}{d!}}+O(h^{d+1})} a 0 + h {\displaystyle a_{0}+h} h d {\displaystyle h^{d}} 0 = b d = a 0 ( 1 / f ) ( d ) ( x ) 1 d ! + ( 1 / f ) ( d − 1 ) ( x ) 1 ( d − 1 ) ! {\displaystyle 0=b_{d}=a_{0}(1/f)^{(d)}(x){\frac {1}{d!}}+(1/f)^{(d-1)}(x){\frac {1}{(d-1)!}}}
ここで、最後の方程式を 分子のゼロについて解くと、 という結果になります 。 h = − a 0 {\displaystyle h=-a_{0}} h = − a 0 = 1 ( d − 1 ) ! ( 1 / f ) ( d − 1 ) ( x ) 1 d ! ( 1 / f ) ( d ) ( x ) = d ( 1 / f ) ( d − 1 ) ( x ) ( 1 / f ) ( d ) ( x ) {\displaystyle {\begin{aligned}h&=-a_{0}={\frac {{\frac {1}{(d-1)!}}(1/f)^{(d-1)}(x)}{{\frac {1}{d!}}(1/f)^{(d)}(x)}}\\&=d\,{\frac {(1/f)^{(d-1)}(x)}{(1/f)^{(d)}(x)}}\end{aligned}}}
これは反復式を意味します 。 x n + 1 = x n + d ( 1 / f ) ( d − 1 ) ( x n ) ( 1 / f ) ( d ) ( x n ) {\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}
ニュートン法との関係 実数値関数 f ( x ) にハウスホルダー法を適用すると
、関数の零点を見つけるために ニュートン法を適用するのと同じ結果が得られます
。 特に、 d = 1 の 場合はニュートン法がそのまま適用され、 d = 2 の 場合はハレー法が適用されます。 x n + 1 = x n − g ( x n ) g ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}} g ( x ) = | ( 1 / f ) ( d − 1 ) | − 1 / d . {\displaystyle g(x)=\left|(1/f)^{(d-1)}\right|^{-1/d}\,.}
注記
参考文献
外部リンク 
![{\displaystyle {\sqrt[{d+1}]{d+1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba3765aac86b6f4301482fd80c50bf116a35ef4d)
![{\displaystyle {\sqrt[{\frac {(d+1)(d+2)}{2}}]{d+1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/898e6d6439586fab0b8701ac8cc47e50729a9fa9)
![{\displaystyle {\sqrt[{3}]{2}}\approx 1.2599}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8298c8331ebdebd9a3ae0fc2d069cb4780a963df)
![{\displaystyle {\sqrt[{6}]{3}}\approx 1.2009}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcb4922c07e817788c6dfd933a69199bc1bc962d)
![{\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+1\,{\frac {\left(1/f\right)(x_{n})}{\left(1/f\right)^{(1)}(x_{n})}}\\[.7em]=&x_{n}+{\frac {1}{f(x_{n})}}\cdot \left({\frac {-f'(x_{n})}{f(x_{n})^{2}}}\right)^{-1}\\[.7em]=&x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/089da8173742980ed852224fb40e27af1a93e4fe)
![{\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+2\,{\frac {\left(1/f\right)'(x_{n})}{\left(1/f\right)''(x_{n})}}\\[1em]=&x_{n}+{\frac {-2f(x_{n})\,f'(x_{n})}{-f(x_{n})f''(x_{n})+2f'(x_{n})^{2}}}\\[1em]=&x_{n}-{\frac {f(x_{n})f'(x_{n})}{f'(x_{n})^{2}-{\tfrac {1}{2}}f(x_{n})f''(x_{n})}}\\[1em]=&x_{n}+h_{n}\;{\frac {1}{1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}}.\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db7caebbe0698395a96add4668acb5f053fa1301)
![{\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+3\,{\frac {\left(1/f\right)''(x_{n})}{\left(1/f\right)'''(x_{n})}}\\[1em]=&x_{n}-{\frac {6f(x_{n})\,f'(x_{n})^{2}-3f(x_{n})^{2}f''(x_{n})}{6f'(x_{n})^{3}-6f(x_{n})f'(x_{n})\,f''(x_{n})+f(x_{n})^{2}\,f'''(x_{n})}}\\[1em]=&x_{n}+h_{n}{\frac {1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}{1+(f''/f')(x_{n})\,h_{n}+{\frac {1}{6}}(f'''/f')(x_{n})\,h_{n}^{2}}}\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1163f08bc9c31161fc264d21da13c020aa223927)
