§E20.12多項式補間

最終更新

多項式は有限個の係数で定まり、その値は四則演算だけで計算することができる。これに対して、数値計算で扱う関数は、有限個の点での値しか与えられていないことが多い。有限個の点での値は関数を定めないので、それらの値から関数全体をどのように推定するかを決める必要がある。

相異なるn+1n+1個の点と、各点に対する値が与えられたとき、それらの点で与えられた値をとる次数nn以下の多項式はただ一つ存在する。この多項式を補間多項式といい、その点を節点という。補間多項式による近似の誤差は、関数を多項式で置き換えることによる誤差と、節点での値の誤差が補間多項式へ伝わる程度とに分けて評価され、どちらも節点の選び方に依存する。たとえばf(x)=1/(1+25x2)f(x)=1/(1+25x^2)を[−1,1][-1,1]の等間隔な2222個の節点で補間すると、補間多項式とffの差はx=20/21x=20/21で1111を超えるが、同じ個数の Chebyshev 節点で補間すると、観察される誤差の最大値は3×10−23\times10^{-2}未満である。

本記事では、補間多項式について、その構成と誤差を解説する。

1 補間多項式

定義 1.1.n∈N≥0n\in\Nとし、実係数で次数がnn以下の多項式の全体をPn\mathcal P_nと書き、その元をR\R上の関数とみなす。相異なる実数x0,…,xnx_0,\dots,x_nと、これらを含む集合S⊆RS\subseteq\R上の関数f ⁣:S→Rf\colon S\to\Rをとる。

  1. p∈Pnp\in\mathcal P_nがp(xi)=f(xi)p(x_i)=f(x_i)（0≤i≤n0\le i\le n）を満たすとき、ppをx0,…,xnx_0,\dots,x_nにおけるffの 補間多項式 (interpolating polynomial) といい、x0,…,xnx_0,\dots,x_nを 節点 (node) という。実数y0,…,yny_0,\dots,y_nが与えられたとき、f(xi):=yif(x_i):=y_iで定まる{x0,…,xn}\{x_0,\dots,x_n\}上の関数ffの補間多項式を、データ(xi,yi)(x_i,y_i)の補間多項式という。
  2. 0≤k≤n+10\le k\le n+1に対してωk(x):=∏j=0k−1(x−xj)\omega_k(x):=\prod_{j=0}^{k-1}(x-x_j)（ω0:=1\omega_0:=1）と置く。ωn+1\omega_{n+1}を 節点多項式 (node polynomial) という。
  3. 0≤i≤n0\le i\le nに対してℓi(x):=∏j≠i(x−xj)/(xi−xj)\ell_i(x):=\prod_{j\ne i}(x-x_j)/(x_i-x_j)（n=0n=0のときℓ0:=1\ell_0:=1）と置く。ℓ0,…,ℓn\ell_0,\dots,\ell_nを Lagrange 基底 (Lagrange basis) といい、∑i=0nf(xi)ℓi\sum_{i=0}^nf(x_i)\ell_iをffの Lagrange 形式 (Lagrange form) という。
  4. 0≤i≤i+k≤n0\le i\le i+k\le nに対して、差商 (divided difference)f[xi,…,xi+k]f[x_i,\dots,x_{i+k}]をkkに関して帰納的にf[xi]:=f(xi)f[x_i]:=f(x_i)、 f[xi,…,xi+k]:=f[xi+1,…,xi+k]−f[xi,…,xi+k−1]xi+k−xi(k≥1)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}\qquad(k\ge1) で定める。
  5. Nn:=∑k=0nf[x0,…,xk] ωkN_n:=\sum_{k=0}^nf[x_0,\dots,x_k]\,\omega_kをffの Newton 形式 (Newton form) という。x0,…,xnx_0,\dots,x_nのいずれとも異なるxn+1∈Sx_{n+1}\in Sを節点に加えると、Newton 形式はNn+1=Nn+f[x0,…,xn+1] ωn+1N_{n+1}=N_n+f[x_0,\dots,x_{n+1}]\,\omega_{n+1}となり、新たに計算する差商はf[xn+1−k,…,xn+1]f[x_{n+1-k},\dots,x_{n+1}]（0≤k≤n+10\le k\le n+1）である。

補題 1.2.r∈N≥1r\in\NNとし、相異なる実数a1,…,ara_1,\dots,a_rとk1,…,kr∈N≥1k_1,\dots,k_r\in\NNをとり、K:=∑i=1rkiK:=\sum_{i=1}^rk_iと置く。実係数多項式ppが、1≤i≤r1\le i\le rと0≤j≤ki−10\le j\le k_i-1を満たすすべてのi,ji,jについてp(j)(ai)=0p^{(j)}(a_i)=0を満たすとする。

  1. 実係数多項式qqが存在してp=q∏i=1r(x−ai)kip=q\prod_{i=1}^r(x-a_i)^{k_i}が成り立つ。
  2. m∈N≥0m\in\Nがm<Km<Kを満たし、p∈Pmp\in\mathcal P_mならば、p=0p=0である。
  3. p∈PKp\in\mathcal P_Kならば、ppのxKx^Kの係数をccとしてp=c∏i=1r(x−ai)kip=c\prod_{i=1}^r(x-a_i)^{k_i}である。

証明. 演習とする（問題 8.1）。▨

定理 1.3.n∈N≥0n\in\Nとし、実数x0,…,xnx_0,\dots,x_nをとり、V:=(xi j)0≤i,j≤nV:=(x_i^{\,j})_{0\le i,j\le n}と置く。次の三条件は同値である。

  1. x0,…,xnx_0,\dots,x_nは相異なる。
  2. 任意の(y0,…,yn)∈Rn+1(y_0,\dots,y_n)\in\R^{n+1}に対して、p(xi)=yip(x_i)=y_i（0≤i≤n0\le i\le n）を満たすp∈Pnp\in\mathcal P_nがただ一つ存在する。
  3. VVは正則である。

これらの条件が成り立つとき、(2)のppはp=∑i=0nyiℓip=\sum_{i=0}^ny_i\ell_iである。

証明.E ⁣:Pn→Rn+1E\colon\mathcal P_n\to\R^{n+1}をE(p):=(p(x0),…,p(xn))E(p):=(p(x_0),\dots,p(x_n))で定める。c=(c0,…,cn)∈Rn+1c=(c_0,\dots,c_n)\in\R^{n+1}に対してE(∑j=0ncjxj)=VcE\bigl(\sum_{j=0}^nc_jx^j\bigr)=Vcである。補題 1.2 (2)により∑jcjxj\sum_jc_jx^jが零関数ならばc=0c=0であるから、c↦∑jcjxjc\mapsto\sum_jc_jx^jはRn+1\R^{n+1}からPn\mathcal P_nへの線形同型である。したがってEEが全単射であることとVVが正則であることは同値であり、(2)⇔\Leftrightarrow(3)が成り立つ。

(1)⇒\Rightarrow(2)を示す。ℓi\ell_iの分子はj≠ij\ne iであるxjx_jで00になり、xix_iで分母に等しいので、ℓi(xj)\ell_i(x_j)はj=ij=iのとき11、j≠ij\ne iのとき00である。ℓi∈Pn\ell_i\in\mathcal P_nであるから、p:=∑iyiℓi∈Pnp:=\sum_iy_i\ell_i\in\mathcal P_nはp(xj)=yjp(x_j)=y_jを満たす。p,p~∈Pnp,\tilde p\in\mathcal P_nがともに条件を満たせば、p−p~∈Pnp-\tilde p\in\mathcal P_nは相異なるn+1n+1点x0,…,xnx_0,\dots,x_nで00になるので、補題 1.2 (2)をki=1k_i=1、K=n+1K=n+1、m=nm=nとして適用してp=p~p=\tilde pを得る。

(2)⇒\Rightarrow(1)を示す。i≠ji\ne jでxi=xjx_i=x_jならば、yi=0y_i=0、yj=1y_j=1であるデータに対してp(xi)=0p(x_i)=0とp(xj)=1p(x_j)=1は両立しないので、(2)は成り立たない。▨

命題 1.4.n∈N≥0n\in\Nとし、相異なる実数x0,…,xnx_0,\dots,x_nと、これらを含む集合上の関数ffをとる。0≤i≤i+k≤n0\le i\le i+k\le nに対して、xi,…,xi+kx_i,\dots,x_{i+k}におけるffのPk\mathcal P_kの補間多項式をPi,kP_{i,k}とする。

  1. Pi,kP_{i,k}のxkx^kの係数は f[xi,…,xi+k]=∑l=ii+kf(xl)∏i≤m≤i+k, m≠l(xl−xm)f[x_i,\dots,x_{i+k}]=\sum_{l=i}^{i+k}\frac{f(x_l)}{\prod_{i\le m\le i+k,\ m\ne l}(x_l-x_m)} に等しい。
  2. 0≤k≤n0\le k\le nに対してP0,k=∑j=0kf[x0,…,xj] ωjP_{0,k}=\sum_{j=0}^kf[x_0,\dots,x_j]\,\omega_jである。特に、ffの Newton 形式と Lagrange 形式は同じ多項式P0,nP_{0,n}である。

証明.Pi,kP_{i,k}のxkx^kの係数をci,kc_{i,k}と置く。

(1)を示す。定理 1.3を節点xi,…,xi+kx_i,\dots,x_{i+k}に適用するとPi,k=∑l=ii+kf(xl)∏m≠l(x−xm)/(xl−xm)P_{i,k}=\sum_{l=i}^{i+k}f(x_l)\prod_{m\ne l}(x-x_m)/(x_l-x_m)（積はi≤m≤i+ki\le m\le i+k、m≠lm\ne lにわたる）であり、第ll項のxkx^kの係数はf(xl)/∏m≠l(xl−xm)f(x_l)/\prod_{m\ne l}(x_l-x_m)であるから、ci,kc_{i,k}は主張の和に等しい。ci,k=f[xi,…,xi+k]c_{i,k}=f[x_i,\dots,x_{i+k}]をkkに関する帰納法で示す。k=0k=0ではPi,0=f(xi)=f[xi]P_{i,0}=f(x_i)=f[x_i]である。k≥1k\ge1とし、k−1k-1で等式が成り立つとする。

Q(x):=(x−xi)Pi+1,k−1(x)−(x−xi+k)Pi,k−1(x)xi+k−xiQ(x):=\frac{(x-x_i)P_{i+1,k-1}(x)-(x-x_{i+k})P_{i,k-1}(x)}{x_{i+k}-x_i}

と置くとQ∈PkQ\in\mathcal P_kである。Q(xi)=Pi,k−1(xi)=f(xi)Q(x_i)=P_{i,k-1}(x_i)=f(x_i)、Q(xi+k)=Pi+1,k−1(xi+k)=f(xi+k)Q(x_{i+k})=P_{i+1,k-1}(x_{i+k})=f(x_{i+k})であり、i<l<i+ki<l<i+kならばPi+1,k−1(xl)=Pi,k−1(xl)=f(xl)P_{i+1,k-1}(x_l)=P_{i,k-1}(x_l)=f(x_l)であるからQ(xl)=f(xl)Q(x_l)=f(x_l)である。定理 1.3の一意性によりQ=Pi,kQ=P_{i,k}であり、xkx^kの係数を比べて

ci,k=ci+1,k−1−ci,k−1xi+k−xi=f[xi+1,…,xi+k]−f[xi,…,xi+k−1]xi+k−xi=f[xi,…,xi+k]c_{i,k}=\frac{c_{i+1,k-1}-c_{i,k-1}}{x_{i+k}-x_i}=\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}=f[x_i,\dots,x_{i+k}]

を得る。

(2)を示す。1≤k≤n1\le k\le nとする。R:=P0,k−P0,k−1∈PkR:=P_{0,k}-P_{0,k-1}\in\mathcal P_kは相異なるkk点x0,…,xk−1x_0,\dots,x_{k-1}で00になる。P0,k−1∈Pk−1P_{0,k-1}\in\mathcal P_{k-1}であるから、RRのxkx^kの係数はc0,k=f[x0,…,xk]c_{0,k}=f[x_0,\dots,x_k]である。補題 1.2 (3)をki=1k_i=1、K=kK=kとして適用してR=f[x0,…,xk] ωkR=f[x_0,\dots,x_k]\,\omega_kを得る。P0,0=f[x0] ω0P_{0,0}=f[x_0]\,\omega_0であるから、kkについて和をとってP0,k=∑j=0kf[x0,…,xj] ωjP_{0,k}=\sum_{j=0}^kf[x_0,\dots,x_j]\,\omega_jを得る。k=nk=nのとき右辺は Newton 形式であり、定理 1.3によりP0,n=∑if(xi)ℓiP_{0,n}=\sum_if(x_i)\ell_iである。▨

例 1.5.f(x)=2xf(x)=2^xと節点0,1,20,1,2をとる。差商はf[0]=1f[0]=1、f[1]=2f[1]=2、f[2]=4f[2]=4、f[0,1]=1f[0,1]=1、f[1,2]=2f[1,2]=2、f[0,1,2]=1/2f[0,1,2]=1/2であり、Newton 形式はN2(x)=1+x+x(x−1)/2N_2(x)=1+x+x(x-1)/2である。節点33を加えると、新たに計算する差商はf[3]=8f[3]=8、f[2,3]=4f[2,3]=4、f[1,2,3]=1f[1,2,3]=1、f[0,1,2,3]=1/6f[0,1,2,3]=1/6であり、N3(x)=N2(x)+x(x−1)(x−2)/6N_3(x)=N_2(x)+x(x-1)(x-2)/6である。N3(3)=1+3+3+1=8N_3(3)=1+3+3+1=8である。 Lagrange 形式では、節点33を加えるとℓ0,ℓ1,ℓ2\ell_0,\ell_1,\ell_2のそれぞれに因子(x−3)/(xi−3)(x-3)/(x_i-3)が掛かり、すべての項が変わる。

2 補間の剰余

補題 2.1.a<ba<bを実数、m∈N≥1m\in\NNとし、g ⁣:[a,b]→Rg\colon[a,b]\to\RをCmC^m級の関数とする。r≥2r\ge2を整数、t1<⋯<trt_1<\dots<t_rを[a,b][a,b]の点とし、整数k1,…,krk_1,\dots,k_rが1≤ki≤m1\le k_i\le mと∑i=1rki≥m+1\sum_{i=1}^rk_i\ge m+1を満たすとする。1≤i≤r1\le i\le rと0≤j≤ki−10\le j\le k_i-1を満たすすべてのi,ji,jについてg(j)(ti)=0g^{(j)}(t_i)=0ならば、g(m)(ξ)=0g^{(m)}(\xi)=0を満たすξ∈(t1,tr)\xi\in(t_1,t_r)が存在する。

証明.mmに関する帰納法で示す。m=1m=1ならばg(t1)=g(t2)=0g(t_1)=g(t_2)=0であり、ggは[t1,t2][t_1,t_2]で連続かつ(t1,t2)(t_1,t_2)で微分可能であるから、§D1.14 定理 2.2によりg′(ξ)=0g'(\xi)=0を満たすξ∈(t1,t2)⊆(t1,tr)\xi\in(t_1,t_2)\subseteq(t_1,t_r)が存在する。

m≥2m\ge2とし、m−1m-1で主張が成り立つとする。各1≤i≤r−11\le i\le r-1について、§D1.14 定理 2.2を[ti,ti+1][t_i,t_{i+1}]上のggに適用して、g′(si)=0g'(s_i)=0を満たすsi∈(ti,ti+1)s_i\in(t_i,t_{i+1})をとる。s1,…,sr−1s_1,\dots,s_{r-1}と、ki≥2k_i\ge2を満たすtit_iの全体を合わせた集合をZZとし、sis_iに重複度11、tit_iに重複度ki−1k_i-1を与える。ZZの点は相異なり、[t1,tr][t_1,t_r]に属する。ki≥2k_i\ge2であるtit_iでは0≤j≤ki−20\le j\le k_i-2に対して(g′)(j)(ti)=g(j+1)(ti)=0(g')^{(j)}(t_i)=g^{(j+1)}(t_i)=0であるから、Cm−1C^{m-1}級の関数g′g'はZZの各点で重複度未満の階数の導関数がすべて00である。重複度は11以上m−1m-1以下であり、その和は(r−1)+∑ki≥2(ki−1)=∑i=1rki−1≥m(r-1)+\sum_{k_i\ge2}(k_i-1)=\sum_{i=1}^rk_i-1\ge mである。r≥3r\ge3ならばs1≠s2s_1\ne s_2であり、r=2r=2ならばk1+k2≥m+1≥3k_1+k_2\ge m+1\ge3からk1≥2k_1\ge2またはk2≥2k_2\ge2であるから、ZZは二点以上を含む。帰納法の仮定をg′g'とZZに適用して、ZZの最小点と最大点の間の開区間に(g′)(m−1)(ξ)=0(g')^{(m-1)}(\xi)=0を満たすξ\xiを得る。この開区間は(t1,tr)(t_1,t_r)に含まれ、g(m)(ξ)=0g^{(m)}(\xi)=0である。▨

定理 2.2.a<ba<bを実数、n∈N≥0n\in\Nとし、f ⁣:[a,b]→Rf\colon[a,b]\to\RをCn+1C^{n+1}級の関数、x0,…,xnx_0,\dots,x_nを[a,b][a,b]の相異なる点、ppをx0,…,xnx_0,\dots,x_nにおけるffの補間多項式とする。

  1. 任意のx∈[a,b]x\in[a,b]に対して f(x)−p(x)=f(n+1)(ξ)(n+1)! ωn+1(x)f(x)-p(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega_{n+1}(x) を満たすξ∈(a,b)\xi\in(a,b)が存在する。xxが節点のとき両辺は00である。n=0n=0のとき、この等式はf(x)−f(x0)=f′(ξ)(x−x0)f(x)-f(x_0)=f'(\xi)(x-x_0)である。
  2. 任意のx∈[a,b]x\in[a,b]に対して ∣f(x)−p(x)∣≤max⁡t∈[a,b]∣f(n+1)(t)∣(n+1)! ∣ωn+1(x)∣|f(x)-p(x)|\le\frac{\max_{t\in[a,b]}|f^{(n+1)}(t)|}{(n+1)!}\,|\omega_{n+1}(x)| が成り立つ。

証明.(1)を示す。xxが節点ならばf(x)=p(x)f(x)=p(x)、ωn+1(x)=0\omega_{n+1}(x)=0であり、任意のξ∈(a,b)\xi\in(a,b)で等式が成り立つ。xxが節点でないとし、K:=(f(x)−p(x))/ωn+1(x)K:=(f(x)-p(x))/\omega_{n+1}(x)、g(t):=f(t)−p(t)−Kωn+1(t)g(t):=f(t)-p(t)-K\omega_{n+1}(t)（t∈[a,b]t\in[a,b]）と置く。ggはCn+1C^{n+1}級であり、相異なるn+2n+2点x0,…,xn,xx_0,\dots,x_n,xで00になる。補題 2.1をm=n+1m=n+1、すべての重複度を11として適用して、これらn+2n+2点の最小点と最大点の間の開区間にg(n+1)(ξ)=0g^{(n+1)}(\xi)=0を満たすξ\xiを得る。この開区間は(a,b)(a,b)に含まれる。p∈Pnp\in\mathcal P_nからp(n+1)=0p^{(n+1)}=0であり、ωn+1\omega_{n+1}はxn+1x^{n+1}の係数が11のn+1n+1次多項式であるからωn+1(n+1)=(n+1)!\omega_{n+1}^{(n+1)}=(n+1)!である。したがって0=g(n+1)(ξ)=f(n+1)(ξ)−K(n+1)!0=g^{(n+1)}(\xi)=f^{(n+1)}(\xi)-K(n+1)!であり、K=f(n+1)(ξ)/(n+1)!K=f^{(n+1)}(\xi)/(n+1)!をKKの定義に代入して等式を得る。

(2)は(1)から従う。▨

3 Lebesgue 定数

定義 3.1.a<ba<bを実数とし、C([a,b])C([a,b])を[a,b][a,b]上の連続な実数値関数の全体、g∈C([a,b])g\in C([a,b])に対して∥g∥∞:=max⁡t∈[a,b]∣g(t)∣\lVert g\rVert_\infty:=\max_{t\in[a,b]}|g(t)|とする。n∈N≥0n\in\Nとし、x0,…,xnx_0,\dots,x_nを[a,b][a,b]の相異なる点、ℓ0,…,ℓn\ell_0,\dots,\ell_nをその Lagrange 基底とする。Pn\mathcal P_nの元は[a,b][a,b]への制限によってC([a,b])C([a,b])の元とみなす。

  1. Inf:=∑i=0nf(xi)ℓiI_nf:=\sum_{i=0}^nf(x_i)\ell_iで定まる写像In ⁣:C([a,b])→C([a,b])I_n\colon C([a,b])\to C([a,b])を 補間作用素 (interpolation operator) という。
  2. λn(x):=∑i=0n∣ℓi(x)∣\lambda_n(x):=\sum_{i=0}^n|\ell_i(x)|を Lebesgue 関数 (Lebesgue function) といい、Λn:=max⁡x∈[a,b]λn(x)\Lambda_n:=\max_{x\in[a,b]}\lambda_n(x)を Lebesgue 定数 (Lebesgue constant) という。
  3. f∈C([a,b])f\in C([a,b])に対してEn(f):=inf⁡q∈Pn∥f−q∥∞E_n(f):=\inf_{q\in\mathcal P_n}\lVert f-q\rVert_\inftyを、ffのPn\mathcal P_nによる 最良一様近似誤差 (error of best uniform approximation) という。

定理 3.2.a<ba<b、n∈N≥0n\in\Nとし、[a,b][a,b]の相異なる点x0,…,xnx_0,\dots,x_nの補間作用素をInI_n、Lebesgue 関数をλn\lambda_n、Lebesgue 定数をΛn\Lambda_nとする。

  1. InI_nは線形であり、任意のq∈Pnq\in\mathcal P_nに対してInq=qI_nq=qである。
  2. sup⁡{∥Inf∥∞∣f∈C([a,b]), ∥f∥∞≤1}=Λn\sup\{\lVert I_nf\rVert_\infty\mid f\in C([a,b]),\ \lVert f\rVert_\infty\le1\}=\Lambda_nである。
  3. δ≥0\delta\ge0とし、実数yi,y~iy_i,\tilde y_iが∣y~i−yi∣≤δ|\tilde y_i-y_i|\le\delta（0≤i≤n0\le i\le n）を満たすとする。データ(xi,yi)(x_i,y_i)と(xi,y~i)(x_i,\tilde y_i)の補間多項式をそれぞれp,p~p,\tilde pとすると、∥p~−p∥∞≤Λnδ\lVert\tilde p-p\rVert_\infty\le\Lambda_n\deltaである。
  4. 任意のf∈C([a,b])f\in C([a,b])に対して∥f−Inf∥∞≤(1+Λn)En(f)\lVert f-I_nf\rVert_\infty\le(1+\Lambda_n)E_n(f)である。

証明.(1)を示す。各f↦f(xi)f\mapsto f(x_i)は線形であるからInI_nは線形である。q∈Pnq\in\mathcal P_nは節点x0,…,xnx_0,\dots,x_nにおける自身の補間多項式であるから、定理 1.3によりInq=∑iq(xi)ℓi=qI_nq=\sum_iq(x_i)\ell_i=qである。

(2)を示す。∥f∥∞≤1\lVert f\rVert_\infty\le1ならば、各x∈[a,b]x\in[a,b]で∣Inf(x)∣≤∑i∣f(xi)∣∣ℓi(x)∣≤λn(x)≤Λn|I_nf(x)|\le\sum_i|f(x_i)||\ell_i(x)|\le\lambda_n(x)\le\Lambda_nである。λn\lambda_nは連続であるから、λn(x∗)=Λn\lambda_n(x^*)=\Lambda_nを満たすx∗∈[a,b]x^*\in[a,b]が存在する。σi∈{−1,0,1}\sigma_i\in\{-1,0,1\}をℓi(x∗)\ell_i(x^*)の符号とし、g ⁣:[a,b]→Rg\colon[a,b]\to\Rを、各節点xix_iで値σi\sigma_iをとり、隣り合う二つの節点の間で一次式、最小の節点より左と最大の節点より右で定数である関数とする。g∈C([a,b])g\in C([a,b])、∥g∥∞≤1\lVert g\rVert_\infty\le1であり、Ing(x∗)=∑iσiℓi(x∗)=ΛnI_ng(x^*)=\sum_i\sigma_i\ell_i(x^*)=\Lambda_nである。

(3)を示す。定理 1.3によりp~−p=∑i(y~i−yi)ℓi\tilde p-p=\sum_i(\tilde y_i-y_i)\ell_iであるから、各x∈[a,b]x\in[a,b]で∣p~(x)−p(x)∣≤δλn(x)≤Λnδ|\tilde p(x)-p(x)|\le\delta\lambda_n(x)\le\Lambda_n\deltaである。

(4)を示す。q∈Pnq\in\mathcal P_nを任意にとる。(1)によりf−Inf=(f−q)−In(f−q)f-I_nf=(f-q)-I_n(f-q)であり、(2)により∥f−Inf∥∞≤∥f−q∥∞+Λn∥f−q∥∞\lVert f-I_nf\rVert_\infty\le\lVert f-q\rVert_\infty+\Lambda_n\lVert f-q\rVert_\inftyである。qqについて下限をとって主張を得る。▨

4 重心形式

定義 4.1.n∈N≥0n\in\Nとし、相異なる実数x0,…,xnx_0,\dots,x_nと実数y0,…,yny_0,\dots,y_nをとる。0≤i≤n0\le i\le nに対してwi:=1/∏j≠i(xi−xj)w_i:=1/\prod_{j\ne i}(x_i-x_j)（n=0n=0のときw0:=1w_0:=1）を 重心の重み (barycentric weight) という。節点でないx∈Rx\in\Rに対して

A(x):=∑i=0nwiyix−xi,D(x):=∑i=0nwix−xiA(x):=\sum_{i=0}^n\frac{w_iy_i}{x-x_i},\qquad D(x):=\sum_{i=0}^n\frac{w_i}{x-x_i}

と置く。x=xix=x_iのときyiy_iを、xxが節点でなくD(x)≠0D(x)\ne0のときA(x)/D(x)A(x)/D(x)を与える式を、データ(xi,yi)(x_i,y_i)の 重心形式 (barycentric formula) という。

命題 4.2.n∈N≥0n\in\N、相異なる実数x0,…,xnx_0,\dots,x_n、実数y0,…,yny_0,\dots,y_nをとり、wiw_i、AA、DDを定義 4.1のとおりとする。ppをデータ(xi,yi)(x_i,y_i)の補間多項式とし、xxを節点でない実数とする。

  1. 0≤i≤n0\le i\le nに対してℓi(x)=ωn+1(x) wi/(x−xi)\ell_i(x)=\omega_{n+1}(x)\,w_i/(x-x_i)である。
  2. D(x)=1/ωn+1(x)D(x)=1/\omega_{n+1}(x)であり、特にD(x)≠0D(x)\ne0である。
  3. p(x)=ωn+1(x)A(x)=A(x)/D(x)p(x)=\omega_{n+1}(x)A(x)=A(x)/D(x)である。したがって、データ(xi,yi)(x_i,y_i)の重心形式は任意の実数でppの値を与える。

証明.x≠xix\ne x_iであるから∏j≠i(x−xj)=ωn+1(x)/(x−xi)\prod_{j\ne i}(x-x_j)=\omega_{n+1}(x)/(x-x_i)であり、ℓi(x)=wi∏j≠i(x−xj)\ell_i(x)=w_i\prod_{j\ne i}(x-x_j)から(1)を得る。定数関数1∈Pn1\in\mathcal P_nはデータ(xi,1)(x_i,1)の補間多項式であるから、定理 1.3により∑iℓi=1\sum_i\ell_i=1であり、(1)と合わせて1=ωn+1(x)D(x)1=\omega_{n+1}(x)D(x)を得る。定理 1.3と(1)によりp(x)=∑iyiℓi(x)=ωn+1(x)A(x)p(x)=\sum_iy_i\ell_i(x)=\omega_{n+1}(x)A(x)であり、(2)によりωn+1(x)=1/D(x)\omega_{n+1}(x)=1/D(x)である。節点xix_iではp(xi)=yip(x_i)=y_iである。▨

補題 4.3. 実数A,A^,D,D^,α,δA,\hat A,D,\hat D,\alpha,\deltaが∣A^−A∣≤α|\hat A-A|\le\alphaと∣D^−D∣≤δ<∣D∣|\hat D-D|\le\delta<|D|を満たすならば、D^≠0\hat D\ne0であり、

∣A^D^−AD∣≤α+∣A/D∣ δ∣D∣−δ\Bigl|\frac{\hat A}{\hat D}-\frac AD\Bigr|\le\frac{\alpha+|A/D|\,\delta}{|D|-\delta}

が成り立つ。

証明.∣D^∣≥∣D∣−∣D^−D∣≥∣D∣−δ>0|\hat D|\ge|D|-|\hat D-D|\ge|D|-\delta>0である。

A^D^−AD=(A^−A)−(A/D)(D^−D)D^\frac{\hat A}{\hat D}-\frac AD=\frac{(\hat A-A)-(A/D)(\hat D-D)}{\hat D}

であるから、分子の絶対値はα+∣A/D∣δ\alpha+|A/D|\delta以下、分母の絶対値は∣D∣−δ|D|-\delta以上である。▨

定理 4.4.FFを浮動小数点数系、uuをその単位丸め誤差、fl⁡\operatorname{fl}をFFの最近接丸めとする。n∈N≥0n\in\Nとし、相異なるx0,…,xn∈Fx_0,\dots,x_n\in F、零でないw0,…,wn∈Fw_0,\dots,w_n\in F、y0,…,yn∈Fy_0,\dots,y_n\in F、どのxix_iとも異なるx∈Fx\in Fをとり、

A:=∑i=0nwiyix−xi,D:=∑i=0nwix−xi,MA:=∑i=0n∣wiyi∣∣x−xi∣,MD:=∑i=0n∣wi∣∣x−xi∣A:=\sum_{i=0}^n\frac{w_iy_i}{x-x_i},\quad D:=\sum_{i=0}^n\frac{w_i}{x-x_i},\quad M_A:=\sum_{i=0}^n\frac{|w_iy_i|}{|x-x_i|},\quad M_D:=\sum_{i=0}^n\frac{|w_i|}{|x-x_i|}

と置く。TTを{1,…,n+1}\{1,\dots,n+1\}上の加算木とし、z=(z0,…,zn)∈Fn+1z=(z_0,\dots,z_n)\in F^{n+1}のTTによる和の計算値vT(z)v_T(z)は、ziz_iを第i+1i+1成分として定める。整数d≥0d\ge0が(d+3)u<1(d+3)u<1を満たし、すべての0≤i≤n0\le i\le nについてdT(i+1)≤dd_T(i+1)\le dであるとし、0≤k≤d+30\le k\le d+3に対してγk:=ku/(1−ku)\gamma_k:=ku/(1-ku)と置く。

  1. 各iiについて∣x−xi∣≤Nmax⁡|x-x_i|\le N_{\max}ならば、si:=fl⁡(x−xi)s_i:=\operatorname{fl}(x-x_i)は00でない。
  2. さらに、各iiについて厳密な商wi/siw_i/s_iが正規範囲にあり、qi:=fl⁡(wi/si)q_i:=\operatorname{fl}(w_i/s_i)とyiy_iの厳密な積が00であるか正規範囲にあるとし、ai:=fl⁡(qiyi)a_i:=\operatorname{fl}(q_iy_i)と置く。a=(a0,…,an)a=(a_0,\dots,a_n)とq=(q0,…,qn)q=(q_0,\dots,q_n)のTTによる和の各加算の厳密な結果の絶対値がNmax⁡N_{\max}以下であるとする。このときA^:=vT(a)\hat A:=v_T(a)とD^:=vT(q)\hat D:=v_T(q)は ∣A^−A∣≤γd+3MA,∣D^−D∣≤γd+2MD|\hat A-A|\le\gamma_{d+3}M_A,\qquad|\hat D-D|\le\gamma_{d+2}M_D を満たす。
  3. さらにγd+2MD<∣D∣\gamma_{d+2}M_D<|D|ならばD^≠0\hat D\ne0である。厳密な商A^/D^\hat A/\hat Dが00であるか正規範囲にあるならば、r:=fl⁡(A^/D^)r:=\operatorname{fl}(\hat A/\hat D)は ∣r−AD∣≤(1+u)e+u∣AD∣,e:=γd+3MA+∣A/D∣ γd+2MD∣D∣−γd+2MD\Bigl|r-\frac AD\Bigr|\le(1+u)e+u\Bigl|\frac AD\Bigr|,\qquad e:=\frac{\gamma_{d+3}M_A+|A/D|\,\gamma_{d+2}M_D}{|D|-\gamma_{d+2}M_D} を満たす。
  4. w0,…,wnw_0,\dots,w_nがx0,…,xnx_0,\dots,x_nの重心の重みであるとし、ppをデータ(xi,yi)(x_i,y_i)の補間多項式、λn(x):=∑i∣ℓi(x)∣\lambda_n(x):=\sum_i|\ell_i(x)|とする。このときA/D=p(x)A/D=p(x)、MD/∣D∣=λn(x)M_D/|D|=\lambda_n(x)、MA/∣D∣=∑i∣yiℓi(x)∣M_A/|D|=\sum_i|y_i\ell_i(x)|である。特に(3)の条件γd+2MD<∣D∣\gamma_{d+2}M_D<|D|はγd+2λn(x)<1\gamma_{d+2}\lambda_n(x)<1と同値であり、 e=γd+3∑i∣yiℓi(x)∣+γd+2λn(x)∣p(x)∣1−γd+2λn(x)e=\frac{\gamma_{d+3}\sum_i|y_i\ell_i(x)|+\gamma_{d+2}\lambda_n(x)|p(x)|}{1-\gamma_{d+2}\lambda_n(x)} である。

証明.(1)を示す。−xi∈F-x_i\in Fであり、x−xi=x+(−xi)x-x_i=x+(-x_i)であるから、§E20.1 系 3.3により∣δi,1∣≤u|\delta_{i,1}|\le uを満たす実数δi,1\delta_{i,1}が存在してsi=(x−xi)(1+δi,1)s_i=(x-x_i)(1+\delta_{i,1})である。x≠xix\ne x_iかつu<1u<1であるからsi≠0s_i\ne0である。

(2)を示す。§E20.1 系 3.2 (2)によりqi=(wi/si)(1+δi,2)q_i=(w_i/s_i)(1+\delta_{i,2})、∣δi,2∣≤u|\delta_{i,2}|\le uである。qiyiq_iy_iが00ならば§E20.1 系 3.2 (1)により、正規範囲にあるならば§E20.1 系 3.2 (2)により、ai=qiyi(1+δi,3)a_i=q_iy_i(1+\delta_{i,3})、∣δi,3∣≤u|\delta_{i,3}|\le uである。したがって

qi=wix−xi(1+δi,1)−1(1+δi,2),ai=wiyix−xi(1+δi,1)−1(1+δi,2)(1+δi,3)q_i=\frac{w_i}{x-x_i}(1+\delta_{i,1})^{-1}(1+\delta_{i,2}),\qquad a_i=\frac{w_iy_i}{x-x_i}(1+\delta_{i,1})^{-1}(1+\delta_{i,2})(1+\delta_{i,3})

である。§E20.3 定理 1.3 (1)により、vT(a)v_T(a)とvT(q)v_T(q)の第ii項には絶対値がuu以下のdT(i+1)d_T(i+1)個の因子1+δ1+\deltaがさらに掛かる。したがってA^\hat Aの第ii項はwiyi/(x−xi)w_iy_i/(x-x_i)にdT(i+1)+3≤d+3d_T(i+1)+3\le d+3個の因子(1+δ)±1(1+\delta)^{\pm1}を掛けたものであり、D^\hat Dの第ii項はwi/(x−xi)w_i/(x-x_i)にdT(i+1)+2≤d+2d_T(i+1)+2\le d+2個の因子を掛けたものである。§E20.1 補題 4.1とk↦ku/(1−ku)k\mapsto ku/(1-ku)の単調性により、∣θi∣≤γd+3|\theta_i|\le\gamma_{d+3}、∣θi′∣≤γd+2|\theta'_i|\le\gamma_{d+2}を満たす実数θi,θi′\theta_i,\theta'_iが存在して

A^=∑i=0nwiyix−xi(1+θi),D^=∑i=0nwix−xi(1+θi′)\hat A=\sum_{i=0}^n\frac{w_iy_i}{x-x_i}(1+\theta_i),\qquad\hat D=\sum_{i=0}^n\frac{w_i}{x-x_i}(1+\theta'_i)

が成り立ち、∣A^−A∣≤γd+3MA|\hat A-A|\le\gamma_{d+3}M_A、∣D^−D∣≤γd+2MD|\hat D-D|\le\gamma_{d+2}M_Dである。

(3)を示す。補題 4.3をα=γd+3MA\alpha=\gamma_{d+3}M_A、δ=γd+2MD\delta=\gamma_{d+2}M_Dとして適用すると、D^≠0\hat D\ne0かつ∣A^/D^−A/D∣≤e|\hat A/\hat D-A/D|\le eである。A^/D^=0\hat A/\hat D=0ならば§E20.1 系 3.2 (1)によりr=A^/D^r=\hat A/\hat Dであり、A^/D^\hat A/\hat Dが正規範囲にあるならば§E20.1 系 3.2 (2)により∣r−A^/D^∣≤u∣A^/D^∣≤u(∣A/D∣+e)|r-\hat A/\hat D|\le u|\hat A/\hat D|\le u(|A/D|+e)である。いずれの場合も∣r−A/D∣≤e+u(∣A/D∣+e)|r-A/D|\le e+u(|A/D|+e)である。

(4)を示す。命題 4.2によりℓi(x)=ωn+1(x)wi/(x−xi)\ell_i(x)=\omega_{n+1}(x)w_i/(x-x_i)、D=1/ωn+1(x)D=1/\omega_{n+1}(x)、A/D=p(x)A/D=p(x)であるから、∣ℓi(x)∣=(∣wi∣/∣x−xi∣)/∣D∣|\ell_i(x)|=(|w_i|/|x-x_i|)/|D|である。iiについて和をとってMD/∣D∣=λn(x)M_D/|D|=\lambda_n(x)とMA/∣D∣=∑i∣yiℓi(x)∣M_A/|D|=\sum_i|y_i\ell_i(x)|を得る。eeの分子と分母を∣D∣|D|で割ってeeの式を得る。▨

例 4.5.F=F(2,53,−1022,1023)F=F(2,53,-1022,1023)、fl⁡\operatorname{fl}を最近接偶数丸め、u=2−53u=2^{-53}とする。節点(x0,x1,x2)=(−1,0,1)(x_0,x_1,x_2)=(-1,0,1)の重心の重みは(w0,w1,w2)=(1/2,−1,1/2)(w_0,w_1,w_2)=(1/2,-1,1/2)であり、f(x)=x2f(x)=x^2のデータ(y0,y1,y2)=(1,0,1)(y_0,y_1,y_2)=(1,0,1)の補間多項式はp(x)=x2p(x)=x^2である。ℓ0(x)=x(x−1)/2\ell_0(x)=x(x-1)/2、ℓ1(x)=1−x2\ell_1(x)=1-x^2、ℓ2(x)=x(x+1)/2\ell_2(x)=x(x+1)/2であるから、0<x<10<x<1では∑i∣yiℓi(x)∣=x\sum_i|y_i\ell_i(x)|=x、λ2(x)=1+x−x2\lambda_2(x)=1+x-x^2である。評価点x:=3⋅2−20x:=3\cdot2^{-20}をとり、TTを逐次和R3R_3とするとd=2d=2である。§E20.1 補題 1.2 (1)によりx+1x+1、xx、x−1x-1はFFに属するのでsi=x−xis_i=x-x_iである。有理数の演算で検算すると、q0+q2=−3⋅2−20q_0+q_2=-3\cdot2^{-20}はFFに属し、A^=−x\hat A=-xである。厳密な値はA=−x/(1−x2)A=-x/(1-x^2)であるからA^=A(1−x2)\hat A=A(1-x^2)である。計算値はr=x2(1−x2)r=x^2(1-x^2)であり、相対誤差はx2=9⋅2−40≈8.19×10−12=73728ux^2=9\cdot2^{-40}\approx8.19\times10^{-12}=73728uである。定理 4.4の仮定はすべて満たされ、γ4λ2(x)<1\gamma_4\lambda_2(x)<1である。定理 4.4 (3)の右辺をp(x)p(x)で割った値は約1.94×10−101.94\times10^{-10}である。yyを変数とする線形汎関数y↦∑iyiℓi(x)y\mapsto\sum_iy_i\ell_i(x)の成分ごとの相対条件数は、§E20.3 補題 2.1 (1)により∑i∣yiℓi(x)∣/∣p(x)∣=1/x=220/3≈3.50×105\sum_i|y_i\ell_i(x)|/|p(x)|=1/x=2^{20}/3\approx3.50\times10^5であり、これとuuの積は約3.88×10−113.88\times10^{-11}である。相対誤差x2x^2はこの積より小さい。

5 Chebyshev 節点

定義 5.1. 以下、k∈N≥0k\in\Nに対してTkT_kは「共役勾配法」のkk次の Chebyshev 多項式（§E20.11 定義 3.1）を表す。n∈N≥0n\in\Nに対して、cj:=cos⁡((2j+1)π/(2n+2))c_j:=\cos\bigl((2j+1)\pi/(2n+2)\bigr)（0≤j≤n0\le j\le n）を[−1,1][-1,1]のn+1n+1個の Chebyshev 節点 (Chebyshev nodes) という。実数a<ba<bに対して、(a+b)/2+(b−a)cj/2(a+b)/2+(b-a)c_j/2（0≤j≤n0\le j\le n）を[a,b][a,b]のn+1n+1個の Chebyshev 節点という。

命題 5.2.k∈N≥0k\in\Nとする。

  1. k≥1k\ge1ならば、TkT_kの次数はkkであり、xkx^kの係数は2k−12^{k-1}である。
  2. k≥1k\ge1ならば、max⁡x∈[−1,1]∣Tk(x)∣=1\max_{x\in[-1,1]}|T_k(x)|=1であり、0≤j≤k0\le j\le kに対してTk(cos⁡(jπ/k))=(−1)jT_k(\cos(j\pi/k))=(-1)^jである。
  3. k≥1k\ge1ならば、cos⁡((2j+1)π/(2k))\cos\bigl((2j+1)\pi/(2k)\bigr)（0≤j≤k−10\le j\le k-1）は(−1,1)(-1,1)の相異なる点であり、Tk=2k−1∏j=0k−1(x−cos⁡((2j+1)π/(2k)))T_k=2^{k-1}\prod_{j=0}^{k-1}\bigl(x-\cos((2j+1)\pi/(2k))\bigr)である。特に、n∈N≥0n\in\Nに対して[−1,1][-1,1]のn+1n+1個の Chebyshev 節点c0,…,cnc_0,\dots,c_nはTn+1T_{n+1}の零点の全体であり、2−nTn+1=∏j=0n(x−cj)2^{-n}T_{n+1}=\prod_{j=0}^n(x-c_j)である。

証明.(1)を示す。T1=xT_1=xである。k≥1k\ge1についてTkT_kの次数がkk、xkx^kの係数が2k−12^{k-1}であり、Tk−1T_{k-1}の次数がk−1k-1以下であれば、Tk+1=2xTk−Tk−1T_{k+1}=2xT_k-T_{k-1}の次数はk+1k+1、xk+1x^{k+1}の係数は2k2^kである。

(2)を示す。§E20.11 補題 3.2 (3)により[−1,1][-1,1]上で∣Tk∣≤1|T_k|\le1である。§E20.11 補題 3.2 (2)によりTk(cos⁡(jπ/k))=cos⁡(jπ)=(−1)jT_k(\cos(j\pi/k))=\cos(j\pi)=(-1)^jであり、j=0j=0で値11をとる。

(3)を示す。θj:=(2j+1)π/(2k)\theta_j:=(2j+1)\pi/(2k)（0≤j≤k−10\le j\le k-1）は(0,π)(0,\pi)の狭義単調増加な点列であり、cos⁡\cosは[0,π][0,\pi]で狭義単調減少であるから、cos⁡θj\cos\theta_jは(−1,1)(-1,1)の相異なる点である。§E20.11 補題 3.2 (2)によりTk(cos⁡θj)=cos⁡((2j+1)π/2)=0T_k(\cos\theta_j)=\cos((2j+1)\pi/2)=0である。(1)と補題 1.2 (3)をki=1k_i=1、K=kK=kとして適用して、Tk=2k−1∏j(x−cos⁡θj)T_k=2^{k-1}\prod_j(x-\cos\theta_j)を得る。この積表示からTkT_kの零点はcos⁡θj\cos\theta_jに限る。k=n+1k=n+1とするとcos⁡θj=cj\cos\theta_j=c_jであり、最後の主張を得る。▨

定理 5.3.n∈N≥0n\in\Nとし、qqをxn+1x^{n+1}の係数が11であるn+1n+1次の実係数多項式とする。このときmax⁡x∈[−1,1]∣q(x)∣≥2−n\max_{x\in[-1,1]}|q(x)|\ge2^{-n}である。q=2−nTn+1q=2^{-n}T_{n+1}は等号を満たし、等号を満たすqqは2−nTn+12^{-n}T_{n+1}に限る。

証明.ηj:=cos⁡(jπ/(n+1))\eta_j:=\cos(j\pi/(n+1))（0≤j≤n+10\le j\le n+1）と置くと、cos⁡\cosは[0,π][0,\pi]で狭義単調減少であるからη0>η1>⋯>ηn+1\eta_0>\eta_1>\dots>\eta_{n+1}である。vj:=1/∏k≠j(ηj−ηk)v_j:=1/\prod_{k\ne j}(\eta_j-\eta_k)と置く。分母の因子のうち負であるものはk<jk<jのjj個であるから、vjv_jの符号は(−1)j(-1)^jである。任意のs∈Pn+1s\in\mathcal P_{n+1}は節点η0,…,ηn+1\eta_0,\dots,\eta_{n+1}における自身の補間多項式であるから、命題 1.4 (1)により

(s の xn+1 の係数)=∑j=0n+1vjs(ηj)(s\text{ の }x^{n+1}\text{ の係数})=\sum_{j=0}^{n+1}v_js(\eta_j)

が成り立つ。s=2−nTn+1s=2^{-n}T_{n+1}とすると、命題 5.2 (1)により左辺は11、命題 5.2 (2)によりs(ηj)=2−n(−1)js(\eta_j)=2^{-n}(-1)^jであるから、1=2−n∑j∣vj∣1=2^{-n}\sum_j|v_j|である。s=qs=qとすると

1=∑j=0n+1vjq(ηj)≤∑j=0n+1∣vj∣∣q(ηj)∣≤2nmax⁡x∈[−1,1]∣q(x)∣1=\sum_{j=0}^{n+1}v_jq(\eta_j)\le\sum_{j=0}^{n+1}|v_j||q(\eta_j)|\le2^n\max_{x\in[-1,1]}|q(x)|

であり、下界を得る。命題 5.2 (2)によりmax⁡x∈[−1,1]∣2−nTn+1(x)∣=2−n\max_{x\in[-1,1]}|2^{-n}T_{n+1}(x)|=2^{-n}である。max⁡x∈[−1,1]∣q(x)∣=2−n\max_{x\in[-1,1]}|q(x)|=2^{-n}とすると、各jjでvjq(ηj)≤∣vj∣2−nv_jq(\eta_j)\le|v_j|2^{-n}であり、その和は2−n∑j∣vj∣=12^{-n}\sum_j|v_j|=1に等しいので、各jjでvjq(ηj)=∣vj∣2−nv_jq(\eta_j)=|v_j|2^{-n}、すなわちq(ηj)=(−1)j2−n=2−nTn+1(ηj)q(\eta_j)=(-1)^j2^{-n}=2^{-n}T_{n+1}(\eta_j)である。q−2−nTn+1∈Pn+1q-2^{-n}T_{n+1}\in\mathcal P_{n+1}は相異なるn+2n+2点で00になるので、補題 1.2 (2)によりq=2−nTn+1q=2^{-n}T_{n+1}である。▨

系 5.4.n∈N≥0n\in\Nとし、a<ba<bを実数とする。

  1. 任意の実数x0,…,xnx_0,\dots,x_nに対してmax⁡x∈[−1,1]∣∏j=0n(x−xj)∣≥2−n\max_{x\in[-1,1]}\bigl|\prod_{j=0}^n(x-x_j)\bigr|\ge2^{-n}であり、等号が成り立つのは(x0,…,xn)(x_0,\dots,x_n)が[−1,1][-1,1]の Chebyshev 節点c0,…,cnc_0,\dots,c_nの並べ替えであるときに限る。
  2. 任意の実数x~0,…,x~n\tilde x_0,\dots,\tilde x_nに対してmax⁡x∈[a,b]∣∏j=0n(x−x~j)∣≥2((b−a)/4)n+1\max_{x\in[a,b]}\bigl|\prod_{j=0}^n(x-\tilde x_j)\bigr|\ge2\bigl((b-a)/4\bigr)^{n+1}であり、x~0,…,x~n\tilde x_0,\dots,\tilde x_nが[a,b][a,b]の Chebyshev 節点であるとき等号が成り立つ。
  3. f ⁣:[a,b]→Rf\colon[a,b]\to\RがCn+1C^{n+1}級であり、ppが[a,b][a,b]の Chebyshev 節点におけるffの補間多項式であるならば、 max⁡x∈[a,b]∣f(x)−p(x)∣≤2(n+1)!(b−a4)n+1max⁡t∈[a,b]∣f(n+1)(t)∣\max_{x\in[a,b]}|f(x)-p(x)|\le\frac{2}{(n+1)!}\Bigl(\frac{b-a}{4}\Bigr)^{n+1}\max_{t\in[a,b]}|f^{(n+1)}(t)| である。[a,b]=[−1,1][a,b]=[-1,1]のとき、右辺はmax⁡t∈[−1,1]∣f(n+1)(t)∣/(2n(n+1)!)\max_{t\in[-1,1]}|f^{(n+1)}(t)|/\bigl(2^n(n+1)!\bigr)である。

証明.(1)を示す。∏j(x−xj)\prod_j(x-x_j)はxn+1x^{n+1}の係数が11のn+1n+1次多項式であるから、定理 5.3により下界が成り立ち、等号は∏j(x−xj)=2−nTn+1\prod_j(x-x_j)=2^{-n}T_{n+1}のときに限る。命題 5.2 (3)により2−nTn+1=∏j(x−cj)2^{-n}T_{n+1}=\prod_j(x-c_j)である。この等式が成り立てば、各ckc_kは∏j(x−xj)\prod_j(x-x_j)の零点であるからあるxjx_jに等しく、相異なるn+1n+1個のckc_kがn+1n+1個のxjx_jに現れるので、(x0,…,xn)(x_0,\dots,x_n)は(c0,…,cn)(c_0,\dots,c_n)の並べ替えである。逆に並べ替えならば∏j(x−xj)=2−nTn+1\prod_j(x-x_j)=2^{-n}T_{n+1}である。

(2)を示す。ϕ(t):=(a+b)/2+(b−a)t/2\phi(t):=(a+b)/2+(b-a)t/2は[−1,1][-1,1]から[a,b][a,b]への全単射であり、tj:=ϕ−1(x~j)t_j:=\phi^{-1}(\tilde x_j)と置くと∏j(ϕ(t)−x~j)=((b−a)/2)n+1∏j(t−tj)\prod_j(\phi(t)-\tilde x_j)=((b-a)/2)^{n+1}\prod_j(t-t_j)である。(1)により[a,b][a,b]上の最大値は((b−a)/2)n+12−n=2((b−a)/4)n+1((b-a)/2)^{n+1}2^{-n}=2((b-a)/4)^{n+1}以上であり、tj=cjt_j=c_jのとき等号が成り立つ。

(3)を示す。[a,b][a,b]の Chebyshev 節点は(a,b)(a,b)の相異なる点である。定理 2.2 (2)と(2)から評価を得る。▨

例 5.5.[a,b]=[−1,1][a,b]=[-1,1]、n=0n=0、f(x)=x2f(x)=x^2とする。Chebyshev 節点はc0=cos⁡(π/2)=0c_0=\cos(\pi/2)=0であり、補間多項式はp=f(0)=0p=f(0)=0、max⁡x∈[−1,1]∣f(x)−p(x)∣=1\max_{x\in[-1,1]}|f(x)-p(x)|=1である。節点x0=1/2x_0=1/\sqrt2では補間多項式は1/21/2であり、max⁡x∈[−1,1]∣x2−1/2∣=1/2\max_{x\in[-1,1]}|x^2-1/2|=1/2である。系 5.4 (1)が最小化するのはmax⁡x∈[−1,1]∣x−x0∣\max_{x\in[-1,1]}|x-x_0|であり、その値はx0=0x_0=0で11、x0=1/2x_0=1/\sqrt2で1+1/21+1/\sqrt2である。

6 等間隔節点と Runge の例

命題 6.1.a<ba<bを実数、n∈N≥1n\in\NNとし、h:=(b−a)/nh:=(b-a)/n、xj:=a+jhx_j:=a+jh（0≤j≤n0\le j\le n）とする。この節点の Lebesgue 関数λn\lambda_nと Lebesgue 定数Λn\Lambda_nは

Λn≥λn(a+h2)=1n!∏j=0n∣j−12∣∑i=0n(ni)1∣i−12∣≥2n4n3/2\Lambda_n\ge\lambda_n\Bigl(a+\frac h2\Bigr)=\frac{1}{n!}\prod_{j=0}^n\Bigl|j-\frac12\Bigr|\sum_{i=0}^n\binom ni\frac{1}{|i-\frac12|}\ge\frac{2^n}{4n^{3/2}}

を満たす。特にn→∞n\to\inftyのときΛn→∞\Lambda_n\to\inftyである。

証明. 演習とする（問題 8.2）。▨

注意 6.2.a<ba<bとし、各n∈N≥1n\in\NNについて[a,b][a,b]の相異なる点x0(n),…,xn(n)x_0^{(n)},\dots,x_n^{(n)}をとり、その補間作用素をInI_n、Lebesgue 定数をΛn\Lambda_nとする。C([a,b])C([a,b])は∥⋅∥∞\lVert\cdot\rVert_\inftyについて完備であり（§E2.5 系 5.6）、定理 3.2 (2)によりInI_nは作用素ノルムがΛn\Lambda_nの有界線形作用素である。sup⁡nΛn=∞\sup_n\Lambda_n=\inftyならば、§E12.4 定理 2.1の対偶によりsup⁡n∥Inf∥∞=∞\sup_n\lVert I_nf\rVert_\infty=\inftyを満たすf∈C([a,b])f\in C([a,b])が存在し、このffについてInfI_nfはffに一様収束しない。等間隔節点では命題 6.1によりΛn→∞\Lambda_n\to\inftyであるから、このようなffが存在する。

例 6.3.f(x):=1/(1+25x2)f(x):=1/(1+25x^2)を[−1,1][-1,1]で考え、n∈{11,21}n\in\{11,21\}について、等間隔節点−1+2j/n-1+2j/n（0≤j≤n0\le j\le n）における補間多項式をpneqp_n^{\mathrm{eq}}、Chebyshev 節点における補間多項式をpnchp_n^{\mathrm{ch}}とする。

等間隔節点、点x∗:=1−1/nx^*:=1-1/n、ffの節点とx∗x^*での値はすべて有理数であり、f(x∗)−pneq(x∗)f(x^*)-p_n^{\mathrm{eq}}(x^*)は有理数の演算で厳密に計算することができる。その値はn=11n=11で−0.4525…-0.4525\ldots、n=21n=21で11.90…11.90\ldotsであり、絶対値は∥f−pneq∥∞\lVert f-p_n^{\mathrm{eq}}\rVert_\inftyの下界である。

50 桁の十進演算で、[−1,1][-1,1]を2000020000等分した格子点上の∣f−p∣|f-p|の最大値を求め、最大点の両隣の格子点の間で三分探索によって精密化した値は次のとおりである。これは観察であり、上界としては証明していない。

nn 等間隔節点 Chebyshev 節点
1111 5.568×10−15.568\times10^{-1} 1.828×10−11.828\times10^{-1}
2121 1.760×1011.760\times10^{1} 2.527×10−22.527\times10^{-2}

ffは∣x∣<1/5|x|<1/5で冪級数∑j≥0(−25x2)j\sum_{j\ge0}(-25x^2)^jに等しいので、偶数kkに対してf(k)(0)=k!(−25)k/2f^{(k)}(0)=k!(-25)^{k/2}である。nnが奇数ならばmax⁡t∈[−1,1]∣f(n+1)(t)∣≥(n+1)! 5n+1\max_{t\in[-1,1]}|f^{(n+1)}(t)|\ge(n+1)!\,5^{n+1}であり、系 5.4 (3)の右辺は5n+1/2n5^{n+1}/2^n以上である。この値はn=11n=11で約1.19×1051.19\times10^5、n=21n=21で約1.14×1091.14\times10^9であり、表の Chebyshev 節点の誤差の10510^5倍、101010^{10}倍を超える。

注意 6.4.a<ba<b、f∈C([a,b])f\in C([a,b])、[a,b][a,b]の相異なる節点x0,…,xnx_0,\dots,x_nをとり、ppをffの補間多項式、p~\tilde pをデータ(xi,y~i)(x_i,\tilde y_i)の補間多項式とすると、f−p~=(f−p)+(p−p~)f-\tilde p=(f-p)+(p-\tilde p)である。第一項は近似の誤差であり、ffがCn+1C^{n+1}級ならば定理 2.2 (2)により導関数の最大値と節点多項式の積で、一般に定理 3.2 (4)により(1+Λn)En(f)(1+\Lambda_n)E_n(f)で上から評価される。第二項はデータの感度であり、∣y~i−f(xi)∣≤δ|\tilde y_i-f(x_i)|\le\deltaならば定理 3.2 (3)によりΛnδ\Lambda_n\delta以下である。例 6.3と同じ方法で観察したΛn\Lambda_nは、等間隔節点でΛ11≈51.21\Lambda_{11}\approx51.21、Λ21≈2.058×104\Lambda_{21}\approx2.058\times10^4、Chebyshev 節点でΛ11≈2.545\Lambda_{11}\approx2.545、Λ21≈2.930\Lambda_{21}\approx2.930である。等間隔節点について証明された下界は、有理数の演算で得たλ11(10/11)=41.04…\lambda_{11}(10/11)=41.04\ldots、λ21(20/21)=1.365…×104\lambda_{21}(20/21)=1.365\ldots\times10^4と、命題 6.1の2n/(4n3/2)2^n/(4n^{3/2})（n=21n=21で約5.45×1035.45\times10^3）である。 binary64 でy~i\tilde y_iをf(xi)f(x_i)の最近接丸めとすると、f(xi)∈[1/26,1]f(x_i)\in[1/26,1]は正規範囲にあるので、§E20.1 定理 2.2 (2)により∣y~i−f(xi)∣≤u=2−53≈1.11×10−16|\tilde y_i-f(x_i)|\le u=2^{-53}\approx1.11\times10^{-16}である。例 6.3の値は厳密な補間多項式の誤差、すなわち第一項であり、n=21n=21の等間隔節点では11.9011.90以上である。観察したΛ21\Lambda_{21}を用いると、同じ節点の第二項は約2.3×10−122.3\times10^{-12}以下である。定理 4.4 (3)が評価するのは、与えられた浮動小数点数の節点・重み・データと評価点に対する比A/DA/Dと、その浮動小数点演算による計算値との差であり、A/DA/Dが補間多項式の値に等しいのは重みが節点の正確な重心の重みである場合である（定理 4.4 (4)）。

7 Hermite 補間

定義 7.1.n∈N≥1n\in\NNとし、相異なる実数x1,…,xnx_1,\dots,x_nと実数y1,…,yny_1,\dots,y_n、d1,…,dnd_1,\dots,d_nをとる。H∈P2n−1H\in\mathcal P_{2n-1}がH(xi)=yiH(x_i)=y_i、H′(xi)=diH'(x_i)=d_i（1≤i≤n1\le i\le n）を満たすとき、HHをデータ(xi,yi,di)(x_i,y_i,d_i)の Hermite 補間多項式 (Hermite interpolating polynomial) という。ffが各xix_iで微分可能な関数でありyi=f(xi)y_i=f(x_i)、di=f′(xi)d_i=f'(x_i)であるとき、HHをx1,…,xnx_1,\dots,x_nにおけるffの Hermite 補間多項式という。

定理 7.2.n∈N≥1n\in\NNとし、相異なる実数x1,…,xnx_1,\dots,x_nと実数y1,…,yny_1,\dots,y_n、d1,…,dnd_1,\dots,d_nをとる。1≤i≤n1\le i\le nに対してLi(x):=∏j≠i(x−xj)/(xi−xj)L_i(x):=\prod_{j\ne i}(x-x_j)/(x_i-x_j)（n=1n=1のときL1:=1L_1:=1）と置く。データ(xi,yi,di)(x_i,y_i,d_i)の Hermite 補間多項式はただ一つ存在し、

H=∑i=1n(yi(1−2Li′(xi)(x−xi))+di(x−xi))Li2H=\sum_{i=1}^n\Bigl(y_i\bigl(1-2L_i'(x_i)(x-x_i)\bigr)+d_i(x-x_i)\Bigr)L_i^2

である。

証明.hi:=(1−2Li′(xi)(x−xi))Li2h_i:=\bigl(1-2L_i'(x_i)(x-x_i)\bigr)L_i^2、ki:=(x−xi)Li2k_i:=(x-x_i)L_i^2と置く。Li∈Pn−1L_i\in\mathcal P_{n-1}であるからhi,ki∈P2n−1h_i,k_i\in\mathcal P_{2n-1}である。j≠ij\ne iならばLi(xj)=0L_i(x_j)=0であり、hih_iとkik_iは一次式とLi2L_i^2の積であって、その導関数は一次式の導関数とLi2L_i^2の積と、一次式と2LiLi′2L_iL_i'の積の和であるから、hi(xj)=hi′(xj)=ki(xj)=ki′(xj)=0h_i(x_j)=h_i'(x_j)=k_i(x_j)=k_i'(x_j)=0である。Li(xi)=1L_i(x_i)=1からhi(xi)=1h_i(x_i)=1、ki(xi)=0k_i(x_i)=0であり、

hi′(xi)=−2Li′(xi)Li(xi)2+2Li(xi)Li′(xi)=0,ki′(xi)=Li(xi)2=1h_i'(x_i)=-2L_i'(x_i)L_i(x_i)^2+2L_i(x_i)L_i'(x_i)=0,\qquad k_i'(x_i)=L_i(x_i)^2=1

である。したがってH=∑i(yihi+diki)H=\sum_i(y_ih_i+d_ik_i)は Hermite 補間多項式である。H,H~H,\tilde Hがともにデータ(xi,yi,di)(x_i,y_i,d_i)の Hermite 補間多項式ならば、G:=H−H~∈P2n−1G:=H-\tilde H\in\mathcal P_{2n-1}は各xix_iでG(xi)=G′(xi)=0G(x_i)=G'(x_i)=0を満たす。補題 1.2 (2)をki=2k_i=2、K=2nK=2n、m=2n−1m=2n-1として適用してG=0G=0を得る。▨

定理 7.3.a<ba<bを実数、n∈N≥1n\in\NNとし、f ⁣:[a,b]→Rf\colon[a,b]\to\RをC2nC^{2n}級の関数、x1,…,xnx_1,\dots,x_nを[a,b][a,b]の相異なる点、HHをx1,…,xnx_1,\dots,x_nにおけるffの Hermite 補間多項式とする。任意のx∈[a,b]x\in[a,b]に対して

f(x)−H(x)=f(2n)(ξ)(2n)!∏i=1n(x−xi)2f(x)-H(x)=\frac{f^{(2n)}(\xi)}{(2n)!}\prod_{i=1}^n(x-x_i)^2

を満たすξ∈(a,b)\xi\in(a,b)が存在する。xxが節点のとき両辺は00である。

証明.Ω(t):=∏i=1n(t−xi)2\Omega(t):=\prod_{i=1}^n(t-x_i)^2と置く。xxが節点ならばf(x)=H(x)f(x)=H(x)、Ω(x)=0\Omega(x)=0であり、任意のξ∈(a,b)\xi\in(a,b)で等式が成り立つ。xxが節点でないとし、K:=(f(x)−H(x))/Ω(x)K:=(f(x)-H(x))/\Omega(x)、g(t):=f(t)−H(t)−KΩ(t)g(t):=f(t)-H(t)-K\Omega(t)（t∈[a,b]t\in[a,b]）と置く。ggはC2nC^{2n}級である。各iiについてΩ=(t−xi)2Ri\Omega=(t-x_i)^2R_i、Ri:=∏j≠i(t−xj)2R_i:=\prod_{j\ne i}(t-x_j)^2と書けばΩ′=2(t−xi)Ri+(t−xi)2Ri′\Omega'=2(t-x_i)R_i+(t-x_i)^2R_i'であるからΩ(xi)=Ω′(xi)=0\Omega(x_i)=\Omega'(x_i)=0であり、H(xi)=f(xi)H(x_i)=f(x_i)、H′(xi)=f′(xi)H'(x_i)=f'(x_i)と合わせてg(xi)=g′(xi)=0g(x_i)=g'(x_i)=0である。またg(x)=0g(x)=0である。相異なるn+1≥2n+1\ge2点x1,…,xn,xx_1,\dots,x_n,xに重複度2,…,2,12,\dots,2,1を与えると、重複度は11以上2n2n以下であり、その和は2n+12n+1である。補題 2.1をm=2nm=2nとして適用して、これらn+1n+1点の最小点と最大点の間の開区間にg(2n)(ξ)=0g^{(2n)}(\xi)=0を満たすξ\xiを得る。この開区間は(a,b)(a,b)に含まれる。H∈P2n−1H\in\mathcal P_{2n-1}からH(2n)=0H^{(2n)}=0であり、Ω\Omegaはt2nt^{2n}の係数が11の2n2n次多項式であるからΩ(2n)=(2n)!\Omega^{(2n)}=(2n)!である。したがって0=g(2n)(ξ)=f(2n)(ξ)−K(2n)!0=g^{(2n)}(\xi)=f^{(2n)}(\xi)-K(2n)!であり、K=f(2n)(ξ)/(2n)!K=f^{(2n)}(\xi)/(2n)!をKKの定義に代入して等式を得る。▨

命題 7.4.c∈Rc\in\R、h>0h>0とし、x∈Rx\in\Rに対してt:=(x−c)/ht:=(x-c)/hと置き、

φ1(t):=(1−t)2(1+2t),φ2(t):=t2(3−2t),ψ1(t):=t(1−t)2,ψ2(t):=−t2(1−t)\varphi_1(t):=(1-t)^2(1+2t),\quad\varphi_2(t):=t^2(3-2t),\quad\psi_1(t):=t(1-t)^2,\quad\psi_2(t):=-t^2(1-t)

とする。

  1. 実数y1,y2,d1,d2y_1,y_2,d_1,d_2に対して、H(x):=y1φ1(t)+y2φ2(t)+h(d1ψ1(t)+d2ψ2(t))H(x):=y_1\varphi_1(t)+y_2\varphi_2(t)+h\bigl(d_1\psi_1(t)+d_2\psi_2(t)\bigr)は、節点c,c+hc,c+hにおけるデータ(c,y1,d1)(c,y_1,d_1)、(c+h,y2,d2)(c+h,y_2,d_2)の Hermite 補間多項式である。
  2. t∈[0,1]t\in[0,1]ならば、φ1(t)≥0\varphi_1(t)\ge0、φ2(t)≥0\varphi_2(t)\ge0、φ1(t)+φ2(t)=1\varphi_1(t)+\varphi_2(t)=1、∣ψ1(t)∣+∣ψ2(t)∣=t(1−t)≤1/4|\psi_1(t)|+|\psi_2(t)|=t(1-t)\le1/4である。
  3. εy,εd≥0\varepsilon_y,\varepsilon_d\ge0とし、実数y~1,y~2,d~1,d~2\tilde y_1,\tilde y_2,\tilde d_1,\tilde d_2が∣y~i−yi∣≤εy|\tilde y_i-y_i|\le\varepsilon_y、∣d~i−di∣≤εd|\tilde d_i-d_i|\le\varepsilon_d（i=1,2i=1,2）を満たすとする。データ(c,y~1,d~1)(c,\tilde y_1,\tilde d_1)、(c+h,y~2,d~2)(c+h,\tilde y_2,\tilde d_2)の Hermite 補間多項式H~\tilde Hはmax⁡x∈[c,c+h]∣H~(x)−H(x)∣≤εy+hεd/4\max_{x\in[c,c+h]}|\tilde H(x)-H(x)|\le\varepsilon_y+h\varepsilon_d/4を満たす。
  4. f ⁣:[c,c+h]→Rf\colon[c,c+h]\to\RがC4C^4級であり、y1=f(c)y_1=f(c)、y2=f(c+h)y_2=f(c+h)、d1=f′(c)d_1=f'(c)、d2=f′(c+h)d_2=f'(c+h)ならば、max⁡x∈[c,c+h]∣f(x)−H(x)∣≤h4max⁡s∈[c,c+h]∣f(4)(s)∣/384\max_{x\in[c,c+h]}|f(x)-H(x)|\le h^4\max_{s\in[c,c+h]}|f^{(4)}(s)|/384である。

証明.(1)を示す。φ1(0)=φ2(1)=1\varphi_1(0)=\varphi_2(1)=1、φ1(1)=φ2(0)=0\varphi_1(1)=\varphi_2(0)=0、ψ1(0)=ψ1(1)=ψ2(0)=ψ2(1)=0\psi_1(0)=\psi_1(1)=\psi_2(0)=\psi_2(1)=0であり、

φ1′(t)=−6t(1−t),φ2′(t)=6t(1−t),ψ1′(t)=(1−t)(1−3t),ψ2′(t)=t(3t−2)\varphi_1'(t)=-6t(1-t),\quad\varphi_2'(t)=6t(1-t),\quad\psi_1'(t)=(1-t)(1-3t),\quad\psi_2'(t)=t(3t-2)

からφ1′,φ2′\varphi_1',\varphi_2'はt=0,1t=0,1で00、ψ1′(0)=ψ2′(1)=1\psi_1'(0)=\psi_2'(1)=1、ψ1′(1)=ψ2′(0)=0\psi_1'(1)=\psi_2'(0)=0である。dt/dx=1/hdt/dx=1/hであるからH′(x)=(y1φ1′(t)+y2φ2′(t))/h+d1ψ1′(t)+d2ψ2′(t)H'(x)=\bigl(y_1\varphi_1'(t)+y_2\varphi_2'(t)\bigr)/h+d_1\psi_1'(t)+d_2\psi_2'(t)であり、H(c)=y1H(c)=y_1、H(c+h)=y2H(c+h)=y_2、H′(c)=d1H'(c)=d_1、H′(c+h)=d2H'(c+h)=d_2である。H∈P3H\in\mathcal P_3であるから、HHは Hermite 補間多項式であり、定理 7.2によりただ一つである。

(2)を示す。t∈[0,1]t\in[0,1]では各因子が非負であるからφ1(t),φ2(t)≥0\varphi_1(t),\varphi_2(t)\ge0である。φ1(t)=1−3t2+2t3\varphi_1(t)=1-3t^2+2t^3、φ2(t)=3t2−2t3\varphi_2(t)=3t^2-2t^3であるから和は11である。∣ψ1(t)∣+∣ψ2(t)∣=t(1−t)2+t2(1−t)=t(1−t)=1/4−(t−1/2)2≤1/4|\psi_1(t)|+|\psi_2(t)|=t(1-t)^2+t^2(1-t)=t(1-t)=1/4-(t-1/2)^2\le1/4である。

(3)を示す。(1)によりH~(x)−H(x)=∑i(y~i−yi)φi(t)+h∑i(d~i−di)ψi(t)\tilde H(x)-H(x)=\sum_i(\tilde y_i-y_i)\varphi_i(t)+h\sum_i(\tilde d_i-d_i)\psi_i(t)である。x∈[c,c+h]x\in[c,c+h]ならばt∈[0,1]t\in[0,1]であり、(2)により∣H~(x)−H(x)∣≤εy(φ1(t)+φ2(t))+hεd(∣ψ1(t)∣+∣ψ2(t)∣)≤εy+hεd/4|\tilde H(x)-H(x)|\le\varepsilon_y\bigl(\varphi_1(t)+\varphi_2(t)\bigr)+h\varepsilon_d\bigl(|\psi_1(t)|+|\psi_2(t)|\bigr)\le\varepsilon_y+h\varepsilon_d/4である。

(4)を示す。M4:=max⁡s∈[c,c+h]∣f(4)(s)∣M_4:=\max_{s\in[c,c+h]}|f^{(4)}(s)|と置く。定理 7.3をn=2n=2、[a,b]=[c,c+h][a,b]=[c,c+h]として適用すると、各x∈[c,c+h]x\in[c,c+h]で∣f(x)−H(x)∣≤M4(x−c)2(x−c−h)2/24=M4h4t2(1−t)2/24|f(x)-H(x)|\le M_4(x-c)^2(x-c-h)^2/24=M_4h^4t^2(1-t)^2/24である。(2)によりt2(1−t)2≤1/16t^2(1-t)^2\le1/16であり、評価を得る。▨

例 7.5.c=0c=0、h=1h=1、f(x)=x4f(x)=x^4とし、HHを0,10,1におけるffの Hermite 補間多項式とする。f(4)=24f^{(4)}=24であるから、定理 7.3により[0,1][0,1]の各点でf(x)−H(x)=x2(x−1)2f(x)-H(x)=x^2(x-1)^2である。この値はx=1/2x=1/2で1/161/16であり、命題 7.4 (4)の右辺24/384=1/1624/384=1/16に等しい。

8 演習

問題 8.1.補題 1.2の証明を完成させよ。

解答.

a∈Ra\in\Rと実係数多項式ssに対して、l≥1l\ge1のときxl−al=(x−a)∑m=0l−1xmal−1−mx^l-a^l=(x-a)\sum_{m=0}^{l-1}x^ma^{l-1-m}であるから、s(x)−s(a)=(x−a)s1(x)s(x)-s(a)=(x-a)s_1(x)を満たす実係数多項式s1s_1が存在する。

一点の場合として、k∈N≥1k\in\NN、s(j)(a)=0s^{(j)}(a)=0（0≤j≤k−10\le j\le k-1）ならばs=(x−a)ks2s=(x-a)^ks_2を満たす実係数多項式s2s_2が存在することを、kkに関する帰納法で示す。k=1k=1の場合は上の等式でs(a)=0s(a)=0としたものである。s(j)(a)=0s^{(j)}(a)=0（0≤j≤k0\le j\le k）とし、kkの場合を用いてs=(x−a)ks2s=(x-a)^ks_2と書く。l<kl<kならば((x−a)k)(l)\bigl((x-a)^k\bigr)^{(l)}は(x−a)k−l(x-a)^{k-l}の定数倍でありaaで00になるので、Leibniz の公式により

0=s(k)(a)=∑l=0k(kl)((x−a)k)(l)(a) s2(k−l)(a)=k! s2(a)0=s^{(k)}(a)=\sum_{l=0}^k\binom kl\bigl((x-a)^k\bigr)^{(l)}(a)\,s_2^{(k-l)}(a)=k!\,s_2(a)

である。s2(a)=0s_2(a)=0からs2=(x−a)s3s_2=(x-a)s_3を満たす実係数多項式s3s_3があり、s=(x−a)k+1s3s=(x-a)^{k+1}s_3である。

補題 1.2 (1)をrrに関する帰納法で示す。r=1r=1は一点の場合である。r≥2r\ge2とし、r−1r-1の場合を用いてP:=∏i=1r−1(x−ai)kiP:=\prod_{i=1}^{r-1}(x-a_i)^{k_i}と実係数多項式ssによりp=Psp=Psと書く。ara_rはa1,…,ar−1a_1,\dots,a_{r-1}と異なるのでP(ar)≠0P(a_r)\ne0である。0≤j≤kr−10\le j\le k_r-1とし、l<jl<jでs(l)(ar)=0s^{(l)}(a_r)=0であるとすると、Leibniz の公式により

0=p(j)(ar)=∑l=0j(jl)P(j−l)(ar) s(l)(ar)=P(ar) s(j)(ar)0=p^{(j)}(a_r)=\sum_{l=0}^j\binom jlP^{(j-l)}(a_r)\,s^{(l)}(a_r)=P(a_r)\,s^{(j)}(a_r)

であるからs(j)(ar)=0s^{(j)}(a_r)=0である。jjに関する帰納法によりs(j)(ar)=0s^{(j)}(a_r)=0（0≤j≤kr−10\le j\le k_r-1）であり、一点の場合からs=(x−ar)krqs=(x-a_r)^{k_r}qを満たす実係数多項式qqがある。p=q∏i=1r(x−ai)kip=q\prod_{i=1}^r(x-a_i)^{k_i}である。

補題 1.2 (2)を示す。補題 1.2 (1)のqqが00でなければ、ppの次数はdeg⁡q+K≥K>m\deg q+K\ge K>mであり、p∈Pmp\in\mathcal P_mと両立しない。したがってq=0q=0であり、p=0p=0である。

補題 1.2 (3)を示す。p∈PKp\in\mathcal P_Kならば、補題 1.2 (1)のqqは00であるか次数が00であり、定数c′c'である。c′∏i(x−ai)kic'\prod_i(x-a_i)^{k_i}のxKx^Kの係数はc′c'であるからc′=cc'=cである。▨

問題 8.2.命題 6.1の証明を完成させよ。

解答.

t:=a+h/2t:=a+h/2と置く。t∈[a,b]t\in[a,b]であるからΛn≥λn(t)\Lambda_n\ge\lambda_n(t)である。t−xj=(1/2−j)ht-x_j=(1/2-j)h、xi−xj=(i−j)hx_i-x_j=(i-j)hであり、∏j≠i∣i−j∣=i! (n−i)!\prod_{j\ne i}|i-j|=i!\,(n-i)!であるから

∣ℓi(t)∣=∏j≠i∣j−12∣∣i−j∣=1∣i−12∣ i! (n−i)!∏j=0n∣j−12∣|\ell_i(t)|=\prod_{j\ne i}\frac{|j-\frac12|}{|i-j|}=\frac{1}{|i-\frac12|\,i!\,(n-i)!}\prod_{j=0}^n\Bigl|j-\frac12\Bigr|

であり、iiについて和をとって等式を得る。0≤i≤n0\le i\le nでは∣i−1/2∣≤n−1/2<n|i-1/2|\le n-1/2<nであるから、∑i(ni)/∣i−1/2∣≥2n/n\sum_i\binom ni/|i-1/2|\ge2^n/nである。また

1n!∏j=0n∣j−12∣=12∏j=1nj−12j=12∏j=1n(1−12j)\frac1{n!}\prod_{j=0}^n\Bigl|j-\frac12\Bigr|=\frac12\prod_{j=1}^n\frac{j-\frac12}{j}=\frac12\prod_{j=1}^n\Bigl(1-\frac1{2j}\Bigr)

である。j≥2j\ge2ならば(1−12j)2=1−1j+14j2≥j−1j(1-\frac1{2j})^2=1-\frac1j+\frac1{4j^2}\ge\frac{j-1}{j}であるから、

∏j=1n(1−12j)≥12(∏j=2nj−1j)1/2=12n\prod_{j=1}^n\Bigl(1-\frac1{2j}\Bigr)\ge\frac12\Bigl(\prod_{j=2}^n\frac{j-1}{j}\Bigr)^{1/2}=\frac{1}{2\sqrt n}

である（n=1n=1では空積を11とする）。これらを掛け合わせてλn(t)≥12⋅12n⋅2nn=2n4n3/2\lambda_n(t)\ge\frac12\cdot\frac1{2\sqrt n}\cdot\frac{2^n}{n}=\frac{2^n}{4n^{3/2}}を得る。2n/(4n3/2)→∞2^n/(4n^{3/2})\to\inftyであるからΛn→∞\Lambda_n\to\inftyである。▨

問題 8.3.δ≥0\delta\ge0とし、[−1,1][-1,1]の節点(x0,x1,x2)=(−1,0,1)(x_0,x_1,x_2)=(-1,0,1)の Lebesgue 関数をλ2\lambda_2とし、実数y0,y1,y2y_0,y_1,y_2をとる。∣y~i−yi∣≤δ|\tilde y_i-y_i|\le\delta（0≤i≤20\le i\le2）を満たす実数y~0,y~1,y~2\tilde y_0,\tilde y_1,\tilde y_2と、データ(xi,yi)(x_i,y_i)、(xi,y~i)(x_i,\tilde y_i)の補間多項式p,p~p,\tilde pについて、∣p~(1/2)−p(1/2)∣|\tilde p(1/2)-p(1/2)|の最大値を求め、それを達成するy~0,y~1,y~2\tilde y_0,\tilde y_1,\tilde y_2を示せ。

解答.

Lagrange 基底はℓ0(x)=x(x−1)/2\ell_0(x)=x(x-1)/2、ℓ1(x)=1−x2\ell_1(x)=1-x^2、ℓ2(x)=x(x+1)/2\ell_2(x)=x(x+1)/2であり、(ℓ0(1/2),ℓ1(1/2),ℓ2(1/2))=(−1/8,3/4,3/8)(\ell_0(1/2),\ell_1(1/2),\ell_2(1/2))=(-1/8,3/4,3/8)である。定理 1.3によりp~−p=∑i(y~i−yi)ℓi\tilde p-p=\sum_i(\tilde y_i-y_i)\ell_iであるから

∣p~(1/2)−p(1/2)∣≤∑i=02∣y~i−yi∣ ∣ℓi(1/2)∣≤δ λ2(1/2)=δ(18+34+38)=5δ4|\tilde p(1/2)-p(1/2)|\le\sum_{i=0}^2|\tilde y_i-y_i|\,|\ell_i(1/2)|\le\delta\,\lambda_2(1/2)=\delta\Bigl(\frac18+\frac34+\frac38\Bigr)=\frac{5\delta}{4}

である。y~0:=y0−δ\tilde y_0:=y_0-\delta、y~1:=y1+δ\tilde y_1:=y_1+\delta、y~2:=y2+δ\tilde y_2:=y_2+\deltaと置くと∣y~i−yi∣≤δ|\tilde y_i-y_i|\le\deltaであり、

p~(1/2)−p(1/2)=−δ(−18)+δ⋅34+δ⋅38=5δ4\tilde p(1/2)-p(1/2)=-\delta\Bigl(-\frac18\Bigr)+\delta\cdot\frac34+\delta\cdot\frac38=\frac{5\delta}{4}

である。したがって最大値は5δ/45\delta/4であり、このy~0,y~1,y~2\tilde y_0,\tilde y_1,\tilde y_2で達成される。▨

前提記事