補間多項式の構築
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/09/04 07:53 UTC 版)
補間多項式が次のような形式であるとする。 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})} の数値的に安定な解法がいくつも提案されている。これらの手法はまず多項式のニュートン補間を構築し、それを上掲のような単項形式に変換する。
※この「補間多項式の構築」の解説は、「多項式補間」の解説の一部です。
「補間多項式の構築」を含む「多項式補間」の記事については、「多項式補間」の概要を参照ください。
- 補間多項式の構築のページへのリンク
