セカント法

Root-finding method

セカント法の最初の2回の反復。赤い曲線は関数f、青い線はセカントです。この特定のケースでは、セカント法は可視根に収束しません。

数値解析において、セカント法は、関数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 ₁ ))を通る直線を描く。点-点形式では、 ^[2]この直線の方程式は

${\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 ₂を用いて同じ処理を繰り返します。この処理をx ₃、x ₄などについて繰り返し、十分に高い精度（x _nとx _{n −1}の差が十分に小さい）に達するまで続けます。

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

実用的な考慮事項

数学的には、次の2つのセカント法は同等である。 $${\displaystyle x_{n+1}=x_{n}-f(x_{n})\left[{\frac {x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}}\right]}$$ $${\displaystyle x_{n+1}={\frac {x_{n-1}f(x_{n})-x_{n}f(x_{n-1})}{f(x_{n})-f(x_{n-1})}}.}$$

近似演算を使用する場合、たとえば、小数点以下の固定桁数で実行されるペンと紙による演算や、コンピューターで使用できる浮動小数点バイナリ演算など、最初のバージョンが 2 つの理由から推奨されます。

• これは、何らかの数 に対して という形をとります。が不正確であっても、 も小さいため、収束時の根の推定値の変化は小さくなります。 ${\displaystyle x_{n+1}=x_{n}-f(x_{n})\Delta }$ ${\displaystyle \Delta }$ ${\displaystyle \Delta }$ ${\displaystyle f(x_{n})}$
• 2 番目の形式は、収束に近づくにつれて分母のキャンセル誤差が大きくなる可能性があるため、壊滅的なキャンセルの影響を受けやすくなります。 ${\displaystyle f(x_{n})\to f(x_{n-1})}$

一般化

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

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

計算例

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

次に^これを応用して、初期点と ${\displaystyle x_{0}=10}$ ${\displaystyle x_{1}=30}$

def secant_method ( f , x0 : int , x1 : int , iterations : int ) -> float : """セカント法を使用して計算された根を返します。""" for i in range ( iterations ): x2 = x1 - f ( x1 ) * ( x1 - x0 ) / float ( f ( x1 ) - f ( x0 )) x0 , x1 = x1 , x2 # ここで停止基準を適用します (以下を参照) return x2                                   def 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のいずれかに達した時点で停止します。^[4]

注記

1. パパコンスタンティノウ, ジョアンナ; タピア, リチャード (2013). 「1次元におけるセカント法の起源と進化」 .アメリカ数学月刊誌. 120 (6): 500– 518. doi :10.4169/amer.math.monthly.120.06.500. JSTOR  10.4169/amer.math.monthly.120.06.500. S2CID  17645996.
2. マースデン、ジェロルド (1985). 微積分学 I. Springer-Verlag New York Inc. p. 31. ISBN 978-1-4612-5024-1。
3. Chanson, Jeffrey R. (2024年10月3日). 「収束の順序」. LibreTexts Mathematics . 2024年10月3日閲覧。
4. 「MATLAB チュートリアル (最初のコース)。パート 1.3: 正割法」。

参照

• 偽位置法

参考文献

• アヴリエル、モーデカイ (1976).非線形計画法：分析と手法プレンティス・ホール. pp.  220– 221. ISBN 0-13-623603-0。
• アレン、マイロン・B; アイザックソン、イーライ・L (1998). 応用科学のための数値解析.ジョン・ワイリー・アンド・サンズ. pp.  188– 195. ISBN 978-0-471-55266-6。

外部リンク

• Holistic Numerical Methods Institute の Secant Method ノート、PPT、Mathcad、Maple、Mathematica、Matlab
• ワイスタイン、エリック・W.「セカント法」。MathWorld。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Secant_method&oldid=1322425576"