0.9.11 バンデルモンド行列とラグランジュ補間
バンデルモンド行列 \( A \in M_n(F) \) は、次の形式を持ちます：
A =
\begin{bmatrix}
1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\
1 & x_2 & x_2^2 & \cdots & x_2^{n-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & x_n & x_n^2 & \cdots & x_n^{n-1}
\end{bmatrix}
ここで、\( x_1, \ldots, x_n \in F \) とし、成分は \( a_{ij} = x_i^{j-1} \) です。
この行列式は次のようになります：
\det A = \prod_{1 \le j < i \le n}(x_i - x_j)
したがって、\( x_1, \ldots, x_n \) がすべて異なるとき、バンデルモンド行列は正則（非特異）です。
このとき、バンデルモンド行列 \( A \) の逆行列 \( A^{-1} = [\alpha_{ij}] \) の成分は次のように与えられます：
\alpha_{ij} =
\frac{(-1)^{i-1} S_{n-i}(x_1, \ldots, \hat{x}_j, \ldots, x_n)}
{\prod_{k \ne j}(x_j - x_k)}
,\\ \quad i,j = 1, \ldots, n
ここで、\( S_0 = 1 \)、\( S_m(x_1, \ldots, \hat{x}_j, \ldots, x_n) \) は変数 \( x_k \)（ただし \( k \ne j \)）に関する \( m \) 次の基本対称式（elementary symmetric function）です。詳細は (1.2.14) を参照してください。
バンデルモンド行列は、次の補間問題に現れます：
係数が体 \( F \) に属する次数高々 \( n-1 \) の多項式
p(x) = a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \cdots + a_1x + a_0
が、与えられた点 \( (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) \) を通るようにしたいとき、次の補間条件を満たす必要があります：
p(x_1) = y_1 \\ p(x_2) = y_2 \\ \vdots \\ p(x_n) = y_n
これらは係数 \( a_0, \ldots, a_{n-1} \) に関する \( n \) 本の連立一次方程式であり、次の形に書けます：
A \mathbf{a} = \mathbf{y}
ここで、
\mathbf{a} =
\begin{bmatrix}
a_0 \\ a_1 \\ \vdots \\ a_{n-1}
\end{bmatrix},\quad
\mathbf{y} =
\begin{bmatrix}
y_1 \\ y_2 \\ \vdots \\ y_n
\end{bmatrix}
となり、\( A \) は前述のバンデルモンド行列です。\( x_1, \ldots, x_n \) がすべて異なれば、\( A \) は正則であるため、常に解が存在します。
この連立方程式を解くことにより補間多項式の係数を求めることも可能ですが、実用上は、補間多項式 \( p(x) \) をラグランジュ補間多項式の線形結合として表現する方が便利です。
ラグランジュ補間多項式 \( L_i(x) \) は以下のように定義されます：
L_i(x) =
\prod_{j \ne i} \frac{x - x_j}{x_i - x_j},\quad i = 1, \ldots, n
それぞれの \( L_i(x) \) は次数 \( n - 1 \) の多項式であり、次の性質を持ちます：
- \( L_i(x_i) = 1 \)
- \( L_i(x_k) = 0 \) （ただし \( k \ne i \)）
したがって、補間多項式はラグランジュの補間公式によって次のように与えられます：
p(x) = y_1 L_1(x) + y_2 L_2(x) + \cdots + y_n L_n(x)
これは補間条件を満たす、次数高々 \( n - 1 \) の多項式です。
コメント