読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

オーダー記法・その3

今回の目標は、より複雑なオーダー記法をきちんと定義することです。例えば、

f(x) = 1 + 3x + O(x^2) \quad (x \to 0)

あるいは、もっと複雑な

f(n) = n^{\log n + O(\sqrt{\log n})} \quad (n \to \infty)

のような記法です。

オーダー記法の拡張

右辺の式にオーダーが入る場合

最初の例を解釈して適切な意味付けを与えましょう。f(x) に関して 1 + 3x に続く項を誤差項として、f(x) = 1 + 3x + \tau(x) と分解します。ここで、意味的に誤差項 \tau(x)\tau(x) = O(x^2) \; (x \to 0) を満たします。つまり、

f(x) = 1 + 3x + O(x^2) \quad (x \to 0)

の意味は、x = 0 の近くで定義される関数 \tau(x)

f(x) = 1 + 3x + \tau(x)

を満たすものに関して

\tau(x) = O(x^2) \quad (x \to 0)

を満たす、となります。

後者の例についても全く同様に解釈できます。すなわち、

f(x) = x^{\log x + O(\sqrt{\log x})} \quad (x \to \infty)

とは、f(x) = x^{\log x + \tau(x)} を満たす関数 \tau(x)

\tau(x) = O(\sqrt{\log x}) \; (x \to \infty)

を満たす、となります。

以上の例を一般化すると、式の中にオーダー記法が入るものは次のように意味付けできます。

定義: 適当な範囲で定義された関数 f(x)g(x) および R(x, u) に関して、

f(x) = R(x, O(g(x)))

とは、f(x) = R(x, \tau(x)) を満たす関数 \tau(x)

\tau(x) = O(g(x))

を満たすことをいう。ただし、上下のオーダーにおいて考える極限は同じとする。

あるいは、後半の表現を次のように書き換えることもできます。(「ちょっと複雑な論理表現・その2」を参照)

ある関数 \tau(x) が存在して、f(x) = R(x, \tau(x)) かつ \tau(x) = O(g(x)) を満たすことをいう。

以上はBig-O記法に関するものでしたが、small-o記法に関しても全く同様です。

定義: 適当な範囲で定義された関数 f(x)g(x) および R(x, u) に関して、

f(x) = R(x, o(g(x)))

とは、f(x) = R(x, \tau(x)) を満たす関数 \tau(x)

\tau(x) = o(g(x))

を満たすことをいう。ただし、それぞれのオーダーにおいて考える極限は同じとする。

この定義をさらに拡張して、右辺にオーダーが複数現れる式にも意味を持たせることができます。すなわち、関数 g_1(x), g_2(x), \dots および R(x, u_1, u_2, \dots) に関して

f(x) = R(x, O(g_1(x)), O(g_2(x)), \dots)

とは、f(x) = R(x, \tau_1(x), \dots) を満たす関数 \tau_1(x), \tau_2(x), \dots

\tau_1(x) = O(g_1(x))\tau_2(x) = O(g_2(x))\dots

を満たすことを言います。例えば

(x^2 + 2 x) (x + 3\sqrt{x}) = (x^2 + O(x))(x + O(\sqrt{x})) \quad (x \to \infty)

などが成り立ちます。さらに進めてBig-O記法とsmall-O記法の両方が入る場合なども考えることはできますが、敢えて突っ込むことはしません。

左辺の式にもオーダーが入る場合

今度は左辺の式にもオーダーが入る場合について意味付けを行います。単純な例としては、

O(x) = O(x^2) \quad (x \to \infty)

などがあります。

これに意味を与えるには、オーダー記法を式変形で置き換える場合について考えます。まず、f(x) = O(x) \; (x \to \infty) を満たす関数 f(x) があるとします。このとき、O(x) = O(x^2) \; (x \to \infty) を用いて

f(x) = O(x) = O(x^2) \quad (x \to \infty)

から

f(x) = O(x^2) \quad (x \to \infty)

という式変形が常に可能であるとするのです。すなわち、f(x) = O(x) \; (x \to \infty) を満たす任意の f(x) に関して f(x) = O(x^2) \; (x \to \infty) が成り立つことをもって O(x) = O(x^2) \; (x \to \infty) とするのです。

これを一般化すると次のように定義できます。

定義: 適当な範囲で定義された関数 g(x)h(x) および L(x, u)R(x, u) に関して、

L(x, O(g(x))) = R(x, O(h(x)))

とは、f(x) = L(x, O(g(x))) を満たす任意の関数 f(x)

f(x) = R(x, O(h(x)))

を満たすことをいう。ただし、それぞれのオーダーにおいて考える極限は同じとする。

後半の表現は次のように書き換えることもできます。

任意の関数 f(x) に関して、f(x) = L(x, O(g(x))) ならば f(x) = R(x, O(h(x))) を満たす。

small-o記法の場合は上のOをoに変えるだけです。あるいは、混在させることもできます。例えば、関数 g(x)h(x) および L(x, u)R(x, u) に関して、

L(x, O(g(x))) = R(x, o(h(x)))

とは、f(x) = L(x, O(g(x))) を満たす任意の関数 f(x)

f(x) = R(x, o(h(x)))

を満たすことを言います。具体例としては O(x) = o(x^2) \; (x \to \infty) などが挙げられます。このようなバリエーションはいくつも考えられるので、これ以上は突っ込みません。

先と同様に、両辺に複数のオーダーが入る場合も考えることができます。例えば

(x^2 + O(x))(x + O(\sqrt{x})) = x^3 + O(x^{5/2}) \quad (x \to \infty)

などが成り立ちます。くどいようですが、定義を敢えて書くと、関数 g_1(x), g_2(x), \dotsh_1(x), h_2(x), \dots および L(x, u_1, u_2, \dots)R(x, u_1, u_2, \dots) に関して、

L(x, O(g_1(x)), O(g_2(x)), \dots) = R(x, O(h_1(x)), O(h_2(x)), \dots)

とは、f(x) = L(x, O(g_1(x)), O(g_2(x)), \dots) を満たす任意の関数 f(x)

f(x) = R(x, O(h_1(x)), O(h_2(x)), \dots)

を満たすことを言います。さらにBig-O記法とsmall-O記法を混在させることもできて…ともうこれ以上はいいでしょう。

オーダー同士の演算

せっかく両辺にオーダーが入る場合を定義したのですから、オーダー記法同士の演算についてもいくつか挙げておきましょう。代表的なものに

  • O(f(x)) + O(g(x)) = O(\max \{|f(x)|, |g(x)|\})
  • O(f(x)) O(g(x)) = O(f(x) g(x))

があります。和の方については、複雑な式を主要項で代表させることができるというオーダー記法の利便性を、式でちゃんと表現したものになっています。例えば、

1 + 3 x + 2 x^2 = O(1) + O(x) + O(x^2) = O(x^2) \quad (x \to \infty)

が成り立ちます。今回導入した記法の便利なところは、このようにオーダーを普通の多項式のように計算することができることです。

試しに最初の式について証明してみましょう。極限としてはとりあえず x \to \infty を考えます。

上の定義を当てはめると、f_1(x) = O(f(x)) および g_1(x) = g(x) を満たす任意の関数 f_1(x), g_1(x) に関して f_1(x) + g_1(x) = O(\max \{ f(x), g(x) \}) が成り立つことを示せばいいということになります。オーダーの定義を書き下すと、

f_1(x) = O(f(x)) \quad (x \to \infty)
\Leftrightarrow
\exists c_1 > 0;\;\exists x_1 > 0;\;\forall x \geq x_1;\; |f(x)| \leq c_1 |g(x)|

および

g_1(x) = O(f(x)) \quad (x \to \infty)
\Leftrightarrow
\exists c_2 > 0;\;\exists x_2 > 0;\;\forall x \geq x_2;\; |f(x)| \leq c_2 |g(x)|

です。これらを組み合わせると

\exists c_1 > 0;\;\exists x_1 > 0;\;\forall x \geq x_1;\; \exists c_2 > 0;\;\exists x_2 > 0;\;\forall x \geq x_2;
|f_1(x)| + |g_1(x)| \leq c_1 |f(x)| + c_2 |g(x)|

となります。ここで c := \max \{c_1, c_2 \} および x_0 := \max \{x_1, x_2 \} と置けば

\exists c > 0;\;\exists x_0 > 0;\;\forall x \geq x_0;\; |f_1(x)| + |g_1(x)| \leq c (|f(x)| + |g(x)|)

と書き換えられます。さらに |f_1(x) + g_1(x)| \leq |f_1(x)| + |g_1(x)|(三角不等式)および |f(x)| + |g(x)| \leq 2 \max \{ |f(x)|, |g(x)| \} を用いると

\exists c > 0;\;\exists x_0 > 0;\;\forall x \geq x_0;\; |f_1(x) + g_1(x)| \leq 2c \max \{ |f(x)|, |g(x)| \}
\Leftrightarrow
f_1(x) + g_1(x) = O(\max \{ |f(x)|, |g(x)| \})

より示されました。

Big-O記法をsmall-o記法に置き換えても同じ関係が成り立ちます。

  • o(f(x)) + o(g(x)) = o(\max \{|f(x)|, |g(x)|\})
  • o(f(x)) o(g(x)) = o(f(x) g(x))

あるいは

  • O(f(x)) o(g(x)) = o(f(x) g(x))

といった関係も成り立ちます。これも挙げるときりがないのでこの辺で。

集合を用いたオーダー記法

これまでのオーダー記法では記号の濫用として等号を用いて表していましたが、実はオーダーを集合として考えた方がすっきりすることを見ます。

関数 g(x) に関して、O(g(x))f(x) = O(g(x)) を満たす関数の集合とします。すると、今まで f(x) = O(g(x)) と書いてきたものは f(x) \in O(g(x)) と書くことになります。実際、このような表記を用いている本も存在します。

ところで、関数 f(x) に対して集合 A を当てはめた記号 f(A)(記号の濫用)は、f によって A の要素を写したものの全体を表します。これを f による A の像と言います。集合の定義を書くと

f(A) = \{ f(x) : x \in A \}

となります。全く同様にして、多変数関数についても像が定義されます。例えば f(x, y) に関して

f(A, B) = \{ f(x, y) : x \in A, y \in B \}
f(x, B) = \{ f(x, y) : y \in B \}

といった具合です。

ここで R(x, u)u に集合 O(g(x)) を当てはめることを考えます。すると

R(x, O(g(x))) = \{ R(x, \tau(x)) : \tau(x) \in O(g(x))\}

となります。これより

f(x) \in R(x, O(g(x)))
\Leftrightarrow
\exists \tau(x) \in O(g(x));\; f(x) = R(x, \tau(x))
\Leftrightarrow
\exists \tau(x);\; f(x) = R(x, \tau(x)) \mbox{ and } \tau(x) \in O(g(x))

となります。最後の式を元の記号で書き下すと、ある関数 \tau(x) が存在して、f(x) = R(x, \tau(x)) かつ \tau(x) = O(g(x)) を満たすということです。これは f(x) = R(x, \tau(x)) の定義そのままです。すなわち f(x) \in R(x, O(g(x)))f(x) = R(x, O(g(x))) と同値な命題となります。

左辺にオーダーが入る場合については、集合の包含関係として解釈することができます。定義によれば

L(x, O(g(x))) = R(x, O(h(x)))

とは、f(x) = L(x, O(g(x))) を満たす任意の関数 f(x)

f(x) = R(x, O(h(x)))

を満たすことでしたが、記号を置き換えて

f(x) \in L(x, O(g(x))) を満たす任意の関数 f(x)f(x) \in R(x, O(h(x))) を満たす

とすると、これは集合の包含関係

L(x, O(g(x))) \subseteq R(x, O(h(x)))

に等しいことが分かります。

このように、オーダーは集合を使って書いた方が自然に意味を取ることができます。ただし、このブログでは、集合を使ってオーダーを書くのはここだけの話として終わらせることにします。

オーダー記法の利用

オーダー記法は元々解析学の命題を簡潔に表現するために用いられました。特に、微小量が入った式の主要項と誤差項を区別するために用いられることが多いです。

例えば、x = a の周りで定義された実関数 f(x)微分可能性は、通常、次のように定義されます。

定義: f(x)x = a の周りで微分可能であるとは、ある実数 f'(a) と関数 \tau(x) が存在して、

f(a + \Delta x) = f(a) + f'(a) \Delta x + \tau(\Delta x)

かつ \Delta x \to 0 のとき \tau(\Delta x) / \Delta x \to 0 が成り立つことを言う。

注意: f'(a)x = a における f(x)微分係数と言い、f(x)x = a微分可能ならば一意に定まります。これを x の関数として見て f'(x) としたものを f(x)導関数と言います。

ここで、任意に固定された x に対して \Delta x \to 0 のとき \tau(\Delta x) / \Delta x \to 0 とは、任意の \epsilon > 0 に対して、ある \delta > 0 が存在して、任意の \Delta x に対して 0 < |\Delta x| \leq \delta ならば |\tau(\Delta x) / \Delta x| \leq \epsilon を満たすことを言います。論理記号で書くと、

\forall \epsilon > 0;\; \exists \delta > 0;\; \forall \Delta x\; 0 < |\Delta x| \leq \delta \Rightarrow |\tau(\Delta x) / \Delta x| \leq \epsilon

となります。これを少し変形すると、

\forall \epsilon > 0;\; \exists \delta > 0;\; \forall \Delta x\; 0 < |\Delta x| \leq \delta \Rightarrow |\tau(\Delta x)| < 2 \epsilon |\Delta x|
\Leftrightarrow
\tau(\Delta x) = o(\Delta x) \quad (\Delta x \to 0)

となることが分かります。これを用いて微分可能性の定義を言い換えると、

f(x)x = a の周りで微分可能であるとは、ある実数 f'(a) が存在して、

f(a + \Delta x) = f(a) + f'(a) \Delta x + o(\Delta x) \quad (\Delta x \to 0)

を満たすことを言う。

となります。オーダー記法を用いたことによって、定義が随分とシンプルになったように見えるでしょう。いちいち関数 \tau(x) を持ち込まなくてもよいのは便利です。

特によく用いられるのは、関数の級数展開を表現する場合です。例えば、

e^x = 1 + x + \frac{x^2}{2!} + \dots + \frac{x^k}{k!} + O(x^{k+1}) \quad (x \to 0)

のように、誤差項が x^{k + 1} のオーダーに収まることを単純に表すことができます。

このように、オーダー記法を用いてシンプルに表現できることは数多くあるのです。無論、次回以降の話で説明するように、情報科学でも非常によく用いられます。というわけで、皆さん、オーダー記法に慣れ親しんで下さい。

今回はここまで

今回の話では、

f(x) = 1 + 3x + O(x^2) = 1 + O(x) \quad (x \to 0)

のような、式や関数の中にオーダー記法が入った場合の扱いについて述べました。それの延長として、オーダー同士の演算を導入しました。これで、ほとんどあらゆる場合のオーダー記法の定義を網羅できたと思われます。次回からは、特に情報科学で用いられる記法について説明します。それではまた。