ランダウ記号と漸近展開 - 世界銀行で働くデータサイエンティストのブログ

微分積分の教科書やプログラミングの計算量の文脈でたまに出てくるランダウの記号o()と，それを用いた漸近展開について勉強したのでメモ。

ランダウ記号って何

2つの関数 $f(x)$ ， $g(x)$ がある点 $x=a$ に収束するスピードはどっちが速いか，を表現できる方法がランダウ記号である。厳密な定義は以下。

ランダウ記号 $o()$ 関数 $f(x)$ ， $g(x)$ が $x=a$ の近傍で定義されており $\displaystyle\lim_{x \rightarrow a}\frac{f(x)}{g(x)}=0$ の時， $f(x)=o{(g(x))} \ \ (x \rightarrow a)$ と表す。

記号の解釈として以下のような表現がされる。

$x=a$ の近傍において， $f(x)$ は $g(x)$ より遥かに小さい
$x=a$ の近傍において， $f(x)$ は $g(x)$ に対して無視できる無限小である
$x=a$ の近傍において， $f(x)$ は $g(x)$ より高位(higher order)の無限小である

例

$\displaystyle\lim_{x \rightarrow 0}\frac{x ^ 3}{x}=0$ なので， $x ^3 = o(x) \ \ (x \rightarrow 0)$
$\alpha>0$ のとき $\displaystyle\lim_{x \rightarrow \infty}\frac{\log{x}}{x ^\alpha}=0$ なので， $\log{x} = o(x ^\alpha) \ \ (x \rightarrow \infty)$

漸近展開

このランダウ記号を用いれば，テイラー展開を書き換えて漸近展開を表現できる。

漸近展開 $f(x)$ が $a$ を含む開区間で定義されていて $C ^n$ 級の関数である時，次のように表せる。

$f(x) = \displaystyle \sum_{k=0}^{n}\frac{1}{k!}f^{(k)}(a)(x-a) ^k+o( (x-a) ^n) \ \ \ (x \rightarrow a)$

(証明)

$\theta \ (0\lt\theta\lt 1)$ を $x$ に依存する実数とし， $x=a$ における有限テイラー展開を表すと，

$f(x) = \displaystyle \sum_{k=0}^{n-1}\frac{1}{k!}f^{(k)}(a)(x-a)^k+\frac{1}{n!}f^{(n)}(a+\theta(x-a))(x-a)^n \\ ここで \ \ g(x) = \frac{1}{n!}f^{(n)}(a+\theta(x-a))(x-a)^n-\frac{1}{n!}f^{(n)}(a))(x-a)^n \ と置き，f(x)に代入すると\\ f(x) = \displaystyle \sum_{k=0}^{n-1}\frac{1}{k!}f^{(k)}(a)(x-a)^k+\frac{1}{n!}f^{(n)}(a))(x-a)^n+ g(x) \\ f(x) = \displaystyle \sum_{k=0}^{n}\frac{1}{k!}f^{(k)}(a)(x-a)^k+ g(x) \\$

ここで $\ \ g(x) = o( (x-a) ^n) \ \ \ (x \rightarrow a)$ を示せれば目的の漸近展開を表現できる。

$\displaystyle\lim_{x \rightarrow a}\frac{g(x)}{(x-a) ^n} = \displaystyle\lim_{x \rightarrow a}\frac{ \frac{1}{n!}f^{(n)}(a+\theta(x-a))(x-a)^n-\frac{1}{n!}f^{(n)}(a)(x-a)^n}{(x-a) ^n}$

分母分子を $(x-a) ^n$ で割って， $1/n!$ で括って

$\displaystyle\lim_{x \rightarrow a}\frac{g(x)}{(x-a) ^n} = \displaystyle\lim_{x \rightarrow a} \frac{1}{n!}(f^{(n)}(a+\theta(x-a))-f^{(n)}(a)) = 0$

よって，ランダウ記号の定義式から $\ \ g(x) = o( (x-a) ^n) \ \ \ (x \rightarrow a)$ を示せた。したがって

$f(x) = \displaystyle \sum_{k=0}^{n}\frac{1}{k!}f^{(k)}(a)(x-a) ^k+o( (x-a) ^n) \ \ \ (x \rightarrow a)$

と表せる。

ランダウ記号を使えばこんな綺麗に表現できる!!!! 美しい!!!!

漸近展開の利用

$f(x)=(1 + x ^2)e ^x$ の $x=0$ における4次の漸近展開を求めたい。愚直に1項ずつ計算してもよいが，ランダウ記号の特性を活かして計算する。 $f(x)=e ^x + x ^2e ^x$ として， $e ^x$ と $x ^2e ^x$ の $x \rightarrow 0$ の4次の漸近展開をそれぞれ用意し足し合わせる。

$n=4で，e^x=1+x+\frac{1}{2}x ^2+\frac{1}{6}x ^3 + \frac{1}{24}x ^4 + o(x ^4) \ \ \ \ \ \ \cdots (i) \\ n=2で，e^x=1+x+\frac{1}{2}x ^2 + o(x ^2) \ \ \ \ \ \ \cdots (ii) \\$

式 $(ii)$ の両辺に $x ^2$ をかけて

$x ^2e^x=x ^2+x ^3+\frac{1}{2}x ^4 + x ^2o(x ^2) \\ 補題より \ \ x ^2 o(x ^2) = o(x ^4)を利用して \\ x ^2e^x=x ^2+x ^3+\frac{1}{2}x ^4 + o(x ^4) \ \ \ \ \ \ \cdots (iii)$

式 $(i)+(iii)$ より

$f(x) = e ^x + x ^2e ^x = 1 + x + \frac{3}{2}x ^2 + \frac{7}{6}x ^3 + \frac{13}{24}x ^4 + o(x ^4) \ \ \ (x \rightarrow 0)$

ランダウ記号の補題を証明

補題1: $x \rightarrow 0$ のとき $x^ m \cdot o(x^ n)=o(x^ {m+n})$

(証明)

$f(x) =x^ m \cdot o(x^ n)$ ， $g(x) = x^ {m+n}$ とおき， $\displaystyle\lim_{x \rightarrow 0}\frac{f(x)}{g(x)}$ を考える。

$\displaystyle\lim _ {x \rightarrow 0}\frac{f(x)}{g(x)} = \lim _ {x \rightarrow 0}\frac{x^ m \cdot o(x^ n)}{x^ {m+n}} =\lim _ {x \rightarrow 0}\frac{x^ m \cdot o(x^ n)}{x^ mx^ n} =\lim _ {x \rightarrow 0}\frac{o(x^ n)}{x^ n} =0$

よって，ランダウの記号の定義式が適用できて， $f(x)=o{(g(x))}$ と表わせ， $x^ m \cdot o(x^ n)=o(x^ {m+n})$ となる。

補題2: $x \rightarrow 0$ のとき $o(x ^m) \cdot o(x^ n)=o(x^ {m+n})$

(証明)

$f(x) =o(x ^m) \cdot o(x^ n)$ ， $g(x) = x^ {m+n}$ とおき， $\displaystyle\lim_{x \rightarrow 0}\frac{f(x)}{g(x)}$ を考える。

$\displaystyle\lim _ {x \rightarrow 0}\frac{f(x)}{g(x)} = \lim _ {x \rightarrow 0}\frac{o(x ^m) \cdot o(x^ n)}{x^ {m+n}} =\lim _ {x \rightarrow 0}\frac{o(x^ m)}{x^ m}\cdot \frac{o(x^ n)}{x^ n} =\lim _ {x \rightarrow 0}\frac{o(x^ m)}{x^ m}\cdot\lim _ {x \rightarrow 0} \frac{o(x^ n)}{x^ n} =0$

よって，ランダウの記号の定義式が適用できて， $f(x)=o{(g(x))}$ と表わせ， $o(x ^m) \cdot o(x^ n)=o(x^ {m+n})$ となる。

補題3: $m \leq n$ のとき， $x \rightarrow 0$ で $o(x ^m) + o(x^ n)=o(x ^m)$

(証明)

$f(x) =o(x ^m) + o(x^ n)$ ， $g(x) = x ^m$ とおき， $\displaystyle\lim_{x \rightarrow 0}\frac{f(x)}{g(x)}$ を考える。

$\displaystyle\lim _ {x \rightarrow 0}\frac{f(x)}{g(x)} = \lim _ {x \rightarrow 0}\frac{o(x ^m) + o(x^ n)}{x ^m} =\lim _ {x \rightarrow 0}\frac{o(x^ m)}{x^ m} + x^{n-m}\frac{o(x^ n)}{x^ n} =0$