多次元の求積

初めに

MC/QMCとquad rulesの続き．何度味わっても飽きない．

Gauss-Legendreは多次元で折り畳んで重なるが，速度は如何ほどか？

Methods

Quadrature

次を計算したい．

\begin{align}
    I \left[ f (\boldsymbol{x}), D \right]
    := \int_{\boldsymbol{x} \in D}
        f (\boldsymbol{x})
    \; d\boldsymbol{x}
    &\approx \sum_{\boldsymbol{x}_i \in D}
        w_i
        f (\boldsymbol{x}_i)
\end{align}

Monte-Carlo

次をMonte-Carlo求積と呼ぶ．

\begin{align}
    I_{\text{MC}}
    &= \frac{|D|}{N} \sum_{i=1}^{N}
        f (\boldsymbol{x}_i)
    \\
    \mathbb{E} \left[ I_{\text{MC}} \right]
    &= \frac{|D|}{N} \sum_{i=1}^{N}
        \mathbb{E}_{\boldsymbol{x}_i \sim \mathcal{U} (D)} \left[
            f (\boldsymbol{x}_i)
        \right]
    \\
    &= \int_{\boldsymbol{x} \in \Omega}
        f (\boldsymbol{x})
    \; d\boldsymbol{x}
    = I
\end{align}

これは等重み求積であり，明らかにpartition of unityを満たす．$\boldsymbol{x}_i$には，所謂Monte Carloから選ばれるものと，quasi-Monte Carloから選ばれるものを採用する．

Gauss-Legendre

次をGauss-Legendre求積と呼ぶ．

\begin{align}
    I_{\text{GL}}
    &= \sum_{i=1}^{N}
        w_i
        f (\boldsymbol{x}_i)
    \\
    w_i
    &= \int_{-1}^{1} l_i (\boldsymbol{x}) \; d\boldsymbol{x}
    \\
    l_i (\boldsymbol{x})
    &= \prod_{j = 1; j \neq i}^{n} \frac{\boldsymbol{x} - \boldsymbol{x}_j}{\boldsymbol{x}_i - \boldsymbol{x}_j}
    \\
    P_n (\boldsymbol{x}_i)
    &= 0
\end{align}

これは重み付き求積であり，やはりpartition of unityを満たす．なお，$l_i$はLagrange多項式の基底，$P_n$はLegendre多項式である．

Results

2D

Test problem 1-2D

以下を考える．

\begin{align}
    \int_{[0, \pi/2]^2}
        \sin (x_1) 
        \sin (x_2) 
    \; d\boldsymbol{x}
    &= 1
\end{align}

$f$	$\epsilon$

Maclaurin展開により，

$\text{poly of order}$	$2$	$4$	$6$	$8$
-

などによって近似していることが分かる．

Test problem 2-2D

以下を考える．

\begin{align}
    \int_{[0, 1]^2}
        x_1 \log (x_1) \
        x_2 \log (x_2) 
    \; d\boldsymbol{x}
    &= \frac{1}{16}
\end{align}

$f$	$\epsilon$

やはりMaclaurin展開により，

$\text{poly of order}$	$\text{4}$	$\text{5}$	$\text{6}$	$\text{7}$
-

を以て近似している．

3D

Test problem 1-3D

\begin{align}
    \int_{[0, \pi/2]^3}
        \sin (x_1) 
        \sin (x_2) 
        \sin (x_3) 
    \; d\boldsymbol{x}
    &= 1
\end{align}

$f$	$\epsilon$

Test problem 2-3D

\begin{align}
    \int_{[0, 1]^3}
        x_1 \log (x_1) \
        x_2 \log (x_2) \
        x_3 \log (x_3) 
    \; d\boldsymbol{x}
    &= \frac{1}{64}
\end{align}

$f$	$\epsilon$

次元が大きくなると速度が落ちる．直感に一致する結果である．しかし，Gauss-LegendreはMCやQMCなど眼中に無いほどに速い．

終わりに

正直に言うと，Gauss-LegendreはGridと同様に重なってゆくから，余り期待していなかった．勿論，強力であることは認めていたし，必要以上に失望していたわけではないのだが．．．予想を遥かに上回るほどに凄まじい結果であった，ということである．

多次元程度ではGauss-Legendreの独壇場のようである．高次元ではMonte Carloにスポットライトが当たるだろうか．

$\text{ID}$	$\text{Quadrature nodes}$
$\text{Test problem 1}$
$\text{Test problem 2}$