2014/05/19

ラグランジュの補間公式とその応用例


ラグランジュの補間公式:
$x$ 座標が相異なる $n+1$ 点$(x_1,y_1), (x_2,y_2),\cdots,(x_{n+1},y_{n+1})$ を通る $n$ 次以下の多項式 $P(x)$ が1つ定まり,以下の式で表される:
$P(x)=\displaystyle\sum_{i=1}^{n+1}y_i\dfrac{f_i(x)}{f_i(x_i)}$
ただし,$f_i(x)=\displaystyle\prod_{k\neq i}(x-x_k)$

ラグランジュの補間公式

いきなり一般形を見ても複雑で意味がつかみにくいと思うので,$n=2$ の場合を書き下してみます:
$P(x)=y_1\dfrac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)}+y_2\dfrac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)}\\+y_3\dfrac{(x-x_1)(x-x_2)}{(x_3-x_1)(x_3-x_2)}$
右辺は $n=2$ 次多項式となっており,例えば右辺に $x_1$ を代入すると第一項は $y_1$,残りの項は $0$ になるので$(x_1,y_1)$ を通ります。
同様に$(x_2,y_2), (x_3,y_3)$ も通ることも分かるので,$P(x)$ が指定された $3$ 点を通る二次関数であることが分かります。

ちなみに,通る $n+1$ 点から $n$ 次以下の多項式が1つ定まるのは因数定理を用いて証明できます。
→二次関数の決定とその背景

ラグランジュ補間の応用例その1

応用例として,IMO 1981のShortlist から1問紹介します。

問題

$n$ 次多項式 $P(x)$ が,$k=0,1,\cdots,n$ に対して
$P(k)=\dfrac{1}{{}_{n+1}C_k}$ を満たすとき $P(n+1)$ を求めよ。

方針:通る $n+1$ 点が明示されているのでラグランジュの補間公式を用いて $P(x)$ を求めることができます。多少計算はゴツイですが,機械的な計算で解答できます。

解答

本問では補間点は $x_i=i$ である。
まずはラグランジュの補間公式における $f_i(x_i)=f_i(i)$ を求める。
$f_i(i)=(i-0)(i-1)\cdots 1\cdot(-1)\cdots(i-n)=i!(n-i)!(-1)^{n-i} $
求めるのは $P(n+1)$ なので,次に $f_i(n+1)$ を計算する。
$f_i(n+1)=\displaystyle\prod_{k\neq i}(n+1-k)=\dfrac{(n+1)!}{(n+1-i)}$
よって,ラグランジュの補間公式から,$y_i=\dfrac{1}{{}_{n+1}C_i}$ に注意すると,
$P(n+1)=\displaystyle\sum_{i=0}^ny_i\dfrac{f_i(n+1)}{f_i(i)}\\
=\displaystyle\sum_{i=0}^n\dfrac{(n+1-i)!i!}{(n+1)!}\dfrac{(n+1)!}{i!(n-i)!(-1)^{n-i}(n+1-i)}\\
=\displaystyle\sum_{i=0}^n(-1)^{i-n}\\
=\displaystyle\sum_{i=0}^n(-1)^{n-i}$
これは $n$ が偶数のときに $1$ で奇数のとき $0$ となる。

ラグランジュの補間公式の応用例その2

次は,USAMO(アメリカ数学オリンピック)の問題です。ラグランジュの補間公式は実際に多項式を求めるためだけでなく,多項式の存在を示すときにも使われます。

問題

任意の $n$ 次モニック多項式(最高次の係数が1の多項式)$F(x)$ が,$n$ 個の実根を持つ2つの $n$ 次モニック多項式の和で表されることを示せ。

方針:$n$ 個の実根を持つ多項式を構成するのが難しいところです。中間値の定理より,十分振動する関数(正負を行き来する関数)を構成すればよいわけです。

解答

ラグランジュの補間公式より,$(1,Y_1),(2,Y_2),(3,Y_3),\cdots,(n,Y_n)$ を通る $n-1$ 次以下の関数 $P(x)$ が存在する。ここで,$Y_i$ を $i$ が奇数のとき十分大きな数,偶数のときに十分小さな数とすれば $P(x)$ は激しく振動する。
これを利用して $n$ 個の実根を持つ $n$ 次モニック多項式を以下のように構成する:
$Q(x)=P(x)+(x-1)(x-2)\cdots(x-n)$
$R(x)=2F(x)-Q(x)$

あとは $Q(x),R(x)$ が $n$ 個の実根を持つことを示せば良い。

実際 $Q(1)=P(1) > 0,Q(2)=P(2) <0$ などから中間値の定理より $Q(x)$ は実根を $n-1$ 個持つが,残り1つの根も実数である。(複素数が解なら共役複素数も解になる→共役複素数の覚えておくべき性質

また,$F(x)$ の値が無視できるくらい $P(x)$ を激しく振動させれば $R(x)$ も激しく振動して同様な議論により実根を $n$ 個持つことが分かる。

※厳密にはどれくらい $Y_i$ を大きく取ればよいか議論する必要があります。


ちなみにラグランジュ補間は情報理論にも応用があります!→(k,n)しきい値法とシャミアの秘密分散法

USAMOの問題は非常に歯ごたえがあります

Tag: 各地の数オリの過去問