Description

Your task in this kata is to solve numerically an ordinary differential equation. This is an equation of the form ${\displaystyle \frac{dy}{dx}}=f(x,y)\backslash dfrac\{dy\}\{dx\}\; =\; f(x,\; y)$ with initial condition $y(0)=x_{0}y(0)\; =\; x\_0$.

Motivation and Euler's method

The method you will have to use is Runge-Kutta method of order 4. The Runge-Kutta methods are generalization of Euler's method, which solves a differential equation numerically by extending the trajectory from point $(x_0,y_0)(x\_0,\; y\_0)$ by small steps with intervals h with the below-mentioned formula:

This directly follows from the fact, that

${\displaystyle f(x,y(x))=\underset{h\to 0}{\lim }\frac{y(x+h)-y(x)}{(x+h)-x}}\backslash displaystyle\; f(x,\; y(x))\; =\; \backslash lim\_\{h\; \backslash to\; 0\}\backslash dfrac\{y(x+h)\; -\; y(x)\}\; \{(x\; +\; h)\; -\; x\}$

which is equivalent to the geometrical meaning of derivative (a tangent of $y(x)y(x)$ at point $xx$).

By making a step arbitrary small, one may theoretically make the computation arbitrary precise. However, in practice the step is bounded by smallest floating point number, and this yields quite imprecise results, because residue in Euler's method is accumulated over a number of steps (which is usually counted in thousands/millions).

In order to reduce the residue as much as possible, one may use a generalization methods, i.e. a family of Runge-Kutta methods. An RK method performs more computations on each step, but also approximates more terms in Taylor decomposition of function $f(x,y)f(x,\; y)$ and thus produces overall smaller residue. The order of RK method corresponds to precision and to a number of calculations on each step.

Further reading: Wikipedia

The actual Runge-Kutta 4

We will be using the most common RK method of order 4. It is given by formula

$y(x+h)=y(x)+{\displaystyle \frac{k_1+2k_2+2k_3+k_4}{6}}y(x+h)\; =\; y(x)\; +\; \backslash dfrac\{k\_1\; +\; 2k\_2\; +\; 2k\_3\; +\; k\_4\}\{6\}$

where

The task

You will be given the following inputs:

• x0, y0 : the initial point
• h: step, will be >0
• f(x,y): the value of derivative dy/dx at point (x,y)
• x1: the x value for the final point. (x1 > x0)

Execute numerical integration with Runge-Kutta 4 and return the following:

• An array of y values for xs from x0 to x1 inclusive separated by step h. You should calculate the value of y for each integer k >= 0 such that x0 + k * h <= x1.

Float outputs are compared to reference with tolerance 1e-9.