Runge-Kutta method with c<1 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T16:37:30Z http://mathoverflow.net/feeds/question/61148 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61148/runge-kutta-method-with-c1 Runge-Kutta method with c<1 Yossi Farjoun 2011-04-09T16:41:03Z 2011-04-11T18:38:33Z <p>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:</p> <p>$k_1=f(x,t)$</p> <p>$k_2=f(x+k_1/2,t+\Delta t/2)$</p> <p>Would be an acceptable 2nd order method. </p> <p>Its Butcher block is</p> <pre><code>0 | 1/2 | 1 --------- 0 1 </code></pre> <p>(If there's a nice way to typeset tables here, please let me know...)</p> <p>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 <strong>explicit</strong> 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. </p> <hr> <p>To summarize, my question is:</p> <blockquote> <ol> <li>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?</li> </ol> </blockquote> http://mathoverflow.net/questions/61148/runge-kutta-method-with-c1/61152#61152 Answer by lvb for Runge-Kutta method with c<1 lvb 2011-04-09T17:22:06Z 2011-04-11T18:38:33Z <p>I understand that you're considering a <em>stiff</em> IVP for an ODE, so you're probably looking for <em>implicit</em> Runge-Kutta methods.</p> <p>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 <a href="http://books.google.com/books?id=zZSv3acps1QC&amp;printsec=frontcover&amp;dq=hairer+wanner+solving+ordinary+differential+equations&amp;hl=de&amp;ei=0JGgTZDtOsv14QaY98G5Aw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=2&amp;ved=0CDsQ6AEwAQ#v=onepage&amp;q&amp;f=false" rel="nofollow">Solving ordinary differential equations II</a> by Hairer and Wanner and search for <em>Gauss</em>- or <em>Radau-methods</em>.</p> <p>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 <em>dense output</em> for Runge-Kutta methods, which is given a quite detailed account of in <a href="http://books.google.com/books?hl=de&amp;lr=&amp;id=F93u7VcSRyYC&amp;oi=fnd&amp;pg=PA1&amp;dq=hairer+wanner+solving+ordinary+differential+equations&amp;ots=3nM5PkNCQ_&amp;sig=2qJo0huaBke571uUBWBL1olL4Rs#v=onepage&amp;q&amp;f=false" rel="nofollow">Solving ordinary differential equations I</a> by Hairer, Norsett, Wanner.</p> <p><strong>Edit:</strong> An explicit RK-method of order 4 with $c&lt;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 <em>Solving ordinary differential equations I</em>.</p> <p>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&lt;1$ might be helpful; a robust automatic step size control should be able to deal with the discontinuities either way.</p>