Namespaces
Variants
Actions

Order relation

From Encyclopedia of Mathematics
Jump to: navigation, search


comparison of functions, $ O $- $ o $ relations, asymptotic relations

A notion arising in studies on the behaviour of a function with respect to another function in a neighbourhood of some point (this point may be infinite).

Let $ x _ {0} $ be a limit point of a set $ E $. If for two functions $ f $ and $ g $ there exist constants $ c > 0 $ and $ \delta > 0 $ such that $ | f (x) | \leq c | g (x) | $ for $ | x - x _ {0} | < \delta $, $ x \neq x _ {0} $, then $ f $ is called a function which is bounded in comparison with $ g $ in some deleted neighbourhood of $ x _ {0} $, and this is written as

$$ f (x) = O ( g (x) ) \ \textrm{ as } x \rightarrow x _ {0} $$

(read "f is of the order of g" ); $ x \rightarrow x _ {0} $ means that the considered property holds only in some deleted neighbourhood of $ x _ {0} $. This definition can be naturally used when $ x \rightarrow \infty $, $ x \rightarrow - \infty $.

If two functions $ f $ and $ g $ are such that $ f = O (g) $ and $ g = O (f ) $ as $ x \rightarrow x _ {0} $, then they are called functions of the same order as $ x \rightarrow x _ {0} $. For instance, if two functions $ \alpha , \beta $ are such that $ \alpha (x) \neq 0 $, $ \beta (x) \neq 0 $ if $ x \neq x _ {0} $ and if the limit

$$ \lim\limits _ {x \rightarrow x _ {0} } \ \frac{\alpha (x) }{\beta (x) } = c \neq 0 $$

exists, then they are of the same order as $ x \rightarrow x _ {0} $.

Two functions $ f $ and $ g $ are called equivalent (asymptotically equal) as $ x \rightarrow x _ {0} $( written as $ f \sim g $) if in some neighbourhood of $ x _ {0} $, except maybe the point $ x _ {0} $ itself, a function $ \phi $ is defined such that

$$ \tag{* } f = \phi g \ \textrm{ and } \ \lim\limits _ {x \rightarrow x _ {0} } \phi (x) = 1 . $$

The condition of equivalency of two functions is symmetric, i.e. if $ f \sim g $, then $ g \sim f $ as $ x \rightarrow x _ {0} $, and transitive, i.e. if $ f \sim g $ and $ g \sim h $, then $ f \sim h $ as $ x \rightarrow x _ {0} $. If in some neighbourhood of the point $ x _ {0} $ the inequalities $ f (x) \neq 0 $, $ g (x) \neq 0 $ hold for $ x \neq x _ {0} $, then (*) is equivalent to any of the following conditions:

$$ \lim\limits _ {x \rightarrow x _ {0} } \ \frac{f (x) }{g (x) } = 1 ,\ \ \lim\limits _ {x \rightarrow x _ {0} } \frac{g (x) }{f (x) } = 1 . $$

If $ \alpha = \epsilon f $ where $ \lim\limits _ {x \rightarrow x _ {0} } \epsilon (x) = 0 $, then $ \alpha $ is said to be an infinitely-small function with respect to $ f $, and one writes

$$ \alpha = o (f ) \ \textrm{ as } x \rightarrow x _ {0} $$

(read "a is of lower order than f" ). If $ f (x) \neq 0 $ when $ x \neq x _ {0} $, then $ \alpha = o (f ) $ if $ \lim\limits _ {x \rightarrow x _ {0} } \alpha (x) / f(x) = 0 $. If $ f $ is an infinitely-small function for $ x \rightarrow x _ {0} $, one says that the function $ \alpha = o (f ) $ is an infinitely-small function of higher order than $ f $ as $ x \rightarrow x _ {0} $. If $ g $ and $ [ f ] ^ {k} $ are quantities of the same order, then one says that $ g $ is a quantity of order $ k $ with respect to $ f $. All formulas of the above type are called asymptotic estimates; they are especially interesting for infinitely-small and infinitely-large functions.

Examples: $ e ^ {x} - 1 = o (1) $( $ x \rightarrow 0 $); $ \cos x ^ {2} = O (1) $; $ ( \mathop{\rm ln} x ) ^ \alpha = o ( x ^ \beta ) $( $ x \rightarrow \infty $; $ \alpha , \beta $ any positive numbers); $ [ x / \sin ( 1 / x ) ] = O ( x ^ {2} ) $( $ x \rightarrow \infty $).

Here are some properties of the symbols $ o $ and $ O $:

$$ O ( \alpha f ) = O (f) \ ( \alpha \textrm{ a non-zero constant } ); $$

$$ O ( O (f ) ) = O (f ) ; $$

$$ O (f ) O (g) = O ( f \cdot g ) ; $$

$$ O ( o (f ) ) = o ( O (f ) ) = o (f ) ; $$

$$ O (f ) o (g) = o ( f \cdot g ) ; $$

if $ 0 < x < x _ {0} $ and $ f = O (g) $, then

$$ \int\limits _ {x _ {0} } ^ { x } f (y) dy = O \left ( \int\limits _ {x _ {0} } ^ { x } | g (y) | dy \right ) \ \ ( x \rightarrow x _ {0} ) . $$

Formulas containing the symbols $ o $ and $ O $ are read only from the left to the right; however, this does not exclude that certain formulas remain true when read from the right to the left. The symbols $ o $ and $ O $ for functions of a complex variable and for functions of several variables are introduced in the same way as it was done above for functions of one real variable.

Comments

The symbols $ o $ and $ O $( "little oh symbol. little oh" and "big Oh symbol, big Oh" ) were introduced by E. Landau.

References

[a1] G.H. Hardy, "A course of pure mathematics" , Cambridge Univ. Press (1975)
[a2] E. Landau, "Grundlagen der Analysis" , Akad. Verlagsgesellschaft (1930)
How to Cite This Entry:
Order relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Order_relation&oldid=44961
This article was adapted from an original article by M.I. Shabunin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article