セカント法

数値解析において、セカント法は、関数fの根をより正確に近似するために、セカント直線の根の連続を使用する根探索アルゴリズムです。セカント法はニュートン法の差分近似として考えることができるため、準ニュートン法と見なされます。歴史的には、ニュートン法より 3000 年以上も前にさかのぼる偽位置法の進化形です。^[1]

セカント法は、関数fの零点を求める反復数値法である。2つの初期値x ₀とx ₁が与えられ、この方法は再帰関係に従って進行する。

${\displaystyle x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}={\frac {x_{n-2}f(x_{n-1})-x_{n-1}f(x_{n-2})}{f(x_{n-1})-f(x_{n-2})}}.}$

これは、 fと 2 つの初期値x ₀およびx ₁が与えられれば明確に定義される非線形 2 次再帰です。理想的には、初期値は目的のゼロに近い値を選択する必要があります。

初期値x ₀とx ₁から始めて、上の図に示すように、点( x ₀、f ( x ₀ ))と点( x ₁、f ( x ₁ ))を通る直線を描きます。傾きと切片の形式では、この直線の方程式は次のようになります。

${\displaystyle y={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}(x-x_{1})+f(x_{1}).}$

この線形関数の根、つまりy = 0となるxの値は

${\displaystyle x=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}.}$

次に、この新しいxの値をx ₂として使用し、 x ₀とx ₁の代わりにx ₁とx _{2 を}使用してプロセスを繰り返します。このプロセスを継続して、十分に高い精度レベル（ x _nとx _{n −1}の差が十分に小さい）に達するまで、x ₃、x ₄などを解きます。

${\displaystyle {\begin{aligned}x_{2}&=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}},\\[6pt]x_{3}&=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}},\\[6pt]&\,\,\,\vdots \\[6pt]x_{n}&=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}.\end{aligned}}}$

セカント法の反復は、初期値とが十分に根に近く、適切に動作する場合、 の根に収束します。が 2 回連続微分可能で、問題の根が単根、つまり重複度が 1 の場合、収束の順序は黄金比です^[2]この収束は超線形ですが、二次以下です。 ${\displaystyle x_{n}}$${\displaystyle f}$${\displaystyle x_{0}}$${\displaystyle x_{1}}$${\displaystyle f}$${\displaystyle f}$ ${\displaystyle \varphi =(1+{\sqrt {5}})/2\approx 1.618.}$

初期値が根に十分近くないか、が適切に動作しない場合は、セカント法が収束するという保証はまったくありません。 「十分近い」の一般的な定義はありませんが、収束の基準は、関数が初期値間の区間でどの程度「波打っている」かに関係しています。 たとえば、 がその区間で微分可能であり、区間上に という点がある場合、アルゴリズムは収束しない可能性があります。 ${\displaystyle f}$${\displaystyle f}$${\displaystyle f'=0}$

セカント法は、二分法のように、根が連続する反復によって括弧で囲まれたままであることを必要としないか保証しないため、常に収束するとは限りません。偽位置法(またはregula falsi ) は、セカント法と同じ式を使用します。ただし、セカント法のように式をと に適用するのではなく、とが異なる符号を持つ最後の反復 と に適用します。つまり、偽位置法は常に収束しますが、収束の順序が線形である場合のみです。セカント法のように超線形収束の順序で括ることは、ITP 法やイリノイ法など、偽位置法の改良 ( Regula falsi § regula falsiの改良を参照)によって実現できます。 ${\displaystyle x_{n-1}}$${\displaystyle x_{n-2}}$${\displaystyle x_{n-1}}$${\displaystyle x_{k}}$${\displaystyle f(x_{k})}$${\displaystyle f(x_{n-1})}$

セカント法の漸化式はニュートン法の式から導かれる。

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

有限差分近似を用いると、小さい に対して次の式が得られます。 ${\displaystyle \epsilon =x_{n-1}-x_{n-2}}$

${\displaystyle f'(x_{n-1})=\lim _{\epsilon \rightarrow 0}{\frac {f(x_{n-1})-f(x_{n-1}-\epsilon )}{\epsilon }}\approx {\frac {f(x_{n-1})-f(x_{n-2})}{x_{n-1}-x_{n-2}}}}$

セカント法は、導関数を近似値に置き換えた方法、つまり準ニュートン法として解釈できます。

ニュートン法とセカント法を比較すると、ニュートン法の方が収束が速いことがわかります（黄金比 φ  ≈ 1.6 の次数に対して 2 次）。^[2]しかし、ニュートン法では、すべてのステップでとその導関数の両方を評価する必要がありますが、セカント法では の評価のみが必要です。したがって、実際にはセカント法の方が速い場合があります。たとえば、 の評価にその導関数の評価と同じ時間がかかり、他のすべてのコストを無視すると仮定すると、セカント法の 2 ステップ（誤差の対数をφ ²  ≈ 2.6 倍に減少）を、ニュートン法の 1 ステップ（誤差の対数を 2 分の 1 に減少）と同じコストで実行できるため、セカント法の方が高速です。次元が高くなると、ニュートン法に必要な偏導関数の完全なセット、つまりヤコビ行列の計算コストが、関数自体の計算コストよりもはるかに高くなる可能性があります。ただし、導関数または導関数の評価に並列処理を考慮すると、ニュートン法はクロック時間では高速化できますが、全体的な計算操作のコストは依然として高くなります。 ${\displaystyle f}$${\displaystyle f'}$${\displaystyle f}$${\displaystyle f}$

Broyden 法は、セカント法を複数の次元に一般化したものです。

次のグラフでは、関数fが赤で、最後の割線が太い青で示されています。グラフでは、割線のx切片がfの根の良い近似値になっているようです。

以下では、セカント法をPythonプログラミング言語で実装します。

次に、これを初期点を持つ関数f ( x ) = x ² − 612の根を求めるために適用し、${\displaystyle x_{0}=10}$${\displaystyle x_{1}=30}$

def  secant_method ( f ,  x0 ,  x1 ,  iterations ): 
"""セカント法を使用して計算された根を返します。""" for i in range ( iterations ): x2 = x1 - f ( x1 ) * ( x1 - x0 ) / float ( f ( x1 ) - f ( x0 )) x0 , x1 = x1 , x2 # ここで停止基準を適用します (下記参照) return x2    
       
                    
            
        
     

 f_example ( x ): 
    x ** 2 - 612を 返す    

ルート =  secant_method ( f_example 、 10 、 30 、 5 )

print ( f "ルート: { root } " )   # ルート: 24.738633748750722

上記の停止基準が適切であることは非常に重要です。そうでないと、浮動小数点数の数値精度の限界により、反復回数が多すぎる場合にアルゴリズムが不正確な結果を返す可能性があります。たとえば、上記のループは、abs(x0 - x1) < tol、abs(x0/x1-1) < tol、abs(f(x1)) < tolのいずれかに最初に到達したときに停止します。^[3]

• 偽位置法

• アヴリエル、モーデカイ (1976)。非線形計画法:分析と方法。プレンティス ホール。pp. 220–221。ISBN 0-13-623603-0。
• Allen, Myron B.; Isaacson, Eli L. (1998). 応用科学のための数値解析. John Wiley & Sons . pp. 188–195. ISBN 978-0-471-55266-6。

• セカント法ノート、PPT、Mathcad、Maple、Mathematica、Matlab（Holistic Numerical Methods Institute より）
• Weisstein、Eric W.「Secant Method」。MathWorld。