ランダウの記号(ランダウのきごう、英: Landau symbol)は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。
ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O (数字の0ではない)を用いることから(バッハマン-ランダウの)O-記法 (Bachmann-Landau O-notation[1])、ランダウのオミクロンなどともいう。
なおここでいうランダウはエトムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。
ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。 ランダウの記号 f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} は 、x がじゅうぶん大きいとき関数 f が関数 g に比例もしくはそれ以下におさえられることを示す。 たとえば二次関数 3x2 + 4x + 10 が x を限りなく大きくしたときどのように増大するかを考えると、変数 x が 2 より大きければ第一項 3x2 が他の項より大きく、さらに大きくなるほど支配的になることがわかる。漸近解析をする上では定数倍のような詳細は必要としないことが多く、O-記法を用いると、必要な情報を 3 x 2 + 4 x + 10 = O ( x 2 ) {\displaystyle 3x^{2}+4x+10=O(x^{2})} と端的に表すことができる。 このように関数 g としては関数 f よりも単純なもの(上の例では x2)が通常用いられる。(#一般的なオーダー参照。) 一方、ランダウの記号 f ( x ) = o ( g ( x ) ) {\displaystyle f(x)=o(g(x))} は関数 f がおおよそ関数 g 未満であることを示している。 たとえば x が十分大きいとき 3x2 + 4x + 10 は x3 と比べると小さくなり、o-記法を用いると、これを 3 x 2 + 4 x + 10 = o ( x 3 ) {\displaystyle 3x^{2}+4x+10=o(x^{3})} と表すことができる。(ただし、o-記法よりも O-記法の方が多くの場合好ましいと考えられている[3][4]。) これまでは変数を限りなく大きくしたときを例に説明してきたが、他にも変数を限りなく小さくしたときや、定数に限りなく近づけたときの漸近挙動も同様にランダウ記法で表すことができる。どの意味で記号が用いられているのかを f ( x ) = O ( g ( x ) ) ( x → ∞ ) {\displaystyle f(x)=O(g(x))\quad (x\to \infty )} のように明示する書き方もある。 f(x) = O(g(x)), f(x) = o(g(x)) (x → ∞) はそれぞれ を表す。(厳密にはε-δ論法で定義する。)特に f(x) = o(1) は lim f(x) = 0 と同値である。 ランダウ記法は様々な分野で有益であり、たとえば指数関数を3次までテイラー展開したものは e x = 1 + x + x 2 2 ! + x 3 3 ! + O ( x 4 ) ( x → 0 ) {\displaystyle \mathrm {e} ^{x}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+O(x^{4})\quad (x\to 0)} と書き表せる。 記号 O とo は通常、関数の収束や発散の漸近的な上界を記述する為に用いられる。同様に漸近的な下界を記述する為にΩ, ωという類似記法が用いられ、上下両方を記述する為にΘ という記法を用いる。 ただし、Ω、ω、Θは主に計算機科学で用いられる記法であり、数学では O と o をこれらの意味に流用する事が多い(どの意味で用いているのかは文脈から判断)。 十分大きい全ての実数 x に対し定義されている実数値関数 f(x) と g(x) に対し、 f ( x ) = O ( g ( x ) ) ( x → ∞ ) {\displaystyle f(x)=O(g(x))\quad (x\to \infty )} を ∃ x 0 , ∃ M > 0 s.t. ∀ x [ x > x 0 ⇒ 。 f ( x ) 。 ≤ M 。 g ( x ) 。 ] {\displaystyle {}^{\exists }x_{0},{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[x>x_{0}\Rightarrow |f(x)|\leq M|g(x)|]} と定義し、「f(x) が x → ∞ のとき オーダーO(g(x)) である」と呼ぶ。 を ∃ δ > 0 , ∃ M > 0 s.t. ∀ x [ 0 < 。 x − a 。 < δ ⇒ 。 f ( x ) 。 ≤ M 。 g ( x ) 。 ] {\displaystyle {}^{\exists }\delta >0,{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[0<|x-a|<\delta \Rightarrow |f(x)|\leq M|g(x)|]} で定義し、「f(x) が x → a のとき オーダーO(g(x)) である」と呼ぶ。 が満たされることと同値である(a が∞の場合も同様)。特に f(x) = O(1) は、近傍において f(x) が有界であることと同値である。 上で定義された f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} という記法は広く用いられている確立した慣習ではあるが紛らわしい記法の濫用で、二つの関数が等しいという意味ではない。 この記法の濫用は、等号の両辺にO -記法が登場した際に問題となり、例えばx →∞のとき、 O ( x ) = O ( x 2 ) {\displaystyle O(x)=O(x^{2})} であるが、 O ( x 2 ) ≠ O ( x ) {\displaystyle O(x^{2})\neq O(x)} である。 すなわち、両辺にO -記法が登場した場合には、直観的には十分大きなx で左辺/右辺が定数未満になる事を意味する。 こうした記法上の問題を回避する為に、 f ∈ O ( g ) {\displaystyle f\in O(g)} ないし、 f ( x ) ≤ O ( g ( x ) ) {\displaystyle f(x)\leq O(g(x))} と書く流儀もあるが、一般的ではない。前者の場合、「O(g)」 は g の定数倍によって押さえられる関数全体からなる集合であるとみなしていることになる。 より複雑な使い方としては、O( ) が等式の異なる場所に複数、もちろん両辺にわたって複数回現れるというものがある。例えば、以下は n → ∞ で正しい内容を記述している。 ( n + 1 ) 2 = n 2 + O ( n ) , ( n + O ( n 1 / 2 ) ) ( n + O ( log n ) ) 2 = n 3 + O ( n 5 / 2 ) , n O ( 1 ) = O ( e n ) . {\displaystyle {\begin{aligned}&(n+1)^{2}=n^{2}+O(n),\\&(n+O(n^{1/2}))(n+O(\log \,n))^{2}=n^{3}+O(n^{5/2}),\\&n^{O(1)}=O(e^{n}).\end{aligned}}}
概要
lim x → ∞ 。 f ( x ) g ( x ) 。 {\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|} が存在する場合には、その値が有限(0 も含む)であること(一般の場合は後述)。極限が存在しない場合、即ち振動する場合でも該当することはあることには注意されたい。
lim x → ∞ 。 f ( x ) g ( x ) 。 = 0 {\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|=0}
厳密な定義
また、a を実数とするとき、aの近傍で定義された実数値関数f(x) と g(x) に対し、 f ( x ) = O ( g ( x ) ) ( x → a ) {\displaystyle f(x)=O(g(x))\quad (x\to a)}
なお、a の十分近くで g(x) が 0 を値にとらない場合、 f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} は lim ¯ x → a 。 f ( x ) g ( x ) 。 < ∞ {\displaystyle \varlimsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty }
記法の問題
Size:67 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef