補間(interpolation)とは、いくつかの点で与えられた値を正確に通る関数を、多項式やスプラインなどの関数の族の中から求めることである。関数の表の間の値の計算、数値積分や数値微分の公式の導出に使う。折れ線、多項式、3 次スプライン、三角多項式などの方法があり、データの点の配置となめらかさで選ぶ。等間隔の点で次数を上げると誤差が発散することがあり(Runge の現象)、Chebyshev 点を使うか、区分的な低い次数の関数を使うとこれを避けられる。
前提知識: 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 つは同値である。
補間問題は $Bc=y$ と同値である。1 はこの方程式がどの $y$ についてもただ 1 つの解をもつことなので、2 と同値である。3 は $Bc=0$ なら $c=0$ ということで、$B$ は正方行列なので 2 と同値である。$\square$
$V$ が次数 $n$ 以下の多項式の全体なら 3 が成り立つ(0 でない多項式の根は次数以下の個数)。これが Lagrange補間 の定理「Lagrange 補間」の内容で、$B$ は Vandermonde 行列である。
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 の不等式」)。
補間を使う条件は次のとおりである。
| 方法 | 関数の集合 | 公式の要点 | 誤差($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$ の最大値を小さくする節点が最もよい。
$n\ge0$ とする。
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))。
等間隔の節点で次数を上げると誤差が増えることは、$f(x)=1/(1+25x^2)$ では厳密な式で確かめられる。この関数は分母が $x^2$ の 1 次式なので、誤差が閉じた形になる。起こる理由と起こる範囲の全体は 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$
$f(x)=1/(1+25x^2)$、$n=2m$($m\ge1$)とし、$p_n$ を $[-1,1]$ の $n+1$ 個の節点の補間多項式とする。
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$)である。
第 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}$ である。
1 の下界は証明のための粗い値で、実際の誤差はもっと大きい(ex-itp-runge)。2 の上界はほぼ正確である。楕円の内部で正則な関数についての評価は Runge現象 の定理「Chebyshev 点の誤差」にある。
図: 左は n=10 の 3 つの補間。右は n と最大誤差の片対数グラフ。等間隔の多項式は増え、Chebyshev 点の多項式と自然スプラインは減る
Runge の関数だけが特別なのではない。データの誤差の増え方も、等間隔の節点では指数的である。
$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。 等比数列の和により、$\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 で計算できる。
| 状況 | 方法 | 理由 |
|---|---|---|
| 節点が等間隔で、点が多い | 3 次スプライン、折れ線 | 高次の多項式は発散しうる(thm-itp-runge) |
| 節点が等間隔で、点が少ない | 多項式 | $\Lambda$ が小さい(ex-itp-lebesgue) |
| 関数を好きな点で評価でき、$f$ がなめらか | Chebyshev 点の多項式 | $\Lambda$ が小さい(ex-itp-lebesgue) |
| 周期関数で等間隔 | 三角補間 | prop-itp-trig |
| 値と導関数が分かる | Hermite 補間、完全スプライン | 導関数の情報を使う |
| 単調性や正値性を保ちたい | 折れ線、区分的な単調 3 次式 | スプラインは行き過ぎることがある(スプライン補間 の節「使える条件と反例」) |
| 点を 1 つずつ足す | Newton の形 | 前の係数が使える |
| 同じ節点で多くのデータを扱う | 重心形 | 重みはデータによらない |
問い:$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$ である。
問い:$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$ |
問い:$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 |
節点 $-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$
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する