Recursive algorithms for computing Birkhoff interpolation polynomials

技術要約：ビルクホフ補間多項式を計算するための再帰的アルゴリズム

問題提起
本論文は、古典的なエルミート補間問題の一般化であるビルクホフ補間問題を取り扱う。各ノードにおける微分条件が連続しているエルミート補間とは異なり、ビルクホフ補間は微分の連続性を要求しない。この構造の欠如により、問題はより複雑になる。具体的には、斉次条件を満たす多項式の集合はイデアルを形成せず、問題の正則性を判定する統一的な基準や、補間多項式の形式を直接指定する方法が存在しない。ガウス消去法のような既存の手法はこれらの問題を解くことができるが、多くの場合、高い計算コストと記憶容量を必要とする。さらに、近年の再帰的なアプローチ（例：RHBPIA）は特定のケースに対処しているが、必要以上に高次の補間基底を生成する場合がある。

手法
著者らは、シューレス補行列（Schur complement）およびシルベスター恒等式（Sylvester identity）の理論に基づいた2つの再帰的アルゴリズム、アルゴリズム1およびアルゴリズム2を提案している。これらのアルゴリズムは、もともとエルミート補間のために設計された一般化再帰的多項式補間アルゴリズム（GRPIA）を一般化したものである。

1. 理論的枠組み:

   • 本論文では、「強正当補間基底（strongly proper interpolation basis）」を、最初の $i$ 個の多項式が最初の $i$ 個の補間条件に対して正当な基底を形成する数列として定義する。
   • シューレス補行列を用いることで、著者らはニュートン型の基底および対応する補間多項式を計算するための再帰的公式を導出している。$k$ 個目の条件までの補間多項式 $p_{k-1}(x)$ は、基底多項式と補間値を含む行列のシューレス補行列として表される。
   • このアプローチは、シルベスター恒等式を利用して補助多項式（$g_{j,k-1}(x)$）を再帰的に更新し、各ステップで系全体を再計算する必要を回避している。

2. アルゴリズム1:

   • 範囲: 単項微分演算子（例：$\delta_{x_\beta} \circ D_x^\alpha$）と評価汎関数から構成されるビルクホフ問題向けに設計されている。
   • メカニズム: ニュートン型の基底を反復的に構築する。各ステップ $k$ において、判定条件 $g^{(\alpha_k)}_{k-2, k-1}(x_{\beta_k}) \neq 0$ をチェックする。これにより、関連するヴァンデルモンド行列の非特異性が保証される。
   • 調整: 判定条件が失敗した場合、基礎となる単項式基底の次数を上げ（$x$ を乗じる）、条件が満たされるまで再計算を行う。
     easily
   • 最適化: このアルゴリズムはガウス消去法を暗黙的に体現しているが、$k$ 番目の基底を計算する際に最初の $k$ 個の条件のみに計算を制限することで、行列の下三角部分全体へのアクセスを回避している。

3. アルゴリズム2:

   • 範囲: 微分演算子が単一の単項式ではなく、微分多項式（微分の線形結合）であるより一般的な条件を扱うために、アルゴリズム1を拡張したものである。
   • メカニズム: 並べ替え戦略を導入している。現在の条件 $L_k$ に対して判定条件が失敗した場合、アルゴリズムは後続の条件（$L_{k+s}$）をチェックする。後の条件が非ゼロの値を与える場合は、$L_k$ と $L_{k+s}$ の位置を入れ替え、基底が強正当であり続けるようにする。
   • 次数低減: この並べ替え機能により、アルゴリズム2は、初期の順序を厳格に守るアルゴリズム1と比較して、より低次の補間多項式を生成できる可能性がある。

主な貢献

• GRPIAの一般化: 本研究は、再帰的な補間技術をエルミート補間から、より広範なクラスであるビルクホフ補間問題へと拡張した。
• 強正当基底の構築: 「強正当補間基底」およびニュートン型基底を生成するための構成的な方法を提供し、各再帰ステップにおいて問題が適切に定まる（well-posed）ことを保証している。
• 判定条件: 再帰プロセス中にヴァンデルモンド行列の非特異性を動的に検証するための、判定条件の組み込みが核心的な貢献である。
• 2つのアルゴリズムによるアプローチ:
  • アルゴリズム1は、計算オーバーヘッドを抑えた単項微分演算子のための再帰的解法を提供する。
  • アルゴリズム2は、一般的な微分多項式条件を扱い、低次の解を得るための条件の並べ替えメカニズムを備えている。

結果と性能
論文では、数値例（例題1–4）を通じてアルゴリズムを検証し、従来のガウス消去法およびRHBPIAアルゴリズムと比較を行っている。

• 計算効率: 再帰的アプローチは、計算コストと記憶容量を大幅に削減する。条件を逐次的に処理し、すべての補助多項式を保持しないことで、ガウス消去法で必要とされるフル行列操作を回避している。
• 次数低減: 例題1において、提案手法は最小次数の補間多項式（次数3）を導出したが、文献[16]のRHBPIA法は同じ問題に対して次数6の多項式を生成した。
• 柔軟性: 例題2は、アルゴリズム2が条件を並べ替えることで、アルゴリズム1（判定条件を満たすために基底の次数を上げる必要がある場合がある）よりも低次の解（次数3）を見つけられることを示している。

意義と主張
著者らは、提案する再帰的アプローチが、ビルクホフ補間において従来のガウス消去法に代わる、より効率的な選択肢となることを主張している。シューレス補行列とシルベスター恒等式を活用することで、計算量とメモリ要件の両方を削減している。さらに、判定条件の導入により、各ステップでの問題の正当性が保証される。本論文は、アルゴリズム2を、一般的な微分多項式条件を扱い、条件の並べ替えを通じて結果となる多項式の次数を最小化するメカニズムを提供することで、既存の手法（特にRHBPIA）に対する重要な進歩として位置づけている。本研究は、非イデアル補間設定における補間基底を構築するための統一的な理論的枠組みに寄与するものである。