ITP法

数値解析において、ITP法（Interpolate Truncate and Projectの略）は、セカント法^[1]の超線形収束を達成しながら、二分法^[2]の最悪ケースの最適性能を維持する最初の根探索アルゴリズムです。^[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}}}$

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 }$
            そうでない場合、
        射影： 
            If then 、${\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}}}$それ
            以外の場合、
            出力
:${\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}$

この例は、二分法と比較できます§ 例: 多項式の根を求める。ITP 法では、最小最大保証にコストをかけずに、より正確な根の推定値を得るために、二分法の半分以下の反復回数しか必要としませんでした。他の方法 (Ridders、Brent など) でも、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に貢献したパッケージです。

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

• 改良された二分法、Kudos 著