5 ms·

If you're interested in how to best calculate derivatives numerically using a finite difference rather than an infinitesimal, try having a look at the Wikipedia

by joe__f 4y ago

If you're interested in how to best calculate derivatives numerically using a finite difference rather than an infinitesimal, try having a look at the Wikipedia page on numerical differentiation. The punchline is that you can control the error in f'(x) much better if you use many displacements, ie. f'(x) = a1 f(x + b1 h) + a2 f(x + b2 h) + a3 f(x + b3 h)..., where the bi are chosen and the ai depend on the bi and h.

ogogmad 4y ago
Such methods are doomed. Consider the function f(x) = a sin(x / a) for very small a. Finite differencing methods would approximate f'(0) as 0 as f(x) is very close to 0, but the actual value of f'(0) is 1. Differentiation is a discontinuous operator, and cannot be accurately estimated using numerical methods. Only exact methods, which include the dual numbers, can produce accurate results.
- goldenkey 4y ago
  This is not true. Doomed is sensational. With proper perturbation analysis, one can choose an appropriate stencil and formula that has desired error bounds. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.3529&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72... https://www.google.com/search?q=finite+difference+stencil+derivative+sensitive+functions https://www.google.com/search?q=finite+difference+stencil+de...
  - ogogmad 4y ago
    Won't work on my example. Given any differentiable function f:R -> R, you can add a very small function to it that dramatically changes its derivative. But maybe this is too pathological to bother about. Over the complex numbers, this phenomenon doesn't happen. This can be shown, for instance, using the maximum modulus principle. You can therefore use Cauchy's Integral Formula to accurately estimate derivatives. But why not then just use the dual numbers?
    - goldenkey 4y ago
      I see your edit - fair point, analyticity does make complex functions much more well-behaved than their real counterparts. Still, this isn't a death knell like you previously claimed. Let's put up a bet. I win the bet if I provide a polynomial approximation of f'(x), R[f(x)], bounded by a maximum of 5% error, on the interval (-1, 1), by November 1st, 2022. If I fail to, or resign by then, you win. If I win, you agree to silence yourself for 1 year, regarding the split-complex and dual numbers, no longer touting them as a panacea. If I lose, I'll agree to make a YouTube video extolling the virtues of a mathematical subject of your choice, such as these types of numbers.
      - ogogmad 4y ago
        I don't fully understand your bet (and I don't take kindly to being asked to silence myself). I don't have time at the moment to craft an example. I might play around a bit with the edges of floating point. Differentiation is indeed discontinuous, so with enough determination I should be able to win such a bet. My function would probably be a sigmoid function which would go from -a to +a (for small a) over a very small interval [-b,b], where b can equal a. > If I win, you agree to silence yourself for 1 year, regarding the split-complex and dual numbers, no longer touting them as a panacea. I never said these numbers were a panacea. I said the dual numbers were an exact method. In this comment [1], which is what you're referring to, I said that the connection with other planar algebras was cute, but you mischaracterised what I said, which was rude. The algebras are pertinent because the article mentioned the dual numbers. [1] - https://news.ycombinator.com/item?id=32305644 https://news.ycombinator.com/item?id=32305644
        goldenkey 4y ago
        Fair enough. The bet I had in mind was the function you'd already stated as intractable: f(x) = a sin(x / a), the value of a is up to you, within reason (no IEEE fp shenanigans.) If you'd rather some other consequence than silencing, please suggest one. I am tired of hearing your panaceas. Symbolic differentiation is also exact but intractible. What makes the duals yield exactness in any way that isn't prone to the same finitude as other approximations? I see a lot of beasts but only one individual claiming to tame them with ease and exactness. If it comes across as rude, that's not my intent. Moreso to have some clarity and to have your claims be validated.
- joe__f 4y ago
  Finite difference derivatives are the basis for a range of numerical methods for solving differential equations. Given that these techniques underpin various areas of modern engineering, I'd say your statement that 'differentiation [...] cannot be accurately estimated using numerical methods' is demonstrably incorrect. I think you're fishing for something like 'there exist functions whose derivatives cannot be accurately estimated numerically'. Presumably some assumptions have been made which rule out such functions in using finite difference schemes in practical applications.
  - ogogmad 4y ago
    > Finite difference derivatives are the basis for a range of numerical methods for solving differential equations. I thought the basis usually involved rewriting the equation in terms of integrals, which can be estimated using quadrature. Numerical quadrature does not have the same problems as finite differencing because integration is a continuous operator. How accurate are these methods you're proposing? Could they be improved using autodiff (via the dual numbers or via reverse-mode autodiff)? Do you have a reference, so I can understand your point better? I'm sceptical and I'm not inclined to believe you yet.
    - joe__f 4y ago
      Well, there are many different methods and certainly some are based on numerical integration as you say. The most simple method based on finite difference derivatives is Euler's method which uses the scheme given by OP, with error O(h). This can be extended to Runge-Kutta methods which use a finite difference with n terms and have error O(h^(n-1)), and which to my knowledge are common and widely used to solve ODEs. You can read about Runge-Kutta methods on Wikipedia, and they also have a page on numerical methods for ODEs which gives an overview of different methods. I don't know what autodiff is, or how the dual numbers fit in here. I'd be interested to learn if you want to explain
      - ogogmad 4y ago
        > I don't know what autodiff is, or how the dual numbers fit in here. I'd be interested to learn if you want to explain Autodiff is an algorithm for computing derivatives in areas like Deep Learning. It's an exact method with two main variants -- forward mode and reverse mode -- differing in terms of when each of them is more efficient. It's implemented in widely-used numerical libraries like PyTorch and TensorFlow. The simplest implementations use the dual numbers to implement the forward mode variant. More sophisticated implementations implement the reverse mode variant. Wikipedia has plenty on it.

by joe__f 4y ago

ogogmad 4y ago

Such methods are doomed. Consider the function f(x) = a sin(x / a) for very small a. Finite differencing methods would approximate f'(0) as 0 as f(x) is very close to 0, but the actual value of f'(0) is 1. Differentiation is a discontinuous operator, and cannot be accurately estimated using numerical methods. Only exact methods, which include the dual numbers, can produce accurate results.

goldenkey 4y ago
This is not true. Doomed is sensational. With proper perturbation analysis, one can choose an appropriate stencil and formula that has desired error bounds. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.3529&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72... https://www.google.com/search?q=finite+difference+stencil+derivative+sensitive+functions https://www.google.com/search?q=finite+difference+stencil+de...
- ogogmad 4y ago
  Won't work on my example. Given any differentiable function f:R -> R, you can add a very small function to it that dramatically changes its derivative. But maybe this is too pathological to bother about. Over the complex numbers, this phenomenon doesn't happen. This can be shown, for instance, using the maximum modulus principle. You can therefore use Cauchy's Integral Formula to accurately estimate derivatives. But why not then just use the dual numbers?
  - goldenkey 4y ago
    I see your edit - fair point, analyticity does make complex functions much more well-behaved than their real counterparts. Still, this isn't a death knell like you previously claimed. Let's put up a bet. I win the bet if I provide a polynomial approximation of f'(x), R[f(x)], bounded by a maximum of 5% error, on the interval (-1, 1), by November 1st, 2022. If I fail to, or resign by then, you win. If I win, you agree to silence yourself for 1 year, regarding the split-complex and dual numbers, no longer touting them as a panacea. If I lose, I'll agree to make a YouTube video extolling the virtues of a mathematical subject of your choice, such as these types of numbers.
    - ogogmad 4y ago
      I don't fully understand your bet (and I don't take kindly to being asked to silence myself). I don't have time at the moment to craft an example. I might play around a bit with the edges of floating point. Differentiation is indeed discontinuous, so with enough determination I should be able to win such a bet. My function would probably be a sigmoid function which would go from -a to +a (for small a) over a very small interval [-b,b], where b can equal a. > If I win, you agree to silence yourself for 1 year, regarding the split-complex and dual numbers, no longer touting them as a panacea. I never said these numbers were a panacea. I said the dual numbers were an exact method. In this comment [1], which is what you're referring to, I said that the connection with other planar algebras was cute, but you mischaracterised what I said, which was rude. The algebras are pertinent because the article mentioned the dual numbers. [1] - https://news.ycombinator.com/item?id=32305644 https://news.ycombinator.com/item?id=32305644
      - goldenkey 4y ago
        Fair enough. The bet I had in mind was the function you'd already stated as intractable: f(x) = a sin(x / a), the value of a is up to you, within reason (no IEEE fp shenanigans.) If you'd rather some other consequence than silencing, please suggest one. I am tired of hearing your panaceas. Symbolic differentiation is also exact but intractible. What makes the duals yield exactness in any way that isn't prone to the same finitude as other approximations? I see a lot of beasts but only one individual claiming to tame them with ease and exactness. If it comes across as rude, that's not my intent. Moreso to have some clarity and to have your claims be validated.
joe__f 4y ago
Finite difference derivatives are the basis for a range of numerical methods for solving differential equations. Given that these techniques underpin various areas of modern engineering, I'd say your statement that 'differentiation [...] cannot be accurately estimated using numerical methods' is demonstrably incorrect. I think you're fishing for something like 'there exist functions whose derivatives cannot be accurately estimated numerically'. Presumably some assumptions have been made which rule out such functions in using finite difference schemes in practical applications.
- ogogmad 4y ago
  > Finite difference derivatives are the basis for a range of numerical methods for solving differential equations. I thought the basis usually involved rewriting the equation in terms of integrals, which can be estimated using quadrature. Numerical quadrature does not have the same problems as finite differencing because integration is a continuous operator. How accurate are these methods you're proposing? Could they be improved using autodiff (via the dual numbers or via reverse-mode autodiff)? Do you have a reference, so I can understand your point better? I'm sceptical and I'm not inclined to believe you yet.
  - joe__f 4y ago
    Well, there are many different methods and certainly some are based on numerical integration as you say. The most simple method based on finite difference derivatives is Euler's method which uses the scheme given by OP, with error O(h). This can be extended to Runge-Kutta methods which use a finite difference with n terms and have error O(h^(n-1)), and which to my knowledge are common and widely used to solve ODEs. You can read about Runge-Kutta methods on Wikipedia, and they also have a page on numerical methods for ODEs which gives an overview of different methods. I don't know what autodiff is, or how the dual numbers fit in here. I'd be interested to learn if you want to explain
    - ogogmad 4y ago
      > I don't know what autodiff is, or how the dual numbers fit in here. I'd be interested to learn if you want to explain Autodiff is an algorithm for computing derivatives in areas like Deep Learning. It's an exact method with two main variants -- forward mode and reverse mode -- differing in terms of when each of them is more efficient. It's implemented in widely-used numerical libraries like PyTorch and TensorFlow. The simplest implementations use the dual numbers to implement the forward mode variant. More sophisticated implementations implement the reverse mode variant. Wikipedia has plenty on it.