多項式補間
補間多項式が次のような形式であるとする。
p ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 2 x 2 + a 1 x + a 0 ( 1 ) {\displaystyle p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}\qquad (1)}
p がデータ点群を補間するとは、次を意味する。
p ( x i ) = y i for all i ∈ { 0 , 1 , ... , n } {\displaystyle p(x_{i})=y_{i}\qquad {\mbox{for all }}i\in \left\{0,1,\dots ,n\right\}}
ここで式 (1) に置換すると、係数 a k {\displaystyle a_{k}} の線型方程式系が得られる。これを行列とベクトルで表すと次のようになる。
[ 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}}}
補間多項式 p ( x ) {\displaystyle p(x)} を構築するには、この方程式系を a k {\displaystyle a_{k}} について解かなければならない。
左辺の行列をファンデルモンド行列と呼ぶ。その行列式はゼロではなく、唯一の補間多項式が存在する。
ファンデルモンド行列の条件数は大きいため、係数 a i {\displaystyle a_{i}} を求めるのにガウスの消去法を使うと、大きな誤差を生じる。そのため、 O ( n 3 ) {\displaystyle {\mathcal {O}}(n^{3})} を要するガウスの消去法の代わりに、ファンデルモンド行列の特性を利用した O ( n 2 ) {\displaystyle {\mathcal {O}}(n^{2})} の数値的に安定な解法がいくつも提案されている。これらの手法はまず多項式のニュートン補間を構築し、それを上掲のような単項形式に変換する。
多項式をより複雑な曲線の近似として使う場合もあり、タイポグラフィにおける文字の形状をいくつかの点で表すなどの例がある。関連する用途としては、自然対数や三角関数の値を求める際に、数表に掲載されている点から多項式補間で必要な値を求める場合がある。これは特定の値を直接求めようとするよりもかなり高速に計算できる。多項式補間はまた、数値積分や常微分方程式の数値解を求めるアルゴリズムの基盤にもなっている。
多項式補間は、Karatsuba法やToom-Cook法(英語版)といった乗算アルゴリズムの基盤であり、積を定義する多項式上の点間の補間が積自体を生成する。例えば a = f(x) = a0x + a1x + ... と b = g(x) = b0x + b1x + ... があるとき、積 ab は W(x) = f(x)g(x) と等しい。f(x) と g(x) が小さいときの x における W(x) 上の点を求めることで、その曲線上の点が得られる。それらの点に基づく補間によって W(x) の項とさらには積 ab が得られる。Karatsuba法の場合、穏当なサイズの入力であっても単純な乗算より高速である。特にハードウェアの並列性を利用するとその特性が発揮される。