Logo by reallybigname - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Support us via Flattr FLATTR Link
 
*
Welcome, Guest. Please login or register. March 29, 2024, 02:00:04 PM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: [1]   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: The problem with finite-difference  (Read 1962 times)
Description: Why finite difference techniques will /never/ work for trigonometric functions.
0 Members and 1 Guest are viewing this topic.
TruthSerum
Guest
« on: June 29, 2014, 08:46:21 PM »

This shows the shortcomings of the finite difference technique

d/dx f(x) = [f(x+h) - f(x)] / h

You can never make your step size small enough to really capture the derivative before cancellation occurs: f(x+h) = f(x).

The figure makes this quite obvious. Here n_0 is what you want and n_1 is what you get.

Logged
Roquen
Iterator
*
Posts: 180


« Reply #1 on: July 01, 2014, 03:38:16 PM »

Dual numbers are fun.
Logged

All code submitted by me is in the public domain. (http://unlicense.org/)
TruthSerum
Guest
« Reply #2 on: July 01, 2014, 10:40:00 PM »

Automatic differentiation appears to be useful when you have functions that are known to be composed of other functions at runtime.

Let's say you want to acquire the derivative of the function f(g(x))

d/dx f(g(x)) = f'(g(x))g'(x) by the chain rule

Then instead of trying to compute the derivative by finite-difference

d/dx f(g(x)) = [f(g(x)) - f(g(x+h))] / h

you attack the individual functions:

Let u = g(x), then

f'(u) = [f(u) - f(u+h)] / h

and

g'(x) = [g(x) - g(x+h)] / h

so that

f'(u)g'(x) = [f(u) - f(u+h)] / h * [g(x) - g(x+h)] / h

put back u = g(x) to find that

d/dx f(g(x)) = [f(g(x)) - f(g(x)+h)] / h * [g(x) - g(x+h)] / h

For a practical example, let's compute the derivative of sin(cos(x))

Instead of [sin(cos(x)) - sin(cos(x+h))] / h

we now have d/dx sin(cos(x)) = [sin(cos(x)) - sin(cos(x)+h)] / h * [cos(x) - cos(x+h)] / h

and at no point did we have to calculate sin(cos(x+h)), so it should be more accurate, at the cost of extra operations.

And of course this works for any number of chained functions f_1(f_2(f_n(...))).

As Syntopia points out in his article on dual numbers, this could be implemented using overloaded operators in C++, and I could see how this would be useful in some cases, but you'll still get the original cancellation problem for functions with a large derivative.

This is unless you go down the route of having truncated Taylor series approximations available for every math function that your program uses, which is apparently what some of the libraries listed on the Wikipedia article are doing. If this is the case, why not have the full, exact, analytic derivative available instead?

I do not find the dual number framework especially elegant. In particular, they are not associative

((1/e)e)e = e, but (1/e)(e*e) = 0

Now how about symbolic differentiation? Does any fractal software implement this?
« Last Edit: July 02, 2014, 08:39:49 AM by TruthSerum » Logged
Roquen
Iterator
*
Posts: 180


« Reply #3 on: July 02, 2014, 12:05:16 PM »

Yeah AD is mostly for unknown functions at compile time made from known building blocks.  Your description doesn't match how dual numbers work however.  They're the same structure as Complex numbers, but i2=0 instead. 

A quick web-search gave me: https://cwzx.wordpress.com/2014/05/31/automatically-computing-the-derivatives-of-a-vector-field-using-dual-numbers/

Quote
I do not find the dual number framework especially elegant. In particular, they are not associative
Humm: I want to think all the identities of real valued functions hold.

Quote
This is unless you go down the route of having truncated Taylor series approximations...
Not needed for dual numbers, but that aside truncated Power series are terrible.  Something like minimax is way better.
Logged

All code submitted by me is in the public domain. (http://unlicense.org/)
Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #4 on: July 02, 2014, 03:58:33 PM »

I do not find the dual number framework especially elegant. In particular, they are not associative

((1/e)e)e = e, but (1/e)(e*e) = 0

Dual numbers are associative. But division is not well-defined for dual numbers. In particular (1/e) does not exist. See 'division' under: en.wikipedia.org/wiki/Dual_number

This shows the shortcomings of the finite difference technique

d/dx f(x) = [f(x+h) - f(x)] / h

You can never make your step size small enough to really capture the derivative before cancellation occurs: f(x+h) = f(x).

I am not sure I understand this? Are you refering to the inherent resolution limit of floating point numbers on a computer?
Logged
TruthSerum
Guest
« Reply #5 on: July 02, 2014, 06:14:25 PM »

Quote
Are you refering to the inherent resolution limit of floating point numbers on a computer?
Yes, of course it is exact, in theory, in the limit of h. Is this what you had in mind?

Quote
Something like minimax is way better.
Thanks, I'll look at this in future.
Logged
Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
What is the difference between members and guests Discuss Fractal Forums Jules Ruis 3 2183 Last post October 19, 2006, 10:04:45 AM
by heneganj
Split the Difference Mandelbulb3D Gallery lenord 0 1896 Last post October 29, 2011, 07:42:57 AM
by lenord
A difference of opinion Images Showcase (Rate My Fractal) thom 0 1715 Last post April 23, 2012, 08:12:58 PM
by thom
Difference between the terms Recursion and Iteration? General Discussion Chillheimer 5 3888 Last post January 20, 2015, 09:07:19 AM
by jehovajah
difference betwen m3p parameters and formulas Tutorials fmazelon 4 5772 Last post December 31, 2016, 04:18:20 AM
by 1Bryan1

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.322 seconds with 24 queries. (Pretty URLs adds 0.01s, 2q)