ITP法

Root-finding algorithm

数値解析において、ITP法（補間、切り捨て、投影法）は、二分法の最適^[2]最悪ケースの性能を保持しながら、割線法^[1]の超線形収束を達成する最初の求根アルゴリズムです。^[3]また、任意の連続分布の下で二分法よりも確実に優れた平均性能が保証された最初の方法でもあります。^[3]実際には、この方法は、適切に動作する関数に対して超線形収束するだけでなく、補間が失敗する動作の悪い関数の下でも高速な性能を保証するため、従来の補間およびハイブリッドベースの戦略（ブレント法、リダーズ、イリノイ）よりも優れた性能を発揮します。^[3]

ITP 法は、根の位置の上限と下限を追跡する標準的なブラケット戦略と同じ構造に従いますが、最悪の場合のパフォーマンスが上限に抑えられる領域も追跡します。ブラケット戦略として、ITP は各反復で 1 つのポイント上の関数の値を照会し、関数値が同じ符号を共有する 2 つのポイント間の間隔部分を破棄します。照会されたポイントは、3 つの手順で計算されます。まず、 regula falsi推定値を求めて補間し、次に推定値を摂動/切り捨て ( Regula falsi § regula falsiの改良と同様)、次に摂動された推定値を二分中点の近傍の間隔に投影します。二分点の周囲の近傍は、ミニマックス最適性 ( ^[3]の定理 2.1) を保証するために、各反復で計算されます。この方法は3つのハイパーパラメータに依存し、は黄金比です。最初の2つは切り捨てのサイズを制御し、3つ目は投影ステップの間隔のサイズを制御するスラック変数です。 ^[a] ${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$ ${\displaystyle n_{0}\in [0,\infty )}$ ${\displaystyle \phi }$ ${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$

根を求める問題

からまで定義される連続関数 が与えられ、 1回のクエリを犠牲にする ことで、任意の におけるの値にアクセスできます。また、事前に指定された目標精度 が与えられている場合、以下の問題を可能な限り少ないクエリ数で解くように、根を求めるアルゴリズムが設計されています。 ${\displaystyle f}$ ${\displaystyle [a,b]}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle f(a)f(b)\leq 0}$ ${\displaystyle f(x)}$ ${\displaystyle x}$ ${\displaystyle \epsilon >0}$

問題の定義:が を満たすような を 見つけます。 ${\displaystyle {\hat {x}}}$ ${\displaystyle |{\hat {x}}-x^{*}|\leq \epsilon }$ ${\displaystyle x^{*}}$ ${\displaystyle f(x^{*})=0}$

この問題は数値解析、コンピュータサイエンス、エンジニアリングにおいて非常に一般的であり、求根アルゴリズムはこれを解くための標準的なアプローチです。求根手順は、より複雑な親アルゴリズムによって、より大きなコンテキスト内で呼び出されることがよくあります。そのため、より大規模なコンテキストを考慮すると、非効率的なアプローチでは計算コストが高くなる可能性があるため、求根問題を効率的に解くことは極めて重要です。ITP法は、 区間 で開始された場合、最大 回の反復で終了する二分法の補間保証と最小最大最適保証を同時に利用することで、これを実現しようとします。 ${\displaystyle n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil }$ ${\displaystyle [a_{0},b_{0}]}$

方法

、黄金比が与えられた場合 、 各反復で ITP メソッドは次の 3 つの手順で点を計算します。 ${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$ ${\displaystyle n_{1/2}\equiv \lceil \log _{2}((b_{0}-a_{0})/2\epsilon )\rceil }$ ${\displaystyle n_{0}\in [0,\infty )}$ ${\displaystyle \phi }$ ${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$ ${\displaystyle j=0,1,2\dots }$ ${\displaystyle x_{\text{ITP}}}$

ITP メソッドのステップ 1。

ITP メソッドのステップ 2。

ITP メソッドのステップ 3。

これら3つのステップを組み合わせることでITP法が完成します。太い青線は、この手法の「投影切り捨て補間」を表しています。

1.  [補間ステップ] 二等分点と正規偽点を計算します 。 ${\displaystyle x_{1/2}\equiv {\frac {a+b}{2}}}$ ${\displaystyle x_{f}\equiv {\frac {bf(a)-af(b)}{f(a)-f(b)}}}$
2. [打ち切りステップ] 推定値を中心に向かって摂動します。 ここで 、および です。 ${\displaystyle x_{t}\equiv x_{f}+\sigma \delta }$ ${\displaystyle \sigma \equiv {\text{sign}}(x_{1/2}-x_{f})}$ ${\displaystyle \delta \equiv \min\{\kappa _{1}|b-a|^{\kappa _{2}},|x_{1/2}-x_{f}|\}}$
3. [投影ステップ] 推定値をminmax区間に投影します。ここで、 ${\displaystyle x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}}$ ${\displaystyle \rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}},|x_{t}-x_{1/2}|\right\}}$

この点における関数の値が照会され、その後、両端に反対符号の関数値を持つサブ区間を維持することで、ルートを囲むように区間が縮小されます。 ${\displaystyle f(x_{\text{ITP}})}$

アルゴリズム

次のアルゴリズム (擬似コードで記述) は、およびの初期値が与えられ、 および を満たすものと想定し、最大回までの関数評価でを満たす推定値を返します。 ${\displaystyle y_{a}}$ ${\displaystyle y_{b}}$ ${\displaystyle y_{a}<0<y_{b}}$ ${\displaystyle y_{a}\equiv f(a)}$ ${\displaystyle y_{b}\equiv f(b)}$ ${\displaystyle {\hat {x}}}$ ${\displaystyle |{\hat {x}}-x^{*}|\leq \epsilon }$ ${\displaystyle n_{1/2}+n_{0}}$

入力: ${\displaystyle a,b,\epsilon ,\kappa _{1},\kappa _{2},n_{0},f}$ 前処理: 、、および ; While ( ) ${\displaystyle n_{1/2}=\lceil \log _{2}{\tfrac {b-a}{2\epsilon }}\rceil }$ ${\displaystyle n_{\max }=n_{1/2}+n_{0}}$ ${\displaystyle j=0}$ ${\displaystyle b-a>2\epsilon }$  計算パラメータ: 、、;補間 : ; 切り捨て: ; ${\displaystyle x_{1/2}={\tfrac {a+b}{2}}}$ ${\displaystyle r=\epsilon 2^{n_{\max }-j}-(b-a)/2}$ ${\displaystyle \delta =\kappa _{1}(b-a)^{\kappa _{2}}}$  ${\displaystyle x_{f}={\tfrac {y_{b}a-y_{a}b}{y_{b}-y_{a}}}}$  ${\displaystyle \sigma ={\text{sign}}(x_{1/2}-x_{f})}$ もしそうなら、 ${\displaystyle \delta \leq |x_{1/2}-x_{f}|}$ ${\displaystyle x_{t}=x_{f}+\sigma \delta }$ そうでなければ、 射影： もしそうなら、 ${\displaystyle x_{t}=x_{1/2}}$ ${\displaystyle |x_{t}-x_{1/2}|\leq r}$ ${\displaystyle x_{\text{ITP}}=x_{t}}$ そうでない場合; 更新間隔: ; ${\displaystyle x_{\text{ITP}}=x_{1/2}-\sigma r}$  ${\displaystyle y_{\text{ITP}}=f(x_{\text{ITP}})}$の 場合、​ ${\displaystyle y_{\text{ITP}}>0}$ ${\displaystyle b=x_{ITP}}$ ${\displaystyle y_{b}=y_{\text{ITP}}}$そうで なければ、そして、 ${\displaystyle y_{\text{ITP}}<0}$ ${\displaystyle a=x_{\text{ITP}}}$ ${\displaystyle y_{a}=y_{\text{ITP}}}$ Else and ; ;出力: ${\displaystyle a=x_{\text{ITP}}}$ ${\displaystyle b=x_{\text{ITP}}}$ ${\displaystyle j=j+1}$ ${\displaystyle {\hat {x}}={\tfrac {a+b}{2}}}$

例: 多項式の根を求める

ITP 法を使用して多項式の根を求めると仮定すると、次のようになります。 ${\displaystyle f(x)=x^{3}-x-2\,.}$ ${\displaystyle \epsilon =0.0005,\kappa _{1}=0.1,\kappa _{2}=2}$ ${\displaystyle n_{0}=1}$

反復	${\displaystyle a_{n}}$	${\displaystyle b_{n}}$	${\displaystyle c_{n}}$	${\displaystyle f(c_{n})}$
1	1	2	1.43333333333333	-0.488629629629630
2	1.43333333333333	2	1.52713145056966	0.0343383329048983
3	1.43333333333333	1.52713145056966	1.52009281150978	-0.00764147709265051
4	1.52009281150978	1.52713145056966	1.52137899116052	-4.25363464540141e-06
5	1.52137899116052	1.52713145056966	1.52138301273268	1.96497878177659e-05
6	1.52137899116052	1.52138301273268	← 停止基準を満たしました

この例は二分法と比較することができます§ 例: 多項式の根を求める。ITP法は、二分法の半分以下の反復回数で、より正確な根の推定値を得ることができ、最小最大解の保証を損なうことなく実現しました。他の手法（Ridders法、Brent法など）でも、ITP法のような最小最大解の保証はありませんが、同様の収束速度を達成できる可能性があります。

分析

ITP法の主な利点は、 の場合に二分法よりも多くの反復を必要としないことが保証されていることです。そのため、補間が失敗した場合でも、ITP法の平均的な性能は二分法よりも優れていることが保証されています。さらに、補間が失敗しない（滑らかな関数）場合、補間に基づく手法と同様に高い収束性が得られることが保証されています。 ${\displaystyle n_{0}=0}$

最悪の場合のパフォーマンス

ITP法は推定値をスラック付きでミニマックス区間に投影するため、最大で回反復が必要となる（^[3]の定理2.1）。これは、 が と選択された場合、二分法と同様にミニマックス最適である。 ${\displaystyle n_{0}}$ ${\displaystyle n_{1/2}+n_{0}}$ ${\displaystyle n_{0}}$ ${\displaystyle n_{0}=0}$

平均的なパフォーマンス

この方法は 回以上の反復を必要としないため、平均反復回数は常に、考慮する分布に対して二分法の反復回数よりも少なくなります( ^[3]の系2.2 )。 ${\displaystyle n_{1/2}+n_{0}}$ ${\displaystyle n_{0}=0}$

漸近的パフォーマンス

関数が2回微分可能で根が単純な場合、ITP法によって生成される区間は、またはが2のべき乗ではなく、項が0に近すぎない場合、収束次数 で0に収束します（[ 3 ]^の定理2.3 ）。 ${\displaystyle f(x)}$ ${\displaystyle x^{*}}$ ${\displaystyle {\sqrt {\kappa _{2}}}}$ ${\displaystyle n_{0}\neq 0}$ ${\displaystyle n_{0}=0}$ ${\displaystyle (b-a)/\epsilon }$ ${\displaystyle {\tfrac {\epsilon 2^{n_{1/2}}}{b-a}}}$

ソフトウェア

• itp ^[4]はRに貢献したパッケージです。

参照

• 二分法
• リダーズ法
• 偽りの規則
• ブレント法

注記

1. ハイパーパラメータの詳細な説明については、kurbo ライブラリの ITP のドキュメントを参照してください。

参考文献

1. Argyros, IK; Hernández-Verón, MA; Rubio, MJ (2019). 「Secant-Like Methodsの収束について」.数学解析とその学際的応用の最新動向. pp.  141– 183. doi :10.1007/978-3-030-15242-0_5. ISBN 978-3-030-15241-3. S2CID  202156085。
2. シコルスキー、K. (1982-02-01)。「二等分が最適です」。数学。40 (1): 111–117。土井:10.1007/BF01459080。ISSN  0945-3245。S2CID  119952605。
3. Oliveira, IFD; Takahashi, RHC (2020-12-06). 「ミニマックス最適性を維持する二分法平均性能の拡張」 . ACM Transactions on Mathematical Software . 47 (1): 5:1–5:24. doi :10.1145/3423597. ISSN  0098-3500. S2CID  230586635.
4. Northrop, PJ (2023), itp: 補間、切り捨て、投影（ITP）根探索アルゴリズム

外部リンク

• 改良二分法（Kudos著）

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