多項式補間
関数 f を x0,...,xn というノードを結ぶn次多項式で補間したとき、その誤差は以下のようになる。
f ( x ) − p n ( x ) = f [ x 0 , ... , x n , x ] ∏ i = 0 n ( x − x i ) {\displaystyle f(x)-p_{n}(x)=f[x_{0},\ldots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})}
ここで
f [ x 0 , ... , x n , x ] {\displaystyle f[x_{0},\ldots ,x_{n},x]}
は差分商を表す。f がノード xi と x を含む微小な区間 I において n+1 階連続微分可能ならば、I 上のある ξ {\displaystyle \xi } について誤差をラグランジュ形式で次のように書くことができる。
f ( x ) − p n ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) !
ここで、次のような性質のノードの組合せを探す。
lim n → ∞ X n f = f , {\displaystyle \lim _{n\to \infty }X_{n}f=f,} for any f ∈ C ( [ a , b ] ) {\displaystyle f\in C([a,b])}
一様有界性原理(英語版)によると、Xn のノルムが一様有界であるときだけこのようなノード群が存在するが、 ‖ X n ‖ ≥ 2 π log  ( n + 1 ) + C {\displaystyle \|X_{n}\|\geq {\frac {2}{\pi }}\log(n+1)+C} であることから、そのようなノード群は存在しない。
例えば、等間隔点を補間ノードとして選択したとき、ルンゲ現象による発散が見られる。なお、その関数は単に連続であるだけでなく、区間 [−1, 1] において無限に微分可能である。チェビシェフノードより良い例は、次の定理により、見つけるのがさらに難しい。
区間 [−1, 1] で絶対連続なあらゆる関数について、チェビシェフノードで構築した一連の補間多項式は一様に f(x) に収束する。
ここで構築しようとしているのは、n次の多項式空間であるベクトル空間 Π n {\displaystyle \Pi _{n}} にある唯一の補間多項式である。 Π n {\displaystyle \Pi _{n}} の単項式基底(英語版)を用いると、ファンデルモンド行列を解いて補間多項式の係数群 a k {\displaystyle a_{k}} を構築しなければならない。これは(コンピュータのクロック数で数えると)非常にコストがかかる操作である。 Π n {\displaystyle \Pi _{n}} の別の基底を選択すると係数の計算を単純化できるが、補間多項式を単項式基底で表現するために追加の計算が必要になる。
1つの手法として、補間多項式をニュートン補間形式で書き、差分商の手法で係数を構築する(これをネヴィル法(英語版)という)。