Gauss–Kronrod求積

同義語:Gauss-Kronrod求積Gauss–Kronrodの公式Gauss–Kronrod公式Gauss–Kronrod quadratureGauss-Kronrod quadratureGauss–Kronrod quadrature formula

概要

Gauss–Kronrod求積(Gauss–Kronrod quadrature)とは、$n$ 点の Gauss の公式の節点をそのまま残し、重みつきの直交条件で決まる Stieltjes 多項式の $n+1$ 個の零点を足した $2n+1$ 点の求積公式のことで、零点が実数で相異なり Gauss の節点と異なれば次数 $3n+1$ の多項式まで正確に積分し、そのような足し方はほかにない。Kronrod の節点の重みが正であることは、節点が Gauss の節点と交互に並ぶことと同値である。Gauss の公式と同じ関数の値を使い回せるので、2 つの値の差を Gauss の公式の誤差の目安にする適応型の数値積分で使われる。

$$\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}} $$

前提知識: Gauss求積, 直交多項式, 数値積分, Lagrange補間

Gauss–Kronrod求積(Gauss–Kronrod quadrature)は、$n$ 点の Gauss の公式の節点をそのまま残し、新しい節点を $n+1$ 個足して作る $2n+1$ 点の公式である。新しい節点を Stieltjes 多項式 の零点にとると、零点が実数で相異なり Gauss の節点と異なるとき、公式は次数 $3n+1$ までの多項式を正確に積分する。
Gauss求積 の $n$ 点の公式 $G_n$ は次数 $2n-1$ まで正確だが、誤差を見積もるために $G_{n+1}$ を計算しても、$G_n$ と $G_{n+1}$ の節点は重ならないので、$n+1$ 回の新しい関数の値で次数は $2$ しか上がらない。Kronrod は 1964 年に、$G_n$ の $n$ 個の値を使い回したうえで $n+1$ 個の値を足し、次数をなるべく高くする公式を作った(Not16 pp. 371–372)。実際の計算では、$G_n$ と Gauss–Kronrod の公式 $K_{2n+1}$ を同じ関数の値から同時に求め、差 $\lvert K_{2n+1}-G_n\rvert$ を $G_n$ の誤差の目安にする。
この記事では、Stieltjes 多項式がただ 1 つ存在すること(thm-gk-stieltjes)、その零点を足した公式が次数 $3n+1$ をもち、そのような公式はほかにないこと(thm-gk-main)、足す点が $n$ 個では次数が上がらないこと(prop-gk-minimum)、重みの公式(prop-gk-weights)、新しい節点の重みが正であることと節点が交互に並ぶことの同値(thm-gk-positive)を証明する。

定義と使える条件

記号は Gauss求積 にそろえる。$(a,b)$ を開区間(無限区間でもよい)、$w\colon(a,b)\to(0,\infty)$ を連続関数で、すべての $k\ge0$ で $\mu_k:=\int_a^bx^kw(x)\,dx$ が絶対収束するものとする。$I(f):=\int_a^bf(x)w(x)\,dx$、$\mathcal P_m$ を次数 $m$ 以下の実係数の多項式全体とする。$p_n$ をモニック直交多項式($\deg p_n=n$、$\mathcal P_{n-1}$ と直交)、$h_n:=I(p_n^2)>0$ とし、$p_n$ の零点(Gauss の節点)を $x_1< \dots< x_n$、Gauss の重みを $\lambda_1,\dots,\lambda_n$ とする。

Stieltjes 多項式

$n\ge1$ とする。次数 $n+1$ のモニック多項式 $E_{n+1}$ で
$$ I\bigl(p_n\,E_{n+1}\,x^k\bigr)=\int_a^bp_n(x)E_{n+1}(x)\,x^k\,w(x)\,dx=0\qquad(k=0,1,\dots,n) $$
を満たすものを、重み $w$ の Stieltjes 多項式 という。$E_{n+1}$ は、符号の変わる重み $p_n(x)w(x)$ について $\mathcal P_n$ と直交する。

Gauss–Kronrod の公式

$E_{n+1}$ が相異なる $n+1$ 個の実数の零点 $\xi_1< \dots< \xi_{n+1}$ をもち、どの $\xi_j$ も Gauss の節点でないとする。$2n+1$ 個の点 $x_1,\dots,x_n,\xi_1,\dots,\xi_{n+1}$ での補間型の公式
$$ K_{2n+1}(f):=\sum_{k=1}^n\sigma_kf(x_k)+\sum_{j=1}^{n+1}\sigma_j^*f(\xi_j) $$
(重みは、この $2n+1$ 点での Lagrange補間 の基本多項式に $w$ を掛けて積分したもの)を Gauss–Kronrod の公式 といい、$\xi_j$ を Kronrod の節点 という。

使える条件は次のとおりである。

  1. Stieltjes 多項式はいつでもただ 1 つある(thm-gk-stieltjes)。しかし、その零点が実数で相異なるとは限らない。零点が実数でない重みでは、Gauss の節点を含み節点がすべて実数の、次数 $3n+1$ の $2n+1$ 点の公式は存在しない(反例の表)。
  2. 零点が実数でも、区間 $(a,b)$ の中にあるとは限らない。区間の外の点では被積分関数の値が定義されないことがある(反例の表)。
  3. 重みが正かどうか は、Kronrod の節点の重みについては、節点が Gauss の節点と交互に並ぶことと同値である(thm-gk-positive)。
  4. $w=1$、$(a,b)=(-1,1)$(Legendre の重み)では、1〜3 はすべての $n$ で成り立つ(thm-gk-legendre。この記事では証明しない)。

公式の表

量式・値条件根拠
Stieltjes 多項式$I(p_nE_{n+1}x^k)=0$($0\le k\le n$)で一意なしthm-gk-stieltjes
次数$3n+1$ 以上$E_{n+1}$ の零点が実数で相異なり、Gauss の節点と異なるthm-gk-main
次数(対称な重み)$n$ が奇数なら $3n+2$ 以上$w$ が偶関数、区間が対称thm-gk-main
Kronrod の節点の重み$\sigma_j^*=\dfrac{h_n}{p_n(\xi_j)\,E_{n+1}'(\xi_j)}$同上prop-gk-weights
Gauss の節点の重み$\sigma_k=\lambda_k+\dfrac{h_n}{p_n'(x_k)\,E_{n+1}(x_k)}$同上prop-gk-weights
$\sigma_j^*>0$(すべての $j$)節点が交互に並ぶことと同値同上thm-gk-positive
足す点の個数$n$ 個以下では次数は $2n-1$ を超えないなしprop-gk-minimum

Legendre の重み($w=1$、$(-1,1)$)の小さい $n$ の値は次のとおりである。$p_1=x$、$p_2=x^2-\frac13$、$p_3=x^3-\frac35x$ である。

$n$$E_{n+1}$Kronrod の節点重み次数
$1$$x^2-\frac35$$\pm\sqrt{3/5}$$0$:$\frac89$;$\pm\sqrt{3/5}$:$\frac59$$5$
$2$$x^3-\frac67x$$0$、$\pm\sqrt{6/7}\approx\pm0.9258200998$$0$:$\frac{28}{45}$;$\pm\frac1{\sqrt3}$:$\frac{27}{55}$;$\pm\sqrt{6/7}$:$\frac{98}{495}$$7$
$3$$x^4-\frac{10}9x^2+\frac{155}{891}$$\pm0.4342437493$、$\pm0.9604912687$$0$:$0.4509165387$;$\pm\sqrt{3/5}$:$0.2684880899$;$\pm0.434\ldots$:$0.4013974148$;$\pm0.960\ldots$:$0.1046562260$$11$

$n=1$ の $K_3$ は 3 点の Gauss の公式そのものである。実際の計算でよく使う $n=7$ の 15 点の公式(Gauss の 7 点と Kronrod の 8 点)の正の側の節点と重みは次のとおりである($0$ は Gauss の節点で重み $0.2094821411$)。

節点種類重み
$0.2077849550$Kronrod$0.2044329401$
$0.4058451514$Gauss$0.1903505781$
$0.5860872355$Kronrod$0.1690047266$
$0.7415311856$Gauss$0.1406532597$
$0.8648644234$Kronrod$0.1047900103$
$0.9491079123$Gauss$0.0630920926$
$0.9914553711$Kronrod$0.0229353220$

この 15 点の公式の次数は $23$ である。Gauss の重みは $n$ 点の Gauss の公式の重み $\lambda_k$ と違うことに注意する。$G_7$ を計算するときは $\lambda_k$ を使う。

主定理と証明

Stieltjes 多項式の存在と一意性

Stieltjes 多項式の存在と一意性

$n\ge1$ について、def-gk-stieltjes の条件を満たす $E_{n+1}$ はただ 1 つ存在する。さらに、区間が対称($a=-b$)で $w$ が偶関数なら、$E_{n+1}(-x)=(-1)^{n+1}E_{n+1}(x)$ である。

係数の連立 1 次方程式が三角形になる

$m_s:=I(p_nx^s)$($s\ge0$)とおく。$p_n$ は $\mathcal P_{n-1}$ と直交するので $s\le n-1$ で $m_s=0$ である。$x^n=p_n+(\mathcal P_{n-1}\text{ の元})$ なので $m_n=I(p_n^2)=h_n>0$ である。
$E=x^{n+1}+\sum_{j=0}^nc_jx^j$ とおくと、条件は
$$ \sum_{j=0}^nm_{j+k}\,c_j=-m_{n+1+k}\qquad(k=0,1,\dots,n) $$
という $c_0,\dots,c_n$ の連立 1 次方程式である。未知数を $c_n,c_{n-1},\dots,c_0$ の順に並べ直すと、係数行列の $(k,i)$ 成分($i=n-j$)は $m_{n-i+k}$ で、$k< i$ なら $n-i+k\le n-1$ なので $0$、$k=i$ なら $m_n=h_n$ である。係数行列は対角成分がすべて $h_n\ne0$ の下三角行列なので正則であり、解はただ 1 つある。
対称性:$w$ が偶関数なら、$(-1)^np_n(-x)$ もモニックで $\mathcal P_{n-1}$ と直交するので、モニック直交多項式の一意性から $p_n(-x)=(-1)^np_n(x)$ である。$\tilde E(x):=(-1)^{n+1}E_{n+1}(-x)$ はモニックで、$x\mapsto-x$ と置換すると
$$ I(p_n\tilde Ex^k)=(-1)^{n+1}\int_a^bp_n(-x)E_{n+1}(x)(-x)^kw(x)\,dx=(-1)^{n+1+n+k}I(p_nE_{n+1}x^k)=0 $$
である。一意性から $\tilde E=E_{n+1}$ である。$\square$

次数 $3n+1$ と一意性

Gauss–Kronrod の公式の次数と一意性

$n\ge1$ とする。

  1. $E_{n+1}$ が相異なる実数の零点 $\xi_1,\dots,\xi_{n+1}$ をもち、どれも Gauss の節点でないなら、$K_{2n+1}$ は $\mathcal P_{3n+1}$ の上で正確である。
  2. 逆に、Gauss の節点と異なる相異なる実数 $y_1,\dots,y_{n+1}$ と実数 $c_k,d_j$ について、$\sum_kc_kg(x_k)+\sum_jd_jg(y_j)=I(g)$ がすべての $g\in\mathcal P_{3n+1}$ で成り立つなら、$\{y_j\}$ は $E_{n+1}$ の零点の全体である。
  3. 1 の仮定のもとで、区間が対称で $w$ が偶関数、$n$ が奇数なら、$K_{2n+1}$ は $\mathcal P_{3n+2}$ の上で正確である。
$p_nE_{n+1}$ で割る
  1. $\Omega:=p_nE_{n+1}$ は次数 $2n+1$ で、$2n+1$ 個の節点のすべてで $0$ になる。$g\in\mathcal P_{3n+1}$ を $\Omega$ で割り、$g=\Omega q+r$($q\in\mathcal P_n$、$r\in\mathcal P_{2n}$)とする。$q$ は $x^0,\dots,x^n$ の 1 次結合なので、def-gk-stieltjes により $I(\Omega q)=0$、よって $I(g)=I(r)$ である。節点では $g=r$ である。$K_{2n+1}$ は $2n+1$ 点の補間型の公式なので $\mathcal P_{2n}$ の上で正確であり、$K_{2n+1}(g)=K_{2n+1}(r)=I(r)=I(g)$ である。
  2. $\omega(x):=\prod_j(x-y_j)$ とおく。$q\in\mathcal P_n$ について $p_n\omega q\in\mathcal P_{3n+1}$ はすべての節点で $0$ なので、仮定から $I(p_n\omega q)=0$ である。$\omega$ はモニックで次数 $n+1$ なので def-gk-stieltjes の条件を満たし、thm-gk-stieltjes の一意性から $\omega=E_{n+1}$ である。
  3. thm-gk-stieltjes により $p_n$ と $E_{n+1}$ は偶関数か奇関数なので、節点の集合は $x\mapsto-x$ で保たれる。反転した公式 $f\mapsto K_{2n+1}(f(-\,\cdot\,))$ は同じ節点の集合の上の公式で、$g\in\mathcal P_{2n}$ なら $g(-\,\cdot\,)\in\mathcal P_{2n}$ と $w$ が偶関数であることから $K_{2n+1}(g(-\,\cdot\,))=I(g(-\,\cdot\,))=I(g)$ なので、$\mathcal P_{2n}$ で正確である。$2n+1$ 点で $\mathcal P_{2n}$ の上で正確な公式の重みは基本多項式を代入して決まるので、点 $t$ と $-t$ の重みは等しい。よって奇関数 $g$ では $K_{2n+1}(g)=0=I(g)$ である。$n$ が奇数なら $3n+2$ は奇数なので、$x^{3n+2}$ でも正確であり、(1) と合わせて $\mathcal P_{3n+2}$ で正確である。$\square$
  1. は、Gauss の節点に $n+1$ 点を足して次数 $3n+1$ を得る方法が Stieltjes 多項式の零点しかないことを述べている。足す点を減らすことはできない。
足す点が $n$ 個以下では次数は上がらない

$0\le m\le n$ とし、Gauss の節点に相異なる実数 $y_1,\dots,y_m$ を足した $n+m$ 点の公式(重みは任意の実数)を考える。この公式の次数は $2n-1$ を超えない。

節点で消える次数 $2n$ の多項式

$\omega(x):=\prod_{j=1}^m(x-y_j)$ とおき、$g:=p_n\,\omega\,x^{n-m}$ とする。$g$ は次数 $2n$ で、すべての節点で $0$ なので、公式の値は $0$ である。一方 $\omega x^{n-m}$ はモニックで次数 $n$ なので $\omega x^{n-m}=p_n+(\mathcal P_{n-1}\text{ の元})$ と書け、$I(g)=I(p_n^2)=h_n>0$ である。よって公式は $g\in\mathcal P_{2n}$ で正確でない。$\square$

重みと正値性

重みの公式

thm-gk-main の 1 の仮定のもとで
$$ \sigma_j^*=\frac{h_n}{p_n(\xi_j)\,E_{n+1}'(\xi_j)},\qquad\sigma_k=\lambda_k+\frac{h_n}{p_n'(x_k)\,E_{n+1}(x_k)} $$
である。

基本多項式を分けて積分する

$\Omega=p_nE_{n+1}$ とすると、節点 $t$ の基本多項式は $L_t(x)=\dfrac{\Omega(x)}{(x-t)\,\Omega'(t)}$ で、重みは $I(L_t)$ である。
Kronrod の節点 $t=\xi_j$ では $\Omega'(\xi_j)=p_n(\xi_j)E_{n+1}'(\xi_j)$ で、$s(x):=E_{n+1}(x)/(x-\xi_j)$ はモニックで次数 $n$ なので、$s=p_n+(\mathcal P_{n-1}\text{ の元})$ から $I(p_ns)=h_n$ である。よって $\sigma_j^*=h_n/(p_n(\xi_j)E_{n+1}'(\xi_j))$ である。
Gauss の節点 $t=x_k$ では $\Omega'(x_k)=p_n'(x_k)E_{n+1}(x_k)$ である。$p_n(x)/(x-x_k)=p_n'(x_k)\ell_k(x)$($\ell_k$ は Gauss の節点の基本多項式)なので $L_{x_k}=\ell_kE_{n+1}/E_{n+1}(x_k)$ である。$E_{n+1}(x)=E_{n+1}(x_k)+(x-x_k)t(x)$($t$ はモニックで次数 $n$)と割ると
$$ \ell_kE_{n+1}=E_{n+1}(x_k)\,\ell_k+\frac{p_n\,t}{p_n'(x_k)} $$
で、積分すると $I(\ell_kE_{n+1})=E_{n+1}(x_k)\lambda_k+h_n/p_n'(x_k)$ である。$E_{n+1}(x_k)$ で割って主張を得る。$\square$

正の重みと交互に並ぶ節点

thm-gk-main の 1 の仮定のもとで、次は同値である。

  1. すべての $j$ で $\sigma_j^*>0$。
  2. 節点が交互に並ぶ:$\xi_1< x_1< \xi_2< x_2< \dots< x_n< \xi_{n+1}$。
零点の数で符号を数える

$E_{n+1}$ はモニックで単純な零点をもつので、$\xi_j$ より大きい零点の個数 $n+1-j$ により $E_{n+1}'(\xi_j)$ の符号は $(-1)^{n+1-j}$ である。prop-gk-weights と $h_n>0$ から、1 は「すべての $j$ で $p_n(\xi_j)$ の符号が $(-1)^{n+1-j}$」と同値である。
2 ⇒ 1:2 のもとで $\xi_j$ より大きい Gauss の節点は $x_j,\dots,x_n$ の $n+1-j$ 個で、$p_n$ はモニックなので $p_n(\xi_j)$ の符号は $(-1)^{n+1-j}$ である。
1 ⇒ 2:$p_n(\xi_j)$ と $p_n(\xi_{j+1})$ の符号は逆なので、中間値の定理 により $p_n$ は $n$ 個の開区間 $(\xi_j,\xi_{j+1})$($j=1,\dots,n$)のそれぞれに零点をもつ。$p_n$ の零点はちょうど $n$ 個なので、各区間にちょうど 1 つずつあり、これが 2 である。$\square$

Gauss の節点の重み $\sigma_k$ は、交互に並んでいても $\lambda_k$ より小さい:2 のもとで $p_n'(x_k)$ の符号は $(-1)^{n-k}$、$E_{n+1}(x_k)$ の符号は $(-1)^{n+1-k}$ なので、補正の項 $h_n/(p_n'(x_k)E_{n+1}(x_k))$ は負である。$\sigma_k>0$ は別に確かめる必要がある。

Legendre の重みの場合

$w=1$、$(a,b)=(-1,1)$ とする。すべての $n\ge1$ で、$E_{n+1}$ の零点は相異なる実数で $(-1,1)$ の中にあり、Gauss の節点と交互に並ぶ。すべての重み $\sigma_k$、$\sigma_j^*$ は正である。公式の次数はちょうど、$n$ が偶数なら $3n+1$、奇数なら $3n+2$ である。

出典

この記事では証明しない。零点の位置と交互の並びは Szegő(1935)、重みが正であることは Monegato(1978)、次数がちょうどこの値であることは Rabinowitz による(Not16 §2.1.1、pp. 374–375)。次数の下界は thm-gk-main の 1・3 から従う。

重みがすべて正で節点がすべて区間に入るなら、Gauss の公式と同じ議論で、連続関数の積分に収束する公式の列になる。

正の重みのときの誤差の評価

$(a,b)$ が有界で、$K_{2n+1}$ の節点がすべて $[a,b]$ にあり重みがすべて正なら、$f\in C[a,b]$ と $g\in\mathcal P_{3n+1}$ について
$$ \lvert I(f)-K_{2n+1}(f)\rvert\le2\mu_0\sup_{[a,b]}\lvert f-g\rvert $$
である。とくに Legendre の重みでは、$n\to\infty$ で $K_{2n+1}(f)\to I(f)$ である。

多項式との差で抑える

$K_{2n+1}$ は定数で正確なので重みの和は $\mu_0$ である。$I(g)=K_{2n+1}(g)$ から $I(f)-K_{2n+1}(f)=I(f-g)-K_{2n+1}(f-g)$ で、各項の絶対値は $\mu_0\sup\lvert f-g\rvert$ 以下である。後半は thm-gk-legendre と Weierstrassの近似定理 による。$\square$

計算の手順

区間 $[c,d]$ の積分 $\int_c^df(x)\,dx$ を Legendre の重みの $G_7$ と $K_{15}$ で計算する手順は次のとおりである。

  1. $x=\frac{c+d}2+\frac{d-c}2t$ と置換し、15 個の節点 $t$(公式の表)で $f$ を評価する。
  2. 7 個の Gauss の節点の値と Gauss の重み $\lambda_k$ から $G_7$ を、15 個すべての値と $\sigma_k,\sigma_j^*$ から $K_{15}$ を求め、どちらにも $\frac{d-c}2$ を掛ける。関数の評価は 15 回で済む。
  3. $\lvert K_{15}-G_7\rvert$ を $G_7$ の誤差の目安とする。答えには、ふつう精度の高い $K_{15}$ を使う。
  4. 目安が許容値より大きければ、区間を 2 つに分けて各半分で 1〜3 を繰り返し、結果を足す(適応型の積分)。分けた区間では節点が変わるので、値は使い回せない。
  5. 重み $w$ がほかの関数のときは、小さい $n$ なら thm-gk-stieltjes の連立方程式を解いて $E_{n+1}$ を求め、零点を thm-gk-positive の条件と区間に入るかで確かめてから prop-gk-weights で重みを計算する。$n$ が大きいと連立方程式は条件が悪いので、Laurie の固有値問題による算法(Not16 §4.2、p. 387)を使う。
    手順 3 の目安は保証ではない。$\lvert K-G\rvert$ が小さくても、両方が同じように間違えることがある(ex-gk-fooled)。$f$ の高い階の導関数の上界が分かるなら、Gauss求積 の定理「Gauss の公式の誤差」で $G_n$ の誤差に保証を付けられる。

例題

$n=2$ の公式を作る

$w=1$、$(-1,1)$、$p_2=x^2-\frac13$ とする。thm-gk-stieltjes の対称性から $E_3=x^3+cx$ で、条件のうち $k=0,2$ は被積分関数が奇関数なので自動的に成り立つ。$k=1$ の条件は
$$ \int_{-1}^1\Bigl(x^2-\frac13\Bigr)(x^4+cx^2)\,dx=\frac{16}{105}+\frac{8}{45}c=0 $$
で、$c=-\frac67$ である。零点 $0,\pm\sqrt{6/7}$ は Gauss の節点 $\pm\frac1{\sqrt3}\approx\pm0.577$ と交互に並ぶ。
答え:$h_2=\frac8{45}$ と prop-gk-weights から、重みは $\sigma^*(0)=\frac{8/45}{(-1/3)(-6/7)}=\frac{28}{45}$、$\sigma^*(\pm\sqrt{6/7})=\frac{8/45}{(11/21)(12/7)}=\frac{98}{495}$、$\sigma(\pm\frac1{\sqrt3})=1+\frac{8/45}{(2/\sqrt3)\cdot(-11/(21\sqrt3))}=\frac{27}{55}$ である。和は $\frac{28}{45}+\frac{196}{495}+\frac{54}{55}=2$ で、公式の次数は $7$ である($x^8$ では正確でない)。

$\int_0^1e^{-x^2}dx$ での誤差の目安

真の値は $I=0.7468241328124\ldots$ である。$[0,1]$ に変換した Legendre の重みの公式を当てる。
答え:

$n$$I-G_n$$I-K_{2n+1}$$\lvert K_{2n+1}-G_n\rvert$
$2$$2.294\times10^{-4}$$1.102\times10^{-7}$$2.293\times10^{-4}$
$3$$9.549\times10^{-6}$$3.023\times10^{-11}$$9.549\times10^{-6}$
$7$$7.887\times10^{-13}$$2.6\times10^{-25}$$7.887\times10^{-13}$

$\lvert K-G\rvert$ は $G_n$ の誤差をほぼ正確に表し、$K_{2n+1}$ の誤差はそれよりはるかに小さい。$n=7$ では $K_{15}$ の誤差は倍精度の丸めの単位(約 $1.1\times10^{-16}$)より小さく、実際の計算では丸めの誤差が支配する。$n=1$ の $K_3$ は 3 点の Gauss の公式なので、$K_3$ と $G_3$ の値は等しい($I-K_3=9.549\times10^{-6}$)。

Chebyshev の重みでは公式が閉じた形になる

$w=(1-x^2)^{-1/2}$、$(-1,1)$、$n\ge2$ とする。Chebyshev多項式 $T_m$ と第 2 種の $U_m$ で、$E_{n+1}=2^{1-n}(x^2-1)U_{n-1}$ であり、$2n+1$ 個の節点は $\cos\frac{m\pi}{2n}$($m=0,1,\dots,2n$)、重みは両端が $\frac\pi{4n}$、ほかが $\frac\pi{2n}$ で、公式の次数はちょうど $4n-1$ である。Kronrod の節点のうち $\pm1$ は区間の端にある。

確かめを開く

$x=\cos\theta$ とすると $T_{n+1}-T_{n-1}=\cos(n+1)\theta-\cos(n-1)\theta=-2\sin n\theta\sin\theta=2(x^2-1)U_{n-1}(x)$ である($U_{n-1}(\cos\theta)=\sin n\theta/\sin\theta$)。$p_n=2^{1-n}T_n$ で、積和の公式から $T_n(T_{n+1}-T_{n-1})=\frac12(T_{2n+1}-T_{2n-1})$ である。$n\ge2$ なら $k\le n\le2n-2$ なので、$x^k$ は $T_{2n\pm1}$ と直交し、条件が成り立つ。最高次の係数をそろえると $E_{n+1}=2^{-n}(T_{n+1}-T_{n-1})$ である。零点は $\pm1$ と $U_{n-1}$ の零点 $\cos\frac{j\pi}n$ で、Gauss の節点 $\cos\frac{(2k-1)\pi}{2n}$ と合わせると $\cos\frac{m\pi}{2n}$ になる。

$N:=2n$ とし、端の項を半分にした和を $\sum''$ と書く。$\cos\frac{(2N-m)k\pi}N=\cos\frac{mk\pi}N$ なので $\sum''_{m=0}^N\cos\frac{mk\pi}N=\frac12\sum_{m=0}^{2N-1}\cos\frac{mk\pi}N$ で、等比数列の和からこれは $2N\mid k$ のとき $N$、ほかは $0$ である。よって公式 $Q(f):=\frac\pi N\sum''_mf(\cos\frac{m\pi}N)$ は $Q(T_k)=\pi$($2N\mid k$)、$0$(ほか)を与える。$I(T_k)=\pi$($k=0$)、$0$($k\ge1$)なので、$Q$ は $0\le k\le2N-1=4n-1$ で正確、$k=4n$ で正確でない。$Q$ は $\mathcal P_{2n}$ で正確な $2n+1$ 点の公式なので補間型の公式 $K_{2n+1}$ に等しい。

誤差の目安がだまされる例

$w=1$、$(-1,1)$、$n=2$ とし、$f:=(p_2E_3)^2=\bigl((x^2-\tfrac13)(x^3-\tfrac67x)\bigr)^2$ とする。
答え:$f$ は 5 個の節点のすべてで $0$ なので $G_2(f)=K_5(f)=0$、$\lvert K_5-G_2\rvert=0$ だが、$I(f)=\frac{328}{101871}\approx3.220\times10^{-3}$ である。$f$ は次数 $10$ の多項式で、$K_5$ の次数 $7$ を超えている。

使える条件と反例

各行は 1 つの仮定だけを外す。

外した仮定反例成り立たなくなる結論
$E_{n+1}$ の零点が実数で相異なる(thm-gk-main の 1)$w=e^{-x^2}$、$(-\infty,\infty)$、$n=3$7 点の実数の節点で、Gauss の 3 点を含み次数 $10$ の公式が存在しない
Legendre の重み(thm-gk-legendre の「零点は区間の中」)$w=e^{-x}$、$(0,\infty)$、$n=1$Kronrod の節点 $2-\sqrt6\approx-0.449$ が区間 $(0,\infty)$ の外にある
足す点が $n+1$ 個(thm-gk-main の 1)$w=1$、$(-1,1)$、$n=2$、足す点を $0,\frac12$ の 2 個にする$\mathcal P_{3n+1}=\mathcal P_7$ の上で正確でない:$g=p_2\,x(x-\frac12)$ で公式の値 $0$、積分 $\frac8{45}$
表の確かめ

1 行目:$\int x^{2m}e^{-x^2}dx=\Gamma(m+\frac12)$ から $p_3=x^3-\frac32x$ である。thm-gk-stieltjes の対称性から $E_4=x^4+c_2x^2+c_0$ で、$k=1,3$ の条件は $\frac{\sqrt\pi}4(15+3c_2)=0$、$\frac{\sqrt\pi}{16}(315+60c_2+12c_0)=0$ になり、$E_4=x^4-5x^2-\frac54$ である。$x^2=\frac{5\pm\sqrt{30}}2$ のうち $\frac{5-\sqrt{30}}2< 0$ なので、零点のうち 2 つ $\pm0.4885i$ は実数でない。そのような公式があれば、thm-gk-main の 2 により足した 4 点は $E_4$ の零点の全体になり、実数であることに反する。
2 行目:$\int x^ke^{-x}dx=k!$ から $p_1=x-1$ で、$E_2=x^2+c_1x+c_0$ の条件は $4+c_1=0$、$18-16+c_0=0$ なので $E_2=x^2-4x-2$、零点は $2\pm\sqrt6$ である。零点は実数で相異なり、Gauss の節点 $1$ と交互に並ぶので、thm-gk-main の 1 と thm-gk-positive は成り立つ(重みは $\frac45$、$\frac1{10}\pm\frac{\sqrt6}{60}$ で正、次数は $4$)。しかし節点 $2-\sqrt6$ は区間の外にあり、たとえば $f(x)=\sqrt x$ では公式の値が定義されない。
3 行目は prop-gk-minimum の証明の $g$ そのものである:$g$ は 4 個の節点 $\pm\frac1{\sqrt3},0,\frac12$ のすべてで $0$、次数は $4\le7$、$I(g)=I(p_2^2)=h_2=\frac8{45}$ である。

よくある誤り

誤り正しくはなぜ
$K_{2n+1}$ の Gauss の節点に Gauss の重み $\lambda_k$ を使う重みは $\sigma_k=\lambda_k+h_n/(p_n'(x_k)E_{n+1}(x_k))$prop-gk-weights
$2n+1$ 点なので次数は $4n+1$Gauss の節点を固定したので次数は $3n+1$(対称な重みで $n$ 奇数なら $3n+2$)thm-gk-main、prop-gk-minimum
$\lvert K-G\rvert$ を $K$ の誤差とみなす$\lvert K-G\rvert$ は $G_n$ の誤差の目安で、$K$ はふつうずっと正確ex-gk-gaussian
$\lvert K-G\rvert$ が小さければ答えは正しい両方が同じ節点で同じように誤ることがあるex-gk-fooled
どの重みでも Gauss–Kronrod の公式がある実数の零点をもたない重みがある反例の表の 1 行目

補足

名前の由来と文献

$E_{n+1}$ は、Stieltjes が 1894 年に Hermite への手紙で Legendre の場合に考え、零点が実数で $(-1,1)$ にあり Gauss の節点と交互に並ぶと予想した多項式で、Szegő が 1935 年に予想を証明した。Kronrod は 1964 年に、求積の公式としてこの零点を独立に得た(Not16 pp. 371–372)。重みが正であることと交互の並びの同値は Monegato による(Not16 p. 373)。$n$ 点の Gauss の公式からの拡張を繰り返す方法や、Gauss–Kronrod の公式の誤差の評価、数表と計算の算法も Not16 にまとめられている。

Gauss求積 の公式は節点の位置まで最適に選ぶ。Gauss–Kronrod の公式は、Gauss の節点を固定するという制約のもとで、残りの $n+1$ 点を最適に選ぶものである。固定した点の分だけ自由度が減るので、$2n+1$ 点の Gauss の公式の次数 $4n+1$ には届かない。端点を固定した Gauss–Lobatto 公式(Gauss求積 の注意「端点を含む公式」)と同じ考え方である。

関連項目

参考文献

[1]
Sotirios E. Notaris, Gauss–Kronrod quadrature formulae — a survey of fifty years of research, Electronic Transactions on Numerical Analysis, 2016, §1(pp. 371–372)、§2(p. 373、式 (2.2)–(2.4))、§2.1.1(pp. 374–375)、§2.1.3(pp. 376–377)、§4.2(p. 387)

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