Source code for sympy.series.order

from sympy.core import Basic, S, sympify, Expr, Rational, Symbol
from sympy.core import Add, Mul, expand_power_base, expand_log
from sympy.core.cache import cacheit
from sympy.core.compatibility import cmp_to_key

[docs]class Order(Expr): """ Represents the limiting behavior of some function The order of a function characterizes the function based on the limiting behavior of the function as it goes to some limit. Only taking the limit point to be 0 is currently supported. This is expressed in big O notation [1]_. The formal definition for the order of a function `g(x)` about a point `a` is such that `g(x) = O(f(x))` as `x \\rightarrow a` if and only if for any `\delta > 0` there exists a `M > 0` such that `|g(x)| \leq M|f(x)|` for `|x-a| < \delta`. This is equivalent to `\lim_{x \\rightarrow a} |g(x)/f(x)| < \infty`. Let's illustrate it on the following example by taking the expansion of `\sin(x)` about 0: .. math :: \sin(x) = x - x^3/3! + O(x^5) where in this case `O(x^5) = x^5/5! - x^7/7! + \cdots`. By the definition of `O`, for any `\delta > 0` there is an `M` such that: .. math :: |x^5/5! - x^7/7! + ....| <= M|x^5| \\text{ for } |x| < \delta or by the alternate definition: .. math :: \lim_{x \\rightarrow 0} | (x^5/5! - x^7/7! + ....) / x^5| < \infty which surely is true, because .. math :: \lim_{x \\rightarrow 0} | (x^5/5! - x^7/7! + ....) / x^5| = 1/5! As it is usually used, the order of a function can be intuitively thought of representing all terms of powers greater than the one specified. For example, `O(x^3)` corresponds to any terms proportional to `x^3, x^4,\ldots` and any higher power. For a polynomial, this leaves terms proportional to `x^2`, `x` and constants. Examples ======== >>> from sympy import O >>> from sympy.abc import x >>> O(x) O(x) >>> O(x)*x O(x**2) >>> O(x)-O(x) O(x) References ========== .. [1] `Big O notation <http://en.wikipedia.org/wiki/Big_O_notation>`_ Notes ===== In ``O(f(x), x)`` the expression ``f(x)`` is assumed to have a leading term. ``O(f(x), x)`` is automatically transformed to ``O(f(x).as_leading_term(x),x)``. ``O(expr*f(x), x)`` is ``O(f(x), x)`` ``O(expr, x)`` is ``O(1)`` ``O(0, x)`` is 0. Multivariate O is also supported: ``O(f(x, y), x, y)`` is transformed to ``O(f(x, y).as_leading_term(x,y).as_leading_term(y), x, y)`` In the multivariate case, it is assumed the limits w.r.t. the various symbols commute. If no symbols are passed then all symbols in the expression are used: """ is_Order = True __slots__ = [] @cacheit def __new__(cls, expr, *symbols, **assumptions): expr = sympify(expr) if expr is S.NaN: return S.NaN if symbols: symbols = map(sympify, symbols) if not all(isinstance(s, Symbol) for s in symbols): raise NotImplementedError( 'Order at points other than 0 not supported.') else: symbols = list(expr.free_symbols) if expr.is_Order: v = set(expr.variables) symbols = v | set(symbols) if symbols == v: return expr symbols = list(symbols) elif symbols: symbols = list(set(symbols)) if len(symbols) > 1: # XXX: better way? We need this expand() to # workaround e.g: expr = x*(x + y). # (x*(x + y)).as_leading_term(x, y) currently returns # x*y (wrong order term!). That's why we want to deal with # expand()'ed expr (handled in "if expr.is_Add" branch below). expr = expr.expand() if expr.is_Add: lst = expr.extract_leading_order(*symbols) expr = Add(*[f.expr for (e, f) in lst]) elif expr: expr = expr.as_leading_term(*symbols) expr = expr.as_independent(*symbols, **dict(as_Add=False))[1] expr = expand_power_base(expr) expr = expand_log(expr) if len(symbols) == 1: # The definition of O(f(x)) symbol explicitly stated that # the argument of f(x) is irrelevant. That's why we can # combine some power exponents (only "on top" of the # expression tree for f(x)), e.g.: # x**p * (-x)**q -> x**(p+q) for real p, q. x = symbols[0] margs = list(Mul.make_args( expr.as_independent(x, **dict(as_Add=False))[1])) for i, t in enumerate(margs): if t.is_Pow: b, q = t.args if b in (x, -x) and q.is_real and not q.has(x): margs[i] = x**q elif b.is_Pow and not b.exp.has(x): b, r = b.args if b in (x, -x) and r.is_real: margs[i] = x**(r*q) elif b.is_Mul and b.args[0] is S.NegativeOne: b = -b if b.is_Pow and not b.exp.has(x): b, r = b.args if b in (x, -x) and r.is_real: margs[i] = x**(r*q) expr = Mul(*margs) if expr is S.Zero: return expr if not expr.has(*symbols): expr = S.One # create Order instance: symbols.sort(key=cmp_to_key(Basic.compare)) obj = Expr.__new__(cls, expr, *symbols, **assumptions) return obj def _hashable_content(self): return self.args def oseries(self, order): return self def _eval_nseries(self, x, n, logx): return self @property def expr(self): return self._args[0] @property def variables(self): return self._args[1:] @property def free_symbols(self): return self.expr.free_symbols def _eval_power(b, e): if e.is_Number: return Order(b.expr ** e, *b.variables) return def as_expr_variables(self, order_symbols): if order_symbols is None: order_symbols = self.variables else: for s in self.variables: if s not in order_symbols: order_symbols = order_symbols + (s,) return self.expr, order_symbols def removeO(self): return S.Zero def getO(self): return self @cacheit
[docs] def contains(self, expr): """ Return True if expr belongs to Order(self.expr, \*self.variables). Return False if self belongs to expr. Return None if the inclusion relation cannot be determined (e.g. when self and expr have different symbols). """ # NOTE: when multiplying out series a lot of queries like # O(...).contains(a*x**b) with many a and few b are made. # Separating out the independent part allows for better caching. c, m = expr.as_coeff_mul(*self.variables) if m != (): return self._contains(Mul(*m)) else: # Mul(*m) == 1, and O(1) treatment is somewhat peculiar ... # some day this else should not be necessary return self._contains(expr)
@cacheit def _contains(self, expr): from sympy import powsimp, limit if expr is S.Zero: return True if expr is S.NaN: return False if expr.is_Order: if self.variables and expr.variables: common_symbols = tuple( [s for s in self.variables if s in expr.variables]) elif self.variables: common_symbols = self.variables else: common_symbols = expr.variables if not common_symbols: if not (self.variables or expr.variables): # O(1),O(1) return True return None r = None for s in common_symbols: l = limit(powsimp(self.expr/expr.expr, deep=True, combine='exp'), s, 0) != 0 if r is None: r = l else: if r != l: return return r obj = Order(expr, *self.variables) return self.contains(obj) def _eval_subs(self, old, new): if old.is_Symbol and old in self.variables: i = list(self.variables).index(old) if isinstance(new, Symbol): return Order(self.expr._subs(old, new), *(self.variables[:i] + (new,) + self.variables[i + 1:])) return Order(self.expr._subs(old, new), *(self.variables[:i] + self.variables[i + 1:])) return Order(self.expr._subs(old, new), *self.variables) def _eval_conjugate(self): expr = self.expr._eval_conjugate() if expr is not None: return self.func(expr, *self.variables) def _eval_derivative(self, x): return self.func(self.expr.diff(x), *self.variables) or self def _eval_transpose(self): expr = self.expr._eval_transpose() if expr is not None: return self.func(expr, *self.variables) def _sage_(self): #XXX: SAGE doesn't have Order yet. Let's return 0 instead. return Rational(0)._sage_()
O = Order