チェビシェフ近似はなぜ「最良」か

本編「チェビシェフ多項式」で、$T_n$ は $[-1,1]$ で $\pm1$ の間を同じ振れ幅で $n$ 回往復し、そのおかげで関数を多項式で近似するとき区間全体での最大誤差をいちばん小さくできる、と述べた。その証明は大学の関数近似論の話題だと予告したので、ここできちんと与える。道具立てはたった二つ、ロルの定理と$T_n$ の等振動性（equioscillation）である。以下、区間は $[-1,1]$、多項式 $g$ の最大値ノルムを $\lVert g\rVert_{\infty}=\max_{-1\le x\le 1}|g(x)|$ と書く。多項式がモニックとは最高次の係数が $1$ のことをいう。証明中の数値はすべて計算機で照合した¹1$T_n$ の先頭係数 $=2^{n-1}$、$\lVert \widetilde{T}_n\rVert_{\infty}=2^{1-n}$ と等振動、モニック $n$ 次で $\widetilde{T}_n$ が sup ノルム最小、チェビシェフ節点で節点多項式が $2^{-n}T_{n+1}$、補間誤差の上界成立を、いずれも $n\le 8$ で数値検算した。下の脚注へ閉じる。

1. 補間の設定と誤差公式

$n{+}1$ 個の相異なる点（節点）$x_0,x_1,\dots,x_n$ を選び、そこで関数 $f$ の値に一致する $n$ 次以下の多項式$p$（補間多項式、$p(x_i)=f(x_i)$）を考える。$p$ は節点の上では $f$ に一致するが、その間ではずれる。このずれ $f-p$ の正体が次である。

証明（ロルの定理）.　 $x$ が節点なら両辺 $0$ で自明。以下 $x$ は節点でないとする。定数 $\displaystyle c:=\frac{f(x)-p(x)}{W(x)}$（$W(x)\ne0$）を使って、$t$ の関数

$$g(t):=f(t)-p(t)-c\,W(t)$$

を作る。$g$ は $n{+}1$ 回連続微分可能である。まず節点 $t=x_0,\dots,x_n$ で $f(t)-p(t)=0$ かつ $W(t)=0$ だから$g(x_i)=0$。さらに $t=x$ でも $g(x)=\bigl(f(x)-p(x)\bigr)-c\,W(x)=0$。よって $g$ は相異なる $n{+}2$ 個の零点$x_0,\dots,x_n,x$ をもつ。

ここでロルの定理²2微分可能な関数 $h$ が $h(a)=h(b)=0$ を満たせば、$a$ と $b$ の間に $h'(c)=0$ となる $c$ があるという定理である。下の脚注へ閉じるを繰り返す。連続微分可能な関数が相異なる $m$ 個の零点をもてば、その導関数は隣り合う零点の間に少なくとも $m{-}1$ 個の零点をもつ。$g$（零点 $n{+}2$ 個）に適用すると $g'$ は $n{+}1$ 個、$g''$ は $n$ 個、$\dots$、$g^{(n+1)}$ は少なくとも $1$ 個の零点をもつ。それを $\xi$ とする。いっぽう $p$ は $n$ 次以下なので $p^{(n+1)}\equiv0$、$W$ はモニックな $n{+}1$ 次なので $W^{(n+1)}\equiv(n+1)!$。したがって

$$\begin{aligned}0&=g^{(n+1)}(\xi)=f^{(n+1)}(\xi)-c\,(n+1)!\\\Longrightarrow\ c&=\frac{f^{(n+1)}(\xi)}{(n+1)!}.\end{aligned}$$

$c$ の定義に戻せば公式を得る。$\blacksquare$

2. チェビシェフ多項式のモニック最小性

本編のとおり $T_n(\cos\theta)=\cos n\theta$ で、漸化式 $T_{n+1}=2xT_n-T_{n-1}$ から $T_n$ の最高次の係数は$2^{\,n-1}$（$n\ge1$）とわかる。そこで

$$\widetilde{T}_n(x):=2^{\,1-n}\,T_n(x)$$

とおくと、これはモニックな $n$ 次多項式である。$T_n(x)=\cos(n\arccos x)$ は $-1$ と $1$ のあいだを往復し、$x_k=\cos\dfrac{k\pi}{n}$（$k=0,1,\dots,n$）という$n{+}1$ 個の点で交互に $\pm1$ をとる：$T_n(x_k)=(-1)^k$。したがって

$$\begin{aligned}\widetilde{T}_n(x_k)&=(-1)^k\,2^{\,1-n},\\\lVert \widetilde{T}_n\rVert_{\infty}&=2^{\,1-n}.\end{aligned}$$

この「最大値と最小値を交互に、しかも等しい振れ幅でとる」性質を等振動（equioscillation）という。

（図は $n=4$。$T_4$ は $5$ 個の点で $+1,-1,+1,-1,+1$ と交互に極値をとる。モニック版 $\widetilde{T}_4=\tfrac1{8}T_4$ はこれを $\tfrac18$ に縮めた同じ形で、$\pm\tfrac18$ を交互にとる。）

証明（等振動＋背理法）.　 $\widetilde{T}_n$ 自身は $\lVert \widetilde{T}_n\rVert_{\infty}=2^{1-n}$ を達成している。これより小さくできないことを示せばよい。あるモニック $n$ 次多項式$q$ が $\lVert q\rVert_{\infty}<2^{1-n}$ を満たすと仮定して矛盾を導く。差

$$d(x):=\widetilde{T}_n(x)-q(x)$$

を考える。$\widetilde{T}_n$ も $q$ もモニックな $n$ 次だから最高次が打ち消し合い、$d$ の次数は $n{-}1$ 以下である。いっぽう先の $n{+}1$ 個の点 $x_k$（$k=0,\dots,n$）では $\widetilde{T}_n(x_k)=(-1)^k2^{1-n}$ で振れ幅ちょうど $2^{1-n}$、かたや $|q(x_k)|\le\lVert q\rVert_{\infty}<2^{1-n}$。ゆえに

$$\begin{aligned}&d(x_k)=\underbrace{\widetilde{T}_n(x_k)}_{\pm2^{1-n}}-\underbrace{q(x_k)}_{|\cdot|<2^{1-n}}\\&\quad\text{の符号は }\widetilde{T}_n(x_k)\text{ と同じ}=(-1)^k.\end{aligned}$$

つまり $d$ は $x_0>x_1>\dots>x_n$ に沿って符号が $n$ 回入れかわる。連続だから隣り合う符号違いの間に零点があり、$d$ は少なくとも $n$ 個の相異なる零点をもつ。ところが $\deg d\le n-1$。$n$ 個以上の零点をもつ $n{-}1$ 次以下の多項式は恒等的に $0$ しかないので $d\equiv0$、すなわち $q=\widetilde{T}_n$。これは $\lVert q\rVert_{\infty}<2^{1-n}=\lVert \widetilde{T}_n\rVert_{\infty}$ に反する。よってそのような $q$ は存在せず、最小値は $2^{1-n}$ である。

最後に「ただ一つ」を確かめる。$\lVert q\rVert_{\infty}=2^{1-n}$ ちょうどのモニック $q$ では、$d(x_k)$ は $0$ か $(-1)^k$ の符号になり、$0$ になる点では符号の入れかわりを数えられない。そこで零点を重複度こみで数える。内側の点 $x_k$（$1\le k\le n-1$）で $d(x_k)=0$ なら、$q(x_k)=\widetilde{T}_n(x_k)=\pm2^{1-n}$ で、$|q|\le2^{1-n}$ の $q$ も $\widetilde{T}_n$ もそこで極値をとるから $q'(x_k)=\widetilde{T}_n{}'(x_k)=0$、すなわち $d$ はそこで $2$ 重以上の零点をもつ。これを使って数え直すと、$d$ の零点は重複度こみでやはり $n$ 個以上あり、$\deg d\le n-1$ から $d\equiv0$、つまり $q=\widetilde{T}_n$。よって最小値を達成するのは $\widetilde{T}_n$ に限る。$\blacksquare$

3. 応用：チェビシェフ節点が誤差上界を最小にする

補間誤差公式にもどる。$|f^{(n+1)}|$ の $[-1,1]$ 上の最大値を $M_{n+1}$ と書くと、任意の $x$ で

$$|f(x)-p(x)|\le\frac{M_{n+1}}{(n+1)!}\,|W(x)|\le\frac{M_{n+1}}{(n+1)!}\,\lVert W\rVert_{\infty}.$$

$W$ はモニックな $n{+}1$ 次だったから、直前の定理（$n\to n{+}1$）より $\lVert W\rVert_{\infty}\ge 2^{-n}$ で、等号は

$$\begin{aligned}&W=\widetilde{T}_{n+1}=2^{-n}T_{n+1},\\&\text{すなわち節点を }T_{n+1}\text{ の零点}\quad x_i=\cos\frac{(2i+1)\pi}{2(n+1)}\ \ (i=0,\dots,n)\end{aligned}$$

に選んだときに限って成り立つ。この $x_i$ をチェビシェフ節点という。このとき誤差の保証値は

$$\boxed{\,|f(x)-p(x)|\le\frac{M_{n+1}}{(n+1)!\,2^{\,n}}\,}$$

となり、これが節点の選び方をどう変えても、これ以上は良くできない最良の上界である。$f$ 側の因子 $M_{n+1}$ には手を出せないが、こちらで自由になる節点多項式の因子を、チェビシェフ節点が最小化してくれる。

チェビシェフ節点はなぜ端に密なのか

$x_i=\cos\dfrac{(2i+1)\pi}{2(n+1)}$ は、上半円周上に等間隔に並べた角を $x$ 軸へ真下に落とした（射影した）点にほかならない。角が等間隔でも、余弦の射影は端（$x=\pm1$）ほど詰まる。下図はその様子である（$n{+}1=6$ 点）。

4. 背景：一般の最良近似と等振動定理

以上はチェビシェフの等振動定理という一般定理の一場面である。区間上の連続関数 $f$ に対し、$n$ 次以下の多項式で最大誤差 $\lVert f-p\rVert_{\infty}$ を最小にする最良近似 $p^{*}$ はただ一つ存在し、それは

ことで特徴づけられる（等振動）。第 $2$ 節のモニック最小問題は、この定理の $f(x)=x^{\,n}$ の場合にあたる。実際、モニック $n$ 次 $q$ は $q(x)=x^{\,n}-r(x)$（$r$ は $n{-}1$ 次以下）と書けるので、$\lVert q\rVert_{\infty}=\lVert x^{\,n}-r\rVert_{\infty}$ を最小にすることは$x^{\,n}$ を $n{-}1$ 次以下で最良近似することにほかならない。その誤差 $x^{\,n}-r^{*}=\widetilde{T}_n$ が$n{+}1=(n{-}1){+}2$ 点で等振動する、というのが第 $2$ 節で使った事実である。整合している。

塾の授業で配った補足資料をもとに書き直しました。

この記事が含まれている連載

連載塾講師木下木下が作成して塾で配布した補足プリントを公開用にちょっと書き直して置いていきます。結構面白いっしょ。46本の記事・木下 智貴