ランダウの記号 - ﾕﾕﾕﾕﾕ

計算量の上界を見るときにビッグオー記法などとよく引き合いに出される、例のランダウの記号というやつについて、解析学のテキストで触れられているものを読んだ。「他の定理はともかくとしてこれなら知っているぞ」といわんばかりの思いで臨んだが、数学的定義のちんぷんかんぷんさに打ちのめされた。とはいえひとまずテキストの内容は理解できたと信じて、この定義を忘れないようにしたいとメモを書いておく。

収束速度の表現

$x \to a$ のとき $0$ に収束するふたつの関数を考える。 $a = 0$ として $x \to 0$ と考えてもよい。

$\displaystyle \lim_{x \to a}{\varphi(x)} = 0$

$\displaystyle \lim_{x \to a}{\psi(x)} = 0$

$\sim$ 記号

$\displaystyle \varphi(x) \sim \psi(x)$ と書いて $\displaystyle \lim_{x \to a}{\frac{\varphi(x)}{\psi(x)}} = 1$ を意味する。

$\displaystyle \varphi(x)$ と $\displaystyle \psi(x)$ が同じ速さで $0$ に収束するということ。

$o$ （スモールオー）記号

$\displaystyle \varphi(x) = o(\psi(x))$ と書いて $\displaystyle \lim_{x \to a}{\frac{\varphi(x)}{\psi(x)}} = 0$ を意味する。

$\displaystyle \varphi(x)$ が $\displaystyle \psi(x)$ よりも速く $0$ にいくということで、このとき $\varphi(x)$ は $\psi(x)$ より 高位の無限小 という。

$O$ （ビッグオー）記号

正の数 $K$ があって

$\displaystyle |\frac{\varphi(x)}{\psi(x)}| \leq K, x \to a$

のとき $\varphi(x) = O(\psi(x))$ と書く。

「 $O(\psi(x))$ は $\psi(x)$ で割って $K$ で上から抑えられる数」と覚えればよい。

発散速度の表現

$x \to \infty$ のときもだいたい同じ感じで表現できる。ここでは省略。

テイラー展開の表現

$Rn$ を剰余項としてこんな風に書くことにする。

$\displaystyle f(x) = f(a) + f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^{2} + \cdots \\\ \displaystyle + \frac{f^{(n-1)(a)}}{(n-1)!}(x-a)^{n-1} + Rn, x \to a$

このときに $Rn$ が $(x - a)^{n}$ で割れてかつ正数 $K$ で上から抑えられるので、

$\displaystyle Rn = O( (x - a)^{n} )$

とも表現できるわけである。

さらに $(x-a)^{n}$ は $(x-a)^{n-1}$ より高位の無限小なので

$\displaystyle Rn = o((x-a)^{n-1})$

としてしまってもよい。

不定形の極限を計算するときには、テイラー展開を上手に使って $O( (x-a)^{n} )$ を $o(1)$ のような形に持ち込みたい。 $o(1)$ はつまり「 $1$ で割って $0$ になる数」として処理できる（無視できる）ことになり、 $\displaystyle \lim_{x \to 0}{(x + o( 1 ) )} = 0$ のように計算できる。

たとえばこのように:

$\displaystyle \lim_{x \to 0}{\frac{\log(1+x) - x}{x^{2}}} \\\displaystyle = \lim_{x \to 0} {\frac{( x - \frac{1}{2} x^{2} + O(x^{3}) ) - x}{x^{2}}} \\\displaystyle = \lim_{x \to 0} {\frac{- \frac{1}{2} x^{2} + o(x^{2})}{x^{2}}} \\\displaystyle = \lim_{x \to 0} {( - \frac{1}{2} + o( 1 ) )} \\\displaystyle = - \frac{1}{2}$