Hacker News Reader

Comment by jordigh | Hacker News Reader

Am I missing something or is this begging the question?

For any function that is not a combination of polynomials, you need to have its Taylor expansion up to the desired order of derivatives, so you can't just take an "arbitrary" function and use this method to compute its derivative in exact arithmetic.

So for anything other than polynomials, you just reword the problem of finding exact derivatives to finding exact Taylor series, and in order to find Taylor series in most cases, you have to differentiate or express your function in terms of the Taylor series of known functions.

Edit: Indeed, take the only non-polynomial example here, a rational function (division by a polynomial). In order to make this work, you have to know the geometric series expansion of 1/(1-x). For each function that you want to differentiate this way, you have to keep adding more such pre-computed Taylor expansions.

View on HN

The typical approach is to provide overloaded versions of primitive functions (generally addition, multiplication, subtraction, division, powers, trig and hyperbolic trig functions, exponential and logarithm) for which you explicitly tell the program what the first N terms in the Taylor series are.

The magic is that you also tell it how to compute Taylor series of function compositions, if the Taylor series of the functions being composed are already known - then any arbitrary function composed out the primitive functions can have its Taylor series computed automatically!

For your example, the function 1/(1-x) is the composition of

    x -> -x
    x -> 1+x
    x -> 1/x

and so its Taylor series is already known as long as you have already defined negation, addition and reciprocation.

So instead of implementing a full CAS that knows linearity of differentiation along with the product and chain rules, you implement something that for a little less computation can give you exact derivatives at any given point. Am I understanding this correctly?

Yes, that's more or less it. The system you implement still knows about linearity of differentiation, the product rule, chain rule etc but it's not a full blown CAS. It can't give you the symbolic derivative of a function (although I guess you can technically apply AD to any numeric type, including a symbolic type..) but it can compute the numerical value of the derivatives at arbitrary points.

You're right, it is begging the question, for any simple function, you basically have to tell it what all the derivatives are for it to work.

The power of this technique is that it handles the product rule and chain rule for you, so composition and multiplication of functions work automatically without extra work.

For the case of 1/(1-x), you only need to tell it the derivatives (wrt x) of

f(x, a) = x * a

g(x, a) = x + a

h(x) = 1/x

Then it automatically knows how to compute the derivatives of h(g(f(x, -1), 1)).

No, really you don't need Taylor series at all; see for example Conal Elliott's "Beautiful Differentiation"[1], which shows how to handle arbitrary derivatives of multidimensional functions and never uses Taylor series for anything; all you need to know is that d/dx sin(x) = cos(x), etc. Just as a warning, Conal's paper is quite dense and is probably not a good introduction.

[1] http://conal.net/papers/beautiful-differentiation/

But knowing that sin' = cos is again begging the question, just rephrasing it back.

I think I get it, though. You can get away with simplifying intermediate steps of a differentiation computation if you only care about the value of the function at a single point.

I am not a mathematician, but I don't think this is actually begging the question.

> you can't just take an arbitrary function and use this method

Actually, you can, AFAIK. The relation f(x + E) = f(x) + f'(x)E still holds.

If we try this method with a rational function:

    f(x) = (x - 1)/(x - 2)

    f(x + E)
     = (x + E - 1) / (x + E - 2)
     = (x + E - 1)(x - E - 2) / ((x + E - 2)(x - E - 2))
     = (x^2 - x E - 2 x + x E - E^2 - 2 E - x + E + 2) / (x^2 - x E - 2 x + x E - E^2 - 2 E - 2 x + 2 E + 4)
     = (x^2 - 3 x + 2 - E) / (x^2 - 4 x + 4)
     = (x^2 - 3 x + 2) / (x^2 - 4 x + 4) - (1 / (x^2 - 4 x + 4)) E
     = (x - 1) / (x - 2) - (1 / (x - 2)^2) E

    f'(x) = -1 / (x - 2)^2

since

    f(x + E) = f(x) + f'(x) E

Edit to add: the key idea here being that no knowledge of differentiation is needed, just tricks for manipulating expressions involving x and E until they are in normal form.

Reply on news.ycombinator.com