4 ms·

Finite difference derivatives are the basis for a range of numerical methods for solving differential equations. Given that these techniques underpin various ar

by 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.
    - joe__f 4y ago
      Ok I had a look at wiki and it's clear to me how the dual numbers encode differentiation and the theory behind how autodiff works. How do the two fit together? I didn't follow that part
      - ogogmad 4y ago
        You define a dual number type in your programming language of choice, and overload the operators +, -, *, /, <, >, sin, cos, etc. Then you take a function which computes a numerical function f which is defined using the previous operations, and simply evaluate them on a dual number. It's "automatic" because, assuming the right programming language, a user-defined numerical function will often be able to take in many different kinds of numbers, like complex numbers, real numbers, arbitrary precision floats, and even user-defined classes like the dual numbers.
        joe__f 4y ago
        Ah thankyou, it was so neat and automatic that I missed the punchline. It looks like you'll always calculate f and f' together and it's not possible to calculate only f' though? Seems like this could waste time in some applications? I can see how this is the solution to the problem of calculating the numerical derivative of a known function composed of finite combinations of rational functions and a set of specified functions, elementary or special. I don't see how it's relevant to solving ODEs numerically though, given that in that case you don't know the functional form of f or f'

by joe__f 4y ago

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.
  - joe__f 4y ago
    Ok I had a look at wiki and it's clear to me how the dual numbers encode differentiation and the theory behind how autodiff works. How do the two fit together? I didn't follow that part
    - ogogmad 4y ago
      You define a dual number type in your programming language of choice, and overload the operators +, -, *, /, <, >, sin, cos, etc. Then you take a function which computes a numerical function f which is defined using the previous operations, and simply evaluate them on a dual number. It's "automatic" because, assuming the right programming language, a user-defined numerical function will often be able to take in many different kinds of numbers, like complex numbers, real numbers, arbitrary precision floats, and even user-defined classes like the dual numbers.
      - joe__f 4y ago
        Ah thankyou, it was so neat and automatic that I missed the punchline. It looks like you'll always calculate f and f' together and it's not possible to calculate only f' though? Seems like this could waste time in some applications? I can see how this is the solution to the problem of calculating the numerical derivative of a known function composed of finite combinations of rational functions and a set of specified functions, elementary or special. I don't see how it's relevant to solving ODEs numerically though, given that in that case you don't know the functional form of f or f'