8
$\begingroup$

I am solving a system of linear equations, $\underline {\dot x}=\underline A\cdot \underline x$, numerically. I have done this using the popular of methods of Euler and Runge-Kutta (RK). I have noticed quite a difference between the two in accuracy to the analytic solution. What is the reason for this?

$\endgroup$

migrated from physics.stackexchange.com Jul 14 '15 at 18:21

This question came from our site for active researchers, academics and students of physics.

  • 5
    $\begingroup$ For the same time step the two methods have vastly different accuracy and stability. Alas, this is mostly a mathematics question, and it would be better if you explain you level of understanding on Numerical Methods. $\endgroup$ – ja72 Jul 14 '15 at 18:15
  • $\begingroup$ My level with this subject is very limited. But thanks for sharing your opinion. $\endgroup$ – Udi Behar Jul 14 '15 at 18:20
17
$\begingroup$

First thing, you could have mentioned, what RK method you have used. Here is a brief introduction to RK methods and Euler method, working, there merits and demerits.

Euler method

Euler's method is first order method. It is a straight-forward method that estimates the next point based on the rate of change at the current point and it is easy to code. It is a single step method. Notably, Forward Euler's method is unconditionally unstable for un-damped oscillating systems (such as a spring-mass system or wave equations) in space desctretization. For complex problems and/or boundary condition it may fail. It can be used for basic numerical analysis. This method is not commonly used for spatial discretization but some times used in time discretization. This scheme is not recommended for hyperbolic differential equation because this is more diffusive. Order of convergence of this scheme with grid refinement is very poor. Extending Euler method to higher order method is easy and straight forward.

RK methods:

Runge-Kutta methods are actually a family of schemes derived in a specific style. You can refer this link to get a basic idea of RK methods: http://web.mit.edu/10.001/Web/Course_Notes/Differential_Equations_Notes/node5.html

The forward Euler method is actually the simplest RK method (1 stage, first order). Higher order accurate RK methods are multi-stage because they involve slope calculations at multiple steps at or between the current and next discrete time values. The next value of the dependent variable is calculated by taking a weighted average of these multiple stages based on a Taylor series approximation of the solution. The weights in this weighted average are derived by solving non-linear algebraic equations which are formed by requiring cancellation of error terms in the Taylor series. Developing higher order RK methods is tedious and difficult without using symbolic tools for computation.

The most popular RK method is RK4 since it offers a good balance between order of accuracy and cost of computation. RK4 is the highest order explicit Runge-Kutta method that requires the same number of steps as the order of accuracy (i.e. RK1=1 stage, RK2=2 stages, RK3=3 stages, RK4=4 stages, RK5=6 stages, ...). Beyond fourth order the RK methods become relatively more expensive to compute.

Answer

  • Usually error in Euler method is higher than higher order RK method (RK2, RK3, etc.), because truncation error in higher order methods is less compared to Euler method.

  • In some of the beginner level literature in numerical methods, it is loosely mentioned that higher order methods (say, RK4) give less error than lower order method (say, Euler method). Most of the time this is true, but not all the time. This property depends on the mesh and initial condition and differential equations you have considered.

  • If the exact solution to the differential equation is a polynomial of order $n$, it will be solved exactly by an $n$-th Runge-Kutta method. For example, forward Euler will be exact if the solution is a line. RK4 will be exact if the solution is a polynomial of degree 4 or less.

  • Initial "absolute maximum difference error" in RK4 method is equal (or) higher than Euler method for coarse grid and reduces with refining grid for problems with shorter waves relative to grid. Because convergence rate of RK4 method is more than Euler. Please note that coarseness or fineness of grid is completely based on differential equation, initial condition and numerical scheme. Please refer following link for more details. Though that is based on differentiation, we can make a relative comparison between time numerical integration and differentiation as long as the "numerical integration" is stable.

You can try this experiment in your code with different differential equations, different number of grids with Euler and RK4 if you have enough time. Order of convergence of scheme can be find out by calculating slope of plot - $\log(\mathrm{error})$ vs $\log(\mathrm{grid\ size})$.

$\endgroup$
  • 5
    $\begingroup$ It's great to see other people who recognize that higher order doesn't always mean lower error, just faster convergence. That's such an important point, but so many seem to miss it! $\endgroup$ – tpg2114 Jul 15 '15 at 2:55
  • $\begingroup$ Yes sir, I came to know this from one of my professors lecture and verified this in one of my assignments. I think it is missing because, most of the time we work in fine mesh and relatively non-stiff differential equations. $\endgroup$ – AGN Jul 15 '15 at 3:14
  • $\begingroup$ Very nice answer overall. I edited to correct a couple points and added some details. Hopefully you don't mind. $\endgroup$ – Doug Lipinski Jul 15 '15 at 14:56
  • 1
    $\begingroup$ @ Doug, Thank you for spending your valuable time in this. My point is simple that is lower order methods are accurate on course grid and higher order methods are accurate in fine grid. Why I have mentioned, (Please note that coarseness or fineness of grid is completely based on differential equation, initial condition and numerical scheme) in my answer is truncation error in schemes depends on grid size and magnitude of order of derivative of function we truncated (Indirectly this may be related to stiffness of ODE). $\endgroup$ – AGN Jul 16 '15 at 2:29
  • $\begingroup$ Sorry, I didn't see your comment until now. People only get notifications if you @ reply to their full user name (or if they're the post owner). Start typing @Dou... and it should offer to autocomplete for you. I've posted an answer at your other question. $\endgroup$ – Doug Lipinski Jul 16 '15 at 18:35
8
$\begingroup$

The Euler method does not take into account the curvature of the solution, so it tends to give different results depending on the step size. RK, depending on the order, takes into account the curvature. And this makes the estimated "next step" more accurate. Basically, if you are pretending a straight line is a good approximation of a curve (Euler) you will always be overshooting your solution. But if you take account of the curvature (RK) you can follow the curve.

Compare with the famous hockey quote (Gretzky): Euler skates to where the puck is; Runge-Kutta skates to where the puck is going to be.

I recommend you read about these algorithms. You can start with Wikipedia articles here and here.

$\endgroup$
5
$\begingroup$

Forgive me for adding a me-too answer, but I just couldn't resist including this page from Press, et al: "Numerical Recipes in C":

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Very nicely complements the other answer. That book is a classic. Although it does show its FORTRAN roots by sometimes starting arrays with an index of 1. $\endgroup$ – Floris Jul 15 '15 at 20:20
  • 2
    $\begingroup$ @Floris: I once worked with a guy from northern Italy, tall, hooked nose, thinning blond hair and all, named Giuseppe. I was kvetching about why people didn't convert to a modern language, like C :) He rolls to me in this deep, imperious voice, "MIke, Fortran is like Rock and Roll. It will never die." $\endgroup$ – Mike Dunlavey Jul 15 '15 at 21:56
  • 1
    $\begingroup$ i fit about half of your description of Giuseppe... :-) $\endgroup$ – Floris Jul 16 '15 at 11:47
4
$\begingroup$

Basically the reason they have different levels of accuracy is in the way they are derived. The (I'm assuming forward)Euler method is first order and can be derived a number of ways. Most easily from Taylor's theroem. In that method, only the second order term is retained thereby making the error first order.

Runge kutta methods on the other hand are staged and have very specifically chosen coefficients to "cancel" out several orders of error terms. Rk4 is fourth order since the zeroth, first, second, third order error terms cancel out by the choice of stage coefficients. The derivation of these coefficients is not very difficult and can probably be found on wikipedia if you're interested in seeing it.

$\endgroup$

Your Answer

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