根探索アルゴリズム

数値解析において、根探索アルゴリズムは連続関数の零点（「根」とも呼ばれる）を求めるアルゴリズムである。関数fの零点は、 f ( x ) = 0となる数xである。一般に関数の零点は正確に計算できず、閉じた形で表現することもできないため、根探索アルゴリズムは零点の近似値を提供する。実数から実数への関数、または複素数から複素数への関数の場合、これらは誤差限界のない浮動小数点数として、または誤差限界付きの浮動小数点値として表現される。後者の誤差限界付き近似値は、実根の場合は小さな分離区間、複素根の場合は円板に相当する。[ 1 ]

方程式f ( x ) = g ( x )を解くことは、関数h ( x ) = f ( x ) – g ( x )の根を求めることと同じです。したがって、根を求めるアルゴリズムは、連続関数のあらゆる方程式を解くために使用できます。ただし、ほとんどの根を求めるアルゴリズムは、関数のすべての根を求めることを保証するものではなく、そのようなアルゴリズムで根が見つからない場合でも、必ずしも根が存在しないことを意味するわけではありません。

数値的に根を求める方法のほとんどは反復法であり、理想的には極限として根に収束する数列を生成します。これらの方法では、根の初期推定値を開始値として1 つ以上必要とし、アルゴリズムの各反復により、根へのより正確な近似値が連続的に生成されます。反復はある時点で停止する必要があるため、これらの方法は、正確な解ではなく、根への近似値を生成します。多くの方法では、先行する値に対して補助関数を評価することで、後続の値を計算します。したがって、極限は補助関数の不動点であり、元の方程式の根を不動点として持ち、これらの固定点に急速に収束するように選択されます。

一般的な求根アルゴリズムの挙動は、数値解析で研究されています。しかし、特に多項式の場合、求根アルゴリズムの研究はコンピュータ代数に属します。多項式の代数的性質が最も効率的なアルゴリズムの基礎となるからです。アルゴリズムの効率と適用性は、与えられた関数の特性に敏感に依存する可能性があります。たとえば、多くのアルゴリズムは入力関数の導関数を使用しますが、他のアルゴリズムはすべての連続関数で機能します。一般に、数値アルゴリズムは関数のすべての根を見つけることは保証されていないため、根が見つからないことは根が存在しないことを証明することにはなりません。しかし、多項式の場合、代数的性質を使用して根が見落とされていないことを証明し、数値法（通常はニュートン法）が各区間（またはディスク）内の唯一の根に収束することを保証するのに十分小さい別々の区間（または複素根の場合はディスク）に根を配置する特定のアルゴリズムが存在します。

ブラケット法

括弧法は、根を含む、次第に小さい区間（括弧）を決定します。区間が十分に小さい場合、根が見つかったとみなされます。これらの方法では一般に、中間値定理が使用されます。中間値定理とは、連続関数が区間の端点で反対の符号の値を持つ場合、関数はその区間に少なくとも 1 つの根を持つというものです。したがって、これらの方法では、関数が区間の端点で反対の符号を取るような区間から開始する必要があります。ただし、多項式の場合は、区間内の根の数を制限または決定するための、デカルトの符号規則、ブーダンの定理、シュトゥルムの定理などの他の方法があります。これらの方法は、すべての実根を保証された精度で見つける、多項式の 実根分離の効率的なアルゴリズムにつながります。

二分法

最も単純な求根アルゴリズムは二分法です。f を連続関数とし、その 区間[ a , b ]においてf ( a )とf ( b )が異符号（括弧内）を持つことが分かっているとします。c = ( a + b )/2を区間の中央（中間点、つまり区間を二分する点）とします。すると、f ( a )とf ( c )、またはf ( c )とf ( b )が異符号になり、区間のサイズが 2 で割られます。二分法は堅牢ですが、反復ごとに精度が 1ビットしか向上しません。したがって、 ε近似根を求めるために必要な関数評価の回数は です。適切な条件下では、他の方法の方がより速く精度を向上させることができます。 ログ2⁡b−1つのε{\displaystyle \log _{2}{\frac {ba}{\varepsilon }}}

偽の位置 ( regula falsi )

偽位置法（レギュラ・ファルシ法とも呼ばれる）は二分法に似ていますが、二分法の区間の中央を使用する代わりに、区間の端点にプロットされた関数値を結ぶ直線の x切片を使用します。

c＝1つのf（b）−bf（1つの）f（b）−f（1つの）。{\displaystyle c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.}

偽位置法はセカント法に似ていますが、最後の2点を保持する代わりに、根の両側に1点ずつ保持する点が異なります。偽位置法は二分法よりも高速で、セカント法のように発散することはありません。ただし、丸め誤差によりf ( c )の符号が誤っている可能性があるため、単純な実装では収束に失敗する可能性があります。これは通常、根の近傍で fの導関数が大きい場合に発生します。

補間

多くの根を求める処理は補間によって行われます。これは、最後に計算された根の近似値を用いて、これらの近似根において同じ値を取る低次多項式で関数を近似する処理です。次に、多項式の根を計算し、それを関数の根の新たな近似値として用い、この処理を反復します。

2つの値を補間すると、1次多項式である直線が得られます。これがセカント法の基礎です。レギュラ・ファルシ法も2点ずつ補間する補間法ですが、必ずしも最後に計算された2点とは限らない2点を使用する点でセカント法とは異なります。3つの値は放物曲線、つまり2次関数を定義します。これがミュラー法の基礎です。

反復法

すべての根探索アルゴリズムは反復処理によって進行しますが、反復根探索法では一般的に、補助関数を定義する特定の種類の反復処理が用いられます。補助関数は、根の最新の近似値に適用され、新たな近似値が得られます。補助関数の固定点が所望の精度に達したとき、つまり、新たに計算された値が以前の値に十分近づいたときに、反復処理は停止します。

ニュートン法（および同様の微分ベースの方法）

ニュートン法は、関数fが連続導関数を持つと仮定します。ニュートン法は、根からあまりにも離れたところから開始すると収束しない可能性があります。しかし、収束する場合は二分法よりも高速です。ニュートン法の収束次数は通常2次ですが、二分法は線形です。ニュートン法は、高次元の問題にも容易に一般化できることでも重要です。ハウスホルダー法は、ニュートン法に似た高収束次数を持つ手法の一種です。ニュートン法に次いで最初の手法は、収束次数が3次の ハレー法です。

セカント法

ニュートン法における微分を有限差分に置き換えると、セカント法が得られます。この方法では微分の計算（および存在）は不要ですが、収束が遅くなります（収束の位数は黄金比で、約1.62 [ 2 ]）。セカント法を高次元に一般化したものがブロイデン法です。

ステフェンセン法

多項式近似を使用して、セカント法で使用される有限差分の二次部分を削除し、導関数をより適切に近似すると、二次収束を持ち、その動作（良い点と悪い点の両方）がニュートン法と本質的に同じであるが、導関数を必要としないステフェンセン法が得られます。

固定小数点反復法

固定小数点反復法を用いて関数の根を求めることができます。根を求めるために関数をゼロに設定した関数( )が与えられた場合、方程式を で書き直すと はとなります（注意：各関数には複数の関数が存在する場合が多い）。次に、方程式の両辺を とラベル付けし、反復処理を実行できるようにします。次に、 の値を取り、関数の根に収束するまで反復処理を実行します。反復処理が収束する場合、根に収束します。反復処理は の場合にのみ収束します。 f（×）{\displaystyle f(x)}f（×）＝0{\displaystyle f(x)=0}×{\displaystyle x}f（×）＝0{\displaystyle f(x)=0}×＝グラム（×）{\displaystyle x=g(x)}グラム（×）{\displaystyle g(x)}f（×）＝0{\displaystyle f(x)=0}×n+1＝グラム（×n）{\displaystyle x_{n+1}=g(x_{n})}×1{\displaystyle x_{1}}|グラム′（root）|<1{\displaystyle |g'(root)|<1}

を に変換する例として、関数 が与えられた場合、それを次の式のいずれかとして書き直します。 f（×）＝0{\displaystyle f(x)=0}×＝グラム（×）{\displaystyle x=g(x)}f（×）＝×2+×−1{\displaystyle f(x)=x^{2}+x-1}

×n+1＝（1/×n）−1{\displaystyle x_{n+1}=(1/x_{n})-1}、
×n+1＝1/（×n+1）{\displaystyle x_{n+1}=1/(x_{n}+1)}、
×n+1＝1−×n2{\displaystyle x_{n+1}=1-x_{n}^{2}}、
×n+1＝×n2+2×n−1{\displaystyle x_{n+1}=x_{n}^{2}+2x_{n}-1}、 または
×n+1＝±1−×n{\displaystyle x_{n+1}=\pm {\sqrt {1-x_{n}}}}。

逆補間

補間法における複素数値の出現は、 fの逆数を補間することで回避でき、結果として逆二次補間法が実現されます。この場合も、収束は漸近的に正割法よりも速くなりますが、反復が根に近くない場合、逆二次補間はしばしば挙動が悪くなります。

方法の組み合わせ

ブレント法

ブレント法は、二分法、正割法、逆二次補間を組み合わせたものです。ブレント法は、反復ごとにこれら3つの方法のうちどれが最も効果的かを判断し、その方法に従ってステップを進めます。これにより堅牢かつ高速な手法が実現されるため、非常に人気があります。

リダーズ法

リダース法は、区間の中点における関数の値を用いて根への指数関数補間を行うハイブリッド法です。この方法は高速収束を実現し、二分法の最大2倍の反復回数で収束することが保証されています。

多項式の根

多項式の根を求めることは、歴史を通じて広く研究され、数学の発展に大きな影響を与えてきた長年の問題です。これは、一変数多項式の根の数値近似値または閉形式の表現を求めること、すなわち、方程式 の近似解または閉形式の解を求めることを意味します。×{\displaystyle x}

1つの0+1つの1×+1つの2×2+⋯+1つのn×n＝0{\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}=0}

ここでは実数または複素数です。 1つの私{\displaystyle a_{i}}

多項式方程式を理解して解く努力により、無理数や複素数などの重要な数学概念や、体、環、群などの現代代数学の基礎構造が発展しました。

歴史的に重要であるにもかかわらず、高次多項式の根を見つけることは、コンピュータ代数における1つの大きな例外を除いて、数学や計算数学においてもはや中心的な役割を果たしていません。[ 3 ]

高次元での根源の発見

二分法は高次元に一般化されており、これらの方法は一般化二分法と呼ばれています。[ 4 ] [ 5 ]各反復において、領域は2つの部分に分割され、アルゴリズムは少数の関数評価に基づいて、これらの2つの部分のどちらに根が含まれるかを決定します。1次元では、関数の符号が逆であることが決定基準となります。この方法を多次元に拡張する際の主な課題は、容易に計算でき、根の存在を保証する基準を見つけることです。

ポアンカレ・ミランダの定理は長方形内の根の存在の基準を与えますが、長方形の境界全体で関数を評価する必要があるため検証が困難です。

クロネッカーの定理[ 6 ]は、別の基準を与えている。これは、長方形上の関数fの位相次数が0でない場合、長方形にはfの根が少なくとも1つ含まれている必要があるというものである。この基準は、ステンガー[ 7 ]やキアフォート[ 8 ]などのいくつかの根探索法の基礎となっている 。しかし、位相次数の計算には時間がかかることがある。

3つ目の基準は特性多面体に基づいています。この基準は特性二分法と呼ばれる方法で使用されます。[ 4 ]：19-- 位相次数の計算は必要なく、関数値の符号の計算のみが必要です。必要な評価回数は少なくとも です。ここで、Dは特性多面体の最長辺の長さです。[ 9 ]：11、補題4.7 VrahatisとIordanidis [ 9 ]は評価回数の下限を証明しており、上限を証明していないことに注意してください。 ログ2⁡（D/ϵ）{\displaystyle \log _{2}(D/\epsilon )}

4番目の方法は、単体の中間値定理を使用する。[ 10 ]この場合も、クエリの数に上限は与えられていない。

参照

ブロイデン法 – 多変数の場合の準ニュートン求根法

参考文献

  1. ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「第9章 根の探索と非線形方程式の集合」 .数値レシピ：科学計算の芸術（第3版）. ニューヨーク：ケンブリッジ大学出版局. ISBN 978-0-521-88068-8。
  2. ^ Chanson, Jeffrey R. (2024年10月3日). 「収束の順序」 . LibreTexts Mathematics . 2024年10月3日閲覧。
  3. ^ Pan, Victor Y. (1997年1月). 「多項式方程式の解法：これまでの経緯と最近の進歩」 . SIAM Review . 39 (2): 187– 220. doi : 10.1137/S0036144595288554 . ISSN 0036-1445 . 
  4. ^ a b Mourrain, B.; Vrahatis, MN; Yakoubsohn, JC (2002-06-01). 「実根の分離と位相次数の確実な計算の計算量について」 . Journal of Complexity . 18 (2): 612– 640. doi : 10.1006/jcom.2001.0636 . ISSN 0885-064X . 
  5. ^ Vrahatis, Michael N. (2020). 「連続関数の固定点と零点の近似における中間値定理の一般化」 . Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (編).数値計算：理論とアルゴリズム. コンピュータサイエンス講義ノート. 第11974巻. シュプリンガー・インターナショナル・パブリッシング. pp.  223– 238. doi : 10.1007/978-3-030-40616-5_17 . ISBN 978-3-030-40616-5. S2CID  211160947 .
  6. ^ Ortega, James M.; Rheinboldt, Werner C. (2000).多変数非線形方程式の反復解法. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-461-6。
  7. ^ Stenger, Frank (1975-03-01). 「Rnにおける写像の位相次数の計算」. Numerische Mathematik . 25 (1): 23– 38. doi : 10.1007/BF01419526 . ISSN 0945-3245 . S2CID 122196773 .  
  8. ^ Kearfott, Baker (1979-06-01). 「一般化された二分法のための効率的な次数計算法」. Numerische Mathematik . 32 (2): 109– 127. doi : 10.1007/BF01404868 . ISSN 0029-599X . S2CID 122058552 .  
  9. ^ a b Vrahatis, MN; Iordanidis, KI (1986-03-01). 「非線形方程式系を解くための高速一般化二分法」. Numerische Mathematik . 49 (2): 123– 138. doi : 10.1007/BF01389620 . ISSN 0945-3245 . S2CID 121771945 .  
  10. ^ Vrahatis, Michael N. (2020-04-15). 「不動点と零点の単体近似における単体の中間値定理」 .トポロジーとその応用. 275 107036. doi : 10.1016/j.topol.2019.107036 . ISSN 0166-8641 . S2CID 213249321 .  

さらに読む

  • Victor Yakovlevich Pan：「多項式方程式の解法：歴史と最近の進歩」、SIAM Review、Vol.39、No.2、pp.187-220（1997年6月）。
  • John Michael McNamee:多項式の根の数値的手法 - パート I、Elsevier、ISBN 978-0-444-52729-5 (2007)。
  • John Michael McNamee と Victor Yakovlevich Pan：「多項式の根の数値的手法 - パート II」、Elsevier、ISBN 978-0-444-52730-1 (2013)。

「 https://en.wikipedia.org/w/index.php?title=Root-finding_algorithm&oldid=1314594894」より取得