ラグランジュ補間
はじめに
ここではガウスの著作gaussよりラグランジュの補間法の導出を紹介します。組合せ論と母関数prevの内容を一部再掲します。
文字の$k$乗の和を$k$次のべき乗和といい$p_k$と表す。
$$
p_k = \sum_j a_j^k
$$
例
\begin{eqnarray} p_1 &=& a & ~+~ & b & ~+~ & c & ~+~ & d & ~+~ & .. \\ p_2 &=& a^2 & ~+~ & b^2 & ~+~ & c^2 & ~+~ & d^2 & ~+~ & .. \\ p_3 &=& a^3 & ~+~ & b^3 & ~+~ & c^3 & ~+~ & d^3 & ~+~ & .. \\ ..\end{eqnarray}
重複を許したk個の文字からなる項の和を$k$次の完全斉次式と呼び$h_k$と表す。
$$
h_k = \sum_{j_1\le j_2 \le.. \le j_k}a_{j_1}a_{j_2}~..a_{j_k}
$$
例
\begin{eqnarray} h_1 = a & ~+~ & b & ~+~ & c & ~+~ & d & ~+~ & .. \\ \end{eqnarray}\begin{eqnarray} h_2 = a^2 & ~+~ & a b & ~+~ & a c & ~+~ & a d & ~+~ & a e & ~+~ .. \\ & ~+~ & b^2 & ~+~ & b c & ~+~ & b d & ~+~ & b e & ~+~ ..\\ & & & ~+~ & c^2 & ~+~ & c d & ~+~ & c e & ~+~ .. \\ & & & & & ~+~ & d^2 & ~+~ & d e & ~+~ ..\\ & & & & & & & ~+~ & e^2 & ~+~ ..\\ \end{eqnarray}\begin{eqnarray} h_3 = a^3 & ~+~ & a^2 b & ~+~ & a^2 c & ~+~ & a^2 d & ~+~ & .. \\ & ~+~ & a b^2 & ~+~ & a b c & ~+~ & a b d & ~+~ & .. \\ & & & ~+~ & a c^2 & ~+~ & a c d & ~+~ & .. \\ & & & & & ~+~ & a d^2 & ~+~ & .. \\ & & & & & & & & \\ & ~+~ & b^3 & ~+~ & b^2 c & ~+~ & b^2 d & ~+~ & .. \\ & & & ~+~ & b c^2 & ~+~ & b c d & ~+~ & .. \\ & & & & & ~+~ & b d^2 & ~+~ & .. \\ & & & & & & & & \\ & & & & c^3 & ~+~ & c^2 d & ~+~ & .. \\ & & & & & ~+~ & c d^2 & ~+~ & .. \\ & & & & & & & & \\ & & & & & ~+~ & d^3 & ~+~ & .. \\\end{eqnarray}
\begin{eqnarray} P&:=&\frac{az}{1-az}+\frac{bz}{1-bz}+\frac{cz}{1-cz} + ~..\\ &=&p_1 z + p_2 z^2 + p_3 z^3 + ~..\\ \end{eqnarray}
\begin{eqnarray} V&:=&\frac{1}{(1-az)(1-bz)(1-cz)~..}\\ &=&(1+az+a^2z^2+~..)(1+bz+b^2z^2+~..)(1+cz+c^2z^2+~..)~..\\ &=&1+h_1z+h_2z^2+h_3z^3+~.. \end{eqnarray}
補題
まず以下のような式を考えます。
\begin{eqnarray}
S_n=\frac{a^n}{(a-b)(a-c)(a-d)..}+
\frac{b^n}{(b-a)(b-c)(b-d)..}+
\frac{c^n}{(c-a)(c-b)(c-d)..}+~..
\end{eqnarray}
文字$a,b,c,..$は互いに異なる$m$個の文字とします。ここで
\begin{eqnarray}
\alpha&=&\frac{1}{(a-b)(a-c)(a-d)..}\\
\beta&=&\frac{1}{(b-a)(b-c)(b-d)..}\\
\gamma&=&\frac{1}{(c-a)(c-b)(c-d)..}\\
..
\end{eqnarray}
とおくと$S_n=\alpha a^n+\beta b^n + \gamma c^n +~..$となります。ここで公式１のべき乗和の母関数に似た以下の式を考えます。
\begin{eqnarray}
P=\frac{\alpha}{1-ax}+\frac{\beta}{1-bx}+\frac{\gamma}{1-cx}+~..
\end{eqnarray}
幾何級数の展開より
\begin{eqnarray}
P&=&\alpha(1+ax+a^2x^2+~..)+\beta(1+bx+b^2x^2+~..)+\gamma(1+cx+c^2x^2+~..)+~..\\
&=&S_0+S_1x+S_2x^2+~..
\end{eqnarray}
ここで
\begin{eqnarray}
Q=(1-ax)(1-bx)(1-cx)..
\end{eqnarray}
とおくと
\begin{eqnarray}
PQ&=&\alpha(1-bx)(1-cx)(1-dx)..\\
&+&\beta(1-ax)(1-cx)(1-dx)..\\
&+&\gamma(1-ax)(1-bx)(1-dx)..
\end{eqnarray}
これに$x=1/a$を代入すると
\begin{eqnarray}
PQ/.(x\to1/a)=\alpha(1-b/a)(1-c/a)(1-d/a)..=1/a^{m-1}
\end{eqnarray}
$f/.(a\to b)$ という記号は$f$の$a$に$b$を代入したものという意味のMathematicaの記号です。皆さんもお使いください。同様に
\begin{eqnarray}
&&PQ/.(x\to1/b)=\beta(1-a/b)(1-c/b)(1-d/b)~..=1/b^{m-1}\\
&&PQ/.(x\to1/c)=\gamma(1-a/c)(1-b/c)(1-d/c)~..=1/c^{m-1}\\
&&..
\end{eqnarray}
ここで文字$a,b,c,..$の総数は$m$で
\begin{eqnarray}
PQ&=&\alpha(1-bx)(1-cx)(1-dx)..\\
&+&\beta(1-ax)(1-cx)(1-dx)..\\
&+&\gamma(1-ax)(1-bx)(1-ex)..
\end{eqnarray}
なので$\deg(PQ)\le m-1$です。ここで$f(x)=PQ-x^{m-1}$を考えると$\deg(f)\le m-1$かつ$f$は$m$個の異なる文字に対して$0$となるので恒等的に$0$しかありえず、$PQ=x^{m-1}$となります。
\begin{eqnarray}
P=x^{m-1}/Q = \frac{x^{m-1}}{(1-ax)(1-bx)(1-cx)..}
\end{eqnarray}
は完全斉次式の母関数に$x^{m-1}$をかけたものなので
\begin{eqnarray}
P=x^{m-1}+h_1x^{m}+h_2x^{m+1}+~..
\end{eqnarray}
また
\begin{eqnarray}
P=S_0+S_1x+S_2x^2+~..
\end{eqnarray}
より
\begin{eqnarray}
S_0 &=& S_1=S_2=~..=S_{m-2}=0\\
S_{m-1}&=&1\\
S_{m}&=&h_1=a+b+c+~..\\
S_{m+1}&=&h_2=a^2+ab+b^2+ac+bc+c^2+~..\\
..
\end{eqnarray}
となります。
例
2文字の場合
\begin{eqnarray} S_0&=&\frac{1}{a-b}+\frac{1}{b-a}=0\\ S_1&=&\frac{a}{a-b}+\frac{b}{b-a}=1\\ S_2&=&\frac{a^2}{a-b}+\frac{b^2}{b-a}=\frac{a^2-b^2}{a-b} = a+b\\ S_3&=&\frac{a^3}{a-b}+\frac{b^3}{b-a}=\frac{a^3-b^3}{a-b} = a^2+ab+b^2\\ .. \end{eqnarray}
3文字の場合
\begin{eqnarray} S_0&=&\frac{1}{(a-b)(a-c)}+\frac{1}{(b-a)(b-c)}+\frac{1}{(c-a)(c-b)} = 0\\ S_1&=&\frac{a}{(a-b)(a-c)}+\frac{b}{(b-a)(b-c)}+\frac{c}{(c-a)(c-b)} = 0\\ S_2&=&\frac{a^2}{(a-b)(a-c)}+\frac{b^2}{(b-a)(b-c)}+\frac{c^2}{(c-a)(c-b) } = 1\\ S_3&=&\frac{a^3}{(a-b)(a-c)}+\frac{b^3}{(b-a)(b-c)}+\frac{c^3}{(c-a)(c-b) } = a+b+c\\ S_4&=&\frac{a^4}{(a-b)(a-c)}+\frac{b^4}{(b-a)(b-c)}+\frac{c^4}{(c-a)(c-b) } = a^2+b^2+c^2+ab+bc+ca\\ .. \end{eqnarray}
ラグランジュ補間
さきほどの$\alpha,\beta,\gamma,..$の定義はresetしてください。$m-1$次の多項式
\begin{eqnarray}
f(x)= \alpha + \beta x + \gamma x^2 + ~..~ + \eta x^{m-1}
\end{eqnarray}
に対し、$m$個の異なる文字$a,b,c~..$を代入した以下の式を考えます。
\begin{eqnarray}
f(a)&=& \alpha + \beta a + \gamma a^2 +~.. +\eta a^{m-1}\\
f(b)&=& \alpha + \beta b + \gamma b^2 +~.. +\eta b^{m-1}\\
f(c)&=& \alpha + \beta c + \gamma c^2 +~.. +\eta c^{m-1}\\
..
\end{eqnarray}
ここで$m$個の異なる文字$a,b,c,..$に$x$を加え、以下の式を考えます。
\begin{eqnarray}
W&=&\frac{f(a)}{(a-b)(a-c)(a-d)~..~(a-x)}\\
&+&\frac{f(b)}{(b-a)(b-c)(b-d)~..~(b-x)}\\
&+&\frac{f(c)}{(c-a)(c-b)(c-d)~..~(c-x)}\\
&+&..\\
&+&\frac{f(x)}{(x-a)(x-b)(x-c)~..}
\end{eqnarray}
さきほどの補題の文字が$m+1$個の場合より、$S_0=S_1=..=S_{m-1}=0$、また $\deg(f)=m-1$ なので$W=0$よって
\begin{eqnarray}
f(x) &=& \frac{(x-b)(x-c)(x-d)~..}{(a-b)(a-c)(a-d)~..}f(a)\\
&+& \frac{(x-a)(x-c)(x-d)~..}{(b-a)(b-c)(b-d)~..}f(b)\\
&+& \frac{(x-a)(x-b)(x-d)~..}{(c-a)(c-b)(c-d)~..}f(c)\\
&+&..
\end{eqnarray}
これがラグランジュ補間の式です。この式は$x$は$a,b,c,~..$とは異なるという条件で導出しましたが、式変形の途中でその条件が緩くなり、$x=a,x=b,x=c,..$のときも成り立ちます。
例
２点を通る直線の方程式
\begin{eqnarray} f(x) &=& \frac{x-b}{a-b}f(a)+\frac{x-a}{b-a}f(b) \\ &=& f(a) + \frac{f(a)-f(b)}{a-b}(x-a) \\ &=& f(b) + \frac{f(a)-f(b)}{a-b}(x-b) \end{eqnarray}
３点を通る放物線の方程式
\begin{eqnarray} f(x) &=& \frac{(x-b)(x-c)}{(a-b)(a-c)}f(a)+\frac{(x-a)(x-c)}{(b-a)(b-c)}f(b) + \frac{(x-a)(x-b)}{(c-a)(c-b)}f(c)\\ &=& \frac{(x-b)(x-a+a-c)}{(a-b)(a-c)}f(a)+\frac{(x-a)(x-b+b-c)}{(b-a)(b-c)}f(b) + \frac{(x-a)(x-b)}{(c-a)(c-b)}f(c)\\ &=& \frac{x-b}{a-b}f(a)+\frac{x-a}{b-a}f(b) + \left(\frac{f(a)}{(a-b)(a-c)}+\frac{f(b)}{(b-a)(b-c)}+\frac{f(c)}{(c-a)(c-b)}\right)(x-a)(x-b)\\ &=& f(a) + \frac{f(a)-f(b)}{a-b}(x-a) + \frac{1}{a-c}\left(\frac{f(a)-f(b)}{a-b}-\frac{f(b)-f(c)}{b-c}\right)(x-a)(x-b) \end{eqnarray}
新しい演算・（名付けて）間分
先程の例の式はテイラー展開に似ています。ここで２点の線を結んだときの線の傾きを間分とよぶことにし、以下のような記号で表します。
\begin{eqnarray}
f(a,b)=\frac{f(a)-f(b)}{a-b}
\end{eqnarray}
二階間分を以下のように定義します。
\begin{eqnarray}
f(a,b,c)=\frac{f(a,b)-f(b,c)}{a-c}
\end{eqnarray}
二階間分を展開すると
\begin{eqnarray}
f(a,b,c)&=&\frac{f(a,b)-f(b,c)}{a-c}\\
&=&\frac{1}{a-c}\left(\frac{f(a)-f(b)}{a-b}+\frac{f(b)-f(c)}{b-c}\right)\\
&=&\frac{f(a)}{(a-b)(a-c)}+\frac{f(b)}{(b-a)(b-c)}+\frac{f(c)}{(c-a)(c-b)}
\end{eqnarray}
三階間分を展開すると
\begin{eqnarray}
f(a,b,c,d)&=&\frac{f(a,b,c)-f(b,c,d)}{a-d}\\
&=&\frac{1}{a-d}\left(\frac{f(a)}{(a-b)(a-c)}+\frac{f(b)}{(b-a)(b-c)}+\frac{f(c)}{(c-a)(c-b)}\right)\\
&-&\frac{1}{a-d}\left(\frac{f(b)}{(b-c)(b-d)}+\frac{f(c)}{(c-b)(c-d)}+\frac{f(d)}{(d-b)(d-c)}\right)\\
&=&\frac{f(a)}{(a-b)(a-c)(a-d)}+\frac{f(d)}{(d-a)(d-b)(d-c)}\\
&+&\frac{f(b)}{(a-d)(b-c)}\left(\frac{1}{b-a}-\frac{1}{b-d}\right)+\frac{f(c)}{(a-d)(c-b)}\left(\frac{1}{c-a}-\frac{1}{c-d}\right)\\
&=&\frac{f(a)}{(a-b)(a-c)(a-d)}+\frac{f(b)}{(b-a)(b-c)(b-d)}+\frac{f(c)}{(c-a)(c-b)(c-d)}+\frac{f(d)}{(d-a)(d-b)(d-c)}
\end{eqnarray}
一般に以下が成り立ちます。
\begin{eqnarray}
f(a,b,c,..)=\frac{f(a)}{(a-b)(a-c)(a-d)..}+
\frac{f(b)}{(b-a)(b-c)(b-d)..}+
\frac{f(c)}{(c-a)(c-b)(c-d)..}+~..
\end{eqnarray}
数学的帰納法を使います。文字が$n$個の表現を既知として、$n+1$個のときの表現が同じ形になることを示します。
\begin{eqnarray}
f(a,b,..,z)&=&\frac{f(a,b,..,x,y)-f(b,c,..,y,z)}{a-z}\\
&=&\frac{1}{a-z}\left(\frac{f(a)}{(a-b)(a-c)..(a-y)}+\frac{f(b)}{(b-a)(b-c)..(b-y)}+~..\frac{f(y)}{(y-a)(y-b)..(y-x)}\right)\\
&-&\frac{1}{a-z}\left(\frac{f(b)}{(b-c)(b-d)..(b-z)}+\frac{f(c)}{(c-b)(c-d)..(c-z)}+~..\frac{f(z)}{(z-b)(z-c)..(z-y)}\right)\\
&=&\frac{f(a)}{(a-b)(a-c)..(a-z)}+\frac{f(z)}{(z-a)(z-b)..(z-y)}\\
&+&\frac{1}{a-z}\frac{f(b)}{(b-c)(b-d)..(b-y)}\left(\frac{1}{b-a}-\frac{1}{b-z}\right)+\frac{1}{a-z}\frac{f(c)}{(c-b)(c-d)..(c-y)}\left(\frac{1}{c-a}-\frac{1}{c-z}\right)+~..\\
&=&\frac{f(a)}{(a-b)(a-c)..(a-z)}+\frac{f(b)}{(b-a)(b-c)..(b-z)}+~..\frac{f(z)}{(z-a)(z-c)..(z-y)}
\end{eqnarray}
補題の再解釈
はじめの補題は$f(x)=x^n$に対する間分の性質だったことが分かります。ここで$f(x)=x^n$のときの間分$f(a,b,..)$をコンパクトに$(x^n)^{a,b,..}$と書くことにすると、補題は以下のようになります。
\begin{eqnarray}
(1)^{a,b}&=&0\\
(x)^{a,b}&=&1\\
(x^2)^{a,b}&=&a+b\\
(x^3)^{a,b}&=&a^2+ab+b^2
\end{eqnarray}
\begin{eqnarray}
(1)^{a,b,c}&=&0\\
(x)^{a,b,c}&=&0\\
(x^2)^{a,b,c}&=&1\\
(x^3)^{a,b,c}&=&a+b+c\\
(x^4)^{a,b,c}&=&a^2+ab+b^2+ac+bc+c^2
\end{eqnarray}
微分との対応を考えると、$f^{a,b},f^{a,b,c},..$は$f',f'',..$と対応させることができます。ただし、定数になるとき$1$になるために正確には$f'/1!,f''/2!,..$と対応しています。
\begin{eqnarray}
(1)'&=&0\\
(x)'&=&1\\
(x^2)'&=&2x\\
(x^3)'&=&3x^2\\
\end{eqnarray}
\begin{eqnarray}
(1)''/2&=&0\\
(x)''/2&=&0\\
(x^2)''/2&=&1\\
(x^3)''/2&=&3x\\
(x^4)''/2&=&6x^2
\end{eqnarray}
こうすると間分の結果を$a=b=c=..=x$とすれば、微分の結果になります。より正確には$a=x,b=x+dx,c=x+2dx,..$とし$dx\to0$としたものと解釈できます。
間分と微分との対応
$a,b,c,..$の代わりに$x,x+dx,x+2dx,..$を入れます。
$$
\begin{array}{lll}
f(x,x+dx)&=&\frac{f(x)-f(x+dx)}{-dx} = f'(x)\\
f(x,x+dx,x+2dx)&=&\frac{1}{-2dx}\left(\frac{f(x)-f(x+dx)}{-dx} - \frac{f(x+dx)-f(x+2dx)}{-dx}\right) = \frac{f''(x)}{2}\\
..
\end{array}
$$
$f^{a,b},f^{a,b,c},f^{a,b,c,d}..$が$f',f''/2!,f'''/3!,..$に対応することが分かります。
ラグランジュ補間の別表現
さきほどの記号を使うと、$(a,f(a)),(b,f(b)),(c,f(c)..)$を通る多項式は以下のように表せます。またさきほどの考察からこれがテイラー展開の類似物であることが分かります。
\begin{eqnarray}
f(x) = f(a) + f(a,b)(x-a)+f(a,b,c)(x-a)(x-b)+~..
\end{eqnarray}
これを変形すると
\begin{eqnarray}
f(x)-f(a) &=& f(a,b)(x-a)+f(a,b,c)(x-a)(x-b)+~..\\
\frac{f(x)-f(a)}{x-a} &=& f(a,b)+f(a,b,c)(x-b)+~..\\
f(x,a)&=&f(a,b)+f(a,b,c)(x-b)+~f(a,b,c,d)(x-b)(x-c)+~..
\end{eqnarray}
同様に
\begin{eqnarray}
f(x,a,b)&=&f(a,b,c)+f(a,b,c,d)(x-c)+f(a,b,c,d,e)(x-c)(x-d)+~..\\
f(x,a,b,c)&=&f(a,b,c,d)+f(a,b,c,d,e)(x-d)+f(a,b,c,d,e,f)(x-d)(x-e)+~..\\
..\\
\end{eqnarray}
文字$a,b,c,..$の総数を$m$とします。これに$x$を加えた$m+1$個の文字による$m$階間分を$g(t)=t^n$に対して考えると
$$
(1)^{x,a,b,c,..}=(t)^{x,a,b,c,..}=~..=(t^{m-1})^{x,a,b,c,..}=0
$$
よって$m-1$次の多項式$f(t)$について
\begin{eqnarray}
f(x,a,b,..)&=& 0
\end{eqnarray}
最後の文字を$..,D,C,B,A$とすると
\begin{eqnarray}
f(x,a,b,..,A)&=&\frac{f(x,a,..,B)-f(a,b,..,A)}{x-A}=0
\end{eqnarray}
よって
\begin{eqnarray}
f(x,a,b,..,B)&=&f(a,b,..,A)
\end{eqnarray}
また変形すると
\begin{eqnarray}
\frac{f(x,a,b,..,C)-f(a,b,..,B)}{x-B}&=&f(a,b,..,A)
\end{eqnarray}
よって
\begin{eqnarray}
f(x,a,b,..,C)&=&f(a,b,..,B)+f(a,b,..,A)(x-B)
\end{eqnarray}
同様に
\begin{eqnarray}
f(x,a,b,..,D)&=&f(a,b,..,C)+f(a,b,..,B)(x-C)+f(a,b,..,A)(x-C)(x-B)\\
f(x,a,b,..,E)&=&f(a,b,..,D)+f(a,b,..,C)(x-D)+f(a,b,..,B)(x-D)(x-C)+
f(a,b,..,A)(x-D)(x-C)(x-B)\\
..
\end{eqnarray}
これを繰り返すことで以下のラグランジュ補間の別表現が得られます。
\begin{eqnarray}
f(x) = f(a) + f(a,b)(x-a)+f(a,b,c)(x-a)(x-b)+~..
\end{eqnarray}
終わりに
これはかなり面白いと思いました。ガウスの著作ではさらに$a,b,c,..$に$e^{ia},e^{ib},e^{ic},..$を入れたものを考え、三角関数の和に関する公式を導いています。ちなみにラテン語ですが、数式を追うのがメインの挑戦で、いざとなったらgoogle翻訳でいけます。ありがとうございました。
