数値積分

$${\int }_a^{b}f(x)dx\approx \sum _i{w}_{i}f(x_i)$$

積分を有限和で近似する。求積法 (quadrature)。

主な公式と誤差#

方法	誤差
台形則	$𝒪(h^2)$
Simpson 則	$𝒪(h^4)$
Gauss 求積（$n$ 点）	$2n-1$ 次多項式まで厳密

Gauss 求積は節点の位置も最適化することで、 同じ評価回数で精度を大幅に上げている。

高次元で破綻する#

$d$ 次元で各軸 $m$ 分割すると $m^d$ 点。 $d=10$、$m=100$ で ${10}^{20}$。 次元の呪いが直撃する。

モンテカルロへの切り替え#

モンテカルロ積分の誤差は $𝒪(1/\sqrt{N})$ で、次元に依存しない。

低次元では求積法が圧倒的に速いが、 $d$ が 4〜5 を超えるとモンテカルロが逆転する。 高次元の期待値計算でモンテカルロしか選択肢が無いのはこのため。

参考文献#

• William H. Press et al. Numerical Recipes, 3rd ed. Cambridge University Press, 2007. https://numerical.recipes/
• Philip J. Davis, Philip Rabinowitz. Methods of Numerical Integration, 2nd ed. Academic Press, 1984. https://doi.org/10.1016/C2013-0-10566-1