補間

同義語:補間法内挿内挿法interpolation

概要

補間(interpolation)とは、いくつかの点で与えられた値を正確に通る関数を、多項式やスプラインなどの関数の族の中から求めることである。関数の表の間の値の計算、数値積分や数値微分の公式の導出に使う。折れ線、多項式、3 次スプライン、三角多項式などの方法があり、データの点の配置となめらかさで選ぶ。等間隔の点で次数を上げると誤差が発散することがあり(Runge の現象)、Chebyshev 点を使うか、区分的な低い次数の関数を使うとこれを避けられる。

$$\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補間, Chebyshev多項式, Taylorの定理

実験や数表から、いくつかの点での値だけが分かっている関数がある。点の間の値を知りたいとき、与えられた点を通る計算しやすい関数を作って代わりに使う。これが 補間 である。
方法はいくつもある。点を結ぶ折れ線、すべての点を通る 1 つの多項式、区間ごとの 3 次式をなめらかにつないだスプライン、周期関数のための三角多項式である。どれを選ぶかで結果は大きく変わる。$f(x)=1/(1+25x^2)$ を $[-1,1]$ の等間隔の $21$ 点で 20 次式で補間すると、最大誤差は約 $60$ になる。同じ 20 次式でも点の位置を変えると最大誤差は約 $0.015$ で、同じ 21 点の 3 次スプラインなら約 $0.0032$ である(ex-itp-runge)。
この記事は補間の入口として、問題の定式化、方法の比較、点の選び方、Runge現象 が起こる理由を扱う。個々の方法の公式と証明は Lagrange補間・Newton補間・スプライン補間 にあり、見出しで引く。なお、ノルム空間の間の作用素を補間する話題は 補間理論、論理学の話題は Craigの補間定理 で、この記事とは別の主題である。

定義と使える条件

補間問題

相異なる点 $x_0,\dots,x_n$(節点)と値 $y_0,\dots,y_n$、関数の集合 $V$ を与える。$u\in V$ で
$$ u(x_i)=y_i\qquad(i=0,\dots,n) $$
を満たすものを求める問題を 補間問題、$u$ を 補間関数 という。$y_i=f(x_i)$ のとき、$u$ を $f$ の補間関数という。節点の範囲の外で $u$ の値を使うことを 外挿 という。

補間は点を 正確に通る 関数を求める。点の近くを通る関数を求める 最小二乗法 とは問題が違う。
$V$ が有限次元のベクトル空間で基底 $\varphi_0,\dots,\varphi_n$ をもつとき、$u=\sum_jc_j\varphi_j$ とおくと、補間問題は連立 1 次方程式になる。

解の存在と一意性

$\dim V=n+1$ とし、$B:=(\varphi_j(x_i))_{i,j}$ とする。次の 3 つは同値である。

  1. どの値 $y_0,\dots,y_n$ に対しても、補間関数がただ 1 つある。
  2. $B$ は正則である。
  3. $u\in V$ がすべての節点で $0$ なら $u=0$ である。

補間問題は $Bc=y$ と同値である。1 はこの方程式がどの $y$ についてもただ 1 つの解をもつことなので、2 と同値である。3 は $Bc=0$ なら $c=0$ ということで、$B$ は正方行列なので 2 と同値である。$\square$

$V$ が次数 $n$ 以下の多項式の全体なら 3 が成り立つ(0 でない多項式の根は次数以下の個数)。これが Lagrange補間 の定理「Lagrange 補間」の内容で、$B$ は Vandermonde 行列である。

補間の Lebesgue 定数

prop-itp-unique の条件が成り立つとき、$\ell_k(x_i)=\delta_{ik}$ を満たす $\ell_k\in V$ を 基本関数 といい、補間関数は $u=\sum_ky_k\ell_k$ である。区間 $[a,b]$ が節点を含み $V\subset C([a,b])$ のとき、
$$ \Lambda:=\max_{a\le x\le b}\sum_{k=0}^n\lvert\ell_k(x)\rvert $$
を Lebesgue 定数 という(Fourier 級数の部分和などほかの近似の方法を含む一般の形は Lebesgue定数)。

$\max_i\lvert y_i\rvert\le\varepsilon$ なら $\max_{[a,b]}\lvert u\rvert\le\Lambda\varepsilon$ である。$\sum_k\lvert\ell_k\rvert$ が最大になる点を $\bar x$ とし、$y_k=\varepsilon\,\mathrm{sign}\,\ell_k(\bar x)$ とすると等号が成り立つ。つまり $\Lambda$ は データの誤差が補間で何倍に増えるか を表す。多項式の補間では、最良近似との差も同じ量で測れる(近似理論 の定理「Lebesgue の不等式」)。
補間を使う条件は次のとおりである。

  • (i) 節点は相異なる(導関数も与えるときは、Lagrange補間 の定理「Hermite 補間」の形にする)。
  • (ii) 関数の集合 $V$ は prop-itp-unique の条件を満たす。
  • (iii) データの誤差は小さい。誤差が大きいデータには最小二乗の当てはめを使う。
  • (iv) 値を求める点は節点の範囲の中にある。外挿では誤差の評価が急に悪くなる。

公式の表

方法関数の集合公式の要点誤差($f$ がなめらかなとき)根拠
折れ線区間ごとの 1 次式隣の 2 点を結ぶ$\frac18h^2\max\lvert f''\rvert$ 以下Lagrange補間
多項式(Lagrange の形)次数 $n$ 以下$\sum_ky_k\prod_{j\ne k}\frac{x-x_j}{x_k-x_j}$$\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_i(x-x_i)$Lagrange補間
多項式(重心形)次数 $n$ 以下$\dfrac{\sum_kw_ky_k/(x-x_k)}{\sum_kw_k/(x-x_k)}$同上prop-itp-bary
多項式(Newton の形)次数 $n$ 以下$\sum_kf[x_0,\dots,x_k]\prod_{j< k}(x-x_j)$同上Newton補間
Hermite 補間次数 $2n+1$ 以下値と 1 階導関数を合わせる—Newton補間
3 次スプライン区間ごとの 3 次式で $C^2$ 級三重対角の方程式$\frac7{64}h^4\max\lvert f''''\rvert$ 以下(完全スプライン)スプライン補間
三角補間次数 $m$ 以下の三角多項式$c_k=\frac1N\sum_jy_je^{-\mathrm{i}kx_j}$$2\sum_{\lvert k\rvert>m}\lvert\hat f_k\rvert$ 以下prop-itp-trig

ここで $h$ は隣り合う節点の間隔の最大値である。
計算の手間は次のとおりである。

方法前の計算1 点の値点を足す1 つの値を変える
折れ線なし点の探索のみ局所的局所的
多項式(Lagrange の形)なし$n^2$ の定数倍計算し直し全体が変わる
多項式(重心形)$n^2$ の定数倍$n$ の定数倍重みの更新全体が変わる
多項式(Newton の形)$n^2$ の定数倍$n$ の定数倍$n$ の定数倍全体が変わる
3 次スプライン$n$ の定数倍点の探索と定数回解き直し全体が変わるが、影響は速く減る
三角補間FFT で $N\log N$ の定数倍$N$ の定数倍解き直し全体が変わる

主定理と証明

節点の選び方

多項式の補間の誤差は、$f$ で決まる部分 $f^{(n+1)}(\xi)/(n+1)!$ と、節点で決まる部分 $\Phi(x):=\prod_{i=0}^n(x-x_i)$ の積である。$\Phi$ の最大値を小さくする節点が最もよい。

Chebyshev 点は節点の多項式を最小にする

$n\ge0$ とする。

  1. $[-1,1]$ のどの $n+1$ 個の節点についても $\max_{[-1,1]}\lvert\Phi\rvert\ge2^{-n}$ である。$T_{n+1}$ の根
    $$ x_i=\cos\frac{(2i+1)\pi}{2n+2}\qquad(i=0,\dots,n) $$
    (Chebyshev 点)をとると $\Phi=2^{-n}T_{n+1}$ で、等号が成り立つ。
  2. $f\colon[a,b]\to\mathbb R$ が $n+1$ 回微分可能で $\lvert f^{(n+1)}\rvert\le M$ なら、Chebyshev 点を $x\mapsto\frac{a+b}2+\frac{b-a}2x$ で移した節点の補間多項式 $p$ は
    $$ \max_{[a,b]}\lvert f-p\rvert\le\frac{2M}{(n+1)!}\Bigl(\frac{b-a}4\Bigr)^{n+1} $$
    を満たす。

1。 $\Phi$ は最高次の係数が $1$ の $n+1$ 次の実数係数多項式なので、Chebyshev多項式 の定理「Chebyshev の最小最大定理」から不等式が従う。$T_{n+1}(\cos\theta)=\cos(n+1)\theta$ より、挙げた $n+1$ 個の点は相異なる根である。$T_{n+1}$ の最高次の係数は $2^n$ なので、$\Phi=2^{-n}T_{n+1}$ である。$[-1,1]$ で $\lvert T_{n+1}\rvert\le1$ で、$x=1$ で値 $1$ をとる。
2。 $t\in[-1,1]$ と $x=\frac{a+b}2+\frac{b-a}2t$ が対応し、節点も同じ対応なので、$x-x_i=\frac{b-a}2(t-t_i)$ である。よって $\max_{[a,b]}\lvert\Phi\rvert=\bigl(\frac{b-a}2\bigr)^{n+1}2^{-n}=2\bigl(\frac{b-a}4\bigr)^{n+1}$ である。Lagrange補間 の定理「補間の誤差」に入れると結論を得る。$\square$

重心形

Lagrange の公式は、点ごとの計算が $n^2$ の定数倍かかる。少し書き換えると、$n$ の定数倍で計算できる形になる。

重心形の公式

相異なる節点について $w_k:=1\big/\prod_{j\ne k}(x_k-x_j)$ を 重み とする。節点でない $x$ で、値 $y_k$ の補間多項式 $p$ は
$$ p(x)=\Phi(x)\sum_{k=0}^n\frac{w_ky_k}{x-x_k}=\frac{\displaystyle\sum_{k=0}^n\frac{w_ky_k}{x-x_k}}{\displaystyle\sum_{k=0}^n\frac{w_k}{x-x_k}} $$
を満たす。

$\prod_{j\ne k}(x-x_j)=\Phi(x)/(x-x_k)$ なので、Lagrange の基本多項式は $\ell_k(x)=\Phi(x)w_k/(x-x_k)$ である。これで 1 つ目の等号を得る。値がすべて $1$ の補間多項式は定数 $1$ なので、$1=\Phi(x)\sum_kw_k/(x-x_k)$ である。1 つ目の式をこれで割ると 2 つ目の等号を得る。$\square$

2 つ目の式の重みは定数倍してよい。式は DB22 Theorem 9.2.1 にある。第 2 種の Chebyshev 点 $-\cos(k\pi/n)$ では、重みは $(-1)^kd_k$($d_0=d_n=\frac12$、ほかは $d_k=1$)の定数倍である(DB22 式 (9.3.3))。

Runge の現象

等間隔の節点で次数を上げると誤差が増えることは、$f(x)=1/(1+25x^2)$ では厳密な式で確かめられる。この関数は分母が $x^2$ の 1 次式なので、誤差が閉じた形になる。起こる理由と起こる範囲の全体は Runge現象 にある。

Runge の関数の誤差の式

$f(x)=1/(1+25x^2)$、$n=2m$($m\ge1$)とし、節点は $0$ と $\pm x_j$($0< x_1<\cdots< x_m$)とする。補間多項式 $p$ について、すべての実数 $x$ で
$$ f(x)-p(x)=(-1)^{m+1}\,\frac{25x^2}{1+25x^2}\prod_{j=1}^m\frac{x^2-x_j^2}{x_j^2+\frac1{25}} $$
である。

$R(u):=u\prod_{j=1}^m(u-x_j^2)$ とおき、$c:=R(-\frac1{25})=(-1)^{m+1}\frac1{25}\prod_j\bigl(x_j^2+\frac1{25}\bigr)\ne0$ とする。多項式 $1-R(u)/c$ は $u=-\frac1{25}$ で $0$ になるので、$1+25u$ で割り切れる。商を $q(u)$ とすると $\deg q=m$ である。
$P(x):=q(x^2)$ は次数 $2m$ の多項式である。節点では $R(x_i^2)=0$ なので、$P(x_i)=1/(1+25x_i^2)=f(x_i)$ である。補間多項式はただ 1 つなので $p=P$ である。よって
$$ f(x)-p(x)=\frac{1-\bigl(1-R(x^2)/c\bigr)}{1+25x^2}=\frac{R(x^2)}{c\,(1+25x^2)} $$
で、$R(x^2)=x^2\prod_j(x^2-x_j^2)$ と $c$ の値を入れると結論を得る。$\square$

$\Phi(x)=x\prod_j(x^2-x_j^2)$、$D:=\prod_j(x_j^2+\frac1{25})$ とおくと、誤差の大きさは
$$ \lvert f(x)-p(x)\rvert=\frac{25\lvert x\rvert}{1+25x^2}\cdot\frac{\lvert\Phi(x)\rvert}{D} $$
である。つまり、実軸の上の $\lvert\Phi\rvert$ と、$f$ の極 $\pm\mathrm{i}/5$ での $\lvert\Phi\rvert=D/5$ の比 が誤差を決める。等間隔の節点では、この比が区間の端の近くで指数的に大きくなる。
次の補題は等間隔の節点の計算に使う。

半整数の積

$n\ge1$ なら $\displaystyle\prod_{k=0}^n\Bigl\lvert k-\frac12\Bigr\rvert\ge\frac{n!}{4\sqrt n}$ である。

左辺は $\frac{n!}{2}\cdot4^{-n}\binom{2n}n$ に等しく、$4^{-n}\binom{2n}n\ge\frac1{2\sqrt n}$ である。

計算を開く

左辺は $\frac12\cdot\frac12\cdot\frac32\cdots\frac{2n-1}2=\frac12\cdot\frac{(2n)!}{4^nn!}=\frac{n!}{2}\cdot4^{-n}\binom{2n}n$ である。$a_n:=4^{-n}\binom{2n}n\sqrt n$ とおくと $a_1=\frac12$ で、

$\frac{a_{n+1}}{a_n}=\frac{2n+1}{2n+2}\sqrt{\frac{n+1}n}=\frac{n+\frac12}{\sqrt{n(n+1)}}\ge1$ である($(n+\frac12)^2\ge n(n+1)$ による)。よって $4^{-n}\binom{2n}n\ge\frac1{2\sqrt n}$ である。$\square$

Runge の現象

$f(x)=1/(1+25x^2)$、$n=2m$($m\ge1$)とし、$p_n$ を $[-1,1]$ の $n+1$ 個の節点の補間多項式とする。

  1. 節点が等間隔 $-1+2i/n$ のとき、$\bar x:=1-\frac1n$ で
    $$ \lvert f(\bar x)-p_n(\bar x)\rvert\ge\frac{25}{1352}\,n^{-3/2}e^{\kappa n},\qquad\kappa:=\log2-\frac12\log1.04-\frac15\arctan5\approx0.39886 $$
    である。とくに $n\to\infty$ で $\max_{[-1,1]}\lvert f-p_n\rvert\to\infty$ である。
  2. 節点が Chebyshev 点のとき、$\rho:=\frac{1+\sqrt{26}}5\approx1.21980$ について
    $$ \max_{[-1,1]}\lvert f-p_n\rvert\le\frac1{\rho^{n+1}-\rho^{-n-1}} $$
    である。とくに誤差は指数的に $0$ に近づく。

1。 節点の間隔は $h=\frac2n=\frac1m$ で、$\bar x$ は最後の区間の中点、正の節点は $x_j=j/m$ である。thm-itp-runge-formula のあとの式の 3 つの因子を評価すると、$\frac{25\bar x}{1+25\bar x^2}\ge\frac{25}{26}$、$\lvert\Phi(\bar x)\rvert\ge\frac{(2/e)^n}{2n^{3/2}}$、$\frac1D\ge\frac1{26}e^{-nI/2}$($I:=\log1.04-2+\frac25\arctan5$)である。

3 つの評価を開く

第 1 の因子:$t\mapsto25t/(1+25t^2)$ は $t>\frac15$ で減少で、$\frac12\le\bar x\le1$ なので、値は $\frac{25}{26}$ 以上である。

第 2 の因子:$\bar x-x_i$ の絶対値は $h\lvert n-\frac12-i\rvert$ の形なので、$i$ を $n-i$ に並べ替えて lem-itp-product を使うと $\lvert\Phi(\bar x)\rvert=h^{n+1}\prod_{k=0}^n\lvert k-\frac12\rvert\ge(\frac2n)^{n+1}\frac{n!}{4\sqrt n}\ge\frac{(2/e)^n}{2n^{3/2}}$ である。最後に $n!\ge(n/e)^n$ を使った。

第 3 の因子:$G(t):=\log(t^2+\frac1{25})$ は $[0,1]$ で増加なので、$1\le j\le m-1$ について $\frac1mG(\frac jm)\le\int_{j/m}^{(j+1)/m}G$、$\int_0^{1/m}G\ge\frac1mG(0)$ である。これらを足して $\log D=\sum_{j=1}^mG(\frac jm)\le m\int_0^1G+G(1)-G(0)=\frac n2I+\log26$($I:=\int_0^1G=\log1.04-2+\frac25\arctan5$)を得る。よって $1/D\ge\frac1{26}e^{-nI/2}$ である。


3 つを掛けると、下界は $\frac{25}{26}\cdot\frac1{2\cdot26}n^{-3/2}\exp\bigl(n(\log2-1-\frac I2)\bigr)$ で、$\log2-1-\frac I2=\kappa$ である。
2。 $n$ は偶数なので、Chebyshev 点は $0$ を含み、原点について対称である。よって thm-itp-runge-formula が使える。thm-itp-chebyshev より $\Phi=2^{-n}T_{n+1}$ である。$\lvert\Phi(\mathrm{i}/5)\rvert=D/5$ と $\frac{5\lvert x\rvert}{1+25x^2}\le\frac12$ から
$$ \lvert f(x)-p_n(x)\rvert=\frac{5\lvert x\rvert}{1+25x^2}\cdot\frac{\lvert\Phi(x)\rvert}{\lvert\Phi(\mathrm{i}/5)\rvert}\le\frac12\cdot\frac{\lvert T_{n+1}(x)\rvert}{\lvert T_{n+1}(\mathrm{i}/5)\rvert}\le\frac1{2\lvert T_{n+1}(\mathrm{i}/5)\rvert} $$
である。$N:=n+1$ とする。$T_N\bigl(\frac12(w+w^{-1})\bigr)=\frac12(w^N+w^{-N})$ は $\lvert w\rvert=1$ で成り立つので($w=e^{\mathrm{i}\theta}$)、両辺を $w$ の Laurent 多項式と見て、$w\ne0$ のすべての複素数で成り立つ。$\rho-\rho^{-1}=\frac25$ なので、$w=\mathrm{i}\rho$ とすると $\frac12(w+w^{-1})=\mathrm{i}/5$ である。$N$ は奇数なので $w^{-N}=-\mathrm{i}^N\rho^{-N}$ で、$\lvert T_N(\mathrm{i}/5)\rvert=\frac12(\rho^N-\rho^{-N})$ である。$\square$

1 の下界は証明のための粗い値で、実際の誤差はもっと大きい(ex-itp-runge)。2 の上界はほぼ正確である。楕円の内部で正則な関数についての評価は Runge現象 の定理「Chebyshev 点の誤差」にある。
図: 左は n=10 の 3 つの補間。右は n と最大誤差の片対数グラフ。等間隔の多項式は増え、Chebyshev 点の多項式と自然スプラインは減る 図: 左は n=10 の 3 つの補間。右は n と最大誤差の片対数グラフ。等間隔の多項式は増え、Chebyshev 点の多項式と自然スプラインは減る

等間隔の節点の Lebesgue 定数

Runge の関数だけが特別なのではない。データの誤差の増え方も、等間隔の節点では指数的である。

等間隔の節点の Lebesgue 定数の下界

$n\ge1$ とし、区間 $[a,b]$ の両端を含む等間隔の $n+1$ 点での多項式の補間の Lebesgue 定数を $\Lambda_n$ とする。このとき
$$ \Lambda_n\ge\frac{2^n}{4n^{3/2}} $$
である。

$\ell_k$ は節点の 1 次式の変数変換で変わらないので、節点を $0,1,\dots,n$、区間を $[0,n]$ としてよい。$x=\frac12$ で $\lvert\ell_j(\frac12)\rvert\ge\binom nj\big/(4n^{3/2})$ であり、$j$ について足すと $2^n/(4n^{3/2})$ を得る。

評価を開く

$\lvert\ell_j(\frac12)\rvert=\frac{\prod_{i\ne j}\lvert\frac12-i\rvert}{\prod_{i\ne j}\lvert j-i\rvert}=\frac1{\lvert j-\frac12\rvert\,j!\,(n-j)!}\prod_{i=0}^n\lvert i-\frac12\rvert$ である。$\lvert j-\frac12\rvert\le n$ と lem-itp-product より、これは $\frac1{n\,j!\,(n-j)!}\cdot\frac{n!}{4\sqrt n}=\binom nj\big/(4n^{3/2})$ 以上である。$\square$

一方、Chebyshev 点では、連続関数 $f$ の補間の誤差が最良一様近似の誤差の $\frac2\pi\log(n+1)+2$ 倍以下である(近似理論 の節「代表例 2:補間と最良近似を比べる Lebesgue の不等式」、VKG14 式 (6.21)、p. 528。この記事では証明しない)。

三角補間

周期関数には三角多項式を使う。$N=2m+1$ を奇数とし、$x_j:=2\pi j/N$($j=0,\dots,N-1$)を節点、$V$ を $e^{\mathrm{i}kx}$($\lvert k\rvert\le m$)で張られる空間とする。実数値のデータでは、補間関数は $1,\cos kx,\sin kx$ の実数係数の和である(prop-itp-trig の $c_k$ は $c_{-k}=\overline{c_k}$ を満たす)。

三角補間の公式と誤差
  1. どの値 $y_j$ についても、$V$ の補間関数はただ 1 つで、$t(x)=\sum_{\lvert k\rvert\le m}c_ke^{\mathrm{i}kx}$、$c_k=\frac1N\sum_{j=0}^{N-1}y_je^{-\mathrm{i}kx_j}$ である。
  2. $f(x)=\sum_{k\in\mathbb Z}\hat f_ke^{\mathrm{i}kx}$、$\sum_k\lvert\hat f_k\rvert<\infty$ なら、$y_j=f(x_j)$ の補間関数 $t$ について $\lvert f(x)-t(x)\rvert\le2\sum_{\lvert k\rvert>m}\lvert\hat f_k\rvert$ である。

1。 等比数列の和により、$\sum_{j=0}^{N-1}e^{\mathrm{i}lx_j}$ は $N\mid l$ なら $N$、そうでなければ $0$ である。$\lvert k\rvert,\lvert k'\rvert\le m$ なら $\lvert k-k'\rvert< N$ なので、$N$ 次の正方行列 $B:=(e^{\mathrm{i}kx_j})$ は $B^*B=NI$ を満たす。よって $B$ は正則で(prop-itp-unique)、$Bc=y$ の解は $c=\frac1NB^*y$ である。これが $c_k$ の式である。
2。 $y_j=\sum_l\hat f_le^{\mathrm{i}lx_j}$ を $c_k$ の式に入れると、1 の和の公式により $c_k=\sum_{r\in\mathbb Z}\hat f_{k+rN}$ である。整数 $l$ は $k+rN$($\lvert k\rvert\le m$)の形にただ 1 通りに書ける。$S(x):=\sum_{\lvert k\rvert\le m}\hat f_ke^{\mathrm{i}kx}$ とすると、$t-S$ の係数は $\lvert k\rvert>m$ の $\hat f_l$ を折り返したものなので、$\lvert t-S\rvert\le\sum_{\lvert l\rvert>m}\lvert\hat f_l\rvert$ である。$\lvert f-S\rvert$ も同じ和以下である。$\square$

$c_k=\sum_r\hat f_{k+rN}$ は、高い周波数が低い周波数に折り返される エイリアシング を表す。$c_k$ は 離散Fourier変換 なので、FFT で計算できる。

計算の手順

  1. データを調べる:点の個数、測定の誤差の大きさ、周期性、導関数の値があるかを確かめる。誤差が大きいなら補間をやめ、最小二乗法 や 平滑化スプライン を使う。
  2. 節点を選べるかを調べる:関数を自由に評価できるなら Chebyshev 点が使える。測定点が決まっているなら、節点は動かせない。
  3. 方法を選ぶ:下の表から選ぶ。
  4. 計算する:多項式は重心形か Newton の形で計算する。Vandermonde 行列の連立方程式は解かない。スプラインは三重対角の方程式を解く。
  5. 誤差を見積もる:点を増やした結果や別の方法の結果と比べる。導関数の上界が分かれば誤差の式に入れる。次数を上げて差が小さくならなければ、それ以上上げない。
  6. 使う範囲を確かめる:外挿しない。やむを得ないときは低い次数にし、誤差を別の方法で確かめる。
    状況方法理由
    節点が等間隔で、点が多い3 次スプライン、折れ線高次の多項式は発散しうる(thm-itp-runge)
    節点が等間隔で、点が少ない多項式$\Lambda$ が小さい(ex-itp-lebesgue)
    関数を好きな点で評価でき、$f$ がなめらかChebyshev 点の多項式$\Lambda$ が小さい(ex-itp-lebesgue)
    周期関数で等間隔三角補間prop-itp-trig
    値と導関数が分かるHermite 補間、完全スプライン導関数の情報を使う
    単調性や正値性を保ちたい折れ線、区分的な単調 3 次式スプラインは行き過ぎることがある(スプライン補間 の節「使える条件と反例」)
    点を 1 つずつ足すNewton の形前の係数が使える
    同じ節点で多くのデータを扱う重心形重みはデータによらない
    補間が当てにならない場合の検出として、節点が重なっていないこと、次数を上げたときに値が振動しないことを確かめる。多項式の補間では $\Lambda$ を計算しておくと、データの誤差の増え方が分かる。

例題

同じデータを 5 つの方法で補間する

問い:$f(x)=\log x$ の $x=1,2,3,4,5$ の値から $\log2.5$ を求め、$[1,5]$ の最大誤差を比べる。
使う公式:Lagrange補間 の公式、スプライン補間 の公式。
答え:下の表のとおりである(真の値は $\log2.5\approx0.916291$。最大誤差は数値計算による値)。端の傾きが分かっている完全スプラインが最もよく、端の情報のない not-a-knot 条件と 4 次の多項式が同じ程度で、自然スプラインは左端の大きな曲がりのために悪い。

方法$x=2.5$ の値誤差$[1,5]$ の最大誤差
折れ線$0.895880$$0.020411$$0.05966$
4 次の多項式$0.918487$$-0.002196$$0.00942$
自然スプライン$0.925239$$-0.008948$$0.03608$
not-a-knot のスプライン$0.919399$$-0.003108$$0.01240$
完全スプライン($S'(1)=1$、$S'(5)=0.2$)$0.915287$$0.001004$$0.00483$
重心形で値を計算する

問い:$(0,1)$、$(1,3)$、$(3,2)$ の補間多項式の $x=2$ の値を重心形で求める。
使う公式:prop-itp-bary。
答え:$w=(\frac13,-\frac12,\frac16)$、$p(2)=\frac{10}3\approx3.33333$ である。

途中の計算を開く

$w_0=\frac1{(0-1)(0-3)}=\frac13$、$w_1=\frac1{(1-0)(1-3)}=-\frac12$、$w_2=\frac1{(3-0)(3-1)}=\frac16$ である。分子は $\frac13\cdot\frac12+(-\frac12)\cdot3+\frac16\cdot\frac2{-1}=-\frac53$、分母は $\frac16-\frac12-\frac16=-\frac12$ なので、比は $\frac{10}3$ である。多項式は $p(x)=-\frac56x^2+\frac{17}6x+1$ で、$p(2)=\frac{10}3$ である。

Chebyshev 点と等間隔の点の比較

問い:$f(x)=e^x$ を $[0,2]$ で 4 点の 3 次式で補間する。
使う公式:thm-itp-chebyshev。
答え:Chebyshev 点は $1\pm\cos\frac\pi8$、$1\pm\cos\frac{3\pi}8$、つまり $0.07612,0.61732,1.38268,1.92388$ である。$\max\lvert\Phi\rvert=0.125$ で、誤差の上界は $\frac{e^2}{24}\cdot0.125\approx0.03848$、実際の最大誤差は $0.01810$ である。等間隔の点 $0,\frac23,\frac43,2$ では $\max\lvert\Phi\rvert\approx0.19753$、最大誤差は $0.02714$ である(最大誤差は数値計算による値)。

データの誤差の増え方

問い:$[-1,1]$ の多項式の補間の Lebesgue 定数を、等間隔の点と Chebyshev 点で比べる。
使う公式:def-itp-lebesgue、thm-itp-lebesgue-lower。
答え:下の表のとおりである(数値計算による値)。$n=40$ の等間隔の点では、大きさ $10^{-10}$ のデータの誤差(符号が交互)が約 $0.47$ の誤差になる。

$n$等間隔の点 $\Lambda_n$下界 $2^n/(4n^{3/2})$Chebyshev 点 $\Lambda_n$
$5$$3.106$$0.716$$2.104$
$10$$29.90$$8.095$$2.489$
$20$$1.099\times10^4$$2931$$2.901$
$40$$4.692\times10^9$$1.087\times10^9$$3.327$
Runge の関数

問い:$f(x)=1/(1+25x^2)$ を $[-1,1]$ の $n+1$ 点で補間し、最大誤差を比べる。
使う公式:thm-itp-runge-formula、thm-itp-runge、スプライン補間 の例「Runge の関数」。
答え:下の表のとおりである(数値計算による値。スプラインは等間隔の節点の自然スプライン)。Chebyshev 点の上界は実際の値にとても近い。$n=40$ あたりまでは同じ点の数でスプラインがよく、それより大きい $n$ では Chebyshev 点の多項式が逆転する。

$n$多項式(等間隔)多項式(Chebyshev 点)上界 $1/(\rho^{n+1}-\rho^{-n-1})$自然スプライン
$6$$0.6169$$0.2642$$0.2653$$0.1293$
$10$$1.916$$0.1092$$0.1139$$0.02197$
$20$$59.82$$0.01533$$0.01542$$0.003183$
$40$$1.047\times10^5$$2.895\times10^{-4}$$2.898\times10^{-4}$$2.780\times10^{-4}$
$80$$5.461\times10^{11}$$1.023\times10^{-7}$$1.024\times10^{-7}$$1.611\times10^{-5}$
周期関数の三角補間

問い:$f(x)=e^{\sin x}$ を $N$ 個の等間隔の点で三角補間する。
使う公式:prop-itp-trig。$\hat f_k$ の絶対値は変形 Bessel 関数の値 $I_{\lvert k\rvert}(1)$ である。
答え:下の表のとおりで(数値計算による値)、$N$ を 2 倍にすると誤差の桁数がほぼ 2 倍になる。$N=5$ では $c_0\approx1.266066$、$c_{\pm1}\approx0.002715\mp0.565159\,\mathrm{i}$、$c_{\pm2}\approx-0.135748\mp0.022167\,\mathrm{i}$ で、$t(1)\approx2.37342$($f(1)\approx2.31978$)である。

$N$最大誤差prop-itp-trig の上界
$5$$0.09311$$0.10080$
$9$$1.110\times10^{-3}$$1.183\times10^{-3}$
$17$$2.223\times10^{-8}$$2.323\times10^{-8}$

使える条件と反例

外す条件反例成り立たなくなること
節点が相異なる同じ点に異なる値関数として補間できない
行列 $B$ の正則性$V$ は $1,x^2$ で張られる空間、節点 $\pm1$値 $(0,1)$ では解がなく、値 $(1,1)$ では解が無数にある
正則性(2 変数)$V$ は $1,x,y$ で張られる空間、節点 $(0,0),(1,1),(2,2)$点が一直線上にあると階数が $2$ に落ちる
三角多項式の空間と節点の対応$N=4$、$V$ は $1,\cos x,\sin x,\sin2x$ で張られる空間$\sin2x$ がすべての節点で $0$ で一意性が成り立たない
節点の分布Runge の関数、等間隔の点次数を上げると発散する(thm-itp-runge)
$f$ のなめらかさ$\lvert x\rvert$、Chebyshev 点誤差の減り方が指数的でなくなり、$n=10,20,40,80$ で $0.0546,0.0285,0.0146,0.0074$
周期性$f(x)=x$($0\le x< 2\pi$)の三角補間上限の誤差は $N$ によらず $2\pi$ 以上で、減らない
区間の中で使う$e^x$、$[0,1]$ の等間隔の 5 点の 4 次式誤差は $x=0.9$ で $5.2\times10^{-5}$、$x=3$ で $2.09$
反例の確認

$1,x^2$ と $\pm1$:$x^2$ は $\pm1$ で値 $1$ なので $B=\begin{pmatrix}1&1\\1&1\end{pmatrix}$ である。$u=x^2$ と $u=1$ は節点で同じ値をとる。
三角多項式:$N=4$ の節点は $0,\frac\pi2,\pi,\frac{3\pi}2$ で、そこで $\sin2x=0$ である。$\sin2x$ のかわりに $\cos2x$ を使うと、$B$ は正則になる。
のこぎり波:周期的に延ばした $f$ は $0$ で跳ぶ。$t$ は周期 $2\pi$ の連続関数で $t(0)=f(0)=0$ なので、$x\to2\pi$ で $t(x)\to0$、$f(x)\to2\pi$ である。よって $\sup\lvert f-t\rvert\ge2\pi$ である。prop-itp-trig の和 $\sum\lvert\hat f_k\rvert$ は、この $f$ では発散する。$x=1$ のような跳びから離れた点では誤差は小さくなる($N=101,1001$ で $0.015,0.0054$)。
表の数値は数値計算による値である。

よくある誤り

誤り正しくはなぜ
点を増やせば多項式の補間は必ずよくなると思う等間隔の点では悪化しうるthm-itp-runge
Runge の現象を丸め誤差のせいだと思う厳密な計算でも起こる。補間多項式そのものの性質であるthm-itp-runge-formula
誤差のあるデータを高次の多項式で補間する誤差が $\Lambda$ 倍まで増える。最小二乗の当てはめを使うdef-itp-lebesgue
補間した式を区間の外へ延ばす$\lvert\Phi\rvert$ が急に増えるex-itp-counterexamples
Vandermonde 行列の方程式を解いて係数を求める重心形か Newton の形で計算するprop-itp-bary
誤差を節点だけで調べる節点では誤差は $0$ なので、節点の間の点で調べるdef-itp-problem

演習

3 点の Lebesgue 定数

節点 $-1,0,1$、区間 $[-1,1]$ の 2 次の補間の Lebesgue 定数を求めよ。

解答を開く

$\ell_{-1}=\frac{x(x-1)}2$、$\ell_0=1-x^2$、$\ell_1=\frac{x(x+1)}2$ である。$0\le x\le1$ では $\lvert\ell_{-1}\rvert+\lvert\ell_0\rvert+\lvert\ell_1\rvert=\frac{x(1-x)}2+1-x^2+\frac{x(x+1)}2=1+x-x^2$ で、最大値は $x=\frac12$ の $\frac54$ である。対称性から $\Lambda=\frac54$ である。

補間は射影

prop-itp-unique の条件のもとで、$f$ に補間関数 $Pf$ を対応させる写像は線形で $P(Pf)=Pf$ を満たす。$\ell_k$ の和について、$V$ が定数を含むなら $\sum_k\ell_k=1$ であることを示せ。

解答を開く

$Pf=\sum_kf(x_k)\ell_k$ は $f$ について線形である。$u\in V$ の補間関数は一意性から $u$ 自身なので、$Pf\in V$ から $P(Pf)=Pf$ である。$V$ が定数 $1$ を含むなら、$P1=1$ より $\sum_k\ell_k=1$ である。$\square$

補足

  • 2 変数以上の補間:格子状の点では 1 変数の補間を変数ごとに行う。点が散らばっているときは、反例の表の 2 変数の場合のように、多項式の空間では点の配置によって一意性が成り立たないことがある。
  • 有理関数の補間:分母のある関数で補間する方法もある。極の近くを表しやすいが、分母の零点が区間に入らないことを別に確かめる必要がある。
  • 最良近似との関係:補間は最良一様近似より誤差が大きいが、計算が簡単である。最良近似 の末尾の項目「補間との比較」も参照する。
  • 体の上の補間:有限体の上の補間は、誤差ではなく代数的な性質に意味がある(Lagrange補間 の節「有限体の上の関数」)。

関連項目

参考文献

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