最良近似

同義語：best approximation

概要

前提知識: ノルム空間, 連続関数, 多項式, 中間値の定理

複雑な関数を、多項式のような扱いやすい関数の集まりの中で「いちばん近いもの」に置き換えたい。どれだけ近いかを測る物差し（ノルム）を決めれば、この問いは「与えられた点から部分空間までの距離を実現する点を求めよ」という問題になる。この点を 最良近似 という。物差しが 2 乗の積分なら、最良近似は直交射影であり、連立 1 次方程式で求まる。物差しが区間全体での誤差の最大値（一様ノルム）なら、答えは直交射影ではなく、誤差が同じ大きさで符号を交互に変えながら振れるという Chebyshev の交代定理で特徴づけられる。
この記事では、最良近似を一般のノルム空間で定義して存在と一意性を調べ、区間上の連続関数を次数 $n$ 以下の多項式で一様に近似する場合について、Chebyshev の交代定理とその帰結を証明する。最後に、2 乗のノルムでの最良近似と比べる。連分数の収束子を有理数の「最良近似」と呼ぶ用法（Diophantus近似の節「収束子と最良近似」）は、ノルム空間の最良近似とは別の意味である。

定義

最良近似

$(X,\|\cdot\|)$ を実数体上のノルム空間、$V\subset X$ を部分集合、$x\in X$ とする。
$$ d(x,V):=\inf_{v\in V}\|x-v\| $$
を $x$ と $V$ の距離という。$\|x-v^*\|=d(x,V)$ を満たす $v^*\in V$ を、$x$ の $V$ における最良近似（best approximation）という。

この記事で主に扱うのは次の場合である。$a< b$ とし、$[a,b]$ 上の実数値連続関数全体 $C([a,b])$ に一様ノルム $\|g\|_\infty:=\max_{a\le x\le b}|g(x)|$ を入れる（最大値は最大値の定理により存在する）。$\mathcal P_n$ を次数 $n$ 以下の実数係数の多項式全体（$n\ge0$）とし、
$$ E_n(f):=d(f,\mathcal P_n)=\inf_{p\in\mathcal P_n}\|f-p\|_\infty $$
を $f$ の最良近似の誤差という。$\mathcal P_n$ における $f$ の最良近似を最良一様近似（Chebyshev 近似、ミニマックス近似）という。$\mathcal P_0\subset\mathcal P_1\subset\cdots$ なので $E_0(f)\ge E_1(f)\ge\cdots$ であり、Weierstrassの近似定理は $E_n(f)\to0$（$n\to\infty$）と言い換えられる（同記事の注意「最良近似」）。
$X$ が内積空間で $\|x\|=\sqrt{\langle x,x\rangle}$ のときの最良近似は、最小 2 乗近似とも呼ばれる。

直感

一様ノルムの最良近似は「最悪の場合の誤差をできるだけ小さくする」近似である。誤差 $e=f-p$ のグラフが帯 $-E\le y\le E$ に収まり、上の縁にも下の縁にも触れているとする。$p$ に小さな多項式 $r$ を足して帯を細くするには、$e$ が上の縁に触れる点では $r>0$、下の縁に触れる点では $r< 0$ でなければならない。縁に触れる点の符号が $n+2$ 回入れ替わるなら、そのような $r$ は $n+1$ 個の根をもつことになり、次数 $n$ 以下では $0$ しかない。逆に入れ替わりが $n+1$ 回以下なら、入れ替わりの間に根をもつ $r$ を作れて、帯を細くできる。これが交代定理の内容である。

存在と一意性

有限次元の部分空間での存在

ノルム空間 $X$ の有限次元の部分空間 $V$ と $x\in X$ について、$x$ の $V$ における最良近似が存在する。とくに $f\in C([a,b])$ の $\mathcal P_n$ における最良一様近似が存在する。

$K:=\{v\in V\mid\|v\|\le2\|x\|\}$ とおく。$K$ は有限次元のノルム空間 $V$ の有界閉集合なので、ノルム空間の系「有限次元ノルム空間の性質」の 3 によりコンパクトである。$v\mapsto\|x-v\|$ は連続なので、$K$ 上で最小値をとる点 $v^*\in K$ がある。$v\in V\setminus K$ なら $\|x-v\|\ge\|v\|-\|x\|>\|x\|=\|x-0\|\ge\|x-v^*\|$（$0\in K$）なので、$v^*$ は $V$ 全体で $\|x-v\|$ を最小にする。$\mathcal P_n$ は $C([a,b])$ の $n+1$ 次元の部分空間である。$\square$

一意性はノルムの形による。単位球面が線分を含まないノルムを狭義凸という。狭義凸なノルム空間では、凸集合における最近点は高々 1 つであり（狭義凸ノルムの定理「最近点の一意性による特徴づけ」）、部分空間は凸集合なので、最良近似は存在すれば一意である。内積から定まるノルムは狭義凸で、有限次元の部分空間 $W$ における最良近似は直交射影 $P_Wx$ そのものである（内積空間の定理「直交分解と最良近似」）。
一様ノルムは狭義凸でない（狭義凸ノルムの例「狭義凸でないノルム」の 3）ので、一意性はノルムの一般論からは出ない。$C([a,b])$ で $V=\mathcal P_n$ のときに一意性を保証するのが、次の節の交代定理である。部分空間を $\mathcal P_n$ でない 1 次元の空間に替えると一意性が崩れる例は、反例の表にある。

Chebyshev の交代定理

以下、$f\in C([a,b])$、$n\ge0$ とする。証明では、次の 2 つの事実を使う。

0 でない次数 $n$ 以下の多項式の根は高々 $n$ 個である。したがって、次数 $n$ 以下の多項式で相異なる $n+1$ 個の根をもつものは $0$ である。
連続関数 $r$ が $s< t$ で $r(s)r(t)< 0$ を満たせば、開区間 $(s,t)$ に $r$ の根がある（中間値の定理）。

交代点

$e\in C([a,b])$、$E:=\|e\|_\infty$ とする。点 $a\le s_0< s_1< \cdots< s_m\le b$ と $\sigma\in\{1,-1\}$ で
$$ e(s_k)=\sigma(-1)^kE\qquad(k=0,1,\dots,m) $$
を満たすものを、$e$ の長さ $m+1$ の交代点の列という。誤差の絶対値の最大値を、符号を交互に変えながら $m+1$ 回とることを表す。

まず、誤差の符号が交代するだけで、最良近似の誤差の下からの評価が得られる。

de la Vallée-Poussin の下界

$p\in\mathcal P_n$ と点 $a\le s_0< \cdots< s_{n+1}\le b$ について、$e:=f-p$ の値 $e(s_0),\dots,e(s_{n+1})$ がどれも $0$ でなく、符号が交互に変わるとする。このとき
$$ \min_{0\le k\le n+1}|e(s_k)|\le E_n(f)\le\|e\|_\infty $$
である。

右の不等式は $E_n(f)$ の定義から従う。左の不等式を示すため、$\mu:=\min_k|e(s_k)|$ とし、$\|f-q\|_\infty< \mu$ となる $q\in\mathcal P_n$ があったと仮定する。$r:=q-p\in\mathcal P_n$ とおくと $r=e-(f-q)$ であり、各 $k$ で $|(f-q)(s_k)|< \mu\le|e(s_k)|$ なので、$r(s_k)$ は $0$ でなく、$e(s_k)$ と同じ符号をもつ。よって $r(s_k)$ の符号は $k$ について交互に変わり、中間値の定理により $r$ は $n+1$ 個の開区間 $(s_k,s_{k+1})$（$k=0,\dots,n$）のそれぞれに根をもつ。これらは相異なる $n+1$ 個の根なので $r=0$ だが、$r(s_0)\ne0$ に反する。よってすべての $q\in\mathcal P_n$ で $\|f-q\|_\infty\ge\mu$、すなわち $E_n(f)\ge\mu$ である。$\square$

Chebyshev の交代定理

$f\in C([a,b])$、$n\ge0$、$p\in\mathcal P_n$ とし、$e:=f-p$ とおく。

$p$ が $f$ の $\mathcal P_n$ における最良一様近似であることは、$e$ が長さ $n+2$ の交代点の列をもつことと同値である。
$f$ の $\mathcal P_n$ における最良一様近似はただ 1 つである。

$E:=\|e\|_\infty$ とおく。$E=0$ なら $f=p\in\mathcal P_n$ であり、$p$ は最良近似で、どの $n+2$ 点も（$e(s_k)=0=\sigma(-1)^k\cdot0$ なので）交代点の列である。以下 $E>0$ とする。
交代点の列があれば最良。 $e(s_k)=\sigma(-1)^kE$ を満たす $s_0< \cdots< s_{n+1}$ があれば、$e(s_k)$ は $0$ でなく符号が交互に変わり、$|e(s_k)|=E$ なので、prop-ba-dlvp により $E\le E_n(f)\le E$ である。よって $\|f-p\|_\infty=E_n(f)$ で、$p$ は最良近似である。
最良なら交代点の列がある。 $p$ が最良近似で、長さ $n+2$ の交代点の列がないと仮定し、$\|e-\lambda r\|_\infty< E$ となる $r\in\mathcal P_n$ と $\lambda>0$ を作る。$p+\lambda r\in\mathcal P_n$ なので、これは $p$ が最良であることに反する。
$A_+:=\{x\mid e(x)=E\}$、$A_-:=\{x\mid e(x)=-E\}$、$A:=A_+\cup A_-$ とおく。これらは閉集合で、$A$ は空でない（$|e|$ は最大値 $E$ をとる）。$e$ は $[a,b]$ 上で一様連続なので、$|x-y|\le\delta$ なら $|e(x)-e(y)|< E$ となる $\delta>0$ がある。$A_+$ の点と $A_-$ の点では $e$ の値の差が $2E$ なので、その距離は $\delta$ より大きい。
$t_1:=\min A$ とし、$t_1$ が $A_\pm$ のどちらに属するかで符号 $\sigma_1\in\{1,-1\}$ を決める。$t_1,\dots,t_j$ と符号 $\sigma_1,\dots,\sigma_j$（$\sigma_{i+1}=-\sigma_i$）が決まったとき、$t_j$ より右にある、符号が $-\sigma_j$ の $A$ の点（$\sigma=1$ なら $A_+$、$\sigma=-1$ なら $A_-$ の点を「符号が $\sigma$ の点」とよぶ）があれば、その最小のものを $t_{j+1}$ とする（閉集合なので最小がある）。隣り合う $t_j,t_{j+1}$ は符号が異なるので $t_{j+1}-t_j>\delta$ であり、この操作は有限回で止まる。止まったときの点を $t_1< \cdots< t_m$ とする。作り方から $e(t_j)=\sigma_1(-1)^{j-1}E$ なので、これは長さ $m$ の交代点の列であり、仮定から $m\le n+1$ である。
$1\le j\le m-1$ について、$u_j$ を $[t_j,t_{j+1}]$ の中の符号 $\sigma_j$ の点の最大のものとする。$t_{j+1}$ の取り方から、$[t_j,t_{j+1})$ の $A$ の点はすべて符号 $\sigma_j$ であり、$u_j< t_{j+1}$ で、開区間 $(u_j,t_{j+1})$ は $A$ と交わらない。$z_j:=(u_j+t_{j+1})/2$ とおくと $z_j\notin A$ であり、次が成り立つ。

$A\cap[a,z_1)$ の点の符号はすべて $\sigma_1$（$m=1$ なら $A$ のすべての点の符号が $\sigma_1$）。
$A\cap(z_j,z_{j+1})$ の点の符号はすべて $\sigma_{j+1}$（$1\le j\le m-2$）、$A\cap(z_{m-1},b]$ の点の符号はすべて $\sigma_m$。
最後の主張は、$t_m$ より右に符号 $-\sigma_m$ の点がないこと（操作が止まったこと）による。そこで
$$ r(x):=\sigma_1\prod_{j=1}^{m-1}(z_j-x) $$
とおく（$m=1$ なら $r=\sigma_1$）。$r$ の次数は $m-1\le n$ で、$x< z_1$ では $r(x)$ の符号は $\sigma_1$、$z_j< x< z_{j+1}$ では $\sigma_1(-1)^j=\sigma_{j+1}$、$x>z_{m-1}$ では $\sigma_m$ である。したがって $A$ のすべての点 $x$ で $r(x)\ne0$ かつ $e(x)r(x)>0$ である。
$R:=\|r\|_\infty>0$ とし、閉集合 $F:=\{x\mid e(x)r(x)\le0\}$ を考える。$F$ は $A$ と交わらないので、$F$ が空でなければ $E':=\max_F|e|< E$ であり、空なら $E':=0$ とおく。$0< \lambda< (E-E')/R$ をとる。$\|e-\lambda r\|_\infty$ は、ある点 $x_0$ での値 $|e(x_0)-\lambda r(x_0)|$ である。$x_0\in F$ なら、これは $E'+\lambda R< E$ 以下である。$x_0\notin F$ なら $e(x_0)$ と $r(x_0)$ は同じ符号で $0$ でないので、
$$ |e(x_0)-\lambda r(x_0)|=\bigl||e(x_0)|-\lambda|r(x_0)|\bigr|< E $$
である（$|e(x_0)|-\lambda|r(x_0)|< |e(x_0)|\le E$、$\lambda|r(x_0)|-|e(x_0)|< \lambda R< E$）。どちらの場合も $\|e-\lambda r\|_\infty< E$ となり、矛盾する。

一意性。 $p,q$ がともに最良近似なら、$\|f-\frac{p+q}2\|_\infty\le\frac12\|f-p\|_\infty+\frac12\|f-q\|_\infty=E_n(f)$ なので $\frac{p+q}2$ も最良近似である。$E_n(f)=0$ なら $p=f=q$ である。$E_n(f)>0$ なら、1 により $f-\frac{p+q}2$ は長さ $n+2$ の交代点の列 $s_0,\dots,s_{n+1}$ をもつ。各 $s_k$ で、絶対値が $E_n(f)$ 以下の 2 数 $(f-p)(s_k)$、$(f-q)(s_k)$ の平均が $\pm E_n(f)$ なので、2 数はどちらも $\pm E_n(f)$ に等しい。よって $(p-q)(s_k)=0$（$k=0,\dots,n+1$）で、次数 $n$ 以下の $p-q$ が $n+2$ 個の根をもつので $p=q$ である。$\square$

交代定理の言明は VKG14 Theorem 6.8（p. 525）に、下界は同書 Theorem 6.7（p. 525）にある。交代点の個数 $n+2$ は $\mathcal P_n$ の次元 $n+1$ より 1 多い。誤差が 0 になる点（$f$ と $p$ のグラフの交点）は、交代点の間に少なくとも 1 つずつあるので $n+1$ 個以上あり、最良一様近似は「うまく選んだ $n+1$ 点での補間多項式」でもある。

偶関数の最良一様近似

$c>0$ とし、$f\in C([-c,c])$ が偶関数（$f(-x)=f(x)$）なら、$f$ の $\mathcal P_n$ における最良一様近似は偶関数である。奇関数についても同様である。

例

定数による最良近似

$n=0$ のとき、$M_+:=\max f$、$M_-:=\min f$ とおくと、$f$ の最良一様近似は定数 $\frac{M_++M_-}2$ で、$E_0(f)=\frac{M_+-M_-}2$ である。実際、$e=f-\frac{M_++M_-}2$ は $|e|\le\frac{M_+-M_-}2$ を満たし、$f$ が最大になる点で $\frac{M_+-M_-}2$、最小になる点で $-\frac{M_+-M_-}2$ をとり（$M_+=M_-$ なら $f$ は定数で $E_0(f)=0$）、この 2 点を左から並べたものが長さ $2=n+2$ の交代点の列になる。たとえば $[0,1]$ 上の $e^x$ の最良な定数は $\frac{1+e}2$ で、$E_0=\frac{e-1}2$ である。

単項式の最良近似

$[-1,1]$ で $f(x)=x^{n+1}$ を $\mathcal P_n$ で近似する。Chebyshev 多項式 $T_{n+1}$（$T_{n+1}(\cos\theta)=\cos(n+1)\theta$。Chebyshev多項式）は最高次の係数が $2^n$ なので、$p:=x^{n+1}-2^{-n}T_{n+1}$ は $\mathcal P_n$ に属し、誤差は $e=2^{-n}T_{n+1}$ である。$|e|\le2^{-n}$ で、$s_k:=\cos\frac{(n+1-k)\pi}{n+1}$（$k=0,\dots,n+1$）は $-1=s_0< s_1< \cdots< s_{n+1}=1$ を満たし、$e(s_k)=2^{-n}\cos(n+1-k)\pi=(-1)^{n+1}(-1)^k2^{-n}$ である。よって thm-ba-alternation により $p$ は最良一様近似で
$$ E_n(x^{n+1})=2^{-n} $$
である。$n=1$ なら $x^2$ の最良な 1 次式は $\frac12$（定数）で、誤差 $x^2-\frac12$ は $-1,0,1$ で $\frac12,-\frac12,\frac12$ をとる。

最小最大の多項式の一意性

$n\ge1$ とし、$q$ を最高次の係数が $1$ の $n$ 次の実数係数多項式とする。$\max_{[-1,1]}|q|=2^{1-n}$ ならば $q=2^{1-n}T_n$ である。

$q=x^n-(x^n-q)$ で、$x^n-q\in\mathcal P_{n-1}$ である。ex-ba-monomial（$n$ を $n-1$ に替える）により $E_{n-1}(x^n)=2^{1-n}$ なので、$\|x^n-(x^n-q)\|_\infty=2^{1-n}$ は $x^n-q$ が最良近似であることを意味する。最良近似は一意で（thm-ba-alternation の 2）、$x^n-2^{1-n}T_n$ も最良近似なので、$x^n-q=x^n-2^{1-n}T_n$ である。$\square$

これは Chebyshev多項式の定理「Chebyshev の最小最大定理」の等号が $2^{1-n}T_n$ でしか成り立たないことを示している。

2 次関数の最良な 1 次式

$[0,1]$ で $f(x)=x^2$ を $\mathcal P_1$ で近似する。$p(x)=x-\frac18$ とすると $e(x)=x^2-x+\frac18=(x-\frac12)^2-\frac18$ は $[0,1]$ で $-\frac18\le e\le\frac18$ を満たし、$0,\frac12,1$ で $\frac18,-\frac18,\frac18$ をとる。長さ $3=n+2$ の交代点の列なので、$p$ は最良一様近似で $E_1(x^2)=\frac18$ である。直線 $y=x$（両端を結ぶ弦）を、弦と $x^2$ のグラフの最大のずれ $\frac14$ の半分だけ下げたものになっている。

2 乗のノルムでの最良近似との比較

$C([a,b])$ に内積 $\langle g,h\rangle:=\int_a^bg(x)h(x)\,dx$ を入れると、$\mathcal P_n$ における最良近似は直交射影であり（内積空間の定理「直交分解と最良近似」）、誤差 $f-p$ が $1,x,\dots,x^n$ のすべてと直交するという $n+1$ 本の 1 次方程式で決まる。三角多項式への最良近似が Fourier 級数の部分和であること（Fourier係数と最良近似）や、偶関数・奇関数への分解（偶関数と奇関数の節「直交分解と最良近似」）はこの場合である。
ex-ba-square の $x^2$ では、$e=x^2-a-bx$ が $1$ と $x$ に直交する条件 $\frac13-a-\frac b2=0$、$\frac14-\frac a2-\frac b3=0$ を解いて $a=-\frac16$、$b=1$、すなわち 2 乗の最良近似は $x-\frac16$ である。$u=x-\frac12$ とおいて誤差の 2 乗の積分を計算すると、次の表になる。

近似	誤差 $e$	$\Vert e\Vert_\infty$	$\bigl(\int_0^1e^2\,dx\bigr)^{1/2}$
一様の最良近似 $x-\frac18$	$u^2-\frac18$	$\frac18=0.125$	$\sqrt{7/960}\approx0.0854$
2 乗の最良近似 $x-\frac16$	$u^2-\frac1{12}$	$\frac16\approx0.1667$	$\sqrt{1/180}\approx0.0745$

それぞれの物差しで、それぞれの最良近似が勝っている。2 乗の最良近似 $x-\frac16$ の誤差も $0,\frac12,1$ で $\frac16,-\frac1{12},\frac16$ と符号を交代するので、prop-ba-dlvp からは $\frac1{12}\le E_1(x^2)\le\frac16$ が分かる。このように、求めやすい近似の誤差の交代から最良一様近似の誤差を挟めることが、下界の使い所である。
一般に、2 つの物差しは
$$ \Bigl(\int_a^b|g|^2\,dx\Bigr)^{1/2}\le\sqrt{b-a}\,\|g\|_\infty $$
で結ばれているので、2 乗の最良近似の誤差は $\sqrt{b-a}\,E_n(f)$ 以下である。逆向きの不等式は定数倍をつけても成り立たない（高さ $1$ で幅がいくらでも小さい山形の連続関数を考えればよい）。2 乗の最良近似は 1 次方程式で求まるのに対し、一様の最良近似は交点の位置が $f$ に非線形に依存し、一般には Remez の方法などの反復計算で求める（VKG14 p. 525 と、同書第 6 章の Further reading の項「Filter design」（p. 599））。

反例：仮定を外すと崩れること

外す条件	反例	成り立たなくなること
$V$ が有限次元（prop-ba-existence）	$C([0,1])$ で $V$＝多項式全体、$f(x)=e^x$	Weierstrassの近似定理により $d(f,V)=0$ だが、$e^x$ は何回微分しても $0$ にならないので多項式でなく、最良近似がない
ノルムが狭義凸（一意性）	$\mathbb R^2$ に $\Vert(y_1,y_2)\Vert_\infty=\max(\lvert y_1\rvert,\lvert y_2\rvert)$、$V=\{(0,t)\}$、$x=(1,0)$	$\Vert x-(0,t)\Vert_\infty=\max(1,\lvert t\rvert)$ なので、$\lvert t\rvert\le1$ のすべての $(0,t)$ が最良近似
部分空間が $\mathcal P_n$（thm-ba-alternation の 2）	$C([-1,1])$ で $V=\{cx\}$（1 次元）、$f(x)=1-\lvert x\rvert$	$\Vert f-cx\Vert_\infty=\max(1,\lvert c\rvert)$ なので、$\lvert c\rvert\le1$ のすべての $cx$ が最良近似
交代点の個数が $n+2$（thm-ba-alternation の 1）	$[0,1]$、$f=x^2$、$n=1$、$p=\frac65x-\frac9{50}$	$e=f-p$ は $0,\frac35$ で $\frac9{50},-\frac9{50}$ をとり（$e(1)=-\frac1{50}$）、長さ $2$ の交代点の列しかない。$\Vert e\Vert_\infty=\frac9{50}>\frac18=E_1(f)$ で最良でない
交代する値の絶対値が $\Vert e\Vert_\infty$（thm-ba-alternation の 1）	$[0,1]$、$f=x^2$、$n=1$、$p=x-\frac16$	誤差は $0,\frac12,1$ で符号を交代するが値は $\frac16,-\frac1{12},\frac16$ で、$\Vert e\Vert_\infty=\frac16>\frac18$

3 行目の $V=\{cx\}$ は、$0$ でない元 $x$ が $0$ で根をもつ。$\mathcal P_n$ では $0$ でない元の根が $n$ 個以下であることが交代定理の証明で効いており、この性質のない部分空間では一意性が崩れうる。

さらに先へ

誤差の減り方：$E_n(f)$ が $n\to\infty$ でどれだけ速く $0$ に近づくかは $f$ の滑らかさで決まる。たとえば $f$ が $[0,1]$ で定数 $K$ の Lipschitz 連続なら、Bernstein 多項式の評価（Weierstrassの近似定理の命題「Lipschitz 連続な関数での誤差」）から $E_n(f)\le\frac K{2\sqrt n}$ である。こうした問いは近似理論の主題である。
補間との比較：等間隔の点での補間多項式は最良近似から大きく外れることがある（Lagrange補間の Runge の現象の段落）。$[-1,1]$ 上の連続関数 $f$ について、$T_{n+1}$ の $n+1$ 個の根を補間点とする次数 $n$ 以下の補間多項式の誤差の一様ノルムは $E_n(f)$ の $\frac2\pi\log(n+1)+2$ 倍以下になる（$\log$ は自然対数）ことが知られている（VKG14 の式 (6.21)、p. 528。この記事では証明しない）。