algorithm to find derivative

I'm writing program in Pyt开发者_如何学运维hon and I need to find the derivative of a function (a function expressed as string).

• For example: x^2+3*x
• Its derivative is: 2*x+3

Are there any scripts available, or is there something helpful you can tell me?

If you are limited to polynomials (which appears to be the case), there would basically be three steps:

1. Parse the input string into a list of coefficients to x^n
2. Take that list of coefficients and convert them into a new list of coefficients according to the rules for deriving a polynomial.
3. Take the list of coefficients for the derivative and create a nice string describing the derivative polynomial function.

If you need to handle polynomials like a*x^15125 + x^2 + c, using a dict for the list of coefficients may make sense, but require a little more attention when doing the iterations through this list.

sympy does it well.

You may find what you are looking for in the answers already provided. I, however, would like to give a short explanation on how to compute symbolic derivatives.

The business is based on operator overloading and the chain rule of derivatives. For instance, the derivative of v^n is n*v^(n-1)dv/dx, right? So, if you have v=3*x and n=3, what would the derivative be? The answer: if f(x)=(3*x)^3, then the derivative is:

f'(x)=3*(3*x)^2*(d/dx(3*x))=3*(3*x)^2*(3)=3^4*x^2

The chain rule allows you to "chain" the operation: each individual derivative is simple, and you just "chain" the complexity. Another example, the derivative of u*v is v*du/dx+u*dv/dx, right? If you get a complicated function, you just chain it, say:

d/dx(x^3*sin(x))
u=x^3; v=sin(x)
du/dx=3*x^2; dv/dx=cos(x)
d/dx=v*du+u*dv

As you can see, differentiation is only a chain of simple operations.

Now, operator overloading.

If you can write a parser (try Pyparsing) then you can request it to evaluate both the function and derivative! I've done this (using Flex/Bison) just for fun, and it is quite powerful. For you to get the idea, the derivative is computed recursively by overloading the corresponding operator, and recursively applying the chain rule, so the evaluation of "*" would correspond to u*v for function value and u*der(v)+v*der(u) for derivative value (try it in C++, it is also fun).

So there you go, I know you don't mean to write your own parser - by all means use existing code (visit www.autodiff.org for automatic differentiation of Fortran and C/C++ code). But it is always interesting to know how this stuff works.

Cheers,

Juan

Better late than never?

I've always done symbolic differentiation in whatever language by working with a parse tree. But I also recently became aware of another method using complex numbers.

The parse tree approach consists of translating the following tiny Lisp code into whatever language you like:

(defun diff (s x)(cond
  ((eq s x) 1)
  ((atom s) 0)
  ((or (eq (car s) '+)(eq (car s) '-))(list (car s)
    (diff (cadr s) x)
    (diff (caddr s) x)
    ))
  ; ... and so on for multiplication, division, and basic functions
  ))

and following it with an appropriate simplifier, so you get rid of additions of 0, multiplying by 1, etc.

But the complex method, while completely numeric, has a certain magical quality. Instead of programming your computation F in double precision, do it in double precision complex. Then, if you need the derivative of the computation with respect to variable X, set the imaginary part of X to a very small number h, like 1e-100. Then do the calculation and get the result R. Now real(R) is the result you would normally get, and imag(R)/h = dF/dX to very high accuracy!

How does it work? Take the case of multiplying complex numbers:

(a+bi)(c+di) = ac + i(ad+bc) - bd

Now suppose the imaginary parts are all zero, except we want the derivative with respect to a. We set b to a very small number h. Now what do we get?

(a+hi)(c) = ac + hci

So the real part of this is ac, as you would expect, and the imaginary part, divided by h, is c, which is the derivative of ac with respect to a.

The same sort of reasoning seems to apply to all the differentiation rules.

Symbolic Differentiation is an impressive introduction to the subject-at least for non-specialist like me :) The code is written in C++ btw.

Look up automatic differentiation. There are tools for Python. Also, this.

If you are thinking of writing the differentiation program from scratch, without utilizing other libraries as help, then the algorithm/approach of computing the derivative of any algebraic equation I described in my blog will be helpful.

You can try creating a class that will represent a limit rigorously and then evaluate it for (f(x)-f(a))/(x-a) as x approaches a. That should give a pretty accurate value of the limit.

if you're using string as an input, you can separate individual terms using + or - char as a delimiter, which will give you individual terms. Now you can use power rule to solve for each term, say you have x^3 which using power rule will give you 3x^2, or suppose you have a more complicated term like a/(x^3) or a(x^-3), again you can single out other variables as a constant and now solving for x^-3 will give you -3a/(x^2). power rule alone should be enough, however it will require extensive use of the factorization.

Unless any already made library deriving it's quite complex because you need to parse and handle functions and expressions.

Deriving by itself it's an easy task, since it's mechanical and can be done algorithmically but you need a basic structure to store a function.