関数のゼロを見つけるためのアルゴリズムは、与えられた関数fについて、 f(x) = 0を検証するxの近似値を見つけるための数値的手法またはアルゴリズムです。ここで、 x はfのゼロと呼ばれる実数、またはf がfの根多項式の場合に表されます。
xがベクトルのとき、 f(x) = 0 となるx を求めるアルゴリズムを一般に「方程式を数値的に解くアルゴリズム」と呼びます。これらのアルゴリズムは、関数のゼロを見つけるためのアルゴリズムを一般化したもので、線形または非線形方程式に適用できます。ゼロを見つけるための一部のアルゴリズム (ニュートン法など) は、非線形方程式の数値分解能に一般化できます。
関数のゼロを見つけるためのアルゴリズムは、数値解析で研究されます。
特定のアルゴリズム
二分法
ゼロを見つけるための最も単純なアルゴリズムは二分法です。関数のゼロを構成する 2 つの点aとbから開始し、各反復で 2 つの区間 [ a , c ] または [ c , b ] のいずれかを選択します。 , c = ( a + b )/2 は、 aとbの中点です。アルゴリズムは常に、ゼロを含む [ a , b ] の部分区間を選択します。二分法では、関数が連続である場合にゼロへの収束が保証されます。収束速度が線形であるため、研究の進歩はかなり遅いです。
ニュートン・ラフソン
ニュートン法は、ニュートン・ラフソン法とも呼ばれ、関数f を現在の近似値ゼロに「線形化」します。これにより、次のような繰り返し関係が得られます。
- $$ {x_{k+1} = x_k – \frac{f(x_k)}{f'(x_k)}.} $$
ゼロから離れすぎると、ニュートン法は収束しない可能性があります。ただし、収束した場合は、二分法 (複雑さは 2 次) よりもはるかに高速になります。ニュートン法は、高次元の問題に簡単に一般化できるため重要です。
割線
ニュートン法の関数の導関数を有限差分に置き換えると、セカント法が得られます。反復関係を使用します
- $$ {x_{n+1} = x_n – \frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} f(x_n).} $$
したがって、セカント法では導関数の計算は必要ありませんが、その代償として収束速度が遅くなります (1.6 程度)。
レギュラーファルシ
偽位置法は、regula falsi 法とも呼ばれ、二分法に似ています。ただし、反復ごとに間隔を 2 つの等しい部分に分割するのではなく、セカント法の公式で指定された点で間隔を分割します。偽位置法は、二分法の堅牢性と割線法の「超線形」複雑さを継承しています。
ミュラー
セカント法は、線形補間によって未知の関数fに近づく場合にも役立ちます。代わりに二次補間を使用すると、ミュラー法が使用されます。セカント法よりも早く収束します。この方法の特徴は、反復項x n が複雑になる可能性があることです。
逆二次補間
この欠点は、逆二次補間法につながるfの逆全単射を補間することによって回避できます。繰り返しになりますが、収束はセカント法よりも漸近的に高速ですが、逆二次補間は、反復回数が 0 に近くない場合、動作が低下することがよくあります。
ブレント
最後に、ブレントの方法は、二分法、割線法、および逆二次補間を組み合わせたものです。ブレントの方法は反復ごとに、これら 3 つの方法のうちどれが最もゼロに近づく可能性が高いかを判断し、その方法を使用してステップを実行します。これにより、堅牢で高速な方法が得られ、非常に人気があり、高く評価されています。
その他のアルゴリズム
他のゼロ探索アルゴリズムは次のとおりです。
- 連続した交代
- ブロイデン法
- 固定小数点法
フォン・ミーゼス
共役勾配
共役勾配法
多項式の根を求める
関数fが多項式である特定のケースに特に注意が払われました。もちろん、前のセクションで説明した方法を使用することもできます。特に、多項式の導関数を求めるのは簡単で、ニュートン法は非常に優れた候補となります。ただし、 fが多項式であるという事実を利用する方法を選択することは可能です。
1 つの可能性は、多項式に関連付けられたコンパニオン行列を考慮することです。この行列の固有値が多項式の根と一致することがわかっているので、任意の固有値検索アルゴリズムを使用して、初期多項式の根の近似値を見つけることができます。
もう 1 つの可能性は、非常に複雑な方法ですが、非常に早く収束するラゲール法を使用することです。実際、単純なルートの 3 次収束速度が向上し、ニュートン法の 2 次収束速度を打ち破ります。
多項式に有理係数があり、有理根だけを探している場合は、ルフィニ法を使用できます。
いずれにせよ、根の近似値を見つける問題は、ウィルキンソン多項式で示されるように条件が不十分になる可能性があることに留意する必要があります。