Runge-Kutta method with c<1

2011-04-09T16:41:03Z

In trying to solve an ODE $y'=f(y,t)$ with a function f that is discontinuous at a subset (codim=1) of $\mathbb R^n$, I am looking for a Runge-Kutta ODE method whose stages do not evaluate $f(x,t)$ at $t+\Delta t$. So for example midpoint method:

$k_1=f(x,t)$

$k_2=f(x+k_1/2,t+\Delta t/2)$

Would be an acceptable 2nd order method.

Its Butcher block is

0   |
1/2 | 1
---------
      0  1

(If there's a nice way to typeset tables here, please let me know...)

the $c$ vector is the one consisting of 0 and 1/2 and as you see it is less than 1 in this case. I would like to find an explicit higher-order method that also has this property. All the higher-order (explicit) methods I have found seem to have at-least one element of $c$ equal to 1.

To summarize, my question is:

Is there a known high-order (4 is enough) explicit Runge-Kutta method that does not evaluate the ODE at the end of the timestep?

Answer by lvb for Runge-Kutta method with c<1

2011-04-09T17:22:06Z

I understand that you're considering a stiff IVP for an ODE, so you're probably looking for implicit Runge-Kutta methods.

Concerning your first question - yes, methods of high order which do not evaluate your right hand side at the end of each time step exist and there is lots of literature about them. You might wish to take a look at Solving ordinary differential equations II by Hairer and Wanner and search for Gauss- or Radau-methods.

Concerning your second question you can either use the evaluations of $f$ you compute in each step and interpolation in order to get a reasonably accurate approximation of your solution $y$ at arbitrary points or you can dive into the concept of dense output for Runge-Kutta methods, which is given a quite detailed account of in Solving ordinary differential equations I by Hairer, Norsett, Wanner.

Edit: An explicit RK-method of order 4 with $c<1$, assuming the usual equations $c_i=\sum_{j=1}^{i-1}a_{ij}$, necessarily has at least 5 stages whereas one can construct methods of order 4 with 4 stages if one allows $c_4=1$. I don't know whether methods of order 4 satisfying your conditions have been constructed so far. I suppose you're on your own here. There is, however, a 3-stage method of order 3 by Heun with $c=(0,1/3,2/3)$, $a_{2,1}=1/3$, $a_{3,2}=2/3$, $a_{ij}=0$ else and $b=(1/4,0,3/4)$ in Chapter II.1 of Solving ordinary differential equations I.

Also, in the case of a right hand side $f$ with discontinuities multistep methods with adaptive order and stepsize control are usually more efficient than one-step RK-methods. And actually I have difficulties to see to what extent $c<1$ might be helpful; a robust automatic step size control should be able to deal with the discontinuities either way.

Runge-Kutta method with c<1 - MathOverflow

Runge-Kutta method with c<1

Answer by lvb for Runge-Kutta method with c<1