2
$\begingroup$

I was told about an algorithm to solve ODEs which I thought was very clever. I am sure its not something new. It works by discarding the $\mathcal{O}(h^2)$-term from the usual formula for computing the second derivative:

$$f''_i = \frac{f_{i-1} + f_{i+1} - 2f_{i}}{h^2} + \mathcal{O}(h^2), \qquad i = 0,1,2,\cdots,N$$

one can rewrite the equations for the derivatives for all $i$, as a set of linear equations, then use smart Gauss elimination from linear algebra to find expression for $f$ with exactly $5N$ floating point operations.

(1) Does this method already have a name?

(2) Should I be excited about this algorithm? Is this a particularly good method? Or are there other very different algorithms for solving ODEs which are much better?

$\endgroup$
3
$\begingroup$

This is essentially the (implicit) Finite Difference Method. There are different variations based on the discretization (implicit, explicit, Crank-Nicolson, leap-frog, etc). Some better than others. For the implicit approach, you can use Thomas Algorithm (modified Gaussian elimination) to solve the tridiagonal system. But you can also use Cyclic Reduction (or one of its variations) which allows you to solve the system in parallel on GPUs and clusters. Much much larger solvers rely on Krylov subspace methods. There are other ODE/PDE solves like Method of Lines, Finite Element Method, and many many others that you'd encounter in a good text on Numerical Analysis (e.g., Kincaid, Cheney).

$\endgroup$
3
$\begingroup$

What you have there is the central difference approximation to the second derivative. The Wikipedia article on finite differences explains this pretty well.

Of course, this isn't a method as such; that depends on the exact problem being solved. If this were an initial value problem, then a simple rearrangement of this equation is typically known as Störmer–Verlet integration (or just Verlet integration depending on whom you ask).

If it was a bounding-value problem, then this discretisation of the derivative gives you a tridiagonal system, and you don't have a complete "method" until you have a method to solve it. A small modification of Gaussian elimination is quite efficient on matrices of this form.

As to competitors... that's a very long discussion. Any introductory textbook on numerical analysis should give you a good start.

$\endgroup$
  • $\begingroup$ This tridiagonal form - isn't it about TDMA - Thomas algorithm? $\endgroup$ – Evil Sep 1 '16 at 23:45
  • $\begingroup$ Uhm... probably, yes. $\endgroup$ – Pseudonym Sep 2 '16 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.