多項式補間
多項式補間（たこうしきほかん、英: polynomial interpolation）は、数値解析において、与えられたデータ群を多項式で内挿（補間）することである。言い換えれば、標本調査などで得たデータ群について、それらを正確に通る多項式を見つけることである。
用途
多項式をより複雑な曲線の近似として使う場合もあり、タイポグラフィにおける文字の形状をいくつかの点で表すなどの例がある。関連する用途としては、自然対数や三角関数の値を求める際に、数表に掲載されている点から多項式補間で必要な値を求める場合がある。これは特定の値を直接求めようとするよりもかなり高速に計算できる。多項式補間はまた、数値積分や常微分方程式の数値解を求めるアルゴリズムの基盤にもなっている。
多項式補間は、Karatsuba法やToom-Cook法といった乗算アルゴリズムの基盤であり、積を定義する多項式上の点間の補間が積自体を生成する。例えば a = f(x) = a0x0 + a1x1 + ... と b = g(x) = b0x0 + b1x1 + ... があるとき、積 ab は W(x) = f(x)g(x) と等しい。f(x) と g(x) が小さいときの x における W(x) 上の点を求めることで、その曲線上の点が得られる。それらの点に基づく補間によって W(x) の項とさらには積 ab が得られる。Karatsuba法の場合、穏当なサイズの入力であっても単純な乗算より高速である。特にハードウェアの並列性を利用するとその特性が発揮される。
定義
n+1 個のデータ点 (xi,yi) があり、xi には同じ値のものがないとする。ここで、
赤い点はデータ点 (xk,yk)T を表し、青い曲線は補間多項式を表している。 補間多項式が次のような形式であるとする。
多項式補間と同じ種類の言葉
- 多項式補間のページへのリンク
