Form of interpolation
数値解析 において 、 多項式補間は 、データセット内の点を通過する可能な限り最低次数の 多項式 によって、 特定の データセットを 補間すること です。
n + 1 個の データ ポイント のセット ( 2 つが同じではない) が与えられた場合、 各 に対して であるとき 、多項式関数は データを 補間する と言われます 。 ( x 0 , y 0 ) , … , ( x n , y n ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})} x j {\displaystyle x_{j}} p ( x ) = a 0 + a 1 x + ⋯ + a n x n {\displaystyle p(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}} p ( x j ) = y j {\displaystyle p(x_{j})=y_{j}} j ∈ { 0 , 1 , … , n } {\displaystyle j\in \{0,1,\dotsc ,n\}}
このような多項式は常に一意であり、通常は ラグランジュ多項式 と ニュートン多項式 という 2 つの明示的な式で与えられます。
アプリケーション 補間多項式の本来の用途は、 自然対数 や 三角関数 といった重要な 超越関数 の値を近似することでした。正確に計算された少数のデータ点から始めて、対応する補間多項式は任意の近傍点における関数を近似します。多項式補間は、 数値積分法 （ シンプソンの定理 ）や 数値常微分方程式 （ マルチグリッド法 ）のアルゴリズムの基礎にもなります。
コンピュータグラフィックス では 、多項式を用いて、いくつかの指定された点、例えば タイポグラフィ における文字の形状など、複雑な平面曲線を近似することができます。これは通常、ベジェ曲線を用いて行われます。 ベジェ曲線 は、指定された接線と指定された点を持つ補間多項式の単純な一般化です。
数値解析において、多項式補間は、カラツバ乗算 や トゥーム・クック乗算 などの準二次乗算および二乗算を実行するために不可欠です 。これらの乗算では、積多項式上の点を介した補間によって、必要な特定の積が得られます。たとえば、 a = f ( x ) = a 0 x 0 + a 1 x 1 + ··· および b = g ( x ) = b 0 x 0 + b 1 x 1 + ··· の場合、積 abは W ( x ) = f ( x ) g ( x )の特定の値です。 x の値が小さいときに W ( x )に沿って点を簡単に見つけることができ、それらの点に基づく補間によって W ( x )の項 と特定の積 ab が得られます。 カラツバ乗算で定式化されているように、この手法は、特に並列ハードウェア上では、入力サイズが小さい場合でも、二次乗算よりも大幅に高速です。
コンピュータサイエンス では、多項式補間は 、安全なマルチパーティ計算 や 秘密共有の アルゴリズムにもつながります 。
補間定理 2変量データポイント（ 2つとして 同じものはない） に対して、 これらのポイントを補間する 最大次数の一意の多項式が存在する 。つまり、 [1] n + 1 {\displaystyle n+1} ( x 0 , y 0 ) , … , ( x n , y n ) ∈ R 2 {\displaystyle (x_{0},y_{0}),\dotsc ,(x_{n},y_{n})\in \mathbb {R} ^{2}} x j {\displaystyle x_{j}} p ( x ) {\displaystyle p(x)} n {\displaystyle n} p ( x 0 ) = y 0 , … , p ( x n ) = y n {\displaystyle p(x_{0})=y_{0},\ldots ,p(x_{n})=y_{n}}
同様に、補間ノードを固定して選択すると 、多項式補間は 実数値の ( n +1)組と 最大 n次の実多項式の ベクトル空間との間の線形 一対一 を定義します。 x j {\displaystyle x_{j}} L n {\displaystyle L_{n}} ( y 0 , … , y n ) ∈ R n + 1 {\displaystyle (y_{0},\ldots ,y_{n})\in \mathbb {R} ^{n+1}} P ( n ) {\displaystyle P(n)} L n : R n + 1 ⟶ ∼ P ( n ) . {\displaystyle L_{n}:\mathbb {R} ^{n+1}{\stackrel {\sim }{\longrightarrow }}\,P(n).}
これはユニソルバ 定理の一種です。この定理は、 実数の代わり に任意の無限 体 、例えば有理数や複素数にも当てはまります。 R {\displaystyle \mathbb {R} }
最初の証明 次式で表されるラグランジュ基底関数 を考えます 。 L 0 ( x ) , … , L n ( x ) {\displaystyle L_{0}(x),\ldots ,L_{n}(x)} L j ( x ) = ∏ i ≠ j x − x i x j − x i = ( x − x 0 ) ⋯ ( x − x j − 1 ) ( x − x j + 1 ) ⋯ ( x − x n ) ( x j − x 0 ) ⋯ ( x j − x j − 1 ) ( x j − x j + 1 ) ⋯ ( x j − x n ) . {\displaystyle L_{j}(x)=\prod _{i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{0})\cdots (x-x_{j-1})(x-x_{j+1})\cdots (x-x_{n})}{(x_{j}-x_{0})\cdots (x_{j}-x_{j-1})(x_{j}-x_{j+1})\cdots (x_{j}-x_{n})}}.}
は次数 の多項式であり 、 各 に対して が成り立ち 、であること に注目してください 。したがって、線形結合 は となるため 、 は 次数 の補間多項式となります 。 L j ( x ) {\displaystyle L_{j}(x)} n {\displaystyle n} L j ( x k ) = 0 {\displaystyle L_{j}(x_{k})=0} j ≠ k {\displaystyle j\neq k} L k ( x k ) = 1 {\displaystyle L_{k}(x_{k})=1} p ( x ) = ∑ j = 0 n y j L j ( x ) {\displaystyle p(x)=\sum _{j=0}^{n}y_{j}L_{j}(x)} p ( x k ) = ∑ j y j L j ( x k ) = y k {\displaystyle p(x_{k})=\sum _{j}y_{j}\,L_{j}(x_{k})=y_{k}} p ( x ) {\displaystyle p(x)} n {\displaystyle n}
一意性を証明するために、任意の に対して となる、 最大 次 の 別の補間多項式が存在すると仮定する 。すると、 は最大 次 の多項式であり、 異なる零点（ ） を持つ 。しかし、最大 次 の非零多項式は 最大 個の零点を持つことができる ため 、 [a] は 零多項式、すなわち となる 。 [2] q ( x ) {\displaystyle q(x)} n {\displaystyle n} p ( x k ) = q ( x k ) {\displaystyle p(x_{k})=q(x_{k})} k = 0 , … , n {\displaystyle k=0,\dotsc ,n} p ( x ) − q ( x ) {\displaystyle p(x)-q(x)} n {\displaystyle n} n + 1 {\displaystyle n+1} x k {\displaystyle x_{k}} n {\displaystyle n} n {\displaystyle n} p ( x ) − q ( x ) {\displaystyle p(x)-q(x)} p ( x ) = q ( x ) {\displaystyle p(x)=q(x)}
第二校正 補間多項式を次の形式で書き出す。
p ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 2 x 2 + a 1 x + a 0 . {\displaystyle p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}.} 1
これを補間方程式に代入すると、 係数の 線形方程式のシステムが 得られ 、これは行列ベクトル形式で次の 乗算 として読み取られます。 p ( x j ) = y j {\displaystyle p(x_{j})=y_{j}} a j {\displaystyle a_{j}} [ x 0 n x 0 n − 1 x 0 n − 2 … x 0 1 x 1 n x 1 n − 1 x 1 n − 2 … x 1 1 ⋮ ⋮ ⋮ ⋮ ⋮ x n n x n n − 1 x n n − 2 … x n 1 ] [ a n a n − 1 ⋮ a 0 ] = [ y 0 y 1 ⋮ y n ] . {\displaystyle {\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&\ldots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&\ldots &x_{1}&1\\\vdots &\vdots &\vdots &&\vdots &\vdots \\x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&\ldots &x_{n}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.}
補間式は、 上記の行列方程式 の 解に対応します。 左辺の 行列 Xは ヴァンデルモンド行列 であり、その行列式は であることが分かっています。これは、すべての ノード が異なっているため、非ゼロです。これにより、行列は 逆行列 であり、方程式は唯一の解 を持つことが保証されます 。つまり、 が存在し、かつ唯一です。 p ( x ) {\displaystyle p(x)} A = ( a n , … , a 0 ) {\displaystyle A=(a_{n},\ldots ,a_{0})} X ⋅ A = Y {\displaystyle X\cdot A=Y} det ( X ) = ∏ 0 ≤ i < j ≤ n ( x j − x i ) , {\displaystyle \textstyle \det(X)=\prod _{0\leq i<j\leq n}(x_{j}-x_{i}),} x j {\displaystyle x_{j}} A = X − 1 ⋅ Y {\displaystyle A=X^{-1}\cdot Y} p ( x ) {\displaystyle p(x)}
推論 が次以下の多項式である 場合、 異なる点 に おける の補間多項式は それ自身です。 f ( x ) {\displaystyle f(x)} n {\displaystyle n} f ( x ) {\displaystyle f(x)} n + 1 {\displaystyle n+1} f ( x ) {\displaystyle f(x)}
補間多項式の構築 赤い点はデータポイント ( x k 、 y k ) を示し、青い曲線は補間多項式を示しています。
ラグランジュ補間 この多項式は、ラグランジュ多項式を 使って次のように直接書き表すことができます 。
行列引数の場合、この式は シルベスターの公式 と呼ばれ 、行列値のラグランジュ多項式は フロベニウス共変量 です。 p ( x ) = ( x − x 1 ) ( x − x 2 ) ⋯ ( x − x n ) ( x 0 − x 1 ) ( x 0 − x 2 ) ⋯ ( x 0 − x n ) y 0 + ( x − x 0 ) ( x − x 2 ) ⋯ ( x − x n ) ( x 1 − x 0 ) ( x 1 − x 2 ) ⋯ ( x 1 − x n ) y 1 + ⋯ + ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x n − 1 ) ( x n − x 0 ) ( x n − x 1 ) ⋯ ( x n − x n − 1 ) y n = ∑ i = 0 n ( ∏ j ≠ i 0 ≤ j ≤ n x − x j x i − x j ) y i = ∑ i = 0 n p ( x ) p ′ ( x i ) ( x − x i ) y i {\displaystyle {\begin{aligned}p(x)&={\frac {(x-x_{1})(x-x_{2})\cdots (x-x_{n})}{(x_{0}-x_{1})(x_{0}-x_{2})\cdots (x_{0}-x_{n})}}y_{0}\\[4pt]&+{\frac {(x-x_{0})(x-x_{2})\cdots (x-x_{n})}{(x_{1}-x_{0})(x_{1}-x_{2})\cdots (x_{1}-x_{n})}}y_{1}\\[4pt]&+\cdots \\[4pt]&+{\frac {(x-x_{0})(x-x_{1})\cdots (x-x_{n-1})}{(x_{n}-x_{0})(x_{n}-x_{1})\cdots (x_{n}-x_{n-1})}}y_{n}\\[7pt]&=\sum _{i=0}^{n}{\Biggl (}\prod _{\stackrel {\!0\,\leq \,j\,\leq \,n}{j\,\neq \,i}}{\frac {x-x_{j}}{x_{i}-x_{j}}}{\Biggr )}y_{i}=\sum _{i=0}^{n}{\frac {p(x)}{p'(x_{i})(x-x_{i})}}\,y_{i}\end{aligned}}}
ニュートン補間
定理 の ノードで 補間する の 次数以下の 多項式について、 です 。 の ノードで 補間する の 次数以下の多項式を とします 。すると、 は次のように与えられます。 ここで は ニュートン基底とも呼ばれ、 です 。 p n {\displaystyle p_{n}} n {\displaystyle n} f {\displaystyle f} x i {\displaystyle x_{i}} i = 0 , 1 , 2 , 3 , ⋯ , n {\displaystyle i=0,1,2,3,\cdots ,n} p n + 1 {\displaystyle p_{n+1}} n + 1 {\displaystyle n+1} f {\displaystyle f} x i {\displaystyle x_{i}} i = 0 , 1 , 2 , 3 , ⋯ , n , n + 1 {\displaystyle i=0,1,2,3,\cdots ,n,n+1} p n + 1 {\displaystyle p_{n+1}} p n + 1 ( x ) = p n ( x ) + a n + 1 w n ( x ) {\displaystyle p_{n+1}(x)=p_{n}(x)+a_{n+1}w_{n}(x)} w n ( x ) := ∏ i = 0 n ( x − x i ) {\textstyle w_{n}(x):=\prod _{i=0}^{n}(x-x_{i})} a n + 1 := f ( x n + 1 ) − p n ( x n + 1 ) w n ( x n + 1 ) {\textstyle a_{n+1}:={f(x_{n+1})-p_{n}(x_{n+1}) \over w_{n}(x_{n+1})}}
証拠：
これは、の場合 、 の場合、 の 場合について示せます 。 より小さい次数の補間多項式の一意性により 、 は必要な多項式補間です。したがって、関数は次のように表すことができます。 i = 0 , 1 , 2 , 3 , ⋯ , n {\displaystyle i=0,1,2,3,\cdots ,n} p n + 1 ( x i ) = p n ( x i ) + a n + 1 ∏ j = 0 n ( x i − x j ) = p n ( x i ) {\displaystyle p_{n+1}(x_{i})=p_{n}(x_{i})+a_{n+1}\prod _{j=0}^{n}(x_{i}-x_{j})=p_{n}(x_{i})} i = n + 1 {\displaystyle i=n+1} p n + 1 ( x n + 1 ) = p n ( x n + 1 ) + f ( x n + 1 ) − p n ( x n + 1 ) w n ( x n + 1 ) w n ( x n + 1 ) = f ( x n + 1 ) {\displaystyle p_{n+1}(x_{n+1})=p_{n}(x_{n+1})+{f(x_{n+1})-p_{n}(x_{n+1}) \over w_{n}(x_{n+1})}w_{n}(x_{n+1})=f(x_{n+1})} n + 1 {\displaystyle n+1} p n + 1 ( x ) = p n ( x ) + a n + 1 w n ( x ) {\textstyle p_{n+1}(x)=p_{n}(x)+a_{n+1}w_{n}(x)}
p n ( x ) = a 0 + a 1 ( x − x 0 ) + a 2 ( x − x 0 ) ( x − x 1 ) + ⋯ + a n ( x − x 0 ) ⋯ ( x − x n − 1 ) . {\textstyle p_{n}(x)=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+\cdots +a_{n}(x-x_{0})\cdots (x-x_{n-1}).}
多項式係数 を求めるには、 上の式を行列形式で 整理して形成される 下三角行列を 解く必要があります。 a i {\displaystyle a_{i}} p n ( x i ) = f ( x i ) = y i {\textstyle p_{n}(x_{i})=f(x_{i})=y_{i}}
[ 1 … 0 1 x 1 − x 0 1 x 2 − x 0 ( x 2 − x 0 ) ( x 2 − x 1 ) ⋮ ⋮ ⋮ ⋱ 1 x k − x 0 … … ∏ j = 0 n − 1 ( x n − x j ) ] [ a 0 ⋮ a n ] = [ y 0 ⋮ y n ] {\displaystyle {\begin{bmatrix}1&&\ldots &&0\\1&x_{1}-x_{0}&&&\\1&x_{2}-x_{0}&(x_{2}-x_{0})(x_{2}-x_{1})&&\vdots \\\vdots &\vdots &&\ddots &\\1&x_{k}-x_{0}&\ldots &\ldots &\prod _{j=0}^{n-1}(x_{n}-x_{j})\end{bmatrix}}{\begin{bmatrix}a_{0}\\\\\vdots \\\\a_{n}\end{bmatrix}}={\begin{bmatrix}y_{0}\\\\\vdots \\\\y_{n}\end{bmatrix}}} 係数は次のように導かれる。
a j := [ y 0 , … , y j ] {\displaystyle a_{j}:=[y_{0},\ldots ,y_{j}]} どこ
[ y 0 , … , y j ] {\displaystyle [y_{0},\ldots ,y_{j}]} は差分商を表す 記法である 。したがって、 ニュートン多項式は n点の多項式補間式を与えるために使用される。 [2]
証拠 最初のいくつかの係数は連立方程式を用いて計算できます。n番目の係数の形は数学的帰納法による証明のために仮定されています。
a 0 = y 0 = [ y 0 ] a 1 = y 1 − y 0 x 1 − x 0 = [ y 0 , y 1 ] ⋮ a n = [ y 0 , ⋯ , y n ] (let) {\displaystyle {\begin{aligned}a_{0}&=y_{0}=[y_{0}]\\a_{1}&={y_{1}-y_{0} \over x_{1}-x_{0}}=[y_{0},y_{1}]\\\vdots \\a_{n}&=[y_{0},\cdots ,y_{n}]\quad {\text{(let)}}\\\end{aligned}}}
Qを点の多項式補間とします 。 多項式Qに以下を加えます。 ( x 1 , y 1 ) , … , ( x n , y n ) {\displaystyle (x_{1},y_{1}),\ldots ,(x_{n},y_{n})} ( x 0 , y 0 ) {\displaystyle (x_{0},y_{0})}
Q ( x ) + a n ′ ( x − x 1 ) ⋅ … ⋅ ( x − x n ) = P n ( x ) , {\displaystyle Q(x)+a'_{n}(x-x_{1})\cdot \ldots \cdot (x-x_{n})=P_{n}(x),}
ここで 、点 の補間多項式が一意であることから 、 の係数を等しくすると 、 が得られます 。 a n ′ ( x 0 − x 1 ) … ( x 0 − x n ) = y 0 − Q ( x 0 ) {\textstyle a'_{n}(x_{0}-x_{1})\ldots (x_{0}-x_{n})=y_{0}-Q(x_{0})} ( x 0 , y 0 ) , … , ( x n , y n ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})} x n − 1 {\displaystyle x^{n-1}} a n ′ = [ y 0 , … , y n ] {\textstyle a'_{n}=[y_{0},\ldots ,y_{n}]}
したがって、多項式は次のように表すことができます。 P n ( x ) = Q ( x ) + [ y 0 , … , y n ] ( x − x 1 ) ⋅ … ⋅ ( x − x n ) . {\displaystyle P_{n}(x)=Q(x)+[y_{0},\ldots ,y_{n}](x-x_{1})\cdot \ldots \cdot (x-x_{n}).}
多項式QにQを 加えると、次の式を満たす必要があります。 ここで、Qの公式 と補間多項式が用いられています。 多項式の項は、次の 式を計算することで求められます。 つまり、Qが成り立ちます 。 ( x n + 1 , y n + 1 ) {\displaystyle (x_{n+1},y_{n+1})} [ y 1 , … , y n + 1 ] ( x n + 1 − x 1 ) ⋅ … ⋅ ( x n + 1 − x n ) = y n + 1 − Q ( x n + 1 ) {\textstyle [y_{1},\ldots ,y_{n+1}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})=y_{n+1}-Q(x_{n+1})} a n {\textstyle a_{n}} a n + 1 {\textstyle a_{n+1}} P n + 1 {\textstyle P_{n+1}} [ y 0 , … , y n + 1 ] ( x n + 1 − x 0 ) ⋅ … ⋅ ( x n + 1 − x n ) = [ y 1 , … , y n + 1 ] − [ y 0 , … , y n ] x n + 1 − x 0 ( x n + 1 − x 0 ) ⋅ … ⋅ ( x n + 1 − x n ) = ( [ y 1 , … , y n + 1 ] − [ y 0 , … , y n ] ) ( x n + 1 − x 1 ) ⋅ … ⋅ ( x n + 1 − x n ) = [ y 1 , … , y n + 1 ] ( x n + 1 − x 1 ) ⋅ … ⋅ ( x n + 1 − x n ) − [ y 0 , … , y n ] ( x n + 1 − x 1 ) ⋅ … ⋅ ( x n + 1 − x n ) = ( y n + 1 − Q ( x n + 1 ) ) − [ y 0 , … , y n ] ( x n + 1 − x 1 ) ⋅ … ⋅ ( x n + 1 − x n ) = y n + 1 − ( Q ( x n + 1 ) + [ y 0 , … , y n ] ( x n + 1 − x 1 ) ⋅ … ⋅ ( x n + 1 − x n ) ) = y n + 1 − P ( x n + 1 ) . {\displaystyle {\begin{aligned}&[y_{0},\ldots ,y_{n+1}](x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&={\frac {[y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]}{x_{n+1}-x_{0}}}(x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=\left([y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]\right)(x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=[y_{1},\ldots ,y_{n+1}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=(y_{n+1}-Q(x_{n+1}))-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=y_{n+1}-(Q(x_{n+1})+[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n}))\\&=y_{n+1}-P(x_{n+1}).\end{aligned}}} a n + 1 = y n + 1 − P n ( x n + 1 ) w n ( x n + 1 ) = [ y 0 , … , y n + 1 ] {\displaystyle a_{n+1}={y_{n+1}-P_{n}(x_{n+1}) \over w_{n}(x_{n+1})}=[y_{0},\ldots ,y_{n+1}]}
したがってそれは数学的帰納法の原理によって証明されます。
ニュートン多項式は、 等間隔で連続して並べると簡略化された形で表現できます。 x 0 , x 1 , … , x k {\displaystyle x_{0},x_{1},\dots ,x_{k}}
が 連続して等間隔に並んでおり、 i = 0, 1, ..., k で 、ある変数 x が と表されると 、その差 は と表すことができます 。したがって、ニュートン多項式は x 0 , x 1 , … , x k {\displaystyle x_{0},x_{1},\dots ,x_{k}} x i = x 0 + i h {\displaystyle {x}_{i}={x}_{0}+ih} x = x 0 + s h {\displaystyle {x}={x}_{0}+sh} x − x i {\displaystyle x-x_{i}} ( s − i ) h {\displaystyle (s-i)h}
N ( x ) = [ y 0 ] + [ y 0 , y 1 ] s h + ⋯ + [ y 0 , … , y k ] s ( s − 1 ) ⋯ ( s − k + 1 ) h k = ∑ i = 0 k s ( s − 1 ) ⋯ ( s − i + 1 ) h i [ y 0 , … , y i ] = ∑ i = 0 k ( s i ) i ! h i [ y 0 , … , y i ] . {\displaystyle {\begin{aligned}N(x)&=[y_{0}]+[y_{0},y_{1}]sh+\cdots +[y_{0},\ldots ,y_{k}]s(s-1)\cdots (s-k+1){h}^{k}\\&=\sum _{i=0}^{k}s(s-1)\cdots (s-i+1){h}^{i}[y_{0},\ldots ,y_{i}]\\&=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}].\end{aligned}}} 商差と前進差の 関係は 次式で表される： [3] をとった場合 、前のセクションでxの表現を とすると 、 ニュートンの前進補間式は 次のように表される： これは より後のすべての点の補間である 。 これは次のように展開される： [ y j , y j + 1 , … , y j + n ] = 1 n ! h n Δ ( n ) y j , {\displaystyle [y_{j},y_{j+1},\ldots ,y_{j+n}]={\frac {1}{n!h^{n}}}\Delta ^{(n)}y_{j},} y i = f ( x i ) {\displaystyle y_{i}=f(x_{i})} x = x j + s h {\displaystyle x=x_{j}+sh} f ( x ) ≈ N ( x ) = N ( x j + s h ) = ∑ i = 0 k ( s i ) Δ ( i ) f ( x j ) {\displaystyle f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{s \choose i}\Delta ^{(i)}f(x_{j})} x j {\displaystyle x_{j}} f ( x j + s h ) = f ( x j ) + s 1 ! Δ f ( x j ) + s ( s − 1 ) 2 ! Δ 2 f ( x j ) + s ( s − 1 ) ( s − 2 ) 3 ! Δ 3 f ( x j ) + s ( s − 1 ) ( s − 2 ) ( s − 3 ) 4 ! Δ 4 f ( x j ) + ⋯ {\displaystyle f(x_{j}+sh)=f(x_{j})+{\frac {s}{1!}}\Delta f(x_{j})+{\frac {s(s-1)}{2!}}\Delta ^{2}f(x_{j})+{\frac {s(s-1)(s-2)}{3!}}\Delta ^{3}f(x_{j})+{\frac {s(s-1)(s-2)(s-3)}{4!}}\Delta ^{4}f(x_{j})+\cdots }
ノードを のように並べ替えると 、ニュートン多項式は次のようになる。 x k , x k − 1 , … , x 0 {\displaystyle {x}_{k},{x}_{k-1},\dots ,{x}_{0}}
N ( x ) = [ y k ] + [ y k , y k − 1 ] ( x − x k ) + ⋯ + [ y k , … , y 0 ] ( x − x k ) ( x − x k − 1 ) ⋯ ( x − x 1 ) . {\displaystyle N(x)=[y_{k}]+[{y}_{k},{y}_{k-1}](x-{x}_{k})+\cdots +[{y}_{k},\ldots ,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots (x-{x}_{1}).} i = 0, 1, ..., k に対して が 等間隔で並んでいる 場合 、 x k , x k − 1 , … , x 0 {\displaystyle {x}_{k},\;{x}_{k-1},\;\dots ,\;{x}_{0}} x i = x k − ( k − i ) h {\displaystyle {x}_{i}={x}_{k}-(k-i)h} x = x k + s h {\displaystyle {x}={x}_{k}+sh}
N ( x ) = [ y k ] + [ y k , y k − 1 ] s h + ⋯ + [ y k , … , y 0 ] s ( s + 1 ) ⋯ ( s + k − 1 ) h k = ∑ i = 0 k ( − 1 ) i ( − s i ) i ! h i [ y k , … , y k − i ] . {\displaystyle {\begin{aligned}N(x)&=[{y}_{k}]+[{y}_{k},{y}_{k-1}]sh+\cdots +[{y}_{k},\ldots ,{y}_{0}]s(s+1)\cdots (s+k-1){h}^{k}\\&=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}].\end{aligned}}} 商差と後退差の関係は次のように表される: [ 要出典 ] 。 とすると 、前のセクションで x の表現を とすると 、 ニュートン後退補間式は 次のように表される: これは より前のすべての点の補間である 。これを展開すると、次のように表される: [ y j , y j − 1 , … , y j − n ] = 1 n ! h n ∇ ( n ) y j , {\displaystyle [{y}_{j},y_{j-1},\ldots ,{y}_{j-n}]={\frac {1}{n!h^{n}}}\nabla ^{(n)}y_{j},} y i = f ( x i ) {\displaystyle y_{i}=f(x_{i})} x = x j + s h {\displaystyle x=x_{j}+sh} f ( x ) ≈ N ( x ) = N ( x j + s h ) = ∑ i = 0 k ( − 1 ) i ( − s i ) ∇ ( i ) f ( x j ) . {\displaystyle f(x)\approx N(x)=N(x_{j}+sh)=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}\nabla ^{(i)}f(x_{j}).} x j {\displaystyle x_{j}} f ( x j + s h ) = f ( x j ) + s 1 ! ∇ f ( x j ) + s ( s + 1 ) 2 ! ∇ 2 f ( x j ) + s ( s + 1 ) ( s + 2 ) 3 ! ∇ 3 f ( x j ) + s ( s + 1 ) ( s + 2 ) ( s + 3 ) 4 ! ∇ 4 f ( x j ) + ⋯ {\displaystyle f(x_{j}+sh)=f(x_{j})+{\frac {s}{1!}}\nabla f(x_{j})+{\frac {s(s+1)}{2!}}\nabla ^{2}f(x_{j})+{\frac {s(s+1)(s+2)}{3!}}\nabla ^{3}f(x_{j})+{\frac {s(s+1)(s+2)(s+3)}{4!}}\nabla ^{4}f(x_{j})+\cdots }
菱形図 ロゼンジ図は、与えられたデータセットに対して構築できる様々な補間式を記述するために使用される図です。図の左端から右端まで引いた線は、以下の規則に従うことで補間式を表すことができます。 [4]
菱形図: 多項式補間の幾何学的表現。 左から右へのステップは加算を示し、右から左へのステップは減算を示す。 階段の傾きが正の場合、使用される項は、その差とそのすぐ下の因子の積です。階段の傾きが負の場合、使用される項は、その差とそのすぐ上の因子の積です。 ステップが水平で因子を通過する場合は、因子とその上下2項の平均との積を使用します。ステップが水平で差を通過する場合は、差とその上下2項の平均との積を使用します。 係数は次の式で表されます。 C ( u + k , n ) = ( u + k ) ( u + k − 1 ) ⋯ ( u + k − n + 1 ) n ! {\displaystyle C(u+k,n)={\frac {(u+k)(u+k-1)\cdots (u+k-n+1)}{n!}}}
同等性の証明 から への経路は 、(a) 経由 、(b) 経由、 または (c) 経由の3 つの中間ステップを経て接続できます 。これら 3 つの 2 ステップ経路の等価性を証明することで、すべての (n ステップ) 経路が同じ開始点と終了点を持つように変形できることが証明されます。これらの経路はすべて同じ式を表します。 Δ n − 1 y s {\displaystyle \Delta ^{n-1}y_{s}} Δ n + 1 y s − 1 {\displaystyle \Delta ^{n+1}y_{s-1}} Δ n y s − 1 {\displaystyle \Delta ^{n}y_{s-1}} C ( u − s , n ) {\textstyle C(u-s,n)} Δ n y s {\displaystyle \Delta ^{n}y_{s}}
パス（a）：
C ( u − s , n ) Δ n y s − 1 + C ( u − s + 1 , n + 1 ) Δ n + 1 y s − 1 {\displaystyle C(u-s,n)\Delta ^{n}y_{s-1}+C(u-s+1,n+1)\Delta ^{n+1}y_{s-1}}
パス（b）：
C ( u − s , n ) Δ n y s + C ( u − s , n + 1 ) Δ n + 1 y s − 1 {\displaystyle C(u-s,n)\Delta ^{n}y_{s}+C(u-s,n+1)\Delta ^{n+1}y_{s-1}}
パス（c）：
C ( u − s , n ) Δ n y s − 1 + Δ n y s 2 + C ( u − s + 1 , n + 1 ) + C ( u − s , n + 1 ) 2 Δ n + 1 y s − 1 {\displaystyle C(u-s,n){\frac {\Delta ^{n}y_{s-1}+\Delta ^{n}y_{s}}{2}}\quad +{\frac {C(u-s+1,n+1)+C(u-s,n+1)}{2}}\Delta ^{n+1}y_{s-1}}
パス a と b からの寄与を減算します。
Path a - Path b = C ( u − s , n ) ( Δ n y s − 1 − Δ n y s ) + ( C ( u − s + 1 , n + 1 ) − C ( u − s , n − 1 ) ) Δ n + 1 y s − 1 = − C ( u − s , n ) Δ n + 1 y s − 1 + C ( u − s , n ) ( u − s + 1 ) − ( u − s − n ) n + 1 Δ n + 1 y s − 1 = C ( u − s , n ) ( − Δ n + 1 y s − 1 + Δ n + 1 y s − 1 ) = 0 {\displaystyle {\begin{aligned}{\text{Path a - Path b}}=&C(u-s,n)(\Delta ^{n}y_{s-1}-\Delta ^{n}y_{s})+(C(u-s+1,n+1)-C(u-s,n-1))\Delta ^{n+1}y_{s-1}\\=&-C(u-s,n)\Delta ^{n+1}y_{s-1}+C(u-s,n){\frac {(u-s+1)-(u-s-n)}{n+1}}\Delta ^{n+1}y_{s-1}\\=&C(u-s,n)(-\Delta ^{n+1}y_{s-1}+\Delta ^{n+1}y_{s-1})=0\\\end{aligned}}}
したがって、パス(a)とパス(b)のどちらの寄与も同じです。パス(c)はパス(a)と(b)の平均であるため、多項式に同一の関数を寄与します。したがって、開始点と終了点が同じパスの等価性が示されます。パスを左端の角で異なる値にシフトできるかどうかを確認するには、2つのステップパスを実行するだけで十分です。(a) から まで、 または (b) から までを因数分解して まで 、 または ( c)から まで 。 y s + 1 {\displaystyle y_{s+1}} y s {\displaystyle y_{s}} Δ y s {\displaystyle \Delta y_{s}} y s + 1 {\displaystyle y_{s+1}} y s {\displaystyle y_{s}} y s {\displaystyle y_{s}} Δ y s {\displaystyle \Delta y_{s}} y s {\displaystyle y_{s}}
パス（a）
y s + 1 + C ( u − s − 1 , 1 ) Δ y s − C ( u − s , 1 ) Δ y s {\displaystyle y_{s+1}+C(u-s-1,1)\Delta y_{s}-C(u-s,1)\Delta y_{s}}
パス（b）
y s + 1 + y s 2 + C ( u − s − 1 , 1 ) + C ( u − s , 1 ) 2 Δ y s − C ( u − s , 1 ) Δ y s {\displaystyle {\frac {y_{s+1}+y_{s}}{2}}+{\frac {C(u-s-1,1)+C(u-s,1)}{2}}\Delta y_{s}-C(u-s,1)\Delta y_{s}}
パス（c）
y s {\displaystyle y_{s}}
なので 、上記の式に を代入すると、上記のすべての項が となり 、したがって同値であることがわかります。したがって、これらの経路は、左端の角から始まり、共通の点で終わるように変形することができます。 [4] Δ y s = y s + 1 − y s {\displaystyle \Delta y_{s}=y_{s+1}-y_{s}} y s {\displaystyle y_{s}}
から へ の負の傾きの横断をとると、連続して配置された すべての点の補間式が得られます 。これは、ニュートンの順方向補間式に相当します。 y 0 {\displaystyle y_{0}} Δ n y 0 {\displaystyle \Delta ^{n}y_{0}} n + 1 {\displaystyle n+1}
y ( s ) = y 0 + C ( s , 1 ) Δ y 0 + C ( s , 2 ) Δ 2 y 0 + C ( s , 3 ) Δ 3 y 0 + ⋯ = y 0 + s Δ y 0 + s ( s − 1 ) 2 Δ 2 y 0 + s ( s − 1 ) ( s − 2 ) 3 ! Δ 3 y 0 + s ( s − 1 ) ( s − 2 ) ( s − 3 ) 4 ! Δ 4 y 0 + ⋯ {\displaystyle {\begin{aligned}y(s)&=y_{0}+C(s,1)\Delta y_{0}+C(s,2)\Delta ^{2}y_{0}+C(s,3)\Delta ^{3}y_{0}+\cdots \\&=y_{0}+s\Delta y_{0}+{\frac {s(s-1)}{2}}\Delta ^{2}y_{0}+{\frac {s(s-1)(s-2)}{3!}}\Delta ^{3}y_{0}+{\frac {s(s-1)(s-2)(s-3)}{4!}}\Delta ^{4}y_{0}+\cdots \end{aligned}}}
一方、 からまで の正の傾きの横断線を取ると 、連続して配置されたすべての点の補間式が得られ 、これはニュートンの後方補間式と等価です。 y n {\displaystyle y_{n}} ∇ n y n = Δ n y 0 {\displaystyle \nabla ^{n}y_{n}=\Delta ^{n}y_{0}} n + 1 {\displaystyle n+1}
y ( u ) = y k + C ( u − k , 1 ) Δ y k − 1 + C ( u − k + 1 , 2 ) Δ 2 y k − 2 + C ( u − k + 2 , 3 ) Δ 3 y k − 3 + ⋯ = y k + ( u − k ) Δ y k − 1 + ( u − k + 1 ) ( u − k ) 2 Δ 2 y k − 2 + ( u − k + 2 ) ( u − k + 1 ) ( u − k ) 3 ! Δ 3 y k − 3 + ⋯ y ( k + s ) = y k + ( s ) ∇ y k + ( s + 1 ) s 2 ∇ 2 y k + ( s + 2 ) ( s + 1 ) s 3 ! ∇ 3 y k + ( s + 3 ) ( s + 2 ) ( s + 1 ) s 4 ! ∇ 4 y k + ⋯ {\displaystyle {\begin{aligned}y(u)&=y_{k}+C(u-k,1)\Delta y_{k-1}+C(u-k+1,2)\Delta ^{2}y_{k-2}+C(u-k+2,3)\Delta ^{3}y_{k-3}+\cdots \\&=y_{k}+(u-k)\Delta y_{k-1}+{\frac {(u-k+1)(u-k)}{2}}\Delta ^{2}y_{k-2}+{\frac {(u-k+2)(u-k+1)(u-k)}{3!}}\Delta ^{3}y_{k-3}+\cdots \\y(k+s)&=y_{k}+(s)\nabla y_{k}+{\frac {(s+1)s}{2}}\nabla ^{2}y_{k}+{\frac {(s+2)(s+1)s}{3!}}\nabla ^{3}y_{k}+{\frac {(s+3)(s+2)(s+1)s}{4!}}\nabla ^{4}y_{k}+\cdots \\\end{aligned}}}
ここで 、 はニュートン補間で導入された数値に対応する数値です。 s = u − k {\displaystyle s=u-k}
負の傾き から右に向かってジグザグの線を引くと、ガウスの順方向の式が得られます。 y 0 {\displaystyle y_{0}}
y ( u ) = y 0 + u Δ y 0 + u ( u − 1 ) 2 Δ 2 y − 1 + ( u + 1 ) u ( u − 1 ) 3 ! Δ 3 y − 1 + ( u + 1 ) u ( u − 1 ) ( u − 2 ) 4 ! Δ 4 y − 2 + ⋯ {\displaystyle y(u)=y_{0}+u\Delta y_{0}+{\frac {u(u-1)}{2}}\Delta ^{2}y_{-1}+{\frac {(u+1)u\left(u-1\right)}{3!}}\Delta ^{3}y_{-1}+{\frac {(u+1)u\left(u-1\right)(u-2)}{4!}}\Delta ^{4}y_{-2}+\cdots }
一方、正の傾き から始めると、ガウスの逆関数の式が得られます。 y 0 {\displaystyle y_{0}}
y ( u ) = y 0 + u Δ y − 1 + ( u + 1 ) u 2 Δ 2 y − 1 + ( u + 1 ) u ( u − 1 ) 3 ! Δ 3 y − 2 + ( u + 2 ) ( u + 1 ) u ( u − 1 ) 4 ! Δ 4 y − 2 + ⋯ {\displaystyle y(u)=y_{0}+u\Delta y_{-1}+{\frac {(u+1)u}{2}}\Delta ^{2}y_{-1}+{\frac {(u+1)u\left(u-1\right)}{3!}}\Delta ^{3}y_{-2}+{\frac {(u+2)(u+1)u\left(u-1\right)}{4!}}\Delta ^{4}y_{-2}+\cdots }
から右方向への水平経路をとると 、スターリングの式が得られます。 y 0 {\displaystyle y_{0}}
y ( u ) = y 0 + u Δ y 0 + Δ y − 1 2 + C ( u + 1 , 2 ) + C ( u , 2 ) 2 Δ 2 y − 1 + C ( u + 1 , 3 ) Δ 3 y − 2 + Δ 3 y − 1 2 + ⋯ = y 0 + u Δ y 0 + Δ y − 1 2 + u 2 2 Δ 2 y − 1 + u ( u 2 − 1 ) 3 ! Δ 3 y − 2 + Δ 3 y − 1 2 + u 2 ( u 2 − 1 ) 4 ! Δ 4 y − 2 + ⋯ {\displaystyle {\begin{aligned}y(u)&=y_{0}+u{\frac {\Delta y_{0}+\Delta y_{-1}}{2}}+{\frac {C(u+1,2)+C(u,2)}{2}}\Delta ^{2}y_{-1}+C(u+1,3){\frac {\Delta ^{3}y_{-2}+\Delta ^{3}y_{-1}}{2}}+\cdots \\&=y_{0}+u{\frac {\Delta y_{0}+\Delta y_{-1}}{2}}+{\frac {u^{2}}{2}}\Delta ^{2}y_{-1}+{\frac {u(u^{2}-1)}{3!}}{\frac {\Delta ^{3}y_{-2}+\Delta ^{3}y_{-1}}{2}}+{\frac {u^{2}(u^{2}-1)}{4!}}\Delta ^{4}y_{-2}+\cdots \end{aligned}}}
スターリングの式は、ガウスの前進式とガウスの後退式の平均です。
と の間の因子から右方向への水平経路をとると 、ベッセルの式が得られます。 y 0 {\displaystyle y_{0}} y 1 {\displaystyle y_{1}}
y ( u ) = 1 y 0 + y 1 2 + C ( u , 1 ) + C ( u − 1 , 1 ) 2 Δ y 0 + C ( u , 2 ) Δ 2 y − 1 + Δ 2 y 0 2 + ⋯ = y 0 + y 1 2 + ( u − 1 2 ) Δ y 0 + u ( u − 1 ) 2 Δ 2 y − 1 + Δ 2 y 0 2 + ( u − 1 2 ) u ( u − 1 ) 3 ! Δ 3 y 0 + ( u + 1 ) u ( u − 1 ) ( u − 2 ) 4 ! Δ 4 y − 1 + Δ 4 y − 2 2 + ⋯ {\displaystyle {\begin{aligned}y(u)&=1{\frac {y_{0}+y_{1}}{2}}+{\frac {C(u,1)+C(u-1,1)}{2}}\Delta y_{0}+C(u,2){\frac {\Delta ^{2}y_{-1}+\Delta ^{2}y_{0}}{2}}+\cdots \\&={\frac {y_{0}+y_{1}}{2}}+\left(u-{\frac {1}{2}}\right)\Delta y_{0}+{\frac {u(u-1)}{2}}{\frac {\Delta ^{2}y_{-1}+\Delta ^{2}y_{0}}{2}}+{\frac {\left(u-{\frac {1}{2}}\right)u\left(u-1\right)}{3!}}\Delta ^{3}y_{0}+{\frac {(u+1)u(u-1)(u-2)}{4!}}{\frac {\Delta ^{4}y_{-1}+\Delta ^{4}y_{-2}}{2}}+\cdots \\\end{aligned}}}
ヴァンデルモンドアルゴリズム 上記の2番目の証明におけるヴァンデルモンド行列は大きな条件数を持つ可能性があり 、 [ 5 ] 方程式 系を ガウス消去法 で解く場合、係数aiを計算するときに大きな誤差が発生 し ます 。
そのため、何人かの著者は、 ガウス消去法で必要なO(n3 ) ではなく、O(n2)の演算 で 数値 的に安定した解を計算するためにヴァンデルモンド行列の構造を利用するアルゴリズムを提案した。 [6] [7] [8]これらの方法は、まず多項式の ニュートン補間を 構築し、次にそれを 単項式形式 に変換することに依存している 。
非ヴァンデルモンドアルゴリズム n 次多項式の ベクトル空間 P ( n ) における補間多項式 p ( x )を求めるには、 P ( n )の通常の 単項式基底 を用い 、ガウス消去法によってヴァンデルモンド行列の逆行列を求めることで、 計算コスト は O( n 3 ) 回となる。このアルゴリズムを改良するために、 P ( n )のより簡便な基底を用いる ことで係数の計算を簡素化できる。係数は、 単項式基底 を用いて逆変換する必要がある。
一つの方法は、補間多項式を ニュートン形式 （つまりニュートン基底を用いる）で記述し、 差分商法（例えば ネヴィルのアルゴリズム ）を用いて係数を構築することです 。コストは O( n 2 )回の演算です。さらに、データセットに点が追加された場合のみO( n )回の追加作業が必要ですが 、他の方法では計算全体をやり直す必要があります。
p ( x ) の 係数 を計算するのではなく、元のデータセットには存在しない 点 x = aにおける 単一の値 p ( a )を求めることが目的である場合は、別の方法が適しています。 ラグランジュ形式は、 p ( a )の値を O( n2 ) の 計算量で計算します。 [9]
バーン スタイン形式は、 バーンスタイン による ワイエルシュトラス近似定理 の構成的証明に使用され、 ベジェ曲線 の形でコンピュータグラフィックスで大きな重要性を獲得しました 。
値の線形結合としての補間 （位置、値）データポイントの集合が与えられ、 2つの位置 が同じではない場合、補間多項式は、 に依存する の 多項式である係数を使用した 値 の 線形結合 として考えることができます 。たとえば、 ラグランジュ形式 の補間多項式は、
各係数が 指定された位置 上の対応するラグランジュ基底多項式によって与えられる 線形結合です 。 ( x 0 , y 0 ) , … , ( x j , y j ) , … , ( x n , y n ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{n},y_{n})} x j {\displaystyle x_{j}} y ( x ) {\displaystyle y(x)} y j {\displaystyle y_{j}} x {\displaystyle x} x j {\displaystyle x_{j}} y ( x ) := ∑ j = 0 k y j c j ( x ) {\displaystyle y(x):=\sum _{j=0}^{k}y_{j}c_{j}(x)} c j ( x ) {\displaystyle c_{j}(x)} x j {\displaystyle x_{j}} c j ( x ) = L j ( x 0 , … , x n ; x ) = ∏ 0 ≤ i ≤ n i ≠ j x − x i x j − x i = ( x − x 0 ) ( x j − x 0 ) ⋯ ( x − x j − 1 ) ( x j − x j − 1 ) ( x − x j + 1 ) ( x j − x j + 1 ) ⋯ ( x − x n ) ( x j − x n ) . {\displaystyle c_{j}(x)=L_{j}(x_{0},\ldots ,x_{n};x)=\prod _{0\leq i\leq n \atop i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{n})}{(x_{j}-x_{n})}}.}
係数は 値ではなく位置にのみ依存するため、 同じ係数 を使用して、同じ位置にある 2 番目のデータ ポイント セットの補間多項式を見つけること ができます。 x j {\displaystyle x_{j}} y j {\displaystyle y_{j}} ( x 0 , v 0 ) , … , ( x n , v n ) {\displaystyle (x_{0},v_{0}),\ldots ,(x_{n},v_{n})} v ( x ) := ∑ j = 0 k v j c j ( x ) . {\displaystyle v(x):=\sum _{j=0}^{k}v_{j}c_{j}(x).}
さらに、係数は 位置間の 相対的な間隔のみに依存します。したがって、点が新しい変数 （の アフィン変換 を で 反転したもの ）によって与えられる3番目のデータセットを考えると、次のようになります。 c j ( x ) {\displaystyle c_{j}(x)} x i − x j {\displaystyle x_{i}-x_{j}} t = a x + b {\displaystyle t=ax+b} x {\displaystyle x} x = t − b a {\displaystyle x={\tfrac {t-b}{a}}} ( t 0 , w 0 ) , … , ( t j , w j ) … , ( t n , w n ) with t j = a x j + b , {\displaystyle (t_{0},w_{0}),\ldots ,(t_{j},w_{j})\ldots ,(t_{n},w_{n})\qquad {\text{with}}\qquad t_{j}=ax_{j}+b,}
前の係数多項式の変換バージョンを使用できます。
c ~ j ( t ) := c j ( t − b a ) = c j ( x ) , {\displaystyle {\tilde {c}}_{j}(t):=c_{j}({\tfrac {t-b}{a}})=c_{j}(x),}
補間多項式を次のように書きます。
w ( t ) := ∑ j = 0 k w j c ~ j ( t ) . {\textstyle w(t):=\sum _{j=0}^{k}w_{j}{\tilde {c}}_{j}(t).}
データポイントは 等間隔の位置 にあることが多く 、これはアフィン変換によって に正規化されることがあります 。例えば、データポイントを考えてみましょう。 ( x j , y j ) {\displaystyle (x_{j},y_{j})} x j = j {\displaystyle x_{j}=j}
( 0 , y 0 ) , ( 1 , y 1 ) , ( 2 , y 2 ) {\displaystyle (0,y_{0}),(1,y_{1}),(2,y_{2})} 。
ラグランジュ形式の補間多項式は 線形結合である。
y ( x ) := ∑ j = 0 2 y j c j ( x ) = y 0 ( x − 1 ) ( x − 2 ) ( 0 − 1 ) ( 0 − 2 ) + y 1 ( x − 0 ) ( x − 2 ) ( 1 − 0 ) ( 1 − 2 ) + y 2 ( x − 0 ) ( x − 1 ) ( 2 − 0 ) ( 2 − 1 ) = 1 2 y 0 ( x − 1 ) ( x − 2 ) − y 1 ( x − 0 ) ( x − 2 ) + 1 2 y 2 ( x − 0 ) ( x − 1 ) . {\displaystyle {\begin{aligned}y(x):=\sum _{j=0}^{2}y_{j}c_{j}(x)&=y_{0}{\frac {(x-1)(x-2)}{(0-1)(0-2)}}+y_{1}{\frac {(x-0)(x-2)}{(1-0)(1-2)}}+y_{2}{\frac {(x-0)(x-1)}{(2-0)(2-1)}}\\&={\tfrac {1}{2}}y_{0}(x-1)(x-2)-y_{1}(x-0)(x-2)+{\tfrac {1}{2}}y_{2}(x-0)(x-1).\end{aligned}}}
たとえば、 および 。 y ( 3 ) = y 3 = y 0 − 3 y 1 + 3 y 2 {\displaystyle y(3)=y_{3}=y_{0}-3y_{1}+3y_{2}} y ( 1.5 ) = y 1.5 = 1 8 ( − y 0 + 6 y 1 + 3 y 2 ) {\displaystyle y(1.5)=y_{1.5}={\tfrac {1}{8}}(-y_{0}+6y_{1}+3y_{2})}
等間隔の点の場合も、 有限差分法 で扱うことができます。値の列の最初の差分は、 によって定義される 列です 。この操作を繰り返すと、 n 番目 の差分操作が得られ 、これは によって明示的に定義されます。 v = { v j } j = 0 ∞ {\displaystyle v=\{v_{j}\}_{j=0}^{\infty }} Δ v = u = { u j } j = 0 ∞ {\displaystyle \Delta v=u=\{u_{j}\}_{j=0}^{\infty }} u j = v j + 1 − v j {\displaystyle u_{j}=v_{j+1}-v_{j}} Δ n v = u {\displaystyle \Delta ^{n}v=u} u j = ∑ k = 0 n ( − 1 ) n − k ( n k ) v j + k . {\displaystyle u_{j}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}v_{j+k}.}
d 次の 多項式は 、正の整数点における値の列を定義し 、 この列の差は常にゼロです。 y ( x ) {\displaystyle y(x)} y j = y ( j ) {\displaystyle y_{j}=y(j)} ( d + 1 ) th {\displaystyle (d+1)^{\text{th}}}
Δ d + 1 y = 0 {\displaystyle \Delta ^{d+1}y=0} 。
したがって、 等間隔の点 ( ) における値が与えられると、次の式 が得られます。 たとえば、 2 次方程式の等間隔のデータ ポイント 4 つは に従い 、 を解くと、 上記でラグランジュ法を使用して得られたものと同じ補間方程式が得られます。 y 0 , … , y n {\displaystyle y_{0},\ldots ,y_{n}} n = d + 1 {\displaystyle n=d+1} ( − 1 ) n y 0 + ( − 1 ) n − 1 ( n 1 ) y 1 + ⋯ − ( n n − 1 ) y n − 1 + y n = 0. {\displaystyle (-1)^{n}y_{0}+(-1)^{n-1}{\binom {n}{1}}y_{1}+\cdots -{\binom {n}{n-1}}y_{n-1}+y_{n}=0.} y 0 , y 1 , y 2 , y 3 {\displaystyle y_{0},y_{1},y_{2},y_{3}} y ( x ) {\displaystyle y(x)} 0 = − y 0 + 3 y 1 − 3 y 2 + y 3 {\displaystyle 0=-y_{0}+3y_{1}-3y_{2}+y_{3}} y 3 {\displaystyle y_{3}}
補間誤差: ラグランジュ剰余公式 与えられた関数 fを n次 の 多項式で ノード x 0 ,..., x n に補間すると、次の誤差が生じる。 p n {\displaystyle p_{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})}
ここで、 データポイントの ( n +1)番目の 差 は f [ x 0 , … , x n , x ] {\textstyle f[x_{0},\ldots ,x_{n},x]}
( x 0 , f ( x 0 ) ) , … , ( x n , f ( x n ) ) , ( x , f ( x ) ) {\displaystyle (x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n})),(x,f(x))} 。
さらに、 閉区間 上で n + 1 回連続微分可能な関数 f と、 f を n + 1 個 の異なる点 で 補間する 最大 n 次 多項式に対して、誤差の ラグランジュ剰余形が 存在する。 それぞれ に対して、 I {\displaystyle I} p n ( x ) {\displaystyle p_{n}(x)} x 0 , … , x n ∈ I {\displaystyle x_{0},\ldots ,x_{n}\in I} x ∈ I {\displaystyle x\in I} ξ ∈ I {\displaystyle \xi \in I}
f ( x ) − p n ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) . {\displaystyle f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}).}
この誤差境界は、積を最小化するために 補間点 x i を選択することを示唆しており、これはチェビシェフノード によって達成されます 。 | ∏ ( x − x i ) | {\textstyle \left|\prod (x-x_{i})\right|}
ラグランジュ剰余の証明 誤差項を に設定し 、補助関数を定義します。 つまり、 R n ( x ) = f ( x ) − p n ( x ) {\textstyle R_{n}(x)=f(x)-p_{n}(x)} Y ( t ) = R n ( t ) − R n ( x ) W ( x ) W ( t ) where W ( t ) = ∏ i = 0 n ( t − x i ) . {\displaystyle Y(t)=R_{n}(t)-{\frac {R_{n}(x)}{W(x)}}W(t)\qquad {\text{where}}\qquad W(t)=\prod _{i=0}^{n}(t-x_{i}).} Y ( n + 1 ) ( t ) = R n ( n + 1 ) ( t ) − R n ( x ) W ( x ) ( n + 1 ) ! {\displaystyle Y^{(n+1)}(t)=R_{n}^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!}
しかし、は最大で n 次 までの多項式であるため 、 となり 、次の式が成り立ちます。 p n ( x ) {\displaystyle p_{n}(x)} R n ( n + 1 ) ( t ) = f ( n + 1 ) ( t ) {\textstyle R_{n}^{(n+1)}(t)=f^{(n+1)}(t)} Y ( n + 1 ) ( t ) = f ( n + 1 ) ( t ) − R n ( x ) W ( x ) ( n + 1 ) ! {\displaystyle Y^{(n+1)}(t)=f^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!}
ここで、 x i は と の根な のでとなり 、これは Y が 少なくとも n + 2 個の 根を持つことを意味します 。 ロールの定理 より、 は少なくとも n + 1 個 の根を持ち、 区間 I において反復的に少なくとも 1 つの根 ξ を 持ちます。したがって、 R n ( t ) {\displaystyle R_{n}(t)} W ( t ) {\displaystyle W(t)} Y ( x ) = Y ( x j ) = 0 {\displaystyle Y(x)=Y(x_{j})=0} Y ′ ( t ) {\displaystyle Y^{\prime }(t)} Y ( n + 1 ) ( t ) {\displaystyle Y^{(n+1)}(t)} Y ( n + 1 ) ( ξ ) = f ( n + 1 ) ( ξ ) − R n ( x ) W ( x ) ( n + 1 ) ! = 0 {\displaystyle Y^{(n+1)}(\xi )=f^{(n+1)}(\xi )-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!=0}
そして： R n ( x ) = f ( x ) − p n ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) . {\displaystyle R_{n}(x)=f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}).}
これはテイラー定理 におけるラグランジュ剰余項の背後にある論理と類似しています 。実際、テイラー剰余は、すべての補間ノード x i が同一である場合の補間誤差の特殊なケースです。 [10] 任意の i に対して、誤差はゼロになることに注意してください 。したがって、最大誤差は、連続する2つのノード間の区間のある時点で発生します。 x = x i {\displaystyle x=x_{i}}
等間隔 等間隔の補間ノードの場合 、 補間誤差式の積項は次のように制限される [ 11]。 x i = a + i h {\displaystyle x_{i}=a+ih} i = 0 , 1 , … , n , {\displaystyle i=0,1,\ldots ,n,} h = ( b − a ) / n , {\displaystyle h=(b-a)/n,} | ∏ i = 0 n ( x − x i ) | = ∏ i = 0 n | x − x i | ≤ n ! 4 h n + 1 . {\displaystyle \left|\prod _{i=0}^{n}(x-x_{i})\right|=\prod _{i=0}^{n}\left|x-x_{i}\right|\leq {\frac {n!}{4}}h^{n+1}.}
したがって、誤差境界は次のように与えられる。 | R n ( x ) | ≤ h n + 1 4 ( n + 1 ) max ξ ∈ [ a , b ] | f ( n + 1 ) ( ξ ) | {\displaystyle \left|R_{n}(x)\right|\leq {\frac {h^{n+1}}{4(n+1)}}\max _{\xi \in [a,b]}\left|f^{(n+1)}(\xi )\right|}
しかし、これは が 、すなわち によって支配されていることを前提としています 。多くの場合、これは当てはまらず、誤差は n → ∞ のにつれて実際に増加します（ ルンゲ現象 を 参照）。この問題については、「収束特性」のセクションで扱います。 f ( n + 1 ) ( ξ ) {\displaystyle f^{(n+1)}(\xi )} h n + 1 {\displaystyle h^{n+1}} f ( n + 1 ) ( ξ ) h n + 1 ≪ 1 {\displaystyle f^{(n+1)}(\xi )h^{n+1}\ll 1}
ルベーグ定数 補間ノード x 0 , ..., x n と、それらすべての補間ノードを含む 区間 [ a , b ] を固定する。補間のプロセスは、関数 f を多項式 pに写像する。これにより、[ a , b ]上のすべての連続関数の 空間 C ([ a , b ]) からそれ自身への写像 X が定義 される。写像 X は線型であり、 n 次以下 の多項式の 部分空間への 射影 である。 P ( n ) {\displaystyle P(n)}
ルベーグ定数 Lは X の 作用素ノルム として定義されます。（ ルベーグの補題 の特別な場合 ） ‖ f − X ( f ) ‖ ≤ ( L + 1 ) ‖ f − p ∗ ‖ . {\displaystyle \left\|f-X(f)\right\|\leq (L+1)\left\|f-p^{*}\right\|.}
言い換えれば、補間多項式は最良近似値よりも最大で( L +1)倍悪くなります。これは、 L を小さく する補間ノードの集合を探すことを示唆しています 。特に、 チェビシェフノード については次のようになります。 L ≤ 2 π log ( n + 1 ) + 1. {\displaystyle L\leq {\frac {2}{\pi }}\log(n+1)+1.}
等距離ノードではn の増加が指数関数的であるため、チェビシェフノードは多項式補間に非常に適していると結論付けられます 。ただし、これらのノードは最適ではありません。
収束特性 当然、どの関数クラスとどの補間ノードに対して、補間多項式の列が n → ∞ として補間関数に収束するのか、という疑問が生じます。収束は、例えば点ごと、一様、あるいは何らかの積分ノルムなど、さまざまな方法で理解できます。
等距離ノードの場合、状況はかなり悪く、無限微分可能関数でさえ一様収束が保証されない。 カール・ルンゲ による古典的な例としては、区間 [−5, 5] 上の関数 f ( x ) = 1 / (1 + x 2 ) が挙げられる。補間誤差 || f − p n || ∞は n → ∞ のにつれて無制限に増大する。別の例としては、 区間 [−1, 1] 上の関数 f ( x ) = | x | が挙げられるが、この場合、補間多項式は x = ±1, 0 の3点を除いて点収束すらしない。 [12]
異なる補間ノードを選択することで、より良い収束特性が得られると考える人もいるかもしれません。以下の結果は、むしろ有望な答えを示しているようです。
定理 - 区間 [ a , b ] 上で連続な任意の関数 f ( x ) に対して、補間多項式のシーケンスが [ a , b ] 上で f ( x )に 一様収束する ノードのテーブルが存在する 。 p n ( x ) {\displaystyle p_{n}(x)}
証拠 最良近似多項式列は f ( x )に一様収束することは明らかである（ ワイエルシュトラスの近似定理 による）。ここで、各多項式が 特定のノードにおける補間によって得られること を示すだけでよい。しかし、これは 等振動定理から知られる最良近似多項式の特殊な性質によるものである。具体的には、そのような多項式は f ( x ) と少なくとも n + 1 回交差する必要があることが分かっている 。交点を補間ノードとして選択することで、最良近似多項式と一致する補間多項式が得られる。 p n ∗ ( x ) {\displaystyle p_{n}^{*}(x)} p n ∗ ( x ) {\displaystyle p_{n}^{*}(x)}
しかし、この方法の欠点は、新しい関数 f ( x ) ごとに補間ノードを新たに計算する必要があることです。このアルゴリズムは数値的に実装するのが困難です。補間多項式の列が任意の連続関数 f ( x ) に収束するようなノードの表は存在するのでしょうか ？残念ながら、答えは「いいえ」です。
定理 - 任意のノードテーブルに対して、 区間 [ a , b ] 上の連続関数 f ( x ) が存在し、その補間多項式の列は [ a , b ] 上で発散します。 [13]
証明は本質的にルベーグ定数の下限推定値を用いるもので、これは上でX n の作用素ノルムとして定義した （ここで X nはΠ n 上の射影作用素である ）。次に、
lim n → ∞ X n f = f , for every f ∈ C ( [ a , b ] ) . {\displaystyle \lim _{n\to \infty }X_{n}f=f,{\text{ for every }}f\in C([a,b]).}
バナッハ・シュタインハウスの定理 によれば 、これは X n のノルムが一様有界である場合にのみ可能であるが、これは次の式からわかるように真ではない。
‖ X n ‖ ≥ 2 π log ( n + 1 ) + C . {\displaystyle \|X_{n}\|\geq {\tfrac {2}{\pi }}\log(n+1)+C.}
例えば、等距離点を補間ノードとして選択すると、 ルンゲ現象 から得られる関数は、そのような補間の発散を示します。この関数は連続であるだけでなく、 [−1, 1] 上で無限微分可能であることに注意してください。しかし、より優れた チェビシェフノード の場合、以下の結果により、そのような例を見つけるのは非常に困難です。
定理 - [−1, 1]上のすべての 絶対連続 関数 に対して、 チェビシェフノード上に構成される補間多項式の列は f ( x )に一様収束する。 [14]
ルンゲ現象は、 n の値が大きい場合 、補間多項式がデータ点間で大きく振動する可能性があることを示しています。この問題は、一般的に スプライン補間 を用いることで解決されます。ここで、補間式は多項式ではなく、 スプライン 、つまり低次数の複数の多項式の連鎖です。
周期関数を 調和 関数で 補間するには、 フーリエ変換 を使用します 。これは、調和関数を基底とする多項式補間の一種と見なすことができます。 三角関数補間 と 三角多項式補間 を参照してください。
エルミート補間問題とは、多項式 p の各ノードにおける値だけでなく 、与えられた次数までのすべての導関数も与えられている問題です。これは多項式合同の連立方程式と等価であり、 多項式の 中国剰余定理を用いて解くことができます。 バーコフ補間はさらに一般化されたもので、0 から a k までのすべての次数ではなく、いくつかの次数の導関数のみが与えられます 。
微分方程式と積分方程式を解く 選点法は、多項式補間に基づいています。
有理関数モデリング の手法は 、多項式関数の比を考慮した一般化です。
最後に、高次元の 多変量補間です 。
参照
注記
引用 ^ ハンフリーズ、ジェフリー、ジャービス、タイラー・J. (2020). 「9.2 補間」. 応用数学の基礎 第2巻：アルゴリズム、近似、最適化 . 産業応用数学協会. p. 418. ISBN 978-1-611976-05-2 。 ^ ab エプパーソン、ジェームズ・F. (2013). 数値解析入門 （第2版）. ホーボーケン、ニュージャージー州: Wiley. ISBN 978-1-118-36759-9 。 ^ Burden, Richard L.; Faires, J. Douglas (2011). 数値解析 （第9版）. Cengage Learning. p. 129. ISBN 9780538733519 。 ^ ab ハミング, リチャード・W. (1986). 科学者とエンジニアのための数値解析法 (第2版 (1973) 版の完全版再出版). ニューヨーク: ドーバー. ISBN 978-0-486-65241-2 。 ^ ウォルター・ガウスキ (1975)。 「ヴァンデルモンド行列の逆行列のノルム推定」。 数学数学 。 23 (4): 337–347 。 土井 :10.1007/BF01438260。 S2CID 122300795。 ^ Higham, NJ (1988). 「直交多項式を含むヴァンデルモンド型システムの高速解法」. IMA Journal of Numerical Analysis . 8 (4): 473– 486. doi :10.1093/imanum/8.4.473. ^ Björck, Å; V. Pereyra (1970). 「ヴァンダーモンド方程式系の解」. 計算数学 . 24 (112). アメリカ数学会: 893–903 . doi :10.2307/2004623. JSTOR 2004623. ^ Calvetti, D. ; Reichel, L. (1993). 「直交多項式を含むヴァンデルモンド型行列の高速逆行列計算」. BIT . 33 (3): 473– 484. doi :10.1007/BF01990529. S2CID 119360991. ^ R.ベビラクア、D.ビニ、M.カポヴァーニ、O.メンチ (2003)。 カルコロヌメリコのAppunti di Calcolo Numerico 。第 5 章、p. 89. Servizio Éditore Universitario Pisa - Azienda Regionale Diritto allo Studio Universitario。 ^ 「多項式補間における誤差」 （PDF） 。 ^ 「多項式補間に関する注記」 （PDF） . ^ Watson (1980, p. 21)は最後の例をBernstein (1912)に帰している。 ^ Watson (1980, p. 21)はこの定理をFaber (1914)に帰している。 ^ クリロフ、VI (1956)。 "Сходимость алгебраического интерполирования покорням многочленов Чебылева для абсолютно непрерывных функций и функций с ограниченным изменением" [絶対連続関数と有界変分関数のチェビシェフ多項式の根に関する代数補間の収束]。 ドクラディ・アカデミ・ナウクSSSR 。新しいシリーズ（ロシア語）。 107 : 362–365 . MR18-32。
参考文献 セルゲイ N. バーンスタイン (1912)。 「Sur l'ordre de la meilleureestimated des fonctions continue par les Polynômes de degré donné」[与えられた次数の多項式による連続関数の最良の近似の順序について]。 メム。アカド。ロイ。ベルク。 （フランス語で）。 4 ： 1～ 104。 ファーバー、ゲオルグ (1914)。 「Über die interpolatorische Darstellung stetiger Funktionen」[連続関数の補間について]。 ドイツ数学。ジャール。 （ドイツ語で）。 23 ： 192～ 210 ワトソン、G. アリスター (1980). 近似理論と数値解析法 . ジョン・ワイリー. ISBN 0-471-27706-1 。
さらに読む JL Walsh: 複素領域における有理関数による補間と近似 、AMS (Colloquium Publications, Vol.20)、ISBN 0-8218-1020-0 (1960)。第7章：「多項式による補間」
外部リンク 「補間過程」、 数学百科事典 、 EMS Press 、2001 [1994] ALGLIB には C++ / C# での実装があります。 GSLにはC言語で多項式補間コードがある 多項式補間のデモンストレーション。 
![{\displaystyle {\begin{aligned}p(x)&={\frac {(x-x_{1})(x-x_{2})\cdots (x-x_{n})}{(x_{0}-x_{1})(x_{0}-x_{2})\cdots (x_{0}-x_{n})}}y_{0}\\[4pt]&+{\frac {(x-x_{0})(x-x_{2})\cdots (x-x_{n})}{(x_{1}-x_{0})(x_{1}-x_{2})\cdots (x_{1}-x_{n})}}y_{1}\\[4pt]&+\cdots \\[4pt]&+{\frac {(x-x_{0})(x-x_{1})\cdots (x-x_{n-1})}{(x_{n}-x_{0})(x_{n}-x_{1})\cdots (x_{n}-x_{n-1})}}y_{n}\\[7pt]&=\sum _{i=0}^{n}{\Biggl (}\prod _{\stackrel {\!0\,\leq \,j\,\leq \,n}{j\,\neq \,i}}{\frac {x-x_{j}}{x_{i}-x_{j}}}{\Biggr )}y_{i}=\sum _{i=0}^{n}{\frac {p(x)}{p'(x_{i})(x-x_{i})}}\,y_{i}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be0f2572bc5be17ca8fd929b1007302527f48dda)
![{\displaystyle a_{j}:=[y_{0},\ldots,y_{j}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f40744c93b8380df3b93026cedb3e03e51e3dd2e)
![{\displaystyle [y_{0},\ldots,y_{j}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e845258d4c5470e5c7fdfdaab88ea5e9734aaf16)
![{\displaystyle {\begin{aligned}a_{0}&=y_{0}=[y_{0}]\\a_{1}&={y_{1}-y_{0} \over x_{1}-x_{0}}=[y_{0},y_{1}]\\\vdots \\a_{n}&=[y_{0},\cdots ,y_{n}]\quad {\text{(let)}}\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96894dfb37aecf78420fe33069ea351bb3706d19)
![{\textstyle a'_{n}=[y_{0},\ldots ,y_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d4a02adbe8ed05bfdae8874dd7f857e2fab3fba)
\cdot \ldots \cdot (x-x_{n}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10101a2d7cdcee1d8fd748aeb5afc7d8818c7fb7)
\cdot \ldots \cdot (x_{n+1}-x_{n})=y_{n+1}-Q(x_{n+1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/996f7d7047b7a1a5f6bc06b2514c761fceb5f4c6)
\cdot \ldots \cdot (x_{n+1}-x_{n})\\&={\frac {[y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]}{x_{n+1}-x_{0}}}(x_{n+1}-x_{0})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=\left([y_{1},\ldots ,y_{n+1}]-[y_{0},\ldots ,y_{n}]\right)(x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=[y_{1},\ldots ,y_{n+1}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=(y_{n+1}-Q(x_{n+1}))-[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n})\\&=y_{n+1}-(Q(x_{n+1})+[y_{0},\ldots ,y_{n}](x_{n+1}-x_{1})\cdot \ldots \cdot (x_{n+1}-x_{n}))\\&=y_{n+1}-P(x_{n+1}).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea80ccc10f4a7ca7ab94079d042cd31c9944f03c)
![{\displaystyle a_{n+1}={y_{n+1}-P_{n}(x_{n+1}) \over w_{n}(x_{n+1})}=[y_{0},\ldots ,y_{n+1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd7959b7e8bd0f08b2dc422c41efc6da4065717f)
![{\displaystyle {\begin{aligned}N(x)&=[y_{0}]+[y_{0},y_{1}]sh+\cdots +[y_{0},\ldots ,y_{k}]s(s-1)\cdots (s-k+1){h}^{k}\\&=\sum _{i=0}^{k}s(s-1)\cdots (s-i+1){h}^{i}[y_{0},\ldots ,y_{i}]\\&=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}].\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acde564918807b08c1c38188d11e9047abee1176)
![{\displaystyle [y_{j},y_{j+1},\ldots ,y_{j+n}]={\frac {1}{n!h^{n}}}\Delta ^{(n)}y_{j},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee85989d232921008c4803b4d1784ccbedeebb1a)
![{\displaystyle N(x)=[y_{k}]+[{y}_{k},{y}_{k-1}](x-{x}_{k})+\cdots +[{y}_{k},\ldots ,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots (x-{x}_{1}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f765e4be03523cff51f10707516961d29d30116)
![{\displaystyle {\begin{aligned}N(x)&=[{y}_{k}]+[{y}_{k},{y}_{k-1}]sh+\cdots +[{y}_{k},\ldots ,{y}_{0}]s(s+1)\cdots (s+k-1){h}^{k}\\&=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{ki}].\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/833c298afa842a34145ce3631ae774b5712e2675)
![{\displaystyle [{y}_{j},y_{j-1},\ldots ,{y}_{jn}]={\frac {1}{n!h^{n}}}\nabla ^{(n)}y_{j},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87599e592c9523e601c830c9f73cb21263beb083)
![{\displaystyle f(x)-p_{n}(x)=f[x_{0},\ldots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20e8c5d91ab5d500891ea9c0b0b528881dde5b08)
![{\textstyle f[x_{0},\ldots,x_{n},x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9429273fee3907bbb1b06a1953a8784f3b63cd7)
![{\displaystyle \left|R_{n}(x)\right|\leq {\frac {h^{n+1}}{4(n+1)}}\max _{\xi \in [a,b]}\left|f^{(n+1)}(\xi )\right|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34dc247e57d4dcc78f9484b320ed389b1ddb375c)
![{\displaystyle \lim _{n\to \infty }X_{n}f=f,{\text{ 任意の }}f\in C([a,b]).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dee3b117b4b32fbb477a4ffb88e213b0177e9b25)
