ラグランジュ補間
$ N+1個の標本点$ (x_i, y_i)から$ N次多項式$ P(x)を$ O(N^2)の計算量で補間する。特に標本点が等差数列のときは$ O(N) 次のような関数$ Q_i(x)を定める。
$ Q_i(x) = \frac{(x-x_0)(x-x_1)...(x-x_N)}{x-x_i} = \frac{\prod_{j=0}^{N} (x-x_j)}{x-x_i}
$ Q_i(x)は$ x = x_iのときのみ値を持ち、それ以外の標本点では0になるという性質をもつ。
この$ Q_i(x)を用いて$ P(x)を表すとすると
$ P(x) = c_0 Q_0(x) + c_1 Q_1(x) + ... + c_N Q_N(x)
となる。$ c_iは定数係数である。ここで$ P(x)に$ x_iを代入すると
$ P(x_i) = c_i Q_i(x_i) = y_i
が成り立つことから
$ c_i = \frac{y_i}{Q_i(x_i)}
と求まる。$ Q_i(x)は$ O(N)で求められるため、ある定数$ Tについて$ P(T)は$ O(N^2)で求められる。
特に、標本点が$ P(0), P(1), ..., P(N)のとき
$ Q_i(x) = \frac{\prod_{j=0}^{N} (x-j)}{x-i}
$ c_i Q_i(x) = y_i \frac{Q_i(x)}{Q_i(i)} = y_i \frac{\prod_{j=0}^{N}(x-j)}{(-1)^{N-i}\cdot i!(N-i)!(x-i)}
となるので、$ \prod_{j=0}^{N}(x-j)と$ (i!)^{-1}を$ O(N)で前計算しておけば各$ c_i Q_i(x)が$ O(1)で求められるので全体で$ O(N)で求められる。