Newton補間

同義語:ニュートン補間Newton interpolationNewton補間多項式Newtonの補間公式Newton補間公式Newtonの前進差分公式差分商(補間)差分商表均差divided differenceHermite–Genocchiの公式

概要

Newton補間(Newton interpolation)とは、相異なる点 $x_0,\dots,x_n$ での値を通る次数 $n$ 以下の多項式を $\sum_{k=0}^nf[x_0,\dots,x_k]\prod_{j< k}(x-x_j)$ の形に書いて計算する方法である。係数の差分商は表の形に並べて順に計算でき、点を 1 つ足しても前の係数は変わらない。誤差は $f[x_0,\dots,x_n,x]\prod_{j\le n}(x-x_j)$ と書け、$f$ が $n+1$ 回微分可能なら $f^{(n+1)}(\xi)/(n+1)!$ を用いた式になる。関数の表の補間、数値積分や数値微分の公式の導出に使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Lagrange補間, Rolleの定理, Taylorの定理

いくつかの点で値が分かっている関数を、多項式に置き換えて計算したいとする。たとえば $\sqrt{100}=10$、$\sqrt{121}=11$、$\sqrt{144}=12$ から $\sqrt{115}$ の近似値を求める。3 点を通る 2 次式の値は $10.72276$ で、真の値 $10.72381$ との差は $0.00105$ である。もう少し精度が欲しくて $\sqrt{169}=13$ を足すと、Lagrange補間 の公式では基本多項式がすべて変わるので、はじめから計算し直すことになる。
Newton 補間は、補間多項式を
$$ p_n(x)=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)+\cdots+c_n(x-x_0)\cdots(x-x_{n-1}) $$
の形に書く方法である。係数 $c_k$ は 差分商 とよばれる量で、表の形に並べて順に計算できる。点を 1 つ足すと、項が 1 つ増えるだけで前の係数は変わらない。上の例では $p_3(x)=p_2(x)+c_3(x-100)(x-121)(x-144)$ となり、$c_3\approx3.137\times10^{-7}$ を足すと $p_3(115)\approx10.72357$ に改善する。
補間多項式がただ 1 つ存在することは Lagrange補間 の定理「Lagrange 補間」にある。この記事は、差分商の公式、Newton の形が補間多項式を与えること、誤差の式、計算の手順と例題、公式が使えない場合を扱う。

定義と使える条件

以下、$x_0,x_1,\dots$ は実数、$f$ は実数値の関数とする。点の数を $n+1$ 個とし、次数 $n$ 以下の多項式で補間する。

差分商

相異なる点 $x_i,x_{i+1},\dots,x_{i+k}$ に対し、$f$ の $k$ 階の差分商 $f[x_i,\dots,x_{i+k}]$ を次の漸化式で定める。
$$ f[x_i]:=f(x_i),\qquad f[x_i,\dots,x_{i+k}]:=\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}\quad(k\ge1). $$

分母は、並びの 両端の点の差 である。1 階の差分商 $f[a,b]=\dfrac{f(b)-f(a)}{b-a}$ は平均変化率で、割線法 の定義「差分商と収束の次数」と同じものである。2 階は
$$ f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0} $$
である。

Newton の形

相異なる点 $x_0,\dots,x_n$ に対し、$N_0(x):=1$、$N_k(x):=\prod_{j=0}^{k-1}(x-x_j)$($k\ge1$)とおく。多項式
$$ p_n(x):=\sum_{k=0}^nf[x_0,\dots,x_k]\,N_k(x) $$
を $f$ の Newton の補間多項式 といい、補間多項式をこの形に書くことを Newton 補間 という。

この公式を使う条件は次のとおりである。

  • (i) 点 $x_0,\dots,x_n$ は相異なる。同じ点を重ねるのは、導関数の値も与えるとき(prop-nip-confluent)に限る。
  • (ii) 公式を立てるのに必要なのは点での値だけで、$f$ の連続性も要らない。
  • (iii) 誤差の式 cor-nip-error は、$f$ が $n+1$ 回微分可能であることを使う。
  • (iv) 点は等間隔でなくてよく、大きさの順に並んでいなくてもよい。prop-nip-forward の公式だけは等間隔を使う。

公式の表

公式使える条件根拠
$p_n=p_{n-1}+f[x_0,\dots,x_n]\,N_n$、$p_0=f(x_0)$点が相異なるthm-nip-main
$f[x_0,\dots,x_n]=\displaystyle\sum_{i=0}^n\dfrac{f(x_i)}{\prod_{j\ne i}(x_i-x_j)}$点が相異なるprop-nip-basic
差分商は点の並べ方によらない点が相異なるprop-nip-basic
$f$ が次数 $n$ 未満の多項式なら $n$ 階の差分商は $0$、$x^n+\cdots$ なら $1$$n\ge1$ で点が相異なるprop-nip-basic
$f(x)-p_n(x)=f[x_0,\dots,x_n,x]\,N_{n+1}(x)$$x$ は補間点と異なる。$f$ に条件なしthm-nip-error
$f[x_0,\dots,x_n]=\dfrac{f^{(n)}(\xi)}{n!}$$f$ が $n$ 回微分可能、$n\ge1$thm-nip-mean
$f(x)-p_n(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}N_{n+1}(x)$$f$ が $n+1$ 回微分可能cor-nip-error
$f[x_0,\dots,x_n]=\displaystyle\int_{\Sigma_n}f^{(n)}\bigl(\textstyle\sum_it_ix_i\bigr)\,dt_1\cdots dt_n$$f$ が $C^n$ 級、$n\ge1$prop-nip-hg
$f[\underbrace{a,\dots,a}_{k+1}]=\dfrac{f^{(k)}(a)}{k!}$$f$ が $C^k$ 級。重複点の定義prop-nip-hg
$p_n(x_0+sh)=\displaystyle\sum_{k=0}^n\binom sk\Delta^kf_0$点が等間隔 $x_i=x_0+ih$prop-nip-forward

差分商の定義・陽公式・導関数との関係と Newton の公式は DLMF §3.3(iii)・(iv) の式 (3.3.34)〜(3.3.36)・(3.3.38) にある。

主定理と証明

Newton の補間公式

次の定理が、差分商が Newton の形の係数であることを述べる。証明の要点は、補間多項式の最高次の係数に注目することである。

Newton の補間公式

$x_0,\dots,x_n$ を相異なる点とし、$k=0,\dots,n$ に対し、$x_0,\dots,x_k$ で $f$ と同じ値をとる次数 $k$ 以下の多項式を $p_k$ とする。このとき
$$ p_k(x)=p_{k-1}(x)+f[x_0,\dots,x_k]\,N_k(x)\qquad(k=1,\dots,n) $$
である。したがって $p_n=\sum_{k=0}^nf[x_0,\dots,x_k]N_k$ は、$x_0,\dots,x_n$ で $f$ と同じ値をとる次数 $n$ 以下のただ 1 つの多項式である。

相異なる点の並び $y_0,\dots,y_k$ に対し、そこで $f$ と同じ値をとる次数 $k$ 以下の多項式はただ 1 つある(Lagrange補間 の定理「Lagrange 補間」)。その $x^k$ の係数を $c(y_0,\dots,y_k)$ と書く。$k=0$ では $c(y_0)=f(y_0)$ である。
ステップ 1:係数の漸化式。 $k\ge1$ とし、$q$ を $y_0,\dots,y_{k-1}$ での補間多項式、$r$ を $y_1,\dots,y_k$ での補間多項式とする。どちらも次数 $k-1$ 以下である。
$$ P(x):=\frac{(x-y_0)\,r(x)-(x-y_k)\,q(x)}{y_k-y_0} $$
とおくと $P$ の次数は $k$ 以下である。$P(y_0)=q(y_0)=f(y_0)$、$P(y_k)=r(y_k)=f(y_k)$ であり、$0< j< k$ なら $q(y_j)=r(y_j)=f(y_j)$ なので
$$ P(y_j)=\frac{(y_j-y_0)-(y_j-y_k)}{y_k-y_0}\,f(y_j)=f(y_j) $$
である。よって $P$ は $y_0,\dots,y_k$ での補間多項式である。$x^k$ の係数を比べると
$$ c(y_0,\dots,y_k)=\frac{c(y_1,\dots,y_k)-c(y_0,\dots,y_{k-1})}{y_k-y_0} $$
を得る。これは def-nip-dd の漸化式と同じなので、$k$ についての帰納法により $c(y_0,\dots,y_k)=f[y_0,\dots,y_k]$ である。
ステップ 2:項が 1 つ増えること。 $p_k-p_{k-1}$ は次数 $k$ 以下で、$x_0,\dots,x_{k-1}$ で $0$ になる。よって定数 $c$ を用いて $p_k-p_{k-1}=cN_k$ と書ける。$p_{k-1}$ の次数は $k-1$ 以下なので、$c$ は $p_k$ の $x^k$ の係数であり、ステップ 1 により $c=f[x_0,\dots,x_k]$ である。
$p_0$ は定数 $f(x_0)$ なので、$k=1,\dots,n$ の式を足せば $p_n$ の表示を得る。$\square$

図: 点を 1 つずつ足したときの Newton の補間多項式。各段で前の多項式に 1 項足す 図: 点を 1 つずつ足したときの Newton の補間多項式。各段で前の多項式に 1 項足す
ステップ 1 の $c(y_0,\dots,y_k)$ は点の並べ方によらずに定まる量なので、次の性質がすぐに従う。

差分商の基本性質

$x_0,\dots,x_n$ を相異なる点とする。

  1. 陽公式:$f[x_0,\dots,x_n]=\sum_{i=0}^nf(x_i)\big/\prod_{j\ne i}(x_i-x_j)$ である。
  2. 対称性:点の並びを入れ替えても $f[x_0,\dots,x_n]$ は変わらない。
  3. 線形性:定数 $a,b$ に対し $(af+bg)[x_0,\dots,x_n]=af[x_0,\dots,x_n]+bg[x_0,\dots,x_n]$ である。
  4. $n\ge1$ とする。$f$ が次数 $n$ 未満の多項式なら $f[x_0,\dots,x_n]=0$ であり、$f$ が $x^n$ の係数 $1$ の次数 $n$ の多項式なら $f[x_0,\dots,x_n]=1$ である。

thm-nip-main の証明のステップ 1 より、$f[x_0,\dots,x_n]$ は補間多項式の $x^n$ の係数である。補間多項式は点の集合だけで決まるので、2 が成り立つ。Lagrange の公式 $p_n=\sum_if(x_i)L_i$ で、$L_i=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}$ の $x^n$ の係数は $1/\prod_{j\ne i}(x_i-x_j)$ なので、1 が成り立つ。3 は 1 から従う。4 は、$f$ の次数が $n$ 以下なら補間多項式が $f$ 自身であることによる。$\square$

点の順を変えて変わらないのは最高階の差分商 $f[x_0,\dots,x_n]$ で、途中の係数は変わる(ex-nip-add の直後の注意)。

誤差の式

差分商を使うと、誤差は 1 行で書ける。

差分商による誤差の式

$x_0,\dots,x_n$ を相異なる点、$x$ をこれらと異なる点とする。$f$ が $x_0,\dots,x_n,x$ で定義されていれば
$$ f(x)-p_n(x)=f[x_0,\dots,x_n,x]\,N_{n+1}(x) $$
である。

$x_{n+1}:=x$ として、$n+1$ の場合の thm-nip-main を使う。$p_{n+1}=p_n+f[x_0,\dots,x_n,x]N_{n+1}$ で、$p_{n+1}$ は $x$ で $f$ と同じ値をとるので、$f(x)=p_n(x)+f[x_0,\dots,x_n,x]N_{n+1}(x)$ である。$\square$

右辺の差分商は $f(x)$ を含むので、この式だけでは誤差は分からない。そこで差分商の大きさを導関数で測る。

差分商の平均値の定理

$n\ge1$ とし、$I$ を区間、$x_0,\dots,x_n\in I$ を相異なる点、$f\colon I\to\mathbb R$ を $n$ 回微分可能とする。このとき $\min_ix_i< \xi< \max_ix_i$ を満たす $\xi$ があって
$$ f[x_0,\dots,x_n]=\frac{f^{(n)}(\xi)}{n!} $$
である。

$g:=f-p_n$ とおく。$g$ は $n$ 回微分可能で、$x_0,\dots,x_n$ の $n+1$ 点で $0$ になる。隣り合う零点の間に Rolleの定理 を使うと、$g'$ は相異なる $n$ 点で $0$ になり、これらは $\min_ix_i$ と $\max_ix_i$ の間の開区間にある。同じことを繰り返すと、$g^{(n)}(\xi)=0$ となる $\xi$ が同じ開区間にある。$p_n$ の $x^n$ の係数は $f[x_0,\dots,x_n]$ なので $p_n^{(n)}=n!\,f[x_0,\dots,x_n]$ である。よって $0=f^{(n)}(\xi)-n!\,f[x_0,\dots,x_n]$ となる。$\square$

$n=1$ はふつうの 平均値の定理 である。2 つの定理を合わせると、誤差の式の標準の形を得る。

導関数による誤差の式

$I$ を区間、$x_0,\dots,x_n\in I$ を相異なる点、$f\colon I\to\mathbb R$ を $n+1$ 回微分可能とする。各 $x\in I$ に対し、$x,x_0,\dots,x_n$ を含む最小の閉区間の中に
$$ f(x)-p_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\,N_{n+1}(x) $$
を満たす $\xi$ がある。とくに、閉区間 $J\subset I$ が $x,x_0,\dots,x_n$ を含み、$J$ で $\lvert f^{(n+1)}\rvert\le M$ なら、$\lvert f(x)-p_n(x)\rvert\le\dfrac{M}{(n+1)!}\lvert N_{n+1}(x)\rvert$ である。

$x$ が補間点なら両辺は $0$ である。そうでないとき、$x,x_0,\dots,x_n$ の $n+2$ 点に thm-nip-mean を使って thm-nip-error に代入する。$\square$

これは Lagrange補間 の定理「補間の誤差」と同じ内容である。差分商の形の利点は、$f$ の導関数が分からなくても誤差の目安が得られることである。$f^{(n+1)}$ の変化が小さければ $f[x_0,\dots,x_n,x]\approx f[x_0,\dots,x_{n+1}]$ なので、
$$ f(x)-p_n(x)\approx f[x_0,\dots,x_{n+1}]\,N_{n+1}(x) $$
となる。つまり 次の項の大きさが、今の誤差の目安になる(ex-nip-sqrt)。

重複点と導関数

thm-nip-mean は、点が 1 点に集まる極限で差分商が導関数に近づくことを示唆している。これを正確に述べるのが次の積分表示である。

Hermite–Genocchi の公式

$n\ge1$、$\Sigma_n:=\{(t_1,\dots,t_n):t_i\ge0,\ t_1+\cdots+t_n\le1\}$ とし、$t_0:=1-t_1-\cdots-t_n$ とおく。$I$ を区間、$f\colon I\to\mathbb R$ を $C^n$ 級、$x_0,\dots,x_n\in I$ を相異なる点とすると
$$ f[x_0,\dots,x_n]=\int_{\Sigma_n}f^{(n)}(t_0x_0+t_1x_1+\cdots+t_nx_n)\,dt_1\cdots dt_n $$
である。右辺は $x_0,\dots,x_n$ が重なっていても意味をもち、$(x_0,\dots,x_n)\in I^{n+1}$ について連続である。そこで、点が重なるときの差分商を右辺で定める。すべての点が $a$ なら、$\Sigma_k$ の体積が $1/k!$ なので $f[a,\dots,a]=f^{(k)}(a)/k!$($a$ が $k+1$ 個)である。

要点:$n$ についての帰納法による。$t_n$ について先に積分すると、$f^{(n)}$ の積分が $f^{(n-1)}$ の差になり、差分商の漸化式が現れる。

詳しい証明を開く

$n=1$ の右辺は $\int_0^1f'(x_0+t_1(x_1-x_0))\,dt_1=\frac{f(x_1)-f(x_0)}{x_1-x_0}$ である。$n\ge2$ とし、$n-1$ で成り立つとする。$t_1,\dots,t_{n-1}$ を止めて $s:=1-t_1-\cdots-t_{n-1}$、$u:=t_1x_1+\cdots+t_{n-1}x_{n-1}$ とおく。$t_n$ は $0$ から $s$ まで動き、$t_0=s-t_n$ なので、被積分関数の引数は $u+sx_0+t_n(x_n-x_0)$ である。$t_n$ で積分すると $$\int_0^sf^{(n)}\bigl(u+sx_0+t_n(x_n-x_0)\bigr)\,dt_n=\frac{f^{(n-1)}(u+sx_n)-f^{(n-1)}(u+sx_0)}{x_n-x_0}$$ となる。これを $\Sigma_{n-1}$ の上で積分すると、帰納法の仮定により、右辺の第 1 項は点の並び $x_n,x_1,\dots,x_{n-1}$ の差分商、第 2 項は並び $x_0,x_1,\dots,x_{n-1}$ の差分商になる($s$ が $\Sigma_{n-1}$ の $t_0$ にあたる)。prop-nip-basic の対称性により $$\frac{f[x_1,\dots,x_n]-f[x_0,\dots,x_{n-1}]}{x_n-x_0}=f[x_0,\dots,x_n]$$ である。連続性は、$f^{(n)}$ がコンパクト集合の上で一様連続であることによる。$\square$

点を $z_0\le z_1\le\cdots\le z_n$ と並べると、$z_i\ne z_{i+k}$ なら def-nip-dd の漸化式が(連続性により)そのまま成り立ち、$z_i=z_{i+k}$ なら全部が同じ点なので値は $f^{(k)}(z_i)/k!$ である。したがって、差分商の表は導関数の値を入れるだけで同じように作れる。

重複点を許す Newton の形

$I$ を区間、$f\colon I\to\mathbb R$ を $C^{n+1}$ 級、$z_0\le\cdots\le z_n$ を $I$ の点とする。
$$ p(x):=\sum_{k=0}^nf[z_0,\dots,z_k]\prod_{j< k}(x-z_j) $$
とおくと、$a$ が $z_i$ の中に $m$ 回現れるとき $p^{(j)}(a)=f^{(j)}(a)$($j=0,\dots,m-1$)である。$p$ はこれらの条件を満たす次数 $n$ 以下のただ 1 つの多項式である。

要点:相異なる点で thm-nip-error を書き、点を近づけて極限をとると、重複点でも誤差の式が成り立つ。

詳しい証明を開く

$I$ の中の相異なる点の並びで $z_0,\dots,z_n$ に近づくものをとる。thm-nip-main により、それらの点の Newton の形は補間多項式で、thm-nip-error の式を満たす。prop-nip-hg の連続性により極限をとると、補間点と異なる $x$ について $f(x)-p(x)=f[z_0,\dots,z_n,x]\prod_j(x-z_j)$ である。$f$ は $C^{n+1}$ 級なので prop-nip-hg により $f[z_0,\dots,z_n,x]$ は $a$ の近くで有界である。よって定数 $C$ があって $a$ の近くで $\lvert f(x)-p(x)\rvert\le C\lvert x-a\rvert^m$ である。$f-p$ は $C^{n+1}$ 級で $m\le n+1$ なので、Taylorの定理 により $(f-p)^{(j)}(a)=0$($j< m$)となる($j< m$ の範囲で最初に $0$ でない導関数があれば、$x\to a$ で $\lvert f-p\rvert$ は $\lvert x-a\rvert^j$ の定数倍の大きさになり、不等式に反する)。一意性は Lagrange補間 の定理「Hermite 補間」による(標数 $0$ では、$(x-a)^m$ を法とする余りを指定することと $p(a),\dots,p^{(m-1)}(a)$ を指定することは同じである)。$\square$

等間隔の点

点が等間隔のとき、差分商は割り算を使わずに書ける。$x_i=x_0+ih$($h>0$)、$f_i:=f(x_i)$ とし、前進差分を $\Delta f_i:=f_{i+1}-f_i$、$\Delta^kf_i:=\Delta(\Delta^{k-1}f_i)$ で定める。実数 $s$ に対し $\binom sk:=\frac{s(s-1)\cdots(s-k+1)}{k!}$ とする。

Newton の前進差分公式

点が等間隔のとき、$f[x_i,\dots,x_{i+k}]=\dfrac{\Delta^kf_i}{k!\,h^k}$ であり、実数 $s$ に対して
$$ p_n(x_0+sh)=\sum_{k=0}^n\binom sk\Delta^kf_0 $$
である。

$k=0$ は定義である。$k-1$ で成り立つとすると、分母が $x_{i+k}-x_i=kh$ なので
$$ f[x_i,\dots,x_{i+k}]=\frac{1}{kh}\cdot\frac{\Delta^{k-1}f_{i+1}-\Delta^{k-1}f_i}{(k-1)!\,h^{k-1}}=\frac{\Delta^kf_i}{k!\,h^k} $$
である。また $N_k(x_0+sh)=\prod_{j< k}(s-j)h=k!\binom skh^k$ なので、def-nip-form に代入すれば後半を得る。$\square$

計算の手順

差分商は次の 差分商表 に並べて計算する。左の列から順に、隣り合う 2 つの差を、両端の点の差で割る。Newton の形の係数は、表の一番上の斜めの並びである。

$x_i$0 階1 階2 階3 階
$x_0$$f[x_0]$$f[x_0,x_1]$$f[x_0,x_1,x_2]$$f[x_0,x_1,x_2,x_3]$
$x_1$$f[x_1]$$f[x_1,x_2]$$f[x_1,x_2,x_3]$
$x_2$$f[x_2]$$f[x_2,x_3]$
$x_3$$f[x_3]$

配列 1 本で計算するには、値を $a_0,\dots,a_n$ に入れて、次のようにする。

  1. 入力:相異なる点 $x_0,\dots,x_n$ と値 $y_0,\dots,y_n$。$a_i\leftarrow y_i$ とする。
  2. 係数の計算:$k=1,\dots,n$ の順に、各 $k$ について $i=n,n-1,\dots,k$ の順(添字の大きい方から)に $a_i\leftarrow(a_i-a_{i-1})/(x_i-x_{i-k})$ とする。終わると $a_k=f[x_0,\dots,x_k]$ である(prop-nip-algorithm)。
  3. 値の計算:点 $x$ での値は、$b\leftarrow a_n$ から始めて、$k=n-1,\dots,0$ の順に $b\leftarrow b\,(x-x_k)+a_k$ とする。最後の $b$ が $p_n(x)$ である(多項式を入れ子にして計算する、組立除法と同じ形)。
  4. 点の追加:点 $x_{n+1}$ を足すときは、表の最後の行($d_k:=f[x_{n-k},\dots,x_n]$、$k=0,\dots,n$)を残しておき、$d'_0\leftarrow y_{n+1}$、$k=1,\dots,n+1$ の順に $d'_k\leftarrow(d'_{k-1}-d_{k-1})/(x_{n+1}-x_{n+1-k})$ とする。$a_{n+1}=d'_{n+1}$ である。
  5. 止める判定:許容誤差 $\varepsilon$ を決め、次の項の大きさ $\lvert a_{k+1}N_{k+1}(x)\rvert$ が $\varepsilon$ 以下になったら止める。次数の上限も決めておく。項が小さくならなくなったら点を足すのをやめる(等間隔の点で次数を上げると悪化することがある。ex-nip-counterexamples)。
手順の正しさ

手順 2 で $k$ の周回が終わった時点で、$i\ge k$ なら $a_i=f[x_{i-k},\dots,x_i]$、$i< k$ なら $a_i=f[x_0,\dots,x_i]$ である。手順 3 の結果は $p_n(x)$ である。除算の回数は手順 2 で $n(n+1)/2$ 回、手順 3 の掛け算は $n$ 回である。

$k$ についての帰納法による。$k=0$ は $a_i=f[x_i]$ である。$k$ の周回では、$i$ の大きい方から更新するので、$a_i$ の更新のときの $a_{i-1}$ はまだ $k-1$ の周回の値 $f[x_{i-k},\dots,x_{i-1}]$ である。よって更新後の値は
$$ \frac{f[x_{i-k+1},\dots,x_i]-f[x_{i-k},\dots,x_{i-1}]}{x_i-x_{i-k}}=f[x_{i-k},\dots,x_i] $$
である。$i< k$ の $a_i$ は更新されない。手順 3 は、$b_n:=a_n$、$b_k:=b_{k+1}(x-x_k)+a_k$ とすると $b_k=\sum_{j\ge k}a_j\prod_{k\le l< j}(x-x_l)$ となるので、$b_0=p_n(x)$ である。回数は $\sum_{k=1}^n(n-k+1)=n(n+1)/2$ による。$\square$

ほかの方法との費用の比較は次のとおりである。

方法前の計算1 点の値の計算点を 1 つ足す
Vandermonde 行列を解く$n^3$ の定数倍$n$ の定数倍解き直し
Lagrange の公式をそのままなし$n^2$ の定数倍基本多項式がすべて変わる
重心形(DB22 §9.2)$n^2$ の定数倍$n$ の定数倍重みの更新で $n$ の定数倍
Newton の形$n^2$ の定数倍$n$ の定数倍$n$ の定数倍

例題

平方根の値を点を足しながら求める

問い:$f(x)=\sqrt x$ の $x=100,121,144,169$ での値から $\sqrt{115}$ を求める。
使う公式:thm-nip-main、cor-nip-error。
答え:$p_3(x)=10+\frac{1}{21}(x-100)-\frac{1}{10626}(x-100)(x-121)+c_3(x-100)(x-121)(x-144)$、$c_3\approx3.13696\times10^{-7}$。$p_1(115)\approx10.714286$、$p_2(115)\approx10.722756$、$p_3(115)\approx10.723574$ で、真の値は $\sqrt{115}\approx10.723805$ である。

途中の計算を開く

1 階の差分商は $\frac{11-10}{21}=\frac1{21}$、$\frac1{23}$、$\frac1{25}$ である。2 階は $\frac{1/23-1/21}{144-100}=-\frac1{10626}\approx-9.41088\times10^{-5}$、$\frac{1/25-1/23}{169-121}=-\frac1{13800}\approx-7.24638\times10^{-5}$ である。3 階は $\frac{-1/13800+1/10626}{169-100}\approx3.13696\times10^{-7}$ である。$x=115$ では $x-100=15$、$x-121=-6$、$x-144=-29$ なので、各項は $10$、$\frac{15}{21}\approx0.714286$、$+\frac{90}{10626}\approx0.008470$、$c_3\cdot2610\approx0.000819$ である。

次の項と実際の誤差を比べると、$p_1$ では次の項 $0.00847$ に対して誤差 $0.00952$、$p_2$ では次の項 $0.00082$ に対して誤差 $0.00105$ で、次の項は誤差の目安になっている。$p_3$ の誤差は $0.00023$ で、$[100,169]$ で $\lvert f^{(4)}\rvert\le\frac{15}{16}100^{-7/2}=9.375\times10^{-8}$ なので cor-nip-error の上界 $\frac{9.375\times10^{-8}}{24}\cdot140940\approx0.00055$ の範囲にある。

等間隔でない点と、あとから足した点

問い:$(0,1)$、$(1,3)$、$(3,2)$、$(4,5)$ を通る 3 次以下の多項式 $p_3$ を求め、次に点 $(2,0)$ を足した $p_4$ を求める。
使う公式:thm-nip-main、計算の手順の段 4。
答え:$p_3(x)=1+2x-\frac56x(x-1)+\frac12x(x-1)(x-3)=\frac12x^3-\frac{17}6x^2+\frac{13}3x+1$。$p_4(x)=p_3(x)-\frac7{12}x(x-1)(x-3)(x-4)$。$x=\frac52$ では $p_3=1.9375$、$p_4=0.296875$ である。

途中の計算を開く

差分商表の 1 階は $2,-\frac12,3$、2 階は $-\frac56,\frac76$、3 階は $\frac12$ である。最後の行は $d_0=5$、$d_1=3$、$d_2=\frac76$、$d_3=\frac12$ である。点 $x_4=2$、$y_4=0$ を足すと $d'_0=0$、$d'_1=\frac{0-5}{2-4}=\frac52$、$d'_2=\frac{5/2-3}{2-3}=\frac12$、$d'_3=\frac{1/2-7/6}{2-1}=-\frac23$、$d'_4=\frac{-2/3-1/2}{2-0}=-\frac7{12}$ となる。前の係数 $1,2,-\frac56,\frac12$ はそのまま使える。

同じ 4 点を $x=4,1,3,0$ の順に並べると、係数は $5,\frac23,\frac76,\frac12$ となる。最高階の係数 $\frac12$ は同じで、途中の係数は変わるが、できる多項式は同じである。

等間隔の表から $\sin 0.15$ を求める

問い:$\sin x$ の $x=0,0.2,0.4,0.6,0.8$ での値から $\sin0.15$ を求める。
使う公式:prop-nip-forward($h=0.2$、$s=0.75$)。
答え:$p_4(0.15)\approx0.149434$。真の値は $\sin0.15\approx0.149438$ である。

途中の計算を開く

値は $0$、$0.198669$、$0.389418$、$0.564642$、$0.717356$ である。$\Delta f_0\approx0.198669$、$\Delta^2f_0\approx-0.007920$、$\Delta^3f_0\approx-0.007605$、$\Delta^4f_0\approx0.000619$ である。$\binom{0.75}1=0.75$、$\binom{0.75}2=-0.09375$、$\binom{0.75}3\approx0.039063$、$\binom{0.75}4\approx-0.021973$ なので、和は $0+0.149002+0.000743-0.000297-0.000014\approx0.149434$ である。

両端で値と傾きを指定する

問い:$p(0)=0$、$p'(0)=1$、$p(1)=1$、$p'(1)=0$ を満たす 3 次以下の多項式を、点の並び $0,0,1,1$ の Newton の形で求める。
使う公式:prop-nip-hg、prop-nip-confluent。
答え:$p(x)=x-x^2(x-1)=-x^3+x^2+x$、$p\bigl(\frac12\bigr)=\frac58=0.625$。Lagrange補間 の例「両端で値と傾きを指定する 3 次式」と同じ多項式である。

途中の計算を開く

1 階の列は、重なる点では導関数の値を入れて $f[0,0]=1$、$f[0,1]=\frac{1-0}{1-0}=1$、$f[1,1]=0$ である。2 階は $f[0,0,1]=\frac{1-1}{1-0}=0$、$f[0,1,1]=\frac{0-1}{1-0}=-1$、3 階は $f[0,0,1,1]=\frac{-1-0}{1-0}=-1$ である。係数は $0,1,0,-1$ で、基底は $1,\ x,\ x^2,\ x^2(x-1)$ である。

誤差の上界と実際の誤差

問い:$f(x)=e^x$ を $x=0,\frac12,1$ で 2 次補間し、$x=\frac14$ の誤差と $[0,1]$ の最大誤差を評価する。
使う公式:cor-nip-error。
答え:$p_2(x)\approx1+1.297443x+0.841679x\bigl(x-\frac12\bigr)$。$p_2\bigl(\frac14\bigr)\approx1.271756$ で、誤差は $e^{1/4}-p_2\bigl(\frac14\bigr)\approx0.012270$ である。cor-nip-error からは $0.007813\le$ 誤差 $\le0.021237$ が分かる。$[0,1]$ 全体の上界は $0.021797$ で、実際の最大誤差は約 $0.014421$ である。

途中の計算を開く

$N_3(\frac14)=\frac14\cdot(-\frac14)\cdot(-\frac34)=\frac3{64}=0.046875$ である。$\xi\in[0,1]$ で $1\le e^\xi\le e$ なので、誤差は $\frac{N_3(1/4)}6$ の $1$ 倍以上 $e$ 倍以下で、下限は $0.0078125$、上限は $0.021237$ である。実際の誤差から逆算すると $\xi\approx0.4514$ である。$\lvert N_3\rvert$ の $[0,1]$ での最大値は、$N_3(x)=(x-\frac12)^3-\frac14(x-\frac12)$ より $\frac1{12\sqrt3}\approx0.048113$ なので、上界は $\frac e6\cdot\frac1{12\sqrt3}\approx0.021797$ である。

平方和の公式を差分の表から作る

問い:$S(n)=\sum_{k=0}^nk^2$ の閉じた形を、$S(0),\dots,S(3)=0,1,5,14$ から求める。
使う公式:prop-nip-forward($h=1$、$s=n$)。
答え:$S(n)=\binom n1+3\binom n2+2\binom n3=\dfrac{n(n+1)(2n+1)}6$、$S(10)=385$。

途中の計算を開く

$\Delta S_0=1$、$\Delta^2S_0=3$、$\Delta^3S_0=2$ である。右辺を $q(n)$ とおくと、展開して $q(n+1)-q(n)=(n+1)^2$ と $q(0)=0$ が確かめられるので、すべての $n$ で $S(n)=q(n)$ である。4 点で決めた多項式が正しいことは、この確認で分かる(数列の和と差分 の差分作用素も参照)。

使える条件と反例

外す条件反例成り立たなくなること
点が相異なる点 $0,0$ に値 $0,1$差分商の分母が $0$ で、補間多項式もない
$f$ の $n$ 回微分可能性$f(x)=\lvert x\rvert$、点 $-1,0,1$thm-nip-mean:$f[-1,0,1]=1$ だが、$f''$ は $0$ 以外の点でつねに $0$
$x$ が上界を測った区間の中にある$\sqrt x$、点 $100,121,144,169$、$x=1$区間 $[100,169]$ の $\lvert f^{(4)}\rvert$ で作った値 $1.115$ を、誤差 $2.635$ が超える
導関数の大きさの制御$1/(1+25x^2)$、$[-1,1]$ の等間隔の点点を増やしても誤差が減らない($n=5,10,20$ で $0.43,1.9,60$)
等間隔prop-nip-forward を点 $0,1,3$ の $x^2$ に使う$x=3$ の値が $9$ でなく $24$ になる
計算の桁が十分ある$e^x$、Chebyshev 点 $81$ 個を昇順に使う(倍精度)多項式は同じはずだが、最大誤差が $10^4$ を超える
反例の確認

$\lvert x\rvert$:$f[-1,0]=-1$、$f[0,1]=1$ なので $f[-1,0,1]=\frac{1-(-1)}{2}=1$ である。$f$ は $0$ で微分できないので Rolleの定理 が使えず、$f''(\xi)/2=1$ となる $\xi$ はない。
外挿:3 次の $p_3$ は $p_3(1)\approx3.63478$ で、$\sqrt1=1$ との差は $2.63478$ である。$N_4(1)=99\cdot120\cdot143\cdot168$ に、ex-nip-sqrt の $[100,169]$ での $M=9.375\times10^{-8}$ を掛けて $24$ で割ると $1.11486$ である。cor-nip-error の $\xi$ は $x$ を含む区間 $[1,169]$ を動くので、$[100,169]$ の $M$ は使えない。
Runge の現象:等間隔の $n+1$ 点での最大誤差は $n=5,10,20$ で $0.4327$、$1.916$、$59.82$ である。同じ次数で点を $\cos\frac{(2i+1)\pi}{2(n+1)}$($i=0,\dots,n$)にとると、$0.5559$、$0.1092$、$0.0153$ である(数値計算による値。Lagrange補間 の節「実数の上の補間と誤差」と同じ現象である。誤差の発散の証明は 補間 の定理「Runge の現象」、発散する範囲は Runge現象)。cor-nip-error は誤差の式であって、点を増やすと誤差が減ることを保証しない。

残りの 2 行の確認を開く

等間隔の公式の誤用:点 $0,1,3$ の値 $0,1,9$ の差は $1,8$、$7$ である。これを $p(x)=x+7\binom x2$ に入れると $p(3)=24$ になる。正しくは差分商 $1,4,1$ を使って $x+x(x-1)=x^2$ である。

点の順序と丸め:$e^x$ を $[-1,1]$ の Chebyshev 点で、倍精度の浮動小数点数で補間する。手順 2・3 で点を昇順に並べると、最大誤差は点 $21$ 個・$41$ 個では $10^{-15}$ 程度だが、$61$ 個で $10^{-4}$ 程度、$81$ 個で $10^4$ を超える。同じ点を、これまでの点との距離の積が最大のものから順に選ぶと、$81$ 個でも $10^{-15}$ 程度である(数値計算による値。丸め誤差の大きさなので、桁の目安として読む)。多項式としては同じなので、この差は丸め誤差による。

よくある誤り

誤り正しくはなぜ
2 階以上の差分商を、隣の点の差 $x_{i+k}-x_{i+k-1}$ で割る両端の差 $x_{i+k}-x_i$ で割るdef-nip-dd
等間隔のとき $\Delta^kf_0$ をそのまま係数にする$x^k$ の基底では $\Delta^kf_0/(k!\,h^k)$、$\binom sk$ の基底なら $\Delta^kf_0$prop-nip-forward
配列 1 本の計算で $i$ を小さい方から更新する大きい方から更新する。小さい方からだと $a_{i-1}$ が書き換わった後の値になるprop-nip-algorithm
点の順を変えると、できる多項式も変わると思う係数の並びは変わるが、多項式は同じ。最高階の差分商も同じprop-nip-basic
次数を上げれば必ず精度が上がると思う等間隔の点では悪化することがあるex-nip-counterexamples
点の範囲の外(外挿)で区間の中と同じ精度を期待する$\lvert N_{n+1}(x)\rvert$ が急に大きくなるcor-nip-error

演習

積の差分商

相異なる点 $x_0,\dots,x_n$ について $(fg)[x_0,\dots,x_n]=\sum_{k=0}^nf[x_0,\dots,x_k]\,g[x_k,\dots,x_n]$ を示せ。

解答を開く

$P:=\sum_kf[x_0,\dots,x_k]N_k$ は $f$ の、点の順を逆にした $Q:=\sum_jg[x_j,\dots,x_n]\prod_{i>j}(x-x_i)$ は $g$ の補間多項式である(thm-nip-main と prop-nip-basic の対称性)。積 $PQ$ の項のうち $k>j$ のものは $N_k\prod_{i>j}(x-x_i)$ を因子にもち、すべての補間点で $0$ である。残りの項の和 $R:=\sum_{k\le j}$ は補間点で $fg$ と同じ値をとり、次数は $k+n-j\le n$ である。よって $R$ は $fg$ の補間多項式で、その $x^n$ の係数は $k=j$ の項の和である。$\square$

差分の表で入力の誤りを見つける

$x^3$ の値 $0,1,8,27,64,125,216,343$ のうち $64$ を $74$ と書き誤った。3 階の差分の列を作り、誤りの位置と大きさが分かることを説明せよ。

解答を開く

正しい値なら 3 階の差分はすべて $6$ である(prop-nip-basic の 4 と prop-nip-forward)。誤った表では $6,16,-24,36,-4$ となる。線形性より、値に $\varepsilon$ の誤りがあると 3 階の差分には二項係数の符号つきの並び $\varepsilon,-3\varepsilon,3\varepsilon,-\varepsilon$ が加わる。$6$ を引くと $0,10,-30,30,-10$ なので $\varepsilon=10$ で、並びの始まりから 5 番目の値($x=4$)が誤りと分かる。

2 階の差分商と中心差分

$f[a-h,a,a+h]$ を $f(a-h),f(a),f(a+h)$ で書き、$f\in C^4$ なら $2f[a-h,a,a+h]=f''(a)+O(h^2)$ であることを示せ。

解答を開く

定義から $f[a-h,a,a+h]=\dfrac{f(a+h)-2f(a)+f(a-h)}{2h^2}$ である。Taylorの定理 で $f(a\pm h)=f(a)\pm hf'(a)+\frac{h^2}2f''(a)\pm\frac{h^3}6f'''(a)+O(h^4)$ を足すと分子は $h^2f''(a)+O(h^4)$ になるので、$2f[a-h,a,a+h]=f''(a)+O(h^2)$ である。$f=\sin$、$a=1$、$h=0.1$ では $-0.840770$ で、$f''(1)\approx-0.841471$ に近い。$\square$

補足

  • 値を直接計算する方法:thm-nip-main の証明の $P(x)$ を、係数でなく点 $x$ での値のまま繰り返し使うと、1 つの点での補間の値を差分商なしに計算できる(Neville の算法)。
  • 体の上の補間:thm-nip-main の証明は、補間多項式がただ 1 つ存在することしか使わないので、実数を任意の体に替えても成り立つ。Lagrange補間 の節「3 つの基底の比較」は、Newton の基底で評価写像の行列が下三角になることを述べている。
  • 複素の点:$f$ が単連結領域で正則なら、差分商は留数の和で $\frac1{2\pi i}\oint_Cf(\zeta)/N_{n+1}(\zeta)\,d\zeta$ と書ける($C$ は領域の中で点 $x_0,\dots,x_n$ を囲み、正の向きに 1 周する単純閉曲線である。DLMF 式 (3.3.37)。この記事では証明しない)。
  • 区分的な補間:次数を上げる代わりに区間を分けて低い次数の多項式をつなぐ方法が スプライン補間 である。ex-nip-counterexamples の Runge の現象を避ける標準の道具である。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する