# 和の近似 ## 定義 多くの和 $S=\sum_{i=1}^n f(i)$ には閉じた形(closed form)が存在しない(例: $\sum_{i=1}^n \sqrt i$、$\sum_{i=1}^n \ln(i)=\ln(n!)$)。積分限界法(Integral Method、定理13.3.2)は、こうした和を積分で挟み込むことで一般的な上下限を与える近似手法である。$f: \mathbb{R}^+ \to \mathbb{R}^+$ を弱増加(weakly increasing、$x<y$ ならば $f(x)\le f(y)$)関数とし、$S \coloneqq \sum_{i=1}^n f(i)$、$I \coloneqq \int_1^n f(x)\,dx$ とすると、 $I+f(1) \le S \le I+f(n)$ が成り立つ。$f$ が弱減少の場合は不等号の向きが反転し、$I+f(n) \le S \le I+f(1)$ となる。証明の骨子は図形的な議論である: $S$ は幅1・高さ $f(1),\dots,f(n)$ の $n$ 個の矩形の面積の総和であり、これを $f(x)$ のグラフの下側の面積 $I$ と比較すると、$S$ は「$I$ に一番左の矩形の面積 $f(1)$ を加えた値以上」であり(下限)、曲線を1単位左にずらして比較すると「$S$ は $I$ に一番右の矩形の面積 $f(n)$ を加えた値以下」である(上限)。この方法の誤差は最悪でも和の中の最大の項の大きさで抑えられる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.3) 積分限界法は次の3つの代表的な和に適用される。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.3〜§13.5) - $\sum_{i=1}^n \sqrt i$: $\int_1^n \sqrt x\,dx = \frac{2}{3}(n^{3/2}-1)$ を用いて $\frac{2}{3}n^{3/2}-\frac{1}{3} \le S \le \frac{2}{3}n^{3/2}+\frac{2}{3}$、すなわち和はおよそ $\frac{2}{3}n^{3/2}$ に近い。 - 調和数 $H_n=\sum_{i=1}^n \frac{1}{i}$: $\int_1^n \frac{1}{x}\,dx=\ln(n)$ を用いて $\ln(n)+\frac{1}{n} \le H_n \le \ln(n)+1$。詳細は[[調和数]]を参照。 - 階乗の対数 $\ln(n!)=\sum_{i=1}^n \ln(i)$: $\int_1^n \ln(x)\,dx = n\ln(n)-n+1$ を用いて $n\ln(n)-n+1 \le \ln(n!) \le n\ln(n)-n+1+\ln(n)$。指数を取ると $n^n/e^{n-1} \le n! \le n^{n+1}/e^{n-1}$ という、階乗が $n$ 倍の因子の範囲内で $n^n/e^{n-1}$ に近いことを示す粗い上下限が得られる(より精密なスターリングの公式は§13.5.1で証明なしに引用される)。 積分限界法は和を積分に置き換えるだけの単純な手法だが適用範囲が広く、閉じた形が存在しない和に対する第一選択の近似手法として使われる。ただし前提として $f$ が(区間全体で)弱増加または弱減少であることが必要であり、振動する関数や区分的にしか単調でない関数へは直接適用できない。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.3) ## 横断的知見 - 第13章は積分限界法によりln(n!)の上下限を導出し、より精密なStirlingの公式を証明なしに引用するにとどまるが、なぜn!という量が近似計算の対象として重要視されるのかは説明しない。第14章(Cardinality Rules)は、n要素集合の順列の数がちょうどn!であることを一般化積の規則から導き(§14.3.3)、「順列がいたるところに現れるからこそ階乗が頻出し、それゆえにStirlingの近似公式を教えた」と明言する。両章を突き合わせると、第13章が「n!をどう近似計算するか」という解析的側面を扱ったのに対し、第14章は「そもそもなぜn!という量が数学のいたるところに現れるのか」という組合せ論的な起源(順列の数え上げ)を与えており、n!という同一の量について解析的近似と組合せ論的起源が相補的に揃うことになる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.5.1, [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.3.3) ## 未解決の問い - 積分限界法は弱増加・弱減少という単調性の仮定に依存する。区分的に単調な関数や振動する関数に対する一般化・別手法は、後続章や別ソースでどう扱われるか。 - 第13章は和の閉じた形を求める別の技法として生成関数(generating function、第15章で扱われる予定)を予告している(§13.1.2)。積分限界法(近似)と生成関数(厳密な閉じた形の探索)の使い分け・組み合わせ方は、第15章の ingest 時に本節へ追記する。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] - 概念: [[漸近記法]](積分限界法で得られた上下限は漸近記法で簡潔に表現される)、[[調和数]](積分限界法の典型的な適用例)、[[数え上げ]](n!が順列の数え上げに由来することの組合せ論的説明) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 13 §13.3〜§13.5, Chapter 14 §14.3.3.