ラグランジュ補間多項式(ラグランジュ補間公式)
概要
n個のデータの組(x_k, y_k) (k=1, \cdots , n)が与えられており、かつその標本点\{x_k\}が全て互いに異なるとき、
\begin{equation}
P(x_k) = y_k \ \ \ \ \ \ \ (k=1, \cdots, n)
\end{equation}
を満たすn-1次多項式P(x)を見つけることができ、以下のように書ける。
\begin{equation}
\begin{align*}
P(x) &= \sum_{i=1}^n y_i L_i(x) \\
L_i(x) &= \frac{(x-x_1)(x-x_2) \cdots (x-x_{i-1})(x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_1)(x_i-x_2) \cdots (x_i-x_{i-1})(x_i-x_{i+1}) \cdots (x_i - x_n)} \\
&= \underset{k \neq i}{ \underset{ k=1 }{ \overset{n}{\Pi} } } \frac{x - x_k }{ x_i - x_k }
\end{align*}
\end{equation}
これがLagrange補間公式であり、式(2)はLagrange補間多項式と呼ばれる。
ここで、
\begin{equation}
W (x) \equiv \overset{n}{ \underset{k=1}{\Pi} } ( x - x_k )
\end{equation}
とおくと、式(2)のL_i (x)は、
\begin{equation}
L_i (x) = \frac{ W(x) }{ ( x - x_i ) } \cdot \frac{1}{ W' ( x_i ) } = \frac{ W ( x ) }{ ( x - x_i ) W' ( x_i)}
\end{equation}
のように書くことができ、従って式(2)のP(x)は、
\begin{equation}
P(x) = \sum_{i=1}^n y_i \frac{ W ( x ) }{ ( x - x_i ) W' ( x_i)}
\end{equation}
とも書ける。
証明
まず、式(1)を満たすようなn-1次以下の多項式は一意的に存在することを確かめる。
\begin{equation}
P(x) = \sum_{j=0}^{n-1} a_j x^j
\end{equation}
とおくとき、これが式(1)を満たすためには(a_0, \cdots ,a_{n-1})に関する以下の連立1次方程式が成り立つ必要がある。
\begin{equation}
\left\{
\begin{align*}
y_1 &= a_0 + a_1 x_1 + a_2 x_1^2 + \cdots + a_{n-1} x_1^{n-1} \\
y_2 &= a_0 + a_1 x_2 + a_2 x_2^2 + \cdots + a_{n-1} x_2^{n-1} \\
&\qquad \qquad \qquad \vdots \\
y_n &= a_0 + a_1 x_n + a_2 x_n^2 + \cdots + a_{n-1} x_n^{n-1}
\end{align*}
\right.
\end{equation}
これは、
\begin{equation}
\begin{bmatrix}
y_1 \\
y_2 \\
\vdots \\
y_n
\end{bmatrix} =
\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 \\
1 &x_n &x_n^2 &\cdots &x_n^{n-1}
\end{bmatrix}
\begin{bmatrix}
a_0 \\
a_1 \\
\vdots \\
a_{n-1}
\end{bmatrix}
\end{equation}
を解くことと同じである。ここで、
\begin{equation}
V_n (x_1, \cdots , x_n) \equiv
\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 \\
1 &x_n &x_n^2 &\cdots &x_n^{n-1}
\end{bmatrix}
\end{equation}
はn次Vandermonde行列と呼ばれ\{ x_k \} (k=1, \cdots ,n)の中に同じものがない限りその行列式は非ゼロであることが以下のように示される。
\begin{align}
det V_n &=
\begin{vmatrix}
1 &x_1 &x_1^2 &\cdots &x_1^{n-1} \\
1 &x_2 &x_2^2 &\cdots &x_2^{n-1} \\
& &\vdots \\
1 &x_n &x_n^2 &\cdots &x_n^{n-1}
\end{vmatrix} \\
&=
\left|
\begin{array}{c|cccc}
1 &x_1 &x_1^2 &\cdots &x_1^{n-1} \\
\hline \\
0 &x_2 - x_1 &x_2^2 - x_1^2 &\cdots &x_2^{n-1} - x_1^{n-1} \\
& &\vdots \\
0 &x_n - x_1 &x_n^2 - x_1^2 &\cdots &x_n^{n-1} - x_1^{n-1}
\end{array}
\right| \\
&=
\left|
\begin{array}{cccc}
x_2 - x_1 &x_2^2 - x_1^2 &\cdots &x_2^{n-2} - x_1^{n-2} &x_2^{n-1} - x_1^{n-1} \\
x_3 - x_1 &x_3^2 - x_1^2 &\cdots &x_3^{n-2} - x_1^{n-2} &x_3^{n-1} - x_1^{n-1} \\
& &\vdots \\
x_n - x_1 &x_n^2 - x_1^2 &\cdots &x_n^{n-2} - x_1^{n-2} &x_n^{n-1} - x_1^{n-1}
\end{array}
\right|
\end{align}
ここで式(11)は式(10)において第2行以降の行から第1行を引いて変形したものであり、式(12)は式(11)を第1列に対して展開したものである。なお式(12)では次の式変形の説明のために列方向の要素を多めに書き出している。次に、各列の(-x_1 )倍を次の列に足すという操作を施す。なお、足すことにより列の値は変化してしまうので、一番後ろの列から順に操作を行っていく(図1)。
図1. 式変形のイメージ
{\footnotesize
\begin{align}
det V_n &=
\left|
\begin{array}{cccc}
x_2 - x_1 &x_2^2 - x_1^2 - x_1(x_2 - x_1) &\cdots &x_2^{n-2} - x_1^{n-2} -x_1 ( x_2^{n-3} - x_1^{n-3} ) &x_2^{n-1} - x_1^{n-1} -x_1 (x_2^{n-2} - x_1^{n-2}) \\
\\
x_3 - x_1 &x_3^2 - x_1^2 - x_1(x_3 - x_1) &\cdots &x_3^{n-2} - x_1^{n-2} -x_1 ( x_3^{n-3} - x_1^{n-3} ) &x_3^{n-1} - x_1^{n-1} -x_1 (x_3^{n-2} - x_1^{n-2}) \\
& &\vdots \\
x_n - x_1 &x_n^2 - x_1^2 - x_1 ( x_n - x_1 ) &\cdots &x_2^{n-2} - x_1^{n-2} - x_1 ( x_n^{n-3} - x_1^{n-3} ) &x_n^{n-1} - x_1^{n-1} - x_1 ( x_n^{n-2} - x_1^{n-2} )
\end{array}
\right| \\
&=
\left|
\begin{array}{ccccc}
x_2 - x_1 &x_2^2-x_1 x_2 &\cdots &x_2^{n-2} - x_1 x_2^{n-3} &x_2^{n-1} - x_1 x_2^{n-2} \\
\\
x_3 - x_1 &x_3^2-x_1 x_3 &\cdots &x_3^{n-2} - x_1 x_3^{n-3} &x_3^{n-1} - x_1 x_3^{n-2} \\
& &\vdots \\
x_n - x_1 &x_n^2 - x_1 x_n &\cdots &x_n^{n-2} - x_1 x_n^{n-3} &x_n^{n-1} - x_1 x_n^{n-2}
\end{array}
\right| \\
&=
\left|
\begin{array}{ccccc}
x_2 - x_1 &x_2(x_2 - x_1) &\cdots &x_2^{n-3}( x_2 - x_1 ) &x_2^{n-2} ( x_2 - x_1 ) \\
\\
x_3 - x_1 &x_3 ( x_3 - x_1 ) &\cdots &x_3^{n-3} ( x_3 - x_1 ) &x_3^{n-2} (x_3 - x_1 ) \\
& &\vdots \\
x_n - x_1 &x_n ( x_n - x_1 ) &\cdots &x_n^{n-3} ( x_n - x_1 ) &x_n^{n-2} ( x_n - x_1 )
\end{array}
\right| \\
&= ( x_2 - x_1 ) (x_3 - x_1 ) \cdots ( x_n - x_1 )
\left|
\begin{array}{ccccc}
1 &x_2 &\cdots &x_2^{n-3} &x_2^{n-2} \\
1 &x_3 &\cdots &x_3^{n-3} &x_3^{n-2} \\
& &\vdots \\
1 &x_n &\cdots &x_n^{n-3} &x_n^{n-2} \\
\end{array}
\right| \\
&= \underset{ j=2 }{ \overset{n}{\Pi} } ( x_j - x_1 )
\left|
\begin{array}{ccccc}
1 &x_2 &\cdots &x_2^{n-3} &x_2^{n-2} \\
1 &x_3 &\cdots &x_3^{n-3} &x_3^{n-2} \\
& &\vdots \\
1 &x_n &\cdots &x_n^{n-3} &x_n^{n-2} \\
\end{array}
\right|
\end{align}
}
よってこれを繰り返していくことで、
\begin{equation}
\begin{align*}
det V_n &= \underset{ j=2 }{ \overset{n}{\Pi} } ( x_j - x_1 )
\underset{ k=3 }{ \overset{n}{\Pi} } ( x_k - x_2 )
\cdots
\underset{ l=n-1 }{ \overset{n}{\Pi} } ( x_l - x_{n-2} )
\cdot
( x_n - x_{n-1}) \\
&= \underset{ j > i }{ \overset{n}{\Pi} } ( x_j - x_i )
\end{align*}
\end{equation}
と書ける。ここで標本点\{ x_k \} ( k=1, \cdots , n )は全て異なるものとするという仮定から式(18)の右辺は非ゼロ、つまり
\begin{equation}
det V_n \neq 0
\end{equation}
である。従って式(9)の行列式が非ゼロであり、V_nの逆行列が存在するため式(8)の連立一次方程式の解は一意に存在することが分かる。
上のことから、n個のデータの組\{( x_k , y_k ) \}に対して式(1)を満たすn-1次多項式P(x)が1つでも見つかれば、それが唯一のものである、つまり一意であることが分かる。そこで次のような多項式を考える。
\begin{equation}
P(x) = \sum_{i=1}^n y_i L_i(x)
\end{equation}
\begin{equation}
\begin{align*}
L_i(x) &= \frac{(x-x_1)(x-x_2) \cdots (x-x_{i-1})(x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_1)(x_i-x_2) \cdots (x_i-x_{i-1})(x_i-x_{i+1}) \cdots (x_i - x_n)} \\
&= \underset{k \neq i}{ \underset{ k=1 }{ \overset{n}{\Pi} } } \frac{x - x_k }{ x_i - x_k }
\end{align*}
\end{equation}
これが式(1)を満たすことは明らかである。以下にこれを示す。
式(21)にx_jを代入したとき、
\begin{equation}
L_i ( x_j ) = \frac{ ( x_j - x_1 )( x_j - x_2 ) \cdots ( x_j - x_{i-1} )( x_j - x_{i+1} ) \cdots ( x_j - x_n ) }{ ( x_i - x_1 )( x_i - x_2 ) \cdots ( x_i - x_{i-1} )( x_i - x_{i+1} ) \cdots ( x_i - x_n ) }
\end{equation}
j=iであれば
\begin{equation}
\begin{align*}
L_i ( x_{j=i} ) &= \frac{ ( x_i - x_1 )( x_i - x_2 ) \cdots ( x_i - x_{i-1} )( x_i - x_{i+1} ) \cdots ( x_i - x_n ) }{ ( x_i - x_1 )( x_i - x_2 ) \cdots ( x_i - x_{i-1} )( x_i - x_{i+1} ) \cdots ( x_i - x_n ) } \\
&= 1
\end{align*}
\end{equation}
であり、j \neq iであればL_i ( x_j )の分子の中に必ず0となる因子が含まれているので、
\begin{equation}
L_i ( x_{j \neq j} ) = 0
\end{equation}
となる、つまり式(23)、(24)より
\begin{equation}
L_i ( x_j ) = \delta_{ij}
\end{equation}
である。よって、式(20)の右辺にx = x_jを代入すると、
\begin{equation}
\begin{align*}
P ( x_j ) &= \sum_{i=1}^n y_i L_i ( x_j ) \\
&= \sum_{i=1}^n y_i \delta_{ij} \\
&= y_j
\end{align*}
\end{equation}
となり、式(20)は点( x_j , y_j )を通ることが示される。
以上でLagnrangeの補間公式が証明できた。
最後に式(4)について導出する。式(3)を微分すると、
\begin{equation}
\begin{align*}
W'(x) = 1 \cdot ( x - x_2 ) \cdots ( x - x_n ) + ( x - x_1 ) \cdot 1 \cdot ( x - x_3 ) \cdots ( x - x_n ) \\
+ \cdots + ( x - x_1 ) \cdots ( x - x_{n-1} ) \cdot 1
\end{align*}
\end{equation}
となる。ここにx=x_iを代入すると、式(27)のうち( x - x_i )の因子を含む項は全て0になるので、
\begin{equation}
W'( x_i ) = ( x_i - x_1 ) \cdots ( x_i - x_{i-1} ) \cdot 1 \cdot ( x_i - x_{i+1} ) \cdots ( x - x_{n-1} )
\end{equation}
と書ける。これは式(2)のL_i (x)の分母そのものである。一方で、L_i (x)の分子はW(x)を( x - x_i )で割ったものであるから、
\begin{equation}
L_i (x) = \frac{ W(x) }{ ( x - x_i ) } \cdot \frac{1}{ W' ( x_i ) } = \frac{ W ( x ) }{ ( x - x_i ) W' ( x_i)}
\end{equation}
と書ける。
以上
Discussion