4 ms·

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 deriv

by 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'
      - ogogmad 4y ago
        > 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. Yes and no. It's worth taking into account that you can apply it to some functions defined using conditions and loops. For instance, if f is the sqrt function defined using Newton's method, then autodiff via the dual numbers will compute an estimate for f'(x) = 1/(2 * sqrt(x)). More explicitly: def f(a): x = 1 oldx = 2 threshold = 1e-10 while abs(x - oldx) < threshold: oldx, x = x, (x + a/x) / 2 return x ^ You can evaluate f on a dual number. This algorithm contains conditions and loops.
        joe__f 4y ago
        This was an interesting comment and I learnt something new, thank you. It does feel a little bit like you are proselytising the good news of the dual number autodiff method though, when you don't respond to questions on potential downsides and only add information about positives.
        ogogmad 4y ago
        I'm more familiar with using differentiation in optimisation, where autodiff seems like the best method. I'm also aware of the fact that the differentiation operator is discontinuous, which makes me sceptical of finite-differencing methods. I'm not familiar with numerically solving differential equations, but the natural connection between Runge-Kutta and finite differencing seems to be an interesting one.

by joe__f 4y ago

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'
    - ogogmad 4y ago
      > 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. Yes and no. It's worth taking into account that you can apply it to some functions defined using conditions and loops. For instance, if f is the sqrt function defined using Newton's method, then autodiff via the dual numbers will compute an estimate for f'(x) = 1/(2 * sqrt(x)). More explicitly: def f(a): x = 1 oldx = 2 threshold = 1e-10 while abs(x - oldx) < threshold: oldx, x = x, (x + a/x) / 2 return x ^ You can evaluate f on a dual number. This algorithm contains conditions and loops.
      - joe__f 4y ago
        This was an interesting comment and I learnt something new, thank you. It does feel a little bit like you are proselytising the good news of the dual number autodiff method though, when you don't respond to questions on potential downsides and only add information about positives.
        ogogmad 4y ago
        I'm more familiar with using differentiation in optimisation, where autodiff seems like the best method. I'm also aware of the fact that the differentiation operator is discontinuous, which makes me sceptical of finite-differencing methods. I'm not familiar with numerically solving differential equations, but the natural connection between Runge-Kutta and finite differencing seems to be an interesting one.