はじめに（Introduction）

閾値（しきいち：threshold）に使うので、ラグランジュ補間公式について記します。

ラグランジュ補間公式

$(n+1)\ $点$\ (x_0,y_0),\ldots ,(x_n,y_n)\ $（ただし、$x_k\ 0\le k\le n$は互いに異なる）が与えられたら、
$n$次関数は__一意__に定まり次の式で表す事ができる。

\begin{align*}
& \ell_k(x) := \prod_{\substack{j = 0 \\ j\ne k}}^{n}\frac{x-x_j}{x_k-x_j} \\
& L(x) := \sum_{k=0}^{n} y_k \ell_k(x)
\end{align*}

まとめて、一つの式にすると

\begin{align*}
L(x) := \sum_{k=0}^{n}\left(y_k \prod_{\substack{j=0 \\ j\ne k}}^{n}\frac{x-x_j}{x_k-x_j} \right)
\end{align*}

例

3点$(1,20),(2,22),(3,32)$から2次関数を求めてみます。

\begin{align*}
L(x)&=20\frac{(x-2)(x-3)}{(1-2)(1-3)}+22\frac{(x-1)(x-3)}{(2-1)(2-3)}+32\frac{(x-1)(x-2)}{(3-1)(3-2)} \\
&=20\frac{(x-2)(x-3)}{2}+22\frac{(x-1)(x-3)}{-1}+32\frac{(x-1)(x-2)}{2} \\
&=10(x-2)(x-3)-22(x-1)(x-3)+16(x-1)(x-2) \\
&=10(x^2-5x+6)-22(x^2-4x+3)+16(x^2-3x+2) \\
&=(10-22+16)x^2+(10\cdot-5+-22\cdot-4+16\cdot-3)x + 10\cdot6-22\cdot3+16\cdot2 \\
&=4x^2-10x+26
\end{align*}

直感的に

$x$が互いに異なる3点$(x_0,y_0),(x_1,y_1),(x_2,y_2)$から2次関数を求める式をみてみます。

\begin{align*}
L(x)&=y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}+y_1\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}+y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} \\
\end{align*}

最初の項$\ y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$をみると、$x_0$を$x$に代入すると、分母と分子が同じになり$y_0$だけが残ります。また、$x_1,x_2$を代入すると分子が$0$となりこの項は$0$となります。
他の項も同じになるので、3点を満たす（通る）関数を導く事ができます。
$x$は互いに異なるので、分母が$0$になることはありません。

証明

式が求められることは直感的にわかりましたが__一意__に定まることが必要です。

因数定理

多項式$f(x)$が$(x-a)$を因数にもつ$\iff f(a)=0$

因数定理の証明

多項式$f(x)$を$(x-a)$で割った商を$g(x)$、あまりを$r$としたとき、$f(x)=(x-a)g(x)+r$となります。
$x$に$a$を代入すると、$f(a)=r$となり、$f(x)$が$(x-a)\ $を因数（$\ f(x)=(x-a)g(x)\ $）にもつ場合$\ r=0$が必要十分条件となります。

一意の証明

$(n+1)\ $点$\ (x_0,y_0),\ldots ,(x_n,y_n)\ $（ただし、$x_k\ 0\le k\le n$は互いに異なる）
を満たす（通る）$n$次式の関数$f(x),g(x)$を考えます。
$h(x)=f(x)-g(x)$とすると、$h(x_k)=0\ (0\le k\le n)$となります。
したがって、因数定理より$\ f(x)-g(x)=a(x-x_0)\cdots (x-x_n)\ $となります。
（各点は、$f(x)-g(x)$の因数となるためです。）
$(x-x_0)\cdots (x-x_n)\ $は$(n+1)$次関数となるなるので、$a=0$でなければなりません。
したがって、$f(x)-g(x)=0$となり、$f(x)=g(x)$となります。
これにより、__一意__となることがわかります。

さいごに

直感的にわかりやすい公式だと思います。
これを使って、閾値（しきいち）署名に適用していこうと思います。

参考（Reference）