|
|
""" |
|
|
Finite difference weights |
|
|
========================= |
|
|
|
|
|
This module implements an algorithm for efficient generation of finite |
|
|
difference weights for ordinary differentials of functions for |
|
|
derivatives from 0 (interpolation) up to arbitrary order. |
|
|
|
|
|
The core algorithm is provided in the finite difference weight generating |
|
|
function (``finite_diff_weights``), and two convenience functions are provided |
|
|
for: |
|
|
|
|
|
- estimating a derivative (or interpolate) directly from a series of points |
|
|
is also provided (``apply_finite_diff``). |
|
|
- differentiating by using finite difference approximations |
|
|
(``differentiate_finite``). |
|
|
|
|
|
""" |
|
|
|
|
|
from sympy.core.function import Derivative |
|
|
from sympy.core.singleton import S |
|
|
from sympy.core.function import Subs |
|
|
from sympy.core.traversal import preorder_traversal |
|
|
from sympy.utilities.exceptions import sympy_deprecation_warning |
|
|
from sympy.utilities.iterables import iterable |
|
|
|
|
|
|
|
|
|
|
|
def finite_diff_weights(order, x_list, x0=S.One): |
|
|
""" |
|
|
Calculates the finite difference weights for an arbitrarily spaced |
|
|
one-dimensional grid (``x_list``) for derivatives at ``x0`` of order |
|
|
0, 1, ..., up to ``order`` using a recursive formula. Order of accuracy |
|
|
is at least ``len(x_list) - order``, if ``x_list`` is defined correctly. |
|
|
|
|
|
Parameters |
|
|
========== |
|
|
|
|
|
order: int |
|
|
Up to what derivative order weights should be calculated. |
|
|
0 corresponds to interpolation. |
|
|
x_list: sequence |
|
|
Sequence of (unique) values for the independent variable. |
|
|
It is useful (but not necessary) to order ``x_list`` from |
|
|
nearest to furthest from ``x0``; see examples below. |
|
|
x0: Number or Symbol |
|
|
Root or value of the independent variable for which the finite |
|
|
difference weights should be generated. Default is ``S.One``. |
|
|
|
|
|
Returns |
|
|
======= |
|
|
|
|
|
list |
|
|
A list of sublists, each corresponding to coefficients for |
|
|
increasing derivative order, and each containing lists of |
|
|
coefficients for increasing subsets of x_list. |
|
|
|
|
|
Examples |
|
|
======== |
|
|
|
|
|
>>> from sympy import finite_diff_weights, S |
|
|
>>> res = finite_diff_weights(1, [-S(1)/2, S(1)/2, S(3)/2, S(5)/2], 0) |
|
|
>>> res |
|
|
[[[1, 0, 0, 0], |
|
|
[1/2, 1/2, 0, 0], |
|
|
[3/8, 3/4, -1/8, 0], |
|
|
[5/16, 15/16, -5/16, 1/16]], |
|
|
[[0, 0, 0, 0], |
|
|
[-1, 1, 0, 0], |
|
|
[-1, 1, 0, 0], |
|
|
[-23/24, 7/8, 1/8, -1/24]]] |
|
|
>>> res[0][-1] # FD weights for 0th derivative, using full x_list |
|
|
[5/16, 15/16, -5/16, 1/16] |
|
|
>>> res[1][-1] # FD weights for 1st derivative |
|
|
[-23/24, 7/8, 1/8, -1/24] |
|
|
>>> res[1][-2] # FD weights for 1st derivative, using x_list[:-1] |
|
|
[-1, 1, 0, 0] |
|
|
>>> res[1][-1][0] # FD weight for 1st deriv. for x_list[0] |
|
|
-23/24 |
|
|
>>> res[1][-1][1] # FD weight for 1st deriv. for x_list[1], etc. |
|
|
7/8 |
|
|
|
|
|
Each sublist contains the most accurate formula at the end. |
|
|
Note, that in the above example ``res[1][1]`` is the same as ``res[1][2]``. |
|
|
Since res[1][2] has an order of accuracy of |
|
|
``len(x_list[:3]) - order = 3 - 1 = 2``, the same is true for ``res[1][1]``! |
|
|
|
|
|
>>> res = finite_diff_weights(1, [S(0), S(1), -S(1), S(2), -S(2)], 0)[1] |
|
|
>>> res |
|
|
[[0, 0, 0, 0, 0], |
|
|
[-1, 1, 0, 0, 0], |
|
|
[0, 1/2, -1/2, 0, 0], |
|
|
[-1/2, 1, -1/3, -1/6, 0], |
|
|
[0, 2/3, -2/3, -1/12, 1/12]] |
|
|
>>> res[0] # no approximation possible, using x_list[0] only |
|
|
[0, 0, 0, 0, 0] |
|
|
>>> res[1] # classic forward step approximation |
|
|
[-1, 1, 0, 0, 0] |
|
|
>>> res[2] # classic centered approximation |
|
|
[0, 1/2, -1/2, 0, 0] |
|
|
>>> res[3:] # higher order approximations |
|
|
[[-1/2, 1, -1/3, -1/6, 0], [0, 2/3, -2/3, -1/12, 1/12]] |
|
|
|
|
|
Let us compare this to a differently defined ``x_list``. Pay attention to |
|
|
``foo[i][k]`` corresponding to the gridpoint defined by ``x_list[k]``. |
|
|
|
|
|
>>> foo = finite_diff_weights(1, [-S(2), -S(1), S(0), S(1), S(2)], 0)[1] |
|
|
>>> foo |
|
|
[[0, 0, 0, 0, 0], |
|
|
[-1, 1, 0, 0, 0], |
|
|
[1/2, -2, 3/2, 0, 0], |
|
|
[1/6, -1, 1/2, 1/3, 0], |
|
|
[1/12, -2/3, 0, 2/3, -1/12]] |
|
|
>>> foo[1] # not the same and of lower accuracy as res[1]! |
|
|
[-1, 1, 0, 0, 0] |
|
|
>>> foo[2] # classic double backward step approximation |
|
|
[1/2, -2, 3/2, 0, 0] |
|
|
>>> foo[4] # the same as res[4] |
|
|
[1/12, -2/3, 0, 2/3, -1/12] |
|
|
|
|
|
Note that, unless you plan on using approximations based on subsets of |
|
|
``x_list``, the order of gridpoints does not matter. |
|
|
|
|
|
The capability to generate weights at arbitrary points can be |
|
|
used e.g. to minimize Runge's phenomenon by using Chebyshev nodes: |
|
|
|
|
|
>>> from sympy import cos, symbols, pi, simplify |
|
|
>>> N, (h, x) = 4, symbols('h x') |
|
|
>>> x_list = [x+h*cos(i*pi/(N)) for i in range(N,-1,-1)] # chebyshev nodes |
|
|
>>> print(x_list) |
|
|
[-h + x, -sqrt(2)*h/2 + x, x, sqrt(2)*h/2 + x, h + x] |
|
|
>>> mycoeffs = finite_diff_weights(1, x_list, 0)[1][4] |
|
|
>>> [simplify(c) for c in mycoeffs] #doctest: +NORMALIZE_WHITESPACE |
|
|
[(h**3/2 + h**2*x - 3*h*x**2 - 4*x**3)/h**4, |
|
|
(-sqrt(2)*h**3 - 4*h**2*x + 3*sqrt(2)*h*x**2 + 8*x**3)/h**4, |
|
|
(6*h**2*x - 8*x**3)/h**4, |
|
|
(sqrt(2)*h**3 - 4*h**2*x - 3*sqrt(2)*h*x**2 + 8*x**3)/h**4, |
|
|
(-h**3/2 + h**2*x + 3*h*x**2 - 4*x**3)/h**4] |
|
|
|
|
|
Notes |
|
|
===== |
|
|
|
|
|
If weights for a finite difference approximation of 3rd order |
|
|
derivative is wanted, weights for 0th, 1st and 2nd order are |
|
|
calculated "for free", so are formulae using subsets of ``x_list``. |
|
|
This is something one can take advantage of to save computational cost. |
|
|
Be aware that one should define ``x_list`` from nearest to furthest from |
|
|
``x0``. If not, subsets of ``x_list`` will yield poorer approximations, |
|
|
which might not grand an order of accuracy of ``len(x_list) - order``. |
|
|
|
|
|
See also |
|
|
======== |
|
|
|
|
|
sympy.calculus.finite_diff.apply_finite_diff |
|
|
|
|
|
References |
|
|
========== |
|
|
|
|
|
.. [1] Generation of Finite Difference Formulas on Arbitrarily Spaced |
|
|
Grids, Bengt Fornberg; Mathematics of computation; 51; 184; |
|
|
(1988); 699-706; doi:10.1090/S0025-5718-1988-0935077-0 |
|
|
|
|
|
""" |
|
|
|
|
|
order = S(order) |
|
|
if not order.is_number: |
|
|
raise ValueError("Cannot handle symbolic order.") |
|
|
if order < 0: |
|
|
raise ValueError("Negative derivative order illegal.") |
|
|
if int(order) != order: |
|
|
raise ValueError("Non-integer order illegal") |
|
|
M = order |
|
|
N = len(x_list) - 1 |
|
|
delta = [[[0 for nu in range(N+1)] for n in range(N+1)] for |
|
|
m in range(M+1)] |
|
|
delta[0][0][0] = S.One |
|
|
c1 = S.One |
|
|
for n in range(1, N+1): |
|
|
c2 = S.One |
|
|
for nu in range(n): |
|
|
c3 = x_list[n] - x_list[nu] |
|
|
c2 = c2 * c3 |
|
|
if n <= M: |
|
|
delta[n][n-1][nu] = 0 |
|
|
for m in range(min(n, M)+1): |
|
|
delta[m][n][nu] = (x_list[n]-x0)*delta[m][n-1][nu] -\ |
|
|
m*delta[m-1][n-1][nu] |
|
|
delta[m][n][nu] /= c3 |
|
|
for m in range(min(n, M)+1): |
|
|
delta[m][n][n] = c1/c2*(m*delta[m-1][n-1][n-1] - |
|
|
(x_list[n-1]-x0)*delta[m][n-1][n-1]) |
|
|
c1 = c2 |
|
|
return delta |
|
|
|
|
|
|
|
|
def apply_finite_diff(order, x_list, y_list, x0=S.Zero): |
|
|
""" |
|
|
Calculates the finite difference approximation of |
|
|
the derivative of requested order at ``x0`` from points |
|
|
provided in ``x_list`` and ``y_list``. |
|
|
|
|
|
Parameters |
|
|
========== |
|
|
|
|
|
order: int |
|
|
order of derivative to approximate. 0 corresponds to interpolation. |
|
|
x_list: sequence |
|
|
Sequence of (unique) values for the independent variable. |
|
|
y_list: sequence |
|
|
The function value at corresponding values for the independent |
|
|
variable in x_list. |
|
|
x0: Number or Symbol |
|
|
At what value of the independent variable the derivative should be |
|
|
evaluated. Defaults to 0. |
|
|
|
|
|
Returns |
|
|
======= |
|
|
|
|
|
sympy.core.add.Add or sympy.core.numbers.Number |
|
|
The finite difference expression approximating the requested |
|
|
derivative order at ``x0``. |
|
|
|
|
|
Examples |
|
|
======== |
|
|
|
|
|
>>> from sympy import apply_finite_diff |
|
|
>>> cube = lambda arg: (1.0*arg)**3 |
|
|
>>> xlist = range(-3,3+1) |
|
|
>>> apply_finite_diff(2, xlist, map(cube, xlist), 2) - 12 # doctest: +SKIP |
|
|
-3.55271367880050e-15 |
|
|
|
|
|
we see that the example above only contain rounding errors. |
|
|
apply_finite_diff can also be used on more abstract objects: |
|
|
|
|
|
>>> from sympy import IndexedBase, Idx |
|
|
>>> x, y = map(IndexedBase, 'xy') |
|
|
>>> i = Idx('i') |
|
|
>>> x_list, y_list = zip(*[(x[i+j], y[i+j]) for j in range(-1,2)]) |
|
|
>>> apply_finite_diff(1, x_list, y_list, x[i]) |
|
|
((x[i + 1] - x[i])/(-x[i - 1] + x[i]) - 1)*y[i]/(x[i + 1] - x[i]) - |
|
|
(x[i + 1] - x[i])*y[i - 1]/((x[i + 1] - x[i - 1])*(-x[i - 1] + x[i])) + |
|
|
(-x[i - 1] + x[i])*y[i + 1]/((x[i + 1] - x[i - 1])*(x[i + 1] - x[i])) |
|
|
|
|
|
Notes |
|
|
===== |
|
|
|
|
|
Order = 0 corresponds to interpolation. |
|
|
Only supply so many points you think makes sense |
|
|
to around x0 when extracting the derivative (the function |
|
|
need to be well behaved within that region). Also beware |
|
|
of Runge's phenomenon. |
|
|
|
|
|
See also |
|
|
======== |
|
|
|
|
|
sympy.calculus.finite_diff.finite_diff_weights |
|
|
|
|
|
References |
|
|
========== |
|
|
|
|
|
Fortran 90 implementation with Python interface for numerics: finitediff_ |
|
|
|
|
|
.. _finitediff: https://github.com/bjodah/finitediff |
|
|
|
|
|
""" |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N = len(x_list) - 1 |
|
|
if len(x_list) != len(y_list): |
|
|
raise ValueError("x_list and y_list not equal in length.") |
|
|
|
|
|
delta = finite_diff_weights(order, x_list, x0) |
|
|
|
|
|
derivative = 0 |
|
|
for nu in range(len(x_list)): |
|
|
derivative += delta[order][N][nu]*y_list[nu] |
|
|
return derivative |
|
|
|
|
|
|
|
|
def _as_finite_diff(derivative, points=1, x0=None, wrt=None): |
|
|
""" |
|
|
Returns an approximation of a derivative of a function in |
|
|
the form of a finite difference formula. The expression is a |
|
|
weighted sum of the function at a number of discrete values of |
|
|
(one of) the independent variable(s). |
|
|
|
|
|
Parameters |
|
|
========== |
|
|
|
|
|
derivative: a Derivative instance |
|
|
|
|
|
points: sequence or coefficient, optional |
|
|
If sequence: discrete values (length >= order+1) of the |
|
|
independent variable used for generating the finite |
|
|
difference weights. |
|
|
If it is a coefficient, it will be used as the step-size |
|
|
for generating an equidistant sequence of length order+1 |
|
|
centered around ``x0``. default: 1 (step-size 1) |
|
|
|
|
|
x0: number or Symbol, optional |
|
|
the value of the independent variable (``wrt``) at which the |
|
|
derivative is to be approximated. Default: same as ``wrt``. |
|
|
|
|
|
wrt: Symbol, optional |
|
|
"with respect to" the variable for which the (partial) |
|
|
derivative is to be approximated for. If not provided it |
|
|
is required that the Derivative is ordinary. Default: ``None``. |
|
|
|
|
|
Examples |
|
|
======== |
|
|
|
|
|
>>> from sympy import symbols, Function, exp, sqrt, Symbol |
|
|
>>> from sympy.calculus.finite_diff import _as_finite_diff |
|
|
>>> x, h = symbols('x h') |
|
|
>>> f = Function('f') |
|
|
>>> _as_finite_diff(f(x).diff(x)) |
|
|
-f(x - 1/2) + f(x + 1/2) |
|
|
|
|
|
The default step size and number of points are 1 and ``order + 1`` |
|
|
respectively. We can change the step size by passing a symbol |
|
|
as a parameter: |
|
|
|
|
|
>>> _as_finite_diff(f(x).diff(x), h) |
|
|
-f(-h/2 + x)/h + f(h/2 + x)/h |
|
|
|
|
|
We can also specify the discretized values to be used in a sequence: |
|
|
|
|
|
>>> _as_finite_diff(f(x).diff(x), [x, x+h, x+2*h]) |
|
|
-3*f(x)/(2*h) + 2*f(h + x)/h - f(2*h + x)/(2*h) |
|
|
|
|
|
The algorithm is not restricted to use equidistant spacing, nor |
|
|
do we need to make the approximation around ``x0``, but we can get |
|
|
an expression estimating the derivative at an offset: |
|
|
|
|
|
>>> e, sq2 = exp(1), sqrt(2) |
|
|
>>> xl = [x-h, x+h, x+e*h] |
|
|
>>> _as_finite_diff(f(x).diff(x, 1), xl, x+h*sq2) |
|
|
2*h*((h + sqrt(2)*h)/(2*h) - (-sqrt(2)*h + h)/(2*h))*f(E*h + x)/((-h + E*h)*(h + E*h)) + |
|
|
(-(-sqrt(2)*h + h)/(2*h) - (-sqrt(2)*h + E*h)/(2*h))*f(-h + x)/(h + E*h) + |
|
|
(-(h + sqrt(2)*h)/(2*h) + (-sqrt(2)*h + E*h)/(2*h))*f(h + x)/(-h + E*h) |
|
|
|
|
|
Partial derivatives are also supported: |
|
|
|
|
|
>>> y = Symbol('y') |
|
|
>>> d2fdxdy=f(x,y).diff(x,y) |
|
|
>>> _as_finite_diff(d2fdxdy, wrt=x) |
|
|
-Derivative(f(x - 1/2, y), y) + Derivative(f(x + 1/2, y), y) |
|
|
|
|
|
See also |
|
|
======== |
|
|
|
|
|
sympy.calculus.finite_diff.apply_finite_diff |
|
|
sympy.calculus.finite_diff.finite_diff_weights |
|
|
|
|
|
""" |
|
|
if derivative.is_Derivative: |
|
|
pass |
|
|
elif derivative.is_Atom: |
|
|
return derivative |
|
|
else: |
|
|
return derivative.fromiter( |
|
|
[_as_finite_diff(ar, points, x0, wrt) for ar |
|
|
in derivative.args], **derivative.assumptions0) |
|
|
|
|
|
if wrt is None: |
|
|
old = None |
|
|
for v in derivative.variables: |
|
|
if old is v: |
|
|
continue |
|
|
derivative = _as_finite_diff(derivative, points, x0, v) |
|
|
old = v |
|
|
return derivative |
|
|
|
|
|
order = derivative.variables.count(wrt) |
|
|
|
|
|
if x0 is None: |
|
|
x0 = wrt |
|
|
|
|
|
if not iterable(points): |
|
|
if getattr(points, 'is_Function', False) and wrt in points.args: |
|
|
points = points.subs(wrt, x0) |
|
|
|
|
|
|
|
|
if order % 2 == 0: |
|
|
|
|
|
points = [x0 + points*i for i |
|
|
in range(-order//2, order//2 + 1)] |
|
|
else: |
|
|
|
|
|
points = [x0 + points*S(i)/2 for i |
|
|
in range(-order, order + 1, 2)] |
|
|
others = [wrt, 0] |
|
|
for v in set(derivative.variables): |
|
|
if v == wrt: |
|
|
continue |
|
|
others += [v, derivative.variables.count(v)] |
|
|
if len(points) < order+1: |
|
|
raise ValueError("Too few points for order %d" % order) |
|
|
return apply_finite_diff(order, points, [ |
|
|
Derivative(derivative.expr.subs({wrt: x}), *others) for |
|
|
x in points], x0) |
|
|
|
|
|
|
|
|
def differentiate_finite(expr, *symbols, |
|
|
points=1, x0=None, wrt=None, evaluate=False): |
|
|
r""" Differentiate expr and replace Derivatives with finite differences. |
|
|
|
|
|
Parameters |
|
|
========== |
|
|
|
|
|
expr : expression |
|
|
\*symbols : differentiate with respect to symbols |
|
|
points: sequence, coefficient or undefined function, optional |
|
|
see ``Derivative.as_finite_difference`` |
|
|
x0: number or Symbol, optional |
|
|
see ``Derivative.as_finite_difference`` |
|
|
wrt: Symbol, optional |
|
|
see ``Derivative.as_finite_difference`` |
|
|
|
|
|
Examples |
|
|
======== |
|
|
|
|
|
>>> from sympy import sin, Function, differentiate_finite |
|
|
>>> from sympy.abc import x, y, h |
|
|
>>> f, g = Function('f'), Function('g') |
|
|
>>> differentiate_finite(f(x)*g(x), x, points=[x-h, x+h]) |
|
|
-f(-h + x)*g(-h + x)/(2*h) + f(h + x)*g(h + x)/(2*h) |
|
|
|
|
|
``differentiate_finite`` works on any expression, including the expressions |
|
|
with embedded derivatives: |
|
|
|
|
|
>>> differentiate_finite(f(x) + sin(x), x, 2) |
|
|
-2*f(x) + f(x - 1) + f(x + 1) - 2*sin(x) + sin(x - 1) + sin(x + 1) |
|
|
>>> differentiate_finite(f(x, y), x, y) |
|
|
f(x - 1/2, y - 1/2) - f(x - 1/2, y + 1/2) - f(x + 1/2, y - 1/2) + f(x + 1/2, y + 1/2) |
|
|
>>> differentiate_finite(f(x)*g(x).diff(x), x) |
|
|
(-g(x) + g(x + 1))*f(x + 1/2) - (g(x) - g(x - 1))*f(x - 1/2) |
|
|
|
|
|
To make finite difference with non-constant discretization step use |
|
|
undefined functions: |
|
|
|
|
|
>>> dx = Function('dx') |
|
|
>>> differentiate_finite(f(x)*g(x).diff(x), points=dx(x)) |
|
|
-(-g(x - dx(x)/2 - dx(x - dx(x)/2)/2)/dx(x - dx(x)/2) + |
|
|
g(x - dx(x)/2 + dx(x - dx(x)/2)/2)/dx(x - dx(x)/2))*f(x - dx(x)/2)/dx(x) + |
|
|
(-g(x + dx(x)/2 - dx(x + dx(x)/2)/2)/dx(x + dx(x)/2) + |
|
|
g(x + dx(x)/2 + dx(x + dx(x)/2)/2)/dx(x + dx(x)/2))*f(x + dx(x)/2)/dx(x) |
|
|
|
|
|
""" |
|
|
if any(term.is_Derivative for term in list(preorder_traversal(expr))): |
|
|
evaluate = False |
|
|
|
|
|
Dexpr = expr.diff(*symbols, evaluate=evaluate) |
|
|
if evaluate: |
|
|
sympy_deprecation_warning(""" |
|
|
The evaluate flag to differentiate_finite() is deprecated. |
|
|
|
|
|
evaluate=True expands the intermediate derivatives before computing |
|
|
differences, but this usually not what you want, as it does not |
|
|
satisfy the product rule. |
|
|
""", |
|
|
deprecated_since_version="1.5", |
|
|
active_deprecations_target="deprecated-differentiate_finite-evaluate", |
|
|
) |
|
|
return Dexpr.replace( |
|
|
lambda arg: arg.is_Derivative, |
|
|
lambda arg: arg.as_finite_difference(points=points, x0=x0, wrt=wrt)) |
|
|
else: |
|
|
DFexpr = Dexpr.as_finite_difference(points=points, x0=x0, wrt=wrt) |
|
|
return DFexpr.replace( |
|
|
lambda arg: isinstance(arg, Subs), |
|
|
lambda arg: arg.expr.as_finite_difference( |
|
|
points=points, x0=arg.point[0], wrt=arg.variables[0])) |
|
|
|
