CODEWITHSUNDEEP
mathcalculusderivative
Dixtosa
Dixtosa

Reputation: 101

algorithm to find derivative

I'm writing program in Python and I need to find the derivative of a function (a function expressed as string).

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

Upvotes: 7

Views: 27417

Answers (6)

Escualo
Escualo

Reputation: 42082

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.

Upvotes: 5

Amit_dash_234
Amit_dash_234

Reputation: 101

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.

Upvotes: 0

Mike Dunlavey
Mike Dunlavey

Reputation: 40669

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.

Upvotes: 4

SalmonKiller
SalmonKiller

Reputation: 2203

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.

Upvotes: 0

ndim
ndim

Reputation: 37787

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.

Upvotes: 6

Jack
Jack

Reputation: 133587

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.

Upvotes: -2

Related Questions