演算に対するオーダーの性質

ランダウのオーダー記法とは、関数の極限におけるふるまいを比較する方法である。ここでは、関数同士の足し算などでオーダーが保存されることを示す。このことは、オーダーの意義を考えるうえで重要な性質となる。

オーダーの定義と諸性質

ここでは以下の定義を使用する。

定義実数関数\(f(x), g(x)\)において \begin{eqnarray} f \in O(g) & \Leftrightarrow & \exists k \gt 0, \exists x_0, \forall x \gt x_0, |f(x)| \leq k \cdot |g(x)|, \\ f \in \Theta(g) & \Leftrightarrow & f \in O(g) \land g \in O(f). \end{eqnarray}

和のオーダー

オーダーと関数の足し算と引き算について次のことが成立する。

定理$f_1$, $f_2$, $g$ を実数関数とする。$f_1\in O(g), f_2\in O(g)$ であるならば $(f_1\pm f_2)\in O(g)$。

(証明) $f_1\in O(g), f_2\in O(g)$ であるとする。このとき、実数 $k'>0$, $k''>0$, $x_0'$, $x_0''$ が存在して\begin{eqnarray}\forall x\gt x_0':&&|f_1(x)|\leq k'|g(x)|, \\ \forall x\gt x_0'':&&|f_2(x)|\leq k''|g(x)|.\end{eqnarray}このとき、$x_0=\max\{x_0', x_0''\}$, $k=k'+k''$ とすると、任意の $x\gt x_0$  に対して\begin{eqnarray}|f_1(x)\pm f_2(x)|&\leq& |f_1(x)|+|f_2(x)| \\ &\leq& k'|g(x)|+k''|g(x)| \\ &=& k|g(x)|.\end{eqnarray}

この定理ではオーターが小さい方は二つに分けている ($f_1$ と $f_2$) のに対し、オーダーが大きい方 ($g$) について二つに分けていない。なぜかというと $f\in O(g_1)$, $f\in O(g_2)$ であっても $f\in O(g_1\pm g_2)$ ではないことがあるからである。現に、$f=1\in O(g_1)$, $g_2=\mp g_1$ とすると $f\in O(g_1)$, $f\in O(g_2)$ であるが $g_1\pm g_2=0$ より $f\not\in O(g_1\pm g_2)$ となる。

定数倍のオーダー

オーダーと定数倍に対して次のことが成立する。

定理$r$ を実数とし、$f$, $g$ を実数関数とする。このとき

  1. $f\in O(g)$ であるならば $(rf)\in O(g)$。
  2. $f\in O(g)$, $r\neq 0$ であるならば $f\in O(rg)$
  3. $f\in \Theta(g)$, $r\neq 0$ であるならば $(rf)\in\Theta(g)$

(証明) まず 1 を示す。$f\in O(g)$ より実数 $k'>0$, $x_0$ が存在して\[\forall x\gt x_0:\;|f(x)|\leq k'|g(x)|.\]このとき、$k=|r|k'+1$ とすると $k\gt 0$ であり、任意の $x\gt x_0$ に対して\begin{eqnarray}|rf(x)| &=& |r||f(x)| \\ &\leq& |r|(k'|g(x)|) \\ &\leq& |r|(k'|g(x)|) + |g(x)| \\ &=& (|r|k'+1)|g(x)| \\ &=& k|g(x)|.\end{eqnarray}

次に 2 を示す。$f\in O(g)$ より実数 $k'>0$, $x_0$ が存在して\[\forall x\gt x_0:\;|f(x)|\leq k'|g(x)|.\]このとき、$k=|r|^{-1}k'$ とすると $k\gt 0$ であり、任意の $x\gt x_0$ に対して\begin{eqnarray}|f(x)| &\leq& k'|g(x)| \\ &=& k|r||g(x)| \\ &=& k|rg(x)|.\end{eqnarray}

3 は 1 と 2 から得られる。

この定理から、オーダーは実数倍をしても変化しないことがわかる。

積のオーダー

オーダーと関数の掛け算について次のことが成り立つ

定理$f_1$, $f_2$, $g_1$, $g_2$ を実数関数とする。このとき

  1. $f_1\in O(g_1), f_2\in O(g_2)$ であるならば $(f_1f_2)\in O(g_1g_2)$
  2. $f_1\in \Theta(g_1), f_2\in \Theta(g_2)$ であるならば $(f_1f_2)\in \Theta(g_1g_2)$

(証明) まず 1 を示す。$f_1\in O(g_1), f_2\in O(g_2)$ とすると、実数 $k'>0$, $k''>0$, $x_0'$, $x_0''$ が存在して\begin{eqnarray}\forall x\gt x_0':&&|f_1(x)|\leq k'|g_1(x)|, \\ \forall x\gt x_0'':&&|f_2(x)|\leq k''|g_2(x)|.\end{eqnarray}このとき、$x_0=\max\{x_0',x_0''\}$, $k=k'k''$ とすると任意の $x\gt x_0$ に対して\begin{eqnarray}|f_1(x)f_2(x)|&\leq& |f_1(x)||f_2(x)| \\ &\leq& (k'|g_1(x)|)(k''|g_2(x)|) \\ &=& k'k''|g_1(x)||g_2(x)| \\ &=& k|g_1(x)g_2(x)|.\end{eqnarray}

2 は 1 から得られる。

たとえば、$f\in\Theta(x^5)$, $g\in\Theta(x^2)$ であれば $fg\in\Theta(x^7)$ である。