Polynomial Interpolation

個人的メモ

まずラグランジュの補間多項式より $f(x) = \sum_{i = 0}^{n-1} v_i \cdot \Pi_{j = 0, j \neq i}^{n-1} \frac{x - u_j}{u_i - u_j}$ が成り立つ. ここで $s_i \overset{\mathrm{def}}{=} \Pi_{j=0, j \neq i}^{n-1} \frac{1}{u_i - u_j}$ とすると $f(x) = \sum_{i=0}^{n-1} v_i s_i \cdot \Pi_{j=0, j \neq i}^{n-1} (x - u_j)$ と書き直せる.
まず前処理として $s_i (0 \le i < n)$ を高速に求める手法について説明する.
今 $g(x) \overset{\mathrm{def}}{=} \Pi_{j=0}^{n-1} (x - u_j)$ とすると $s_i$ の値は $g(x)$ の導関数 $g'(x)$ を用いて $s_i = g'(u_i)^{-1}$ のように計算できるため結局 $g'(u_0), \dots, g'(u_{n-1})$ の値を multipoint_evaluation を用いて $\O(n \log^2 n)$ で求めれば $s_i (0 \le i < n)$ の値は求まる.
よって問題は $f(x) = \sum_{i=0}^{n-1} v_i s_i \cdot \Pi_{j=0, j \neq i}^{n-1} (x - u_j)$ の形で表される多項式 $f$ と $n$ 個の組 $(u_0, v_0 s_0), \dots, (u_{n-1}, v_{n-1} s_{n-1})$ が分かっているときに多項式 $f$ の各項の係数を求めることと言える. そしてこの問題は以下のようにして再帰的に解くことができる.
多項式 $r_0(x), r_1(x)$ を $r_0(x) \overset{\mathrm{def}}{=} \sum_{i=0}^{n/2-1} v_i s_i \cdot \Pi_{j=0, j \neq i}^{n / 2 - 1} (x - u_j)$, $r_1(x) \overset{\mathrm{def}}{=} \sum_{i=n/2}^{n-1} v_i s_i \cdot \Pi_{j=n/2, j \neq i}^{n - 1} (x - u_j)$ と定めれば $f(x) = r_0(x) \Pi_{j=n/2}^{n-1} (x - u_j) + r_1(x) \Pi_{j=0}^{n/2} (x - u_j)$ と書き直せる.
ここで $r_0(x)$ は $(u_0, v_0 s_0), \dots, (u_{n/2-1}, v_{n/2-1}s_{n/2-1})$ の $n / 2$ 個の値の組から復元するというサイズ $n / 2$ の問題を再帰的に解くことで求めることができる. $r_1(x)$ についても同様である.
よって分割統治法を用いてこの問題を解くことができ, 計算時間 $T(n)$ は $T(n) = 2 T(n / 2) + \O( n \log n) \Rightarrow T(n) = \O( n \log^2 n)$ となる. 前処理などと合わせても合計 $\O( n \log^2 n)$ 時間でこの問題を解くことができる($\Pi_{j=l}^{r} (x - u_j)$ の部分も $\O (n \log^2 n)$ 時間かけて前計算しておく).