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)!$ を用いた式になる。関数の表の補間、数値積分や数値微分の公式の導出に使う。
前提知識: 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}
$$
である。
相異なる点 $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 補間 という。
この公式を使う条件は次のとおりである。
| 公式 | 使える条件 | 根拠 |
|---|---|---|
| $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 の形の係数であることを述べる。証明の要点は、補間多項式の最高次の係数に注目することである。
$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 の $c(y_0,\dots,y_k)$ は点の並べ方によらずに定まる量なので、次の性質がすぐに従う。
$x_0,\dots,x_n$ を相異なる点とする。
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 点に集まる極限で差分商が導関数に近づくことを示唆している。これを正確に述べるのが次の積分表示である。
$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!$ である。したがって、差分商の表は導関数の値を入れるだけで同じように作れる。
$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!}$ とする。
点が等間隔のとき、$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$ に入れて、次のようにする。
手順 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 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 は誤差の式であって、点を増やすと誤差が減ることを保証しない。
等間隔の公式の誤用:点 $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$)が誤りと分かる。
$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$
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する